moonbitlang / core / 6127

91%

push

github

fix(regex): stop applying a sequence's continuation twice (#4075)

When more than one alternation branch accepts the same character, the
alternation leaves more than one thread behind — two that have finished
it where the branches are single characters, one finished and one still
going where they differ in length. `ThreadSet::remove_duplicates`
rewrote a finished thread — one sitting at `Eps` — into
`Exp(marks, next)`, carrying the continuation. Its caller then wrapped
the deduplicated set in `ts_seq(pref, .., next)`, which appends the same
continuation again. The text after the alternation therefore had to
appear twice for the match to succeed.

    Regex("(?:a|a)c").execute("ac")     // no match
    Regex("(?:a|a)c").execute("acc")    // matched "acc"
    Regex("(?:a|a)bc").execute("abcbc") // matched "abcbc"

It is only visible when the alternation leaves more than one thread
alive, which is why disjoint branches were unaffected. Beyond missed
matches it also produced spans outside the language and let a counted
repetition run past its maximum:

    Regex("(?:.a|a)(?:b|)").execute("abb")  // matched "abb"; ends 1 and 2
                                            // are the only ones in the language
    Regex("(?:.|ab){2,4}").execute("aaaaa") // matched five characters

Both `Regex::compile` and the combinator API were affected; the `re""`
literal mostly escaped because that path folds an alternation of
character classes into a single class before the engine sees it. Wrapping
the same alternation in a capturing group also hid it, because the
zero-width mark expressions a capture inserts change the continuation
structure — not, as it first appeared, because slots distinguish the
threads: dedup ignores marks and slots entirely. Closes #4072.

The rewrite is not merely redundant, though: keying the finished thread
by `next.id` is what lets it collapse with a thread already sitting at
`next`, and without that collapse a sequence whose first part can bot... (continued)

1 of 1 new or added line in 1 file covered. (100.0%)

16061 of 17704 relevant lines covered (90.72%)

323857.78 hits per line