Struct egg::Pattern

pub struct Pattern<L> {
    pub ast: PatternAst<L>,
    // some fields omitted
}

A pattern that can function as either a Searcher or Applier.

A Pattern is essentially a for-all quantified expression with Vars 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 (Substs) 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 Patterns.

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

impl<L: Language> Pattern<L>

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

Returns a list of the Vars in this pattern.

pub fn pretty(&self, width: usize) -> String

Pretty print this pattern as a sexp with the given width

Trait Implementations

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

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

Apply a single substitition.

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

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

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

Apply many substititions.

impl<L: Clone> Clone for Pattern<L>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<L: Debug> Debug for Pattern<L>

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

Formats the value using the given formatter.

impl<L: Language> Display for Pattern<L>

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

Formats the value using the given formatter.

impl<'a, L: Language> From<&'a [L]> for Pattern<L>

fn from(expr: &'a [L]) -> Self

Performs the conversion.

impl<'a, L: Language> From<RecExpr<ENodeOrVar<L>>> for Pattern<L>

fn from(ast: PatternAst<L>) -> Self

Performs the conversion.

impl<L: Language> FromStr for Pattern<L>

type Err = String

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<Pattern<L>> for Pattern<L>

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

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Pattern<L>) -> bool

This method tests for !=.

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

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

Search the whole [EGraph], returning a list of all the [SearchMatches] where something was found. This just calls [search_eclass] on each eclass.

fn search_eclass(
    &self,
    egraph: &EGraph<L, A>,
    eclass: Id
) -> Option<SearchMatches>

Search one eclass, returning None if no matches can be found. This should not return a SearchMatches with no substs.

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

Returns a list of the variables bound by this Searcher

impl<L> StructuralPartialEq for Pattern<L>

impl<L: Language> TryFrom<Pattern<L>> for RecExpr<L>

type Error = Var

The type returned in the event of a conversion error.

fn try_from(pat: Pattern<L>) -> Result<Self, Self::Error>

Performs the conversion.