Diff
Modified: trunk/Source/WebCore/ChangeLog (196280 => 196281)
--- trunk/Source/WebCore/ChangeLog 2016-02-09 01:06:23 UTC (rev 196280)
+++ trunk/Source/WebCore/ChangeLog 2016-02-09 01:15:52 UTC (rev 196281)
@@ -1,3 +1,63 @@
+2016-02-08 Antti Koivisto <an...@apple.com>
+
+ Implement ComposedTreeIterator in terms of ElementAndTextDescendantIterator
+ https://bugs.webkit.org/show_bug.cgi?id=154003
+
+ Reviewed by Darin Adler.
+
+ Currently ComposedTreeIterator implements tree traversal using NodeTraversal. This makes it overly complicated.
+ It can also return nodes other than Element and Text which should not be part of the composed tree.
+
+ This patch adds a new iterator type, ElementAndTextDescendantIterator, similar to the existing ElementDescendantIterator.
+ ComposedTreeIterator is then implemented using this new iterator.
+
+ When entering a shadow tree or a slot the local iterator is pushed along with the context stack and a new local
+ iterator is initialized for the new context. When leaving a shadow tree the context stack is popped and the previous
+ local iterator becomes active.
+
+ * WebCore.xcodeproj/project.pbxproj:
+ * dom/ComposedTreeIterator.cpp:
+ (WebCore::ComposedTreeIterator::ComposedTreeIterator):
+ (WebCore::ComposedTreeIterator::initializeContextStack):
+ (WebCore::ComposedTreeIterator::pushContext):
+ (WebCore::ComposedTreeIterator::traverseNextInShadowTree):
+ (WebCore::ComposedTreeIterator::traverseNextLeavingContext):
+ (WebCore::ComposedTreeIterator::advanceInSlot):
+ (WebCore::ComposedTreeIterator::traverseSiblingInSlot):
+ (WebCore::ComposedTreeIterator::initializeShadowStack): Deleted.
+ (WebCore::ComposedTreeIterator::traverseParentInShadowTree): Deleted.
+ (WebCore::ComposedTreeIterator::traverseNextSiblingSlot): Deleted.
+ (WebCore::ComposedTreeIterator::traversePreviousSiblingSlot): Deleted.
+ * dom/ComposedTreeIterator.h:
+ (WebCore::ComposedTreeIterator::operator*):
+ (WebCore::ComposedTreeIterator::operator->):
+ (WebCore::ComposedTreeIterator::operator==):
+ (WebCore::ComposedTreeIterator::operator!=):
+ (WebCore::ComposedTreeIterator::operator++):
+ (WebCore::ComposedTreeIterator::Context::Context):
+ (WebCore::ComposedTreeIterator::context):
+ (WebCore::ComposedTreeIterator::current):
+ (WebCore::ComposedTreeIterator::ComposedTreeIterator):
+ (WebCore::ComposedTreeIterator::traverseNext):
+ (WebCore::ComposedTreeIterator::traverseNextSkippingChildren):
+ (WebCore::ComposedTreeIterator::traverseNextSibling):
+ (WebCore::ComposedTreeIterator::traversePreviousSibling):
+ (WebCore::ComposedTreeDescendantAdapter::ComposedTreeDescendantAdapter):
+ (WebCore::ComposedTreeDescendantAdapter::begin):
+ (WebCore::ComposedTreeDescendantAdapter::end):
+ (WebCore::ComposedTreeDescendantAdapter::at):
+ (WebCore::ComposedTreeChildAdapter::Iterator::Iterator):
+ (WebCore::ComposedTreeChildAdapter::ComposedTreeChildAdapter):
+ (WebCore::ComposedTreeChildAdapter::begin):
+ (WebCore::ComposedTreeChildAdapter::end):
+ (WebCore::ComposedTreeChildAdapter::at):
+ (WebCore::ComposedTreeIterator::ShadowContext::ShadowContext): Deleted.
+ (WebCore::ComposedTreeIterator::traverseParent): Deleted.
+ * dom/ElementAndTextDescendantIterator.h: Added.
+
+ New iterator type that traverses Element and Text nodes (that is renderable nodes only).
+ It also tracks depth for future use.
+
2016-02-08 Joseph Pecoraro <pecor...@apple.com>
Web Inspector: copy({x:1}) should copy "{x:1}", not "[object Object]"
Modified: trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj (196280 => 196281)
--- trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2016-02-09 01:06:23 UTC (rev 196280)
+++ trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj 2016-02-09 01:15:52 UTC (rev 196281)
@@ -6530,6 +6530,7 @@
E43A023D17EB3713004CDD25 /* RenderElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E43A023C17EB3713004CDD25 /* RenderElement.cpp */; };
E43AF8E61AC5B7E800CA717E /* CacheValidation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E43AF8E41AC5B7DD00CA717E /* CacheValidation.cpp */; };
E43AF8E71AC5B7EC00CA717E /* CacheValidation.h in Headers */ = {isa = PBXBuildFile; fileRef = E43AF8E51AC5B7DD00CA717E /* CacheValidation.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ E440AA961C68420800A265CC /* ElementAndTextDescendantIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = E440AA951C68420800A265CC /* ElementAndTextDescendantIterator.h */; };
E44613A10CD6331000FADA75 /* HTMLAudioElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E446138F0CD6331000FADA75 /* HTMLAudioElement.cpp */; };
E44613A20CD6331000FADA75 /* HTMLAudioElement.h in Headers */ = {isa = PBXBuildFile; fileRef = E44613900CD6331000FADA75 /* HTMLAudioElement.h */; };
E44613A40CD6331000FADA75 /* HTMLMediaElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E44613920CD6331000FADA75 /* HTMLMediaElement.cpp */; };
@@ -14508,6 +14509,7 @@
E43A023C17EB3713004CDD25 /* RenderElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderElement.cpp; sourceTree = "<group>"; };
E43AF8E41AC5B7DD00CA717E /* CacheValidation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CacheValidation.cpp; sourceTree = "<group>"; };
E43AF8E51AC5B7DD00CA717E /* CacheValidation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CacheValidation.h; sourceTree = "<group>"; };
+ E440AA951C68420800A265CC /* ElementAndTextDescendantIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ElementAndTextDescendantIterator.h; sourceTree = "<group>"; };
E446138F0CD6331000FADA75 /* HTMLAudioElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLAudioElement.cpp; sourceTree = "<group>"; };
E44613900CD6331000FADA75 /* HTMLAudioElement.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = HTMLAudioElement.h; sourceTree = "<group>"; };
E44613910CD6331000FADA75 /* HTMLAudioElement.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = HTMLAudioElement.idl; sourceTree = "<group>"; };
@@ -24091,6 +24093,7 @@
A8C4A7F509D563270003AC8D /* Element.h */,
93EEC1EA09C2877700C515D1 /* Element.idl */,
E4AE7C1917D232350009FB31 /* ElementAncestorIterator.h */,
+ E440AA951C68420800A265CC /* ElementAndTextDescendantIterator.h */,
E46A2B1D17CA76B1000DBCD8 /* ElementChildIterator.h */,
B5B7A16F17C1080600E4AA0A /* ElementData.cpp */,
B5B7A16E17C1048000E4AA0A /* ElementData.h */,
@@ -25850,6 +25853,7 @@
93309E0E099E64920056E581 /* FrameSelection.h in Headers */,
C4CD629B18383766007EBAF1 /* FrameSnapshotting.h in Headers */,
65A21485097A3F5300B9050A /* FrameTree.h in Headers */,
+ E440AA961C68420800A265CC /* ElementAndTextDescendantIterator.h in Headers */,
65CBFEFA0974F607001DAC25 /* FrameView.h in Headers */,
97205AB0123928CA00B17380 /* FTPDirectoryDocument.h in Headers */,
51C81B8A0C4422F70019ECE3 /* FTPDirectoryParser.h in Headers */,
Modified: trunk/Source/WebCore/dom/ComposedTreeIterator.cpp (196280 => 196281)
--- trunk/Source/WebCore/dom/ComposedTreeIterator.cpp 2016-02-09 01:06:23 UTC (rev 196280)
+++ trunk/Source/WebCore/dom/ComposedTreeIterator.cpp 2016-02-09 01:15:52 UTC (rev 196281)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-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
@@ -30,163 +30,153 @@
namespace WebCore {
-void ComposedTreeIterator::initializeShadowStack()
+ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root)
{
+ ASSERT(!is<ShadowRoot>(root));
+
+#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
+ if (is<HTMLSlotElement>(root)) {
+ auto& slot = downcast<HTMLSlotElement>(root);
+ if (auto* assignedNodes = slot.assignedNodes()) {
+ initializeContextStack(root, *assignedNodes->at(0));
+ return;
+ }
+ }
+#endif
+ auto& effectiveRoot = root.shadowRoot() ? *root.shadowRoot() : root;
+ m_contextStack.uncheckedAppend(Context(effectiveRoot));
+}
+
+ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current)
+{
+ ASSERT(!is<ShadowRoot>(root));
+ ASSERT(!is<ShadowRoot>(current));
+
+ bool mayNeedShadowStack = root.shadowRoot() || (¤t != &root && current.parentNode() != &root);
+ if (mayNeedShadowStack)
+ initializeContextStack(root, current);
+ else
+ m_contextStack.uncheckedAppend(Context(root, current));
+}
+
+void ComposedTreeIterator::initializeContextStack(ContainerNode& root, Node& current)
+{
// This code sets up the iterator for arbitrary node/root pair. It is not needed in common cases
// or completes fast because node and root are close (like in composedTreeChildren(*parent).at(node) case).
- auto* node = m_current;
- while (node != &m_root) {
+ auto* node = ¤t;
+ auto* contextCurrent = node;
+ size_t currentSlotNodeIndex = notFound;
+ while (node != &root) {
auto* parent = node->parentNode();
if (!parent) {
- m_current = nullptr;
+ *this = { };
return;
}
if (is<ShadowRoot>(*parent)) {
auto& shadowRoot = downcast<ShadowRoot>(*parent);
- if (m_shadowStack.isEmpty() || m_shadowStack.last().host != shadowRoot.host())
- m_shadowStack.append(shadowRoot.host());
+ m_contextStack.append(Context(shadowRoot, *contextCurrent, currentSlotNodeIndex));
node = shadowRoot.host();
+ contextCurrent = node;
+ currentSlotNodeIndex = notFound;
continue;
}
if (auto* shadowRoot = parent->shadowRoot()) {
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- m_shadowStack.append(shadowRoot->host());
+ m_contextStack.append(Context(*parent, *contextCurrent, currentSlotNodeIndex));
auto* assignedSlot = shadowRoot->findAssignedSlot(*node);
if (assignedSlot) {
- size_t index = assignedSlot->assignedNodes()->find(node);
- ASSERT(index != notFound);
-
- m_shadowStack.last().currentSlot = assignedSlot;
- m_shadowStack.last().currentSlotNodeIndex = index;
+ currentSlotNodeIndex = assignedSlot->assignedNodes()->find(node);
+ ASSERT(currentSlotNodeIndex != notFound);
node = assignedSlot;
+ contextCurrent = assignedSlot;
continue;
}
// The node is not part of the composed tree.
#else
UNUSED_PARAM(shadowRoot);
- m_current = nullptr;
- return;
#endif
+ *this = { };
+ return;
}
node = parent;
}
- m_shadowStack.reverse();
+ m_contextStack.append(Context(root, *contextCurrent, currentSlotNodeIndex));
+
+ m_contextStack.reverse();
}
+bool ComposedTreeIterator::pushContext(ShadowRoot& shadowRoot)
+{
+ Context shadowContext(shadowRoot);
+ if (!shadowContext.iterator)
+ return false;
+ m_contextStack.append(WTFMove(shadowContext));
+ return true;
+}
+
void ComposedTreeIterator::traverseNextInShadowTree()
{
- ASSERT(!m_shadowStack.isEmpty());
+ ASSERT(m_contextStack.size() > 1);
- auto* shadowContext = &m_shadowStack.last();
-
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- if (is<HTMLSlotElement>(*m_current) && !shadowContext->currentSlot) {
- auto& slot = downcast<HTMLSlotElement>(*m_current);
+ if (is<HTMLSlotElement>(current())) {
+ auto& slot = downcast<HTMLSlotElement>(current());
if (auto* assignedNodes = slot.assignedNodes()) {
- shadowContext->currentSlot = &slot;
- shadowContext->currentSlotNodeIndex = 0;
- m_current = assignedNodes->at(0);
+ context().slotNodeIndex = 0;
+ auto* assignedNode = assignedNodes->at(0);
+ m_contextStack.append(Context(*assignedNode->parentElement(), *assignedNode));
return;
}
}
#endif
- m_current = NodeTraversal::next(*m_current, shadowContext->host);
+ context().iterator.traverseNext();
- while (!m_current) {
-#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- if (auto* slot = shadowContext->currentSlot) {
- bool nextNodeInSameSlot = ++shadowContext->currentSlotNodeIndex < slot->assignedNodes()->size();
- if (nextNodeInSameSlot) {
- m_current = slot->assignedNodes()->at(shadowContext->currentSlotNodeIndex);
- return;
- }
- m_current = NodeTraversal::nextSkippingChildren(*slot, shadowContext->host);
- shadowContext->currentSlot = nullptr;
- continue;
- }
-#endif
- auto& previousHost = *shadowContext->host;
- m_shadowStack.removeLast();
-
- if (m_shadowStack.isEmpty()) {
- m_current = NodeTraversal::nextSkippingChildren(previousHost, &m_root);
- return;
- }
- shadowContext = &m_shadowStack.last();
- m_current = NodeTraversal::nextSkippingChildren(previousHost, shadowContext->host);
- }
+ if (!context().iterator)
+ traverseNextLeavingContext();
}
-void ComposedTreeIterator::traverseParentInShadowTree()
+void ComposedTreeIterator::traverseNextLeavingContext()
{
- ASSERT(!m_shadowStack.isEmpty());
+ ASSERT(m_contextStack.size() > 1);
- auto& shadowContext = m_shadowStack.last();
-
- auto* parent = m_current->parentNode();
- if (is<ShadowRoot>(parent)) {
- ASSERT(shadowContext.host == downcast<ShadowRoot>(*parent).host());
-
- m_current = shadowContext.host;
- m_shadowStack.removeLast();
- return;
- }
- if (parent->shadowRoot()) {
+ while (!context().iterator && m_contextStack.size() > 1) {
+ m_contextStack.removeLast();
+ if (!context().iterator)
+ return;
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- ASSERT(shadowContext.host == parent);
-
- auto* slot = shadowContext.currentSlot;
- ASSERT(slot->assignedNodes()->at(shadowContext.currentSlotNodeIndex) == m_current);
-
- m_current = slot;
- shadowContext.currentSlot = nullptr;
- return;
-#else
- m_current = nullptr;
- return;
+ if (is<HTMLSlotElement>(current()) && advanceInSlot(1))
+ return;
#endif
+ context().iterator.traverseNextSkippingChildren();
}
- m_current = parent;
}
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
-void ComposedTreeIterator::traverseNextSiblingSlot()
+bool ComposedTreeIterator::advanceInSlot(int direction)
{
- ASSERT(m_current->parentNode()->shadowRoot());
- ASSERT(!m_shadowStack.isEmpty());
- ASSERT(m_shadowStack.last().host == m_current->parentNode());
+ ASSERT(context().slotNodeIndex != notFound);
- auto& shadowContext = m_shadowStack.last();
+ auto& assignedNodes = *downcast<HTMLSlotElement>(current()).assignedNodes();
+ // It is fine to underflow this.
+ context().slotNodeIndex += direction;
+ if (context().slotNodeIndex >= assignedNodes.size())
+ return false;
- if (!shadowContext.currentSlot) {
- m_current = nullptr;
- return;
- }
- auto* slotNodes = shadowContext.currentSlot->assignedNodes();
- ASSERT(slotNodes->at(shadowContext.currentSlotNodeIndex) == m_current);
-
- bool nextNodeInSameSlot = ++shadowContext.currentSlotNodeIndex < slotNodes->size();
- m_current = nextNodeInSameSlot ? slotNodes->at(shadowContext.currentSlotNodeIndex) : nullptr;
+ auto* slotNode = assignedNodes.at(context().slotNodeIndex);
+ m_contextStack.append(Context(*slotNode->parentElement(), *slotNode));
+ return true;
}
-void ComposedTreeIterator::traversePreviousSiblingSlot()
+void ComposedTreeIterator::traverseSiblingInSlot(int direction)
{
- ASSERT(m_current->parentNode()->shadowRoot());
- ASSERT(!m_shadowStack.isEmpty());
- ASSERT(m_shadowStack.last().host == m_current->parentNode());
+ ASSERT(m_contextStack.size() > 1);
+ ASSERT(current().parentNode()->shadowRoot());
- auto& shadowContext = m_shadowStack.last();
+ m_contextStack.removeLast();
- if (!shadowContext.currentSlot) {
- m_current = nullptr;
- return;
- }
- auto* slotNodes = shadowContext.currentSlot->assignedNodes();
- ASSERT(slotNodes->at(shadowContext.currentSlotNodeIndex) == m_current);
-
- bool previousNodeInSameSlot = shadowContext.currentSlotNodeIndex > 0;
- m_current = previousNodeInSameSlot ? slotNodes->at(--shadowContext.currentSlotNodeIndex) : nullptr;
+ if (!advanceInSlot(direction))
+ *this = { };
}
#endif
Modified: trunk/Source/WebCore/dom/ComposedTreeIterator.h (196280 => 196281)
--- trunk/Source/WebCore/dom/ComposedTreeIterator.h 2016-02-09 01:06:23 UTC (rev 196280)
+++ trunk/Source/WebCore/dom/ComposedTreeIterator.h 2016-02-09 01:15:52 UTC (rev 196281)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-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
@@ -23,7 +23,7 @@
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#include "NodeTraversal.h"
+#include "ElementAndTextDescendantIterator.h"
#include "ShadowRoot.h"
#ifndef ComposedTreeIterator_h
@@ -35,115 +35,118 @@
class ComposedTreeIterator {
public:
+ ComposedTreeIterator();
ComposedTreeIterator(ContainerNode& root);
ComposedTreeIterator(ContainerNode& root, Node& current);
- Node& operator*() { return *m_current; }
- Node* operator->() { return m_current; }
+ Node& operator*() { return current(); }
+ Node* operator->() { return ¤t(); }
- bool operator==(const ComposedTreeIterator& other) const { return m_current == other.m_current; }
- bool operator!=(const ComposedTreeIterator& other) const { return m_current != other.m_current; }
+ bool operator==(const ComposedTreeIterator& other) const { return context().iterator == other.context().iterator; }
+ bool operator!=(const ComposedTreeIterator& other) const { return context().iterator != other.context().iterator; }
- ComposedTreeIterator& operator++() { return traverseNextSibling(); }
+ ComposedTreeIterator& operator++() { return traverseNext(); }
ComposedTreeIterator& traverseNext();
+ ComposedTreeIterator& traverseNextSkippingChildren();
ComposedTreeIterator& traverseNextSibling();
ComposedTreeIterator& traversePreviousSibling();
- ComposedTreeIterator& traverseParent();
+ unsigned depth() const;
+
private:
- void initializeShadowStack();
+ void initializeContextStack(ContainerNode& root, Node& current);
void traverseNextInShadowTree();
- void traverseParentInShadowTree();
+ void traverseNextLeavingContext();
+ bool pushContext(ShadowRoot&);
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- void traverseNextSiblingSlot();
- void traversePreviousSiblingSlot();
+ bool advanceInSlot(int direction);
+ void traverseSiblingInSlot(int direction);
#endif
- ContainerNode& m_root;
- Node* m_current { 0 };
-
- struct ShadowContext {
- ShadowContext(Element* host)
- : host(host)
+ struct Context {
+ Context() { }
+ explicit Context(ContainerNode& root)
+ : iterator(root)
{ }
+ Context(ContainerNode& root, Node& node, size_t slotNodeIndex = notFound)
+ : iterator(root, &node)
+ , slotNodeIndex(slotNodeIndex)
+ { }
- Element* host;
+ ElementAndTextDescendantIterator iterator;
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- HTMLSlotElement* currentSlot { nullptr };
- unsigned currentSlotNodeIndex { 0 };
+ size_t slotNodeIndex { notFound };
#endif
};
- Vector<ShadowContext, 4> m_shadowStack;
+ Context& context() { return m_contextStack.last(); }
+ const Context& context() const { return m_contextStack.last(); }
+ Node& current() { return *context().iterator; }
+
+ Vector<Context, 4> m_contextStack;
};
-inline ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root)
- : m_root(root)
+inline ComposedTreeIterator::ComposedTreeIterator()
+ : m_contextStack({ { } })
{
- ASSERT(!is<ShadowRoot>(m_root));
}
-inline ComposedTreeIterator::ComposedTreeIterator(ContainerNode& root, Node& current)
- : m_root(root)
- , m_current(¤t)
-{
- ASSERT(!is<ShadowRoot>(m_root));
- ASSERT(!is<ShadowRoot>(m_current));
-
- bool mayNeedShadowStack = m_root.shadowRoot() || (m_current != &m_root && current.parentNode() != &m_root);
- if (mayNeedShadowStack)
- initializeShadowStack();
-}
-
inline ComposedTreeIterator& ComposedTreeIterator::traverseNext()
{
- if (auto* shadowRoot = m_current->shadowRoot()) {
- m_shadowStack.append(shadowRoot->host());
- m_current = shadowRoot;
+ if (auto* shadowRoot = context().iterator->shadowRoot()) {
+ if (pushContext(*shadowRoot))
+ return *this;
}
- if (m_shadowStack.isEmpty())
- m_current = NodeTraversal::next(*m_current, &m_root);
- else
+ if (m_contextStack.size() > 1) {
traverseNextInShadowTree();
+ return *this;
+ }
+ context().iterator.traverseNext();
return *this;
}
+inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSkippingChildren()
+{
+ context().iterator.traverseNextSkippingChildren();
+
+ if (!context().iterator && m_contextStack.size() > 1)
+ traverseNextLeavingContext();
+
+ return *this;
+}
+
inline ComposedTreeIterator& ComposedTreeIterator::traverseNextSibling()
{
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- bool isAssignedToSlot = !m_shadowStack.isEmpty() && m_current->parentNode()->shadowRoot();
- if (isAssignedToSlot) {
- traverseNextSiblingSlot();
+ if (current().parentNode()->shadowRoot()) {
+ traverseSiblingInSlot(1);
return *this;
}
#endif
- m_current = m_current->nextSibling();
+ context().iterator.traverseNextSibling();
return *this;
}
inline ComposedTreeIterator& ComposedTreeIterator::traversePreviousSibling()
{
#if ENABLE(SHADOW_DOM) || ENABLE(DETAILS_ELEMENT)
- bool isAssignedToSlot = !m_shadowStack.isEmpty() && m_current->parentNode()->shadowRoot();
- if (isAssignedToSlot) {
- traversePreviousSiblingSlot();
+ if (current().parentNode()->shadowRoot()) {
+ traverseSiblingInSlot(-1);
return *this;
}
#endif
- m_current = m_current->previousSibling();
+ context().iterator.traversePreviousSibling();
return *this;
}
-inline ComposedTreeIterator& ComposedTreeIterator::traverseParent()
+inline unsigned ComposedTreeIterator::depth() const
{
- if (m_shadowStack.isEmpty())
- m_current = m_current->parentNode();
- else
- traverseParentInShadowTree();
-
- return *this;
+ unsigned depth = 0;
+ for (auto& context : m_contextStack)
+ depth += context.iterator.depth();
+ return depth;
}
class ComposedTreeDescendantAdapter {
@@ -152,8 +155,8 @@
: m_parent(parent)
{ }
- ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent, m_parent).traverseNext(); }
- ComposedTreeIterator end() { return ComposedTreeIterator(m_parent); }
+ ComposedTreeIterator begin() { return ComposedTreeIterator(m_parent); }
+ ComposedTreeIterator end() { return { }; }
ComposedTreeIterator at(const Node& child) { return ComposedTreeIterator(m_parent, const_cast<Node&>(child)); }
private:
@@ -164,7 +167,8 @@
public:
class Iterator : public ComposedTreeIterator {
public:
- Iterator(ContainerNode& root)
+ Iterator() = default;
+ explicit Iterator(ContainerNode& root)
: ComposedTreeIterator(root)
{ }
Iterator(ContainerNode& root, Node& current)
@@ -179,8 +183,8 @@
: m_parent(parent)
{ }
- Iterator begin() { return static_cast<Iterator&>(Iterator(m_parent, m_parent).traverseNext()); }
- Iterator end() { return Iterator(m_parent); }
+ Iterator begin() { return Iterator(m_parent); }
+ Iterator end() { return { }; }
Iterator at(const Node& child) { return Iterator(m_parent, const_cast<Node&>(child)); }
private:
Added: trunk/Source/WebCore/dom/ElementAndTextDescendantIterator.h (0 => 196281)
--- trunk/Source/WebCore/dom/ElementAndTextDescendantIterator.h (rev 0)
+++ trunk/Source/WebCore/dom/ElementAndTextDescendantIterator.h 2016-02-09 01:15:52 UTC (rev 196281)
@@ -0,0 +1,320 @@
+/*
+ * 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.
+ */
+
+#ifndef ElementAndTextDescendantIterator_h
+#define ElementAndTextDescendantIterator_h
+
+#include "Element.h"
+#include "ElementIteratorAssertions.h"
+#include "Text.h"
+#include <wtf/Vector.h>
+
+namespace WebCore {
+
+class ElementAndTextDescendantIterator {
+public:
+ ElementAndTextDescendantIterator();
+ explicit ElementAndTextDescendantIterator(ContainerNode& root);
+ 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_current; }
+ explicit operator bool() const { return m_current; }
+
+ 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_DISABLED
+ 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)
+ : m_current(firstChild(root))
+#if !ASSERT_DISABLED
+ , 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 != &root ? current : nullptr)
+#if !ASSERT_DISABLED
+ , m_assertions(m_current)
+#endif
+{
+ if (!m_current)
+ return;
+ ASSERT(isElementOrText(*m_current));
+
+ 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_DISABLED
+ 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_DISABLED
+ // 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_DISABLED
+ 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_DISABLED
+ 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;
+}
+
+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);
+}
+
+inline ElementAndTextDescendantIterator ElementAndTextDescendantIteratorAdapter::end()
+{
+ return { };
+}
+
+// Standalone functions
+
+inline ElementAndTextDescendantIteratorAdapter elementAndTextDescendants(ContainerNode& root)
+{
+ return ElementAndTextDescendantIteratorAdapter(root);
+}
+
+}
+#endif
Modified: trunk/Source/WebCore/dom/ElementIteratorAssertions.h (196280 => 196281)
--- trunk/Source/WebCore/dom/ElementIteratorAssertions.h 2016-02-09 01:06:23 UTC (rev 196280)
+++ trunk/Source/WebCore/dom/ElementIteratorAssertions.h 2016-02-09 01:15:52 UTC (rev 196281)
@@ -32,7 +32,7 @@
class ElementIteratorAssertions {
public:
- ElementIteratorAssertions(const Element* first = nullptr);
+ ElementIteratorAssertions(const Node* first = nullptr);
bool domTreeHasMutated() const;
void dropEventDispatchAssertion();
void clear();
@@ -45,7 +45,7 @@
// FIXME: No real point in doing these as inlines; they are for debugging and we usually turn off inlining in debug builds.
-inline ElementIteratorAssertions::ElementIteratorAssertions(const Element* first)
+inline ElementIteratorAssertions::ElementIteratorAssertions(const Node* first)
: m_document(first ? &first->document() : nullptr)
, m_initialDOMTreeVersion(first ? m_document->domTreeVersion() : 0)
{
