Remove some unnecessary branches from LiveNodeList traversal
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 27 Mar 2014 20:49:27 +0000 (20:49 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 27 Mar 2014 20:49:27 +0000 (20:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=130854

Reviewed by Andreas Kling.

Compile different traversal code paths for all NodeList subclasses.

* dom/ClassNodeList.cpp:
(WebCore::ClassNodeList::ClassNodeList):
(WebCore::ClassNodeList::~ClassNodeList):
(WebCore::ClassNodeList::nodeMatches): Deleted.
* dom/ClassNodeList.h:
(WebCore::ClassNodeList::nodeMatches):
(WebCore::ClassNodeList::nodeMatchesInlined): Deleted.

    Remove separate nodeMatchesInlined functions.
    We now rely on exact types and marking classes final.

* dom/LiveNodeList.cpp:
(WebCore::LiveNodeList::LiveNodeList):
(WebCore::LiveNodeList::~LiveNodeList):
(WebCore::LiveNodeList::namedItem):
(WebCore::LiveNodeList::rootNode): Deleted.
(WebCore::isMatchingElement): Deleted.
(WebCore::firstMatchingElement): Deleted.
(WebCore::lastMatchingElement): Deleted.
(WebCore::nextMatchingElement): Deleted.
(WebCore::previousMatchingElement): Deleted.
(WebCore::traverseMatchingElementsForward): Deleted.
(WebCore::traverseMatchingElementsBackward): Deleted.
(WebCore::LiveNodeList::collectionFirst): Deleted.
(WebCore::LiveNodeList::collectionLast): Deleted.
(WebCore::LiveNodeList::collectionTraverseForward): Deleted.
(WebCore::LiveNodeList::collectionTraverseBackward): Deleted.
(WebCore::LiveNodeList::length): Deleted.
(WebCore::LiveNodeList::item): Deleted.
(WebCore::LiveNodeList::memoryCost): Deleted.
(WebCore::LiveNodeList::invalidateCache): Deleted.
* dom/LiveNodeList.h:
(WebCore::LiveNodeList::invalidateCacheForAttribute):
(WebCore::CachedLiveNodeList::collectionCanTraverseBackward):
(WebCore::LiveNodeList::rootNode):
(WebCore::CachedLiveNodeList<NodeListType>::CachedLiveNodeList):

    Add CachedLiveNodeList<NodeListType> utility type that interfaces with CollectionIndexCache.
    It is the base class for all concrete LiveNodeLists.

(WebCore::CachedLiveNodeList<NodeListType>::~CachedLiveNodeList):
(WebCore::CachedLiveNodeList<NodeListType>::collectionFirst):
(WebCore::CachedLiveNodeList<NodeListType>::collectionLast):
(WebCore::nextMatchingElement):
(WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseForward):
(WebCore::previousMatchingElement):
(WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseBackward):
(WebCore::CachedLiveNodeList<NodeListType>::willValidateIndexCache):
(WebCore::CachedLiveNodeList<NodeListType>::invalidateCache):
(WebCore::CachedLiveNodeList<NodeListType>::length):
(WebCore::CachedLiveNodeList<NodeListType>::item):
(WebCore::CachedLiveNodeList<NodeListType>::memoryCost):

    Templated code moves to header.

(WebCore::LiveNodeList::LiveNodeList): Deleted.
(WebCore::LiveNodeList::~LiveNodeList): Deleted.
(WebCore::LiveNodeList::invalidateCache): Deleted.
(WebCore::LiveNodeList::collectionCanTraverseBackward): Deleted.
(WebCore::LiveNodeList::willValidateIndexCache): Deleted.
* dom/NameNodeList.cpp:
(WebCore::NameNodeList::NameNodeList):
* dom/NameNodeList.h:
* dom/Node.cpp:
(WebCore::Document::invalidateNodeListAndCollectionCaches):
(WebCore::NodeListsNodeData::invalidateCaches):
* dom/TagNodeList.cpp:
(WebCore::TagNodeList::TagNodeList):
(WebCore::HTMLTagNodeList::HTMLTagNodeList):
(WebCore::HTMLTagNodeList::~HTMLTagNodeList):
(WebCore::TagNodeList::nodeMatches): Deleted.
(WebCore::HTMLTagNodeList::nodeMatches): Deleted.
* dom/TagNodeList.h:
(WebCore::TagNodeList::nodeMatches):
(WebCore::HTMLTagNodeList::nodeMatches):
(WebCore::TagNodeList::create): Deleted.
(WebCore::HTMLTagNodeList::nodeMatchesInlined): Deleted.
* html/LabelsNodeList.cpp:
(WebCore::LabelsNodeList::LabelsNodeList):
* html/LabelsNodeList.h:
* html/RadioNodeList.cpp:
(WebCore::RadioNodeList::RadioNodeList):
* html/RadioNodeList.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@166369 268f45cc-cd09-0410-ab3c-d52691b4dbfc

14 files changed:
Source/WebCore/ChangeLog
Source/WebCore/dom/ClassNodeList.cpp
Source/WebCore/dom/ClassNodeList.h
Source/WebCore/dom/LiveNodeList.cpp
Source/WebCore/dom/LiveNodeList.h
Source/WebCore/dom/NameNodeList.cpp
Source/WebCore/dom/NameNodeList.h
Source/WebCore/dom/Node.cpp
Source/WebCore/dom/TagNodeList.cpp
Source/WebCore/dom/TagNodeList.h
Source/WebCore/html/LabelsNodeList.cpp
Source/WebCore/html/LabelsNodeList.h
Source/WebCore/html/RadioNodeList.cpp
Source/WebCore/html/RadioNodeList.h

index c0077110753a2b48926478d0c7e67322509e7172..886e94e5fff39bacc5a5a4d82c240869f6bdac66 100644 (file)
@@ -1,3 +1,96 @@
+2014-03-27  Antti Koivisto  <antti@apple.com>
+
+        Remove some unnecessary branches from LiveNodeList traversal
+        https://bugs.webkit.org/show_bug.cgi?id=130854
+
+        Reviewed by Andreas Kling.
+
+        Compile different traversal code paths for all NodeList subclasses.
+
+        * dom/ClassNodeList.cpp:
+        (WebCore::ClassNodeList::ClassNodeList):
+        (WebCore::ClassNodeList::~ClassNodeList):
+        (WebCore::ClassNodeList::nodeMatches): Deleted.
+        * dom/ClassNodeList.h:
+        (WebCore::ClassNodeList::nodeMatches):
+        (WebCore::ClassNodeList::nodeMatchesInlined): Deleted.
+        
+            Remove separate nodeMatchesInlined functions. 
+            We now rely on exact types and marking classes final.
+
+        * dom/LiveNodeList.cpp:
+        (WebCore::LiveNodeList::LiveNodeList):
+        (WebCore::LiveNodeList::~LiveNodeList):
+        (WebCore::LiveNodeList::namedItem):
+        (WebCore::LiveNodeList::rootNode): Deleted.
+        (WebCore::isMatchingElement): Deleted.
+        (WebCore::firstMatchingElement): Deleted.
+        (WebCore::lastMatchingElement): Deleted.
+        (WebCore::nextMatchingElement): Deleted.
+        (WebCore::previousMatchingElement): Deleted.
+        (WebCore::traverseMatchingElementsForward): Deleted.
+        (WebCore::traverseMatchingElementsBackward): Deleted.
+        (WebCore::LiveNodeList::collectionFirst): Deleted.
+        (WebCore::LiveNodeList::collectionLast): Deleted.
+        (WebCore::LiveNodeList::collectionTraverseForward): Deleted.
+        (WebCore::LiveNodeList::collectionTraverseBackward): Deleted.
+        (WebCore::LiveNodeList::length): Deleted.
+        (WebCore::LiveNodeList::item): Deleted.
+        (WebCore::LiveNodeList::memoryCost): Deleted.
+        (WebCore::LiveNodeList::invalidateCache): Deleted.
+        * dom/LiveNodeList.h:
+        (WebCore::LiveNodeList::invalidateCacheForAttribute):
+        (WebCore::CachedLiveNodeList::collectionCanTraverseBackward):
+        (WebCore::LiveNodeList::rootNode):
+        (WebCore::CachedLiveNodeList<NodeListType>::CachedLiveNodeList):
+        
+            Add CachedLiveNodeList<NodeListType> utility type that interfaces with CollectionIndexCache.
+            It is the base class for all concrete LiveNodeLists.
+
+        (WebCore::CachedLiveNodeList<NodeListType>::~CachedLiveNodeList):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionFirst):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionLast):
+        (WebCore::nextMatchingElement):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseForward):
+        (WebCore::previousMatchingElement):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseBackward):
+        (WebCore::CachedLiveNodeList<NodeListType>::willValidateIndexCache):
+        (WebCore::CachedLiveNodeList<NodeListType>::invalidateCache):
+        (WebCore::CachedLiveNodeList<NodeListType>::length):
+        (WebCore::CachedLiveNodeList<NodeListType>::item):
+        (WebCore::CachedLiveNodeList<NodeListType>::memoryCost):
+        
+            Templated code moves to header.
+
+        (WebCore::LiveNodeList::LiveNodeList): Deleted.
+        (WebCore::LiveNodeList::~LiveNodeList): Deleted.
+        (WebCore::LiveNodeList::invalidateCache): Deleted.
+        (WebCore::LiveNodeList::collectionCanTraverseBackward): Deleted.
+        (WebCore::LiveNodeList::willValidateIndexCache): Deleted.
+        * dom/NameNodeList.cpp:
+        (WebCore::NameNodeList::NameNodeList):
+        * dom/NameNodeList.h:
+        * dom/Node.cpp:
+        (WebCore::Document::invalidateNodeListAndCollectionCaches):
+        (WebCore::NodeListsNodeData::invalidateCaches):
+        * dom/TagNodeList.cpp:
+        (WebCore::TagNodeList::TagNodeList):
+        (WebCore::HTMLTagNodeList::HTMLTagNodeList):
+        (WebCore::HTMLTagNodeList::~HTMLTagNodeList):
+        (WebCore::TagNodeList::nodeMatches): Deleted.
+        (WebCore::HTMLTagNodeList::nodeMatches): Deleted.
+        * dom/TagNodeList.h:
+        (WebCore::TagNodeList::nodeMatches):
+        (WebCore::HTMLTagNodeList::nodeMatches):
+        (WebCore::TagNodeList::create): Deleted.
+        (WebCore::HTMLTagNodeList::nodeMatchesInlined): Deleted.
+        * html/LabelsNodeList.cpp:
+        (WebCore::LabelsNodeList::LabelsNodeList):
+        * html/LabelsNodeList.h:
+        * html/RadioNodeList.cpp:
+        (WebCore::RadioNodeList::RadioNodeList):
+        * html/RadioNodeList.h:
+
 2014-03-27  Adenilson Cavalcanti  <cavalcantii@gmail.com>
 
         Remove comment from Filter.h
 2014-03-27  Adenilson Cavalcanti  <cavalcantii@gmail.com>
 
         Remove comment from Filter.h
