[][src]Crate egg

EGraphs (and almost everything else in this crate) are parameterized over the language given by the user (by implementing the Language trait).

If your Language implements FromStr (and Languages derived using define_language! do), you can easily create RecExprs to add to an EGraph.

Add egg to your Cargo.toml like this:

[dependencies]
egg = "0.4.0"

Example

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

define_language! {
    enum SimpleLanguage {
        Num(i32),
        "+" = Add([Id; 2]),
        "*" = Mul([Id; 2]),
        // language items are parsed in order, and we want symbol to
        // be a fallback, so we put it last
        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();
let runner = Runner::default().with_expr(&start).run(&rules);
println!(
    "Stopped after {} iterations, reason: {:?}",
    runner.iterations.len(),
    runner.stop_reason
);

Macros

define_language

A macro to easily create a Language.

rewrite

A macro to easily make Rewrites.

test_fn

Make a test function

Structs

AstDepth

A simple CostFunction that counts maximum ast depth.

AstSize

A simple CostFunction that counts total ast size.

BackoffScheduler

A RewriteScheduler that implements exponentional rule backoff.

ConditionEqual

A Condition that checks if two terms are equivalent.

ConditionalApplier

An Applier that checks a Condition before applying.

Dot

A wrapper for an EGraph that can output GraphViz for visualization.

EClass

An equivalence class of enodes.

EGraph

A data structure to keep track of equalities between expressions.

Extractor

Extracting a single RecExpr from an EGraph.

Iteration

Data generated by running a Runner one iteration.

Pattern

A pattern that can function as either a Searcher or Applier.

RecExpr

A recursive expression from a user-defined Language.

Rewrite

A rewrite that searches for the lefthand side and applies the righthand side.

Runner

Faciliates running rewrites over an EGraph.

SearchMatches

The result of searching a Searcher over one eclass.

SimpleScheduler

A very simple RewriteScheduler that runs every rewrite every time.

StringLang

A simple language used for testing.

Subst

A substitition mapping Vars to eclass Ids.

Var

A variable for use in Patterns or Substs.

Enums

StopReason

Error returned by Runner when it stops.

Traits

Analysis

Arbitrary data associated with an EClass.

Applier

The righthand side of a Rewrite.

Condition

A condition to check in a ConditionalApplier.

CostFunction

A cost function that can be used by an Extractor.

IterationData

Custom data to inject into the Iterations recorded by a Runner

Language

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

RewriteScheduler

A way to customize how a Runner runs Rewrites.

Searcher

The lefthand side of a Rewrite.

Functions

merge_if_different

Replace the first with second value if they are different returning whether or not something was done.

Type Definitions

Id

A key to identify EClasses within an EGraph.