1 files changed, 241 insertions, 0 deletions
diff --git a/Source/WebCore/dom/ComposedTreeIterator.cpp b/Source/WebCore/dom/ComposedTreeIterator.cpp
new file mode 100644
index 000000000..af554ac04
--- /dev/null
+++ b/Source/WebCore/dom/ComposedTreeIterator.cpp
@@ -0,0 +1,241 @@
+/*
+ * 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
+ * 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.
+ */
+
+#include "config.h"
+#include "ComposedTreeIterator.h"
+
+#include "HTMLSlotElement.h"
+#include "TextStream.h"
+
+namespace WebCore {
+
+ComposedTreeIterator::Context::Context()
+{
+}
+
+ComposedTreeIterator::Context::Context(ContainerNode& root, FirstChildTag)
+    : iterator(root, ElementAndTextDescendantIterator::FirstChild)
+{
+}
+
+ComposedTreeIterator::Context::Context(ContainerNode& root, Node& node)
+    : iterator(root, &node)
+{
+}
+
+ComposedTreeIterator::Context::Context(ContainerNode& root, Node& node, SlottedTag)
+    : iterator(root, &node)
+    , end(iterator)
+{
+    end.traverseNextSibling();
+}
+
+ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, FirstChildTag)
+    : m_rootIsInShadowTree(root.isInShadowTree())
+{
+    ASSERT(!is<ShadowRoot>(root));
+
+    if (is<HTMLSlotElement>(root)) {
+        auto& slot = downcast<HTMLSlotElement>(root);
+        if (auto* assignedNodes = slot.assignedNodes()) {
+            initializeContextStack(root, *assignedNodes->at(0));
+            return;
+        }
+    }
+    if (auto* shadowRoot = root.shadowRoot()) {
+        ElementAndTextDescendantIterator firstChild(*shadowRoot, ElementAndTextDescendantIterator::FirstChild);
+        initializeContextStack(root, firstChild ? *firstChild : root);
+        return;
+    }
+
+    m_contextStack.uncheckedAppend(Context(root, FirstChild));
+}
+
+ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current)
+    : m_rootIsInShadowTree(root.isInShadowTree())
+{
+    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 = &current;
+    auto* contextCurrent = node;
+    size_t currentSlotNodeIndex = notFound;
+    while (node != &root) {
+        auto* parent = node->parentNode();
+        if (!parent) {
+            *this = { };
+            return;
+        }
+        if (is<ShadowRoot>(*parent)) {
+            auto& shadowRoot = downcast<ShadowRoot>(*parent);
+            m_contextStack.append(Context(shadowRoot, *contextCurrent));
+            m_contextStack.last().slotNodeIndex = currentSlotNodeIndex;
+
+            node = shadowRoot.host();
+            contextCurrent = node;
+            currentSlotNodeIndex = notFound;
+            continue;
+        }
+        if (auto* shadowRoot = parent->shadowRoot()) {
+            m_contextStack.append(Context(*parent, *contextCurrent, Context::Slotted));
+            m_contextStack.last().slotNodeIndex = currentSlotNodeIndex;
+
+            auto* assignedSlot = shadowRoot->findAssignedSlot(*node);
+            if (assignedSlot) {
+                currentSlotNodeIndex = assignedSlot->assignedNodes()->find(node);
+                ASSERT(currentSlotNodeIndex != notFound);
+                node = assignedSlot;
+                contextCurrent = assignedSlot;
+                continue;
+            }
+            // The node is not part of the composed tree.
+            *this = { };
+            return;
+        }
+        node = parent;
+    }
+    m_contextStack.append(Context(root, *contextCurrent));
+    m_contextStack.last().slotNodeIndex = currentSlotNodeIndex;
+
+    m_contextStack.reverse();
+}
+
+void ComposedTreeIterator::dropAssertions()
+{
+    for (auto& context : m_contextStack)
+        context.iterator.dropAssertions();
+    m_didDropAssertions = true;
+}
+
+void ComposedTreeIterator::traverseShadowRoot(ShadowRoot& shadowRoot)
+{
+    Context shadowContext(shadowRoot, FirstChild);
+    if (!shadowContext.iterator) {
+        // Empty shadow root.
+        traverseNextSkippingChildren();
+        return;
+    }
+
+    if (m_didDropAssertions)
+        shadowContext.iterator.dropAssertions();
+
+    m_contextStack.append(WTFMove(shadowContext));
+}
+
+void ComposedTreeIterator::traverseNextInShadowTree()
+{
+    ASSERT(m_contextStack.size() > 1 || m_rootIsInShadowTree);
+
+    if (is<HTMLSlotElement>(current())) {
+        auto& slot = downcast<HTMLSlotElement>(current());
+        if (auto* assignedNodes = slot.assignedNodes()) {
+            context().slotNodeIndex = 0;
+            auto* assignedNode = assignedNodes->at(0);
+            m_contextStack.append(Context(*assignedNode->parentElement(), *assignedNode, Context::Slotted));
+            return;
+        }
+    }
+
+    context().iterator.traverseNext();
+
+    if (context().iterator == context().end)
+        traverseNextLeavingContext();
+}
+
+void ComposedTreeIterator::traverseNextLeavingContext()
+{
+    while (context().iterator == context().end && m_contextStack.size() > 1) {
+        m_contextStack.removeLast();
+        if (is<HTMLSlotElement>(current()) && advanceInSlot(1))
+            return;
+        if (context().iterator == context().end)
+            return;
+        context().iterator.traverseNextSkippingChildren();
+    }
+}
+
+bool ComposedTreeIterator::advanceInSlot(int direction)
+{
+    ASSERT(context().slotNodeIndex != notFound);
+
+    auto& assignedNodes = *downcast<HTMLSlotElement>(current()).assignedNodes();
+    // It is fine to underflow this.
+    context().slotNodeIndex += direction;
+    if (context().slotNodeIndex >= assignedNodes.size())
+        return false;
+
+    auto* slotNode = assignedNodes.at(context().slotNodeIndex);
+    m_contextStack.append(Context(*slotNode->parentElement(), *slotNode, Context::Slotted));
+    return true;
+}
+
+void ComposedTreeIterator::traverseSiblingInSlot(int direction)
+{
+    ASSERT(m_contextStack.size() > 1);
+    ASSERT(current().parentNode()->shadowRoot());
+
+    m_contextStack.removeLast();
+
+    if (!advanceInSlot(direction))
+        *this = { };
+}
+
+String composedTreeAsText(ContainerNode& root, ComposedTreeAsTextMode mode)
+{
+    TextStream stream;
+    auto descendants = composedTreeDescendants(root);
+    for (auto it = descendants.begin(), end = descendants.end(); it != end; ++it) {
+        writeIndent(stream, it.depth());
+
+        if (is<Text>(*it)) {
+            stream << "#text";
+            if (mode == ComposedTreeAsTextMode::WithPointers)
+                stream << " " << &*it;
+            stream << "\n";
+            continue;
+        }
+        auto& element = downcast<Element>(*it);
+        stream << element.localName();
+        if (element.shadowRoot())
+            stream << " (shadow root)";
+        if (mode == ComposedTreeAsTextMode::WithPointers)
+            stream << " " << &*it;
+        stream << "\n";
+    }
+    return stream.release();
+}
+
+}