_sre: drive an all-ASCII str subject over its bytes - #8520
Merged
Conversation
StrDrive carried no documentation, so nothing recorded that a cursor's position is a character index rather than a byte offset. Every implementation satisfies it -- skip(n) advances position by exactly n in all three -- and the engine depends on it: _count bounds a repeat with position + max_count and reports the repeat length as a difference of positions, ASSERT compares position against a lookbehind width, and search_info recovers a match start as position - (len - 1). A drive over a variable-width encoding that stored byte offsets would leave those type-correct and wrong, and would index a lookbehind out of bounds. Write the invariant down on StringCursor and on each trait method. Also walk the group's own cursor in GROUPREF instead of counting to the group's width, so the loop bound is the thing being stepped. Generated machine code is unchanged. Assisted-by: Claude
with_sre_str handed every str subject to the &Wtf8 drive, which answers
count() by counting every code point and create_cursor(n) by stepping over the
first n. Both run once per Request, so a scan that restarts at successive
positions walked the subject again on every call: finditer over an ASCII
subject of n tokens was quadratic in n.
PyStr already records whether it is ASCII -- StrKind is decided when the
string is built -- and for ASCII a character index is a byte index, so the
&[u8] drive's cursor arithmetic already applies: count() is the byte length
and create_cursor() is a pointer offset. Add AsciiStr, which delegates every
StrDrive method to that impl and differs only in slice(), which reslices the
span and returns str rather than bytes.
Matching is unaffected: StrDrive carries no unicode semantics, because the
engine keys every unicode decision on the compiled pattern's opcode rather
than on the subject type.
Also bind the subject once in with_sre_str, so callers passing a temporary
(`&x.clone()`) build it once rather than per arm.
finditer over an ASCII subject, n tokens, this machine:
n before after
5000 41.60ms 1.37ms
10000 217.30ms 2.68ms
20000 1206.28ms 5.17ms
40000 5016.65ms 10.31ms
Per-doubling x5.22/x5.55/x4.16 becomes x1.95/x1.93/x1.99. Collecting
m.group(0) for every match goes 5061.02ms -> 17.80ms at n=40000.
test.test_re is unchanged at 166 tests, OK (skipped=14, expected failures=6),
and a 2731-line differential over the is_ascii() boundary -- findall,
finditer spans and groups, sub, split, match, search, fullmatch across
subjects that are empty, ASCII, non-ASCII, or mixed -- is byte-identical to
CPython 3.14.6. Introducing an off-by-one in AsciiStr::slice moves 1224 of
those lines, so the comparison reaches the new code.
Assisted-by: Claude
Contributor
|
No actionable comments were generated in the recent review. 🎉 ℹ️ Recent review info⚙️ Run configurationConfiguration used: Path: .coderabbit.yml Review profile: CHILL Plan: Pro Plus Run ID: 📒 Files selected for processing (3)
📝 WalkthroughWalkthroughThe SRE engine now treats cursor positions as character indexes. Group matching uses cursor positions as bounds. The VM adds ASCII string adaptation and dispatches byte, ASCII string, and general Unicode string subjects separately. ChangesASCII string matching
Estimated code review effort: 3 (Moderate) | ~20 minutes Merge Risk: 🟡 Moderate · up to The PR changes Rust matching behavior, but required formatting and lint checks have not yet been confirmed. Merge should wait for cargo fmt and cargo clippy to pass, or for an explicit owner acceptance. Sequence Diagram(s)sequenceDiagram
participant Pattern
participant with_sre_str
participant AsciiStr
participant SRECallback
Pattern->>with_sre_str: Bind the subject
with_sre_str->>Pattern: Check subject and pattern representation
Pattern->>AsciiStr: Validate ASCII str and expose bytes
AsciiStr->>SRECallback: Provide cursor operations and str slices
Suggested reviewers: 🚥 Pre-merge checks | ✅ 4 | ❌ 1❌ Failed checks (1 warning)
✅ Passed checks (4 passed)
✨ Finishing Touches🧪 Generate unit tests (beta)
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
re.finditerover an all-ASCIIstrwas quadratic in the subject's length.Why it was quadratic
StrDrivepositions are character indices, so the&Wtf8drive answerscount()by countingcode points from the start of the subject, and
create_cursor(n)by walking ton. Both areO(n). A scan that restarts at successive positions pays that setup once per step, so the subject
is walked again for every match.
For an ASCII subject a character index is a byte index, so
&[u8]'s cursor arithmetic isalready the right arithmetic:
countis the byte length andcreate_cursoris a pointer offset.AsciiStris a newtype that takes&[u8]'sStrDriveand overrides onlyslice, to hand backstrinstead ofbytes.with_sre_str!selects it onStrKind::is_ascii(), whichPyStrdecided when the string was built, so the choice is a field load and not a scan.
Matching is unaffected by the choice:
StrDrivecarries no unicode semantics of its own, becausethe engine keys every unicode decision on the compiled pattern's opcode rather than on the
subject type.
Measurements
re.compile(r"\d+")over("item%04d " % 7) * n, best of 3, same machine and base commit forboth columns (
xis the factor over the previous row, so 4 is quadratic and 2 is linear):m.group(0)beforem.group(0)afterThe two arms this does not touch, as controls in the same runs:
strfinditer (&Wtf8drive)bytesfinditer (&[u8]drive)Non-ASCII
stris unchanged and still quadratic. Removing that needs a character-index tobyte-offset mapping stored on
PyStr, which is a separate change.Correctness
test_re: run=166, skipped=14, SUCCESS.(
findall,finditerspans/groups,sub,split,match,search,fullmatch) — produces2731 lines of output that are identical on CPython 3.14.6 and on this branch. The subjects
include the empty string, pure ASCII, mixed strings where only the first/middle/last character
is non-ASCII, Korean, emoji, a lone surrogate, and an embedded NUL, so both drives are
exercised and the split between them is covered from either side.
The first commit
sre_engine: document that StrDrive positions are character indiceswrites down the unitStringCursor::positionis in and which engine sites depend on it:_countbounds a repeat withposition + max_count,ASSERTcompares a position against a lookbehind width, andsearch_inforecovers a match start asposition - (len - 1). A drive that stored byte offsetsthere would leave all of them type-correct and silently wrong;
AsciiStris only sound becauseASCII makes the two units coincide.
It also rewrites the
GROUPREFcomparison loop aswhile g_ctx.cursor.position < group_endinstead of
for _ in group_start..group_end, sinceg_ctxis already stepping over exactly thecharacters being compared. Both spellings iterate the same number of times, and the normalized
machine code for the crate's consumers is byte-identical across the change (1,217,188 lines
compared), so it is a readability change only.
🤖 Generated with Claude Code
Summary by CodeRabbit
Bug Fixes
Documentation