Trait egg::Language

source · [−]
pub trait Language: Debug + Clone + Eq + Ord + Hash {
    type Discriminant: Debug + Clone + Eq + Hash;

Show 17 methods    fn discriminant(&self) -> Self::Discriminant;

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

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

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

    fn for_each<F: FnMut(Id)>(&self, f: F) { ... }

    fn for_each_mut<F: FnMut(&mut Id)>(&mut self, f: F) { ... }

    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: FnMut(Id) -> Id>(&mut self, f: F) { ... }

    fn map_children<F: FnMut(Id) -> Id>(self, f: F) -> Self { ... }

    fn fold<F, T>(&self, init: T, f: F) -> T
    where
        F: FnMut(T, Id) -> T,
        T: Clone,
    { ... }

    fn all<F: FnMut(Id) -> bool>(&self, f: F) -> bool { ... }

    fn any<F: FnMut(Id) -> bool>(&self, f: F) -> 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,
    { ... }

    fn try_build_recexpr<F, Err>(
        &self, 
        get_node: F
    ) -> Result<RecExpr<Self>, Err>
    where
        F: FnMut(Id) -> Result<Self, Err>,
    { ... }

}
Expand description

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.

Associated Types

Type representing the cases of this language.

Used for short-circuiting the search for equivalent nodes.

Required methods

Return the Discriminant of this node.

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

Returns the children of this e-node.

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

Provided methods

Runs a given function on each child Id.

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

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

Returns the number of the children this enode has.

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

Returns true if this enode has no children.

Runs a given function to replace the children.

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

Folds over the children, given an initial accumulator.

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

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

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())

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)

Same as Language::build_recexpr, but fallible.

Implementors