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
32namespace WebCore {
33
34class HTMLSlotElement;
35
36class ComposedTreeIterator {
37public:
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
60private:
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
88inline ComposedTreeIterator::ComposedTreeIterator()
89{
90 m_contextStack.uncheckedAppend({ });
91}
92
93inline 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
109inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
110{
111 context().iterator.traverseNextSkippingChildren();
112
113 if (context().iterator == context().end)
114 traverseNextLeavingContext();
115
116 return *this;
117}
118
119inline 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
129inline 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
139inline 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
147class ComposedTreeDescendantAdapter {
148public:
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
157private:
158 ContainerNode& m_parent;
159};
160
161class ComposedTreeChildAdapter {
162public:
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
185private:
186 ContainerNode& m_parent;
187};
188
189// FIXME: We should have const versions too.
190inline ComposedTreeDescendantAdapter composedTreeDescendants(ContainerNode& parent)
191{
192 return ComposedTreeDescendantAdapter(parent);
193}
194
195inline ComposedTreeChildAdapter composedTreeChildren(ContainerNode& parent)
196{
197 return ComposedTreeChildAdapter(parent);
198}
199
200enum class ComposedTreeAsTextMode { Normal, WithPointers };
201WEBCORE_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
207inline 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
215inline 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
223inline 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
234inline 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
248inline 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
259inline Node* nextInComposedTreeIgnoringUserAgentShadow(Node& node)
260{
261 if (auto* firstChild = firstChildInComposedTreeIgnoringUserAgentShadow(node))
262 return firstChild;
263 return nextSkippingChildrenInComposedTreeIgnoringUserAgentShadow(node);
264}
265
266} // namespace WebCore
267