Struct egg::SimpleRunner

pub struct SimpleRunner { /* fields omitted */ }

A reasonable default Runner.

SimpleRunner is a Runner, so it runs rewrites over an EGraph. This implementation offers several conveniences to prevent rewriting from behaving badly and eating your computer:

• Saturation checking

  SimpleRunner checks to see if any of the rules added anything new to the EGraph. If none did, then it stops, returning SimpleRunnerError::Saturated.

• Iteration limits

  You can set a upper limit of iterations to do in case the search doesn't stop for some other reason. If this limit is hit, it stops with SimpleRunnerError::IterationLimit.

• EGraph size limit

  You can set a upper limit on the number of enodes in the egraph. If this limit is hit, it stops with SimpleRunnerError::NodeLimit.

• Rule backoff

  Some rules enable themselves, blowing up the EGraph and preventing other rewrites from running as many times. To prevent this, SimpleRunner implements exponentional rule backoff.

  For each rewrite, there exists a configurable initial match limit. If a rewrite search yield more than this limit, then we ban this rule for number of iterations, double its limit, and double the time it will be banned next time.

  This seems effective at preventing explosive rules like associativity from taking an unfair amount of resources.

Example

use egg::{*, rewrite as rw};

define_language! {
    enum SimpleLanguage {
        Num(i32),
        Add = "+",
        Mul = "*",
        Symbol(String),
    }
}

let rules: &[Rewrite<SimpleLanguage, ()>] = &[
    rw!("commute-add"; "(+ ?a ?b)" => "(+ ?b ?a)"),
    rw!("commute-mul"; "(* ?a ?b)" => "(* ?b ?a)"),

    rw!("add-0"; "(+ ?a 0)" => "?a"),
    rw!("mul-0"; "(* ?a 0)" => "0"),
    rw!("mul-1"; "(* ?a 1)" => "?a"),
];

let start = "(+ 0 (* 1 foo))".parse().unwrap();
// SimpleRunner is customizable in the builder pattern style.
let (egraph, report) = SimpleRunner::default()
    .with_iter_limit(10)
    .with_node_limit(10_000)
    .run_expr(start, &rules);
println!(
    "Stopped after {} iterations, reason: {:?}",
    report.iterations.len(),
    report.stop_reason
);

Methods

impl SimpleRunner

pub fn with_iter_limit(self, iter_limit: usize) -> Self

Sets the iteration limit. Default: 30

pub fn with_node_limit(self, node_limit: usize) -> Self

Sets the egraph size limit (in enodes). Default: 10,000

pub fn with_initial_match_limit(self, initial_match_limit: usize) -> Self

Sets the initial match limit before a rule is banned. Default: 1,000

Setting this to a really big number will effectively disable rule backoff.

Trait Implementations

impl Default for SimpleRunner

fn default() -> Self

Returns the "default value" for a type.

impl<L, M> Runner<L, M> for SimpleRunner where
    L: Language,
    M: Metadata<L>, 

type Error = SimpleRunnerError

The type of an error that should stop the runner.

fn pre_step(&mut self, egraph: &mut EGraph<L, M>) -> Result<(), Self::Error>

The pre-iteration hook. If this returns an error, then the search will stop. Useful for checking stop conditions or updating Runner state.

fn during_step(&mut self, egraph: &EGraph<L, M>) -> Result<(), Self::Error>

The intra-iteration hook. If this returns an error, then the search will stop. Useful for checking stop conditions. This is called after search each rule and after applying each rule.

fn post_step(
    &mut self,
    iteration: &Iteration,
    _egraph: &mut EGraph<L, M>
) -> Result<(), Self::Error>

The post-iteration hook. If this returns an error, then the search will stop. Useful for checking stop conditions or updating Runner state.

fn search_rewrite(
    &mut self,
    egraph: &mut EGraph<L, M>,
    rewrite: &Rewrite<L, M>
) -> Vec<SearchMatches>

A hook allowing you to customize rewrite search behavior. Useful to implement rule management.

fn apply_rewrite(
    &mut self,
    egraph: &mut EGraph<L, M>,
    rewrite: &Rewrite<L, M>,
    matches: Vec<SearchMatches>
) -> usize

A hook allowing you to customize rewrite application behavior. Useful to implement rule management.

fn step(
    &mut self,
    egraph: &mut EGraph<L, M>,
    rules: &[Rewrite<L, M>]
) -> Result<Iteration, Self::Error>

Run the rewrites once on the egraph.

fn run(
    &mut self,
    egraph: &mut EGraph<L, M>,
    rules: &[Rewrite<L, M>]
) -> (Vec<Iteration>, Self::Error)

Run the rewrites on the egraph until an error.

fn run_expr(
    &mut self,
    initial_expr: RecExpr<L>,
    rules: &[Rewrite<L, M>]
) -> (EGraph<L, M>, RunReport<L, Self::Error>)

Given an initial expression, make and egraph and [run] the rules on it.