[−][src]Trait egg::Metadata
Arbitrary data associated with an EClass
.
egg
allows you to associate arbitrary data with each eclass.
The Metadata
allows that data to behave well even across eclasses merges.
Metadata
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 Metadata
.
If you don't care about Metadata
, ()
implements it trivally,
just use that.
Example
use egg::{*, rewrite as rw}; define_language! { enum EasyMath { Num(i32), Add = "+", Mul = "*", Variable(String), } } use EasyMath::*; type Meta = Option<i32>; impl Metadata<EasyMath> for Meta { type Error = (); fn merge(&self, other: &Self) -> Self { self.clone().and(other.clone()) } fn make(enode: ENode<EasyMath, &Self>) -> Self { let c = |i: usize| enode.children[i].clone(); match enode.op { Num(i) => Some(i), Add => Some(c(0)? + c(1)?), Mul => Some(c(0)? * c(1)?), _ => None, } } fn modify(eclass: &mut EClass<EasyMath, Self>) { if let Some(i) = eclass.metadata { eclass.nodes.push(enode!(Num(i))) } } } let rules: &[Rewrite<EasyMath, Meta>] = &[ 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 mut egraph = EGraph::<EasyMath, Meta>::default(); let whole_thing = egraph.add_expr(&"(+ 0 (* (+ 4 -3) foo))".parse().unwrap()); SimpleRunner::default().run(&mut egraph, &rules); let just_foo = egraph.add(enode!(Variable("foo".into()))); assert_eq!(egraph.find(whole_thing), egraph.find(just_foo));