1/*
2 * Copyright (C) 2014 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 "ElementTraversal.h"
31#include <wtf/Vector.h>
32
33namespace WebCore {
34
35class ElementDescendantIterator {
36public:
37 ElementDescendantIterator();
38 explicit ElementDescendantIterator(Element* current);
39
40 ElementDescendantIterator& operator++();
41 ElementDescendantIterator& operator--();
42
43 Element& operator*();
44 Element* operator->();
45
46 bool operator==(const ElementDescendantIterator& other) const;
47 bool operator!=(const ElementDescendantIterator& other) const;
48
49 void dropAssertions();
50
51private:
52 Element* m_current;
53 Vector<Element*, 16> m_ancestorSiblingStack;
54
55#if !ASSERT_DISABLED
56 ElementIteratorAssertions m_assertions;
57#endif
58};
59
60class ElementDescendantConstIterator {
61public:
62 ElementDescendantConstIterator();
63 explicit ElementDescendantConstIterator(const Element*);
64
65 ElementDescendantConstIterator& operator++();
66
67 const Element& operator*() const;
68 const Element* operator->() const;
69
70 bool operator==(const ElementDescendantConstIterator& other) const;
71 bool operator!=(const ElementDescendantConstIterator& other) const;
72
73 void dropAssertions();
74
75private:
76 const Element* m_current;
77 Vector<Element*, 16> m_ancestorSiblingStack;
78
79#if !ASSERT_DISABLED
80 ElementIteratorAssertions m_assertions;
81#endif
82};
83
84class ElementDescendantIteratorAdapter {
85public:
86 ElementDescendantIteratorAdapter(ContainerNode& root);
87 ElementDescendantIterator begin();
88 ElementDescendantIterator end();
89 ElementDescendantIterator last();
90
91private:
92 ContainerNode& m_root;
93};
94
95class ElementDescendantConstIteratorAdapter {
96public:
97 ElementDescendantConstIteratorAdapter(const ContainerNode& root);
98 ElementDescendantConstIterator begin() const;
99 ElementDescendantConstIterator end() const;
100 ElementDescendantConstIterator last() const;
101
102private:
103 const ContainerNode& m_root;
104};
105
106ElementDescendantIteratorAdapter elementDescendants(ContainerNode&);
107ElementDescendantConstIteratorAdapter elementDescendants(const ContainerNode&);
108
109// ElementDescendantIterator
110
111inline ElementDescendantIterator::ElementDescendantIterator()
112 : m_current(nullptr)
113{
114}
115
116inline ElementDescendantIterator::ElementDescendantIterator(Element* current)
117 : m_current(current)
118#if !ASSERT_DISABLED
119 , m_assertions(current)
120#endif
121{
122 m_ancestorSiblingStack.uncheckedAppend(nullptr);
123}
124
125inline void ElementDescendantIterator::dropAssertions()
126{
127#if !ASSERT_DISABLED
128 m_assertions.clear();
129#endif
130}
131
132ALWAYS_INLINE ElementDescendantIterator& ElementDescendantIterator::operator++()
133{
134 ASSERT(m_current);
135 ASSERT(!m_assertions.domTreeHasMutated());
136
137 Element* firstChild = ElementTraversal::firstChild(*m_current);
138 Element* nextSibling = ElementTraversal::nextSibling(*m_current);
139
140 if (firstChild) {
141 if (nextSibling)
142 m_ancestorSiblingStack.append(nextSibling);
143 m_current = firstChild;
144 return *this;
145 }
146
147 if (nextSibling) {
148 m_current = nextSibling;
149 return *this;
150 }
151
152 m_current = m_ancestorSiblingStack.takeLast();
153
154#if !ASSERT_DISABLED
155 // Drop the assertion when the iterator reaches the end.
156 if (!m_current)
157 m_assertions.dropEventDispatchAssertion();
158#endif
159
160 return *this;
161}
162
163ALWAYS_INLINE ElementDescendantIterator& ElementDescendantIterator::operator--()
164{
165 ASSERT(m_current);
166 ASSERT(!m_assertions.domTreeHasMutated());
167
168 Element* previousSibling = ElementTraversal::previousSibling(*m_current);
169
170 if (!previousSibling) {
171 m_current = m_current->parentElement();
172 // The stack optimizes for forward traversal only, this just maintains consistency.
173 if (m_current->nextSibling() && m_current->nextSibling() == m_ancestorSiblingStack.last())
174 m_ancestorSiblingStack.removeLast();
175 return *this;
176 }
177
178 Element* deepestSibling = previousSibling;
179 while (Element* lastChild = ElementTraversal::lastChild(*deepestSibling))
180 deepestSibling = lastChild;
181 ASSERT(deepestSibling);
182
183 if (deepestSibling != previousSibling)
184 m_ancestorSiblingStack.append(m_current);
185
186 m_current = deepestSibling;
187
188#if !ASSERT_DISABLED
189 // Drop the assertion when the iterator reaches the end.
190 if (!m_current)
191 m_assertions.dropEventDispatchAssertion();
192#endif
193
194 return *this;
195}
196
197inline Element& ElementDescendantIterator::operator*()
198{
199 ASSERT(m_current);
200 ASSERT(!m_assertions.domTreeHasMutated());
201 return *m_current;
202}
203
204inline Element* ElementDescendantIterator::operator->()
205{
206 ASSERT(m_current);
207 ASSERT(!m_assertions.domTreeHasMutated());
208 return m_current;
209}
210
211inline bool ElementDescendantIterator::operator==(const ElementDescendantIterator& other) const
212{
213 ASSERT(!m_assertions.domTreeHasMutated());
214 return m_current == other.m_current;
215}
216
217inline bool ElementDescendantIterator::operator!=(const ElementDescendantIterator& other) const
218{
219 return !(*this == other);
220}
221
222// ElementDescendantConstIterator
223
224inline ElementDescendantConstIterator::ElementDescendantConstIterator()
225 : m_current(nullptr)
226{
227}
228
229inline ElementDescendantConstIterator::ElementDescendantConstIterator(const Element* current)
230 : m_current(current)
231#if !ASSERT_DISABLED
232 , m_assertions(current)
233#endif
234{
235 m_ancestorSiblingStack.uncheckedAppend(nullptr);
236}
237
238inline void ElementDescendantConstIterator::dropAssertions()
239{
240#if !ASSERT_DISABLED
241 m_assertions.clear();
242#endif
243}
244
245ALWAYS_INLINE ElementDescendantConstIterator& ElementDescendantConstIterator::operator++()
246{
247 ASSERT(m_current);
248 ASSERT(!m_assertions.domTreeHasMutated());
249
250 Element* firstChild = ElementTraversal::firstChild(*m_current);
251 Element* nextSibling = ElementTraversal::nextSibling(*m_current);
252
253 if (firstChild) {
254 if (nextSibling)
255 m_ancestorSiblingStack.append(nextSibling);
256 m_current = firstChild;
257 return *this;
258 }
259
260 if (nextSibling) {
261 m_current = nextSibling;
262 return *this;
263 }
264
265 m_current = m_ancestorSiblingStack.takeLast();
266
267#if !ASSERT_DISABLED
268 // Drop the assertion when the iterator reaches the end.
269 if (!m_current)
270 m_assertions.dropEventDispatchAssertion();
271#endif
272
273 return *this;
274}
275
276inline const Element& ElementDescendantConstIterator::operator*() const
277{
278 ASSERT(m_current);
279 ASSERT(!m_assertions.domTreeHasMutated());
280 return *m_current;
281}
282
283inline const Element* ElementDescendantConstIterator::operator->() const
284{
285 ASSERT(m_current);
286 ASSERT(!m_assertions.domTreeHasMutated());
287 return m_current;
288}
289
290inline bool ElementDescendantConstIterator::operator==(const ElementDescendantConstIterator& other) const
291{
292 ASSERT(!m_assertions.domTreeHasMutated());
293 return m_current == other.m_current;
294}
295
296inline bool ElementDescendantConstIterator::operator!=(const ElementDescendantConstIterator& other) const
297{
298 return !(*this == other);
299}
300
301// ElementDescendantIteratorAdapter
302
303inline ElementDescendantIteratorAdapter::ElementDescendantIteratorAdapter(ContainerNode& root)
304 : m_root(root)
305{
306}
307
308inline ElementDescendantIterator ElementDescendantIteratorAdapter::begin()
309{
310 return ElementDescendantIterator(ElementTraversal::firstChild(m_root));
311}
312
313inline ElementDescendantIterator ElementDescendantIteratorAdapter::end()
314{
315 return ElementDescendantIterator();
316}
317
318inline ElementDescendantIterator ElementDescendantIteratorAdapter::last()
319{
320 return ElementDescendantIterator(ElementTraversal::lastWithin(m_root));
321}
322
323// ElementDescendantConstIteratorAdapter
324
325inline ElementDescendantConstIteratorAdapter::ElementDescendantConstIteratorAdapter(const ContainerNode& root)
326 : m_root(root)
327{
328}
329
330inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::begin() const
331{
332 return ElementDescendantConstIterator(ElementTraversal::firstChild(m_root));
333}
334
335inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::end() const
336{
337 return ElementDescendantConstIterator();
338}
339
340inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::last() const
341{
342 return ElementDescendantConstIterator(ElementTraversal::lastWithin(m_root));
343}
344
345// Standalone functions
346
347inline ElementDescendantIteratorAdapter elementDescendants(ContainerNode& root)
348{
349 return ElementDescendantIteratorAdapter(root);
350}
351
352inline ElementDescendantConstIteratorAdapter elementDescendants(const ContainerNode& root)
353{
354 return ElementDescendantConstIteratorAdapter(root);
355}
356
357} // namespace WebCore
358
359namespace std {
360template <> struct iterator_traits<WebCore::ElementDescendantIterator> {
361 typedef WebCore::Element value_type;
362};
363template <> struct iterator_traits<WebCore::ElementDescendantConstIterator> {
364 typedef const WebCore::Element value_type;
365};
366}
367