Struct Pattern

pub struct Pattern<L> {
    pub ast: RecExpr<ENodeOrVar<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: RecExpr<ENodeOrVar<L>>

The actual pattern as a RecExpr

Implementations

impl<L> Pattern<L>

where L: Language,

pub fn new(ast: RecExpr<ENodeOrVar<L>>) -> Pattern<L>

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

where L: Language + Display,

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<&RecExpr<ENodeOrVar<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 substititions.

fn apply_one( &self, egraph: &mut EGraph<L, A>, eclass: Id, subst: &Subst, searcher_ast: Option<&RecExpr<ENodeOrVar<L>>>, rule_name: Symbol, ) -> Vec<Id>

Apply a single substitition.

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

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

impl<L> Clone for Pattern<L>

where L: Clone,

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<L> Debug for Pattern<L>

where L: Debug,

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

Formats the value using the given formatter.

impl<L> Display for Pattern<L>

where L: Language + Display,

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

Formats the value using the given formatter.

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

where L: Language,

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

Converts to this type from the input type.

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

where L: Language,

fn from(ast: RecExpr<ENodeOrVar<L>>) -> Pattern<L>

Converts to this type from the input type.

impl<L> FromStr for Pattern<L>

where L: FromOp,

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

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Pattern<L>, <Pattern<L> as FromStr>::Err>

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

impl<L> PartialEq for Pattern<L>

where L: PartialEq,

fn eq(&self, other: &Pattern<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, A> Searcher<L, A> for Pattern<L>

where L: Language, A: Analysis<L>,

fn get_pattern_ast(&self) -> Option<&RecExpr<ENodeOrVar<L>>>

For patterns, return the ast directly as a reference

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.

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.

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

Returns a list of the variables bound by this Searcher

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

Returns the number of matches in the e-graph

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

where L: Language,

type Error = Var

The type returned in the event of a conversion error.

fn try_from( pat: Pattern<L>, ) -> Result<RecExpr<L>, <RecExpr<L> as TryFrom<Pattern<L>>>::Error>

Performs the conversion.

impl<L> StructuralPartialEq for Pattern<L>