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 | #include "config.h" |
27 | #include "ComposedTreeIterator.h" |
28 | |
29 | #include "HTMLSlotElement.h" |
30 | #include <wtf/text/TextStream.h> |
31 | |
32 | namespace WebCore { |
33 | |
34 | ComposedTreeIterator::Context::Context() |
35 | { |
36 | } |
37 | |
38 | ComposedTreeIterator::Context::Context(ContainerNode& root, FirstChildTag) |
39 | : iterator(root, ElementAndTextDescendantIterator::FirstChild) |
40 | { |
41 | } |
42 | |
43 | ComposedTreeIterator::Context::Context(ContainerNode& root, Node& node) |
44 | : iterator(root, &node) |
45 | { |
46 | } |
47 | |
48 | ComposedTreeIterator::Context::Context(ContainerNode& root, Node& node, SlottedTag) |
49 | : iterator(root, &node) |
50 | , end(iterator) |
51 | { |
52 | end.traverseNextSibling(); |
53 | } |
54 | |
55 | ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, FirstChildTag) |
56 | : m_rootIsInShadowTree(root.isInShadowTree()) |
57 | { |
58 | ASSERT(!is<ShadowRoot>(root)); |
59 | |
60 | if (is<HTMLSlotElement>(root)) { |
61 | auto& slot = downcast<HTMLSlotElement>(root); |
62 | if (auto* assignedNodes = slot.assignedNodes()) { |
63 | initializeContextStack(root, *assignedNodes->at(0)); |
64 | return; |
65 | } |
66 | } |
67 | if (auto* shadowRoot = root.shadowRoot()) { |
68 | ElementAndTextDescendantIterator firstChild(*shadowRoot, ElementAndTextDescendantIterator::FirstChild); |
69 | initializeContextStack(root, firstChild ? *firstChild : root); |
70 | return; |
71 | } |
72 | |
73 | m_contextStack.uncheckedAppend(Context(root, FirstChild)); |
74 | } |
75 | |
76 | ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current) |
77 | : m_rootIsInShadowTree(root.isInShadowTree()) |
78 | { |
79 | ASSERT(!is<ShadowRoot>(root)); |
80 | ASSERT(!is<ShadowRoot>(current)); |
81 | |
82 | bool mayNeedShadowStack = root.shadowRoot() || (¤t != &root && current.parentNode() != &root); |
83 | if (mayNeedShadowStack) |
84 | initializeContextStack(root, current); |
85 | else |
86 | m_contextStack.uncheckedAppend(Context(root, current)); |
87 | } |
88 | |
89 | void ComposedTreeIterator::initializeContextStack(ContainerNode& root, Node& current) |
90 | { |
91 | // This code sets up the iterator for arbitrary node/root pair. It is not needed in common cases |
92 | // or completes fast because node and root are close (like in composedTreeChildren(*parent).at(node) case). |
93 | auto* node = ¤t; |
94 | auto* contextCurrent = node; |
95 | size_t currentSlotNodeIndex = notFound; |
96 | while (node != &root) { |
97 | auto* parent = node->parentNode(); |
98 | if (!parent) { |
99 | *this = { }; |
100 | return; |
101 | } |
102 | if (is<ShadowRoot>(*parent)) { |
103 | auto& shadowRoot = downcast<ShadowRoot>(*parent); |
104 | m_contextStack.append(Context(shadowRoot, *contextCurrent)); |
105 | m_contextStack.last().slotNodeIndex = currentSlotNodeIndex; |
106 | |
107 | node = shadowRoot.host(); |
108 | contextCurrent = node; |
109 | currentSlotNodeIndex = notFound; |
110 | continue; |
111 | } |
112 | if (auto* shadowRoot = parent->shadowRoot()) { |
113 | m_contextStack.append(Context(*parent, *contextCurrent, Context::Slotted)); |
114 | m_contextStack.last().slotNodeIndex = currentSlotNodeIndex; |
115 | |
116 | auto* assignedSlot = shadowRoot->findAssignedSlot(*node); |
117 | if (assignedSlot) { |
118 | currentSlotNodeIndex = assignedSlot->assignedNodes()->find(node); |
119 | ASSERT(currentSlotNodeIndex != notFound); |
120 | node = assignedSlot; |
121 | contextCurrent = assignedSlot; |
122 | continue; |
123 | } |
124 | // The node is not part of the composed tree. |
125 | *this = { }; |
126 | return; |
127 | } |
128 | node = parent; |
129 | } |
130 | m_contextStack.append(Context(root, *contextCurrent)); |
131 | m_contextStack.last().slotNodeIndex = currentSlotNodeIndex; |
132 | |
133 | m_contextStack.reverse(); |
134 | } |
135 | |
136 | void ComposedTreeIterator::dropAssertions() |
137 | { |
138 | for (auto& context : m_contextStack) |
139 | context.iterator.dropAssertions(); |
140 | m_didDropAssertions = true; |
141 | } |
142 | |
143 | void ComposedTreeIterator::traverseShadowRoot(ShadowRoot& shadowRoot) |
144 | { |
145 | Context shadowContext(shadowRoot, FirstChild); |
146 | if (!shadowContext.iterator) { |
147 | // Empty shadow root. |
148 | traverseNextSkippingChildren(); |
149 | return; |
150 | } |
151 | |
152 | if (m_didDropAssertions) |
153 | shadowContext.iterator.dropAssertions(); |
154 | |
155 | m_contextStack.append(WTFMove(shadowContext)); |
156 | } |
157 | |
158 | void ComposedTreeIterator::traverseNextInShadowTree() |
159 | { |
160 | ASSERT(m_contextStack.size() > 1 || m_rootIsInShadowTree); |
161 | |
162 | if (is<HTMLSlotElement>(current())) { |
163 | auto& slot = downcast<HTMLSlotElement>(current()); |
164 | if (auto* assignedNodes = slot.assignedNodes()) { |
165 | context().slotNodeIndex = 0; |
166 | auto* assignedNode = assignedNodes->at(0); |
167 | m_contextStack.append(Context(*assignedNode->parentElement(), *assignedNode, Context::Slotted)); |
168 | return; |
169 | } |
170 | } |
171 | |
172 | context().iterator.traverseNext(); |
173 | |
174 | if (context().iterator == context().end) |
175 | traverseNextLeavingContext(); |
176 | } |
177 | |
178 | void ComposedTreeIterator::traverseNextLeavingContext() |
179 | { |
180 | while (context().iterator == context().end && m_contextStack.size() > 1) { |
181 | m_contextStack.removeLast(); |
182 | if (is<HTMLSlotElement>(current()) && advanceInSlot(1)) |
183 | return; |
184 | if (context().iterator == context().end) |
185 | return; |
186 | context().iterator.traverseNextSkippingChildren(); |
187 | } |
188 | } |
189 | |
190 | bool ComposedTreeIterator::advanceInSlot(int direction) |
191 | { |
192 | ASSERT(context().slotNodeIndex != notFound); |
193 | |
194 | auto& assignedNodes = *downcast<HTMLSlotElement>(current()).assignedNodes(); |
195 | // It is fine to underflow this. |
196 | context().slotNodeIndex += direction; |
197 | if (context().slotNodeIndex >= assignedNodes.size()) |
198 | return false; |
199 | |
200 | auto* slotNode = assignedNodes.at(context().slotNodeIndex); |
201 | m_contextStack.append(Context(*slotNode->parentElement(), *slotNode, Context::Slotted)); |
202 | return true; |
203 | } |
204 | |
205 | void ComposedTreeIterator::traverseSiblingInSlot(int direction) |
206 | { |
207 | ASSERT(m_contextStack.size() > 1); |
208 | ASSERT(current().parentNode()->shadowRoot()); |
209 | |
210 | m_contextStack.removeLast(); |
211 | |
212 | if (!advanceInSlot(direction)) |
213 | *this = { }; |
214 | } |
215 | |
216 | String composedTreeAsText(ContainerNode& root, ComposedTreeAsTextMode mode) |
217 | { |
218 | TextStream stream; |
219 | auto descendants = composedTreeDescendants(root); |
220 | for (auto it = descendants.begin(), end = descendants.end(); it != end; ++it) { |
221 | writeIndent(stream, it.depth()); |
222 | |
223 | if (is<Text>(*it)) { |
224 | stream << "#text" ; |
225 | if (mode == ComposedTreeAsTextMode::WithPointers) |
226 | stream << " " << &*it; |
227 | stream << "\n" ; |
228 | continue; |
229 | } |
230 | auto& element = downcast<Element>(*it); |
231 | stream << element.localName(); |
232 | if (element.shadowRoot()) |
233 | stream << " (shadow root)" ; |
234 | if (mode == ComposedTreeAsTextMode::WithPointers) |
235 | stream << " " << &*it; |
236 | stream << "\n" ; |
237 | } |
238 | return stream.release(); |
239 | } |
240 | |
241 | } |
242 | |