Modified: trunk/Source/WebCore/ChangeLog (292942 => 292943)
--- trunk/Source/WebCore/ChangeLog 2022-04-16 20:31:36 UTC (rev 292942)
+++ trunk/Source/WebCore/ChangeLog 2022-04-16 22:59:17 UTC (rev 292943)
@@ -1,5 +1,39 @@
2022-04-16 Chris Dumez <[email protected]>
+ Optimize id matching in AccessibilityObject::ariaElementsReferencedByAttribute()
+ https://bugs.webkit.org/show_bug.cgi?id=239406
+ <rdar://problem/91829358>
+
+ Reviewed by Darin Adler.
+
+ For every element in the DOM tree, the function would get the value of ones of its attributes,
+ then construct a SpaceSplitString (which would tokenize and atomize every space-separated
+ component in the value), and finally see if the SpaceSplitString contains the id we're looking
+ for. This was unnecessarily expensive.
+
+ This patch revives SpaceSplitString::spaceSplitStringContainsValue() which was unused and makes
+ it work with a StringView input instead of only a const char*/LChar*. We now use this function
+ inside AccessibilityObject::ariaElementsReferencedByAttribute() to avoid the construction of
+ a SpaceSplitString. spaceSplitStringContainsValue() simply iterates the string until it finds
+ an HTML space, then compare the chunk of characters with the provided StringView. If it matches,
+ it returns early, otherwise, it keeps searching till the end of the String.
+
+ * accessibility/AccessibilityObject.cpp:
+ (WebCore::AccessibilityObject::ariaElementsReferencedByAttribute const):
+ * dom/SpaceSplitString.cpp:
+ (WebCore::tokenizeSpaceSplitString):
+ (WebCore::TokenIsEqualToCharactersTokenProcessor::TokenIsEqualToCharactersTokenProcessor):
+ (WebCore::TokenIsEqualToCharactersTokenProcessor::processToken):
+ (WebCore::spaceSplitStringContainsValueInternal):
+ (WebCore::SpaceSplitString::spaceSplitStringContainsValue):
+ (WebCore::TokenIsEqualToCStringTokenProcessor::TokenIsEqualToCStringTokenProcessor): Deleted.
+ (WebCore::TokenIsEqualToCStringTokenProcessor::processToken): Deleted.
+ (WebCore::TokenIsEqualToCStringTokenProcessor::referenceStringWasFound const): Deleted.
+ * dom/SpaceSplitString.h:
+ (WebCore::SpaceSplitString::spaceSplitStringContainsValue): Deleted.
+
+2022-04-16 Chris Dumez <[email protected]>
+
Replace complex String::insert() with a simplified makeStringByInserting() free function
https://bugs.webkit.org/show_bug.cgi?id=239370
Modified: trunk/Source/WebCore/accessibility/AccessibilityObject.cpp (292942 => 292943)
--- trunk/Source/WebCore/accessibility/AccessibilityObject.cpp 2022-04-16 20:31:36 UTC (rev 292942)
+++ trunk/Source/WebCore/accessibility/AccessibilityObject.cpp 2022-04-16 22:59:17 UTC (rev 292943)
@@ -3914,6 +3914,8 @@
}
}
+// FIXME: This function iterates the whole DOM tree and tries to match every Element in the tree, which is very expensive.
+// We should find a better way to achieve this.
void AccessibilityObject::ariaElementsReferencedByAttribute(AccessibilityChildrenVector& elements, const QualifiedName& attribute) const
{
auto id = identifierAttribute();
@@ -3920,16 +3922,16 @@
if (id.isEmpty())
return;
- AXObjectCache* cache = axObjectCache();
+ auto* cache = axObjectCache();
if (!cache)
return;
for (auto& element : descendantsOfType<Element>(node()->treeScope().rootNode())) {
- const AtomString& idList = element.attributeWithoutSynchronization(attribute);
- if (!SpaceSplitString(idList, false).contains(id))
+ auto& idList = element.attributeWithoutSynchronization(attribute);
+ if (!SpaceSplitString::spaceSplitStringContainsValue(idList, id))
continue;
- if (AccessibilityObject* axObject = cache->getOrCreate(&element))
+ if (auto* axObject = cache->getOrCreate(&element))
elements.append(axObject);
}
}
Modified: trunk/Source/WebCore/dom/SpaceSplitString.cpp (292942 => 292943)
--- trunk/Source/WebCore/dom/SpaceSplitString.cpp 2022-04-16 20:31:36 UTC (rev 292942)
+++ trunk/Source/WebCore/dom/SpaceSplitString.cpp 2022-04-16 22:59:17 UTC (rev 292943)
@@ -50,15 +50,14 @@
}
template<typename TokenProcessor>
-static inline void tokenizeSpaceSplitString(TokenProcessor& tokenProcessor, const String& string)
+static inline void tokenizeSpaceSplitString(TokenProcessor& tokenProcessor, StringView string)
{
ASSERT(!string.isNull());
- const StringImpl& stringImpl = *string.impl();
- if (stringImpl.is8Bit())
- tokenizeSpaceSplitString(tokenProcessor, stringImpl.characters8(), stringImpl.length());
+ if (string.is8Bit())
+ tokenizeSpaceSplitString(tokenProcessor, string.characters8(), string.length());
else
- tokenizeSpaceSplitString(tokenProcessor, stringImpl.characters16(), stringImpl.length());
+ tokenizeSpaceSplitString(tokenProcessor, string.characters16(), string.length());
}
bool SpaceSplitStringData::containsAll(SpaceSplitStringData& other)
@@ -101,19 +100,19 @@
m_data = SpaceSplitStringData::create(shouldFoldCase ? inputString.convertToASCIILowercase() : inputString);
}
-class TokenIsEqualToCStringTokenProcessor {
+template<typename ReferenceCharacterType>
+class TokenIsEqualToCharactersTokenProcessor {
public:
- explicit TokenIsEqualToCStringTokenProcessor(const char* referenceString, unsigned referenceStringLength)
- : m_referenceString(referenceString)
- , m_referenceStringLength(referenceStringLength)
- , m_referenceStringWasFound(false)
+ explicit TokenIsEqualToCharactersTokenProcessor(const ReferenceCharacterType* referenceCharacters, unsigned length)
+ : m_referenceCharacters(referenceCharacters)
+ , m_referenceLength(length)
{
}
- template <typename CharacterType>
- bool processToken(const CharacterType* characters, unsigned length)
+ template <typename TokenCharacterType>
+ bool processToken(const TokenCharacterType* characters, unsigned length)
{
- if (length == m_referenceStringLength && equal(characters, reinterpret_cast<const LChar*>(m_referenceString), length)) {
+ if (length == m_referenceLength && equal(characters, m_referenceCharacters, length)) {
m_referenceStringWasFound = true;
return false;
}
@@ -123,19 +122,27 @@
bool referenceStringWasFound() const { return m_referenceStringWasFound; }
private:
- const char* m_referenceString;
- unsigned m_referenceStringLength;
- bool m_referenceStringWasFound;
+ const ReferenceCharacterType* m_referenceCharacters;
+ unsigned m_referenceLength;
+ bool m_referenceStringWasFound { false };
};
-bool SpaceSplitString::spaceSplitStringContainsValue(const String& inputString, const char* value, unsigned valueLength, bool shouldFoldCase)
+template <typename ValueCharacterType>
+static bool spaceSplitStringContainsValueInternal(StringView spaceSplitString, StringView value)
{
- if (inputString.isNull())
+ TokenIsEqualToCharactersTokenProcessor<ValueCharacterType> tokenProcessor(value.characters<ValueCharacterType>(), value.length());
+ tokenizeSpaceSplitString(tokenProcessor, spaceSplitString);
+ return tokenProcessor.referenceStringWasFound();
+}
+
+bool SpaceSplitString::spaceSplitStringContainsValue(StringView spaceSplitString, StringView value)
+{
+ if (spaceSplitString.isNull())
return false;
- TokenIsEqualToCStringTokenProcessor tokenProcessor(value, valueLength);
- tokenizeSpaceSplitString(tokenProcessor, shouldFoldCase ? inputString.impl()->convertToASCIILowercase() : inputString);
- return tokenProcessor.referenceStringWasFound();
+ if (value.is8Bit())
+ return spaceSplitStringContainsValueInternal<LChar>(spaceSplitString, value);
+ return spaceSplitStringContainsValueInternal<UChar>(spaceSplitString, value);
}
class TokenCounter {
Modified: trunk/Source/WebCore/dom/SpaceSplitString.h (292942 => 292943)
--- trunk/Source/WebCore/dom/SpaceSplitString.h 2022-04-16 20:31:36 UTC (rev 292942)
+++ trunk/Source/WebCore/dom/SpaceSplitString.h 2022-04-16 22:59:17 UTC (rev 292943)
@@ -117,12 +117,7 @@
return (*m_data)[i];
}
- static bool spaceSplitStringContainsValue(const String& spaceSplitString, const char* value, unsigned length, bool shouldFoldCase);
- template<size_t length>
- static bool spaceSplitStringContainsValue(const String& spaceSplitString, const char (&value)[length], bool shouldFoldCase)
- {
- return spaceSplitStringContainsValue(spaceSplitString, value, length - 1, shouldFoldCase);
- }
+ static bool spaceSplitStringContainsValue(StringView spaceSplitString, StringView value);
private:
RefPtr<SpaceSplitStringData> m_data;
