Delete WebMetal implementation in favor of WebGPU
[WebKit-https.git] / Source / WebCore / dom / ComposedTreeIterator.h
1 /*
2  * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #pragma once
27
28 #include "ElementAndTextDescendantIterator.h"
29 #include "HTMLSlotElement.h"
30 #include "ShadowRoot.h"
31
32 namespace WebCore {
33
34 class HTMLSlotElement;
35
36 class ComposedTreeIterator {
37 public:
38     ComposedTreeIterator();
39     enum FirstChildTag { FirstChild };
40     ComposedTreeIterator(ContainerNode& root, FirstChildTag);
41     ComposedTreeIterator(ContainerNode& root, Node& current);
42
43     Node& operator*() { return current(); }
44     Node* operator->() { return &current(); }
45
46     bool operator==(const ComposedTreeIterator& other) const { return context().iterator == other.context().iterator; }
47     bool operator!=(const ComposedTreeIterator& other) const { return context().iterator != other.context().iterator; }
48
49     ComposedTreeIterator& operator++() { return traverseNext(); }
50
51     ComposedTreeIterator& traverseNext();
52     ComposedTreeIterator& traverseNextSkippingChildren();
53     ComposedTreeIterator& traverseNextSibling();
54     ComposedTreeIterator& traversePreviousSibling();
55
56     unsigned depth() const;
57
58     void dropAssertions();
59
60 private:
61     void initializeContextStack(ContainerNode& root, Node& current);
62     void traverseNextInShadowTree();
63     void traverseNextLeavingContext();
64     void traverseShadowRoot(ShadowRoot&);
65     bool advanceInSlot(int direction);
66     void traverseSiblingInSlot(int direction);
67
68     struct Context {
69         Context();
70         Context(ContainerNode& root, FirstChildTag);
71         Context(ContainerNode& root, Node& node);
72
73         enum SlottedTag { Slotted };
74         Context(ContainerNode& root, Node& node, SlottedTag);
75         ElementAndTextDescendantIterator iterator;
76         ElementAndTextDescendantIterator end;
77         size_t slotNodeIndex { notFound };
78     };
79     Context& context() { return m_contextStack.last(); }
80     const Context& context() const { return m_contextStack.last(); }
81     Node& current() { return *context().iterator; }
82
83     bool m_rootIsInShadowTree { false };
84     bool m_didDropAssertions { false };
85     Vector<Context, 8> m_contextStack;
86 };
87
88 inline ComposedTreeIterator::ComposedTreeIterator()
89 {
90     m_contextStack.uncheckedAppend({ });
91 }
92
93 inline ComposedTreeIterator& ComposedTreeIterator::traverseNext()
94 {
95     if (auto* shadowRoot = context().iterator->shadowRoot()) {
96         traverseShadowRoot(*shadowRoot);
97         return *this;
98     }
99
100     if (m_contextStack.size() > 1 || m_rootIsInShadowTree) {
101         traverseNextInShadowTree();
102         return *this;
103     }
104
105     context().iterator.traverseNext();
106     return *this;
107 }
108
109 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
110 {
111     context().iterator.traverseNextSkippingChildren();
112
113     if (context().iterator == context().end)
114         traverseNextLeavingContext();
115     
116     return *this;
117 }
118
119 inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSibling()
120 {
121     if (current().parentNode()->shadowRoot()) {
122         traverseSiblingInSlot(1);
123         return *this;
124     }
125     context().iterator.traverseNextSibling();
126     return *this;
127 }
128
129 inline ComposedTreeIterator& ComposedTreeIterator::traversePreviousSibling()
130 {
131     if (current().parentNode()->shadowRoot()) {
132         traverseSiblingInSlot(-1);
133         return *this;
134     }
135     context().iterator.traversePreviousSibling();
136     return *this;
137 }
138
139 inline unsigned ComposedTreeIterator::depth() const
140 {
141     unsigned depth = 0;
142     for (auto& context : m_contextStack)
143         depth += context.iterator.depth();
144     return depth;
145 }
146
147 class ComposedTreeDescendantAdapter {
148 public:
149     ComposedTreeDescendantAdapter(ContainerNode& parent)
150         : m_parent(parent)
151     { }
152
153     ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent, ComposedTreeIterator::FirstChild); }
154     ComposedTreeIterator end() { return { }; }
155     ComposedTreeIterator at(const Node& child) { return ComposedTreeIterator(m_parent, const_cast<Node&>(child)); }
156     
157 private:
158     ContainerNode& m_parent;
159 };
160
161 class ComposedTreeChildAdapter {
162 public:
163     class Iterator : public ComposedTreeIterator {
164     public:
165         Iterator() = default;
166         explicit Iterator(ContainerNode& root)
167             : ComposedTreeIterator(root, ComposedTreeIterator::FirstChild)
168         { }
169         Iterator(ContainerNode& root, Node& current)
170             : ComposedTreeIterator(root, current)
171         { }
172
173         Iterator& operator++() { return static_cast<Iterator&>(traverseNextSibling()); }
174         Iterator& operator--() { return static_cast<Iterator&>(traversePreviousSibling()); }
175     };
176
177     ComposedTreeChildAdapter(ContainerNode& parent)
178         : m_parent(parent)
179     { }
180
181     Iterator begin() { return Iterator(m_parent); }
182     Iterator end() { return { }; }
183     Iterator at(const Node& child) { return Iterator(m_parent, const_cast<Node&>(child)); }
184
185 private:
186     ContainerNode& m_parent;
187 };
188
189 // FIXME: We should have const versions too.
190 inline ComposedTreeDescendantAdapter composedTreeDescendants(ContainerNode& parent)
191 {
192     return ComposedTreeDescendantAdapter(parent);
193 }
194
195 inline ComposedTreeChildAdapter composedTreeChildren(ContainerNode& parent)
196 {
197     return ComposedTreeChildAdapter(parent);
198 }
199
200 enum class ComposedTreeAsTextMode { Normal, WithPointers };
201 WEBCORE_EXPORT String composedTreeAsText(ContainerNode& root, ComposedTreeAsTextMode = ComposedTreeAsTextMode::Normal);
202
203
204 // Helper functions for walking the composed tree.
205 // FIXME: Use ComposedTreeIterator instead. These functions are more expensive because they might do O(n) work.
206
207 inline HTMLSlotElement* assignedSlotIgnoringUserAgentShadow(Node& node)
208 {
209     auto* slot = node.assignedSlot();
210     if (!slot || slot->containingShadowRoot()->mode() == ShadowRootMode::UserAgent)
211         return nullptr;
212     return slot;
213 }
214
215 inline ShadowRoot* shadowRootIgnoringUserAgentShadow(Node& node)
216 {
217     auto* shadowRoot = node.shadowRoot();
218     if (!shadowRoot || shadowRoot->mode() == ShadowRootMode::UserAgent)
219         return nullptr;
220     return shadowRoot;
221 }
222
223 inline Node* firstChildInComposedTreeIgnoringUserAgentShadow(Node& node)
224 {
225     if (auto* shadowRoot = shadowRootIgnoringUserAgentShadow(node))
226         return shadowRoot->firstChild();
227     if (is<HTMLSlotElement>(node)) {
228         if (auto* assignedNodes = downcast<HTMLSlotElement>(node).assignedNodes())
229             return assignedNodes->at(0);
230     }
231     return node.firstChild();
232 }
233
234 inline Node* nextSiblingInComposedTreeIgnoringUserAgentShadow(Node& node)
235 {
236     if (auto* slot = assignedSlotIgnoringUserAgentShadow(node)) {
237         auto* assignedNodes = slot->assignedNodes();
238         ASSERT(assignedNodes);
239         auto nodeIndex = assignedNodes->find(&node);
240         ASSERT(nodeIndex != notFound);
241         if (assignedNodes->size() > nodeIndex + 1)
242             return assignedNodes->at(nodeIndex + 1);
243         return nullptr;
244     }
245     return node.nextSibling();
246 }
247
248 inline Node* nextSkippingChildrenInComposedTreeIgnoringUserAgentShadow(Node& node)
249 {
250     if (auto* sibling = nextSiblingInComposedTreeIgnoringUserAgentShadow(node))
251         return sibling;
252     for (auto* ancestor = node.parentInComposedTree(); ancestor; ancestor = ancestor->parentInComposedTree()) {
253         if (auto* sibling = nextSiblingInComposedTreeIgnoringUserAgentShadow(*ancestor))
254             return sibling;
255     }
256     return nullptr;
257 }
258
259 inline Node* nextInComposedTreeIgnoringUserAgentShadow(Node& node)
260 {
261     if (auto* firstChild = firstChildInComposedTreeIgnoringUserAgentShadow(node))
262         return firstChild;
263     return nextSkippingChildrenInComposedTreeIgnoringUserAgentShadow(node);
264 }
265
266 } // namespace WebCore