apache / apache/lucene

Parsing a regex with groups that may match empty strings seems to be incorrect sometimes

Open
#15,182 3 comments 0 reactions 0 assignees View on GitHub
type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

Consider a regex of the form `a(b|)c`. This should match `ac` and `abc`. Some regexes of this form seem to behave incorrectly. To try to make a slightly more concrete or realistic example, one might want to search some logs for something like `[a-z-]*(|-prod|-main) `.

I cobbled together some tests against a recent version of the lucene repo. I have three docs which respectively contain:
- `foo-bar-baz`
- `foo--baz`
- `foo-test-baz`

And then I spell a regex to match only the first two docs a bunch of different ways:

1. `.*foo-(bar|)-baz.*` - IllegalArgumentException: expected ')' at position 18
2. `.*foo-(|bar)-baz.*` - 0 matches but 2 expected
3. `.*(foo-(bar|)-baz).*` - IllegalArgumentException: expected ')' at position 20
4. `.*(foo-(|bar)-baz).*` - 0 matches but 2 expected
5. `.*foo-(bar|())-baz.*` - 2 matches
6. `.*foo-(bar|()?)-baz.*` - 2 matches
7. `.*foo-(bar|#?)-baz.*` - 2 matches
8. `.*(foo-(bar|())-baz).*` - 2 matches
9. `.*(foo-(bar|()?)-baz).*` - 2 matches
10. `.*(foo-(bar|#?)-baz).*` - 2 matches
11. `.*foo-(bar)?-baz.*` - 2 matches

The first four cases seem incorrect to me.

I came to this investigation after some problems with elasticsearch (v8.12.2, using lucene 9.9.2) where regexes following pattern number 5 also failed. Maybe that is some useful context.

### Version and environment details

I added tests by modifying `lucene/core/src/test/org/apache/lucene/search/TestRegexpQuery.java` with a base revision of `cd1a4ecc9ead8e06b08f3bc2016297525f65b37c`.

Here are other details in case they are relevant:
OS: linux (el8 with a 6.12.39 kernel)
Java: openjdk version "24.0.1" 2025-04-15
This is on an x86_64 box.

Contributor guide

Open the contributing guide

Research direction

Start with lucene/core/src/test/org/apache/lucene/search/TestRegexpQuery.java and reproduce the first four patterns against the three documents. Trace the regexp parsing entry point used by those tests, then verify that the empty-alternative forms produce the expected matches while the existing successful cases continue to pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.