blob: 48e3b1a618d2fe0a28767b3731f2fadf973efbce [file] [log] [blame]
/*
* Copyright (C) 2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#pragma once
#include "Element.h"
#include "ElementIteratorAssertions.h"
#include "Text.h"
#include <wtf/Vector.h>
namespace WebCore {
class ElementAndTextDescendantIterator {
public:
ElementAndTextDescendantIterator();
enum FirstChildTag { FirstChild };
ElementAndTextDescendantIterator(ContainerNode& root, FirstChildTag);
ElementAndTextDescendantIterator(ContainerNode& root, Node* current);
ElementAndTextDescendantIterator& operator++() { return traverseNext(); }
Node& operator*();
Node* operator->();
const Node& operator*() const;
const Node* operator->() const;
bool operator==(const ElementAndTextDescendantIterator& other) const;
bool operator!=(const ElementAndTextDescendantIterator& other) const;
bool operator!() const { return !m_depth; }
explicit operator bool() const { return m_depth; }
void dropAssertions();
ElementAndTextDescendantIterator& traverseNext();
ElementAndTextDescendantIterator& traverseNextSkippingChildren();
ElementAndTextDescendantIterator& traverseNextSibling();
ElementAndTextDescendantIterator& traversePreviousSibling();
unsigned depth() const { return m_depth; }
private:
static bool isElementOrText(const Node& node) { return is<Element>(node) || is<Text>(node); }
static Node* firstChild(Node&);
static Node* nextSibling(Node&);
static Node* previousSibling(Node&);
void popAncestorSiblingStack();
Node* m_current;
struct AncestorSibling {
Node* node;
unsigned depth;
};
Vector<AncestorSibling, 16> m_ancestorSiblingStack;
unsigned m_depth { 0 };
#if ASSERT_ENABLED
ElementIteratorAssertions m_assertions;
#endif
};
class ElementAndTextDescendantIteratorAdapter {
public:
explicit ElementAndTextDescendantIteratorAdapter(ContainerNode& root);
ElementAndTextDescendantIterator begin();
ElementAndTextDescendantIterator end();
private:
ContainerNode& m_root;
};
ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode&);
// ElementAndTextDescendantIterator
inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator()
: m_current(nullptr)
{
}
inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator(ContainerNode& root, FirstChildTag)
: m_current(firstChild(root))
#if ASSERT_ENABLED
, m_assertions(m_current)
#endif
{
if (!m_current)
return;
m_ancestorSiblingStack.uncheckedAppend({ nullptr, 0 });
m_depth = 1;
}
inline ElementAndTextDescendantIterator::ElementAndTextDescendantIterator(ContainerNode& root, Node* current)
: m_current(current)
#if ASSERT_ENABLED
, m_assertions(m_current)
#endif
{
if (!m_current)
return;
ASSERT(isElementOrText(*m_current));
if (m_current == &root)
return;
Vector<Node*, 20> ancestorStack;
auto* ancestor = m_current->parentNode();
while (ancestor != &root) {
ancestorStack.append(ancestor);
ancestor = ancestor->parentNode();
}
m_ancestorSiblingStack.uncheckedAppend({ nullptr, 0 });
for (unsigned i = ancestorStack.size(); i; --i) {
if (auto* sibling = nextSibling(*ancestorStack[i - 1]))
m_ancestorSiblingStack.append({ sibling, i });
}
m_depth = ancestorStack.size() + 1;
}
inline void ElementAndTextDescendantIterator::dropAssertions()
{
#if ASSERT_ENABLED
m_assertions.clear();
#endif
}
inline Node* ElementAndTextDescendantIterator::firstChild(Node& current)
{
auto* node = current.firstChild();
while (node && !isElementOrText(*node))
node = node->nextSibling();
return node;
}
inline Node* ElementAndTextDescendantIterator::nextSibling(Node& current)
{
auto* node = current.nextSibling();
while (node && !isElementOrText(*node))
node = node->nextSibling();
return node;
}
inline Node* ElementAndTextDescendantIterator::previousSibling(Node& current)
{
auto* node = current.previousSibling();
while (node && !isElementOrText(*node))
node = node->previousSibling();
return node;
}
inline void ElementAndTextDescendantIterator::popAncestorSiblingStack()
{
m_current = m_ancestorSiblingStack.last().node;
m_depth = m_ancestorSiblingStack.last().depth;
m_ancestorSiblingStack.removeLast();
#if ASSERT_ENABLED
// Drop the assertion when the iterator reaches the end.
if (!m_current)
m_assertions.dropEventDispatchAssertion();
#endif
}
inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNext()
{
ASSERT(m_current);
ASSERT(!m_assertions.domTreeHasMutated());
auto* firstChild = ElementAndTextDescendantIterator::firstChild(*m_current);
auto* nextSibling = ElementAndTextDescendantIterator::nextSibling(*m_current);
if (firstChild) {
if (nextSibling)
m_ancestorSiblingStack.append({ nextSibling, m_depth });
++m_depth;
m_current = firstChild;
return *this;
}
if (!nextSibling) {
popAncestorSiblingStack();
return *this;
}
m_current = nextSibling;
return *this;
}
inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNextSkippingChildren()
{
ASSERT(m_current);
ASSERT(!m_assertions.domTreeHasMutated());
auto* nextSibling = ElementAndTextDescendantIterator::nextSibling(*m_current);
if (!nextSibling) {
popAncestorSiblingStack();
return *this;
}
m_current = nextSibling;
return *this;
}
inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traverseNextSibling()
{
ASSERT(m_current);
ASSERT(!m_assertions.domTreeHasMutated());
m_current = nextSibling(*m_current);
#if ASSERT_ENABLED
if (!m_current)
m_assertions.dropEventDispatchAssertion();
#endif
return *this;
}
inline ElementAndTextDescendantIterator& ElementAndTextDescendantIterator::traversePreviousSibling()
{
ASSERT(m_current);
ASSERT(!m_assertions.domTreeHasMutated());
m_current = previousSibling(*m_current);
#if ASSERT_ENABLED
if (!m_current)
m_assertions.dropEventDispatchAssertion();
#endif
return *this;
}
inline Node& ElementAndTextDescendantIterator::operator*()
{
ASSERT(m_current);
ASSERT(isElementOrText(*m_current));
ASSERT(!m_assertions.domTreeHasMutated());
return *m_current;
}
inline Node* ElementAndTextDescendantIterator::operator->()
{
ASSERT(m_current);
ASSERT(isElementOrText(*m_current));
ASSERT(!m_assertions.domTreeHasMutated());
return m_current;
}
inline const Node& ElementAndTextDescendantIterator::operator*() const
{
ASSERT(m_current);
ASSERT(isElementOrText(*m_current));
ASSERT(!m_assertions.domTreeHasMutated());
return *m_current;
}
inline const Node* ElementAndTextDescendantIterator::operator->() const
{
ASSERT(m_current);
ASSERT(isElementOrText(*m_current));
ASSERT(!m_assertions.domTreeHasMutated());
return m_current;
}
inline bool ElementAndTextDescendantIterator::operator==(const ElementAndTextDescendantIterator& other) const
{
ASSERT(!m_assertions.domTreeHasMutated());
return m_current == other.m_current || (!m_depth && !other.m_depth);
}
inline bool ElementAndTextDescendantIterator::operator!=(const ElementAndTextDescendantIterator& other) const
{
return !(*this == other);
}
// ElementAndTextDescendantIteratorAdapter
inline ElementAndTextDescendantIteratorAdapter::ElementAndTextDescendantIteratorAdapter(ContainerNode& root)
: m_root(root)
{
}
inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::begin()
{
return ElementAndTextDescendantIterator(m_root, ElementAndTextDescendantIterator::FirstChild);
}
inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::end()
{
return { };
}
// Standalone functions
inline ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode& root)
{
return ElementAndTextDescendantIteratorAdapter(root);
}
} // namespace WebCore