Struct egg::Pattern

pub struct Pattern<L> {
    pub ast: PatternAst<L>,
    /* private fields */
}

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 new(ast: PatternAst<L>) -> Self

Creates a new pattern from the given pattern ast.

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

Returns a list of the Vars in this pattern.

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

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 get_pattern_ast(&self) -> Option<&PatternAst<L>>

For patterns, get the ast directly as a reference.

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

Apply many substitutions.

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 vars(&self) -> Vec<Var>

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

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

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

Formats the value using the given formatter.

impl<L: Language> From<&'_ RecExpr<L>> for Pattern<L>

fn from(expr: &RecExpr<L>) -> Self

Performs the conversion.

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

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

Performs the conversion.

impl<L: Language> From<RecExpr<ENodeOrVar<L>>> for Pattern<L>

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

Performs the conversion.

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

type Err = RecExprParseError<ENodeOrVarParseError<L::Error>>

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 get_pattern_ast(&self) -> Option<&PatternAst<L>>

For patterns, return the ast directly as a reference

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

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

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 n_matches(&self, egraph: &EGraph<L, N>) -> usize

Returns the number of matches in the e-graph

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.

impl<L: Eq> Eq for Pattern<L>

impl<L> StructuralEq for Pattern<L>

impl<L> StructuralPartialEq for Pattern<L>