Implement ComposedTreeIterator in terms of ElementAndTextDescendantIterator
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Feb 2016 01:15:52 +0000 (01:15 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 9 Feb 2016 01:15:52 +0000 (01:15 +0000)
https://bugs.webkit.org/show_bug.cgi?id=154003

Reviewed by Darin Adler.

Currently ComposedTreeIterator implements tree traversal using NodeTraversal. This makes it overly complicated.
It can also return nodes other than Element and Text which should not be part of the composed tree.

This patch adds a new iterator type, ElementAndTextDescendantIterator, similar to the existing ElementDescendantIterator.
ComposedTreeIterator is then implemented using this new iterator.

When entering a shadow tree or a slot the local iterator is pushed along with the context stack and a new local
iterator is initialized for the new context. When leaving a shadow tree the context stack is popped and the previous
local iterator becomes active.

* WebCore.xcodeproj/project.pbxproj:
* dom/ComposedTreeIterator.cpp:
(WebCore::ComposedTreeIterator::ComposedTreeIterator):
(WebCore::ComposedTreeIterator::initializeContextStack):
(WebCore::ComposedTreeIterator::pushContext):
(WebCore::ComposedTreeIterator::traverseNextInShadowTree):
(WebCore::ComposedTreeIterator::traverseNextLeavingContext):
(WebCore::ComposedTreeIterator::advanceInSlot):
(WebCore::ComposedTreeIterator::traverseSiblingInSlot):
(WebCore::ComposedTreeIterator::initializeShadowStack): Deleted.
(WebCore::ComposedTreeIterator::traverseParentInShadowTree): Deleted.
(WebCore::ComposedTreeIterator::traverseNextSiblingSlot): Deleted.
(WebCore::ComposedTreeIterator::traversePreviousSiblingSlot): Deleted.
* dom/ComposedTreeIterator.h:
(WebCore::ComposedTreeIterator::operator*):
(WebCore::ComposedTreeIterator::operator->):
(WebCore::ComposedTreeIterator::operator==):
(WebCore::ComposedTreeIterator::operator!=):
(WebCore::ComposedTreeIterator::operator++):
(WebCore::ComposedTreeIterator::Context::Context):
(WebCore::ComposedTreeIterator::context):
(WebCore::ComposedTreeIterator::current):
(WebCore::ComposedTreeIterator::ComposedTreeIterator):
(WebCore::ComposedTreeIterator::traverseNext):
(WebCore::ComposedTreeIterator::traverseNextSkippingChildren):
(WebCore::ComposedTreeIterator::traverseNextSibling):
(WebCore::ComposedTreeIterator::traversePreviousSibling):
(WebCore::ComposedTreeDescendantAdapter::ComposedTreeDescendantAdapter):
(WebCore::ComposedTreeDescendantAdapter::begin):
(WebCore::ComposedTreeDescendantAdapter::end):
(WebCore::ComposedTreeDescendantAdapter::at):
(WebCore::ComposedTreeChildAdapter::Iterator::Iterator):
(WebCore::ComposedTreeChildAdapter::ComposedTreeChildAdapter):
(WebCore::ComposedTreeChildAdapter::begin):
(WebCore::ComposedTreeChildAdapter::end):
(WebCore::ComposedTreeChildAdapter::at):
(WebCore::ComposedTreeIterator::ShadowContext::ShadowContext): Deleted.
(WebCore::ComposedTreeIterator::traverseParent): Deleted.
* dom/ElementAndTextDescendantIterator.h: Added.

    New iterator type that traverses Element and Text nodes (that is renderable nodes only).
    It also tracks depth for future use.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@196281 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/dom/ComposedTreeIterator.cpp
Source/WebCore/dom/ComposedTreeIterator.h
Source/WebCore/dom/ElementAndTextDescendantIterator.h [new file with mode: 0644]
Source/WebCore/dom/ElementIteratorAssertions.h

index 6652ad2..4318a4f 100644 (file)
@@ -1,3 +1,63 @@
+2016-02-08  Antti Koivisto  <antti@apple.com>
+
+        Implement ComposedTreeIterator in terms of ElementAndTextDescendantIterator
+        https://bugs.webkit.org/show_bug.cgi?id=154003
+
+        Reviewed by Darin Adler.
+
+        Currently ComposedTreeIterator implements tree traversal using NodeTraversal. This makes it overly complicated.
+        It can also return nodes other than Element and Text which should not be part of the composed tree.
+
+        This patch adds a new iterator type, ElementAndTextDescendantIterator, similar to the existing ElementDescendantIterator.
+        ComposedTreeIterator is then implemented using this new iterator.
+
+        When entering a shadow tree or a slot the local iterator is pushed along with the context stack and a new local
+        iterator is initialized for the new context. When leaving a shadow tree the context stack is popped and the previous
+        local iterator becomes active.
+
+        * WebCore.xcodeproj/project.pbxproj:
+        * dom/ComposedTreeIterator.cpp:
+        (WebCore::ComposedTreeIterator::ComposedTreeIterator):
+        (WebCore::ComposedTreeIterator::initializeContextStack):
+        (WebCore::ComposedTreeIterator::pushContext):
+        (WebCore::ComposedTreeIterator::traverseNextInShadowTree):
+        (WebCore::ComposedTreeIterator::traverseNextLeavingContext):
+        (WebCore::ComposedTreeIterator::advanceInSlot):
+        (WebCore::ComposedTreeIterator::traverseSiblingInSlot):
+        (WebCore::ComposedTreeIterator::initializeShadowStack): Deleted.
+        (WebCore::ComposedTreeIterator::traverseParentInShadowTree): Deleted.
+        (WebCore::ComposedTreeIterator::traverseNextSiblingSlot): Deleted.
+        (WebCore::ComposedTreeIterator::traversePreviousSiblingSlot): Deleted.
+        * dom/ComposedTreeIterator.h:
+        (WebCore::ComposedTreeIterator::operator*):
+        (WebCore::ComposedTreeIterator::operator->):
+        (WebCore::ComposedTreeIterator::operator==):
+        (WebCore::ComposedTreeIterator::operator!=):
+        (WebCore::ComposedTreeIterator::operator++):
+        (WebCore::ComposedTreeIterator::Context::Context):
+        (WebCore::ComposedTreeIterator::context):
+        (WebCore::ComposedTreeIterator::current):
+        (WebCore::ComposedTreeIterator::ComposedTreeIterator):
+        (WebCore::ComposedTreeIterator::traverseNext):
+        (WebCore::ComposedTreeIterator::traverseNextSkippingChildren):
+        (WebCore::ComposedTreeIterator::traverseNextSibling):
+        (WebCore::ComposedTreeIterator::traversePreviousSibling):
+        (WebCore::ComposedTreeDescendantAdapter::ComposedTreeDescendantAdapter):
+        (WebCore::ComposedTreeDescendantAdapter::begin):
+        (WebCore::ComposedTreeDescendantAdapter::end):
+        (WebCore::ComposedTreeDescendantAdapter::at):
+        (WebCore::ComposedTreeChildAdapter::Iterator::Iterator):
+        (WebCore::ComposedTreeChildAdapter::ComposedTreeChildAdapter):
+        (WebCore::ComposedTreeChildAdapter::begin):
+        (WebCore::ComposedTreeChildAdapter::end):
+        (WebCore::ComposedTreeChildAdapter::at):
+        (WebCore::ComposedTreeIterator::ShadowContext::ShadowContext): Deleted.
+        (WebCore::ComposedTreeIterator::traverseParent): Deleted.
+        * dom/ElementAndTextDescendantIterator.h: Added.
+
+            New iterator type that traverses Element and Text nodes (that is renderable nodes only).
+            It also tracks depth for future use.
+
 2016-02-08  Joseph Pecoraro  <pecoraro@apple.com>
 
         Web Inspector: copy({x:1}) should copy "{x:1}", not "[object Object]"
index 0139789..ac96205 100644 (file)
                E43A023D17EB3713004CDD25 /* RenderElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E43A023C17EB3713004CDD25 /* RenderElement.cpp */; };
                E43AF8E61AC5B7E800CA717E /* CacheValidation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E43AF8E41AC5B7DD00CA717E /* CacheValidation.cpp */; };
                E43AF8E71AC5B7EC00CA717E /* CacheValidation.h in Headers */ = {isa = PBXBuildFile; fileRef = E43AF8E51AC5B7DD00CA717E /* CacheValidation.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               E440AA961C68420800A265CC /* ElementAndTextDescendantIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = E440AA951C68420800A265CC /* ElementAndTextDescendantIterator.h */; };
                E44613A10CD6331000FADA75 /* HTMLAudioElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E446138F0CD6331000FADA75 /* HTMLAudioElement.cpp */; };
                E44613A20CD6331000FADA75 /* HTMLAudioElement.h in Headers */ = {isa = PBXBuildFile; fileRef = E44613900CD6331000FADA75 /* HTMLAudioElement.h */; };
                E44613A40CD6331000FADA75 /* HTMLMediaElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E44613920CD6331000FADA75 /* HTMLMediaElement.cpp */; };
                E43A023C17EB3713004CDD25 /* RenderElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderElement.cpp; sourceTree = "<group>"; };
                E43AF8E41AC5B7DD00CA717E /* CacheValidation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CacheValidation.cpp; sourceTree = "<group>"; };
                E43AF8E51AC5B7DD00CA717E /* CacheValidation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CacheValidation.h; sourceTree = "<group>"; };
+               E440AA951C68420800A265CC /* ElementAndTextDescendantIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ElementAndTextDescendantIterator.h; sourceTree = "<group>"; };
                E446138F0CD6331000FADA75 /* HTMLAudioElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLAudioElement.cpp; sourceTree = "<group>"; };
                E44613900CD6331000FADA75 /* HTMLAudioElement.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HTMLAudioElement.h; sourceTree = "<group>"; };
                E44613910CD6331000FADA75 /* HTMLAudioElement.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = HTMLAudioElement.idl; sourceTree = "<group>"; };
                                A8C4A7F509D563270003AC8D /* Element.h */,
                                93EEC1EA09C2877700C515D1 /* Element.idl */,
                                E4AE7C1917D232350009FB31 /* ElementAncestorIterator.h */,
