Skip to content

RegexBuilder infinite loop when nullable capture starts with NegativeLookahead #865

Closed

Description

@ekassos

Description

A RegexBuilder pattern can hang when an unbounded quantifier repeats a body that can match the empty string, where that body begins with NegativeLookahead.

In the reducer below, matching "A" repeatedly invokes the capture transform with an empty substring without advancing through the input.

Reproduction

import RegexBuilder

let regex = Regex {
    ZeroOrMore {
        Capture {
            NegativeLookahead { "a" }
            ZeroOrMore(.digit)
        } transform: { String($0) }   // invoked repeatedly with ""
    }
}

_ = "A".matches(of: regex)   // never returns

Reduced string form:

_ = try! Regex(#"(?:(?!a)\d*)*"#).firstMatch(in: "A")   // never returns

Expected Behavior

Matching completes, similar to other nullable quantified forms such as (?:\w|)+ (#558) and (a*)* (#542). Since the repeated body can match the empty string, the engine should stop repeating when the current position does not advance.

Environment

swiftlang/swift:nightly-6.4.x-noble (Swift 6.4-dev) or swiftlang/swift:nightly-main (Swift 6.5-dev). Works as expected on swiftlang/swift:nightly-6.3-noble (Swift 6.3.3-dev) and swift:6.3 (Swift 6.3.2 release).

Notes

This appears to be a regression from the DSL-list flattening work in #845, which was reverted in #847, then re-introduced by #849. The reducer passes at d474af96^ and fails at d474af96. The issue is in the same forward-progress class as #851, which taught the walker to skip a nullable quantification's child subtree. Lookaround groups appear to need the same treatment.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions