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