Trait Language 

pub trait Language:
    Debug
    + Clone
    + Eq
    + Ord
    + Hash {
    // Required methods
    fn matches(&self, other: &Self) -> bool;
    fn children(&self) -> &[Id];
    fn children_mut(&mut self) -> &mut [Id];

    // Provided methods
    fn for_each<F>(&self, f: F)
       where F: FnMut(Id) { ... }
    fn for_each_mut<F>(&mut self, f: F)
       where F: FnMut(&mut Id) { ... }
    fn try_for_each<E, F>(&self, f: F) -> Result<(), E>
       where F: FnMut(Id) -> Result<(), E>,
             E: Clone { ... }
    fn len(&self) -> usize { ... }
    fn is_leaf(&self) -> bool { ... }
    fn update_children<F>(&mut self, f: F)
       where F: FnMut(Id) -> Id { ... }
    fn map_children<F>(self, f: F) -> Self
       where F: FnMut(Id) -> Id { ... }
    fn fold<F, T>(&self, init: T, f: F) -> T
       where F: FnMut(T, Id) -> T,
             T: Clone { ... }
    fn all<F>(&self, f: F) -> bool
       where F: FnMut(Id) -> bool { ... }
    fn any<F>(&self, f: F) -> bool
       where F: FnMut(Id) -> bool { ... }
    fn join_recexprs<F, Expr>(&self, child_recexpr: F) -> RecExpr<Self>
       where F: FnMut(Id) -> Expr,
             Expr: AsRef<[Self]> { ... }
    fn build_recexpr<F>(&self, get_node: F) -> RecExpr<Self>
       where F: FnMut(Id) -> Self { ... }
}

Trait that defines a Language whose terms will be in the EGraph.

Check out the define_language! macro for an easy way to create a Language.

If you want to pretty-print expressions, you should implement Display to display the language node’s operator. For example, a language node Add([Id; 2]) might be displayed as “+”.

To parse expressions from strings you should also implement FromOp.

The define_language! macro automatically implements both Display and FromOp.

See SymbolLang for quick-and-dirty use cases.

Required Methods

fn matches(&self, other: &Self) -> bool

Returns true if this enode matches another enode. This should only consider the operator, not the children Ids.

fn children(&self) -> &[Id]

Returns the children of this e-node.

fn children_mut(&mut self) -> &mut [Id]

Returns a mutable slice of the children of this e-node.

Provided Methods

fn for_each<F>(&self, f: F)

where F: FnMut(Id),

Runs a given function on each child Id.

fn for_each_mut<F>(&mut self, f: F)

where F: FnMut(&mut Id),

Runs a given function on each child Id, allowing mutation of that Id.

fn try_for_each<E, F>(&self, f: F) -> Result<(), E>

where F: FnMut(Id) -> Result<(), E>, E: Clone,

Runs a falliable function on each child, stopping if the function returns an error.

fn len(&self) -> usize

Returns the number of the children this enode has.

The default implementation uses fold to accumulate the number of children.

fn is_leaf(&self) -> bool

Returns true if this enode has no children.

fn update_children<F>(&mut self, f: F)

where F: FnMut(Id) -> Id,

Runs a given function to replace the children.

fn map_children<F>(self, f: F) -> Self

where F: FnMut(Id) -> Id,

Creates a new enode with children determined by the given function.

fn fold<F, T>(&self, init: T, f: F) -> T

where F: FnMut(T, Id) -> T, T: Clone,

Folds over the children, given an initial accumulator.

fn all<F>(&self, f: F) -> bool

where F: FnMut(Id) -> bool,

Returns true if the predicate is true on all children. Does not short circuit.

fn any<F>(&self, f: F) -> bool

where F: FnMut(Id) -> bool,

Returns true if the predicate is true on any children. Does not short circuit.

fn join_recexprs<F, Expr>(&self, child_recexpr: F) -> RecExpr<Self>

where F: FnMut(Id) -> Expr, Expr: AsRef<[Self]>,

Make a RecExpr by mapping this enodes children to other RecExprs.

This can be used to join together different expression with a new node.

Example

let a_plus_2: RecExpr<SymbolLang> = "(+ a 2)".parse().unwrap();
// here's an enode with some meaningless child ids
let enode = SymbolLang::new("*", vec![Id::from(0), Id::from(0)]);
// make a new recexpr, replacing enode's children with a_plus_2
let recexpr = enode.join_recexprs(|_id| &a_plus_2);
assert_eq!(recexpr, "(* (+ a 2) (+ a 2))".parse().unwrap())

fn build_recexpr<F>(&self, get_node: F) -> RecExpr<Self>

where F: FnMut(Id) -> Self,

Build a RecExpr from an e-node.

The provided get_node function must return the same node for a given Id on multiple invocations.

Example

You could use this method to perform an “ad-hoc” extraction from the e-graph, where you already know which node you want pick for each class:

let mut egraph = EGraph::<SymbolLang, ()>::default();
let expr = "(foo (bar1 (bar2 (bar3 baz))))".parse().unwrap();
let root = egraph.add_expr(&expr);
let get_first_enode = |id| egraph[id].nodes[0].clone();
let expr2 = get_first_enode(root).build_recexpr(get_first_enode);
assert_eq!(expr, expr2)

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl Language for Lambda

implement egg-compatability for Lambda

impl Language for SymbolLang

impl<L> Language for ENodeOrVar<L>

where L: Language,