[−][src]Trait egg::Analysis
Arbitrary data associated with an EClass
.
egg
allows you to associate arbitrary data with each eclass.
The Analysis
allows that data to behave well even across eclasses merges.
Analysis
can prove useful in many situtations.
One common one is constant folding, a kind of partial evaluation.
In that case, the metadata is basically Option<L>
, storing
the cheapest constant expression (if any) that's equivalent to the
enodes in this eclass.
See the test files math.rs
and prop.rs
for more complex
examples on this usage of Analysis
.
If you don't care about Analysis
, ()
implements it trivally,
just use that.
Example
use egg::{*, rewrite as rw}; define_language! { enum SimpleMath { "+" = Add([Id; 2]), "*" = Mul([Id; 2]), Num(i32), Symbol(Symbol), } } // in this case, our analysis itself doens't require any data, so we can just // use a unit struct and derive Default #[derive(Default)] struct ConstantFolding; impl Analysis<SimpleMath> for ConstantFolding { type Data = Option<i32>; fn merge(&self, to: &mut Self::Data, from: Self::Data) -> bool { egg::merge_if_different(to, to.or(from)) } fn make(egraph: &EGraph<SimpleMath, Self>, enode: &SimpleMath) -> Self::Data { let x = |i: &Id| egraph[*i].data; match enode { SimpleMath::Num(n) => Some(*n), SimpleMath::Add([a, b]) => Some(x(a)? + x(b)?), SimpleMath::Mul([a, b]) => Some(x(a)? * x(b)?), _ => None, } } fn modify(egraph: &mut EGraph<SimpleMath, Self>, id: Id) { if let Some(i) = egraph[id].data { let added = egraph.add(SimpleMath::Num(i)); egraph.union(id, added); } } } 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"), ]; let expr = "(+ 0 (* (+ 4 -3) foo))".parse().unwrap(); let mut runner = Runner::<SimpleMath, ConstantFolding, ()>::default().with_expr(&expr).run(rules); let just_foo = runner.egraph.add_expr(&"foo".parse().unwrap()); assert_eq!(runner.egraph.find(runner.roots[0]), runner.egraph.find(just_foo));
Associated Types
Loading content...Required methods
fn make(egraph: &EGraph<L, Self>, enode: &L) -> Self::Data
fn merge(&self, to: &mut Self::Data, from: Self::Data) -> bool
Defines how to merge two Data
s when their containing
EClass
es merge.
Provided methods
fn modify(egraph: &mut EGraph<L, Self>, id: Id)
A hook that allows the modification of the
EGraph
By default this does nothing.