Trait egg::Applier

source · [−]
pub trait Applier<L, N> where
    L: Language,
    N: Analysis<L>, {
    fn apply_one(
        &self, 
        egraph: &mut EGraph<L, N>, 
        eclass: Id, 
        subst: &Subst, 
        searcher_ast: Option<&PatternAst<L>>, 
        rule_name: Symbol
    ) -> Vec<Id>;

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

    fn get_pattern_ast(&self) -> Option<&PatternAst<L>> { ... }

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

The righthand side of a Rewrite.

An Applier is anything that can do something with a substitution (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, *};
use std::sync::Arc;

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(&mut self, to: &mut Self::Data, from: Self::Data) -> DidMerge {
        merge_min(to, from)
    }
    fn make(egraph: &mut 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(),
        ast: "(+ (+ ?a 0) (* (+ ?b 0) (+ ?c 0)))".parse().unwrap(),
    }}),
];

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

impl Applier<Math, MinSize> for Funky {

    fn apply_one(&self, egraph: &mut EGraph, matched_id: Id, subst: &Subst, searcher_pattern: Option<&PatternAst<Math>>, rule_name: Symbol) -> 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]));
            // Don't forget to union the new node with the matched node!
            if egraph.union(matched_id, a0b0c0) {
                vec![a0b0c0]
            } else {
                vec![]
            }
        }
    }
}

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

Required methods

Apply a single substitution.

An Applier should add things and union them with eclass. Appliers can also inspect the eclass if necessary using the eclass parameter.

This should return a list of Ids of eclasses that were changed. There can be zero, one, or many. When explanations mode is enabled, a PatternAst for the searcher is provided.

Provided methods

Apply many substitutions.

This method should call apply_one for each match.

It returns the ids resulting from the calls to apply_one. The default implementation does this and should suffice for most use cases.

For patterns, get the ast directly as a reference.

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.

Implementors