EGSTRA: E-Graph-Based Strategy for Test Suite Reduction and Abstraction
summary
EGSTRA uses e-graphs over JSON ASTs to reduce huge program inputs by applying destructive rewrite rules that delete or replace terms, then standard equivalence rewrites and pattern-based extraction. It implements hash-consing, a modified union-find with the Kaplan chaur and Tarjan deletion approach, and a Python DSL demo on 100 Turtle files (≈110k LOC) that runs in ~3s. Rewrites cut extracted op patterns from ~4,700 to ~143; a prior multi-million-line run drops from 2.5 hours to 20s after the deletion fix.
AI-written summary · about
chapters (11)
- 0:00EGSTRA project intro
- 1:27Test suite creation challenges
- 3:34EGraph-based solution
- 4:38Workflow with EGraph/EGAP
- 6:47Demo with Turtle DSL
- 10:42Traditional equivalence rewrites
- 13:12Union-Find deletion mods
- 14:37Performance improvements & metrics
- 17:22Test case extraction results
- 18:48Future work & language transition
- 21:19Q&A
related talks
19mDestructive E-Graph Rewrites
26mTowards Efficient Model Comparison Using Automated Program Rewriting
23mVersioned E-Graphs
21mVerifying term graph optimizations using Isabelle/HOL
30megg: Fast and Extensible Equality Saturation
20mFast and Optimal Extraction for Sparse Equality Graphs
27mAugmenting Rewrite Rule Sets via Knuth-Bendix Completion
23mE-Stitch: Top-Down Library Learning for E-Graphs