E-graphs and equality saturation for Java 25, a port of egg (Willsey et al., POPL 2021), with extraction over several roots that keeps a shared subterm in one form.
A language is one record: the operator and its payload in op, the children in the record's
IntList.
record Node(String op, IntList children) implements Language<Node> {
public Node withChildren(IntList c) { return new Node(op, c); }
}With it, the rewrite x + 0 -> x is seven lines; the dependency is in Using it:
EGraph<Node, Void> g = EGraph.withoutAnalysis();
int x = g.add(new Node("x", IntList.EMPTY));
int sum = g.add(new Node("+", IntList.of(x, g.add(new Node("0", IntList.EMPTY)))));
Pattern<Node> v = Pattern.var("v");
Runner.of(g, List.of(Rewrite.of("x + 0 -> x", Pattern.of(new Node("+", IntList.EMPTY), v,
Pattern.of(new Node("0", IntList.EMPTY))), v))).run();
Extracted<Node> best = new Extractor<>(g, CostFunction.astSize()).extract(sum); // Node[op=x]It saturates in one iteration, and best.node() is the x node;
QuickStartTest runs it on every
build. docs/first-language.md goes further: payloads, a TreeBridge,
a rule that binds a payload, and extraction over several roots.
- A compiler or query optimizer choosing among equivalent forms for many outputs: an e-class is every way to compute one value, and extraction chooses one form per class, paying a shared subterm once.
- A DSL or rules engine simplifying terms with rules that interact: saturation runs them to a fixpoint, and analyses carry facts the rules read.
- A simplifier or verifier that wants the cheapest or smallest term, or all roots at once: extraction under a client cost function, over one root or several.
- Not for a fixed, small rule set with no analysis and one root, where a hand-written pass is
simpler;
docs/egg-comparison.mdlists what else is not ported.
sealed interface Arith extends Language<Arith> permits Num, Var, Add, Mul {}
record Num(long value) implements Arith { /* no children */ }
record Var(String name) implements Arith { /* no children */ }
record Add(IntList children) implements Arith { /* withChildren(c) -> new Add(c) */ }
record Mul(IntList children) implements Arith { /* withChildren(c) -> new Mul(c) */ }
EGraph<Arith, Void> g = EGraph.withoutAnalysis();
int a = g.add(new Var("a"));
int root = g.add(new Add(IntList.of(
g.add(new Mul(IntList.of(a, g.add(new Num(2))))), g.add(new Num(0))))); // (a * 2) + 0
Pattern<Arith> x = Pattern.var("x");
List<Rewrite<Arith, Void>> rules = List.of(
Rewrite.of("add-0", Pattern.of(new Add(IntList.EMPTY), x, Pattern.of(new Num(0))), x),
Rewrite.of("mul-2", Pattern.of(new Mul(IntList.EMPTY), x, Pattern.of(new Num(2))),
Pattern.of(new Add(IntList.EMPTY), x, x)));
RunReport report = Runner.of(g, rules).run(); // saturates in a few steps
Extracted<Arith> best = new Extractor<>(g, CostFunction.astSize()).extract(root); // a * 2The whole example, with the records written out, is
ReadmeExampleTest,
which runs on every build.
Status. The library is complete to the plan's eighth step (PLAN.md 8):
e-graph, rebuilding, analyses, patterns and rewrites, the runner with egg's
backoff scheduler, extraction over one root and over several, and the
measurement harness. egg's five test suites (simple, prop, lambda,
math, datalog) are ported test for test, each run checked against egg's own
iteration, node and class counts; the library has egg's multi-patterns too. Every build prints the tests' coverage of
src/main (98% of lines). Version 0.1.2 is on Maven Central (Using it);
the API still moves between minor versions while it is 0.x, and CHANGELOG.md and
CONTRIBUTING.md ("Releases") say what each release changed, how versions are numbered and
what a 0.x adopter can rely on.
An e-graph holds many equivalent terms at once: a union-find over e-class ids,
a hashcons from e-nodes to classes, deferred rebuilding that restores
congruence once per iteration rather than after every merge, e-class analyses
that carry facts (constants, ranges, types) up the graph as a semilattice,
rewrites matched against the whole graph and applied in a batch, a runner with
node and iteration limits, and an extractor that picks the cheapest term under
a cost function. egg's paper gives the algorithms; this library ports them to
plain Java 25 - records, sealed hierarchies, int ids - and adds one property
egg does not promise: the extracted term is a function of the input, with
iteration order fixed wherever it could reach an id.
Three things egg's API does not have and a compiler client needs are in from
the start: e-nodes with payloads and a TreeBridge from a client's own tree
type, patterns that bind payloads as well as subterms, and extractAll over
several roots that chooses one node per class and pays a shared subterm once.
Proof production, s-expression parsing and ILP extraction are deliberately out;
docs/egg-comparison.md lists everything else egg has that jegg does not.
It was planned for Varka, which will use it to choose physical representations over a whole projection, but it has no Spark dependency and nothing in it is specific to Varka.
docs/concepts.md: the ideas, each with the jegg type that embodies it and the paper's section, for a reader new to e-graphs.docs/why-jegg.md: for the Java developer weighing a small e-graph of their own, the pitfalls jegg already handles and when writing one is the better call.docs/egg-comparison.md: for a reader who knows egg, what is and is not ported, module by module, and what jegg adds.docs/first-language.md: a language with a payload, a bridge from your own tree, a rule that binds a payload, and an extraction over several roots.dev/explore.sh prop|math <rules-file> '<term>': tries a rule set and a term without writing Java, with--jsonfor structured output;dev/explore.sh --helpfor the syntax.- Javadoc of the public surface:
EGraph,Language,TreeBridge,Analysis,Pattern,MultiPattern,Searcher,Subst,Rewrite,Condition,Applier,Applied,Runner,RunLimits,RunReport,Scheduler,Extractor,Selection,CostFunction. PLAN.md: where the library came from, the design, egg's components mapped to their Java forms, and the outcome of the measurement.docs/skills/: what this repository learned the hard way, one page per lesson, for whoever touches that area next.
Three files under benchmarks/, each naming the commit, JDK,
machine and load it was measured under (benchmarks/README.md says how):
RebuildBenchmark: deferred rebuilding against rebuilding after every merge, on the ported suites; within noise below 300 nodes, over 10x on a 14,600-node run (lambda_fib: 3.1 s against 0.2 s).ProjectionBenchmark: a 64-node projection with 20 rules, as a compiler would run it; saturation to a 200-node limit in 0.10 ms warm, extraction over 20 roots in 0.11 ms.DeterminismRun: ten fresh JVMs render the same graph byte for byte.
An issue stating the problem or goal, then a plan in the issue, then the code as
a pull request: CONTRIBUTING.md has the order, the why,
and the practical half (running one test, the slow tests, the benchmarks, the
counts pinned to egg). Issues labelled
good first issue
have their plans written and are sized for a first pull request.
jegg 0.1.2 is on Maven Central:
<dependency>
<groupId>io.github.vecbricks</groupId>
<artifactId>jegg</artifactId>
<version>0.1.2</version>
</dependency>The artifact is a module, io.github.vecbricks.jegg; its only dependency, JSpecify's
annotations, is requires static (not needed at run time), and the pom supplies it at compile
time, so a modular build finds it on the module path. Java 25.
Java 25 and Maven:
mvn -B verify
Group id io.github.vecbricks, artifact jegg, package io.github.vecbricks.jegg.
Apache License 2.0. egg is MIT-licensed; its notice is in NOTICE.