index f13d7d933347e488239ab3b68f40f58ed8d954a1..4a00aedb429e57d166dae38e6e8909974d2e21ac 100644 (file)
@@ -36,7 +36,7 @@
 namespace WebCore {
 
 ClassNodeList::ClassNodeList(ContainerNode& rootNode, const String& classNames)
 namespace WebCore {
 
 ClassNodeList::ClassNodeList(ContainerNode& rootNode, const String& classNames)
-    : LiveNodeList(rootNode, Type::ClassNodeListType, InvalidateOnClassAttrChange)
+    : CachedLiveNodeList(rootNode, Type::ClassNodeListType, InvalidateOnClassAttrChange)
     , m_classNames(classNames, document().inQuirksMode())
     , m_originalClassNames(classNames)
 {
     , m_classNames(classNames, document().inQuirksMode())
     , m_originalClassNames(classNames)
 {
@@ -45,11 +45,6 @@ ClassNodeList::ClassNodeList(ContainerNode& rootNode, const String& classNames)
 ClassNodeList::~ClassNodeList()
 {
     ownerNode().nodeLists()->removeCacheWithName(this, m_originalClassNames);
 ClassNodeList::~ClassNodeList()
 {
     ownerNode().nodeLists()->removeCacheWithName(this, m_originalClassNames);
-} 
-
-bool ClassNodeList::nodeMatches(Element* testNode) const
-{
-    return nodeMatchesInlined(testNode);
 }
 
 } // namespace WebCore
 }
 
 } // namespace WebCore
index cbb73e9a4712e13a39d04834713b38e6b671822a..5f18d5d98a9b9329f2f53c6935035a5d1f87a371 100644 (file)
@@ -37,7 +37,7 @@
 
 namespace WebCore {
 
 
 namespace WebCore {
 
-class ClassNodeList : public LiveNodeList {
+class ClassNodeList final : public CachedLiveNodeList<ClassNodeList> {
 public:
     static PassRefPtr<ClassNodeList> create(ContainerNode& rootNode, const String& classNames)
     {
 public:
     static PassRefPtr<ClassNodeList> create(ContainerNode& rootNode, const String& classNames)
     {
@@ -46,28 +46,26 @@ public:
 
     virtual ~ClassNodeList();
 
 
     virtual ~ClassNodeList();
 
-    bool nodeMatchesInlined(Element*) const;
+    virtual bool nodeMatches(Element*) const override;
 
 private:
     ClassNodeList(ContainerNode& rootNode, const String& classNames);
 
 
 private:
     ClassNodeList(ContainerNode& rootNode, const String& classNames);
 
-    virtual bool nodeMatches(Element*) const override;
-
     SpaceSplitString m_classNames;
     String m_originalClassNames;
 };
 
     SpaceSplitString m_classNames;
     String m_originalClassNames;
 };
 
-inline bool ClassNodeList::nodeMatchesInlined(Element* testNode) const
+inline bool ClassNodeList::nodeMatches(Element* element) const
 {
 {
-    if (!testNode->hasClass())
+    if (!element->hasClass())
         return false;
     if (!m_classNames.size())
         return false;
     // FIXME: DOM4 allows getElementsByClassName to return non StyledElement.
     // https://bugs.webkit.org/show_bug.cgi?id=94718
         return false;
     if (!m_classNames.size())
         return false;
     // FIXME: DOM4 allows getElementsByClassName to return non StyledElement.
     // https://bugs.webkit.org/show_bug.cgi?id=94718
-    if (!testNode->isStyledElement())
+    if (!element->isStyledElement())
         return false;
         return false;
-    return testNode->classNames().containsAll(m_classNames);
+    return element->classNames().containsAll(m_classNames);
 }
 
 } // namespace WebCore
 }
 
 } // namespace WebCore
index 17727aa4c47f443b2695aa2b29337dbd2d4477db..cf21a9729b9c7edda24375d36637c6913812a8ff 100644 (file)
 
 namespace WebCore {
 
 
 namespace WebCore {
 
-ContainerNode& LiveNodeList::rootNode() const
+LiveNodeList::LiveNodeList(ContainerNode& ownerNode, Type type, NodeListInvalidationType invalidationType, NodeListRootType rootType)
+    : m_ownerNode(ownerNode)
+    , m_rootType(rootType)
+    , m_invalidationType(invalidationType)
+    , m_type(static_cast<unsigned>(type))
 {
 {
-    if (isRootedAtDocument() && ownerNode().inDocument())
-        return ownerNode().document();
-
-    return ownerNode();
-}
-
-template <class NodeListType>
-inline bool isMatchingElement(const NodeListType*, Element*);
-
-template <> inline bool isMatchingElement(const LiveNodeList* nodeList, Element* element)
-{
-    return nodeList->nodeMatches(element);
-}
-
-template <> inline bool isMatchingElement(const HTMLTagNodeList* nodeList, Element* element)
-{
-    return nodeList->nodeMatchesInlined(element);
-}
-
-template <> inline bool isMatchingElement(const ClassNodeList* nodeList, Element* element)
-{
-    return nodeList->nodeMatchesInlined(element);
-}
-
-template <class NodeListType>
-inline Element* firstMatchingElement(const NodeListType* nodeList, ContainerNode& root)
-{
-    Element* element = ElementTraversal::firstWithin(&root);
-    while (element && !isMatchingElement(nodeList, element))
-        element = ElementTraversal::next(element, &root);
-    return element;
-}
-
-template <class NodeListType>
-inline Element* lastMatchingElement(const NodeListType* nodeList, ContainerNode& root)
-{
-    Element* element = ElementTraversal::lastWithin(&root);
-    while (element && !isMatchingElement(nodeList, element))
-        element = ElementTraversal::previous(element, &root);
-    return element;
-}
-
-template <class NodeListType>
-inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
-{
-    do {
-        current = ElementTraversal::next(current, &root);
-    } while (current && !isMatchingElement(nodeList, current));
-    return current;
-}
-
-template <class NodeListType>
-inline Element* previousMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
-{
-    do {
-        current = ElementTraversal::previous(current, &root);
-    } while (current && !isMatchingElement(nodeList, current));
-    return current;
-}
-
-template <class NodeListType>
-inline Element* traverseMatchingElementsForward(const NodeListType* nodeList, Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root)
-{
-    Element* element = &current;
-    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
-        element = nextMatchingElement(nodeList, element, root);
-        if (!element)
-            return nullptr;
-    }
-    return element;
-}
-
-template <class NodeListType>
-inline Element* traverseMatchingElementsBackward(const NodeListType* nodeList, Element& current, unsigned count, ContainerNode& root)
-{
-    Element* element = &current;
-    for (; count; --count) {
-        element = previousMatchingElement(nodeList, element, root);
-        if (!element)
-            return nullptr;
-    }
-    return element;
-}
-
-Element* LiveNodeList::collectionFirst() const
-{
-    auto& root = rootNode();
-    if (type() == Type::HTMLTagNodeListType)
-        return firstMatchingElement(static_cast<const HTMLTagNodeList*>(this), root);
-    if (type() == Type::ClassNodeListType)
-        return firstMatchingElement(static_cast<const ClassNodeList*>(this), root);
-    return firstMatchingElement(static_cast<const LiveNodeList*>(this), root);
-}
-
-Element* LiveNodeList::collectionLast() const
-{
-    auto& root = rootNode();
-    if (type() == Type::HTMLTagNodeListType)
-        return lastMatchingElement(static_cast<const HTMLTagNodeList*>(this), root);
-    if (type() == Type::ClassNodeListType)
-        return lastMatchingElement(static_cast<const ClassNodeList*>(this), root);
-    return lastMatchingElement(static_cast<const LiveNodeList*>(this), root);
-}
-
-Element* LiveNodeList::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
-{
-    auto& root = rootNode();
-    if (type() == Type::HTMLTagNodeListType)
-        return traverseMatchingElementsForward(static_cast<const HTMLTagNodeList*>(this), current, count, traversedCount, root);
-    if (type() == Type::ClassNodeListType)
-        return traverseMatchingElementsForward(static_cast<const ClassNodeList*>(this), current, count, traversedCount, root);
-    return traverseMatchingElementsForward(static_cast<const LiveNodeList*>(this), current, count, traversedCount, root);
-}
-
-Element* LiveNodeList::collectionTraverseBackward(Element& current, unsigned count) const
-{
-    auto& root = rootNode();
-    if (type() == Type::HTMLTagNodeListType)
-        return traverseMatchingElementsBackward(static_cast<const HTMLTagNodeList*>(this), current, count, root);
-    if (type() == Type::ClassNodeListType)
-        return traverseMatchingElementsBackward(static_cast<const ClassNodeList*>(this), current, count, root);
-    return traverseMatchingElementsBackward(static_cast<const LiveNodeList*>(this), current, count, root);
-}
-
-unsigned LiveNodeList::length() const
-{
-    return m_indexCache.nodeCount(*this);
+    ASSERT(m_rootType == static_cast<unsigned>(rootType));
+    ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
+    ASSERT(m_type == static_cast<unsigned>(type));
 }
 
 }
 
-Node* LiveNodeList::item(unsigned offset) const
+LiveNodeList::~LiveNodeList()
 {
 {
-    return m_indexCache.nodeAt(*this, offset);
 }
 
 }
 
-size_t LiveNodeList::memoryCost() const
-{
-    return m_indexCache.memoryCost();
-}
-
-void LiveNodeList::invalidateCache(Document& document) const
-{
-    if (!m_indexCache.hasValidCache())
-        return;
-    document.unregisterNodeList(const_cast<LiveNodeList&>(*this));
-    m_indexCache.invalidate();
-}
 
 Node* LiveNodeList::namedItem(const AtomicString& elementId) const
 {
 
 Node* LiveNodeList::namedItem(const AtomicString& elementId) const
 {
@@ -190,7 +57,7 @@ Node* LiveNodeList::namedItem(const AtomicString& elementId) const
         if (element && nodeMatches(element) && element->isDescendantOf(&rootNode))
             return element;
         if (!element)
         if (element && nodeMatches(element) && element->isDescendantOf(&rootNode))
             return element;
         if (!element)
-            return 0;
+            return nullptr;
         // In the case of multiple nodes with the same name, just fall through.
     }
 
         // In the case of multiple nodes with the same name, just fall through.
     }
 
@@ -205,7 +72,7 @@ Node* LiveNodeList::namedItem(const AtomicString& elementId) const
             return node;
     }
 
             return node;
     }
 
-    return 0;
+    return nullptr;
 }
 
 } // namespace WebCore
 }
 
 } // namespace WebCore
