Struct Engine 

pub struct Engine<T, M, R>
where
    T: Uniplate,
    R: Rule<T, M>,
{ /* private fields */ }

An engine for exhaustively transforming trees with user-defined rules.

See the morph method for more information.

Implementations

impl<T, M, R> Engine<T, M, R>

where T: Uniplate, R: Rule<T, M>,

pub fn morph(&self, tree: T, meta: M) -> (T, M)

where T: Uniplate, R: Rule<T, M>,

Exhaustively rewrites a tree using user-defined rule groups.

Rewriting is complete when all rules have been attempted with no change. Rules may be organised into groups to control the order in which they are attempted.

Rule Groups

If all rules are treated equally, those which apply higher in the tree will take precedence because of the left-most outer-most traversal order of the engine.

This can cause problems if a rule which should ideally be applied early (e.g. evaluating constant expressions) is left until later.

To solve this, rules are organised into different collections or “groups”. The engine will apply rules in an earlier group to the entire tree before trying later groups. That is, no rule is attempted if a rule in an earlier group is applicable to any part of the tree.

Selector Functions

If multiple rules in the same group are applicable to an expression, the user-defined selector function is used to choose one. This function is given an iterator over pairs of rules and the engine-created [Update] values which contain their modifications to the tree.

Some useful selector functions are available in the helpers module. One common function is select_first, which simply returns the first applicable rule.

Event Handlers

The engine provides events for more fine-tuned control over rewriting behaviour. Events have mutable access to the current metadata.

The engine will call the provided handlers for the “enter” and “exits” events as it enters and exits subtrees while traversing, respectively.

The “enter” event is triggered first on the root, and then whenever the engine moves down into a subtree. As a result, when a node is passed to rules, all nodes above it will have been passed to handlers for this event, in ascending order of their proximity to the root.

The “exit” event is triggered when the engine leaves a subtree. All nodes passed to “enter” event handlers (except the root) will also be passed to “exit” event handlers in reverse order.

In effect, before a node is passed to rules, all nodes in the path from the root (including the current node) will have been passed to the “enter” event in order. No nodes are skipped.

Event handling is useful when, for example, using a symbol table to keep track of variable definitions. When entering a scope where a variable is defined, one can place the variable and its value into the table. That stack can then be used for quick value lookup while inside the scope. When leaving the scope the variable can be removed from the table.

Optimizations

To optimize the morph function, we use a dirty/clean approach. Since whether a rule applies is purely a function of a node and its children, rules should only be checked once unless a node or one of its children has been changed.

Example

use tree_morph::{prelude::*, helpers::select_panic};
use uniplate::Uniplate;


// A simple language of multiplied and squared constant expressions
#[derive(Debug, Clone, PartialEq, Eq, Uniplate)]
#[uniplate()]
enum Expr {
    Val(i32),
    Mul(Box<Expr>, Box<Expr>),
    Sqr(Box<Expr>),
}

// a * b ~> (value of) a * b, where 'a' and 'b' are literal values
fn rule_eval_mul(cmds: &mut Commands<Expr, i32>, subtree: &Expr, meta: &i32) -> Option<Expr> {
    cmds.mut_meta(Box::new(|m: &mut i32| *m += 1));

    if let Expr::Mul(a, b) = subtree {
        if let (Expr::Val(a_v), Expr::Val(b_v)) = (a.as_ref(), b.as_ref()) {
            return Some(Expr::Val(a_v * b_v));
        }
    }
    None
}

// e ^ 2 ~> e * e, where e is an expression
// If this rule is applied before the sub-expression is fully evaluated, duplicate work
// will be done on the resulting two identical sub-expressions.
fn rule_expand_sqr(cmds: &mut Commands<Expr, i32>, subtree: &Expr, meta: &i32) -> Option<Expr> {
    cmds.mut_meta(Box::new(|m: &mut i32| *m += 1));

    if let Expr::Sqr(expr) = subtree {
        return Some(Expr::Mul(
            Box::new(*expr.clone()),
            Box::new(*expr.clone())
        ));
    }
    None
}

// (1 * 2) ^ 2
let expr = Expr::Sqr(
    Box::new(Expr::Mul(
        Box::new(Expr::Val(1)),
        Box::new(Expr::Val(2))
    ))
);

// Try with both rules in the same group, keeping track of the number of rule applications
let engine = EngineBuilder::new()
    .set_selector(select_panic)
    .add_rule_group(rule_fns![rule_eval_mul, rule_expand_sqr])
    .build();
let (result, num_applications) = engine.morph(expr.clone(), 0);
assert_eq!(result, Expr::Val(4));
assert_eq!(num_applications, 4); // The `Sqr` is expanded first, causing duplicate work

// Move the evaluation rule to an earlier group
let engine = EngineBuilder::new()
    .set_selector(select_panic)
    .add_rule_group(rule_fns![rule_eval_mul])
    .add_rule_group(rule_fns![rule_expand_sqr])
    .build();
let (result, num_applications) = engine.morph(expr.clone(), 0);
assert_eq!(result, Expr::Val(4));
assert_eq!(num_applications, 3); // Now the sub-expression (1 * 2) is evaluated first

Trait Implementations

impl<T, M, R> From<EngineBuilder<T, M, R>> for Engine<T, M, R>

where T: Uniplate, R: Rule<T, M>,

fn from(val: EngineBuilder<T, M, R>) -> Self

Converts to this type from the input type.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 176 bytes