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