Regex fails expected match

[jjvliu]

I created a minimal working example for a problem in the regular expression engine. I was able to reproduce the issue on the latest stable release 1.8.3, on 1.9.0-alpha1, and on master built today. It seems to be a problem with the engine failing to backtrack.

julia> match(r"a+[bc]+c", "ababc")

julia> versioninfo()
Julia Version 1.10.0-DEV.156
Commit 9be3c85e49 (2022-12-19 21:17 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 72 × Intel(R) Xeon(R) Gold 6150 CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake-avx512)
  Threads: 1 on 72 virtual cores

julia> match(r"a+[bc]+c", "ababc")

julia> versioninfo()
Julia Version 1.8.3
Commit 0434deb161 (2022-11-14 20:14 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 72 × Intel(R) Xeon(R) Gold 6150 CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, skylake-avx512)
  Threads: 1 on 72 virtual cores

[Seelengrab]

Your regex is matching at least one a, followed by at least one b or c, followed by a single c. To match ababc, you need to add a grouping specifier:

julia> match(r"(a+[bc])+c", "ababc")
RegexMatch("ababc", 1="ab")

[jakobnissen]

Why does it not match the last three characters though? Regex need not match the full string, but should be able to match a substring. For example:

julia> m = match(r"a+[bc]c", "ababc")
RegexMatch("abc")

Here, the last three letters are being matched. Similarly, OP's regex should match the same last three letters.

[martinholters]

Also:

julia> match(r"a[bc]+c", "ababc")
RegexMatch("abc")

Seems to have regressed in 1.6, btw as with 1.5:

julia> match(r"a+[bc]+c", "ababc")
RegexMatch("abc")

[Seelengrab]

Nice catch, I missed that this was the intention!

[Seelengrab]

Cursory testing suggests this is due to anchoring - see https://regex101.com/r/YoewW3/1 and toggle the Anchoring flag.

[fredrikekre]

Change and/or regression in PCRE2 then, it was updated from 10.36 to 10.40 between 1.7 and 1.8 (v1.7.3...v1.8.3#diff-077a0e0d8ff036a0ed8b93361a2c26cfc8ce3d96049890896e25c20d06e07461R97).

[Seelengrab]

Which is weird, since we don't pass the anchoring flag in that codepath, as far as I can tell 🤔

It does work though if we pass in ENDANCHORED directly:

julia> match(r"a+[bc]+c"a, "ababc", 1, Base.PCRE.ANCHORED)

julia> match(r"a+[bc]+c"a, "ababc", 1, Base.PCRE.ENDANCHORED)
RegexMatch("abc")

[martinholters]

Change and/or regression in PCRE2 then, it was updated from 10.36 to 10.40 between 1.7 and 1.8

Nope, must have been earlier than that:

julia> VERSION
v"1.5.1"

julia> match(r"a+[bc]+c", "ababc")
RegexMatch("abc")

julia> VERSION
v"1.6.7"

julia> match(r"a+[bc]+c", "ababc")

[fredrikekre]

Works in 1.6.6, and indeed that same version bump of PCRE was backported for 1.6.7 (v1.6.6...v1.6.7#diff-077a0e0d8ff036a0ed8b93361a2c26cfc8ce3d96049890896e25c20d06e07461L94).

[Seelengrab]

The only change in PCRE related to anchoring I can find the in the changelog between 10.36 and 10.40 is this, in 10.38:

https://github.com/PCRE2Project/pcre2/blob/0746b3d523c9a799aa62ae9e03188b23664f48b0/ChangeLog#L338-L342

So we could try with 10.37 to see if 10.38 is to blame, and the current most recent version 10.42 and if that also doesn't work, open an issue upstream?