Struct EGraph

pub struct EGraph {
    pub parser: Parser,
    pub fact_directory: Option<PathBuf>,
    pub seminaive: bool,
    /* private fields */
}

The main interface for an e-graph in egglog.

An EGraph maintains a collection of equivalence classes of terms and provides operations for adding facts, running rules, and extracting optimal terms.

Examples

use egglog::*;

let mut egraph = EGraph::default();
egraph.parse_and_run_program(None, "(datatype Math (Num i64) (Add Math Math))").unwrap();

Fields

parser: Parser

fact_directory: Option<PathBuf>

seminaive: bool

Implementations

impl EGraph

pub fn repl(&mut self, mode: RunMode) -> Result<()>

Start a Read-Eval-Print Loop with standard I/O.

pub fn repl_with<R, W>( &mut self, input: R, output: W, mode: RunMode, is_terminal: bool, ) -> Result<()>

where R: Read, W: Write,

Start a Read-Eval-Print Loop with the given input and output channel.

impl EGraph

pub fn add_scheduler(&mut self, scheduler: Box<dyn Scheduler>) -> SchedulerId

Register a new scheduler and return its id.

pub fn remove_scheduler( &mut self, scheduler_id: SchedulerId, ) -> Option<Box<dyn Scheduler>>

Removes a scheduler

pub fn step_rules_with_scheduler( &mut self, scheduler_id: SchedulerId, ruleset: &str, ) -> Result<RunReport, Error>

Runs a ruleset for one iteration using the given ruleset

impl EGraph

pub fn serialize(&self, config: SerializeConfig) -> SerializeOutput

Serialize the egraph into a format that can be read by the egraph-serialize crate.

There are multiple different semantically valid ways to do this. This is how this implementation does it:

For node costs:

• Primitives: 1.0
• Function without costs: 1.0
• Function with costs: the cost
• Omitted nodes: infinite

For node IDs:

• Functions: Function name + hash of input values
• Args which are eq sorts: Choose one ID from the e-class, distribute roughly evenly.
• Args and outputs values which are primitives: Sort name + hash of value

For e-classes IDs:

• tag and value of canonicalized value

This is to achieve the following properties:

• Equivalent primitive values will show up once in the e-graph.
• Functions which return primitive values will be added to the e-class of that value.
• Nodes will have consistant IDs throughout execution of e-graph (used for animating changes in the visualization)
• Edges in the visualization will be well distributed (used for animating changes in the visualization) (Note that this will be changed in <https://github.com/egraphs-good/egglog/pull/158> so that edges point to exact nodes instead of looking up the e-class)

pub fn value_to_class_id(&self, sort: &ArcSort, value: Value) -> ClassId

Gets the serialized class ID for a value.

pub fn class_id_to_value(&self, eclass_id: &ClassId) -> Value

Gets the value for a serialized class ID.

pub fn to_node_id(&self, sort: Option<&ArcSort>, node: SerializedNode) -> NodeId

Gets the serialized node ID for the primitive, omitted, or function value.

pub fn from_node_id(&self, node_id: &NodeId) -> SerializedNode

Gets the serialized node for the node ID.

impl EGraph

pub fn add_sort<S: Sort + 'static>( &mut self, sort: S, span: Span, ) -> Result<(), TypeError>

Add a user-defined sort to the e-graph.

Also look at prelude::add_base_sort for a convenience method for adding user-defined sorts

pub fn declare_sort( &mut self, name: impl Into<String>, presort_and_args: &Option<(String, Vec<Expr>)>, span: Span, ) -> Result<(), TypeError>

Declare a sort. This corresponds to the sort keyword in egglog. It can either declares a new EqSort if presort_and_args is not provided, or an instantiation of a presort (e.g., containers like Vec).

pub fn add_arcsort( &mut self, sort: ArcSort, span: Span, ) -> Result<(), TypeError>

Add a user-defined sort to the e-graph.

pub fn add_primitive<T>(&mut self, x: T)

where T: Clone + Primitive + Send + Sync + 'static,

Add a user-defined primitive

impl EGraph

pub fn add_command( &mut self, name: String, command: Arc<dyn UserDefinedCommand>, ) -> Result<(), Error>

Add a user-defined command to the e-graph

pub fn push(&mut self)

Push a snapshot of the e-graph into the stack.

See EGraph::pop.

pub fn pop(&mut self) -> Result<(), Error>

Pop the current egraph off the stack, replacing it with the previously pushed egraph. It preserves the run report and messages from the popped egraph.

pub fn function_to_dag( &self, sym: &str, n: usize, include_output: bool, ) -> Result<(Vec<Term>, Option<Vec<Term>>, TermDag), Error>

Extract rows of a table using the default cost model with name sym The include_output parameter controls whether the output column is always extracted For functions, the output column is usually useful For constructors and relations, the output column can be ignored

pub fn print_function( &mut self, sym: &str, n: Option<usize>, file: Option<File>, mode: PrintFunctionMode, ) -> Result<Option<CommandOutput>, Error>

Print up to n the tuples in a given function. Print all tuples if n is not provided.

pub fn print_size(&mut self, sym: Option<&str>) -> Result<CommandOutput, Error>

Print the size of a function. If no function name is provided, print the size of all functions in “name: len” pairs.

pub fn extract_value( &self, sort: &ArcSort, value: Value, ) -> Result<(TermDag, Term, DefaultCost), Error>

Extract a value to a TermDag and Term in the TermDag using the default cost model. See also EGraph::extract_value_with_cost_model for more control.

pub fn extract_value_with_cost_model<CM: CostModel<DefaultCost> + 'static>( &self, sort: &ArcSort, value: Value, cost_model: CM, ) -> Result<(TermDag, Term, DefaultCost), Error>

Extract a value to a TermDag and Term in the TermDag. Note that the TermDag may contain a superset of the nodes in the Term. See also EGraph::extract_value_to_string for convenience.

pub fn extract_value_to_string( &self, sort: &ArcSort, value: Value, ) -> Result<(String, DefaultCost), Error>

Extract a value to a string for printing. See also EGraph::extract_value for more control.

pub fn step_rules(&mut self, ruleset: &str) -> Result<RunReport, Error>

Runs a ruleset for an iteration.

This applies every match it finds (under semi-naive). See EGraph::step_rules_with_scheduler for more fine-grained control.

This will return an error if an egglog primitive returns None in an action.

pub fn eval_expr(&mut self, expr: &Expr) -> Result<(ArcSort, Value), Error>

Evaluates an expression, returns the sort of the expression and the evaluation result.

pub fn run_program( &mut self, program: Vec<Command>, ) -> Result<Vec<CommandOutput>, Error>

Run a program, represented as an AST. Return a list of messages.

pub fn resugar_program( &mut self, filename: Option<String>, input: &str, ) -> Result<Vec<String>, Error>

pub fn parse_and_run_program( &mut self, filename: Option<String>, input: &str, ) -> Result<Vec<CommandOutput>, Error>

Takes a source program input, parses it, runs it, and returns a list of messages.

filename is an optional argument to indicate the source of the program for error reporting. If filename is None, a default name will be used.

pub fn num_tuples(&self) -> usize

Get the number of tuples in the database.

pub fn get_sort<S: Sort>(&self) -> Arc<S>

Returns a sort based on the type.

pub fn get_sort_by<S: Sort>(&self, f: impl Fn(&Arc<S>) -> bool) -> Arc<S>

Returns a sort that satisfies the type and predicate.

pub fn get_sorts<S: Sort>(&self) -> Vec<Arc<S>>

Returns all sorts based on the type.

pub fn get_sorts_by<S: Sort>(&self, f: impl Fn(&Arc<S>) -> bool) -> Vec<Arc<S>>

Returns all sorts that satisfy the type and predicate.

pub fn get_arcsort_by(&self, f: impl Fn(&ArcSort) -> bool) -> ArcSort

Returns a sort based on the predicate.

pub fn get_arcsorts_by(&self, f: impl Fn(&ArcSort) -> bool) -> Vec<ArcSort>

Returns all sorts that satisfy the predicate.

pub fn get_sort_by_name(&self, sym: &str) -> Option<&ArcSort>

Returns the sort with the given name if it exists.

pub fn get_overall_run_report(&self) -> &RunReport

Gets the overall run report and returns it.

pub fn value_to_base<T: BaseValue>(&self, x: Value) -> T

Convert from an egglog value to a Rust type.

pub fn base_to_value<T: BaseValue>(&self, x: T) -> Value

Convert from a Rust type to an egglog value.

pub fn value_to_container<T: ContainerValue>( &self, x: Value, ) -> Option<impl Deref<Target = T>>

Convert from an egglog value to a reference of a Rust container type.

Returns None if the value cannot be converted to the requested container type.

Warning: The return type of this function may contain lock guards. Attempts to modify the contents of the containers database may deadlock if the given guard has not been dropped.

pub fn container_to_value<T: ContainerValue>(&mut self, x: T) -> Value

Convert from a Rust container type to an egglog value.

pub fn get_size(&self, func: &str) -> usize

Get the size of a function in the e-graph.

panics if the function does not exist.

pub fn lookup_function(&self, name: &str, key: &[Value]) -> Option<Value>

Lookup a tuple in afunction in the e-graph.

Returns None if the tuple does not exist. panics if the function does not exist.

pub fn get_function(&self, name: &str) -> Option<&Function>

Get a function by name.

Returns None if the function does not exist.

pub fn set_report_level(&mut self, level: ReportLevel)

pub fn dump_debug_info(&self)

A basic method for dumping the state of the database to log::info!.

For large tables, this is unlikely to give particularly useful output.

pub fn get_canonical_value(&self, val: Value, sort: &ArcSort) -> Value

Get the canonical representation for val based on type.

Trait Implementations

impl Clone for EGraph

fn clone(&self) -> EGraph

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Default for EGraph

fn default() -> Self

Returns the “default value” for a type.