+                               E440AA951C68420800A265CC /* ElementAndTextDescendantIterator.h */,
                                E46A2B1D17CA76B1000DBCD8 /* ElementChildIterator.h */,
                                B5B7A16F17C1080600E4AA0A /* ElementData.cpp */,
                                B5B7A16E17C1048000E4AA0A /* ElementData.h */,
                                93309E0E099E64920056E581 /* FrameSelection.h in Headers */,
                                C4CD629B18383766007EBAF1 /* FrameSnapshotting.h in Headers */,
                                65A21485097A3F5300B9050A /* FrameTree.h in Headers */,
+                               E440AA961C68420800A265CC /* ElementAndTextDescendantIterator.h in Headers */,
                                65CBFEFA0974F607001DAC25 /* FrameView.h in Headers */,
                                97205AB0123928CA00B17380 /* FTPDirectoryDocument.h in Headers */,
                                51C81B8A0C4422F70019ECE3 /* FTPDirectoryParser.h in Headers */,
index 4143750..6201427 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 namespace WebCore {
 
-void ComposedTreeIterator::initializeShadowStack()
+ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root)
+{
+    ASSERT(!is<ShadowRoot>(root));
+
+#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
+    if (is<HTMLSlotElement>(root)) {
+        auto& slot = downcast<HTMLSlotElement>(root);
+        if (auto* assignedNodes = slot.assignedNodes()) {
+            initializeContextStack(root, *assignedNodes->at(0));
+            return;
+        }
+    }
+#endif
+    auto& effectiveRoot = root.shadowRoot() ? *root.shadowRoot() : root;
+    m_contextStack.uncheckedAppend(Context(effectiveRoot));
+}
+
+ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current)
+{
+    ASSERT(!is<ShadowRoot>(root));
+    ASSERT(!is<ShadowRoot>(current));
+
+    bool mayNeedShadowStack = root.shadowRoot() || (&current != &root && current.parentNode() != &root);
+    if (mayNeedShadowStack)
+        initializeContextStack(root, current);
+    else
+        m_contextStack.uncheckedAppend(Context(root, current));
+}
+
+void ComposedTreeIterator::initializeContextStack(ContainerNode& root, Node& current)
 {
     // This code sets up the iterator for arbitrary node/root pair. It is not needed in common cases
     // or completes fast because node and root are close (like in composedTreeChildren(*parent).at(node) case).
-    auto* node = m_current;
-    while (node != &m_root) {
+    auto* node = &current;
+    auto* contextCurrent = node;
+    size_t currentSlotNodeIndex = notFound;
+    while (node != &root) {
         auto* parent = node->parentNode();
         if (!parent) {
-            m_current = nullptr;
+            *this = { };
             return;
         }
         if (is<ShadowRoot>(*parent)) {
             auto& shadowRoot = downcast<ShadowRoot>(*parent);
-            if (m_shadowStack.isEmpty() || m_shadowStack.last().host != shadowRoot.host())
-                m_shadowStack.append(shadowRoot.host());
+            m_contextStack.append(Context(shadowRoot, *contextCurrent, currentSlotNodeIndex));
             node = shadowRoot.host();
+            contextCurrent = node;
+            currentSlotNodeIndex = notFound;
             continue;
         }
         if (auto* shadowRoot = parent->shadowRoot()) {
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-            m_shadowStack.append(shadowRoot->host());
+            m_contextStack.append(Context(*parent, *contextCurrent, currentSlotNodeIndex));
             auto* assignedSlot = shadowRoot->findAssignedSlot(*node);
             if (assignedSlot) {
-                size_t index = assignedSlot->assignedNodes()->find(node);
-                ASSERT(index != notFound);
-
-                m_shadowStack.last().currentSlot = assignedSlot;
-                m_shadowStack.last().currentSlotNodeIndex = index;
+                currentSlotNodeIndex = assignedSlot->assignedNodes()->find(node);
+                ASSERT(currentSlotNodeIndex != notFound);
                 node = assignedSlot;
+                contextCurrent = assignedSlot;
                 continue;
             }
             // The node is not part of the composed tree.
 #else
             UNUSED_PARAM(shadowRoot);
-            m_current = nullptr;
-            return;
 #endif
+            *this = { };
+            return;
         }
         node = parent;
     }
-    m_shadowStack.reverse();
+    m_contextStack.append(Context(root, *contextCurrent, currentSlotNodeIndex));
+
+    m_contextStack.reverse();
 }
 
-void ComposedTreeIterator::traverseNextInShadowTree()
+bool ComposedTreeIterator::pushContext(ShadowRoot& shadowRoot)
 {
-    ASSERT(!m_shadowStack.isEmpty());
+    Context shadowContext(shadowRoot);
+    if (!shadowContext.iterator)
+        return false;
+    m_contextStack.append(WTFMove(shadowContext));
+    return true;
+}
 
-    auto* shadowContext = &m_shadowStack.last();
+void ComposedTreeIterator::traverseNextInShadowTree()
+{
+    ASSERT(m_contextStack.size() > 1);
 
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-    if (is<HTMLSlotElement>(*m_current) && !shadowContext->currentSlot) {
-        auto& slot = downcast<HTMLSlotElement>(*m_current);
+    if (is<HTMLSlotElement>(current())) {
+        auto& slot = downcast<HTMLSlotElement>(current());
         if (auto* assignedNodes = slot.assignedNodes()) {
-            shadowContext->currentSlot = &slot;
-            shadowContext->currentSlotNodeIndex = 0;
-            m_current = assignedNodes->at(0);
+            context().slotNodeIndex = 0;
+            auto* assignedNode = assignedNodes->at(0);
+            m_contextStack.append(Context(*assignedNode->parentElement(), *assignedNode));
             return;
         }
     }
 #endif
 
-    m_current = NodeTraversal::next(*m_current, shadowContext->host);
+    context().iterator.traverseNext();
 
-    while (!m_current) {
-#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-        if (auto* slot = shadowContext->currentSlot) {
-            bool nextNodeInSameSlot = ++shadowContext->currentSlotNodeIndex < slot->assignedNodes()->size();
-            if (nextNodeInSameSlot) {
-                m_current = slot->assignedNodes()->at(shadowContext->currentSlotNodeIndex);
-                return;
-            }
-            m_current = NodeTraversal::nextSkippingChildren(*slot, shadowContext->host);
-            shadowContext->currentSlot = nullptr;
-            continue;
-        }
-#endif
-        auto& previousHost = *shadowContext->host;
-        m_shadowStack.removeLast();
-
-        if (m_shadowStack.isEmpty()) {
-            m_current = NodeTraversal::nextSkippingChildren(previousHost, &m_root);
-            return;
-        }
-        shadowContext = &m_shadowStack.last();
-        m_current = NodeTraversal::nextSkippingChildren(previousHost, shadowContext->host);
-    }
+    if (!context().iterator)
+        traverseNextLeavingContext();
 }
 
-void ComposedTreeIterator::traverseParentInShadowTree()
+void ComposedTreeIterator::traverseNextLeavingContext()
 {
-    ASSERT(!m_shadowStack.isEmpty());
-
-    auto& shadowContext = m_shadowStack.last();
-
-    auto* parent = m_current->parentNode();
-    if (is<ShadowRoot>(parent)) {
-        ASSERT(shadowContext.host == downcast<ShadowRoot>(*parent).host());
+    ASSERT(m_contextStack.size() > 1);
 
-        m_current = shadowContext.host;
-        m_shadowStack.removeLast();
-        return;
-    }
-    if (parent->shadowRoot()) {
+    while (!context().iterator && m_contextStack.size() > 1) {
+        m_contextStack.removeLast();
+        if (!context().iterator)
+            return;
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-        ASSERT(shadowContext.host == parent);
-
-        auto* slot = shadowContext.currentSlot;
-        ASSERT(slot->assignedNodes()->at(shadowContext.currentSlotNodeIndex) == m_current);
-
-        m_current = slot;
-        shadowContext.currentSlot = nullptr;
-        return;
-#else
-        m_current = nullptr;
-        return;
+        if (is<HTMLSlotElement>(current()) && advanceInSlot(1))
+            return;
 #endif
+        context().iterator.traverseNextSkippingChildren();
     }
-    m_current = parent;
 }
 
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-void ComposedTreeIterator::traverseNextSiblingSlot()
+bool ComposedTreeIterator::advanceInSlot(int direction)
 {
-    ASSERT(m_current->parentNode()->shadowRoot());
-    ASSERT(!m_shadowStack.isEmpty());
-    ASSERT(m_shadowStack.last().host == m_current->parentNode());
-
-    auto& shadowContext = m_shadowStack.last();
+    ASSERT(context().slotNodeIndex != notFound);
 
-    if (!shadowContext.currentSlot) {
-        m_current = nullptr;
-        return;
-    }
-    auto* slotNodes = shadowContext.currentSlot->assignedNodes();
-    ASSERT(slotNodes->at(shadowContext.currentSlotNodeIndex) == m_current);
+    auto& assignedNodes = *downcast<HTMLSlotElement>(current()).assignedNodes();
+    // It is fine to underflow this.
+    context().slotNodeIndex += direction;
+    if (context().slotNodeIndex >= assignedNodes.size())
+        return false;
 
-    bool nextNodeInSameSlot = ++shadowContext.currentSlotNodeIndex < slotNodes->size();
-    m_current = nextNodeInSameSlot ? slotNodes->at(shadowContext.currentSlotNodeIndex) : nullptr;
+    auto* slotNode = assignedNodes.at(context().slotNodeIndex);
+    m_contextStack.append(Context(*slotNode->parentElement(), *slotNode));
+    return true;
 }
 
-void ComposedTreeIterator::traversePreviousSiblingSlot()
+void ComposedTreeIterator::traverseSiblingInSlot(int direction)
 {
-    ASSERT(m_current->parentNode()->shadowRoot());
-    ASSERT(!m_shadowStack.isEmpty());
-    ASSERT(m_shadowStack.last().host == m_current->parentNode());
+    ASSERT(m_contextStack.size() > 1);
+    ASSERT(current().parentNode()->shadowRoot());
 
-    auto& shadowContext = m_shadowStack.last();
-
-    if (!shadowContext.currentSlot) {
-        m_current = nullptr;
-        return;
-    }
-    auto* slotNodes = shadowContext.currentSlot->assignedNodes();
-    ASSERT(slotNodes->at(shadowContext.currentSlotNodeIndex) == m_current);
+    m_contextStack.removeLast();
 
-    bool previousNodeInSameSlot = shadowContext.currentSlotNodeIndex > 0;
-    m_current = previousNodeInSameSlot ? slotNodes->at(--shadowContext.currentSlotNodeIndex) : nullptr;
+    if (!advanceInSlot(direction))
+        *this = { };
 }
 #endif
 
index ae86557..bb029bd 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -23,7 +23,7 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#include "NodeTraversal.h"
+#include "ElementAndTextDescendantIterator.h"
 #include "ShadowRoot.h"
 
 #ifndef ComposedTreeIterator_h
@@ -35,115 +35,118 @@ class HTMLSlotElement;
 
 class ComposedTreeIterator {
 public:
+    ComposedTreeIterator();
     ComposedTreeIterator(ContainerNode& root);
     ComposedTreeIterator(ContainerNode& root, Node& current);
 
-    Node& operator*() { return *m_current; }
-    Node* operator->() { return m_current; }
+    Node& operator*() { return current(); }
+    Node* operator->() { return &current(); }
 
-    bool operator==(const ComposedTreeIterator& other) const { return m_current == other.m_current; }
-    bool operator!=(const ComposedTreeIterator& other) const { return m_current != other.m_current; }
+    bool operator==(const ComposedTreeIterator& other) const { return context().iterator == other.context().iterator; }
+    bool operator!=(const ComposedTreeIterator& other) const { return context().iterator != other.context().iterator; }
 
-    ComposedTreeIterator& operator++() { return traverseNextSibling(); }
+    ComposedTreeIterator& operator++() { return traverseNext(); }
 
     ComposedTreeIterator& traverseNext();
+    ComposedTreeIterator& traverseNextSkippingChildren();
     ComposedTreeIterator& traverseNextSibling();
     ComposedTreeIterator& traversePreviousSibling();
-    ComposedTreeIterator& traverseParent();
+
+    unsigned depth() const;
 
 private:
-    void initializeShadowStack();
+    void initializeContextStack(ContainerNode& root, Node& current);
     void traverseNextInShadowTree();
-    void traverseParentInShadowTree();
+    void traverseNextLeavingContext();
+    bool pushContext(ShadowRoot&);
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-    void traverseNextSiblingSlot();
-    void traversePreviousSiblingSlot();
+    bool advanceInSlot(int direction);
+    void traverseSiblingInSlot(int direction);
 #endif
 
-    ContainerNode& m_root;
-    Node* m_current { 0 };
-
-    struct ShadowContext {
-        ShadowContext(Element* host)
-            : host(host)
+    struct Context {
+        Context() { }
+        explicit Context(ContainerNode& root)
+            : iterator(root)
+        { }
+        Context(ContainerNode& root, Node& node, size_t slotNodeIndex = notFound)
+            : iterator(root, &node)
+            , slotNodeIndex(slotNodeIndex)
         { }
 
-        Element* host;
+        ElementAndTextDescendantIterator iterator;
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-        HTMLSlotElement* currentSlot { nullptr };
-        unsigned currentSlotNodeIndex { 0 };
+        size_t slotNodeIndex { notFound };
 #endif
     };
-    Vector<ShadowContext, 4> m_shadowStack;
-};
+    Context& context() { return m_contextStack.last(); }
+    const Context& context() const { return m_contextStack.last(); }
+    Node& current() { return *context().iterator; }
 
-inline ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root)
-    : m_root(root)
-{
-    ASSERT(!is<ShadowRoot>(m_root));
-}
+    Vector<Context, 4> m_contextStack;
+};
 
-inline ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current)
-    : m_root(root)
-    , m_current(&current)
+inline ComposedTreeIterator::ComposedTreeIterator()
+    : m_contextStack({ { } })
 {
-    ASSERT(!is<ShadowRoot>(m_root));
-    ASSERT(!is<ShadowRoot>(m_current));
-
-    bool mayNeedShadowStack = m_root.shadowRoot() || (m_current != &m_root && current.parentNode() != &m_root);
-    if (mayNeedShadowStack)
-        initializeShadowStack();
 }
 
 inline ComposedTreeIterator& ComposedTreeIterator::traverseNext()
 {
-    if (auto* shadowRoot = m_current->shadowRoot()) {
-        m_shadowStack.append(shadowRoot->host());
-        m_current = shadowRoot;
+    if (auto* shadowRoot = context().iterator->shadowRoot()) {
+        if (pushContext(*shadowRoot))
+            return *this;
     }
 
-    if (m_shadowStack.isEmpty())
-        m_current = NodeTraversal::next(*m_current, &m_root);
-    else
+    if (m_contextStack.size() > 1) {
         traverseNextInShadowTree();
+        return *this;
+    }
 
+    context().iterator.traverseNext();
+    return *this;
+}
+
+inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
+{
+    context().iterator.traverseNextSkippingChildren();
+
+    if (!context().iterator && m_contextStack.size() > 1)
+        traverseNextLeavingContext();
+    
     return *this;
 }
 
 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSibling()
 {
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-    bool isAssignedToSlot = !m_shadowStack.isEmpty() && m_current->parentNode()->shadowRoot();
-    if (isAssignedToSlot) {
-        traverseNextSiblingSlot();
+    if (current().parentNode()->shadowRoot()) {
+        traverseSiblingInSlot(1);
         return *this;
     }
 #endif
-    m_current = m_current->nextSibling();
+    context().iterator.traverseNextSibling();
     return *this;
 }
 
 inline ComposedTreeIterator& ComposedTreeIterator::traversePreviousSibling()
 {
 #if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-    bool isAssignedToSlot = !m_shadowStack.isEmpty() && m_current->parentNode()->shadowRoot();
-    if (isAssignedToSlot) {
-        traversePreviousSiblingSlot();
+    if (current().parentNode()->shadowRoot()) {
+        traverseSiblingInSlot(-1);
         return *this;
     }
 #endif
-    m_current = m_current->previousSibling();
+    context().iterator.traversePreviousSibling();
     return *this;
 }
 
-inline ComposedTreeIterator& ComposedTreeIterator::traverseParent()
+inline unsigned ComposedTreeIterator::depth() const
 {
-    if (m_shadowStack.isEmpty())
-        m_current = m_current->parentNode();
-    else
-        traverseParentInShadowTree();
-
-    return *this;
+    unsigned depth = 0;
+    for (auto& context : m_contextStack)
+        depth += context.iterator.depth();
+    return depth;
 }
 
 class ComposedTreeDescendantAdapter {
@@ -152,8 +155,8 @@ public:
         : m_parent(parent)
     { }
 
-    ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent, m_parent).traverseNext(); }
-    ComposedTreeIterator end() { return ComposedTreeIterator(m_parent); }
+    ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent); }
+    ComposedTreeIterator end() { return { }; }
     ComposedTreeIterator at(const Node& child) { return ComposedTreeIterator(m_parent, const_cast<Node&>(child)); }
     
 private:
