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