1 | /* |
2 | * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``AS IS'' |
14 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
15 | * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS |
17 | * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
18 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
19 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
20 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
21 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
22 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
23 | * THE POSSIBILITY OF SUCH DAMAGE. |
24 | */ |
25 | |
26 | #pragma once |
27 | |
28 | #include "CollectionType.h" |
29 | #include "ElementChildIterator.h" |
30 | #include "ElementDescendantIterator.h" |
31 | |
32 | namespace WebCore { |
33 | |
34 | template <CollectionTraversalType traversalType> |
35 | struct CollectionTraversal { }; |
36 | |
37 | template <> |
38 | struct CollectionTraversal<CollectionTraversalType::Descendants> { |
39 | using Iterator = ElementDescendantIterator; |
40 | |
41 | static ElementDescendantIterator end(ContainerNode&) { return ElementDescendantIterator(); } |
42 | |
43 | template <typename CollectionClass> |
44 | static ElementDescendantIterator begin(const CollectionClass&, ContainerNode& rootNode); |
45 | |
46 | template <typename CollectionClass> |
47 | static ElementDescendantIterator last(const CollectionClass&, ContainerNode& rootNode); |
48 | |
49 | template <typename CollectionClass> |
50 | static void traverseForward(const CollectionClass&, ElementDescendantIterator& current, unsigned count, unsigned& traversedCount); |
51 | |
52 | template <typename CollectionClass> |
53 | static void traverseBackward(const CollectionClass&, ElementDescendantIterator& current, unsigned count); |
54 | }; |
55 | |
56 | template <typename CollectionClass> |
57 | inline ElementDescendantIterator CollectionTraversal<CollectionTraversalType::Descendants>::begin(const CollectionClass& collection, ContainerNode& rootNode) |
58 | { |
59 | auto descendants = elementDescendants(rootNode); |
60 | auto end = descendants.end(); |
61 | for (auto it = descendants.begin(); it != end; ++it) { |
62 | if (collection.elementMatches(*it)) { |
63 | // Drop iterator assertions because HTMLCollections / NodeList use a fine-grained invalidation scheme. |
64 | it.dropAssertions(); |
65 | return it; |
66 | } |
67 | } |
68 | return end; |
69 | } |
70 | |
71 | template <typename CollectionClass> |
72 | inline ElementDescendantIterator CollectionTraversal<CollectionTraversalType::Descendants>::last(const CollectionClass& collection, ContainerNode& rootNode) |
73 | { |
74 | auto descendants = elementDescendants(rootNode); |
75 | ElementDescendantIterator invalid; |
76 | for (auto it = descendants.last(); it != invalid; --it) { |
77 | if (collection.elementMatches(*it)) { |
78 | // Drop iterator assertions because HTMLCollections / NodeList use a fine-grained invalidation scheme. |
79 | it.dropAssertions(); |
80 | return it; |
81 | } |
82 | } |
83 | return invalid; |
84 | } |
85 | |
86 | template <typename CollectionClass> |
87 | inline void CollectionTraversal<CollectionTraversalType::Descendants>::traverseForward(const CollectionClass& collection, ElementDescendantIterator& current, unsigned count, unsigned& traversedCount) |
88 | { |
89 | ASSERT(collection.elementMatches(*current)); |
90 | ElementDescendantIterator invalid; |
91 | for (traversedCount = 0; traversedCount < count; ++traversedCount) { |
92 | do { |
93 | ++current; |
94 | if (current == invalid) |
95 | return; |
96 | } while (!collection.elementMatches(*current)); |
97 | } |
98 | } |
99 | |
100 | template <typename CollectionClass> |
101 | inline void CollectionTraversal<CollectionTraversalType::Descendants>::traverseBackward(const CollectionClass& collection, ElementDescendantIterator& current, unsigned count) |
102 | { |
103 | ASSERT(collection.elementMatches(*current)); |
104 | ElementDescendantIterator invalid; |
105 | for (; count; --count) { |
106 | do { |
107 | --current; |
108 | if (current == invalid) |
109 | return; |
110 | } while (!collection.elementMatches(*current)); |
111 | } |
112 | } |
113 | |
114 | template <> |
115 | struct CollectionTraversal<CollectionTraversalType::ChildrenOnly> { |
116 | using Iterator = ElementChildIterator<Element>; |
117 | |
118 | static ElementChildIterator<Element> end(ContainerNode& rootNode) { return ElementChildIterator<Element>(rootNode); } |
119 | |
120 | template <typename CollectionClass> |
121 | static ElementChildIterator<Element> begin(const CollectionClass&, ContainerNode& rootNode); |
122 | |
123 | template <typename CollectionClass> |
124 | static ElementChildIterator<Element> last(const CollectionClass&, ContainerNode& rootNode); |
125 | |
126 | template <typename CollectionClass> |
127 | static void traverseForward(const CollectionClass&, ElementChildIterator<Element>& current, unsigned count, unsigned& traversedCount); |
128 | |
129 | template <typename CollectionClass> |
130 | static void traverseBackward(const CollectionClass&, ElementChildIterator<Element>& current, unsigned count); |
131 | }; |
132 | |
133 | template <typename CollectionClass> |
134 | inline ElementChildIterator<Element> CollectionTraversal<CollectionTraversalType::ChildrenOnly>::begin(const CollectionClass& collection, ContainerNode& rootNode) |
135 | { |
136 | auto children = childrenOfType<Element>(rootNode); |
137 | auto end = children.end(); |
138 | for (auto it = children.begin(); it != end; ++it) { |
139 | if (collection.elementMatches(*it)) { |
140 | // Drop iterator assertions because HTMLCollections / NodeList use a fine-grained invalidation scheme. |
141 | it.dropAssertions(); |
142 | return it; |
143 | } |
144 | } |
145 | return end; |
146 | } |
147 | |
148 | template <typename CollectionClass> |
149 | inline ElementChildIterator<Element> CollectionTraversal<CollectionTraversalType::ChildrenOnly>::last(const CollectionClass& collection, ContainerNode& rootNode) |
150 | { |
151 | auto children = childrenOfType<Element>(rootNode); |
152 | ElementChildIterator<Element> invalid(collection.rootNode()); |
153 | ElementChildIterator<Element> last(rootNode, children.last()); |
154 | for (auto it = last; it != invalid; --it) { |
155 | if (collection.elementMatches(*it)) { |
156 | // Drop iterator assertions because HTMLCollections / NodeList use a fine-grained invalidation scheme. |
157 | it.dropAssertions(); |
158 | return it; |
159 | } |
160 | } |
161 | return invalid; |
162 | } |
163 | |
164 | template <typename CollectionClass> |
165 | inline void CollectionTraversal<CollectionTraversalType::ChildrenOnly>::traverseForward(const CollectionClass& collection, ElementChildIterator<Element>& current, unsigned count, unsigned& traversedCount) |
166 | { |
167 | ASSERT(collection.elementMatches(*current)); |
168 | ElementChildIterator<Element> invalid(collection.rootNode()); |
169 | for (traversedCount = 0; traversedCount < count; ++traversedCount) { |
170 | do { |
171 | ++current; |
172 | if (current == invalid) |
173 | return; |
174 | } while (!collection.elementMatches(*current)); |
175 | } |
176 | } |
177 | |
178 | template <typename CollectionClass> |
179 | inline void CollectionTraversal<CollectionTraversalType::ChildrenOnly>::traverseBackward(const CollectionClass& collection, ElementChildIterator<Element>& current, unsigned count) |
180 | { |
181 | ASSERT(collection.elementMatches(*current)); |
182 | ElementChildIterator<Element> invalid(collection.rootNode()); |
183 | for (; count; --count) { |
184 | do { |
185 | --current; |
186 | if (current == invalid) |
187 | return; |
188 | } while (!collection.elementMatches(*current)); |
189 | } |
190 | } |
191 | |
192 | template <> |
193 | struct CollectionTraversal<CollectionTraversalType::CustomForwardOnly> { |
194 | using Iterator = Element*; |
195 | |
196 | static Element* end(ContainerNode&) { return nullptr; } |
197 | |
198 | template <typename CollectionClass> |
199 | static Element* begin(const CollectionClass&, ContainerNode&); |
200 | |
201 | template <typename CollectionClass> |
202 | static Element* last(const CollectionClass&, ContainerNode&); |
203 | |
204 | template <typename CollectionClass> |
205 | static void traverseForward(const CollectionClass&, Element*& current, unsigned count, unsigned& traversedCount); |
206 | |
207 | template <typename CollectionClass> |
208 | static void traverseBackward(const CollectionClass&, Element*&, unsigned count); |
209 | }; |
210 | |
211 | template <typename CollectionClass> |
212 | inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::begin(const CollectionClass& collection, ContainerNode&) |
213 | { |
214 | return collection.customElementAfter(nullptr); |
215 | } |
216 | |
217 | template <typename CollectionClass> |
218 | inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::last(const CollectionClass&, ContainerNode&) |
219 | { |
220 | ASSERT_NOT_REACHED(); |
221 | return nullptr; |
222 | } |
223 | |
224 | template <typename CollectionClass> |
225 | inline void CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::traverseForward(const CollectionClass& collection, Element*& current, unsigned count, unsigned& traversedCount) |
226 | { |
227 | Element* element = current; |
228 | for (traversedCount = 0; traversedCount < count; ++traversedCount) { |
229 | element = collection.customElementAfter(element); |
230 | if (!element) { |
231 | current = nullptr; |
232 | return; |
233 | } |
234 | } |
235 | current = element; |
236 | } |
237 | |
238 | template <typename CollectionClass> |
239 | inline void CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::traverseBackward(const CollectionClass&, Element*&, unsigned count) |
240 | { |
241 | UNUSED_PARAM(count); |
242 | ASSERT_NOT_REACHED(); |
243 | } |
244 | |
245 | } // namespace WebCore |
246 | |