- Revision
- 165822
- Author
- [email protected]
- Date
- 2014-03-18 11:11:46 -0700 (Tue, 18 Mar 2014)
Log Message
Micro-optimize element descendant iterator.
<https://webkit.org/b/130384>
Add a slightly more efficient ElementDescendantIterator that keeps a stack
of relevant ancestor siblings instead of walking up the parent chain every
time we run out of children.
Reviewed by Antti Koivisto.
* WebCore.xcodeproj/project.pbxproj:
* dom/ElementDescendantIterator.h: Added.
(WebCore::ElementDescendantIterator::ElementDescendantIterator):
(WebCore::ElementDescendantIterator::operator++):
(WebCore::ElementDescendantConstIterator::ElementDescendantConstIterator):
(WebCore::ElementDescendantConstIterator::operator++):
(WebCore::ElementDescendantIteratorAdapter::ElementDescendantIteratorAdapter):
(WebCore::ElementDescendantIteratorAdapter::begin):
(WebCore::ElementDescendantIteratorAdapter::end):
(WebCore::ElementDescendantConstIteratorAdapter::ElementDescendantConstIteratorAdapter):
(WebCore::ElementDescendantConstIteratorAdapter::begin):
(WebCore::ElementDescendantConstIteratorAdapter::end):
(WebCore::elementDescendants):
* dom/ElementIterator.h:
* dom/SelectorQuery.cpp:
(WebCore::elementsForLocalName):
(WebCore::anyElement):
(WebCore::SelectorDataList::executeSingleTagNameSelectorData):
(WebCore::SelectorDataList::executeSingleClassNameSelectorData):
(WebCore::SelectorDataList::executeSingleSelectorData):
(WebCore::SelectorDataList::executeSingleMultiSelectorData):
(WebCore::SelectorDataList::executeCompiledSimpleSelectorChecker):
Modified Paths
Added Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (165821 => 165822)
--- trunk/Source/WebCore/ChangeLog 2014-03-18 18:06:52 UTC (rev 165821)
+++ trunk/Source/WebCore/ChangeLog 2014-03-18 18:11:46 UTC (rev 165822)
@@ -1,3 +1,37 @@
+2014-03-18 Andreas Kling <[email protected]>
+
+ Micro-optimize element descendant iterator.
+ <https://webkit.org/b/130384>
+
+ Add a slightly more efficient ElementDescendantIterator that keeps a stack
+ of relevant ancestor siblings instead of walking up the parent chain every
+ time we run out of children.
+
+ Reviewed by Antti Koivisto.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * dom/ElementDescendantIterator.h: Added.
+ (WebCore::ElementDescendantIterator::ElementDescendantIterator):
+ (WebCore::ElementDescendantIterator::operator++):
+ (WebCore::ElementDescendantConstIterator::ElementDescendantConstIterator):
+ (WebCore::ElementDescendantConstIterator::operator++):
+ (WebCore::ElementDescendantIteratorAdapter::ElementDescendantIteratorAdapter):
+ (WebCore::ElementDescendantIteratorAdapter::begin):
+ (WebCore::ElementDescendantIteratorAdapter::end):
+ (WebCore::ElementDescendantConstIteratorAdapter::ElementDescendantConstIteratorAdapter):
+ (WebCore::ElementDescendantConstIteratorAdapter::begin):
+ (WebCore::ElementDescendantConstIteratorAdapter::end):
+ (WebCore::elementDescendants):
+ * dom/ElementIterator.h:
+ * dom/SelectorQuery.cpp:
+ (WebCore::elementsForLocalName):
+ (WebCore::anyElement):
+ (WebCore::SelectorDataList::executeSingleTagNameSelectorData):
+ (WebCore::SelectorDataList::executeSingleClassNameSelectorData):
+ (WebCore::SelectorDataList::executeSingleSelectorData):
+ (WebCore::SelectorDataList::executeSingleMultiSelectorData):
+ (WebCore::SelectorDataList::executeCompiledSimpleSelectorChecker):
+
2014-03-18 Antti Koivisto <[email protected]>
Mutating rules returned by getMatchedCSSRules can result in crash
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (165821 => 165822)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2014-03-18 18:06:52 UTC (rev 165821)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2014-03-18 18:11:46 UTC (rev 165822)
@@ -11293,6 +11293,7 @@
AD726FEC16D9F4B9003A4E6D /* JSStyleSheetCustom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSStyleSheetCustom.h; sourceTree = "<group>"; };
ADDF1AD41257CD9A0003A759 /* RenderSVGPath.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderSVGPath.cpp; sourceTree = "<group>"; };
ADDF1AD51257CD9A0003A759 /* RenderSVGPath.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderSVGPath.h; sourceTree = "<group>"; };
+ ADE11F4A18D8311B0078983B /* ElementDescendantIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ElementDescendantIterator.h; sourceTree = "<group>"; };
ADE16736181050C300463A2E /* RenderPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderPtr.h; sourceTree = "<group>"; };
B10B697D140C174000BC1C26 /* WebVTTToken.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebVTTToken.h; sourceTree = "<group>"; };
B10B697E140C174000BC1C26 /* WebVTTTokenizer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WebVTTTokenizer.cpp; sourceTree = "<group>"; };
@@ -22123,6 +22124,7 @@
B5B7A16F17C1080600E4AA0A /* ElementData.cpp */,
B5B7A16E17C1048000E4AA0A /* ElementData.h */,
E46A2B1B17CA65B9000DBCD8 /* TypedElementDescendantIterator.h */,
+ ADE11F4A18D8311B0078983B /* ElementDescendantIterator.h */,
E4AE7C1517D1BB950009FB31 /* ElementIterator.h */,
E401C27417CE53EC00C41A35 /* ElementIteratorAssertions.h */,
4FAB48641643A66D00F70C07 /* ElementRareData.cpp */,
Added: trunk/Source/WebCore/dom/ElementDescendantIterator.h (0 => 165822)
--- trunk/Source/WebCore/dom/ElementDescendantIterator.h (rev 0)
+++ trunk/Source/WebCore/dom/ElementDescendantIterator.h 2014-03-18 18:11:46 UTC (rev 165822)
@@ -0,0 +1,289 @@
+/*
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef ElementDescendantIterator_h
+#define ElementDescendantIterator_h
+
+#include "Element.h"
+#include "ElementIteratorAssertions.h"
+#include "ElementTraversal.h"
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+class ElementDescendantIterator {
+public:
+ ElementDescendantIterator();
+ explicit ElementDescendantIterator(Element* current);
+
+ ElementDescendantIterator& operator++();
+
+ Element& operator*();
+ Element* operator->();
+
+ bool operator==(const ElementDescendantIterator& other) const;
+ bool operator!=(const ElementDescendantIterator& other) const;
+
+private:
+ Element* m_current;
+ Vector<Element*, 16, UnsafeVectorOverflow> m_ancestorSiblingStack;
+
+#if !ASSERT_DISABLED
+ ElementIteratorAssertions m_assertions;
+#endif
+};
+
+class ElementDescendantConstIterator {
+public:
+ ElementDescendantConstIterator();
+ explicit ElementDescendantConstIterator(const Element*);
+
+ ElementDescendantConstIterator& operator++();
+
+ const Element& operator*() const;
+ const Element* operator->() const;
+
+ bool operator==(const ElementDescendantConstIterator& other) const;
+ bool operator!=(const ElementDescendantConstIterator& other) const;
+
+private:
+ const Element* m_current;
+ Vector<Element*, 16, UnsafeVectorOverflow> m_ancestorSiblingStack;
+
+#if !ASSERT_DISABLED
+ ElementIteratorAssertions m_assertions;
+#endif
+};
+
+class ElementDescendantIteratorAdapter {
+public:
+ ElementDescendantIteratorAdapter(ContainerNode& root);
+ ElementDescendantIterator begin();
+ ElementDescendantIterator end();
+
+private:
+ ContainerNode& m_root;
+};
+
+class ElementDescendantConstIteratorAdapter {
+public:
+ ElementDescendantConstIteratorAdapter(const ContainerNode& root);
+ ElementDescendantConstIterator begin() const;
+ ElementDescendantConstIterator end() const;
+
+private:
+ const ContainerNode& m_root;
+};
+
+ElementDescendantIteratorAdapter elementDescendants(ContainerNode&);
+ElementDescendantConstIteratorAdapter elementDescendants(const ContainerNode&);
+
+// ElementDescendantIterator
+
+inline ElementDescendantIterator::ElementDescendantIterator()
+ : m_current(nullptr)
+{
+}
+
+inline ElementDescendantIterator::ElementDescendantIterator(Element* current)
+ : m_current(current)
+{
+ m_ancestorSiblingStack.uncheckedAppend(nullptr);
+}
+
+ALWAYS_INLINE ElementDescendantIterator& ElementDescendantIterator::operator++()
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+
+ Element* firstChild = ElementTraversal::firstChild(m_current);
+ Element* nextSibling = ElementTraversal::nextSibling(m_current);
+
+ if (firstChild) {
+ if (nextSibling)
+ m_ancestorSiblingStack.append(nextSibling);
+ m_current = firstChild;
+ return *this;
+ }
+
+ if (nextSibling) {
+ m_current = nextSibling;
+ return *this;
+ }
+
+ m_current = m_ancestorSiblingStack.takeLast();
+
+#if !ASSERT_DISABLED
+ // Drop the assertion when the iterator reaches the end.
+ if (!m_current)
+ m_assertions.dropEventDispatchAssertion();
+#endif
+
+ return *this;
+}
+
+inline Element& ElementDescendantIterator::operator*()
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+ return *m_current;
+}
+
+inline Element* ElementDescendantIterator::operator->()
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+ return m_current;
+}
+
+inline bool ElementDescendantIterator::operator==(const ElementDescendantIterator& other) const
+{
+ ASSERT(!m_assertions.domTreeHasMutated());
+ return m_current == other.m_current;
+}
+
+inline bool ElementDescendantIterator::operator!=(const ElementDescendantIterator& other) const
+{
+ return !(*this == other);
+}
+
+// ElementDescendantConstIterator
+
+inline ElementDescendantConstIterator::ElementDescendantConstIterator()
+ : m_current(nullptr)
+{
+}
+
+inline ElementDescendantConstIterator::ElementDescendantConstIterator(const Element* current)
+ : m_current(current)
+{
+ m_ancestorSiblingStack.uncheckedAppend(nullptr);
+}
+
+ALWAYS_INLINE ElementDescendantConstIterator& ElementDescendantConstIterator::operator++()
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+
+ Element* firstChild = ElementTraversal::firstChild(m_current);
+ Element* nextSibling = ElementTraversal::nextSibling(m_current);
+
+ if (firstChild) {
+ if (nextSibling)
+ m_ancestorSiblingStack.append(nextSibling);
+ m_current = firstChild;
+ return *this;
+ }
+
+ if (nextSibling) {
+ m_current = nextSibling;
+ return *this;
+ }
+
+ m_current = m_ancestorSiblingStack.takeLast();
+
+#if !ASSERT_DISABLED
+ // Drop the assertion when the iterator reaches the end.
+ if (!m_current)
+ m_assertions.dropEventDispatchAssertion();
+#endif
+
+ return *this;
+}
+
+inline const Element& ElementDescendantConstIterator::operator*() const
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+ return *m_current;
+}
+
+inline const Element* ElementDescendantConstIterator::operator->() const
+{
+ ASSERT(m_current);
+ ASSERT(!m_assertions.domTreeHasMutated());
+ return m_current;
+}
+
+inline bool ElementDescendantConstIterator::operator==(const ElementDescendantConstIterator& other) const
+{
+ ASSERT(!m_assertions.domTreeHasMutated());
+ return m_current == other.m_current;
+}
+
+inline bool ElementDescendantConstIterator::operator!=(const ElementDescendantConstIterator& other) const
+{
+ return !(*this == other);
+}
+
+// ElementDescendantIteratorAdapter
+
+inline ElementDescendantIteratorAdapter::ElementDescendantIteratorAdapter(ContainerNode& root)
+ : m_root(root)
+{
+}
+
+inline ElementDescendantIterator ElementDescendantIteratorAdapter::begin()
+{
+ return ElementDescendantIterator(ElementTraversal::firstChild(&m_root));
+}
+
+inline ElementDescendantIterator ElementDescendantIteratorAdapter::end()
+{
+ return ElementDescendantIterator();
+}
+
+// ElementDescendantConstIteratorAdapter
+
+inline ElementDescendantConstIteratorAdapter::ElementDescendantConstIteratorAdapter(const ContainerNode& root)
+ : m_root(root)
+{
+}
+
+inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::begin() const
+{
+ return ElementDescendantConstIterator(ElementTraversal::firstChild(&m_root));
+}
+
+inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::end() const
+{
+ return ElementDescendantConstIterator();
+}
+
+// Standalone functions
+
+inline ElementDescendantIteratorAdapter elementDescendants(ContainerNode& root)
+{
+ return ElementDescendantIteratorAdapter(root);
+}
+
+inline ElementDescendantConstIteratorAdapter elementDescendants(const ContainerNode& root)
+{
+ return ElementDescendantConstIteratorAdapter(root);
+}
+
+}
+
+#endif
Modified: trunk/Source/WebCore/dom/SelectorQuery.cpp (165821 => 165822)
--- trunk/Source/WebCore/dom/SelectorQuery.cpp 2014-03-18 18:06:52 UTC (rev 165821)
+++ trunk/Source/WebCore/dom/SelectorQuery.cpp 2014-03-18 18:11:46 UTC (rev 165822)
@@ -27,7 +27,7 @@
#include "SelectorQuery.h"
#include "CSSParser.h"
-#include "ElementIterator.h"
+#include "ElementDescendantIterator.h"
#include "SelectorChecker.h"
#include "SelectorCheckerFastPath.h"
#include "StaticNodeList.h"
@@ -264,7 +264,7 @@
template <typename SelectorQueryTrait>
static inline void elementsForLocalName(const ContainerNode& rootNode, const AtomicString& localName, typename SelectorQueryTrait::OutputType& output)
{
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (element.tagQName().localName() == localName) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
@@ -276,7 +276,7 @@
template <typename SelectorQueryTrait>
static inline void anyElement(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output)
{
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
@@ -304,7 +304,7 @@
}
} else {
// Fallback: NamespaceURI is set, selectorLocalName may be starAtom.
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (element.namespaceURI() == selectorNamespaceURI && (selectorLocalName == starAtom || element.tagQName().localName() == selectorLocalName)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
@@ -321,7 +321,7 @@
ASSERT(isSingleClassNameSelector(*selectorData.selector));
const AtomicString& className = selectorData.selector->value();
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (element.hasClass() && element.classNames().contains(className)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
@@ -335,7 +335,7 @@
{
ASSERT(m_selectors.size() == 1);
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (selectorMatches(selectorData, element, rootNode)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
@@ -348,7 +348,7 @@
ALWAYS_INLINE void SelectorDataList::executeSingleMultiSelectorData(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
unsigned selectorCount = m_selectors.size();
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
for (unsigned i = 0; i < selectorCount; ++i) {
if (selectorMatches(m_selectors[i], element, rootNode)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
@@ -364,7 +364,7 @@
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeCompiledSimpleSelectorChecker(const ContainerNode& rootNode, SelectorCompiler::SimpleSelectorChecker selectorChecker, typename SelectorQueryTrait::OutputType& output) const
{
- for (auto& element : descendantsOfType<Element>(const_cast<ContainerNode&>(rootNode))) {
+ for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (selectorChecker(&element)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
