How awss1236/egg works
egg is a Rust library for equality saturation: clients represent expressions in a language, add them to an e-graph, apply rewrite rules until saturation or a limit, then extract a preferred equivalent expression. Its API also supports domain analyses, multipattern rewrites, explanations, graph visualization, and optional LP-based extraction. The graph follows the documented workflow and sampled implementations; some capability links rely on the README/API description because their source was not sampled.
Main entry points: egraph.rs E-Graph · run.rs Saturation Runner · rewrite.rs Rewrite Rules · machine.rs Pattern Machine
Components 17
Expression Model
- Language and AST
src/language.rs - Language Macro
src/macros.rs - Patterns
src/pattern.rs - Multipatterns
src/multipattern.rs
Equality Saturation
- Saturation Runner
src/run.rs - Rewrite Rules
src/rewrite.rs - E-Graph
src/egraph.rs - E-Classes and Analysis
src/eclass.rs - Pattern Machine
src/machine.rs - Substitutions
src/subst.rs
Results and Analysis
- Best-Expression Extraction
src/extract.rs - LP Extraction
src/lp_extract.rs - Equality Explanations
src/explain.rs - Graph Visualization
src/dot.rs
Core Internals
- Union-Find
src/unionfind.rs
Other components
- Library Client
- Selected Expression
Connections 24
- Library Client → Language and AST: defines language
- Language Macro → Language and AST: generates support
- Library Client → E-Graph: adds expressions
- Language and AST → E-Graph: provides nodes
- Library Client → Saturation Runner: runs rules
- Saturation Runner → Rewrite Rules: searches and applies
- Rewrite Rules → Patterns: delegates matching
- Patterns → Pattern Machine: compiles patterns
- Pattern Machine → E-Graph: searches classes
- Pattern Machine → Substitutions: produces bindings
- Rewrite Rules → E-Graph: adds and merges
- Saturation Runner → E-Graph: rebuilds graph
- Saturation Runner → Multipatterns: runs multipattern rules
- E-Graph → E-Classes and Analysis: stores classes
- E-Graph → Union-Find: tracks equivalence
- Library Client → Best-Expression Extraction: requests extraction
- Best-Expression Extraction → E-Graph: reads alternatives
- Best-Expression Extraction → Selected Expression: returns best expression
- Library Client → LP Extraction: requests LP extraction
- LP Extraction → E-Graph: reads alternatives
- Library Client → Equality Explanations: requests justification
- Equality Explanations → Selected Expression: returns explanation
- Library Client → Graph Visualization: requests visualization
- Graph Visualization → E-Graph: reads graph