[−][src]Trait egg::Runner

pub trait Runner<L, M> where
    L: Language,
    M: Metadata<L>, {
    type Error: Debug;
    fn pre_step(
        &mut self, 
        _egraph: &mut EGraph<L, M>
    ) -> Result<(), Self::Error> { ... }

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

    fn during_step(&mut self, _egraph: &EGraph<L, M>) -> Result<(), Self::Error> { ... }

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

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

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

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

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

Faciliates running rewrites over an EGraph.

One use for EGraphs is as the basis of a rewriting system. Since an egraph never "forgets" state when applying a Rewrite, you can apply many rewrites many times quite efficiently. After the egraph is "full" (the rewrites can no longer find new equalities) or some other condition, the egraph compactly represents many, many equivalent expressions. At this point, the egraph is ready for extraction (see Extractor) which can pick the represented expression that's best according to some cost function.

This technique is called equality saturation in general. However, there can be many challenges in implementing this "outer loop" of applying rewrites, mostly revolving around which rules to run and when to stop.

Implementing the Runner trait allows you to customize this outer loop in many ways. Many of Runners method have default implementation, and these call the various hooks (pre_step, during_step, post_step) during their operation.

SimpleRunner is egg's provided Runner that has reasonable defaults and implements many useful things like saturation checking, an egraph size limits, and rule back off. Consider using SimpleRunner before implementing your own Runner.

Associated Types

type Error: Debug

The type of an error that should stop the runner.

This will be recorded in RunReport.

Loading content...

Provided methods

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.

Default implementation simply returns Ok(()).

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.

Default implementation simply returns Ok(()).

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.

Default implementation simply returns Ok(()).

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.

Default implementation just calls Rewrite::search.

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.

Default implementation just calls Rewrite::apply and returns number of new applications.

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

Run the rewrites once on the egraph.

It first searches all the rules using the search_rewrite wrapper. Then it applies all the rules using the apply_rewrite wrapper.

Expectations

After searching or applying a rule, this should call during_step, returning immediately if it returns an error. This should not call pre_step or post_step, those should be called by the run method.

Default implementation just calls Rewrite::apply and returns number of new applications.

Default implementation

The default implementation is probably good enough. It conforms to all the above expectations, and it performs the necessary bookkeeping to return an Iteration. It additionally performs useful logging at the debug and info levels. If you're using env_logger (which the tests of egg do), see its documentation on how to see the logs.

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.

This should call pre_step, step, and post_step in a loop, in that order, until one of them returns an error. It returns the completed Iterations and the error that caused it to stop.

The default implementation does these things.

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.

The default implementation does exactly this, also performing the bookkeeping needed to return a RunReport.

Loading content...

Implementors

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

type Error = SimpleRunnerError

Loading content...