| Ticket UUID: | a6029ee50552e4e89fd57a4a18c83379b64da46c | ||
| Title: | regexp hangs with backreferences when a possible empty match fails | ||
| Type: | Bug | Created on: | 2026-10-10 18:47:21 |
| Submitter: | serhiy.storchaka | Assigned to: | |
| Subsystem: | 43. Regexp | Severity: | Important |
| Priority: | 5 Medium | Last modified: | 2026-10-17 07:16:33 |
| Status: | Open | Closed by: | |
| Resolution: | None | Closed on: | |
| Version: | 8.6.18, 9.0.5, 9.1.0 | ||
| Description: | ||||
|
These never return:
regexp {(b*)a\1|\1} ba ;# should return 1 (matches "a")
regexp {$()|^\1} a ;# should return 0
regexp {.. ()|\1} a ;# should return 0
regexp {()*\1} a ;# should return 1
The first one was found by comparing random patterns with backreferences against PostgreSQL; the other three are from the PostgreSQL regression tests.
complicatedFindLoop() asks the search DFA for the earliest possible match end close, tries every start point up to it, and when all of them fail, searches again from the same close. The DFA treats a backreference as matching anything, so it reports a possible empty match there again, and the loop never advances. This is only possible with backreferences. It started with the fix for [6585b21ca8] in 8.6.1; ()*\1 hangs since 8.6.5. PostgreSQL fixed this in 2015, after the same change, in commit f2c4ffc330: advance close after a failed range (close++), and in citerdissect() try a real iteration before accepting zero iterations of an empty match, so that ()*\1 matches instead of failing. This fix was not included in the regexp bundle [497b93405b]. With both changes ported, all four examples give the PostgreSQL results, and the regexp tests pass. | ||||
| User Comments: | ||||
serhiy.storchaka added on 2026-10-10 19:29:32:
Proposed fix in branch regexp-backref-search-loop: the port of PostgreSQL commit f2c4ffc330. Tests reg-14.32 to 14.36 (the four examples and ()+\1). serhiy.storchaka added on 2026-10-17 07:16:33:
Merged into main in [ac36095ed4], not yet into 9.0 and 8.6. Besides the hang, it also changes which groups are set when an iteration matches an empty string: the engine now prefers one empty iteration to zero (as PostgreSQL does), so [regexp -indices -inline {((a?)*|(b?)*)+} aaa] gives {0 2} {3 2} {3 2} {-1 -1} on main, as in 8.4 to 8.6.4, and {0 2} {3 2} {-1 -1} {-1 -1} in 8.6.5 to 9.0 (since [c8dfe06653]). | ||||