moonbitlang / core / 6972

89%

Build Type

push

github

Committed by web-flow

Commit Message

feat(regex): run string.Regex on the compiler's tagged DFA construction (#4371)

Replace the engine behind `@string.Regex` with a priority-ordered tagged NFA
determinised lazily into a tagged DFA, the construction the compiler uses for
`lexmatch` and `=~`, so that a regex gives the same result compiled or at
run time.

- Repetitions whose body can match the empty string now give the result
  compile-time `lexmatch` gives; nothing else changes.
- DFA states are cached under a budget (16M words) instead of without
  limit. States store only the tags each thread has set; states that differ
  only in register names share one cached copy when the cache is full, and
  the transitions that move registers are kept.
- Remove `internal/regex_engine/automata` and the match preference nodes of
  the internal AST, which the new engine does not use.
- Add the compile-time `lexmatch` results for 520 patterns as a table the
  runtime engine must reproduce, a Pike VM oracle, and cache tests.

Coverage Stats

316 of 319 new or added lines in 5 files covered. (99.06%)

1 existing line in 1 file now uncovered.

16741 of 18701 relevant lines covered (89.52%)

377485.1 hits per line