apache / apache/datafusion-comet

Add grammar-based differential fuzzing for CometRegex

Open
#5,811 0 comments 0 reactions 0 assignees View on GitHub
enhancement requires-triage
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.