### Building an Optimizer with egg::Runner in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=std%3A%3Avec

Shows how to create an optimizer using the `egg::Runner` API. It defines rewrite rules using the `rewrite!` macro and demonstrates the equality saturation process. The example also includes extracting the best expression using `Extractor`.

```rust
use egg::rewrite as rw;
use egg::{AstSize, Extractor, Runner, SymbolLang};

// Define a slice of rewrite rules using the `rw!` macro.
let rules: &[egg::Rewrite<SymbolLang, ()>] = &[
    rw!("commute-add"; "(+ ?x ?y)" => "(+ ?y ?x)"),
    rw!("commute-mul"; "(* ?x ?y)" => "(* ?y ?x)"),
    rw!("add-0"; "(+ ?x 0)" => "?x"),
    rw!("mul-0"; "(* ?x 0)" => "0"),
    rw!("mul-1"; "(* ?x 1)" => "?x"),
];

// Define the starting expression.
let start = "(+ 0 (* 1 a))".parse().unwrap();

// Initialize and run the `Runner` to perform equality saturation.
let runner = Runner::default().with_expr(&start).run(rules);

// Create an `Extractor` with a cost function (AstSize) to find the best expression.
let extractor = Extractor::new(&runner.egraph, AstSize);

// Find the best expression in the e-class of the initial expression.
let (best_cost, best_expr) = extractor.find_best(runner.roots[0]);

// Assert that the best expression is 'a' with a cost of 1.
assert_eq!(best_expr, "a".parse().unwrap());
assert_eq!(best_cost, 1);
```

--------------------------------

### Searching an EGraph with Patterns in Egg (Rust)

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Demonstrates the initial setup for searching an EGraph using Patterns. It includes creating an EGraph, adding nodes, and rebuilding the EGraph to prepare it for pattern matching.

```rust
# use egg::*
// let's make an e-graph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// rebuild the e-graph since we modified it
egraph.rebuild();

```

--------------------------------

### Creating an Optimizer with Egg Runner in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=

Illustrates the creation of an optimizer using Egg's `Runner`. It defines rewrite rules using the `rw!` macro, sets up an initial expression, and runs the equality saturation algorithm. The example also shows how to extract the best expression using `Extractor` and a cost function like `AstSize`.

```rust
use egg::{*, rewrite as rw};

let rules: &[Rewrite<SymbolLang, ()>] = &[
    rw!("commute-add"; "(+ ?x ?y)" => "(+ ?y ?x)"),
    rw!("commute-mul"; "(* ?x ?y)" => "(* ?y ?x)"),

    rw!("add-0"; "(+ ?x 0)" => "?x"),
    rw!("mul-0"; "(* ?x 0)" => "0"),
    rw!("mul-1"; "(* ?x 1)" => "?x"),
];

let start = "(+ 0 (* 1 a))".parse().unwrap();

let runner = Runner::default().with_expr(&start).run(rules);

let extractor = Extractor::new(&runner.egraph, AstSize);

let (best_cost, best_expr) = extractor.find_best(runner.roots[0]);

assert_eq!(best_expr, "a".parse().unwrap());
assert_eq!(best_cost, 1);
```

--------------------------------

### Initializing an EGraph for Pattern Searching

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs

Sets up an EGraph with SymbolLang and adds basic elements. It then calls rebuild() on the EGraph, which is necessary before pattern searching. Requires the 'egg' crate.

```rust
# use egg::*;
// let's make an e-graph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// rebuild the e-graph since we modified it
egraph.rebuild();


```

--------------------------------

### Parsing and Displaying Expressions with SymbolLang

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs

Demonstrates how to parse a string into a RecExpr<SymbolLang> and print it. It also shows the creation of a leaf e-node. Requires the 'egg' crate. Panics on parsing errors due to .unwrap().

```rust
# use egg::*;
// Since parsing can return an error, `unwrap` just panics if the result doesn't return Ok
let my_expression: RecExpr<SymbolLang> = "(foo a b)".parse().unwrap();
println!("this is my expression {}", my_expression);

// let's try to create an e-node, but hmmm, what do I put as the children?
let my_enode = SymbolLang::new("bar", vec![]);

```

--------------------------------

### Building RecExpr and EGraph with SymbolLang

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs

Illustrates how to build a RecExpr and an EGraph by adding leaf and complex e-nodes. It shows that adding equivalent expressions to an EGraph returns the same Id. Requires the 'egg' crate.

```rust
# use egg::*;
let mut expr = RecExpr::default();
let a = expr.add(SymbolLang::leaf("a"));
let b = expr.add(SymbolLang::leaf("b"));
let foo = expr.add(SymbolLang::new("foo", vec![a, b]));

// we can do the same thing with an EGraph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// we can also add RecExprs to an egraph
let foo2 = egraph.add_expr(&expr);
// note that if you add the same thing to an e-graph twice, you'll get back equivalent Ids
assert_eq!(foo, foo2);

```

--------------------------------

### Creating an Optimizer with Runner and Rewrite Macro in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs

Illustrates building an optimizer in Rust using the `egg` crate. It shows how to define rewrite rules with the `rewrite!` macro, parse an initial expression, and run the equality saturation algorithm using `Runner`. Finally, it demonstrates extracting the best expression using `Extractor`.

```rust
use egg::{*, rewrite as rw};

let rules: &[Rewrite<SymbolLang, ()>] = &[
    rw!("commute-add"; "(+ ?x ?y)" => "(+ ?y ?x)"),
    rw!("commute-mul"; "(* ?x ?y)" => "(* ?y ?x)"),

    rw!("add-0"; "(+ ?x 0)" => "?x"),
    rw!("mul-0"; "(* ?x 0)" => "0"),
    rw!("mul-1"; "(* ?x 1)" => "?x"),
];

let start = "(+ 0 (* 1 a))".parse().unwrap();
let runner = Runner::default().with_expr(&start).run(rules);

let extractor = Extractor::new(&runner.egraph, AstSize);
let (best_cost, best_expr) = extractor.find_best(runner.roots[0]);

assert_eq!(best_expr, "a".parse().unwrap());
assert_eq!(best_cost, 1);
```

--------------------------------

### Initialize and Rebuild EGraph for Pattern Search

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=

Sets up an EGraph with SymbolLang, adds some basic expressions, and then rebuilds the EGraph. Rebuilding is often necessary after modifications to ensure the EGraph is in a consistent state for searching.

```rust
# use egg::*;
// let's make an e-graph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// rebuild the e-graph since we modified it
egraph.rebuild();

```

--------------------------------

### Examples of FromOp Usage

Source: https://docs.rs/egg/latest/egg/trait.FromOp_search=std%3A%3Avec

Illustrates how the `define_language!` macro automatically implements `FromOp` and `Display`, along with a usage example.

```APIDOC
## Examples

`define_language!` implements `FromOp` and `Display` automatically:

```rust
define_language! {
    enum Calc {
       "+" = Add([Id; 2]),
       Num(i32),
    }
}

let add = Calc::Add([Id::from(0), Id::from(1)]);
let parsed = Calc::from_op("+", vec![Id::from(0), Id::from(1)]).unwrap();

assert_eq!(add.to_string(), "+");
assert_eq!(parsed, add);
```
```

--------------------------------

### Creating an Optimizer with Runner and Rewrite in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Illustrates how to build an optimizer using egg's `Runner` and `Rewrite` functionalities. It defines a set of rewrite rules using the `rewrite!` macro, initializes an expression, and then runs the equality saturation algorithm. Finally, it uses an `Extractor` to find the best expression based on a cost function.

```rust
use egg::{*, rewrite as rw, AstSize, Extractor, Runner, SymbolLang};

let rules: &[Rewrite<SymbolLang, ()>] = &[ 
    rw!("commute-add"; "(+ ?x ?y)" => "(+ ?y ?x)"),
    rw!("commute-mul"; "(* ?x ?y)" => "(* ?y ?x)"),

    rw!("add-0"; "(+ ?x 0)" => "?x"),
    rw!("mul-0"; "(* ?x 0)" => "0"),
    rw!("mul-1"; "(* ?x 1)" => "?x"),
];

// While it may look like we are working with numbers,
// SymbolLang stores everything as strings.
// We can make our own Language later to work with other types.
let start = "(+ 0 (* 1 a))".parse().unwrap();

// That's it! We can run equality saturation now.
let runner = Runner::default().with_expr(&start).run(rules);

// Extractors can take a user-defined cost function,
// we'll use the egg-provided AstSize for now
let extractor = Extractor::new(&runner.egraph, AstSize);

// We want to extract the best expression represented in the
// same e-class as our initial expression, not from the whole e-graph.
// Luckily the runner stores the eclass Id where we put the initial expression.
let (best_cost, best_expr) = extractor.find_best(runner.roots[0]);

// we found the best thing, which is just "a" in this case
assert_eq!(best_expr, "a".parse().unwrap());
assert_eq!(best_cost, 1);
```

--------------------------------

### Parsing and Creating Expressions in Egg (Rust)

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Demonstrates how to parse a string into a RecExpr and create basic e-nodes using SymbolLang. It highlights the use of `unwrap()` for error handling and the distinction between leaf nodes and nodes with children.

```rust
use egg::*
// Since parsing can return an error, `unwrap` just panics if the result doesn't return Ok
let my_expression: RecExpr<SymbolLang> = "(foo a b)".parse().unwrap();
println!("this is my expression {}", my_expression);

// let's try to create an e-node, but hmmm, what do I put as the children?
let my_enode = SymbolLang::new("bar", vec![]);

```

--------------------------------

### Example Solver Selection (CBC)

Source: https://docs.rs/egg/latest/src/egg/lp_extract.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Illustrates how to select the CBC solver from `good_lp` when using `LpExtractor::solve_with`. This example is marked with `# ignore` as it's for demonstration.

