Struct EGraph 

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

Fields

parser: Parser

fact_directory: Option<PathBuf>

seminaive: bool

no_decomp: 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 extract_value( &self, sort: &ArcSort, value: Value, ) -> Result<(TermDag, TermId, DefaultCost), Error>

Extract a value to a TermDag and TermId 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, TermId, DefaultCost), Error>

Extract a value to a TermDag and TermId in the TermDag. Note that the TermDag may contain a superset of the nodes referenced by the returned TermId. 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 function_to_dag( &self, sym: &str, n: usize, include_output: bool, ) -> Result<(Vec<TermId>, Option<Vec<TermId>>, TermDag), Error>

For constructors and relations, the output column can be ignored

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_pure_primitive<T>( &mut self, x: T, validator: Option<PrimitiveValidator>, )

where T: PurePrim + Clone,

Register a PurePrim. Pass None for the validator if not using the proof checker.

Pick the trait whose state wrapper matches the body’s needs: PurePrim for pure ops, WritePrim for writes, ReadPrim for table reads, FullPrim for both. The Rust type checker enforces the body only uses methods the chosen state allows.

pub fn add_write_primitive<T>( &mut self, x: T, validator: Option<PrimitiveValidator>, )

where T: WritePrim + Clone,

Register a WritePrim. Pass None for the validator if not using the proof checker.

pub fn add_read_primitive<T>( &mut self, x: T, validator: Option<PrimitiveValidator>, )

where T: ReadPrim + Clone,

Register a ReadPrim. Pass None for the validator if not using the proof checker.

pub fn add_full_primitive<T>( &mut self, x: T, validator: Option<PrimitiveValidator>, )

where T: FullPrim + Clone,

Register a FullPrim. Pass None for the validator if not using the proof checker.

impl EGraph

pub fn new(num_threads: usize) -> Self

Create a new e-graph configured with num_threads.

Passing 1 keeps execution serial. Passing 0 uses available parallelism.

pub fn new_with_term_encoding() -> Self

Create a new e-graph with the term-encoding pipeline enabled.

In term-encoding mode the e-graph eagerly instruments every constructor and function with auxiliary term tables, view tables, and per-sort union-finds so that canonical representatives and their justifications are materialized explicitly. This makes it possible to record and emit equality proofs while preserving the observable behaviour of supported commands.

pub fn new_with_proofs() -> Self

Create a new e-graph with proof generation enabled.

pub fn with_proof_testing(self) -> Self

Enable testing of getting proofs for all check commands.

pub fn with_num_threads(self, num_threads: usize) -> Self

Return a copy of this e-graph configured with num_threads.

pub fn set_num_threads(&mut self, num_threads: usize)

Set the number of threads used by this e-graph.

Passing 1 keeps execution serial. Passing 0 uses available parallelism.

pub fn num_threads(&self) -> usize

Return the number of threads configured for this e-graph.

pub fn extension_state<T>(&self) -> Option<&T>

where T: Send + Sync + 'static,

Return extension-owned state stored on this e-graph.

Extension state is keyed by Rust type and follows the same lifecycle as the rest of the e-graph: cloning an EGraph clones the state, and push/pop snapshots and restores it.

pub fn extension_state_or_default<T>(&mut self) -> &mut T

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

Return mutable extension-owned state, inserting T::default() when absent.

pub fn type_info(&mut self) -> &mut TypeInfo

Add a user-defined command to the e-graph Get the type information for this e-graph

pub fn command_macros(&self) -> &CommandMacroRegistry

Get read-only access to the command macro registry

pub fn command_macros_mut(&mut self) -> &mut CommandMacroRegistry

Get mutable access to the command macro registry

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

pub fn set_strict_mode(&mut self, strict_mode: bool)

Configure whether globals missing the required $ prefix are treated as errors.

pub fn strict_mode(&self) -> bool

Returns true when missing $ prefixes on globals are treated as errors.

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 print_function( &mut self, sym: &str, n: Option<usize>, file: Option<(File, PathBuf)>, span: Span, mode: PrintFunctionMode, ) -> Result<Option<CommandOutput>, 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 Print up to n the tuples in a given function. Print all tuples if n is not provided.

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

Print the size of a function. If no function name is provided, print the size of all non-hidden functions as an s-expression list of (name size) pairs, e.g. ((name size) ...).

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 get_function_names(&self) -> Vec<String>

Get the list of all functions in the e-graph.

pub fn functions_iter(&self) -> impl Iterator<Item = (&String, &Function)>

Iterate over every (name, function) pair registered in the e-graph, in registration order.

pub fn read<R>(&self, f: impl FnOnce(ReadState<'_, '_>) -> R) -> R

Run a read-only closure against the e-graph. The closure receives a ReadState, so it can read but not write. Because this borrows &self, the closure and its callbacks may also call other &self methods such as EGraph::value_to_base.

