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
32namespace WebCore {
33
34ComposedTreeIterator::Context::Context()
35{
36}
37
38ComposedTreeIterator::Context::Context(ContainerNode& root, FirstChildTag)
39 : iterator(root, ElementAndTextDescendantIterator::FirstChild)
40{
41}
42
43ComposedTreeIterator::Context::Context(ContainerNode& root, Node& node)
44 : iterator(root, &node)
45{
46}
47
48ComposedTreeIterator::Context::Context(ContainerNode& root, Node& node, SlottedTag)
49 : iterator(root, &node)
50 , end(iterator)
51{
52 end.traverseNextSibling();
53}
54
55ComposedTreeIterator::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
76ComposedTreeIterator::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() || (&current != &root && current.parentNode() != &root);
83 if (mayNeedShadowStack)
84 initializeContextStack(root, current);
85 else
86 m_contextStack.uncheckedAppend(Context(root, current));
87}
88
89void 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 = &current;
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
136void ComposedTreeIterator::dropAssertions()
137{
138 for (auto& context : m_contextStack)
139 context.iterator.dropAssertions();
140 m_didDropAssertions = true;
141}
142
143void 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
158void 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
178void 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
190bool 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
205void 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
216String 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