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