1 files changed, 202 insertions, 0 deletions
diff --git a/Source/WebCore/dom/ComposedTreeIterator.h b/Source/WebCore/dom/ComposedTreeIterator.h
new file mode 100644
index 000000000..89740cfb8
--- /dev/null
+++ b/Source/WebCore/dom/ComposedTreeIterator.h
@@ -0,0 +1,202 @@
+/*
+ * 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.
+ */
+
+#pragma once
+
+#include "ElementAndTextDescendantIterator.h"
+#include "ShadowRoot.h"
+
+namespace WebCore {
+
+class HTMLSlotElement;
+
+class ComposedTreeIterator {
+public:
+    ComposedTreeIterator();
+    enum FirstChildTag { FirstChild };
+    ComposedTreeIterator(ContainerNode& root, FirstChildTag);
+    ComposedTreeIterator(ContainerNode& root, Node& current);
+
+    Node& operator*() { return current(); }
+    Node* operator->() { return &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 traverseNext(); }
+
+    ComposedTreeIterator& traverseNext();
+    ComposedTreeIterator& traverseNextSkippingChildren();
+    ComposedTreeIterator& traverseNextSibling();
+    ComposedTreeIterator& traversePreviousSibling();
+
+    unsigned depth() const;
+
+    void dropAssertions();
+
+private:
+    void initializeContextStack(ContainerNode& root, Node& current);
+    void traverseNextInShadowTree();
+    void traverseNextLeavingContext();
+    void traverseShadowRoot(ShadowRoot&);
+    bool advanceInSlot(int direction);
+    void traverseSiblingInSlot(int direction);
+
+    struct Context {
+        Context();
+        Context(ContainerNode& root, FirstChildTag);
+        Context(ContainerNode& root, Node& node);
+
+        enum SlottedTag { Slotted };
+        Context(ContainerNode& root, Node& node, SlottedTag);
+        ElementAndTextDescendantIterator iterator;
+        ElementAndTextDescendantIterator end;
+        size_t slotNodeIndex { notFound };
+    };
+    Context& context() { return m_contextStack.last(); }
+    const Context& context() const { return m_contextStack.last(); }
+    Node& current() { return *context().iterator; }
+
+    bool m_rootIsInShadowTree { false };
+    bool m_didDropAssertions { false };
+    Vector<Context, 8> m_contextStack;
+};
+
+inline ComposedTreeIterator::ComposedTreeIterator()
+{
+    m_contextStack.uncheckedAppend({ });
+}
+
+inline ComposedTreeIterator& ComposedTreeIterator::traverseNext()
+{
+    if (auto* shadowRoot = context().iterator->shadowRoot()) {
+        traverseShadowRoot(*shadowRoot);
+        return *this;
+    }
+
+    if (m_contextStack.size() > 1 || m_rootIsInShadowTree) {
+        traverseNextInShadowTree();
+        return *this;
+    }
+
+    context().iterator.traverseNext();
+    return *this;
+}
+
+inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
+{
+    context().iterator.traverseNextSkippingChildren();
+
+    if (context().iterator == context().end)
+        traverseNextLeavingContext();
+    
+    return *this;
+}
+
+inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSibling()
+{
+    if (current().parentNode()->shadowRoot()) {
+        traverseSiblingInSlot(1);
+        return *this;
+    }
+    context().iterator.traverseNextSibling();
+    return *this;
+}
+
+inline ComposedTreeIterator& ComposedTreeIterator::traversePreviousSibling()
+{
+    if (current().parentNode()->shadowRoot()) {
+        traverseSiblingInSlot(-1);
+        return *this;
+    }
+    context().iterator.traversePreviousSibling();
+    return *this;
+}
+
+inline unsigned ComposedTreeIterator::depth() const
+{
+    unsigned depth = 0;
+    for (auto& context : m_contextStack)
+        depth += context.iterator.depth();
+    return depth;
+}
+
+class ComposedTreeDescendantAdapter {
+public:
+    ComposedTreeDescendantAdapter(ContainerNode& parent)
+        : m_parent(parent)
+    { }
+
+    ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent, ComposedTreeIterator::FirstChild); }
+    ComposedTreeIterator end() { return { }; }
+    ComposedTreeIterator at(const Node& child) { return ComposedTreeIterator(m_parent, const_cast<Node&>(child)); }
+    
+private:
+    ContainerNode& m_parent;
+};
+
+class ComposedTreeChildAdapter {
+public:
+    class Iterator : public ComposedTreeIterator {
+    public:
+        Iterator() = default;
+        explicit Iterator(ContainerNode& root)
+            : ComposedTreeIterator(root, ComposedTreeIterator::FirstChild)
+        { }
+        Iterator(ContainerNode& root, Node& current)
+            : ComposedTreeIterator(root, current)
+        { }
+
+        Iterator& operator++() { return static_cast<Iterator&>(traverseNextSibling()); }
+        Iterator& operator--() { return static_cast<Iterator&>(traversePreviousSibling()); }
+    };
+
+    ComposedTreeChildAdapter(ContainerNode& parent)
+        : m_parent(parent)
+    { }
+
+    Iterator begin() { return Iterator(m_parent); }
+    Iterator end() { return { }; }
+    Iterator at(const Node& child) { return Iterator(m_parent, const_cast<Node&>(child)); }
+
+private:
+    ContainerNode& m_parent;
+};
+
+// FIXME: We should have const versions too.
+inline ComposedTreeDescendantAdapter composedTreeDescendants(ContainerNode& parent)
+{
+    return ComposedTreeDescendantAdapter(parent);
+}
+
+inline ComposedTreeChildAdapter composedTreeChildren(ContainerNode& parent)
+{
+    return ComposedTreeChildAdapter(parent);
+}
+
+enum class ComposedTreeAsTextMode { Normal, WithPointers };
+WEBCORE_EXPORT String composedTreeAsText(ContainerNode& root, ComposedTreeAsTextMode = ComposedTreeAsTextMode::Normal);
+
+} // namespace WebCore