Linear Matching of JavaScript Regular Expressions

on YouTube ↗23m

" summary

Presents a proof that a much larger subset of JavaScript regexes admits linear-time matching, identifies semantic bugs and superlinear cases in V8’s linear engine, and delivers concrete fixes: a two-copy NFA construction to enforce JavaScript’s star semantics, a precomputed lookaround table plus single-replay reconstruction for capture groups, and a prototype engine called regel with several patches merged into V8. Implements and benchmarks the algorithms, showing linear scaling in regex and input size.

AI-written summary · about

" chapters (12)

1. 0:00Regex matching complexity
2. 1:29Linear regex engines rarity
3. 3:14JavaScript regex semantics
4. 4:40Priority rules in regex
5. 6:23Star semantics and loops
6. 8:55Fixing NFA simulation
7. 10:21Lookarounds with capture groups
8. 12:25Precomputing lookaround positions
9. 13:50Capture reset and linear matching
10. 15:17Experimental validation
11. 15:58Lessons from JavaScript regex
12. 17:06Question and answer session

" related talks

• 29mReimplement RegExp in JavaScriptJulian Viereck · JSConf EU 2013
• 25mFormal Verification for JavaScript Regular Expressions: A Proven Mechanized Semantics(…)Clément Pit-Claudel, Aurèle Barrière, Victor Deng · POPL 2026
• 01h 06mEverybody stands back! I know regular expressionsAndrey Listochkin · JavaScript fwdays'20 autumn online
• 24mSolving String Constraints with Regex-Dependent Functions through Transducers wiZhilei Han, Anthony W. Lin, Matthew Hague, Taolue Chen, Zhilin Wu, Alejandro Flores-Lamas, Denghang Hu, Shuanglong Kan, Philipp Römmer · POPL 2022
• 17mWhen Chomsky Met JavaScript: Exploring the Linguistics(...)Alaina Kafkes · JSConf EU 2018
• 01h 13m/ Reg (exp) {2} lained / Demystifying Regular ExpressionsLea verou · HolyJS 2017
• 22mTwo Problems: Regular Expressions for RevolutionariesSarah Saltrick Meyer · JSConf EU 2017
• 26mTotal ReDoS: The Dangers of regex in JavaScriptPhil Nash · XtremeJS 2024