1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#![warn(missing_docs)]
/*!
[`EGraph`]s (and almost everything else in this crate) are
parameterized over the language given by the user (by implementing
the [`Language`] trait).

If your Language implements [`FromStr`] (and Languages derived using
[`define_language!`] do), you can easily create [`RecExpr`]s to add to
an [`EGraph`].

[`EGraph`]: struct.EGraph.html
[`Language`]: trait.Language.html
[`RecExpr`]: struct.RecExpr.html
[`define_language!`]: macro.define_language.html
[`FromStr`]: https://doc.rust-lang.org/std/str/trait.FromStr.html

Add `egg` to your `Cargo.toml` like this:
```toml
[dependencies]
egg = "0.3.0"
```

# Example

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

define_language! {
    enum SimpleLanguage {
        Num(i32),
        Add = "+",
        Mul = "*",
        // language items are parsed in order, and we want symbol to
        // be a fallback, so we put it last
        Symbol(String),
    }
}

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"),
];

let start = "(+ 0 (* 1 foo))".parse().unwrap();
let runner = Runner::new().with_expr(&start).run(&rules);
println!(
    "Stopped after {} iterations, reason: {:?}",
    runner.iterations.len(),
    runner.stop_reason
);
```
!*/

mod macros;

pub(crate) mod machine;
pub(crate) mod unionfind;

pub(crate) use pattern::PatternAst;

mod dot;
mod eclass;
mod egraph;
mod expr;
mod extract;
mod parse;
mod pattern;
mod rewrite;
mod run;
mod subst;

pub use dot::Dot;
pub use eclass::{EClass, Metadata};
pub use egraph::EGraph;
pub use expr::{ENode, Id, Language, RecExpr};
pub use extract::*;
pub use parse::ParseError;
pub use pattern::{Pattern, SearchMatches};
pub use rewrite::{Applier, Condition, ConditionEqual, ConditionalApplier, Rewrite, Searcher};
pub use run::*;
pub use subst::{Subst, Var};

#[cfg(test)]
fn init_logger() {
    let _ = env_logger::builder().is_test(true).try_init();
}

#[doc(hidden)]
pub fn egg_bench<T>(name: &str, mut f: impl FnMut() -> T) -> T {
    fn mean_stdev(data: &[f64]) -> (f64, f64) {
        assert_ne!(data.len(), 0);

        let sum = data.iter().sum::<f64>();
        let n = data.len() as f64;
        let mean = sum / n;

        let variance = data
            .iter()
            .map(|value| {
                let diff = mean - (*value as f64);
                diff * diff
            })
            .sum::<f64>()
            / n;

        (mean, variance.sqrt())
    }

    use std::env::{var, VarError};
    use std::time::{Duration, Instant};

    match var("EGG_BENCH") {
        Err(VarError::NotPresent) => f(),
        Ok(s) => {
            let seconds = s.parse().unwrap();
            let duration = Duration::from_secs_f64(seconds);

            let start = Instant::now();
            let mut times = vec![];

            println!("benching {} for {} seconds...", name, seconds);

            let result = loop {
                let i = Instant::now();
                let result = f();
                times.push(i.elapsed().as_secs_f64());

                if start.elapsed() > duration {
                    break result;
                }
            };

            let (mean, stdev) = mean_stdev(&times);
            println!("bench    {}:", name);
            println!("  n = {}", times.len());
            println!("  μ = {}", mean);
            println!("  σ = {}", stdev);

            result
        }
        _ => panic!(),
    }
}