str: take search bounds through the character index - #8530

Follows #8522 and #8526, which gave PyStr a code-point index (Wtf8Index) and used it to drive re and to resolve subscripts and slices. The same index answers the remaining quadratic in the string type: the search methods.

What was happening

find, rfind, index, rindex, count, startswith and endswith all take character bounds. They resolved them through AnyStr::get_chars, which walks the payload to both bounds, and find then reported its hit with _to_char_idx, which counts the code points in front of it -- the // FIXME: two traversals of str is expensive that sat above it.

So a sweep over a subject's own indices walked the subject once per call. AnyStr sees only the payload, which does not say whether it is ASCII, so the ASCII path walked too.

What this does

Resolve the bounds with StrData::char_range_to_bytes, the converter #8526 added for slices -- so the search methods inherit its short-walk case too, and s.startswith(x, 1, -1) does not build a table over the whole string. Map the hit back with Wtf8Index::char_index_at_byte, added here as the table's inverse. The table is keyed by character index, so the inverse is a search rather than a lookup, but a narrow one: a character is one to four bytes, which brackets the answer to a band around the byte offset before the first comparison, and the walk that follows is at most an entry's worth of steps. It is also amortised -- the callers that need it have already built the table resolving their own bounds.

AnyStr::get_chars keeps its byte-string callers, where a character range is already a byte range; the FIXME is replaced by a note saying so.

Measurements

n=8000, sweeping the bound over the subject, best of 3, the two binaries interleaved:

The per-doubling factor is the clearer statement: find and startswith go from ×4 (quadratic) to ×2 (linear). count stays ×3 because counting is linear in the range it is handed -- CPython is the same shape there; what drops is the constant.

The first commit is an independent fix

str.count with an empty needle answered in encoded positions rather than characters, because find_iter over the range's bytes reports one hit per byte boundary:

>>> '가나다'.count('')
10          # CPython: 4
>>> '가나다'.count('', 1, 2)
4           # CPython: 2

This is on main today, independent of the rest of the PR; it is fixed first, in the shape main has, so it can be read on its own. bytes.count keeps the byte-position answer, which is correct there. The snippet assertions added with it fail on main and pass after.

Verification

• A differential of find/rfind/index/rindex/count/startswith/endswith against CPython over 356048 shapes -- 16 subjects (empty, ASCII, 2/3/4-byte, lone surrogates, embedded NUL, and lengths on and around the 64-character group boundary) x 11 needles (absent, ASCII, non-ASCII, multi-character, a lone surrogate) x 17 x 17 bounds (None, in range, past the end, negative, far negative). main differs from CPython on 1375 of them, all of them the empty-needle count; this branch differs on 0.
• The re differential from _sre: drive a non-ASCII str subject through a character index on the string #8522 (2731 lines) and the subscript/slice differential from str: resolve subscripts and slices through the code point index #8526 (44331 shapes): 0 diffs.
• test_str, test_bytes, test_re, test_string, test_userstring: SUCCESS. (test_unicode fails identically on main -- it does not reach its tests on either.)
• cargo clippy --all-targets, cargo fmt --check, cargo test -p rustpython-common clean.

Summary by CodeRabbit

• Bug Fixes

  • Improved Unicode handling for string searches, indexing, counting, and prefix/suffix checks.
  • Corrected character-position results when operations use byte ranges or supplementary-plane characters.
  • Fixed empty-string counting across ASCII, Unicode, and bounded ranges.

• Performance

  • Optimized string operations by reducing unnecessary character-by-character traversal while preserving character-based results.
  • Improved handling of character positions in Unicode text, including lookups at the end of strings.

What a single call pays

The table costs a pass over the buffer, so the fair question is what happens to a string that is searched once and never again. Measured on a fresh subject per call, so nothing is amortised, n=1,000,000:

A bounded search is a wash: building the table costs about what the walk it replaces cost. An unbounded search is 13x, and that is the common form -- s.find(x) is 0..len, which char_range_to_bytes answers by walking zero steps at each end, so the call becomes a plain byte search with no conversion at all. On main it walked the whole string through get_chars before searching it.