- Revision
- 292943
- Author
- cdu...@apple.com
- Date
- 2022-04-16 15:59:17 -0700 (Sat, 16 Apr 2022)
Log Message
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.
Modified Paths
Diff
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 <cdu...@apple.com>
+ 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 <cdu...@apple.com>
+
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;
