E-Graph Visualization

An interactive visualization of e-graphs and equality saturation, based on the paper "egg: Fast and Extensible Equality Saturation". This project demonstrates how the equality saturation algorithm works step-by-step using an interactive web interface.

• Two engines: naive (restore invariants after every union) and deferred (egg's rebuilding: read every match into a writelist, apply them all, then compact and repair once).
• Parallel workers: in deferred mode ×1–×32 workers run the read and write phases in lock-step rounds. Reading, each worker scans one e-class per step; matches light up and are queued in the writelist. Writing, each worker applies one writelist entry per step. Try the Parallel Matching preset.
• Real execution time: switch the scrub bar from Steps to Time (or press T). The engine is benchmarked in a web worker (hundreds of snapshot-free runs, every task timed), each step becomes as wide as it takes, parallel steps show one lane per worker, and playback runs in scaled real time. The comparison panel puts naive, deferred ×1 and deferred ×N side by side, stage by stage.
• Every step is a snapshot: init → read → write → compact → repair → … → done. Scrub, step, jump by phase, or play with smooth animations between snapshots. The scrub bar has one segment per animation, colored by the phase it animates, with ticks at phase changes and iteration starts.
• Faithful rebuilding: unions leave stale e-node children and hashcons keys behind; repair re-canonicalizes parents, merges congruent ones and removes duplicate e-nodes, exactly as in egg.
• Linked views: the graph, e-class table, hashcons, union-find, worklist and writelist highlight the same e-classes on hover and selection.
• Editable presets: edit the initial term and rewrite rules live, save your own presets (stored in localStorage), import/export them as JSON.

Development

npm install
npm run dev        # start the dev server
npm test           # run the test suite
npm run check      # type-check (svelte-check)
npm run build      # static build for GitHub Pages

FC_RUNS=1000 npm test runs more property-based test cases.

Architecture

Path	Purpose
src/lib/engine/runtime.ts	E-graph data structure: union-find, e-classes, hashcons, worklist, merge, repairClass
src/lib/engine/algorithms.ts	E-matching, applying rewrites, the compaction + repair rebuild loop
src/lib/engine/timeline.ts	Runs equality saturation and records structurally shared snapshots (and the work behind each one)
src/lib/engine/work.ts, benchmark.ts	Timing every task, and averaging snapshot-free runs into per-step execution times
src/lib/engine/invariants.ts	Checks the congruence/hashcons invariants (used by tests and debugInvariants)
src/lib/engine/layout.ts	ELK layouts (in a web worker), cached per distinct graph structure
src/lib/graph/frame.ts	Pure frame builder: interpolates two snapshots into positioned shapes and edge paths
src/lib/components/graph_pane/GraphCanvas.svelte	SVG renderer with pan/zoom and a follow camera
src/lib/stores/timelineStore.ts	Loading presets, playback, scrubbing and step animations

See SPECIFICATION.md for the original design notes.

Testing

The suite (Vitest) covers:

• Engine units: union-find, hashcons, merging in both modes, congruence repair and deduplication.
• Property-based tests (fast-check): random terms × random rule sets; invariants hold after every rebuild, saturation really is saturated, naive and deferred reach the same e-graph, runs are deterministic, disabled rules never fire.
• Timeline integrity: phase grammar, snapshot ids, structural sharing, writelist sharing, halting limits, metadata.
• Presets: every built-in preset is well formed and runs with valid invariants; known results (e.g. the paper's (a * 2) / 2 = a).
• Layout & rendering: ELK containment/overlap checks, edge routing, frame interpolation (no NaNs, no dangling edges, merge/dedup animations), viewport math.
• Stores & components: playback, load races, preset editing/revert, preset import validation, and rendering of the state pane, controller, rules panel, rule editor and graph canvas (jsdom + Testing Library).