Crate egglog 

egglog

Egglog is a language for writing equality saturation applications. It is the successor to the Rust library egg. Egglog is more expressive than egg and scales better to complex workloads.

Tutorial

We have a text tutorial on egglog and how to use it. We also have a slightly outdated video tutorial.

Language reference

The egglog language itself is documented through the Command enum (a type alias for ast::GenericCommand): one variant per top-level egglog command (Datatype, Function, Rule, RunSchedule, …), each with its own doc comment describing the syntax and semantics. Whatever you can write between parentheses at the top of an egglog program shows up as a variant there.

Using egglog from Rust

We encourage using the egglog language as much as possible, even from Rust. In some cases, custom primitives or custom rules are necessary. For this reason, we expose a Rust API in the prelude module — start there for the full surface.

The default path: write your sorts, functions, and rules as an egglog program and run it via EGraph::parse_and_run_program. Reach for EGraph::update only when you really need to do reads and writes from Rust (e.g. building rows from non-egglog data, integrating with a Rust-side data structure). For rules whose RHS needs Rust logic, use prelude::rust_rule / prelude::rust_rule_full. For new functions callable from egglog expressions, define a custom Primitive and register it with the matching EGraph::add_*_primitive — the add_primitive! macro covers the common “pure native function” case.

To pull an extracted term back out of the e-graph, let-bind a global name to it ((let $root ...)), resolve the global with EGraph::eval_expr to get its (sort, Value), then call EGraph::extract_value (default cost model) or EGraph::extract_value_with_cost_model / a custom extract::CostModel when you want non-default costs. The extract module has the full extractor API.

Re-exports

pub use ast::ResolvedExpr;

pub use ast::ResolvedFact;

pub use ast::ResolvedVar;

pub use crate::api::ApiError;

pub use crate::api::FromValue;

pub use crate::api::FromValues;

pub use crate::api::IntoValue;

pub use crate::api::IntoValues;

pub use crate::api::RawValues;

Modules

api

Row encoding for the crate::EGraph surface API.

ast

constraint

extract

prelude

Rust entry point for egglog.

proof

Read-only proof reconstruction API.

scheduler

sort

util

Macros

action

actions

add_literal_prim

This macro lets the user declare literal primitives with automatic validator generation. It automatically generates validators by converting between Rust values and Literal types.

add_primitive

This macro lets the user declare custom egglog primitives. It supports a few special features:

add_primitive_with_validator

This macro lets the user declare custom egglog primitives with explicit validators. It combines primitive registration with a custom validator function.

call

datatype

Adds sorts and constructor tables to the database.

expr

fact

facts

lit

match_term_app

sort

span

var

vars

Structs

CommandMacroRegistry

A registry of command macros

EGraph

Enode

One enode from Read::constructor_enodes. Columns are raw Values; convert with Core::value_to_base / Core::value_to_container.

FullState

Wrapper for Context::Full. Implements Core + Read + Write.

FuncType

Function

A function in the e-graph.

FunctionEntry

One entry from Read::function_entries. Columns are raw Values; convert with Core::value_to_base / Core::value_to_container.

NotFoundError

OrdTerm

A TermId paired with its TermDag so it can be ordered by TermDag::ast_cmp, for use in ordered collections like BTreeMap/BTreeSet (see TermDag::ord_term). Only compare wrappers from the same TermDag.

PureState

Wrapper for Context::Pure. Implements Core only.

ReadState

Wrapper for Context::Read. Implements Core + Read.

SerializeConfig

SerializeOutput

Output of serializing an e-graph, including values that were omitted if any.

SpecializedPrimitive

TermDag

A hashconsing arena for Terms.

TypeInfo

Stores resolved typechecking information.

Value

A generic identifier representing an egglog value

WriteState

Wrapper for Context::Write. Implements Core + Write.

Enums

CommandOutput

Output from a command.

Context

The four contexts a primitive may run in, named after the capability profile they grant. Each variant maps 1:1 to one of the state wrappers below: Pure ↔ PureState, Write ↔ WriteState, Read ↔ ReadState, Full ↔ FullState. The egglog typechecker filters primitive definitions by whether they carry a runtime id for the surrounding Context at each call site.

Error

ResolvedCall

RunMode

SerializedNode

A node in the serialized egraph.

Term

Like Exprs but with sharing and deduplication.

TypeError

Constants

GLOBAL_NAME_PREFIX

Traits

BaseValue

A simple data type that can be interned in a database.

CommandMacro

A command macro that can transform commands during desugaring

ContainerValue

A trait implemented by container types.

Core

Core methods available on every state wrapper: base values, counters, container interning, value/base/container conversion sugar. Always seminaive-safe.

FullPrim

A primitive whose body sees a FullState. Register via EGraph::add_full_primitive.

Primitive

Methods shared by every kind-specific primitive trait.

PurePrim

A primitive whose body sees a PureState. Register via EGraph::add_pure_primitive.

Read

Read-side methods — name-indexed table lookup and iteration. Implemented for ReadState and FullState; not for PureState or WriteState (a Write context body must not depend on live DB state).

ReadPrim

A primitive whose body sees a ReadState. Register via EGraph::add_read_primitive.

UserDefinedCommand

A user-defined command allows users to inject custom command that can be called in an egglog program.

UserDefinedCommandOutput

A user-defined command output trait.

Write

Action-side write methods — name-indexed inserts/removes/subsumes plus union and panic. Implemented for WriteState and FullState; not for PureState or ReadState.

WritePrim

A primitive whose body sees a WriteState. Register via EGraph::add_write_primitive.

Functions

cli

Start a command-line interface for the E-graph.

file_supports_proofs

Reads a file and checks that its commands support the proof encoding.

program_supports_proofs

Checks whether a desugared program supports proof encoding.

Type Aliases

ArcSort

Atom

AtomTerm

PrimitiveValidator

Validators take a termdag and arguments (as TermIds) and return a newly computed TermId if the primitive application is valid, or None if it is invalid.

TermId