Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 5590f2e70615e4b6f6a7187dbdaddf5c7b98520f
https://github.com/WebKit/WebKit/commit/5590f2e70615e4b6f6a7187dbdaddf5c7b98520f
Author: Chris Dumez <[email protected]>
Date: 2026-07-29 (Wed, 29 Jul 2026)
Changed paths:
M Source/WTF/wtf/text/AdaptiveStringSearcher.h
Log Message:
-----------
AdaptiveStringSearcher good-suffix shift table is one element too small
https://bugs.webkit.org/show_bug.cgi?id=320520
Reviewed by Darin Adler.
The Boyer-Moore good-suffix shift table (m_goodSuffixShiftTable) was sized
bmMaxShift, but it is indexed by pattern index over the range
[m_start, patternLength], i.e. up to and including patternLength. When a
needle's length is exactly bmMaxShift (250), populateBoyerMooreTable() writes
to index patternLength, which is one past the end of the table.
The out-of-bounds access was masked because the tables were handed around as
raw int* and the good-suffix / suffix tables were accessed through a biased
pointer (table - m_start), so nothing bounds-checked the index against the
physical array.
Fix the size (bmMaxShift + 1) and, to make this class of bug fail loudly
rather than silently write in the wrong place, replace the raw table pointers
with std::span:
- AdaptiveStringSearcherTables now vends fixed-extent std::span accessors
instead of int*, so every access is bounds-checked against a compile-time
constant extent (a hard trap under hardened libc++).
- Introduce BiasedShiftTable, which maps pattern indices in
[m_start, patternLength] onto the shift table while bounds-checking both
ends against the physical table, replacing the previous biased raw pointer.
- charOccurrence() takes a fixed-extent span and reduces the index into
[0, ucharAlphabetSize) via uint8_t / uint16_t casts so the bounds check
folds away.
- Replace the manual memset/loop that initializes the bad-char table with
std::ranges::fill.
This change tested as performance neutral on Speedometer and JetStream.
* Source/WTF/wtf/text/AdaptiveStringSearcher.h:
(WTF::BiasedShiftTable::BiasedShiftTable):
(WTF::BiasedShiftTable::operator[] const):
(WTF::AdaptiveStringSearcher::charOccurrence):
(WTF::AdaptiveStringSearcher::goodSuffixShiftTable):
(WTF::AdaptiveStringSearcher::suffixTable):
(WTF::SubjectChar>::boyerMooreSearch):
(WTF::SubjectChar>::populateBoyerMooreTable):
(WTF::SubjectChar>::boyerMooreHorspoolSearch):
(WTF::SubjectChar>::populateBoyerMooreHorspoolTable):
Canonical link: https://commits.webkit.org/318198@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
