Clément Pit-Claudel

Aurèle Barrière, Victor Deng, Clément Pit-Claudel

We present the first mechanized, succinct, practical, complete, and proven-faithful semantics for a modern regular expression language with backtracking semantics. We ensure its faithfulness by proving it equivalent to a preexisting line-by-line embedding of the official ECMAScript specification of JavaScript regular expressions. We demonstrate its practicality by presenting two real-world applications. First, a new notion of contextual equivalence for modern regular expressions, which we use to prove or disprove rewrites drawn from previous work. Second, the first formal proof of the PikeVM algorithm used in many real-world engines. In contrast with the specification and other formalization work, our semantics captures not only the top-priority match, but a full backtracking tree recording all possible matches and their respective priority. All our definitions and results have been mechanized in the Rocq proof assistant.

Victor Deng, Aurèle Barrière, Clément Pit-Claudel

Despite widespread use, the complexity class of modern regular expression matching was not well-understood. Previous work proved that regular expression matching with backreferences and lookarounds was PSPACE-complete, but the proof was not mechanized and applied to an abstract regex language. This paper clarifies the question for JavaScript regular expressions. In this paper, we prove the following new results, with most core proofs mechanized in the Rocq proof assistant. We prove that JavaScript regex matching is indeed PSPACE-hard, even without negative lookarounds, and OptP-hard as well; that JavaScript regex matching without lower-bounded quantifiers (i.e. quantifiers with a non-zero minimum number of repetitions) is PSPACE-complete; and that JavaScript regex matching without lower-bounded quantifiers and without lookarounds is OptP-complete.

Shardul Chiplunkar, Clément Pit-Claudel

Programmers often use an iterative process of hypothesis generation ("perhaps this function is called twice?") and hypothesis testing ("let's count how many times this breakpoint fires") to understand the behavior of unfamiliar or malfunctioning software. Existing debugging tools are much better suited to testing hypotheses than to generating them. Step debuggers, for example, present isolated snapshots of the program's state, leaving it to the programmer to mentally reconstruct the evolution of that state over time. We advocate for a different approach: building a debugging and program-exploration tool around a *trace*, or complete history, of the program's execution. Our key claim is that the user should see every line *as executed* (in time order) rather than *as written* (in syntax order). We discuss design choices, preliminary results, and interesting challenges.