```rust
# use egg::*
use good_lp::coin_cbc;
# let egraph: &EGraph<SymbolLang, ()> = &EGraph::default();
# let root = Id::from(0usize);
let rec = LpExtractor::new(egraph, AstSize)
  .solve_with(root, coin_cbc);
# let _ = rec;
```

--------------------------------

### Searching an EGraph with Patterns in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=u32+-%3E+bool

Demonstrates the process of creating an EGraph and then searching it using a `Pattern`. This involves adding elements to the EGraph, rebuilding it to optimize, and then using pattern matching to find specific structures within the graph.

```rust
use egg :: *;
// let's make an e-graph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// rebuild the e-graph since we modified it
egra ph.rebuild();

```

--------------------------------

### Example Solver Selection (HiGHS)

Source: https://docs.rs/egg/latest/src/egg/lp_extract.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Demonstrates selecting the HiGHS solver from `good_lp` using `LpExtractor::solve_with`. This example is also marked with `# ignore` for illustrative purposes.

```rust
# use egg::*
use good_lp::highs;
# let egraph: &EGraph<SymbolLang, ()> = &EGraph::default();
# let root = Id::from(0usize);
let rec = LpExtractor::new(egraph, AstSize)
    .solve_with(root, highs);
# let _ = rec;
```

--------------------------------

### Pattern Matching and Egraph Manipulation in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs

Demonstrates creating and parsing patterns in Rust, searching an egraph for matches, and updating the egraph using union and rebuild operations. It highlights how pattern variables like '?x' enforce matching the same value twice.

```rust
let pat: Pattern<SymbolLang> = "(foo ?x ?x)".parse().unwrap();
let matches = pat.search(&egraph);
assert!(matches.is_empty());

egraph.union(a, b);
egraph.rebuild();

let matches = pat.search(&egraph);
assert!(!matches.is_empty());
```

--------------------------------

### Pattern Matching and EGraph Operations in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Demonstrates how to create and use patterns for searching within an EGraph. It shows how to define a pattern with variables, search for matches, perform union operations on the EGraph, rebuild it, and search again to observe changes. This is crucial for understanding how egg identifies and manipulates equivalent expressions.

```rust
use egg::{*, Extractor, Pattern, RecExpr, Rewrite, Runner, SymbolLang};

// Assume egraph, a, b are defined and initialized elsewhere for demonstration
// let mut egraph = EGraph::<SymbolLang, ()>::default();
// let a = egraph.add(SymbolLang::from("a"));
// let b = egraph.add(SymbolLang::from("b"));

// we can make Patterns by parsing, similar to RecExprs
// names preceded by ? are parsed as Pattern variables and will match anything
let pat: Pattern<SymbolLang> = "(foo ?x ?x)".parse().unwrap();

// since we use ?x twice, it must match the same thing,
// so this search will return nothing
// let matches = pat.search(&egraph);
// assert!(matches.is_empty());

// egraph.union(a, b);
// recall that rebuild must be called to "see" the effects of adds or unions
// egraph.rebuild();

// now we can find a match since a = b
// let matches = pat.search(&egraph);
// assert!(!matches.is_empty());
```

--------------------------------

### Runner Usage Example

Source: https://docs.rs/egg/latest/egg/struct.Runner_search=u32+-%3E+bool

A comprehensive example demonstrating how to define a language, set up rules, customize the Runner with various limits and schedulers, and run the rewriting process.

```APIDOC
## §Example
```rust
use egg::{*, rewrite as rw};

define_language! {
    enum SimpleLanguage {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
        Symbol(Symbol),
    }
}

let rules: &[Rewrite<SimpleLanguage, ()>] = &[
    rw!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
    rw!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),

    rw!("add-0"; "(+ ?a 0)" => "?a"),
    rw!("mul-0"; "(* ?a 0)" => "0"),
    rw!("mul-1"; "(* ?a 1)" => "?a"),
];

pub struct MyIterData {
    smallest_so_far: usize,
}

type MyRunner = Runner<SimpleLanguage, (), MyIterData>;

impl IterationData<SimpleLanguage, ()> for MyIterData {
    fn make(runner: &MyRunner) -> Self {
        let root = runner.roots[0];
        let mut extractor = Extractor::new(&runner.egraph, AstSize);
        MyIterData {
            smallest_so_far: extractor.find_best(root).0,
        }
    }
}

let start = "(+ 0 (* 1 foo))".parse().unwrap();
// Runner is customizable in the builder pattern style.
let runner = MyRunner::new(Default::default())
    .with_iter_limit(10)
    .with_node_limit(10_000)
    .with_expr(&start)
    .with_scheduler(SimpleScheduler)
    .run(rules);

// Now we can check our iteration data to make sure that the cost only
// got better over time
for its in runner.iterations.windows(2) {
    assert!(its[0].data.smallest_so_far >= its[1].data.smallest_so_far);
}

println!(
    "Stopped after {} iterations, reason: {:?}",
    runner.iterations.len(),
    runner.stop_reason
);
```
```

--------------------------------

### Applier Implementation Example

Source: https://docs.rs/egg/latest/egg/trait.Applier