@@ -164,7 +167,8 @@ class ComposedTreeChildAdapter {
 public:
     class Iterator : public ComposedTreeIterator {
     public:
-        Iterator(ContainerNode& root)
+        Iterator() = default;
+        explicit Iterator(ContainerNode& root)
             : ComposedTreeIterator(root)
         { }
         Iterator(ContainerNode& root, Node& current)
@@ -179,8 +183,8 @@ public:
         : m_parent(parent)
     { }
 
-    Iterator begin() { return static_cast<Iterator&>(Iterator(m_parent, m_parent).traverseNext()); }
-    Iterator end() { return Iterator(m_parent); }
+    Iterator begin() { return Iterator(m_parent); }
+    Iterator end() { return { }; }
     Iterator at(const Node& child) { return Iterator(m_parent, const_cast<Node&>(child)); }
 
 private:
diff --git a/Source/WebCore/dom/ElementAndTextDescendantIterator.h b/Source/WebCore/dom/ElementAndTextDescendantIterator.h
new file mode 100644 (file)
index 0000000..cb2df22
--- /dev/null
@@ -0,0 +1,320 @@
+/*
+ * Copyright (C) 2016 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 ElementAndTextDescendantIterator_h
+#define ElementAndTextDescendantIterator_h
+
+#include "Element.h"
+#include "ElementIteratorAssertions.h"
+#include "Text.h"
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+class ElementAndTextDescendantIterator {
+public:
+    ElementAndTextDescendantIterator();
+    explicit ElementAndTextDescendantIterator(ContainerNode& root);
+    ElementAndTextDescendantIterator(ContainerNode& root, Node* current);
+
+    ElementAndTextDescendantIterator& operator++() { return traverseNext(); }
+
+    Node& operator*();
+    Node* operator->();
+    const Node& operator*() const;
+    const Node* operator->() const;
+
+    bool operator==(const ElementAndTextDescendantIterator& other) const;
+    bool operator!=(const ElementAndTextDescendantIterator& other) const;
+
+    bool operator!() const { return !m_current; }
+    explicit operator bool() const { return m_current; }
+
+    void dropAssertions();
+
+    ElementAndTextDescendantIterator& traverseNext();
+    ElementAndTextDescendantIterator& traverseNextSkippingChildren();
+    ElementAndTextDescendantIterator& traverseNextSibling();
+    ElementAndTextDescendantIterator& traversePreviousSibling();
+
+    unsigned depth() const { return m_depth; }
+
+private:
+    static bool isElementOrText(const Node& node) { return is<Element>(node) || is<Text>(node); }
+    static Node* firstChild(Node&);
+    static Node* nextSibling(Node&);
+    static Node* previousSibling(Node&);
+
+    void popAncestorSiblingStack();
+
+    Node* m_current;
+    struct AncestorSibling {
+        Node* node;
+        unsigned depth;
+    };
+    Vector<AncestorSibling, 16> m_ancestorSiblingStack;
+    unsigned m_depth { 0 };
+
+#if !ASSERT_DISABLED
+    ElementIteratorAssertions m_assertions;
+#endif
+};
+
+class ElementAndTextDescendantIteratorAdapter {
+public:
+    explicit ElementAndTextDescendantIteratorAdapter(ContainerNode& root);
+    ElementAndTextDescendantIterator begin();
+    ElementAndTextDescendantIterator end();
+
+private:
+    ContainerNode& m_root;
+};
+
+ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode&);
+
+// ElementAndTextDescendantIterator
+
+inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator()
+    : m_current(nullptr)
+{
+}
+
+inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator(ContainerNode& root)
+    : m_current(firstChild(root))
+#if !ASSERT_DISABLED
+    , m_assertions(m_current)
+#endif
+{
+    if (!m_current)
+        return;
+    m_ancestorSiblingStack.uncheckedAppend({ nullptr, 0 });
+    m_depth = 1;
+}
+
+inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator(ContainerNode& root, Node* current)
+    : m_current(current != &root ? current : nullptr)
+#if !ASSERT_DISABLED
+    , m_assertions(m_current)
+#endif
+{
+    if (!m_current)
+        return;
+    ASSERT(isElementOrText(*m_current));
+
+    Vector<Node*, 20> ancestorStack;
+    auto* ancestor = m_current->parentNode();
+    while (ancestor != &root) {
+        ancestorStack.append(ancestor);
+        ancestor = ancestor->parentNode();
+    }
+
+    m_ancestorSiblingStack.uncheckedAppend({ nullptr, 0 });
+    for (unsigned i = ancestorStack.size(); i; --i) {
+        if (auto* sibling = nextSibling(*ancestorStack[i - 1]))
+            m_ancestorSiblingStack.append({ sibling, i });
+    }
+
+    m_depth = ancestorStack.size() + 1;
+}
+
+inline void ElementAndTextDescendantIterator::dropAssertions()
+{
+#if !ASSERT_DISABLED
+    m_assertions.clear();
+#endif
+}
+
+inline Node* ElementAndTextDescendantIterator::firstChild(Node& current)
+{
+    auto* node = current.firstChild();
+    while (node && !isElementOrText(*node))
+        node = node->nextSibling();
+    return node;
+}
+
+inline Node* ElementAndTextDescendantIterator::nextSibling(Node& current)
+{
+    auto* node = current.nextSibling();
+    while (node && !isElementOrText(*node))
+        node = node->nextSibling();
+    return node;
+}
+
+inline Node* ElementAndTextDescendantIterator::previousSibling(Node& current)
+{
+    auto* node = current.previousSibling();
+    while (node && !isElementOrText(*node))
+        node = node->previousSibling();
+    return node;
+}
+
+inline void ElementAndTextDescendantIterator::popAncestorSiblingStack()
+{
+    m_current = m_ancestorSiblingStack.last().node;
+    m_depth = m_ancestorSiblingStack.last().depth;
+    m_ancestorSiblingStack.removeLast();
+
+#if !ASSERT_DISABLED
+    // Drop the assertion when the iterator reaches the end.
+    if (!m_current)
+        m_assertions.dropEventDispatchAssertion();
+#endif
+}
+
+inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNext()
+{
+    ASSERT(m_current);
+    ASSERT(!m_assertions.domTreeHasMutated());
+
+    auto* firstChild = ElementAndTextDescendantIterator::firstChild(*m_current);
+    auto* nextSibling = ElementAndTextDescendantIterator::nextSibling(*m_current);
+    if (firstChild) {
+        if (nextSibling)
+            m_ancestorSiblingStack.append({ nextSibling, m_depth });
+        ++m_depth;
+        m_current = firstChild;
+        return *this;
+    }
+    if (!nextSibling) {
+        popAncestorSiblingStack();
+        return *this;
+    }
+
+    m_current = nextSibling;
+    return *this;
+}
+
+inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNextSkippingChildren()
+{
+    ASSERT(m_current);
+    ASSERT(!m_assertions.domTreeHasMutated());
+
+    auto* nextSibling = ElementAndTextDescendantIterator::nextSibling(*m_current);
+    if (!nextSibling) {
+        popAncestorSiblingStack();
+        return *this;
+    }
+
+    m_current = nextSibling;
+    return *this;
+}
+
+inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNextSibling()
+{
+    ASSERT(m_current);
+    ASSERT(!m_assertions.domTreeHasMutated());
+
+    m_current = nextSibling(*m_current);
+
+#if !ASSERT_DISABLED
+    if (!m_current)
+        m_assertions.dropEventDispatchAssertion();
+#endif
+    return *this;
+}
+
+inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traversePreviousSibling()
+{
+    ASSERT(m_current);
+    ASSERT(!m_assertions.domTreeHasMutated());
+
+    m_current = previousSibling(*m_current);
+
+#if !ASSERT_DISABLED
+    if (!m_current)
+        m_assertions.dropEventDispatchAssertion();
+#endif
+    return *this;
+}
+
+inline Node& ElementAndTextDescendantIterator::operator*()
+{
+    ASSERT(m_current);
+    ASSERT(isElementOrText(*m_current));
+    ASSERT(!m_assertions.domTreeHasMutated());
+    return *m_current;
+}
+
+inline Node* ElementAndTextDescendantIterator::operator->()
+{
+    ASSERT(m_current);
+    ASSERT(isElementOrText(*m_current));
+    ASSERT(!m_assertions.domTreeHasMutated());
+    return m_current;
+}
+
+inline const Node& ElementAndTextDescendantIterator::operator*() const
+{
+    ASSERT(m_current);
+    ASSERT(isElementOrText(*m_current));
+    ASSERT(!m_assertions.domTreeHasMutated());
+    return *m_current;
+}
+
+inline const Node* ElementAndTextDescendantIterator::operator->() const
+{
+    ASSERT(m_current);
+    ASSERT(isElementOrText(*m_current));
+    ASSERT(!m_assertions.domTreeHasMutated());
+    return m_current;
+}
+
+inline bool ElementAndTextDescendantIterator::operator==(const ElementAndTextDescendantIterator& other) const
+{
+    ASSERT(!m_assertions.domTreeHasMutated());
+    return m_current == other.m_current;
+}
+
+inline bool ElementAndTextDescendantIterator::operator!=(const ElementAndTextDescendantIterator& other) const
+{
+    return !(*this == other);
+}
+
+// ElementAndTextDescendantIteratorAdapter
+
+inline ElementAndTextDescendantIteratorAdapter::ElementAndTextDescendantIteratorAdapter(ContainerNode& root)
+    : m_root(root)
+{
+}
+
+inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::begin()
+{
+    return ElementAndTextDescendantIterator(m_root);
+}
+
+inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::end()
+{
+    return { };
+}
+
+// Standalone functions
+
+inline ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode& root)
+{
+    return ElementAndTextDescendantIteratorAdapter(root);
+}
+
+}
+#endif
index e138f76..2d438be 100644 (file)
@@ -32,7 +32,7 @@ namespace WebCore {
 
 class ElementIteratorAssertions {
 public:
-    ElementIteratorAssertions(const Element* first = nullptr);
+    ElementIteratorAssertions(const Node* first = nullptr);
     bool domTreeHasMutated() const;
     void dropEventDispatchAssertion();
     void clear();
@@ -45,7 +45,7 @@ private:
 
 // FIXME: No real point in doing these as inlines; they are for debugging and we usually turn off inlining in debug builds.
 
-inline ElementIteratorAssertions::ElementIteratorAssertions(const Element* first)
+inline ElementIteratorAssertions::ElementIteratorAssertions(const Node* first)
     : m_document(first ? &first->document() : nullptr)
     , m_initialDOMTreeVersion(first ? m_document->domTreeVersion() : 0)
 {