index 5e69e9a0d8606f9327092643504c3c9f68839cf5..630a371205f3b42c02b085ff91ed09a626b0200e 100644 (file)
@@ -27,6 +27,7 @@
 #include "CollectionIndexCache.h"
 #include "CollectionType.h"
 #include "Document.h"
 #include "CollectionIndexCache.h"
 #include "CollectionType.h"
 #include "Document.h"
+#include "ElementTraversal.h"
 #include "HTMLNames.h"
 #include "NodeList.h"
 #include <wtf/Forward.h>
 #include "HTMLNames.h"
 #include "NodeList.h"
 #include <wtf/Forward.h>
@@ -54,48 +55,22 @@ public:
         LabelsNodeListType,
     };
 
         LabelsNodeListType,
     };
 
-    LiveNodeList(ContainerNode& ownerNode, Type type, NodeListInvalidationType invalidationType, NodeListRootType rootType = NodeListIsRootedAtNode)
-        : m_ownerNode(ownerNode)
-        , m_rootType(rootType)
-        , m_invalidationType(invalidationType)
-        , m_type(static_cast<unsigned>(type))
-    {
-        ASSERT(m_rootType == static_cast<unsigned>(rootType));
-        ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
-        ASSERT(m_type == static_cast<unsigned>(type));
-    }
+    LiveNodeList(ContainerNode& ownerNode, Type, NodeListInvalidationType, NodeListRootType);
     virtual Node* namedItem(const AtomicString&) const override final;
     virtual bool nodeMatches(Element*) const = 0;
 
     virtual Node* namedItem(const AtomicString&) const override final;
     virtual bool nodeMatches(Element*) const = 0;
 