An example of implementing the `Applier` trait for a custom rewrite rule.

```APIDOC
## §Example
```rust
use egg::{
    rewrite as rw,
    Applier,
    Analysis,
    AstSize,
    DidMerge,
    EGraph,
    Id,
    Language,
    merge_min,
    PatternAst,
    SearchMatches,
    Subst,
    Symbol,
    Var,
    Runner,
};
use std::sync::Arc;

define_language! {
    enum Math {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
        Symbol(Symbol),
    }
}

type EGraph = egg::EGraph<Math, MinSize>;

// Our metadata in this case will be size of the smallest
// represented expression in the eclass.
#[derive(Default)]
struct MinSize;
impl Analysis<Math> for MinSize {
    type Data = usize;
    fn merge(&mut self, to: &mut Self::Data, from: Self::Data) -> DidMerge {
        merge_min(to, from)
    }
    fn make(egraph: &mut EGraph, enode: &Math, _id: Id) -> Self::Data {
        let get_size = |i: Id| egraph[i].data;
        AstSize.cost(enode, get_size)
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct Funky {
    a: Var,
    b: Var,
    c: Var,
    ast: PatternAst<Math>,
}

impl Applier<Math, MinSize> for Funky {

    fn apply_one(&self, egraph: &mut EGraph, matched_id: Id, subst: &Subst, _searcher_pattern: Option<&PatternAst<Math>>, _rule_name: Symbol) -> Vec<Id> {
        let a: Id = subst[self.a];
        // In a custom Applier, you can inspect the analysis data,
        // which is powerful combination!
        let size_of_a = egraph[a].data;
        if size_of_a > 50 {
            println!("Too big! Not doing anything");
            vec![]
        } else {
            // we're going to manually add:
            // (+ (+ ?a 0) (* (+ ?b 0) (+ ?c 0)))
            // to be unified with the original:
            // (+    ?a    (*    ?b       ?c   ))
            let b: Id = subst[self.b];
            let c: Id = subst[self.c];
            let zero = egraph.add(Math::Num(0));
            let a0 = egraph.add(Math::Add([a, zero]));
            let b0 = egraph.add(Math::Add([b, zero]));
            let c0 = egraph.add(Math::Add([c, zero]));
            let b0c0 = egraph.add(Math::Mul([b0, c0]));
            let a0b0c0 = egraph.add(Math::Add([a0, b0c0]));
            // Don't forget to union the new node with the matched node!
            if egraph.union(matched_id, a0b0c0) {
                vec![a0b0c0]
            } else {
                vec![]
            }
        }
    }
}

let rules = &
    [
        rw!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
        rw!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),
        rw!("add-0"; "(+ ?a 0)" => "?a"),
        rw!("mul-0"; "(* ?a 0)" => "0"),
        rw!("mul-1"; "(* ?a 1)" => "?a"),
        // the rewrite macro parses the rhs as a single token tree, so
        // we wrap it in braces (parens work too).
        rw!("funky"; "(+ ?a (* ?b ?c))" => {
            Funky {
                a: "?a".parse().unwrap(),
                b: "?b".parse().unwrap(),
                c: "?c".parse().unwrap(),
                ast: "(+ (+ ?a 0) (* (+ ?b 0) (+ ?c 0)))".parse().unwrap(),
            }
        }),
    ];

let start = "(+ x (* y z))\n    .parse()
    .unwrap();
Runner::default().with_expr(&start).run(rules);
```
```

--------------------------------

### Dot Generation Example

Source: https://docs.rs/egg/latest/egg/struct.Dot_search=

Example demonstrating how to generate and use the Dot struct to visualize an EGraph and save it to various file formats.

```APIDOC
## Example
```rust
use egg::{*, rewrite as rw};

let rules = &
    [
        rw!("mul-commutes"; "(* ?x ?y)" => "(* ?y ?x)"),
        rw!("mul-two"; "(* ?x 2)" => "(<< ?x 1)"),
    ];

let mut egraph: EGraph<SymbolLang, ()> = Default::default();
egraph.add_expr(&"(/ (* 2 a) 2)".parse().unwrap());
let egraph = Runner::default().with_egraph(egraph).run(rules).egraph;

// Dot implements std::fmt::Display
println!("My egraph dot file: {}", egraph.dot());

// create a Dot and then compile it assuming `dot` is on the system
egraph.dot().to_svg("target/foo.svg").unwrap();
egraph.dot().to_png("target/foo.png").unwrap();
egraph.dot().to_pdf("target/foo.pdf").unwrap();
egraph.dot().to_dot("target/foo.dot").unwrap();
```
```

--------------------------------

### Example: SillyCostFn Implementation

Source: https://docs.rs/egg/latest/egg/trait.CostFunction_search=u32+-%3E+bool

An example demonstrating how to implement the CostFunction trait with custom logic based on operator names and child costs.

```APIDOC
## Example: SillyCostFn
```rust
struct SillyCostFn;
impl CostFunction<SymbolLang> for SillyCostFn {
    type Cost = f64;
    fn cost<C>(&mut self, enode: &SymbolLang, mut costs: C) -> Self::Cost
    where
        C: FnMut(Id) -> Self::Cost
    {
        let op_cost = match enode.op.as_str() {
            "foo" => 100.0,
            "bar" => 0.7,
            _ => 1.0
        };
        enode.fold(op_cost, |sum, id| sum + costs(id))
    }
}

let e: RecExpr<SymbolLang> = "(do_it foo bar baz)".parse().unwrap();
assert_eq!(SillyCostFn.cost_rec(&e), 102.7);
assert_eq!(AstSize.cost_rec(&e), 4);
assert_eq!(AstDepth.cost_rec(&e), 2);
```
```

--------------------------------

### egg Crate Module Structure (Rust)

Source: https://docs.rs/egg/latest/src/egg/tutorials/mod.rs_search=std%3A%3Avec

This Rust code defines the module structure for the 'egg' crate. It includes main module definitions that link to various tutorial sub-modules, such as background, getting started, and explanations. This serves as the entry point for navigating the crate's documentation and examples.

```Rust
pub mod _01_background;
pub mod _02_getting_started;
pub mod _03_explanations;
```

--------------------------------

### Example: Slice Length in Rust

Source: https://docs.rs/egg/latest/egg/struct.RecExpr_search=

A simple example demonstrating how to get the length of a slice (or a `RecExpr` via deref coercion).

```rust
let a = [1, 2, 3];
assert_eq!(a.len(), 3);
```

--------------------------------

### Searching an EGraph with Patterns in Rust

Source: https://docs.rs/egg/latest/egg/tutorials/_02_getting_started/index

Illustrates how to search an `EGraph` for specific structures using `Pattern`s. This involves creating an e-graph, adding elements, rebuilding the graph to reflect changes, defining a pattern with variables, and then executing the search. The example highlights how pattern variables must match consistently across the pattern.

```rust
// let's make an e-graph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// rebuild the e-graph since we modified it
egraph.rebuild();

// we can make Patterns by parsing, similar to RecExprs
// names preceded by ? are parsed as Pattern variables and will match anything
let pat: Pattern<SymbolLang> = "(foo ?x ?x)".parse().unwrap();

// since we use ?x twice, it must match the same thing,
// so this search will return nothing
let matches = pat.search(&egraph);
assert!(matches.is_empty());

egraph.union(a, b);
// recall that rebuild must be called to "see" the effects of adds or unions
egraph.rebuild();

// now we can find a match since a = b
let matches = pat.search(&egraph);
assert!(!matches.is_empty());

```

--------------------------------

### Rust: Write Dot to a file

Source: https://docs.rs/egg/latest/egg/struct.Dot_search=std%3A%3Avec

Provides an example of writing the GraphViz representation of an `EGraph` directly to a `.dot` file using the `to_dot` method. This method does not require the `dot` binary to be installed.

```rust
use egg::*;
use std::path::Path;

// Assuming egraph is defined and has a dot() method.
// let dot_output = egraph.dot();

// Write to a .dot file
// dot_output.to_dot("path/to/output.dot").unwrap();

// Dummy implementation for compilation purposes
struct MockDot<'a> { _phantom: std::marker::PhantomData<&'a ()> }
impl<'a> MockDot<'a> {
    pub fn to_dot(&self, _filename: impl AsRef<Path>) -> Result<(), String> {
        Ok(())
    }
}

struct MockEGraph<'a> { _phantom: std::marker::PhantomData<&'a ()> }
impl<'a> MockEGraph<'a> {
    pub fn dot(&self) -> MockDot<'a> {
        MockDot { _phantom: std::marker::PhantomData }
    }
}

#[test]
fn test_to_dot() {
    let egraph = MockEGraph { _phantom: std::marker::PhantomData };
    egraph.dot().to_dot("path/to/output.dot").unwrap();
}

```

--------------------------------

### Example: Get Last Slice Element in Rust

Source: https://docs.rs/egg/latest/egg/struct.RecExpr_search=

Demonstrates retrieving the last element of a slice (or a `RecExpr`).

```rust
let v = [10, 40, 30];
assert_eq!(Some(&30), v.last());

let w: &[i32] = &[];
assert_eq!(None, w.last());
```

--------------------------------

### Example: Get First Slice Element in Rust

Source: https://docs.rs/egg/latest/egg/struct.RecExpr_search=

Demonstrates retrieving the first element of a slice (or a `RecExpr`).

```rust
let v = [10, 40, 30];
assert_eq!(Some(&10), v.first());

let w: &[i32] = &[];
assert_eq!(None, w.first());
```

--------------------------------

### Runner Initialization and Configuration

Source: https://docs.rs/egg/latest/src/egg/run.rs

Provides details on how to initialize a Runner and configure its various parameters such as limits and hooks.

```APIDOC
## Runner Initialization and Configuration

### Description
Initialize a new `Runner` with default parameters or configure specific limits, hooks, and schedulers.

### Methods

*   **`new(analysis: N) -> Self`**
    *   Description: Create a new `Runner` with the given analysis and default parameters.
*   **`with_iter_limit(self, iter_limit: usize) -> Self`**
    *   Description: Sets the iteration limit. Default: 30.
*   **`with_node_limit(self, node_limit: usize) -> Self`**
    *   Description: Sets the egraph size limit (in enodes). Default: 10,000.
*   **`with_time_limit(self, time_limit: Duration) -> Self`**
    *   Description: Sets the runner time limit. Default: 5 seconds.
*   **`with_hook<F>(mut self, hook: F) -> Self`**
    *   Description: Add a hook to instrument or modify the behavior of a `Runner`. Each hook will run at the beginning of each iteration, i.e. before all the rewrites.
    *   Example:
        ```rust
        # use egg::*;
        let rules: &[Rewrite<SymbolLang, ()>] = &[
            rewrite!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
        ];
        
        Runner::<SymbolLang, ()>::default()
            .with_expr(&"(+ 5 2)".parse().unwrap())
            .with_hook(|runner| {
                 println!("Egraph is this big: {}", runner.egraph.total_size());
                 Ok(())
            })
            .run(rules);
        ```
*   **`with_scheduler(self, scheduler: impl RewriteScheduler<L, N> + 'static) -> Self`**
    *   Description: Change out the `RewriteScheduler` used by this `Runner`. The default one is `BackoffScheduler`.
*   **`with_expr(mut self, expr: &RecExpr<L>) -> Self`**
    *   Description: Add an expression to the egraph to be run. The eclass id of this addition will be recorded in the `roots` field, ordered by insertion order.
*   **`with_egraph(self, egraph: EGraph<L, N>) -> Self`**
    *   Description: Replace the `EGraph` of this `Runner`.
```

--------------------------------

### Example: Get Mutable First Slice Element in Rust

Source: https://docs.rs/egg/latest/egg/struct.RecExpr_search=

Shows how to modify the first element of a mutable slice (or `RecExpr`).

```rust
let x = &mut [0, 1, 2];

if let Some(first) = x.first_mut() {
    *first = 5;
}
assert_eq!(x, &[5, 1, 2]);

let y: &mut [i32] = &mut [];
assert_eq!(None, y.first_mut());
```

--------------------------------

### Get Total Size of Egraph

Source: https://docs.rs/egg/latest/src/egg/egraph.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Returns the total number of enodes in the egraph, which corresponds to the size of the internal hashcons index. Includes an example.

```rust
pub fn total_size(&self) -> usize {
    self.memo.len()
}

// Example:
// use egg::{*, SymbolLang as S};
// let mut egraph = EGraph::<S, ()>::default();
// let x = egraph.add(S::leaf("x"));
// let y = egraph.add(S::leaf("y"));
// egraph.union(x, y);
// egraph.rebuild();
// assert_eq!(egraph.total_size(), 2);
```

--------------------------------

### Rust: Example of using a Runner hook

Source: https://docs.rs/egg/latest/src/egg/run.rs_search=std%3A%3Avec

Demonstrates how to use the `with_hook` method to add a closure that prints the current size of the e-graph during each iteration. This example also shows setting up rules and running the optimization.

```rust
let rules: &[Rewrite<SymbolLang, ()>] = &[
    rewrite!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
    // probably some others ...
];

Runner::<SymbolLang, ()>::default()
    .with_expr(&"(+ 5 2)".parse().unwrap())
    .with_hook(|runner| {
         println!("Egraph is this big: {}", runner.egraph.total_size());
         Ok(())
    })
    .run(rules);
```

--------------------------------

### Generate DOT file from EGraph

Source: https://docs.rs/egg/latest/src/egg/dot.rs_search=

This example demonstrates how to create a Dot struct from an EGraph and then output its representation directly to a .dot file. This method does not require the `dot` binary to be installed.

```rust
use egg::*; 

let rules = &[ 
    rw!("mul-commutes"; "(* ?x ?y)" => "(* ?y ?x)"), 
    rw!("mul-two"; "(* ?x 2)" => "(<< ?x 1)"), 
]; 

let mut egraph: EGraph<SymbolLang, ()> = Default::default(); 
egraph.add_expr(&"(/ (* 2 a) 2)".parse().unwrap()); 
let egraph = Runner::default().with_egraph(egraph).run(rules).egraph; 

// Dot implements std::fmt::Display 
println!("My egraph dot file: {}", egraph.dot()); 

// create a Dot and then compile it assuming `dot` is on the system 
egraph.dot().to_svg("target/foo.svg").unwrap(); 
egraph.dot().to_png("target/foo.png").unwrap(); 
egraph.dot().to_pdf("target/foo.pdf").unwrap(); 
egraph.dot().to_dot("target/foo.dot").unwrap();
```

--------------------------------

### Get Initial Flat Term with get_initial_flat_term in Rust

Source: https://docs.rs/egg/latest/egg/struct.TreeTerm

A method to retrieve a `FlatTerm` representing the first term in the proof represented by the `TreeTerm`. This is useful for understanding the starting point of the rewriting process.

```rust
pub fn get_initial_flat_term(&self) -> FlatTerm<L>
```

--------------------------------

### Var Implementations

Source: https://docs.rs/egg/latest/egg/struct.Var

Details on how to create and interact with `Var` instances.

```APIDOC
## Implementations

### impl Var

#### pub fn from_u32(num: u32) -> Self

Create a new variable from a u32.
You can also use special syntax `?#3`, `?#42` to denote a numeric variable. These avoid some symbol interning, and can also be created manually from using this function or the `From` impl.

```rust
assert_eq!(Var::from(12), "?#12".parse().unwrap());
assert_eq!(Var::from_u32(12), "?#12".parse().unwrap());
```

#### pub fn as_u32(&self) -> Option<u32>

If this variable was created from a u32, get it back out.
```

--------------------------------

### Parse and Print RecExpr in Rust with egg

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=std%3A%3Avec

Demonstrates parsing a string into a `RecExpr<SymbolLang>` and printing it. This requires the `egg::*` prelude and uses `parse().unwrap()` for simplicity, which will panic on invalid input.

```rust
use egg::*;
// Since parsing can return an error, `unwrap` just panics if the result doesn't return Ok
let my_expression: RecExpr<SymbolLang> = "(foo a b)".parse().unwrap();
println!("this is my expression {}", my_expression);

// let's try to create an e-node, but hmmm, what do I put as the children?
let my_enode = SymbolLang::new("bar", vec![]);

```

--------------------------------

### Rust: Run dot with arguments

Source: https://docs.rs/egg/latest/egg/struct.Dot_search=std%3A%3Avec

Demonstrates the `run_dot` method, which allows executing the `dot` command with specific arguments and piping the GraphViz output to its standard input. This offers fine-grained control over the rendering process.

```rust
use egg::*;
use std::ffi::OsStr;

// Assuming egraph is defined and has a dot() method.
// let dot_output = egraph.dot();

// Run `dot` with custom arguments
// dot_output.run_dot(&["-Tpng", "-o", "output.png"]).unwrap();

// Dummy implementation for compilation purposes
struct MockDot<'a> { _phantom: std::marker::PhantomData<&'a ()> }
impl<'a> MockDot<'a> {
    pub fn run_dot<S, I>(&self, _args: I) -> Result<(), String>
    where
        S: AsRef<OsStr>,
        I: IntoIterator<Item = S>,
    {
        Ok(())
    }
}

struct MockEGraph<'a> { _phantom: std::marker::PhantomData<&'a ()> }
impl<'a> MockEGraph<'a> {
    pub fn dot(&self) -> MockDot<'a> {
        MockDot { _phantom: std::marker::PhantomData }
    }
}

#[test]
fn test_run_dot() {
    let egraph = MockEGraph { _phantom: std::marker::PhantomData };
    egraph.dot().run_dot(&["-Tpng", "-o", "output.png"]).unwrap();
}

```

--------------------------------

### Parsing a RecExpr in Rust

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=u32+-%3E+bool

Demonstrates how to parse a string representation of an expression into a `RecExpr` using `SymbolLang`. It handles potential parsing errors by unwrapping the result. This is useful for quickly creating expression structures.

```rust
use egg :: *;
// Since parsing can return an error, `unwrap` just panics if the result doesn't return Ok
let my_expression: RecExpr<SymbolLang> = "(foo a b)".parse().unwrap();
println!("this is my expression {}", my_expression);

// let's try to create an e-node, but hmmm, what do I put as the children?
let my_enode = SymbolLang::new("bar", vec![]);
```

--------------------------------

### Runner Configuration

Source: https://docs.rs/egg/latest/src/egg/run.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

This section details how to configure and initialize the Egg Runner with various parameters.

```APIDOC
## Runner Initialization and Configuration

### Description
Initializes a new `Runner` with a given analysis and default parameters. Allows configuration of iteration limits, node limits, time limits, hooks, schedulers, and initial expressions.

### Methods

- **`new(analysis: N)`**: Creates a new `Runner` with the specified analysis and default limits.
- **`with_iter_limit(iter_limit: usize)`**: Sets the maximum number of iterations. Default: 30.
- **`with_node_limit(node_limit: usize)`**: Sets the maximum number of egraph nodes. Default: 10,000.
- **`with_time_limit(time_limit: Duration)`**: Sets the maximum time limit for the runner. Default: 5 seconds.
- **`with_hook<F>(hook: F)`**: Adds a hook function that runs at the beginning of each iteration. The hook can modify the e-graph.
- **`with_scheduler(scheduler: impl RewriteScheduler<L, N> + 'static)`**: Replaces the default rewrite scheduler with a custom one.
- **`with_expr(expr: &RecExpr<L>)`**: Adds an expression to the egraph to be processed. The eclass ID is stored in `roots`.
- **`with_egraph(egraph: EGraph<L, N>)`**: Replaces the existing egraph with a new one.

