All Classes and Interfaces
Class
Description
An e-class analysis: a fact of type
D for every e-class, kept true as the graph
changes (egg's Analysis trait, the paper's section 4).What applying one match did, in the two senses a run needs.
A rewrite's right-hand side: given a match, adds whatever it adds to the graph and returns the
classes to make equal to the matched class.
egg's
BackoffScheduler, the runner's default: a rule whose matches in one iteration
exceed its match limit is banned for a number of iterations, and each time it is banned again
its limit and its ban double, so a rule that would grow the graph without bound - associativity,
commutativity, distributivity - gets its turn less and less often while the other rules
finish their work.A rewrite's side condition: whether a match may be applied, read from the graph - the facts
of the bound classes, their nodes - and the substitution.
What a term costs, for extraction.
An equivalence class of e-nodes: its id, its nodes, its parents and its analysis fact.
An e-graph: a union-find over e-class ids, a hashcons from canonical e-nodes to the class each
is in, and the classes themselves - egg's
EGraph, the paper's Figure 4, with the
data structures in plain Java.An extracted term: the node chosen for a class over the terms chosen for its children.
Extraction: the cheapest term in a class under a
CostFunction, as a bottom-up fixed
point over the classes (the paper's section 4.3, egg's Extractor); and
Extractor.extractAll(IntList) over several roots at once, which chooses one node per class so that a
subterm the roots share is chosen once and paid once - what egg's per-root extraction cannot
do, and the case a compiler with many outputs over shared prefixes is in (PLAN.md 3.2).A class's best node and the cost of the tree rooted there.
An immutable list of
ints: the children of an e-node, held as e-class ids.An e-node of a client's language: an operator, a payload and children held as e-class ids.
E-matching by backtracking: a pattern is matched against a class by trying each of the class's
nodes whose head matches, then each child pattern against the child's class, threading the
substitution through and backtracking by discarding it. egg's compiled machine is the
replacement if a measurement asks for it.
One match: the class the pattern's root matched in, and what its variables stand for.
Several patterns joined, egg's
MultiPattern: a list of clauses ?var = pattern.One clause: a pattern that must match in the class a variable names.
A pattern over a language: a variable, which matches any e-class and binds it, or a node,
whose
Pattern.Head matches an e-node's operator and payload and whose children are patterns.What a pattern node says about an e-node's operator and payload, and how it builds one.
An operator with its payload constraint, over child patterns in argument order.
A variable: matches any class, binding it; or must agree with its binding.
A named rewrite: a left-hand
Searcher (a pattern, or several joined in a
MultiPattern), a right-hand Applier and a Condition.Where a run stops if it has not saturated: after this many iterations, or once the graph
holds more than this many nodes or classes.
Equality saturation (the paper's Figure 5b): each iteration searches every rule over the
graph as it stands, then applies every match found, then rebuilds once; it stops when an
iteration changes nothing and counts nothing as applied (a multi-pattern right-hand side counts
every match, as egg's does; see
Applied), a RunLimits limit is hit or a
Runner.Hook asks, and reports what it did.Run before each iteration, on the rebuilt graph (egg's
with_hook): a reason to stop
ends the run with StopReason.Other, an empty one (never null) lets the
iteration go ahead.The wall time of one iteration's three phases, in nanoseconds (egg's
Iteration
carries the same three): searching every rule, applying every match, and the rebuild.What a run did, iteration by iteration, and why it stopped: the record a client's plan quotes.
One iteration: the graph's size after its rebuild, the matches each rule was given to
apply, the rules the scheduler held back (whose matches read zero for that reason), the
rules whose matches were not applied because a limit was passed before their turn, how
many matches were applied (their condition held at apply time), how many unions merged two
classes that were different, how many applications egg would count as applied (the input
of the stop rule,
Applied), and how many parent entries the rebuild repaired.What decides, each iteration, which of a rule's matches are applied (egg's
RewriteScheduler).What a
Rewrite searches with: a Pattern, or a MultiPattern that joins
several. egg's Searcher trait, reduced to what the runner and the schedulers use: the
matches, to a limit, and the variables they bind.One node chosen per class, for the classes some roots reach: the result of extraction over
several roots at once, where a subterm two roots share is one choice paid once.
Why a run ended.
The graph grew past the class limit.
The iteration limit was reached.
The graph grew past the node limit.
A
Runner.Hook stopped the run, for the reason it gave (egg's Other).No rule changed the graph in the last iteration, and the scheduler had nothing held back.
A substitution: what a pattern's variables stand for in one match.
How a client's own tree type becomes e-nodes and comes back: the three functions
EGraph.addTree(T, TreeBridge) and an extractor need, so that a client whose terms are an existing
tree of records - children held as nodes, not ids - does not mirror its language by hand.