google / google/re2j

Pattern "\uDC21"` matches inside a surrogate pair; equivalent classes don't

Open Beginner friendly
#207 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
1.3k
Forks
165
PR merge metrics
No merged PRs in 30d

Description

A pattern whose literal prefix is a lone low surrogate matches *inside* a well-formed surrogate pair; the equivalent alternation/char-class patterns do not:

Pattern.compile("\uDC21").matcher("a\uD801\uDC21b").find() // true — U+10421's low unit
Pattern.compile("\uDC21|\uDC22").matcher("a\uD801\uDC21b").find() // false
Pattern.compile("[\uD800-\uDFFF]").matcher("a\uD801\uDC21b").find() // false

Whether a match may start between the units of a pair depends on whether the pattern compiles to a single literal prefix.

Repro (SurrogatePairTest):

assertFalse(Pattern.compile("\uDC21").matcher("a\uD801\uDC21b").find());
// search must resume past the skipped interior hit:
Matcher m = Pattern.compile("\uDC21").matcher("\uD801\uDC21\uDC21");
assertTrue(m.find());
assertEquals(2, m.start());

Cause: `MachineInput.StringInput.index()` jumps to raw `String.indexOf` hits. Such a hit can be the low unit of a pair — not a codepoint boundary — and `step()` then decodes the lone low unit as a rune. Paths without the fast path decode pairs and never enter the interior.

Fix: skip `indexOf` hits that are a low surrogate preceded by a high surrogate; keep searching.

Sidenote: RE2 proper operates on UTF-8 runes, where pair-interior positions cannot exist; this is a UTF-16 port artifact.

Disclosure: this was discovered when fuzzing another library (https://github.com/jemmix/tdfa-jvm) against re2j. Patch and fix composed agentically using GLM 5.3.

Contributor guide

Open the contributing guide

Research direction

Start in MachineInput.StringInput.index(), where raw String.indexOf hits are selected, and inspect SurrogatePairTest for the reproductions. Verify that searches do not treat a low surrogate inside a pair as a match start, while still finding a subsequent valid occurrence at index 2; the existing literal, alternation, and character-class cases should remain covered.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
devtools
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
88/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.