### Request Example (Configuration)
```rust
use egg::*; 
use std::time::Duration;

let rules: &[Rewrite<SymbolLang, ()>] = &[]; // Define your rewrite rules here

let runner = Runner::<SymbolLang, ()>::new(()) // Assuming () is a valid Analysis
    .with_iter_limit(50)
    .with_node_limit(20_000)
    .with_time_limit(Duration::from_secs(10))
    .with_expr(&"(egg)".parse().unwrap());

// To run the optimization:
// runner.run(rules);
```

### Response Example (Runner Instance)

The methods return a modified `Runner` instance, allowing for chained configuration.
```

--------------------------------

### Initialize and Build EGraph with Expressions

Source: https://docs.rs/egg/latest/src/egg/rewrite.rs_search=

Initializes a default EGraph and adds starting and goal expressions. It defines a helper function 'get' to retrieve the operation symbol from an e-class and a custom Appender struct for rewrite rules.

```rust
let mut egraph = EGraph::default();

        let start = RecExpr::from_str("(+ x y)").unwrap();
        let goal = RecExpr::from_str("xy").unwrap();

        let root = egraph.add_expr(&start);

        fn get(egraph: &EGraph, id: Id) -> Symbol {
            egraph[id].nodes[0].op
        }
```

--------------------------------

### Example of Runner Usage for Equality Saturation in Rust

Source: https://docs.rs/egg/latest/egg/struct.Runner_search=u32+-%3E+bool

Provides a detailed example of using the 'Runner' for equality saturation with a custom language 'SimpleLanguage' and iteration data 'MyIterData'. It demonstrates defining rules, configuring the runner with limits and a scheduler, running the process, and analyzing the iteration data.

```rust
use egg::{*,
    rewrite as rw
};

