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