-    virtual ~LiveNodeList()
-    {
-        if (m_indexCache.hasValidCache())
-            document().unregisterNodeList(*this);
-    }
-
-    // DOM API
-    virtual unsigned length() const override final;
-    virtual Node* item(unsigned offset) const override final;
-    virtual size_t memoryCost() const override;
+    virtual ~LiveNodeList();
 
     ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootType == NodeListIsRootedAtDocument; }
     ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
     ALWAYS_INLINE Type type() const { return static_cast<Type>(m_type); }
     ContainerNode& ownerNode() const { return const_cast<ContainerNode&>(m_ownerNode.get()); }
 
     ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootType == NodeListIsRootedAtDocument; }
     ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
     ALWAYS_INLINE Type type() const { return static_cast<Type>(m_type); }
     ContainerNode& ownerNode() const { return const_cast<ContainerNode&>(m_ownerNode.get()); }
-    ALWAYS_INLINE void invalidateCache(const QualifiedName* attrName) const
+    ALWAYS_INLINE void invalidateCacheForAttribute(const QualifiedName* attrName) const
     {
         if (!attrName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attrName))
             invalidateCache(document());
     }
     {
         if (!attrName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attrName))
             invalidateCache(document());
     }
-    void invalidateCache(Document&) const;
-
-    // For CollectionIndexCache
-    Element* collectionFirst() const;
-    Element* collectionLast() const;
-    Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
-    Element* collectionTraverseBackward(Element&, unsigned count) const;
-    bool collectionCanTraverseBackward() const { return true; }
-    void willValidateIndexCache() const { document().registerNodeList(const_cast<LiveNodeList&>(*this)); }
+    virtual void invalidateCache(Document&) const = 0;
 
 protected:
     Document& document() const { return m_ownerNode->document(); }
 
 protected:
     Document& document() const { return m_ownerNode->document(); }
