pub trait Applier<L, N>where
L: Language,
N: Analysis<L>,{
// Required method
fn apply_one(
&self,
egraph: &mut EGraph<L, N>,
eclass: Id,
subst: &Subst,
searcher_ast: Option<&PatternAst<L>>,
rule_name: Symbol
) -> Vec<Id>;
// Provided methods
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
Condition
s 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: &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§
sourcefn apply_one(
&self,
egraph: &mut EGraph<L, N>,
eclass: Id,
subst: &Subst,
searcher_ast: Option<&PatternAst<L>>,
rule_name: Symbol
) -> Vec<Id>
fn apply_one( &self, egraph: &mut EGraph<L, N>, eclass: Id, subst: &Subst, searcher_ast: Option<&PatternAst<L>>, rule_name: Symbol ) -> Vec<Id>
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 Id
s 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§
sourcefn apply_matches(
&self,
egraph: &mut EGraph<L, N>,
matches: &[SearchMatches<'_, L>],
rule_name: Symbol
) -> Vec<Id>
fn apply_matches( &self, egraph: &mut EGraph<L, N>, matches: &[SearchMatches<'_, L>], rule_name: Symbol ) -> Vec<Id>
sourcefn get_pattern_ast(&self) -> Option<&PatternAst<L>>
fn get_pattern_ast(&self) -> Option<&PatternAst<L>>
For patterns, get the ast directly as a reference.