apache / apache/datafusion-comet
Add grammar-based differential fuzzing for CometRegex
- Dominant language
- Scala
- Stars
- 1.3k
- Forks
- 373
- Avg merge
- 2d 4h
- Merged PRs (30d)
- 198
Description
### What is the problem the feature request solves?
PR #5415 introduces `CometRegex`, a conservative plan-time analyzer that allows a restricted subset of literal Java regex patterns to use native Rust `rlike` execution by default.
The current parity suite uses a fixed corpus. This covers patterns we anticipated, but it may not detect an unexpected combination of otherwise admitted constructs. The safety property is that every pattern admitted by `CometRegex` must have the same matching behavior in Java's `java.util.regex` engine and Comet's native Rust regex kernel.
### Describe the potential solution
Add a deterministic grammar-based generator that produces both admitted and rejected regex patterns, including combinations of:
- printable ASCII literals;
- character classes, ranges, negation, and escaped metacharacters;
- concatenation and alternation;
- capturing and non-capturing groups;
- greedy and counted quantifiers;
- constructs that `CometRegex` is expected to reject.
For every generated pattern admitted by `CometRegex`, compare Java `Pattern.matcher(subject).find()` with the actual native Rust `rlike` result.
Generated subjects should include ASCII and non-ASCII strings, empty strings, newlines, control characters, exotic whitespace, supplementary Unicode code points, and NULL where applicable.
The generator should use a reproducible seed and report the seed, pattern, subject, and both results on failure. If the test is too expensive for every pull request, it could run in a nightly workflow.
### Additional context
Follow-up from #5415 and #5351.
This tracks the grammar-based fuzzing requested during review of #5415: https://github.com/apache/datafusion-comet/pull/5415#pullrequestreview-5154502402
Andy also performed an offline fuzzing campaign during the review, but that process is not currently part of the repository or CI: https://github.com/apache/datafusion-comet/pull/5415#issuecomment-5443268056
Contributor guide
Research direction
Start with CometRegex, the existing fixed-corpus parity suite, and the review discussion in PR #5415. Define a reproducible grammar and subject generator, then compare Java Pattern.matcher(subject).find() with native Rust rlike for admitted patterns. Done means failures report the seed, pattern, subject, and both results, with the test integrated into pull-request or nightly CI.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java, rust, scala
- Domain
- backend, testing-qa
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100