pub struct Pattern<L> {
pub ast: PatternAst<L>,
/* private fields */
}
Expand description
A pattern that can function as either a Searcher
or Applier
.
A Pattern
is essentially a for-all quantified expression with
Var
s as the variables (in the logical sense).
When creating a Rewrite
, the most common thing to use as either
the left hand side (the Searcher
) or the right hand side
(the Applier
) is a Pattern
.
As a Searcher
, a Pattern
does the intuitive
thing.
Here is a somewhat verbose formal-ish statement:
Searching for a pattern in an egraph yields substitutions
(Subst
s) s such that, for any s’—where instead of
mapping a variables to an eclass as s does, s’ maps
a variable to an arbitrary expression represented by that
eclass—p[s’] (the pattern under substitution s’) is also
represented by the egraph.
As an Applier
, a Pattern
performs the given substitution
and adds the result to the EGraph
.
Importantly, Pattern
implements FromStr
if the
Language
does.
This is probably how you’ll create most Pattern
s.
use egg::*;
define_language! {
enum Math {
Num(i32),
"+" = Add([Id; 2]),
}
}
let mut egraph = EGraph::<Math, ()>::default();
let a11 = egraph.add_expr(&"(+ 1 1)".parse().unwrap());
let a22 = egraph.add_expr(&"(+ 2 2)".parse().unwrap());
// use Var syntax (leading question mark) to get a
// variable in the Pattern
let same_add: Pattern<Math> = "(+ ?a ?a)".parse().unwrap();
// Rebuild before searching
egraph.rebuild();
// This is the search method from the Searcher trait
let matches = same_add.search(&egraph);
let matched_eclasses: Vec<Id> = matches.iter().map(|m| m.eclass).collect();
assert_eq!(matched_eclasses, vec![a11, a22]);
Fields
ast: PatternAst<L>
The actual pattern as a RecExpr
Implementations
Trait Implementations
sourceimpl<L, A> Applier<L, A> for Pattern<L> where
L: Language,
A: Analysis<L>,
impl<L, A> Applier<L, A> for Pattern<L> where
L: Language,
A: Analysis<L>,
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.
sourcefn apply_matches(
&self,
egraph: &mut EGraph<L, A>,
matches: &[SearchMatches<'_, L>],
rule_name: Symbol
) -> Vec<Id>
fn apply_matches(
&self,
egraph: &mut EGraph<L, A>,
matches: &[SearchMatches<'_, L>],
rule_name: Symbol
) -> Vec<Id>
Apply many substititions. Read more
sourceimpl<L: Language> From<RecExpr<ENodeOrVar<L>>> for Pattern<L>
impl<L: Language> From<RecExpr<ENodeOrVar<L>>> for Pattern<L>
sourcefn from(ast: PatternAst<L>) -> Self
fn from(ast: PatternAst<L>) -> Self
Converts to this type from the input type.
sourceimpl<L: Language, A: Analysis<L>> Searcher<L, A> for Pattern<L>
impl<L: Language, A: Analysis<L>> Searcher<L, A> for Pattern<L>
sourcefn get_pattern_ast(&self) -> Option<&PatternAst<L>>
fn get_pattern_ast(&self) -> Option<&PatternAst<L>>
For patterns, return the ast directly as a reference
sourcefn search(&self, egraph: &EGraph<L, A>) -> Vec<SearchMatches<'_, L>>
fn search(&self, egraph: &EGraph<L, A>) -> Vec<SearchMatches<'_, L>>
Search the whole EGraph
, returning a list of all the
SearchMatches
where something was found.
This just calls search_eclass
on each eclass. Read more
sourcefn search_eclass(
&self,
egraph: &EGraph<L, A>,
eclass: Id
) -> Option<SearchMatches<'_, L>>
fn search_eclass(
&self,
egraph: &EGraph<L, A>,
eclass: Id
) -> Option<SearchMatches<'_, L>>
Search one eclass, returning None if no matches can be found. This should not return a SearchMatches with no substs. Read more
impl<L> StructuralPartialEq for Pattern<L>
Auto Trait Implementations
impl<L> RefUnwindSafe for Pattern<L> where
L: RefUnwindSafe,
impl<L> Send for Pattern<L> where
L: Send,
impl<L> Sync for Pattern<L> where
L: Sync,
impl<L> Unpin for Pattern<L> where
L: Unpin,
impl<L> UnwindSafe for Pattern<L> where
L: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more