d6ff4980be133e6378e294bb5af1301e7f17d5b8
[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, 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 {
57     ASSERT(!is<ShadowRoot>(root));
58
59     if (is<HTMLSlotElement>(root)) {
60         auto& slot = downcast<HTMLSlotElement>(root);
61         if (auto* assignedNodes = slot.assignedNodes()) {
62             initializeContextStack(root, *assignedNodes->at(0));
63             return;
64         }
65     }
66     if (auto* shadowRoot = root.shadowRoot()) {
67         ElementAndTextDescendantIterator firstChild(*shadowRoot, ElementAndTextDescendantIterator::FirstChild);
68         initializeContextStack(root, firstChild ? *firstChild : root);
69         return;
70     }
71
72     m_contextStack.uncheckedAppend(Context(root, FirstChild));
73 }
74
75 ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current)
76 {
77     ASSERT(!is<ShadowRoot>(root));
78     ASSERT(!is<ShadowRoot>(current));
79
80     bool mayNeedShadowStack = root.shadowRoot() || (&current != &root && current.parentNode() != &root);
81     if (mayNeedShadowStack)
82         initializeContextStack(root, current);
83     else
84         m_contextStack.uncheckedAppend(Context(root, current));
85 }
86
87 void ComposedTreeIterator::initializeContextStack(ContainerNode& root, Node& current)
88 {
89     // This code sets up the iterator for arbitrary node/root pair. It is not needed in common cases
90     // or completes fast because node and root are close (like in composedTreeChildren(*parent).at(node) case).
91     auto* node = &current;
92     auto* contextCurrent = node;
93     size_t currentSlotNodeIndex = notFound;
94     while (node != &root) {
95         auto* parent = node->parentNode();
96         if (!parent) {
97             *this = { };
98             return;
99         }
100         if (is<ShadowRoot>(*parent)) {
101             auto& shadowRoot = downcast<ShadowRoot>(*parent);
102             m_contextStack.append(Context(shadowRoot, *contextCurrent));
103             m_contextStack.last().slotNodeIndex = currentSlotNodeIndex;
104
105             node = shadowRoot.host();
106             contextCurrent = node;
107             currentSlotNodeIndex = notFound;
108             continue;
109         }
110         if (auto* shadowRoot = parent->shadowRoot()) {
111             m_contextStack.append(Context(*parent, *contextCurrent, Context::Slotted));
112             m_contextStack.last().slotNodeIndex = currentSlotNodeIndex;
113
114             auto* assignedSlot = shadowRoot->findAssignedSlot(*node);
115             if (assignedSlot) {
116                 currentSlotNodeIndex = assignedSlot->assignedNodes()->find(node);
117                 ASSERT(currentSlotNodeIndex != notFound);
118                 node = assignedSlot;
119                 contextCurrent = assignedSlot;
120                 continue;
121             }
122             // The node is not part of the composed tree.
123             *this = { };
124             return;
125         }
126         node = parent;
127     }
128     m_contextStack.append(Context(root, *contextCurrent));
129     m_contextStack.last().slotNodeIndex = currentSlotNodeIndex;
130
131     m_contextStack.reverse();
132 }
133
134 void ComposedTreeIterator::dropAssertions()
135 {
136     for (auto& context : m_contextStack)
137         context.iterator.dropAssertions();
138     m_didDropAssertions = true;
139 }
140
141 void ComposedTreeIterator::traverseShadowRoot(ShadowRoot& shadowRoot)
142 {
143     Context shadowContext(shadowRoot, FirstChild);
144     if (!shadowContext.iterator) {
145         // Empty shadow root.
146         traverseNextSkippingChildren();
147         return;
148     }
149
150     if (m_didDropAssertions)
151         shadowContext.iterator.dropAssertions();
152
153     m_contextStack.append(WTFMove(shadowContext));
154 }
155
156 void ComposedTreeIterator::traverseNextInShadowTree()
157 {
158     ASSERT(m_contextStack.size() > 1);
159
160     if (is<HTMLSlotElement>(current())) {
161         auto& slot = downcast<HTMLSlotElement>(current());
162         if (auto* assignedNodes = slot.assignedNodes()) {
163             context().slotNodeIndex = 0;
164             auto* assignedNode = assignedNodes->at(0);
165             m_contextStack.append(Context(*assignedNode->parentElement(), *assignedNode, Context::Slotted));
166             return;
167         }
168     }
169
170     context().iterator.traverseNext();
171
172     if (context().iterator == context().end)
173         traverseNextLeavingContext();
174 }
175
176 void ComposedTreeIterator::traverseNextLeavingContext()
177 {
178     ASSERT(m_contextStack.size() > 1);
179
180     while (context().iterator == context().end && m_contextStack.size() > 1) {
181         m_contextStack.removeLast();
182         if (context().iterator == context().end)
183             return;
184         if (is<HTMLSlotElement>(current()) && advanceInSlot(1))
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 }