[webkit-changes] [WebKit/WebKit] 802150: [WTF] Adopt adaptive string searching

[Yusuke Suzuki]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 802150baed8ddc888da813f8a5c076de17e152a3
      https://github.com/WebKit/WebKit/commit/802150baed8ddc888da813f8a5c076de17e152a3
  Author: Yusuke Suzuki <ysuzuki at apple.com>
  Date:   2024-02-02 (Fri, 02 Feb 2024)

  Changed paths:
    A JSTests/stress/string-index-of-pathological.js
    A JSTests/stress/v8-string-indexof-1.js
    A JSTests/stress/v8-string-indexof-2.js
    M Source/JavaScriptCore/dfg/DFGOperations.cpp
    M Source/JavaScriptCore/runtime/StringPrototype.cpp
    M Source/JavaScriptCore/runtime/StringPrototypeInlines.h
    M Source/JavaScriptCore/runtime/VM.cpp
    M Source/JavaScriptCore/runtime/VM.h
    M Source/WTF/WTF.xcodeproj/project.pbxproj
    M Source/WTF/wtf/CMakeLists.txt
    M Source/WTF/wtf/text/ASCIIFastPath.h
    A Source/WTF/wtf/text/AdaptiveStringSearcher.h
    M Source/WTF/wtf/text/StringView.cpp
    M Source/WTF/wtf/text/StringView.h

  Log Message:
  -----------
  [WTF] Adopt adaptive string searching
https://bugs.webkit.org/show_bug.cgi?id=268635
rdar://121082299

Reviewed by Mark Lam.

This patch adopts V8's StringSearch class. We tailor it to our use and name it AdaptiveStringSearcher.
We add `StringView::find(AdaptiveStringSearcherTables&, ...)` function which uses `AdaptiveStringSearcher`,
when the table is attached. In this way, we can use this function even without JSC VM for example.

The mechanism of this class is that, it requires additional space for large table (AdaptiveStringSearcherTables).
And it *adaptively* switches string searching algorithm: linearSearch -> boyerMooreHorspoolSearch -> boyerMooreSearch.
The reason is that the latter requires more costly preprocess to populate table data. For very simple case, linearSearch suffice,
but for more complex cases, the preprocess gets paid, and boyerMooreHorspoolSearch / boyerMooreSearch works better for performance.

* Source/JavaScriptCore/dfg/DFGOperations.cpp:
(JSC::DFG::JSC_DEFINE_JIT_OPERATION):
* Source/JavaScriptCore/runtime/StringPrototype.cpp:
(JSC::stringIndexOfImpl):
(JSC::JSC_DEFINE_HOST_FUNCTION):
(JSC::stringIncludesImpl):
* Source/JavaScriptCore/runtime/StringPrototypeInlines.h:
(JSC::stringReplaceStringString):
(JSC::replaceUsingStringSearch):
* Source/JavaScriptCore/runtime/VM.cpp:
(JSC::VM::VM):
* Source/JavaScriptCore/runtime/VM.h:
(JSC::VM::adaptiveStringSearcherTables):
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/text/ASCIIFastPath.h:
(WTF::charactersAreAllLatin1):
* Source/WTF/wtf/text/AdaptiveStringSearcher.h: Added.
(WTF::AdaptiveStringSearcherBase::exceedsOneByte):
(WTF::AdaptiveStringSearcherBase::alignDown):
(WTF::AdaptiveStringSearcherBase::getHighestValueByte):
(WTF::AdaptiveStringSearcherBase::findFirstCharacter):
(WTF::AdaptiveStringSearcherTables::badCharShiftTable):
(WTF::AdaptiveStringSearcherTables::goodSuffixShiftTable):
(WTF::AdaptiveStringSearcherTables::suffixTable):
(WTF::AdaptiveStringSearcher::AdaptiveStringSearcher):
(WTF::AdaptiveStringSearcher::search):
(WTF::AdaptiveStringSearcher::alphabetSize):
(WTF::AdaptiveStringSearcher::failSearch):
(WTF::AdaptiveStringSearcher::charOccurrence):
(WTF::AdaptiveStringSearcher::badCharTable):
(WTF::AdaptiveStringSearcher::goodSuffixShiftTable):
(WTF::AdaptiveStringSearcher::suffixTable):
(WTF::SubjectChar>::singleCharSearch):
(WTF::SubjectChar>::linearSearch):
(WTF::SubjectChar>::boyerMooreSearch):
(WTF::SubjectChar>::populateBoyerMooreTable):
(WTF::SubjectChar>::boyerMooreHorspoolSearch):
(WTF::SubjectChar>::populateBoyerMooreHorspoolTable):
(WTF::SubjectChar>::initialSearch):
(WTF::searchString):
(WTF::searchStringRaw):
* Source/WTF/wtf/text/StringView.cpp:
(WTF::StringView::find const):
* Source/WTF/wtf/text/StringView.h:

Canonical link: https://commits.webkit.org/274033@main