[−][src]Trait egg::Applier

pub trait Applier<L, N> where
    L: Language,
    N: Analysis<L>, {
    fn apply_one(
        &self, 
        egraph: &mut EGraph<L, N>, 
        eclass: Id, 
        subst: &Subst
    ) -> Vec<Id>;

    fn apply_matches(
        &self, 
        egraph: &mut EGraph<L, N>, 
        matches: &[SearchMatches]
    ) -> Vec<Id> { ... }

    fn vars(&self) -> Vec<Var> { ... }
}

The righthand side of a Rewrite.

An Applier is anything that can do something with a substitition (Subst). This allows you to implement rewrites that determine when and how to respond to a match using custom logic, including access to the Analysis data of an EClass.

Notably, Pattern implements Applier, which suffices in most cases. Additionally, egg provides ConditionalApplier to stack Conditions onto an Applier, which in many cases can save you from having to implement your own applier.

Example

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

define_language! {
    enum Math {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
        Symbol(Symbol),
    }
}

type EGraph = egg::EGraph<Math, MinSize>;

// Our metadata in this case will be size of the smallest
// represented expression in the eclass.
#[derive(Default)]
struct MinSize;
impl Analysis<Math> for MinSize {
    type Data = usize;
    fn merge(&self, to: &mut Self::Data, from: Self::Data) -> bool {
        merge_if_different(to, (*to).min(from))
    }
    fn make(egraph: &EGraph, enode: &Math) -> Self::Data {
        let get_size = |i: Id| egraph[i].data;
        AstSize.cost(enode, get_size)
    }
}

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"),
    // the rewrite macro parses the rhs as a single token tree, so
    // we wrap it in braces (parens work too).
    rw!("funky"; "(+ ?a (* ?b ?c))" => { Funky {
        a: "?a".parse().unwrap(),
        b: "?b".parse().unwrap(),
        c: "?c".parse().unwrap(),
    }}),
];

#[derive(Debug, Clone, PartialEq, Eq)]
struct Funky {
    a: Var,
    b: Var,
    c: Var,
}

impl Applier<Math, MinSize> for Funky {
    fn apply_one(&self, egraph: &mut EGraph, matched_id: Id, subst: &Subst) -> Vec<Id> {
        let a: Id = subst[self.a];
        // In a custom Applier, you can inspect the analysis data,
        // which is powerful combination!
        let size_of_a = egraph[a].data;
        if size_of_a > 50 {
            println!("Too big! Not doing anything");
            vec![]
        } else {
            // we're going to manually add:
            // (+ (+ ?a 0) (* (+ ?b 0) (+ ?c 0)))
            // to be unified with the original:
            // (+    ?a    (*    ?b       ?c   ))
            let b: Id = subst[self.b];
            let c: Id = subst[self.c];
            let zero = egraph.add(Math::Num(0));
            let a0 = egraph.add(Math::Add([a, zero]));
            let b0 = egraph.add(Math::Add([b, zero]));
            let c0 = egraph.add(Math::Add([c, zero]));
            let b0c0 = egraph.add(Math::Mul([b0, c0]));
            let a0b0c0 = egraph.add(Math::Add([a0, b0c0]));
            // NOTE: we just return the id according to what we
            // want unified with matched_id. The `apply_matches`
            // method actually does the union, _not_ `apply_one`.
            vec![a0b0c0]
        }
    }
}

let start = "(+ x (* y z))".parse().unwrap();
Runner::default().with_expr(&start).run(rules);

Required methods

fn apply_one(
    &self,
    egraph: &mut EGraph<L, N>,
    eclass: Id,
    subst: &Subst
) -> Vec<Id>

Apply a single substitition.

An Applier should only add things to the egraph here, not union them with the id eclass. That is the responsibility of the apply_matches method. The eclass parameter allows the implementer to inspect the eclass where the match was found if they need to.

This should return a list of Ids of things you'd like to be unioned with eclass. There can be zero, one, or many.

Loading content...

Provided methods

fn apply_matches(
    &self,
    egraph: &mut EGraph<L, N>,
    matches: &[SearchMatches]
) -> Vec<Id>

Apply many substititions.

This method should call apply_one for each match and then unify the results with the matched eclass. This should return a list of Ids where the union actually did something.

The default implementation does this and should suffice for most use cases.

fn vars(&self) -> Vec<Var>

Returns a list of variables that this Applier assumes are bound.

egg will check that the corresponding Searcher binds those variables. By default this return an empty Vec, which basically turns off the checking.

Loading content...

Implementors

impl<C, A, N, L> Applier<L, N> for ConditionalApplier<C, A> where
    L: Language,
    C: Condition<L, N>,
    A: Applier<L, N>,
    N: Analysis<L>, [src]

impl<L, A> Applier<L, A> for Pattern<L> where
    L: Language,
    A: Analysis<L>, [src]

Loading content...