define_language! {
    enum SimpleLanguage {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
        Symbol(Symbol),
    }
}

let rules: &[Rewrite<SimpleLanguage, ()>] = &[
    rw!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
    rw!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),

    rw!("add-0"; "(+ ?a 0)" => "?a"),
    rw!("mul-0"; "(* ?a 0)" => "0"),
    rw!("mul-1"; "(* ?a 1)" => "?a"),
];

pub struct MyIterData {
    smallest_so_far: usize,
}

type MyRunner = Runner<SimpleLanguage, (), MyIterData>;

impl IterationData<SimpleLanguage, ()> for MyIterData {
    fn make(runner: &MyRunner) -> Self {
        let root = runner.roots[0];
        let mut extractor = Extractor::new(&runner.egraph, AstSize);
        MyIterData {
            smallest_so_far: extractor.find_best(root).0,
        }
    }
}

let start = "(+ 0 (* 1 foo))".parse().unwrap();
// Runner is customizable in the builder pattern style.
let runner = MyRunner::new(Default::default())
    .with_iter_limit(10)
    .with_node_limit(10_000)
    .with_expr(&start)
    .with_scheduler(SimpleScheduler)
    .run(rules);

// Now we can check our iteration data to make sure that the cost only
// got better over time
for its in runner.iterations.windows(2) {
    assert!(its[0].data.smallest_so_far >= its[1].data.smallest_so_far);
}

println!(
    "Stopped after {} iterations, reason: {:?}",
    runner.iterations.len(),
    runner.stop_reason
);

```

--------------------------------

### Adding Nodes to RecExpr and EGraph in Egg (Rust)

Source: https://docs.rs/egg/latest/src/egg/tutorials/_02_getting_started.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Shows how to add leaf nodes and compound nodes to both a RecExpr and an EGraph. It illustrates that adding equivalent expressions to an EGraph results in the same Id, and how to add a RecExpr to an EGraph.

```rust
use egg::*
let mut expr = RecExpr::default();
let a = expr.add(SymbolLang::leaf("a"));
let b = expr.add(SymbolLang::leaf("b"));
let foo = expr.add(SymbolLang::new("foo", vec![a, b]));

// we can do the same thing with an EGraph
let mut egraph: EGraph<SymbolLang, ()> = Default::default();
let a = egraph.add(SymbolLang::leaf("a"));
let b = egraph.add(SymbolLang::leaf("b"));
let foo = egraph.add(SymbolLang::new("foo", vec![a, b]));

// we can also add RecExprs to an egraph
let foo2 = egraph.add_expr(&expr);
// note that if you add the same thing to an e-graph twice, you'll get back equivalent Ids
assert_eq!(foo, foo2);

```

--------------------------------

### Create New Runner

Source: https://docs.rs/egg/latest/src/egg/run.rs_search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Initializes a new `Runner` with a given analysis and default parameters for limits, roots, iterations, hooks, and scheduler.

```rust
pub fn new(analysis: N) -> Self {
    Self {
        limits: RunnerLimits {
            iter_limit: 30,
            node_limit: 10_000,
            time_limit: Duration::from_secs(5),
            start_time: None,
        },
        egraph: EGraph::new(analysis),
        roots: vec![],
        iterations: vec![],
        stop_reason: None,
        hooks: vec![],
        scheduler: Box::new(BackoffScheduler::default()),
    }
}
```