@@ -110,13 +85,37 @@ private:
 
     Ref<ContainerNode> m_ownerNode;
 
 
     Ref<ContainerNode> m_ownerNode;
 
-    mutable CollectionIndexCache<LiveNodeList, Element> m_indexCache;
-
     const unsigned m_rootType : 1;
     const unsigned m_invalidationType : 4;
     const unsigned m_type : 3;
 };
 
     const unsigned m_rootType : 1;
     const unsigned m_invalidationType : 4;
     const unsigned m_type : 3;
 };
 
+template <class NodeListType>
+class CachedLiveNodeList : public LiveNodeList {
+public:
+    virtual ~CachedLiveNodeList();
+
+    virtual unsigned length() const override final;
+    virtual Node* item(unsigned offset) const override final;
+
+    // For CollectionIndexCache
+    Element* collectionFirst() const;
+    Element* collectionLast() const;
+    Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
+    Element* collectionTraverseBackward(Element&, unsigned count) const;
+    bool collectionCanTraverseBackward() const { return true; }
+    void willValidateIndexCache() const;
+
+    virtual void invalidateCache(Document&) const;
+    virtual size_t memoryCost() const override;
+
+protected:
+    CachedLiveNodeList(ContainerNode& rootNode, Type, NodeListInvalidationType, NodeListRootType = NodeListIsRootedAtNode);
+
+private:
+    mutable CollectionIndexCache<NodeListType, Element> m_indexCache;
+};
+
 ALWAYS_INLINE bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
 {
     switch (type) {
 ALWAYS_INLINE bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
 {
     switch (type) {
@@ -141,6 +140,123 @@ ALWAYS_INLINE bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationTyp
     return false;
 }
 
     return false;
 }
 
+inline ContainerNode& LiveNodeList::rootNode() const
+{
+    if (isRootedAtDocument() && ownerNode().inDocument())
+        return ownerNode().document();
+
+    return ownerNode();
+}
+
+template <class NodeListType>
+CachedLiveNodeList<NodeListType>::CachedLiveNodeList(ContainerNode& ownerNode, Type type, NodeListInvalidationType invalidationType, NodeListRootType rootType)
+    : LiveNodeList(ownerNode, type, invalidationType, rootType)
+{
+}
+
+template <class NodeListType>
+CachedLiveNodeList<NodeListType>::~CachedLiveNodeList()
+{
+    if (m_indexCache.hasValidCache())
+        document().unregisterNodeList(*this);
+}
+
+template <class NodeListType>
+Element* CachedLiveNodeList<NodeListType>::collectionFirst() const
+{
+    auto& root = rootNode();
+    Element* element = ElementTraversal::firstWithin(&root);
+    while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
+        element = ElementTraversal::next(element, &root);
+    return element;
+}
+
+template <class NodeListType>
+Element* CachedLiveNodeList<NodeListType>::collectionLast() const
+{
+    auto& root = rootNode();
+    Element* element = ElementTraversal::lastWithin(&root);
+    while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
+        element = ElementTraversal::previous(element, &root);
+    return element;
+}
+
+template <class NodeListType>
+inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
+{
+    do {
+        current = ElementTraversal::next(current, &root);
+    } while (current && !static_cast<const NodeListType*>(nodeList)->nodeMatches(current));
+    return current;
+}
+
+template <class NodeListType>
+Element* CachedLiveNodeList<NodeListType>::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
+{
+    auto& root = rootNode();
+    Element* element = &current;
+    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+        element = nextMatchingElement(static_cast<const NodeListType*>(this), element, root);
+        if (!element)
+            return nullptr;
+    }
+    return element;
+}
+
+template <class NodeListType>
+inline Element* previousMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
+{
+    do {
+        current = ElementTraversal::previous(current, &root);
+    } while (current && !nodeList->nodeMatches(current));
+    return current;
+}
+
+template <class NodeListType>
+Element* CachedLiveNodeList<NodeListType>::collectionTraverseBackward(Element& current, unsigned count) const
+{
+    auto& root = rootNode();
+    Element* element = &current;
+    for (; count; --count) {
+        element = previousMatchingElement(static_cast<const NodeListType*>(this), element, root);
+        if (!element)
+            return nullptr;
+    }
+    return element;
+}
+template <class NodeListType>
+void CachedLiveNodeList<NodeListType>::willValidateIndexCache() const
+{
+    document().registerNodeList(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
+}
+
+template <class NodeListType>
+void CachedLiveNodeList<NodeListType>::invalidateCache(Document& document) const
+{
+    if (!m_indexCache.hasValidCache())
+        return;
+    document.unregisterNodeList(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
+    m_indexCache.invalidate();
+}
+
+template <class NodeListType>
+unsigned CachedLiveNodeList<NodeListType>::length() const
+{
+    return m_indexCache.nodeCount(static_cast<const NodeListType&>(*this));
+}
+
+template <class NodeListType>
+Node* CachedLiveNodeList<NodeListType>::item(unsigned offset) const
+{
+    return m_indexCache.nodeAt(static_cast<const NodeListType&>(*this), offset);
+}
+
+template <class NodeListType>
+size_t CachedLiveNodeList<NodeListType>::memoryCost() const
+{
+    return m_indexCache.memoryCost();
+}
+
 } // namespace WebCore
 
 #endif // LiveNodeList_h
 } // namespace WebCore
 
 #endif // LiveNodeList_h
index 6fd4545be85e666f1f8129da01aa0106403b947f..60a6c7945cceb429b888cccbfc9e6e663d39f50f 100644 (file)
@@ -30,7 +30,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 NameNodeList::NameNodeList(ContainerNode& rootNode, const AtomicString& name)
 using namespace HTMLNames;
 
 NameNodeList::NameNodeList(ContainerNode& rootNode, const AtomicString& name)
-    : LiveNodeList(rootNode, Type::NameNodeListType, InvalidateOnNameAttrChange)
+    : CachedLiveNodeList(rootNode, Type::NameNodeListType, InvalidateOnNameAttrChange)
     , m_name(name)
 {
 }
     , m_name(name)
 {
 }
index 2a369513f13aec097bb81377b0457c251bb60fa9..95da32ec07d1f9179b1042798371bbb422d13ba2 100644 (file)
@@ -31,7 +31,7 @@
 namespace WebCore {
 
 // NodeList which lists all Nodes in a Element with a given "name" attribute
 namespace WebCore {
 
 // NodeList which lists all Nodes in a Element with a given "name" attribute
-class NameNodeList : public LiveNodeList {
+class NameNodeList final : public CachedLiveNodeList<NameNodeList> {
 public:
     static PassRefPtr<NameNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& name)
     {
 public:
     static PassRefPtr<NameNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& name)
     {
@@ -41,11 +41,11 @@ public:
 
     virtual ~NameNodeList();
 
 
     virtual ~NameNodeList();
 
+    virtual bool nodeMatches(Element*) const override;
+
 private:
     NameNodeList(ContainerNode& rootNode, const AtomicString& name);
 
 private:
     NameNodeList(ContainerNode& rootNode, const AtomicString& name);
 
-    virtual bool nodeMatches(Element*) const override;
-
     AtomicString m_name;
 };
 
     AtomicString m_name;
 };
 
index 3cf8af39d6876ea01837f8bfb8f3e36767fc3d16..ad6b8b0dd2fe8c9d991331fa3b7e4abed5cb34f7 100644 (file)
@@ -726,7 +726,7 @@ void Document::invalidateNodeListAndCollectionCaches(const QualifiedName* attrNa
 #endif
     HashSet<LiveNodeList*> lists = std::move(m_listsInvalidatedAtDocument);
     for (auto* list : lists)
 #endif
     HashSet<LiveNodeList*> lists = std::move(m_listsInvalidatedAtDocument);
     for (auto* list : lists)
-        list->invalidateCache(attrName);
+        list->invalidateCacheForAttribute(attrName);
     HashSet<HTMLCollection*> collections = std::move(m_collectionsInvalidatedAtDocument);
     for (auto* collection : collections)
         collection->invalidateCache(attrName);
     HashSet<HTMLCollection*> collections = std::move(m_collectionsInvalidatedAtDocument);
     for (auto* collection : collections)
         collection->invalidateCache(attrName);
@@ -1685,10 +1685,10 @@ void Node::showTreeForThisAcrossFrame() const
 void NodeListsNodeData::invalidateCaches(const QualifiedName* attrName)
 {
     for (auto& atomicName : m_atomicNameCaches)
 void NodeListsNodeData::invalidateCaches(const QualifiedName* attrName)
 {
     for (auto& atomicName : m_atomicNameCaches)
-        atomicName.value->invalidateCache(attrName);
+        atomicName.value->invalidateCacheForAttribute(attrName);
 
     for (auto& name : m_nameCaches)
 
     for (auto& name : m_nameCaches)
-        name.value->invalidateCache(attrName);
+        name.value->invalidateCacheForAttribute(attrName);
 
     for (auto& collection : m_cachedCollections)
         collection.value->invalidateCache(attrName);
 
     for (auto& collection : m_cachedCollections)
         collection.value->invalidateCache(attrName);
@@ -1697,7 +1697,7 @@ void NodeListsNodeData::invalidateCaches(const QualifiedName* attrName)
         return;
 
     for (auto& tagNodeList : m_tagNodeListCacheNS)
         return;
 
     for (auto& tagNodeList : m_tagNodeListCacheNS)
-        tagNodeList.value->invalidateCache(nullptr);
+        tagNodeList.value->invalidateCacheForAttribute(nullptr);
 }
 
 void Node::getSubresourceURLs(ListHashSet<URL>& urls) const
 }
 
 void Node::getSubresourceURLs(ListHashSet<URL>& urls) const
index a011e6c59255e63b236bec9f600829a431edd5d7..3c19091bd59ccc043e80828c4a8ece9c6de232b4 100644 (file)
@@ -28,8 +28,8 @@
 
 namespace WebCore {
 
 
 namespace WebCore {
 
-TagNodeList::TagNodeList(ContainerNode& rootNode, Type type, const AtomicString& namespaceURI, const AtomicString& localName)
-    : LiveNodeList(rootNode, type, DoNotInvalidateOnAttributeChanges)
+TagNodeList::TagNodeList(ContainerNode& rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
+    : CachedLiveNodeList(rootNode, Type::TagNodeListType, DoNotInvalidateOnAttributeChanges)
     , m_namespaceURI(namespaceURI)
     , m_localName(localName)
 {
     , m_namespaceURI(namespaceURI)
     , m_localName(localName)
 {
@@ -44,24 +44,16 @@ TagNodeList::~TagNodeList()
         ownerNode().nodeLists()->removeCacheWithQualifiedName(this, m_namespaceURI, m_localName);
 }
 
         ownerNode().nodeLists()->removeCacheWithQualifiedName(this, m_namespaceURI, m_localName);
 }
 
-bool TagNodeList::nodeMatches(Element* testNode) const
-{
-    // Implements http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#concept-getelementsbytagnamens
-    if (m_localName != starAtom && m_localName != testNode->localName())
-        return false;
-
-    return m_namespaceURI == starAtom || m_namespaceURI == testNode->namespaceURI();
-}
-
 HTMLTagNodeList::HTMLTagNodeList(ContainerNode& rootNode, const AtomicString& localName)
 HTMLTagNodeList::HTMLTagNodeList(ContainerNode& rootNode, const AtomicString& localName)
-    : TagNodeList(rootNode, Type::HTMLTagNodeListType, starAtom, localName)
+    : CachedLiveNodeList(rootNode, Type::HTMLTagNodeListType, DoNotInvalidateOnAttributeChanges)
+    , m_localName(localName)
     , m_loweredLocalName(localName.lower())
 {
 }
 
     , m_loweredLocalName(localName.lower())
 {
 }
 
-bool HTMLTagNodeList::nodeMatches(Element* testNode) const
+HTMLTagNodeList::~HTMLTagNodeList()
 {
 {
-    return nodeMatchesInlined(testNode);
+    ownerNode().nodeLists()->removeCacheWithAtomicName(this, m_localName);
 }
 
 } // namespace WebCore
 }
 
 } // namespace WebCore
index 0009fdb4c9ff528e1eddd8b9216a258d0b59e667..8f751037035d886f4bdd173fd3d77b70dd842983 100644 (file)
 namespace WebCore {
 
 // NodeList that limits to a particular tag.
 namespace WebCore {
 
 // NodeList that limits to a particular tag.
-class TagNodeList : public LiveNodeList {
+class TagNodeList final : public CachedLiveNodeList<TagNodeList> {
 public:
     static PassRefPtr<TagNodeList> create(ContainerNode& rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
     {
         ASSERT(namespaceURI != starAtom);
 public:
     static PassRefPtr<TagNodeList> create(ContainerNode& rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
     {
         ASSERT(namespaceURI != starAtom);
-        return adoptRef(new TagNodeList(rootNode, Type::TagNodeListType, namespaceURI, localName));
+        return adoptRef(new TagNodeList(rootNode, namespaceURI, localName));
     }
 
     static PassRefPtr<TagNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& localName)
     {
         ASSERT_UNUSED(type, type == Type::TagNodeListType);
     }
 
     static PassRefPtr<TagNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& localName)
     {
         ASSERT_UNUSED(type, type == Type::TagNodeListType);
-        return adoptRef(new TagNodeList(rootNode, Type::TagNodeListType, starAtom, localName));
+        return adoptRef(new TagNodeList(rootNode, starAtom, localName));
     }
 
     virtual ~TagNodeList();
 
     }
 
     virtual ~TagNodeList();
 
-protected:
-    TagNodeList(ContainerNode& rootNode, Type, const AtomicString& namespaceURI, const AtomicString& localName);
-
     virtual bool nodeMatches(Element*) const override;
 
     virtual bool nodeMatches(Element*) const override;
 
+protected:
+    TagNodeList(ContainerNode& rootNode, const AtomicString& namespaceURI, const AtomicString& localName);
+
     AtomicString m_namespaceURI;
     AtomicString m_localName;
 };
 
     AtomicString m_namespaceURI;
     AtomicString m_localName;
 };
 
-class HTMLTagNodeList : public TagNodeList {
+inline bool TagNodeList::nodeMatches(Element* element) const
+{
+    // Implements http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#concept-getelementsbytagnamens
+    if (m_localName != starAtom && m_localName != element->localName())
+        return false;
+
+    return m_namespaceURI == starAtom || m_namespaceURI == element->namespaceURI();
+}
+
+class HTMLTagNodeList final : public CachedLiveNodeList<HTMLTagNodeList> {
 public:
     static PassRefPtr<HTMLTagNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& localName)
     {
 public:
     static PassRefPtr<HTMLTagNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& localName)
     {
@@ -64,26 +73,24 @@ public:
         return adoptRef(new HTMLTagNodeList(rootNode, localName));
     }
 
         return adoptRef(new HTMLTagNodeList(rootNode, localName));
     }
 
-    bool nodeMatchesInlined(Element*) const;
+    virtual ~HTMLTagNodeList();
+
+    virtual bool nodeMatches(Element*) const override;
 
 private:
     HTMLTagNodeList(ContainerNode& rootNode, const AtomicString& localName);
 
 
 private:
     HTMLTagNodeList(ContainerNode& rootNode, const AtomicString& localName);
 
-    virtual bool nodeMatches(Element*) const override;
-
+    AtomicString m_localName;
     AtomicString m_loweredLocalName;
 };
 
     AtomicString m_loweredLocalName;
 };
 
-inline bool HTMLTagNodeList::nodeMatchesInlined(Element* testNode) const
+inline bool HTMLTagNodeList::nodeMatches(Element* element) const
 {
     // Implements http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#concept-getelementsbytagname
 {
     // Implements http://dvcs.w3.org/hg/domcore/raw-file/tip/Overview.html#concept-getelementsbytagname
-    if (m_localName != starAtom) {
-        const AtomicString& localName = testNode->isHTMLElement() ? m_loweredLocalName : m_localName;
-        if (localName != testNode->localName())
-            return false;
-    }
-    ASSERT(m_namespaceURI == starAtom);
-    return true;
+    if (m_localName == starAtom)
+        return true;
+    const AtomicString& localName = element->isHTMLElement() ? m_loweredLocalName : m_localName;
+    return localName == element->localName();
 }
 
 } // namespace WebCore
 }
 
 } // namespace WebCore
index a09b4d752e0a15d9e16db30803a28afc0443f790..2ae10840845359934cc55f1d345c01804dfbbd2d 100644 (file)
@@ -34,7 +34,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 LabelsNodeList::LabelsNodeList(LabelableElement& forNode)
 using namespace HTMLNames;
 
 LabelsNodeList::LabelsNodeList(LabelableElement& forNode)
-    : LiveNodeList(forNode, Type::LabelsNodeListType, InvalidateOnForAttrChange, NodeListIsRootedAtDocument)
+    : CachedLiveNodeList(forNode, Type::LabelsNodeListType, InvalidateOnForAttrChange, NodeListIsRootedAtDocument)
 {
 }
 
 {
 }
 
index 88271fa8268cf38db5a312950fe08043b53469e7..232fb9064bc1a82c9c4db62dab147244a52805a6 100644 (file)
@@ -30,7 +30,7 @@
 
 namespace WebCore {
 
 
 namespace WebCore {
 
-class LabelsNodeList final : public LiveNodeList {
+class LabelsNodeList final : public CachedLiveNodeList<LabelsNodeList> {
 public:
     static PassRef<LabelsNodeList> create(LabelableElement& forNode, Type type, const AtomicString&)
     {
 public:
     static PassRef<LabelsNodeList> create(LabelableElement& forNode, Type type, const AtomicString&)
     {
@@ -39,10 +39,10 @@ public:
     }
     ~LabelsNodeList();
 
     }
     ~LabelsNodeList();
 
-protected:
-    explicit LabelsNodeList(LabelableElement& forNode);
-
     virtual bool nodeMatches(Element*) const override;
     virtual bool nodeMatches(Element*) const override;
+
+private:
+    explicit LabelsNodeList(LabelableElement& forNode);
 };
 
 } // namespace WebCore
 };
 
 } // namespace WebCore
index ccd4093f21b446d2e883dee484b58562a989ba52..1d892606ce373973215a12950bdceeffe6bd1f19 100644 (file)
@@ -38,7 +38,7 @@ namespace WebCore {
 using namespace HTMLNames;
 
 RadioNodeList::RadioNodeList(ContainerNode& rootNode, const AtomicString& name)
 using namespace HTMLNames;
 
 RadioNodeList::RadioNodeList(ContainerNode& rootNode, const AtomicString& name)
-    : LiveNodeList(rootNode, Type::RadioNodeListType, InvalidateForFormControls, isHTMLFormElement(rootNode) ? NodeListIsRootedAtDocument : NodeListIsRootedAtNode)
+    : CachedLiveNodeList(rootNode, Type::RadioNodeListType, InvalidateForFormControls, isHTMLFormElement(rootNode) ? NodeListIsRootedAtDocument : NodeListIsRootedAtNode)
     , m_name(name)
 {
 }
     , m_name(name)
 {
 }
index 281aa7fadb438ef573360a241e6175d37bf148e0..97dced9f005b747934320f2618dc93b8aef901fd 100644 (file)
@@ -32,7 +32,7 @@
 
 namespace WebCore {
 
 
 namespace WebCore {
 
-class RadioNodeList : public LiveNodeList {
+class RadioNodeList final : public CachedLiveNodeList<RadioNodeList> {
 public:
     static PassRefPtr<RadioNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& name)
     {
 public:
     static PassRefPtr<RadioNodeList> create(ContainerNode& rootNode, Type type, const AtomicString& name)
     {
@@ -45,7 +45,6 @@ public:
     String value() const;
     void setValue(const String&);
 
     String value() const;
     void setValue(const String&);
 
-protected:
     virtual bool nodeMatches(Element*) const override;
 
 private:
     virtual bool nodeMatches(Element*) const override;
 
 private: