Trait egg::Metadata

pub trait Metadata<L>: Sized + Debug {
    type Error: Debug;
    fn merge(&self, other: &Self) -> Self;
    fn make(enode: ENode<L, &Self>) -> Self;

    fn modify(_eclass: &mut EClass<L, Self>) { ... }
}

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));

Associated Types

type Error: Debug

Unused for now, probably just make this ().

Loading content...

Required methods

fn merge(&self, other: &Self) -> Self

Defines how to merge two Metadatas when their containing EClasses merge.

fn make(enode: ENode<L, &Self>) -> Self

Makes a new Metadata given an operator and its children Metadata.

Loading content...

Provided methods

fn modify(_eclass: &mut EClass<L, Self>)

A hook that allow a Metadata to modify its containing EClass.

By default this does nothing.

Loading content...

Implementations on Foreign Types

impl<L: Language> Metadata<L> for ()

type Error = Infallible

fn merge(&self, _other: &())

fn make(_enode: ENode<L, &()>)

Loading content...

Implementors

Loading content...