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 | |
33 | namespace WebCore { |
34 | |
35 | class ElementDescendantIterator { |
36 | public: |
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 | |
51 | private: |
52 | Element* m_current; |
53 | Vector<Element*, 16> m_ancestorSiblingStack; |
54 | |
55 | #if !ASSERT_DISABLED |
56 | ElementIteratorAssertions m_assertions; |
57 | #endif |
58 | }; |
59 | |
60 | class ElementDescendantConstIterator { |
61 | public: |
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 | |
75 | private: |
76 | const Element* m_current; |
77 | Vector<Element*, 16> m_ancestorSiblingStack; |
78 | |
79 | #if !ASSERT_DISABLED |
80 | ElementIteratorAssertions m_assertions; |
81 | #endif |
82 | }; |
83 | |
84 | class ElementDescendantIteratorAdapter { |
85 | public: |
86 | ElementDescendantIteratorAdapter(ContainerNode& root); |
87 | ElementDescendantIterator begin(); |
88 | ElementDescendantIterator end(); |
89 | ElementDescendantIterator last(); |
90 | |
91 | private: |
92 | ContainerNode& m_root; |
93 | }; |
94 | |
95 | class ElementDescendantConstIteratorAdapter { |
96 | public: |
97 | ElementDescendantConstIteratorAdapter(const ContainerNode& root); |
98 | ElementDescendantConstIterator begin() const; |
99 | ElementDescendantConstIterator end() const; |
100 | ElementDescendantConstIterator last() const; |
101 | |
102 | private: |
103 | const ContainerNode& m_root; |
104 | }; |
105 | |
106 | ElementDescendantIteratorAdapter elementDescendants(ContainerNode&); |
107 | ElementDescendantConstIteratorAdapter elementDescendants(const ContainerNode&); |
108 | |
109 | // ElementDescendantIterator |
110 | |
111 | inline ElementDescendantIterator::ElementDescendantIterator() |
112 | : m_current(nullptr) |
113 | { |
114 | } |
115 | |
116 | inline 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 | |
125 | inline void ElementDescendantIterator::dropAssertions() |
126 | { |
127 | #if !ASSERT_DISABLED |
128 | m_assertions.clear(); |
129 | #endif |
130 | } |
131 | |
132 | ALWAYS_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 | |
163 | ALWAYS_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 | |
197 | inline Element& ElementDescendantIterator::operator*() |
198 | { |
199 | ASSERT(m_current); |
200 | ASSERT(!m_assertions.domTreeHasMutated()); |
201 | return *m_current; |
202 | } |
203 | |
204 | inline Element* ElementDescendantIterator::operator->() |
205 | { |
206 | ASSERT(m_current); |
207 | ASSERT(!m_assertions.domTreeHasMutated()); |
208 | return m_current; |
209 | } |
210 | |
211 | inline bool ElementDescendantIterator::operator==(const ElementDescendantIterator& other) const |
212 | { |
213 | ASSERT(!m_assertions.domTreeHasMutated()); |
214 | return m_current == other.m_current; |
215 | } |
216 | |
217 | inline bool ElementDescendantIterator::operator!=(const ElementDescendantIterator& other) const |
218 | { |
219 | return !(*this == other); |
220 | } |
221 | |
222 | // ElementDescendantConstIterator |
223 | |
224 | inline ElementDescendantConstIterator::ElementDescendantConstIterator() |
225 | : m_current(nullptr) |
226 | { |
227 | } |
228 | |
229 | inline 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 | |
238 | inline void ElementDescendantConstIterator::dropAssertions() |
239 | { |
240 | #if !ASSERT_DISABLED |
241 | m_assertions.clear(); |
242 | #endif |
243 | } |
244 | |
245 | ALWAYS_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 | |
276 | inline const Element& ElementDescendantConstIterator::operator*() const |
277 | { |
278 | ASSERT(m_current); |
279 | ASSERT(!m_assertions.domTreeHasMutated()); |
280 | return *m_current; |
281 | } |
282 | |
283 | inline const Element* ElementDescendantConstIterator::operator->() const |
284 | { |
285 | ASSERT(m_current); |
286 | ASSERT(!m_assertions.domTreeHasMutated()); |
287 | return m_current; |
288 | } |
289 | |
290 | inline bool ElementDescendantConstIterator::operator==(const ElementDescendantConstIterator& other) const |
291 | { |
292 | ASSERT(!m_assertions.domTreeHasMutated()); |
293 | return m_current == other.m_current; |
294 | } |
295 | |
296 | inline bool ElementDescendantConstIterator::operator!=(const ElementDescendantConstIterator& other) const |
297 | { |
298 | return !(*this == other); |
299 | } |
300 | |
301 | // ElementDescendantIteratorAdapter |
302 | |
303 | inline ElementDescendantIteratorAdapter::ElementDescendantIteratorAdapter(ContainerNode& root) |
304 | : m_root(root) |
305 | { |
306 | } |
307 | |
308 | inline ElementDescendantIterator ElementDescendantIteratorAdapter::begin() |
309 | { |
310 | return ElementDescendantIterator(ElementTraversal::firstChild(m_root)); |
311 | } |
312 | |
313 | inline ElementDescendantIterator ElementDescendantIteratorAdapter::end() |
314 | { |
315 | return ElementDescendantIterator(); |
316 | } |
317 | |
318 | inline ElementDescendantIterator ElementDescendantIteratorAdapter::last() |
319 | { |
320 | return ElementDescendantIterator(ElementTraversal::lastWithin(m_root)); |
321 | } |
322 | |
323 | // ElementDescendantConstIteratorAdapter |
324 | |
325 | inline ElementDescendantConstIteratorAdapter::ElementDescendantConstIteratorAdapter(const ContainerNode& root) |
326 | : m_root(root) |
327 | { |
328 | } |
329 | |
330 | inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::begin() const |
331 | { |
332 | return ElementDescendantConstIterator(ElementTraversal::firstChild(m_root)); |
333 | } |
334 | |
335 | inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::end() const |
336 | { |
337 | return ElementDescendantConstIterator(); |
338 | } |
339 | |
340 | inline ElementDescendantConstIterator ElementDescendantConstIteratorAdapter::last() const |
341 | { |
342 | return ElementDescendantConstIterator(ElementTraversal::lastWithin(m_root)); |
343 | } |
344 | |
345 | // Standalone functions |
346 | |
347 | inline ElementDescendantIteratorAdapter elementDescendants(ContainerNode& root) |
348 | { |
349 | return ElementDescendantIteratorAdapter(root); |
350 | } |
351 | |
352 | inline ElementDescendantConstIteratorAdapter elementDescendants(const ContainerNode& root) |
353 | { |
354 | return ElementDescendantConstIteratorAdapter(root); |
355 | } |
356 | |
357 | } // namespace WebCore |
358 | |
359 | namespace std { |
360 | template <> struct iterator_traits<WebCore::ElementDescendantIterator> { |
361 | typedef WebCore::Element value_type; |
362 | }; |
363 | template <> struct iterator_traits<WebCore::ElementDescendantConstIterator> { |
364 | typedef const WebCore::Element value_type; |
365 | }; |
366 | } |
367 | |