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
32namespace WebCore {
33
34template <CollectionTraversalType traversalType>
35struct CollectionTraversal { };
36
37template <>
38struct 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
56template <typename CollectionClass>
57inline 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
71template <typename CollectionClass>
72inline 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
86template <typename CollectionClass>
87inline 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
100template <typename CollectionClass>
101inline 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
114template <>
115struct 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
133template <typename CollectionClass>
134inline 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
148template <typename CollectionClass>
149inline 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
164template <typename CollectionClass>
165inline 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
178template <typename CollectionClass>
179inline 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
192template <>
193struct 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
211template <typename CollectionClass>
212inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::begin(const CollectionClass& collection, ContainerNode&)
213{
214 return collection.customElementAfter(nullptr);
215}
216
217template <typename CollectionClass>
218inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::last(const CollectionClass&, ContainerNode&)
219{
220 ASSERT_NOT_REACHED();
221 return nullptr;
222}
223
224template <typename CollectionClass>
225inline 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
238template <typename CollectionClass>
239inline 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