Regex backtracking experiment / 正则回溯实验 / 正規表現のバックトラッキング実験
2026-10-11

Tested: CPython 3.12.14, macOS 27.0.1 arm64; standard library only.
Python 3.11 or newer is required for (?>...) and possessive quantifiers.

In the extracted folder:
  python3.12 regex-backtracking-lab.py regex-backtracking-output

Patterns: (a+)+, a+, (?>a+)+, a++
Inputs: 16, 18, 20, 22, 24 copies of a, with or without a final !.
Each compiled Pattern.fullmatch call is timed inside a child process.
Three calls are measured; the median and all three readings are saved.
Compilation, string creation and child startup are outside that timer.
Each ordinary case has a five-second subprocess communication timeout.

A separate (a+)+ test with 32 copies of a and a final ! uses a two-second
subprocess communication timeout. That wait covers remaining child
initialization and matching calls, rather than just the regex timer.
Process creation and cleanup can add wall-clock time. On timeout,
subprocess.run kills and waits for the child. The report records no
completed match time and no True/False result. This is an experiment
guard, not a timeout built into the regex pattern itself.

Outputs: results.json and timings.csv. Timing values depend on the
machine and load; exact reproduction of milliseconds is not expected.
The CSV contains only completed cases, not the interrupted case.

Semantic checks cover six sample strings, 1,365 strings of lengths
0 through 5 over {a, b, !, newline}, capture groups for aaa, and the
different results of a+a and a++a on aa. Finite enumeration is not a
general proof that arbitrary regex rewrites preserve their behavior.
The four tested patterns accept the same strings under fullmatch,
but their capture-group interfaces are different.

This script uses only fixed patterns and short synthetic strings.
It does not contact servers, test application endpoints, measure
throughput, or benchmark an alternative regex engine.

Sources:
  https://docs.python.org/3.12/library/re.html
  https://docs.python.org/3.12/howto/regex.html
  https://swtch.com/~rsc/regexp/regexp1.html
  https://github.com/google/re2
  https://docs.python.org/3.12/library/subprocess.html
  https://docs.python.org/3.11/whatsnew/3.11.html#re