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