# awss1236/egg architecture

> Architecture diagram of the GitHub repository awss1236/egg, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-09-25). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/awss1236/egg
- Repository: https://github.com/awss1236/egg

## Overview

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: [`src/egraph.rs`](https://github.com/awss1236/egg/blob/main/src/egraph.rs) (E-Graph), [`src/run.rs`](https://github.com/awss1236/egg/blob/main/src/run.rs) (Saturation Runner), [`src/rewrite.rs`](https://github.com/awss1236/egg/blob/main/src/rewrite.rs) (Rewrite Rules), [`src/machine.rs`](https://github.com/awss1236/egg/blob/main/src/machine.rs) (Pattern Machine)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_model["Expression Model"]
  node_language["Language and AST<br/>[language.rs]"]
  node_macros["Language Macro<br/>[macros.rs]"]
  node_patterns["Patterns<br/>[pattern.rs]"]
  node_multipattern["Multipatterns<br/>[multipattern.rs]"]
end

subgraph group_saturation["Equality Saturation"]
  node_runner["Saturation Runner<br/>[run.rs]"]
  node_rewrite["Rewrite Rules<br/>[rewrite.rs]"]
  node_egraph[("E-Graph<br/>[egraph.rs]")]
  node_eclass["E-Classes and Analysis<br/>[eclass.rs]"]
  node_matcher["Pattern Machine<br/>[machine.rs]"]
  node_substitution["Substitutions<br/>[subst.rs]"]
end

subgraph group_results["Results and Analysis"]
  node_extractor["Best-Expression Extraction<br/>[extract.rs]"]
  node_lp["LP Extraction<br/>[lp_extract.rs]"]
  node_explanations["Equality Explanations<br/>[explain.rs]"]
  node_dot["Graph Visualization<br/>[dot.rs]"]
end

subgraph group_internals["Core Internals"]
  node_unionfind["Union-Find<br/>[unionfind.rs]"]
end

node_client(("Library Client"))
node_client_output["Selected Expression"]

node_client -->|"defines language"| node_language
node_macros -->|"generates support"| node_language
node_client -->|"adds expressions"| node_egraph
node_language -->|"provides nodes"| node_egraph
node_client -->|"runs rules"| node_runner
node_runner -->|"searches and applies"| node_rewrite
node_rewrite -->|"delegates matching"| node_patterns
node_patterns -->|"compiles patterns"| node_matcher
node_matcher -->|"searches classes"| node_egraph
node_matcher -->|"produces bindings"| node_substitution
node_rewrite -->|"adds and merges"| node_egraph
node_runner -->|"rebuilds graph"| node_egraph
node_runner -->|"runs multipattern rules"| node_multipattern
node_egraph -->|"stores classes"| node_eclass
node_egraph -->|"tracks equivalence"| node_unionfind
node_client -->|"requests extraction"| node_extractor
node_extractor -->|"reads alternatives"| node_egraph
node_extractor -->|"returns best expression"| node_client_output
node_client -.->|"requests LP extraction"| node_lp
node_lp -.->|"reads alternatives"| node_egraph
node_client -->|"requests justification"| node_explanations
node_explanations -->|"returns explanation"| node_client_output
node_client -->|"requests visualization"| node_dot
node_dot -->|"reads graph"| node_egraph

click node_language "https://github.com/awss1236/egg/blob/main/src/language.rs"
click node_macros "https://github.com/awss1236/egg/blob/main/src/macros.rs"
click node_patterns "https://github.com/awss1236/egg/blob/main/src/pattern.rs"
click node_multipattern "https://github.com/awss1236/egg/blob/main/src/multipattern.rs"
click node_runner "https://github.com/awss1236/egg/blob/main/src/run.rs"
click node_rewrite "https://github.com/awss1236/egg/blob/main/src/rewrite.rs"
click node_egraph "https://github.com/awss1236/egg/blob/main/src/egraph.rs"
click node_eclass "https://github.com/awss1236/egg/blob/main/src/eclass.rs"
click node_matcher "https://github.com/awss1236/egg/blob/main/src/machine.rs"
click node_substitution "https://github.com/awss1236/egg/blob/main/src/subst.rs"
click node_extractor "https://github.com/awss1236/egg/blob/main/src/extract.rs"
click node_lp "https://github.com/awss1236/egg/blob/main/src/lp_extract.rs"
click node_explanations "https://github.com/awss1236/egg/blob/main/src/explain.rs"
click node_dot "https://github.com/awss1236/egg/blob/main/src/dot.rs"
click node_unionfind "https://github.com/awss1236/egg/blob/main/src/unionfind.rs"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_language,node_macros,node_patterns,node_multipattern,node_client toneBlue
class node_runner,node_rewrite,node_egraph,node_eclass,node_matcher,node_substitution toneAmber
class node_extractor,node_lp,node_explanations,node_dot toneMint
class node_unionfind toneRose
class node_client_output toneIndigo
```

## Components

### Expression Model

- [Language and AST](https://github.com/awss1236/egg/blob/main/src/language.rs): `src/language.rs`
- [Language Macro](https://github.com/awss1236/egg/blob/main/src/macros.rs): `src/macros.rs`
- [Patterns](https://github.com/awss1236/egg/blob/main/src/pattern.rs): `src/pattern.rs`
- [Multipatterns](https://github.com/awss1236/egg/blob/main/src/multipattern.rs): `src/multipattern.rs`

### Equality Saturation

- [Saturation Runner](https://github.com/awss1236/egg/blob/main/src/run.rs): `src/run.rs`
- [Rewrite Rules](https://github.com/awss1236/egg/blob/main/src/rewrite.rs): `src/rewrite.rs`
- [E-Graph](https://github.com/awss1236/egg/blob/main/src/egraph.rs): `src/egraph.rs`
- [E-Classes and Analysis](https://github.com/awss1236/egg/blob/main/src/eclass.rs): `src/eclass.rs`
- [Pattern Machine](https://github.com/awss1236/egg/blob/main/src/machine.rs): `src/machine.rs`
- [Substitutions](https://github.com/awss1236/egg/blob/main/src/subst.rs): `src/subst.rs`

### Results and Analysis

- [Best-Expression Extraction](https://github.com/awss1236/egg/blob/main/src/extract.rs): `src/extract.rs`
- [LP Extraction](https://github.com/awss1236/egg/blob/main/src/lp_extract.rs): `src/lp_extract.rs`
- [Equality Explanations](https://github.com/awss1236/egg/blob/main/src/explain.rs): `src/explain.rs`
- [Graph Visualization](https://github.com/awss1236/egg/blob/main/src/dot.rs): `src/dot.rs`

### Core Internals

- [Union-Find](https://github.com/awss1236/egg/blob/main/src/unionfind.rs): `src/unionfind.rs`

### Other components

- **Library Client**
- **Selected Expression**

## Connections

- 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