[][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.1.2"

Example

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

define_language! {
    enum SimpleLanguage {
        Num(i32),
        Add = "+",
        Mul = "*",
        // 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 (egraph, report) = SimpleRunner::default().run_expr(start, &rules);
println!(
    "Stopped after {} iterations, reason: {:?}",
    report.iterations.len(),
    report.stop_reason
);

Macros

define_language

A macro to easily create a Language.

enode

Utility macro to create an ENode.

recexpr

Utility macro to create an RecExpr.

rewrite

A macro to easily make Rewrites.

Structs

AstDepth

A simple CostFunction that counts maximum ast depth.

AstSize

A simple CostFunction that counts total ast size.

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.

ENode

An operator from the user-defined Language with some children.

Extractor

Extracting a single RecExpr from an EGraph.

Iteration

Data generated by running a Runner one iteration.

ParseError

An error resulting from parsing a Pattern or RecExpr.

QuestionMarkName

A wildcard for use in Patterns or WildMaps.

RecExpr

A recursive expression from a user-defined Language.

Rewrite

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

RunReport

Data generated by running a Runner to completion.

SearchMatches

The result of searching a Searcher over one eclass.

SimpleRunner

A reasonable default Runner.

WildMap

A substitition mapping QuestionMarkNames to eclass Ids.

Enums

Pattern

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

SimpleRunnerError

Error returned by SimpleRunner when it stops.

Traits

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.

Language

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

Metadata

Arbitrary data associated with an EClass.

Runner

Faciliates running rewrites over an EGraph.

Searcher

The lefthand side of a Rewrite.

Type Definitions

Id

The type of an eclass id in the EGraph