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 ¤t(); } |
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 |
267 | |