Lookaheads produce incorrect results (toRegExp returns empty-matching regex)

[futpib]

Description

Lookahead assertions ((?=...) and (?!...)) are not working correctly. They produce incorrect results in both the internal parser and the public API.

Public API Impact

.toRegExp() produces wrong output

node -e "import('@gruhn/regex-utils').then(m => console.log('/(?=a)/ ->', m.RB(/(?=a)/).toRegExp()))"
# Output: /(?=a)/ -> /^$.^$/

node -e "import('@gruhn/regex-utils').then(m => console.log('/a{2}/ ->', m.RB(/a{2}/).toRegExp()))"
# Output: /a{2}/ -> /^.*aa.*$/

The lookahead /(?=a)/ becomes /^$.^$/ (matches nothing), while /a{2}/ correctly becomes /^.*aa.*$/.

isStdRegex flag is false for lookaheads

node -e "import('@gruhn/regex-utils').then(m => console.log(m.RB(/a{2}/).regex.isStdRegex))"
# Output: true

node -e "import('@gruhn/regex-utils').then(m => console.log(m.RB(/(?=a)/).regex.isStdRegex))"
# Output: false

Internal Parser Issue

The internal parseRegExpString function has a specific issue with quantified lookaheads - it parses the quantifier as literal characters instead of applying it to the lookahead:

# Quantifier on normal atom - correctly produces "repeat" type
node -e "import('./node_modules/@gruhn/regex-utils/dist/regex-parser.js').then(m => console.log(m.parseRegExpString('a{2}').type))"
# Output: repeat

# Quantifier on lookahead - lookahead captures {2} as literals in 'right' field
node -e "import('./node_modules/@gruhn/regex-utils/dist/regex-parser.js').then(m => console.log(JSON.stringify(m.parseRegExpString('(?=a){2}'))))"
# The {2} appears as literal characters in the 'right' field instead of wrapping the lookahead in a 'repeat' node

Expected Behavior

JavaScript allows quantified lookaheads:

node -e "console.log(/(?=a){2}/.test('a'))"
# Output: true

node -e "console.log(new RegExp('(?=a){2}').source)"
# Output: (?=a){2}

Lookaheads should:

1. Produce correct toRegExp() output (not /^$.^$/)
2. Have isStdRegex: true
3. Parse quantifiers as quantifiers, not literals

[gruhn]

Thanks for reporting. Yes, unfortunately there are a ton of issues with lookaheads.

The internal parse error you identified is a good catch. I didn't know about that. But it's not the core issue with lookaheads.

That the isStdRegex flag is false should be expected. I don't know how much you care about the details.

Some Background:

Internally, we just rewrite lookaheads as intersections. For example, say

^(?=.{10,20})<email-regex>$

is a regex that matches email addresses with 10-20 characters. The same can be written with regex intersections. Something like:

RB(/^.{10,20}$/).and(<email-regex>)

However, it turns out, rewriting lookaheads as intersections is not so simple. I'm convinced it's technically possible but it's hard to determine what sub-regex the lookahead "acts on".

I still don't have an approach how to deal with this.

If you don't use lookaheads, I'm pretty confident that the library is working correctly though. That is, it either returns a result that is correct or throws an error that this situation is not supported.

Right now, I recommend using RB(...).and(...) and RB(...).not() instead of positive/negative lookaheads, where possible. Can you elaborate more on your use case?

[futpib]

My use case was really just to use your regexp parser (which, I suppose, was never intended, since it isn’t exported). I came across the parser bug and tried to figure out whether it affects your public API, mainly so this finding wouldn’t go to waste.

[gruhn]

Makes sense 👌 The parser bug shouldn't be too hard to fix. I'll look into it.

[gruhn]

Looks like even regex101.com is getting this wrong. When I select the ECMAScript regex flavor and enter (?=a){2}, regex101 claims that:

{2} The preceding token is not quantifiable  

But it must be valid because new RegExp('(?=a){2}') is not throwing an error.

Anyway, I have fix ready (see #14). With that, lookaheads should parse correctly. The parser also accepts lookbehind assertions now. An UnsupportedSynaxError is thrown in later stages though. I adjusted the AST representation. Lookaheads/lookbehinds don't parse like operators anymore. For example:

(?=a)b

previously parsed to:

{ 
  type: "lookahead", 
  isPositive: true, 
  inner: "a",                          // (not really just a string)
  right: "b" 
}

Now it parses to:

{ 
  type: "concat", 
  left: { 
    type: "lookahead", 
    isPositive: true, 
    inner: "a"
    // no more "right" field
  },
  right: "b"
}

[futpib]

That the isStdRegex flag is false should be expected. I don't know how much you care about the details.

I was trying to understand what this project actually does beyond the parser and I don't get why do you do dfaToRegex at all instead of printing intersections as lookaheads and complements as negative lookaheads. I'm not saying it's easy or something, it's pretty intense here actually, I just don't see why not. What am I missing?

[gruhn]

You're right that's probably much simpler to convert back to a valid regex. But the original motivation for this library was this fast-check issue: dubzzz/fast-check#5562

Fast-check can generate random strings from a regex but it doesn't support lookaheads. So you don't have a way to combine regex (like an email regex that also has a length constraint). This library makes it possible, because the roundtrip throughdfaToRegex eliminates lookaheads, intersections, complement.