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 | |
33 | namespace WebCore { |
34 | |
35 | class ElementAndTextDescendantIterator { |
36 | public: |
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 | |
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, 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 | |
116 | inline 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 | |
144 | inline void ElementAndTextDescendantIterator::dropAssertions() |
145 | { |
146 | #if !ASSERT_DISABLED |
147 | m_assertions.clear(); |
148 | #endif |
149 | } |
150 | |
151 | inline 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 | |
159 | inline 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 | |
167 | inline 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 | |
175 | inline 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 | |
188 | inline 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 | |
211 | inline 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 | |
226 | inline 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 | |
240 | inline 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 | |
254 | inline Node& ElementAndTextDescendantIterator::operator*() |
255 | { |
256 | ASSERT(m_current); |
257 | ASSERT(isElementOrText(*m_current)); |
258 | ASSERT(!m_assertions.domTreeHasMutated()); |
259 | return *m_current; |
260 | } |
261 | |
262 | inline Node* ElementAndTextDescendantIterator::operator->() |
263 | { |
264 | ASSERT(m_current); |
265 | ASSERT(isElementOrText(*m_current)); |
266 | ASSERT(!m_assertions.domTreeHasMutated()); |
267 | return m_current; |
268 | } |
269 | |
270 | inline 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 | |
278 | inline 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 | |
286 | inline 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 | |
292 | inline bool ElementAndTextDescendantIterator::operator!=(const ElementAndTextDescendantIterator& other) const |
293 | { |
294 | return !(*this == other); |
295 | } |
296 | |
297 | // ElementAndTextDescendantIteratorAdapter |
298 | |
299 | inline ElementAndTextDescendantIteratorAdapter::ElementAndTextDescendantIteratorAdapter(ContainerNode& root) |
300 | : m_root(root) |
301 | { |
302 | } |
303 | |
304 | inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::begin() |
305 | { |
306 | return ElementAndTextDescendantIterator(m_root, ElementAndTextDescendantIterator::FirstChild); |
307 | } |
308 | |
309 | inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::end() |
310 | { |
311 | return { }; |
312 | } |
313 | |
314 | // Standalone functions |
315 | |
316 | inline ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode& root) |
317 | { |
318 | return ElementAndTextDescendantIteratorAdapter(root); |
319 | } |
320 | |
321 | } // namespace WebCore |
322 | |