ComposedTreeIterator may crash when first child of shadow root is a comment node
[WebKit-https.git] / Source / WebCore / dom / ElementAndTextDescendantIterator.h
1 /*
2  * Copyright (C) 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 #ifndef ElementAndTextDescendantIterator_h
27 #define ElementAndTextDescendantIterator_h
28
29 #include "Element.h"
30 #include "ElementIteratorAssertions.h"
31 #include "Text.h"
32 #include <wtf/Vector.h>
33
34 namespace WebCore {
35
36 class ElementAndTextDescendantIterator {
37 public:
38     ElementAndTextDescendantIterator();
39     enum FirstChildTag { FirstChild };
40     ElementAndTextDescendantIterator(ContainerNode& root, FirstChildTag);
41     ElementAndTextDescendantIterator(ContainerNode& root, Node* current);
42
43     ElementAndTextDescendantIterator& operator++() { return traverseNext(); }
44
45     Node& operator*();
46     Node* operator->();
47     const Node& operator*() const;
48     const Node* operator->() const;
49
50     bool operator==(const ElementAndTextDescendantIterator& other) const;
51     bool operator!=(const ElementAndTextDescendantIterator& other) const;
52
53     bool operator!() const { return !m_current; }
54     explicit operator bool() const { return m_current; }
55
56     void dropAssertions();
57
58     ElementAndTextDescendantIterator& traverseNext();
59     ElementAndTextDescendantIterator& traverseNextSkippingChildren();
60     ElementAndTextDescendantIterator& traverseNextSibling();
61     ElementAndTextDescendantIterator& traversePreviousSibling();
62
63     unsigned depth() const { return m_depth; }
64
65 private:
66     static bool isElementOrText(const Node& node) { return is<Element>(node) || is<Text>(node); }
67     static Node* firstChild(Node&);
68     static Node* nextSibling(Node&);
69     static Node* previousSibling(Node&);
70
71     void popAncestorSiblingStack();
72
73     Node* m_current;
74     struct AncestorSibling {
75         Node* node;
76         unsigned depth;
77     };
78     Vector<AncestorSibling, 16> m_ancestorSiblingStack;
79     unsigned m_depth { 0 };
80
81 #if !ASSERT_DISABLED
82     ElementIteratorAssertions m_assertions;
83 #endif
84 };
85
86 class ElementAndTextDescendantIteratorAdapter {
87 public:
88     explicit ElementAndTextDescendantIteratorAdapter(ContainerNode& root);
89     ElementAndTextDescendantIterator begin();
90     ElementAndTextDescendantIterator end();
91
92 private:
93     ContainerNode& m_root;
94 };
95
96 ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode&);
97
98 // ElementAndTextDescendantIterator
99
100 inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator()
101     : m_current(nullptr)
102 {
103 }
104
105 inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator(ContainerNode& root, FirstChildTag)
106     : m_current(firstChild(root))
107 #if !ASSERT_DISABLED
108     , m_assertions(m_current)
109 #endif
110 {
111     if (!m_current)
112         return;
113     m_ancestorSiblingStack.uncheckedAppend({ nullptr, 0 });
114     m_depth = 1;
115 }
116
117 inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator(ContainerNode& root, Node* current)
118     : m_current(current != &root ? current : nullptr)
119 #if !ASSERT_DISABLED
120     , m_assertions(m_current)
121 #endif
122 {
123     if (!m_current)
124         return;
125     ASSERT(isElementOrText(*m_current));
126
127     Vector<Node*, 20> ancestorStack;
128     auto* ancestor = m_current->parentNode();
129     while (ancestor != &root) {
130         ancestorStack.append(ancestor);
131         ancestor = ancestor->parentNode();
132     }
133
134     m_ancestorSiblingStack.uncheckedAppend({ nullptr, 0 });
135     for (unsigned i = ancestorStack.size(); i; --i) {
136         if (auto* sibling = nextSibling(*ancestorStack[i - 1]))
137             m_ancestorSiblingStack.append({ sibling, i });
138     }
139
140     m_depth = ancestorStack.size() + 1;
141 }
142
143 inline void ElementAndTextDescendantIterator::dropAssertions()
144 {
145 #if !ASSERT_DISABLED
146     m_assertions.clear();
147 #endif
148 }
149
150 inline Node* ElementAndTextDescendantIterator::firstChild(Node& current)
151 {
152     auto* node = current.firstChild();
153     while (node && !isElementOrText(*node))
154         node = node->nextSibling();
155     return node;
156 }
157
158 inline Node* ElementAndTextDescendantIterator::nextSibling(Node& current)
159 {
160     auto* node = current.nextSibling();
161     while (node && !isElementOrText(*node))
162         node = node->nextSibling();
163     return node;
164 }
165
166 inline Node* ElementAndTextDescendantIterator::previousSibling(Node& current)
167 {
168     auto* node = current.previousSibling();
169     while (node && !isElementOrText(*node))
170         node = node->previousSibling();
171     return node;
172 }
173
174 inline void ElementAndTextDescendantIterator::popAncestorSiblingStack()
175 {
176     m_current = m_ancestorSiblingStack.last().node;
177     m_depth = m_ancestorSiblingStack.last().depth;
178     m_ancestorSiblingStack.removeLast();
179
180 #if !ASSERT_DISABLED
181     // Drop the assertion when the iterator reaches the end.
182     if (!m_current)
183         m_assertions.dropEventDispatchAssertion();
184 #endif
185 }
186
187 inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNext()
188 {
189     ASSERT(m_current);
190     ASSERT(!m_assertions.domTreeHasMutated());
191
192     auto* firstChild = ElementAndTextDescendantIterator::firstChild(*m_current);
193     auto* nextSibling = ElementAndTextDescendantIterator::nextSibling(*m_current);
194     if (firstChild) {
195         if (nextSibling)
196             m_ancestorSiblingStack.append({ nextSibling, m_depth });
197         ++m_depth;
198         m_current = firstChild;
199         return *this;
200     }
201     if (!nextSibling) {
202         popAncestorSiblingStack();
203         return *this;
204     }
205
206     m_current = nextSibling;
207     return *this;
208 }
209
210 inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNextSkippingChildren()
211 {
212     ASSERT(m_current);
213     ASSERT(!m_assertions.domTreeHasMutated());
214
215     auto* nextSibling = ElementAndTextDescendantIterator::nextSibling(*m_current);
216     if (!nextSibling) {
217         popAncestorSiblingStack();
218         return *this;
219     }
220
221     m_current = nextSibling;
222     return *this;
223 }
224
225 inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNextSibling()
226 {
227     ASSERT(m_current);
228     ASSERT(!m_assertions.domTreeHasMutated());
229
230     m_current = nextSibling(*m_current);
231
232 #if !ASSERT_DISABLED
233     if (!m_current)
234         m_assertions.dropEventDispatchAssertion();
235 #endif
236     return *this;
237 }
238
239 inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traversePreviousSibling()
240 {
241     ASSERT(m_current);
242     ASSERT(!m_assertions.domTreeHasMutated());
243
244     m_current = previousSibling(*m_current);
245
246 #if !ASSERT_DISABLED
247     if (!m_current)
248         m_assertions.dropEventDispatchAssertion();
249 #endif
250     return *this;
251 }
252
253 inline Node& ElementAndTextDescendantIterator::operator*()
254 {
255     ASSERT(m_current);
256     ASSERT(isElementOrText(*m_current));
257     ASSERT(!m_assertions.domTreeHasMutated());
258     return *m_current;
259 }
260
261 inline Node* ElementAndTextDescendantIterator::operator->()
262 {
263     ASSERT(m_current);
264     ASSERT(isElementOrText(*m_current));
265     ASSERT(!m_assertions.domTreeHasMutated());
266     return m_current;
267 }
268
269 inline const Node& ElementAndTextDescendantIterator::operator*() const
270 {
271     ASSERT(m_current);
272     ASSERT(isElementOrText(*m_current));
273     ASSERT(!m_assertions.domTreeHasMutated());
274     return *m_current;
275 }
276
277 inline const Node* ElementAndTextDescendantIterator::operator->() const
278 {
279     ASSERT(m_current);
280     ASSERT(isElementOrText(*m_current));
281     ASSERT(!m_assertions.domTreeHasMutated());
282     return m_current;
283 }
284
285 inline bool ElementAndTextDescendantIterator::operator==(const ElementAndTextDescendantIterator& other) const
286 {
287     ASSERT(!m_assertions.domTreeHasMutated());
288     return m_current == other.m_current;
289 }
290
291 inline bool ElementAndTextDescendantIterator::operator!=(const ElementAndTextDescendantIterator& other) const
292 {
293     return !(*this == other);
294 }
295
296 // ElementAndTextDescendantIteratorAdapter
297
298 inline ElementAndTextDescendantIteratorAdapter::ElementAndTextDescendantIteratorAdapter(ContainerNode& root)
299     : m_root(root)
300 {
301 }
302
303 inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::begin()
304 {
305     return ElementAndTextDescendantIterator(m_root, ElementAndTextDescendantIterator::FirstChild);
306 }
307
308 inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::end()
309 {
310     return { };
311 }
312
313 // Standalone functions
314
315 inline ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode& root)
316 {
317     return ElementAndTextDescendantIteratorAdapter(root);
318 }
319
320 }
321 #endif