Struct MultiPattern

pub struct MultiPattern<L> { /* private fields */ }

A set of open expressions bound to variables.

Multipatterns bind many expressions to variables, allowing for simultaneous searching or application of many terms constrained to the same substitution.

Multipatterns are good for writing graph rewrites or datalog-style rules.

You can create multipatterns via the MultiPattern::new function or the multi_rewrite! macro.

MultiPattern implements both Searcher and Applier. When searching a multipattern, the result ensures that patterns bound to the same variable are equivalent. When applying a multipattern, patterns bound a variable occuring in the searcher are unioned with that e-class.

Multipatterns currently do not support the explanations feature.

Implementations

impl<L: Language> MultiPattern<L>

pub fn new(asts: Vec<(Var, PatternAst<L>)>) -> Self

Creates a new multipattern, binding the given patterns to the corresponding variables.

use egg::*;

let mut egraph = EGraph::<SymbolLang, ()>::default();
egraph.add_expr(&"(f a a)".parse().unwrap());
egraph.add_expr(&"(f a b)".parse().unwrap());
egraph.add_expr(&"(g a a)".parse().unwrap());
egraph.add_expr(&"(g a b)".parse().unwrap());
egraph.rebuild();

let f_pat: PatternAst<SymbolLang> = "(f ?x ?y)".parse().unwrap();
let g_pat: PatternAst<SymbolLang> = "(g ?x ?y)".parse().unwrap();
let v1: Var = "?v1".parse().unwrap();
let v2: Var = "?v2".parse().unwrap();

let multipattern = MultiPattern::new(vec![(v1, f_pat), (v2, g_pat)]);
// you can also parse multipatterns
assert_eq!(multipattern, "?v1 = (f ?x ?y), ?v2 = (g ?x ?y)".parse().unwrap());

assert_eq!(multipattern.n_matches(&egraph), 2);

Trait Implementations

impl<L: Language, A: Analysis<L>> Applier<L, A> for MultiPattern<L>

fn apply_one( &self, _egraph: &mut EGraph<L, A>, _eclass: Id, _subst: &Subst, _searcher_ast: Option<&PatternAst<L>>, _rule_name: Symbol, ) -> Vec<Id>

Apply a single substitution.

fn apply_matches( &self, egraph: &mut EGraph<L, A>, matches: &[SearchMatches<'_, L>], _rule_name: Symbol, ) -> Vec<Id>

Apply many substitutions.

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

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

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

For patterns, get the ast directly as a reference.

impl<L: Clone> Clone for MultiPattern<L>

fn clone(&self) -> MultiPattern<L>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<L: Debug> Debug for MultiPattern<L>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<L: Language + FromOp> FromStr for MultiPattern<L>

type Err = MultiPatternParseError<<RecExpr<ENodeOrVar<L>> as FromStr>::Err>

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Self, Self::Err>

Parses a string s to return a value of this type.

impl<L: PartialEq> PartialEq for MultiPattern<L>

fn eq(&self, other: &MultiPattern<L>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<L: Language, A: Analysis<L>> Searcher<L, A> for MultiPattern<L>

fn search_eclass_with_limit( &self, egraph: &EGraph<L, A>, eclass: Id, limit: usize, ) -> Option<SearchMatches<'_, L>>

Similar to search_eclass, but return at most limit many matches.

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

Returns a list of the variables bound by this Searcher

fn search_eclass( &self, egraph: &EGraph<L, N>, 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.

fn search(&self, egraph: &EGraph<L, N>) -> Vec<SearchMatches<'_, L>>

Search the whole EGraph, returning a list of all the SearchMatches where something was found. This just calls Searcher::search_with_limit with a big limit.

fn search_with_limit( &self, egraph: &EGraph<L, N>, limit: usize, ) -> Vec<SearchMatches<'_, L>>

Similar to search, but return at most limit many matches.

fn n_matches(&self, egraph: &EGraph<L, N>) -> usize

Returns the number of matches in the e-graph

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

For patterns, return the ast directly as a reference

impl<L: Eq> Eq for MultiPattern<L>

impl<L> StructuralPartialEq for MultiPattern<L>