[][src]Trait egg::Analysis

pub trait Analysis<L: Language>: Sized {
    type Data: Debug;
    fn make(egraph: &EGraph<L, Self>, enode: &L) -> Self::Data;
fn merge(&self, to: &mut Self::Data, from: Self::Data) -> bool; fn modify(egraph: &mut EGraph<L, Self>, id: Id) { ... } }

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

type Data: Debug

The per-EClass data for this analysis.

Loading content...

Required methods

fn make(egraph: &EGraph<L, Self>, enode: &L) -> Self::Data

Makes a new Analysis for a given enode Analysis.

fn merge(&self, to: &mut Self::Data, from: Self::Data) -> bool

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

Loading content...

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.

Loading content...

Implementations on Foreign Types

impl<L: Language> Analysis<L> for ()[src]

type Data = ()

Loading content...

Implementors

Loading content...