pub fn function_entries( &self, name: &str, f: impl FnMut(FunctionEntry<'_>), ) -> Result<(), Error>

Call f on each FunctionEntry of a function table. Top-level form of Read::function_entries; errors if name is a constructor or unregistered.

pub fn function_entries_while( &self, name: &str, f: impl FnMut(FunctionEntry<'_>) -> bool, ) -> Result<(), Error>

Like EGraph::function_entries, but stops when f returns false.

pub fn constructor_enodes( &self, name: &str, f: impl FnMut(Enode<'_>), ) -> Result<(), Error>

Call f on each Enode of a constructor / relation table. Top-level form of Read::constructor_enodes; errors if name is a function or unregistered.

pub fn constructor_enodes_while( &self, name: &str, f: impl FnMut(Enode<'_>) -> bool, ) -> Result<(), Error>

Like EGraph::constructor_enodes, but stops when f returns false.

pub fn clear_function(&mut self, func_name: &str) -> Result<(), Error>

Remove every row from the named function in bulk.

This is intended as a faster alternative to issuing a (delete …) for every row of the function: it drops the backing row storage in O(1)-in-row-count time, rather than O(n) per-row teardown. Any pending staged inserts/removes for this function are dropped as part of the clear, so callers that have staged updates they want to land first should arrange for those to be flushed beforehand.

Cached indexes and subsets that reference this table are invalidated by a generation bump and are lazily rebuilt against the now-empty table on next access.

Raises an error if the function does not exist.

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 typecheck_expr_with_bindings_and_output( &mut self, expr: &Expr, bindings: &[(String, Span, ArcSort)], output_sort: ArcSort, context: Context, ) -> Result<ResolvedExpr, TypeError>

Typecheck an expression under explicit local bindings, an expected output sort, and a primitive call context.

bindings contains the local variables in scope while resolving expr. Each tuple is (name, span, sort), where span is used for diagnostics tied to that binding. output_sort constrains overload resolution and output-type inference for the expression. Global references are rewritten into the same zero-argument function calls used during command execution. context should match the runtime context where the resolved expression will be evaluated.

pub fn prepare_unstable_fn_targets_for_eval( &mut self, expr: &ResolvedExpr, ) -> Result<(ResolvedExpr, Vec<(String, Value)>), Error>

Replace literal (unstable-fn "...") targets with hidden evaluator bindings.

The returned expression must be evaluated with the returned bindings in scope before any caller-supplied local bindings. This lets direct execution-state evaluation use the same hidden ResolvedFunction value that backend rule lowering injects for unstable-fn.

For example, a resolved body like (unstable-app (unstable-fn "f") _0) cannot evaluate the string literal "f" directly. This helper replaces the (unstable-fn "f") sub-expression with a fresh hidden variable and returns a binding from that variable to the prepared function value.

pub fn are_proofs_enabled(&self) -> bool

Returns true if proofs are enabled.

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 resolve_program( &mut self, filename: Option<String>, input: &str, ) -> Result<Vec<ResolvedCommand>, Error>

Resolves an egglog program by parsing, typechecking, and desugaring each command. Outputs a new egglog program without any syntactic sugar, either user provided (CommandMacro) or built-in (e.g., rewrite commands). Also removes globals from the program by replacing with new constructors.

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

Takes a source program input and parses it into a list of Commands.

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_arcsort_for_value_type<T: 'static>(&self) -> ArcSort

Returns the unique sort whose runtime values have Rust type T.

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. This method assumes x belongs to sort T.

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 get_function(&self, name: &str) -> Option<&Function>

Get a function by name.

Returns None if the function does not exist.

pub fn has_command(&self, name: &str) -> bool

Returns true if a user-defined command with the given name is registered in this e-graph.

pub fn run_user_defined_command( &mut self, name: &str, args: &[Expr], ) -> Result<Vec<CommandOutput>, Error>

Invoke a registered user-defined command by name, passing the given unresolved expression arguments.

This is equivalent to writing (name args...) at the top level, but callable directly from Rust. Returns an error if no command with the given name is registered.

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

Set the report verbosity level for rule execution output.

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 update<R>( &mut self, f: impl FnOnce(FullState<'_, '_>) -> Result<R, Error>, ) -> Result<R, Error>

Run f with a FullState handle on this EGraph’s database — the same handle a :naive rule’s add_rust_rule_full callback receives. Use to drive name-indexed reads / writes (fs.set, fs.add, fs.lookup, fs.eclass_of, fs.contains, fs.remove, …) from outside a rule.

Flush semantics

Pending writes flush once, after f returns. Two consequences:

1. A set / add / remove inside the closure is not visible to a subsequent lookup / contains / eclass_of in the same closure. Split write-then-read into separate update calls.
2. Conversely, batching multiple writes in one closure is the fast path — only one flush + rebuild happens, regardless of how many writes occurred.
3. A closure that only reads (e.g. lookup, constructor_enodes) stages nothing, so the flush is skipped entirely — a read costs no more than a direct backend scan.

Example

use egglog::prelude::*;
let mut eg = EGraph::default();
eg.parse_and_run_program(None, "(function f (i64) i64 :no-merge)")?;
eg.update(|mut fs| fs.set("f", (1_i64,), 42_i64))?;
let got = eg.update(|fs| fs.lookup("f", 1_i64))?;
let got: Option<i64> = got.map(|v| eg.value_to_base::<i64>(v));
assert_eq!(got, Some(42));

pub fn query( &mut self, vars: &[(&str, ArcSort)], facts: Facts<String, String>, ) -> Result<Vec<HashMap<String, Value, BuildHasherDefault<FxHasher>>>, Error>

Run a pattern query: bind the variables in vars against facts and return one [HashMap] per match, keyed by variable name. Values stay raw — convert via EGraph::value_to_base.

With zero vars, returns at most one empty map (so .len() is 1 if the body matched, 0 if it didn’t).

Trait Implementations

impl Clone for EGraph

fn clone(&self) -> EGraph

Returns a duplicate 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.