Refactor HTMLCollection to be as fast as CachedLiveNodeList
authorcdumez@apple.com <cdumez@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 15 Aug 2015 05:44:46 +0000 (05:44 +0000)
committercdumez@apple.com <cdumez@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 15 Aug 2015 05:44:46 +0000 (05:44 +0000)
https://bugs.webkit.org/show_bug.cgi?id=147979

Reviewed by Ryosuke Niwa.

Refactor HTMLCollection to be as fast as CachedLiveNodeList. This is in
preparation of having getElementsByTagName*() / getElementsByClassName()
return an HTMLCollection instead of a NodeList, as per the
specification. Chrome and Firefox already match the specification in
this case.

Traversing an HTMLCollection was slow because of all the extra
branching it had compared to CachedLiveNodeList. To address the issue,
this patch introduces a new templated CachedHTMLCollection subclass,
which behaves in a similar way as CachedLiveNodeList. The 2 template
parameters are:
1. The type of the subclass of CachedHTMLCollection, so we can call
   elementMatches() directly on the subclass, without needed any
   virtual function call or switch statement. This is the same approach
   as in CachedLiveNodeList.
2. The type of tree traversal used (Descendants, ChildrenOnly,
   CustomForwardOnly). Unlike LiveNodeList, HTMLCollection needs to
   support these 3 types of tree traversal. These were causing extra
   branching for every item() call. We are now able to choose the right
   type of traversal for the CachedHTMLCollection at compile time.

* WebCore.xcodeproj/project.pbxproj:
Add new files to the Project.

* dom/ContainerNode.cpp:
(WebCore::ContainerNode::children):
(WebCore::ContainerNode::cachedHTMLCollection): Deleted.
* dom/ContainerNode.h:
Drop ContainerNode::ensureCachedHTMLCollection() and use
NodeListsNodeData::addCachedCollection() directly at call sites
instead. We need access to the CollectionType at build-time so
we can resolve the CollectionTraversalType parameter for the
GenericCachedHTMLCollection using CollectionTypeTraits.

* dom/Document.cpp:
* dom/Document.h:
Update ensureCachedCollection() so the CollectionType is now a template
parameter instead of a method argument. We need to know the
CollectionType at build time to construct the GenericCachedHTMLCollection.

* dom/ElementChildIterator.h:
(WebCore::ElementChildIterator<ElementType>::operator):
(WebCore::ElementChildConstIterator<ElementType>::operator):
Add support for decrementing an ElementChildIterator, for consistency
with ElementDescendantIterator. We need this to support backward
traversal in CachedHTMLCollections that use the 'ChildrenOnly' type
of traversal.

* dom/LiveNodeList.h:
(WebCore::CachedLiveNodeList<NodeListType>::collectionBegin):
(WebCore::CachedLiveNodeList<NodeListType>::collectionLast):
(WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseForward):
(WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseBackward):
Move traversal implementation to CollectionTraversal.h, so it can be
shared with achedHTMLCollection.h.

* html/CachedHTMLCollection.h: Added.
(WebCore::traversalType>::CachedHTMLCollection):
(WebCore::traversalType>::~CachedHTMLCollection):
(WebCore::traversalType>::CachedHTMLCollection::memoryCost):
(WebCore::traversalType>::collectionCanTraverseBackward):
(WebCore::traversalType>::collectionTraverseForward):
(WebCore::traversalType>::collectionTraverseBackward):
(WebCore::traversalType>::willValidateIndexCache):
(WebCore::traversalType>::length):
(WebCore::traversalType>::item):
(WebCore::traversalType>::invalidateCache):
(WebCore::traversalType>::elementMatches):
(WebCore::nameShouldBeVisibleInDocumentAll):
(WebCore::traversalType>::namedItem):

* html/CollectionTraversal.h: Added.
Add new template class that provide the collection traversal code
needed by CollectionIndexCache. It has template specializations for
all 3 types of traversal: Descendants, ChildrenOnly, and
CustomForwardOnly.

* html/CollectionType.h:
Add CollectionTypeTraits traits so we can resolve the
CollectionTraversalType used by a specific CollectionType at
compile-time. This is needed for the second template parameter of
CachedHTMLCollection.

* html/GenericCachedHTMLCollection.cpp: Added.
(WebCore::GenericCachedHTMLCollection<traversalType>::elementMatches):
* html/GenericCachedHTMLCollection.h: Added.
Add CachedHTMLCollection subclass is the generic one used for all
CollectionTypes that do not have their own subclass (e.g. NodeChildren).
This has an elementMatches() method with a switch() statement handling
all these CollectionTypes. Those are not normally not performance
sensitive.

* html/HTMLAllCollection.cpp:
(WebCore::HTMLAllCollection::HTMLAllCollection):
* html/HTMLAllCollection.h:
Subclass CachedHTMLCollection instead of HTMLCollection. Also provide
an elementMatches() method that simply returns true as we want to
match all elements.

* html/HTMLCollection.cpp:
(WebCore::HTMLCollection::HTMLCollection):
Move CollectionIndexCache member to the subclass and drop the 2 other
members as they are replaced with the CollectionTraversalType template
parameter of CachedHTMLCollection.

(WebCore::HTMLCollection::~HTMLCollection):
Move Document::unregisterCollection() call to ~CachedHTMLCollection()
as we needed to check if the CollectionIndexCache was valid first.

(WebCore::HTMLCollection::updateNamedElementCache):
Move part of the implementation to the CachedHTMLCollection subclass
as it needs to know about the type of traversal and it needs to be
able to call elementMatches().

* html/HTMLCollection.h:
(WebCore::HTMLCollection::rootNode):
Inline for performance reasons and consistency with CachedLiveNodeList.

(WebCore::HTMLCollection::memoryCost):
Make virtual and move part of the implementation to the
CachedHTMLCollection subclass to compute the cost of the
CollectionIndexCache.

(WebCore::HTMLCollection::invalidateCache):
Move part of the implementation to the subclass to invalidate the
CollectionIndexCache.

* html/HTMLFieldSetElement.cpp:
(WebCore::HTMLFieldSetElement::elements):

* html/HTMLFormControlsCollection.cpp:
* html/HTMLFormControlsCollection.h:
Subclass CachedHTMLCollection instead of HTMLCollection.
customElementAfter() no longer needs to be virtual as it
is called directly by CachedHTMLCollection on the subclass.

* html/HTMLFormElement.cpp:
(WebCore::HTMLFormElement::elements):
* html/HTMLMapElement.cpp:
(WebCore::HTMLMapElement::areas):
Call NodeListsNodeData::addCachedCollection() directly.

* html/HTMLNameCollection.cpp:
* html/HTMLNameCollection.h:
Subclass CachedHTMLCollection instead of HTMLCollection.

* html/HTMLOptionsCollection.cpp:
* html/HTMLOptionsCollection.h:
Subclass CachedHTMLCollection instead of HTMLCollection.

* html/HTMLSelectElement.cpp:
(WebCore::HTMLSelectElement::selectedOptions):
(WebCore::HTMLSelectElement::options):
* html/HTMLTableElement.cpp:
(WebCore::HTMLTableElement::rows):
(WebCore::HTMLTableElement::tBodies):
* html/HTMLTableRowElement.cpp:
(WebCore::HTMLTableRowElement::cells):
Call NodeListsNodeData::addCachedCollection() directly.

* html/HTMLTableRowsCollection.cpp:
* html/HTMLTableRowsCollection.h:
Subclass CachedHTMLCollection instead of HTMLCollection.
customElementAfter() no longer needs to be virtual as it
is called directly by CachedHTMLCollection on the subclass.

* html/HTMLTableSectionElement.cpp:
(WebCore::HTMLTableSectionElement::rows):
Call NodeListsNodeData::addCachedCollection() directly.

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

35 files changed:
Source/WebCore/CMakeLists.txt
Source/WebCore/ChangeLog
Source/WebCore/WebCore.vcxproj/WebCore.vcxproj
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/dom/ContainerNode.cpp
Source/WebCore/dom/ContainerNode.h
Source/WebCore/dom/Document.cpp
Source/WebCore/dom/Document.h
Source/WebCore/dom/ElementChildIterator.h
Source/WebCore/dom/LiveNodeList.h
Source/WebCore/html/CachedHTMLCollection.h [new file with mode: 0644]
Source/WebCore/html/CollectionTraversal.h [new file with mode: 0644]
Source/WebCore/html/CollectionType.h
Source/WebCore/html/GenericCachedHTMLCollection.cpp [new file with mode: 0644]
Source/WebCore/html/GenericCachedHTMLCollection.h [new file with mode: 0644]
Source/WebCore/html/HTMLAllCollection.cpp
Source/WebCore/html/HTMLAllCollection.h
Source/WebCore/html/HTMLCollection.cpp
Source/WebCore/html/HTMLCollection.h
Source/WebCore/html/HTMLDataListElement.cpp
Source/WebCore/html/HTMLFieldSetElement.cpp
Source/WebCore/html/HTMLFormControlsCollection.cpp
Source/WebCore/html/HTMLFormControlsCollection.h
Source/WebCore/html/HTMLFormElement.cpp
Source/WebCore/html/HTMLMapElement.cpp
Source/WebCore/html/HTMLNameCollection.cpp
Source/WebCore/html/HTMLNameCollection.h
Source/WebCore/html/HTMLOptionsCollection.cpp
Source/WebCore/html/HTMLOptionsCollection.h
Source/WebCore/html/HTMLSelectElement.cpp
Source/WebCore/html/HTMLTableElement.cpp
Source/WebCore/html/HTMLTableRowElement.cpp
Source/WebCore/html/HTMLTableRowsCollection.cpp
Source/WebCore/html/HTMLTableRowsCollection.h
Source/WebCore/html/HTMLTableSectionElement.cpp

index dc0d361..a3a506f 100644 (file)
@@ -1608,6 +1608,7 @@ set(WebCore_SOURCES
     html/FormAssociatedElement.cpp
     html/FormController.cpp
     html/FormDataList.cpp
+    html/GenericCachedHTMLCollection.cpp
     html/HTMLAllCollection.cpp
     html/HTMLAnchorElement.cpp
     html/HTMLAppletElement.cpp
index bf7f73a..01c18ae 100644 (file)
@@ -1,3 +1,180 @@
+2015-08-14  Chris Dumez  <cdumez@apple.com>
+
+        Refactor HTMLCollection to be as fast as CachedLiveNodeList
+        https://bugs.webkit.org/show_bug.cgi?id=147979
+
+        Reviewed by Ryosuke Niwa.
+
+        Refactor HTMLCollection to be as fast as CachedLiveNodeList. This is in
+        preparation of having getElementsByTagName*() / getElementsByClassName()
+        return an HTMLCollection instead of a NodeList, as per the
+        specification. Chrome and Firefox already match the specification in
+        this case.
+
+        Traversing an HTMLCollection was slow because of all the extra
+        branching it had compared to CachedLiveNodeList. To address the issue,
+        this patch introduces a new templated CachedHTMLCollection subclass,
+        which behaves in a similar way as CachedLiveNodeList. The 2 template
+        parameters are:
+        1. The type of the subclass of CachedHTMLCollection, so we can call
+           elementMatches() directly on the subclass, without needed any
+           virtual function call or switch statement. This is the same approach
+           as in CachedLiveNodeList.
+        2. The type of tree traversal used (Descendants, ChildrenOnly,
+           CustomForwardOnly). Unlike LiveNodeList, HTMLCollection needs to
+           support these 3 types of tree traversal. These were causing extra
+           branching for every item() call. We are now able to choose the right
+           type of traversal for the CachedHTMLCollection at compile time.
+
+        * WebCore.xcodeproj/project.pbxproj:
+        Add new files to the Project.
+
+        * dom/ContainerNode.cpp:
+        (WebCore::ContainerNode::children):
+        (WebCore::ContainerNode::cachedHTMLCollection): Deleted.
+        * dom/ContainerNode.h:
+        Drop ContainerNode::ensureCachedHTMLCollection() and use
+        NodeListsNodeData::addCachedCollection() directly at call sites
+        instead. We need access to the CollectionType at build-time so
+        we can resolve the CollectionTraversalType parameter for the
+        GenericCachedHTMLCollection using CollectionTypeTraits.
+
+        * dom/Document.cpp:
+        * dom/Document.h:
+        Update ensureCachedCollection() so the CollectionType is now a template
+        parameter instead of a method argument. We need to know the
+        CollectionType at build time to construct the GenericCachedHTMLCollection.
+
+        * dom/ElementChildIterator.h:
+        (WebCore::ElementChildIterator<ElementType>::operator):
+        (WebCore::ElementChildConstIterator<ElementType>::operator):
+        Add support for decrementing an ElementChildIterator, for consistency
+        with ElementDescendantIterator. We need this to support backward
+        traversal in CachedHTMLCollections that use the 'ChildrenOnly' type
+        of traversal.
+
+        * dom/LiveNodeList.h:
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionBegin):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionLast):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseForward):
+        (WebCore::CachedLiveNodeList<NodeListType>::collectionTraverseBackward):
+        Move traversal implementation to CollectionTraversal.h, so it can be
+        shared with achedHTMLCollection.h.
+
+        * html/CachedHTMLCollection.h: Added.
+        (WebCore::traversalType>::CachedHTMLCollection):
+        (WebCore::traversalType>::~CachedHTMLCollection):
+        (WebCore::traversalType>::CachedHTMLCollection::memoryCost):
+        (WebCore::traversalType>::collectionCanTraverseBackward):
+        (WebCore::traversalType>::collectionTraverseForward):
+        (WebCore::traversalType>::collectionTraverseBackward):
+        (WebCore::traversalType>::willValidateIndexCache):
+        (WebCore::traversalType>::length):
+        (WebCore::traversalType>::item):
+        (WebCore::traversalType>::invalidateCache):
+        (WebCore::traversalType>::elementMatches):
+        (WebCore::nameShouldBeVisibleInDocumentAll):
+        (WebCore::traversalType>::namedItem):
+
+        * html/CollectionTraversal.h: Added.
+        Add new template class that provide the collection traversal code
+        needed by CollectionIndexCache. It has template specializations for
+        all 3 types of traversal: Descendants, ChildrenOnly, and
+        CustomForwardOnly.
+
+        * html/CollectionType.h:
+        Add CollectionTypeTraits traits so we can resolve the
+        CollectionTraversalType used by a specific CollectionType at
+        compile-time. This is needed for the second template parameter of
+        CachedHTMLCollection.
+
+        * html/GenericCachedHTMLCollection.cpp: Added.
+        (WebCore::GenericCachedHTMLCollection<traversalType>::elementMatches):
+        * html/GenericCachedHTMLCollection.h: Added.
+        Add CachedHTMLCollection subclass is the generic one used for all
+        CollectionTypes that do not have their own subclass (e.g. NodeChildren).
+        This has an elementMatches() method with a switch() statement handling
+        all these CollectionTypes. Those are not normally not performance
+        sensitive.
+
+        * html/HTMLAllCollection.cpp:
+        (WebCore::HTMLAllCollection::HTMLAllCollection):
+        * html/HTMLAllCollection.h:
+        Subclass CachedHTMLCollection instead of HTMLCollection. Also provide
+        an elementMatches() method that simply returns true as we want to
+        match all elements.
+
+        * html/HTMLCollection.cpp:
+        (WebCore::HTMLCollection::HTMLCollection):
+        Move CollectionIndexCache member to the subclass and drop the 2 other
+        members as they are replaced with the CollectionTraversalType template
+        parameter of CachedHTMLCollection.
+
+        (WebCore::HTMLCollection::~HTMLCollection):
+        Move Document::unregisterCollection() call to ~CachedHTMLCollection()
+        as we needed to check if the CollectionIndexCache was valid first.
+
+        (WebCore::HTMLCollection::updateNamedElementCache):
+        Move part of the implementation to the CachedHTMLCollection subclass
+        as it needs to know about the type of traversal and it needs to be
+        able to call elementMatches().
+
+        * html/HTMLCollection.h:
+        (WebCore::HTMLCollection::rootNode):
+        Inline for performance reasons and consistency with CachedLiveNodeList.
+
+        (WebCore::HTMLCollection::memoryCost):
+        Make virtual and move part of the implementation to the
+        CachedHTMLCollection subclass to compute the cost of the
+        CollectionIndexCache.
+
+        (WebCore::HTMLCollection::invalidateCache):
+        Move part of the implementation to the subclass to invalidate the
+        CollectionIndexCache.
+
+        * html/HTMLFieldSetElement.cpp:
+        (WebCore::HTMLFieldSetElement::elements):
+
+        * html/HTMLFormControlsCollection.cpp:
+        * html/HTMLFormControlsCollection.h:
+        Subclass CachedHTMLCollection instead of HTMLCollection.
+        customElementAfter() no longer needs to be virtual as it
+        is called directly by CachedHTMLCollection on the subclass.
+
+        * html/HTMLFormElement.cpp:
+        (WebCore::HTMLFormElement::elements):
+        * html/HTMLMapElement.cpp:
+        (WebCore::HTMLMapElement::areas):
+        Call NodeListsNodeData::addCachedCollection() directly.
+
+        * html/HTMLNameCollection.cpp:
+        * html/HTMLNameCollection.h:
+        Subclass CachedHTMLCollection instead of HTMLCollection.
+
+        * html/HTMLOptionsCollection.cpp:
+        * html/HTMLOptionsCollection.h:
+        Subclass CachedHTMLCollection instead of HTMLCollection.
+
+        * html/HTMLSelectElement.cpp:
+        (WebCore::HTMLSelectElement::selectedOptions):
+        (WebCore::HTMLSelectElement::options):
+        * html/HTMLTableElement.cpp:
+        (WebCore::HTMLTableElement::rows):
+        (WebCore::HTMLTableElement::tBodies):
+        * html/HTMLTableRowElement.cpp:
+        (WebCore::HTMLTableRowElement::cells):
+        Call NodeListsNodeData::addCachedCollection() directly.
+
+        * html/HTMLTableRowsCollection.cpp:
+        * html/HTMLTableRowsCollection.h:
+        Subclass CachedHTMLCollection instead of HTMLCollection.
+        customElementAfter() no longer needs to be virtual as it
+        is called directly by CachedHTMLCollection on the subclass.
+
+        * html/HTMLTableSectionElement.cpp:
+        (WebCore::HTMLTableSectionElement::rows):
+        Call NodeListsNodeData::addCachedCollection() directly.
+
 2015-08-14  Matthew Daiter  <mdaiter@apple.com>
 
         Implementing enumerateDevices
index 92b9e1a..d17e362 100644 (file)
     <ClCompile Include="..\html\FormController.cpp" />
     <ClCompile Include="..\html\FormDataList.cpp" />
     <ClCompile Include="..\html\FTPDirectoryDocument.cpp" />
+    <ClCompile Include="..\html\GenericCachedHTMLCollection.cpp" />
     <ClCompile Include="..\html\HiddenInputType.cpp" />
     <ClCompile Include="..\html\HTMLAllCollection.cpp" />
     <ClCompile Include="..\html\HTMLAnchorElement.cpp">
index dc4e928..3a4a128 100644 (file)
                46C83EFE1A9BBE2900A79A41 /* GeoNotifier.h in Headers */ = {isa = PBXBuildFile; fileRef = 46C83EFC1A9BBE2900A79A41 /* GeoNotifier.h */; settings = {ATTRIBUTES = (Private, ); }; };
                46DB7D571B20FE46005651B2 /* VNodeTrackerCocoa.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 46DB7D561B20FE3C005651B2 /* VNodeTrackerCocoa.cpp */; };
                46DBB6501AB8C96F00D9A813 /* PowerObserverMac.h in Headers */ = {isa = PBXBuildFile; fileRef = 46DBB64E1AB8C96F00D9A813 /* PowerObserverMac.h */; };
+               46EBEA021B7D4D6500BE4941 /* CollectionTraversal.h in Headers */ = {isa = PBXBuildFile; fileRef = 46EBEA011B7D4D5D00BE4941 /* CollectionTraversal.h */; };
                46F3E3F91B2109000087ED13 /* VNodeTracker.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 46DB7D581B20FE58005651B2 /* VNodeTracker.cpp */; };
                46F3E3FA1B2109100087ED13 /* VNodeTracker.h in Headers */ = {isa = PBXBuildFile; fileRef = 46DB7D591B20FE58005651B2 /* VNodeTracker.h */; settings = {ATTRIBUTES = (Private, ); }; };
                46FCB6181A70820E00C5A21E /* DiagnosticLoggingKeys.h in Headers */ = {isa = PBXBuildFile; fileRef = CD37B37515C1A7E1006DC898 /* DiagnosticLoggingKeys.h */; settings = {ATTRIBUTES = (Private, ); }; };
                82AB1776125C826700C5069D /* InspectorResourceAgent.h in Headers */ = {isa = PBXBuildFile; fileRef = 82AB1772125C826700C5069D /* InspectorResourceAgent.h */; };
                82E3D8DE122EA0D1003AE5BC /* CSSPropertySourceData.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 82E3D8DC122EA0D1003AE5BC /* CSSPropertySourceData.cpp */; };
                82E3D8DF122EA0D1003AE5BC /* CSSPropertySourceData.h in Headers */ = {isa = PBXBuildFile; fileRef = 82E3D8DD122EA0D1003AE5BC /* CSSPropertySourceData.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               830030F51B7D33B500ED3AAC /* GenericCachedHTMLCollection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 830030F31B7D33A600ED3AAC /* GenericCachedHTMLCollection.cpp */; };
+               830030F61B7D33B500ED3AAC /* GenericCachedHTMLCollection.h in Headers */ = {isa = PBXBuildFile; fileRef = 830030F41B7D33A600ED3AAC /* GenericCachedHTMLCollection.h */; };
+               830030F81B7D3B7800ED3AAC /* CachedHTMLCollection.h in Headers */ = {isa = PBXBuildFile; fileRef = 830030F71B7D398800ED3AAC /* CachedHTMLCollection.h */; };
+               831D48C01B7D9A52006DE39A /* ClassNodeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 831D48BE1B7D9A46006DE39A /* ClassNodeList.cpp */; };
+               831D48C11B7D9A52006DE39A /* ClassNodeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 831D48BF1B7D9A46006DE39A /* ClassNodeList.h */; };
                832B843419D8E55100B26055 /* SVGAnimateElementBase.h in Headers */ = {isa = PBXBuildFile; fileRef = 832B843319D8E55100B26055 /* SVGAnimateElementBase.h */; };
                832B843619D8E57400B26055 /* SVGAnimateElementBase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 832B843519D8E57400B26055 /* SVGAnimateElementBase.cpp */; };
                83520C7E1A71BFCC006BD2AA /* CSSFontFamily.h in Headers */ = {isa = PBXBuildFile; fileRef = 83520C7D1A71BFCC006BD2AA /* CSSFontFamily.h */; };
                BC8BF15A1058141800A40A07 /* UserStyleSheetTypes.h in Headers */ = {isa = PBXBuildFile; fileRef = BC8BF1591058141800A40A07 /* UserStyleSheetTypes.h */; settings = {ATTRIBUTES = (Private, ); }; };
                BC8C8FAD0DDCD31B00B592F4 /* RenderStyle.cpp in Sources */ = {isa = PBXBuildFile; fileRef = BC8C8FAB0DDCD31B00B592F4 /* RenderStyle.cpp */; };
                BC8C8FAE0DDCD31B00B592F4 /* RenderStyle.h in Headers */ = {isa = PBXBuildFile; fileRef = BC8C8FAC0DDCD31B00B592F4 /* RenderStyle.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               BC904B760D10998F00680D32 /* ClassNodeList.cpp in Sources */ = {isa = PBXBuildFile; fileRef = BC904B720D10998F00680D32 /* ClassNodeList.cpp */; };
-               BC904B770D10998F00680D32 /* ClassNodeList.h in Headers */ = {isa = PBXBuildFile; fileRef = BC904B730D10998F00680D32 /* ClassNodeList.h */; };
                BC926F800C0552470082776B /* JSHTMLFrameSetElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = BC926F7E0C0552470082776B /* JSHTMLFrameSetElement.cpp */; };
                BC926F810C0552470082776B /* JSHTMLFrameSetElement.h in Headers */ = {isa = PBXBuildFile; fileRef = BC926F7F0C0552470082776B /* JSHTMLFrameSetElement.h */; };
                BC9439C3116CF4940048C750 /* JSNodeCustom.h in Headers */ = {isa = PBXBuildFile; fileRef = BC9439C2116CF4940048C750 /* JSNodeCustom.h */; settings = {ATTRIBUTES = (Private, ); }; };
                46DB7D581B20FE58005651B2 /* VNodeTracker.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VNodeTracker.cpp; sourceTree = "<group>"; };
                46DB7D591B20FE58005651B2 /* VNodeTracker.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VNodeTracker.h; sourceTree = "<group>"; };
                46DBB64E1AB8C96F00D9A813 /* PowerObserverMac.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PowerObserverMac.h; sourceTree = "<group>"; };
+               46EBEA011B7D4D5D00BE4941 /* CollectionTraversal.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CollectionTraversal.h; sourceTree = "<group>"; };
                490707E41219C04300D90E51 /* ANGLEWebKitBridge.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ANGLEWebKitBridge.cpp; sourceTree = "<group>"; };
                490707E51219C04300D90E51 /* ANGLEWebKitBridge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ANGLEWebKitBridge.h; sourceTree = "<group>"; };
                49291E4A134172C800E753DE /* ImageRenderingMode.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ImageRenderingMode.h; sourceTree = "<group>"; };
                82AB1772125C826700C5069D /* InspectorResourceAgent.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = InspectorResourceAgent.h; sourceTree = "<group>"; };
                82E3D8DC122EA0D1003AE5BC /* CSSPropertySourceData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CSSPropertySourceData.cpp; sourceTree = "<group>"; };
                82E3D8DD122EA0D1003AE5BC /* CSSPropertySourceData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CSSPropertySourceData.h; sourceTree = "<group>"; };
+               830030F31B7D33A600ED3AAC /* GenericCachedHTMLCollection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = GenericCachedHTMLCollection.cpp; sourceTree = "<group>"; };
+               830030F41B7D33A600ED3AAC /* GenericCachedHTMLCollection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GenericCachedHTMLCollection.h; sourceTree = "<group>"; };
+               830030F71B7D398800ED3AAC /* CachedHTMLCollection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CachedHTMLCollection.h; sourceTree = "<group>"; };
+               831D48BE1B7D9A46006DE39A /* ClassNodeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ClassNodeList.cpp; sourceTree = "<group>"; };
+               831D48BF1B7D9A46006DE39A /* ClassNodeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ClassNodeList.h; sourceTree = "<group>"; };
                832B843319D8E55100B26055 /* SVGAnimateElementBase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SVGAnimateElementBase.h; sourceTree = "<group>"; };
                832B843519D8E57400B26055 /* SVGAnimateElementBase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SVGAnimateElementBase.cpp; sourceTree = "<group>"; };
                83520C7D1A71BFCC006BD2AA /* CSSFontFamily.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CSSFontFamily.h; sourceTree = "<group>"; };
                BC8BF1591058141800A40A07 /* UserStyleSheetTypes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UserStyleSheetTypes.h; sourceTree = "<group>"; };
                BC8C8FAB0DDCD31B00B592F4 /* RenderStyle.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RenderStyle.cpp; sourceTree = "<group>"; };
                BC8C8FAC0DDCD31B00B592F4 /* RenderStyle.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RenderStyle.h; sourceTree = "<group>"; };
-               BC904B720D10998F00680D32 /* ClassNodeList.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ClassNodeList.cpp; sourceTree = "<group>"; };
-               BC904B730D10998F00680D32 /* ClassNodeList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ClassNodeList.h; sourceTree = "<group>"; };
                BC926F7E0C0552470082776B /* JSHTMLFrameSetElement.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = JSHTMLFrameSetElement.cpp; sourceTree = "<group>"; };
                BC926F7F0C0552470082776B /* JSHTMLFrameSetElement.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = JSHTMLFrameSetElement.h; sourceTree = "<group>"; };
                BC9439C2116CF4940048C750 /* JSNodeCustom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSNodeCustom.h; sourceTree = "<group>"; };
                                F55B3D7A1251F12D003EF269 /* BaseTextInputType.h */,
                                F55B3D7B1251F12D003EF269 /* ButtonInputType.cpp */,
                                F55B3D7C1251F12D003EF269 /* ButtonInputType.h */,
+                               830030F71B7D398800ED3AAC /* CachedHTMLCollection.h */,
                                F55B3D7D1251F12D003EF269 /* CheckboxInputType.cpp */,
                                F55B3D7E1251F12D003EF269 /* CheckboxInputType.h */,
                                4ACBC0BC12713CBD0094F9B2 /* ClassList.cpp */,
                                4ACBC0BD12713CBD0094F9B2 /* ClassList.h */,
+                               46EBEA011B7D4D5D00BE4941 /* CollectionTraversal.h */,
                                93C441FF0F813AE100C1A634 /* CollectionType.h */,
                                BC29935C17A1DD5800BCE880 /* ColorInputType.cpp */,
                                F55B3D801251F12D003EF269 /* ColorInputType.h */,
                                9B50B1DC17CD4C0F0087F63C /* FormNamedItem.h */,
                                97205AAD123928CA00B17380 /* FTPDirectoryDocument.cpp */,
                                97205AAE123928CA00B17380 /* FTPDirectoryDocument.h */,
+                               830030F31B7D33A600ED3AAC /* GenericCachedHTMLCollection.cpp */,
+                               830030F41B7D33A600ED3AAC /* GenericCachedHTMLCollection.h */,
                                F55B3D8B1251F12D003EF269 /* HiddenInputType.cpp */,
                                F55B3D8C1251F12D003EF269 /* HiddenInputType.h */,
                                BC97E239109144950010D361 /* HTMLAllCollection.cpp */,
                                83D26D3C1AFDCC50001B3873 /* ChildNode.idl */,
                                A818721A0977D3C0005826D9 /* ChildNodeList.cpp */,
                                A81872150977D3C0005826D9 /* ChildNodeList.h */,
-                               BC904B720D10998F00680D32 /* ClassNodeList.cpp */,
-                               BC904B730D10998F00680D32 /* ClassNodeList.h */,
+                               831D48BE1B7D9A46006DE39A /* ClassNodeList.cpp */,
+                               831D48BF1B7D9A46006DE39A /* ClassNodeList.h */,
                                BCC065770F3CE1B700CD2D87 /* ClientRect.cpp */,
                                BCC065780F3CE1B700CD2D87 /* ClientRect.h */,
                                BCC065790F3CE1B700CD2D87 /* ClientRect.idl */,
                                14D823520AF92A790004F057 /* Chrome.h in Headers */,
                                14D824080AF93AEB0004F057 /* ChromeClient.h in Headers */,
                                4ACBC0BF12713CBD0094F9B2 /* ClassList.h in Headers */,
-                               BC904B770D10998F00680D32 /* ClassNodeList.h in Headers */,
                                BCC0657E0F3CE1B700CD2D87 /* ClientRect.h in Headers */,
                                BCC065810F3CE1B700CD2D87 /* ClientRectList.h in Headers */,
                                85031B400A44EFC700F992E0 /* ClipboardEvent.h in Headers */,
                                8372DB311A6780A800C697C5 /* DiagnosticLoggingResultType.h in Headers */,
                                CECADFC7153778FF00E37068 /* DictationAlternative.h in Headers */,
                                CECADFC9153778FF00E37068 /* DictationCommand.h in Headers */,
+                               46EBEA021B7D4D6500BE4941 /* CollectionTraversal.h in Headers */,
                                D0BD4F5D1408850F006839B6 /* DictationCommandIOS.h in Headers */,
                                15145B901B3A1CE000662BF7 /* MediaDeviceInfo.h in Headers */,
                                316023F01532C40C00D50FF4 /* Dictionary.h in Headers */,
                                85E711960AC5D5350053270F /* DOMDocumentTypeInternal.h in Headers */,
                                8518DCE90A9CC80D0091B7A6 /* DOMDOMImplementation.h in Headers */,
                                85E711970AC5D5350053270F /* DOMDOMImplementationInternal.h in Headers */,
+                               831D48C11B7D9A52006DE39A /* ClassNodeList.h in Headers */,
                                52CCA9E815E3F64C0053C77F /* DOMDOMNamedFlowCollection.h in Headers */,
                                52CCA9EA15E3F64C0053C77F /* DOMDOMNamedFlowCollectionInternal.h in Headers */,
                                2D9A247415B9C2E300D34527 /* DOMDOMSecurityPolicy.h in Headers */,
                                FDA15EB212B03EE1003A583A /* JSPannerNode.h in Headers */,
                                8A9A587511E84C81008ACFD1 /* JSPerformance.h in Headers */,
                                8A9A587111E84C36008ACFD1 /* JSPerformanceNavigation.h in Headers */,
+                               830030F61B7D33B500ED3AAC /* GenericCachedHTMLCollection.h in Headers */,
                                8A9A588811E84F37008ACFD1 /* JSPerformanceTiming.h in Headers */,
                                FDEA6247152102FC00479DF0 /* JSPeriodicWave.h in Headers */,
                                93B70D6C09EB0C7C009D8468 /* JSPluginElementFunctions.h in Headers */,
                                B2227A510D00BF220071B782 /* SVGNumberList.h in Headers */,
                                B2227A540D00BF220071B782 /* SVGPaint.h in Headers */,
                                B2227A570D00BF220071B782 /* SVGParserUtilities.h in Headers */,
+                               830030F81B7D3B7800ED3AAC /* CachedHTMLCollection.h in Headers */,
                                2D3A0E3613A7D76100E85AF0 /* SVGParsingError.h in Headers */,
                                84C6784D1214814700A92902 /* SVGPathBlender.h in Headers */,
                                8476C9EB11DF6A2900555B02 /* SVGPathBuilder.h in Headers */,
                                14D8238B0AF92DF60004F057 /* Chrome.cpp in Sources */,
                                ABAF22080C03B1C700B0BCF0 /* ChromeMac.mm in Sources */,
                                4ACBC0BE12713CBD0094F9B2 /* ClassList.cpp in Sources */,
-                               BC904B760D10998F00680D32 /* ClassNodeList.cpp in Sources */,
                                BCC0657D0F3CE1B700CD2D87 /* ClientRect.cpp in Sources */,
                                BCC065800F3CE1B700CD2D87 /* ClientRectList.cpp in Sources */,
                                85031B3F0A44EFC700F992E0 /* ClipboardEvent.cpp in Sources */,
                                A9C6E64C0D7465E7006442E9 /* JSDOMPluginArrayCustom.cpp in Sources */,
                                A9C6E64D0D7465E7006442E9 /* JSDOMPluginCustom.cpp in Sources */,
                                E172AF8F1811BC3700FBADB9 /* JSDOMPromise.cpp in Sources */,
+                               831D48C01B7D9A52006DE39A /* ClassNodeList.cpp in Sources */,
                                BC5A86B50C3367E800EEA649 /* JSDOMSelection.cpp in Sources */,
                                4ACBC0CA12713D0A0094F9B2 /* JSDOMSettableTokenList.cpp in Sources */,
                                C5137CF211A58378004ADB99 /* JSDOMStringList.cpp in Sources */,
                                07969DBD17D14151007FF842 /* JSRTCSessionDescriptionCallback.cpp in Sources */,
                                07D07B141834158800ABDD3C /* JSRTCSessionDescriptionCustom.cpp in Sources */,
                                07969DBF17D14151007FF842 /* JSRTCStatsCallback.cpp in Sources */,
+                               830030F51B7D33B500ED3AAC /* GenericCachedHTMLCollection.cpp in Sources */,
                                07969DC117D14151007FF842 /* JSRTCStatsReport.cpp in Sources */,
                                07969DC317D14151007FF842 /* JSRTCStatsResponse.cpp in Sources */,
                                07DC5FD417D3EEE90099F890 /* JSRTCStatsResponseCustom.cpp in Sources */,
index be3a3c1..be964bc 100644 (file)
@@ -32,6 +32,7 @@
 #include "Editor.h"
 #include "FloatRect.h"
 #include "FrameView.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLFormControlsCollection.h"
 #include "HTMLOptionsCollection.h"
 #include "HTMLTableRowsCollection.h"
@@ -902,7 +903,7 @@ RefPtr<RadioNodeList> ContainerNode::radioNodeList(const AtomicString& name)
 
 Ref<HTMLCollection> ContainerNode::children()
 {
-    return ensureCachedHTMLCollection(NodeChildren);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<NodeChildren>::traversalType>>(*this, NodeChildren);
 }
 
 Element* ContainerNode::firstElementChild() const
@@ -939,22 +940,6 @@ void ContainerNode::prepend(Vector<NodeOrString>&& nodeOrStringVector, Exception
     insertBefore(node.release(), firstChild(), ec);
 }
 
-Ref<HTMLCollection> ContainerNode::ensureCachedHTMLCollection(CollectionType type)
-{
-    if (HTMLCollection* collection = cachedHTMLCollection(type))
-        return *collection;
-
-    if (type == TableRows)
-        return ensureRareData().ensureNodeLists().addCachedCollection<HTMLTableRowsCollection>(downcast<HTMLTableElement>(*this), type);
-    else if (type == SelectOptions)
-        return ensureRareData().ensureNodeLists().addCachedCollection<HTMLOptionsCollection>(downcast<HTMLSelectElement>(*this), type);
-    else if (type == FormControls) {
-        ASSERT(hasTagName(HTMLNames::formTag) || hasTagName(HTMLNames::fieldsetTag));
-        return ensureRareData().ensureNodeLists().addCachedCollection<HTMLFormControlsCollection>(*this, type);
-    }
-    return ensureRareData().ensureNodeLists().addCachedCollection<HTMLCollection>(*this, type);
-}
-
 HTMLCollection* ContainerNode::cachedHTMLCollection(CollectionType type)
 {
     return hasRareData() && rareData()->nodeLists() ? rareData()->nodeLists()->cachedCollection<HTMLCollection>(type) : nullptr;
index da0621d..05b3fca 100644 (file)
@@ -169,7 +169,6 @@ protected:
     void setFirstChild(Node* child) { m_firstChild = child; }
     void setLastChild(Node* child) { m_lastChild = child; }
 
-    Ref<HTMLCollection> ensureCachedHTMLCollection(CollectionType);
     HTMLCollection* cachedHTMLCollection(CollectionType);
 
 private:
index 9dec6c8..d128a21 100644 (file)
 #include "FrameLoader.h"
 #include "FrameLoaderClient.h"
 #include "FrameView.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLAllCollection.h"
 #include "HTMLAnchorElement.h"
 #include "HTMLBaseElement.h"
 #include "HTMLBodyElement.h"
 #include "HTMLCanvasElement.h"
-#include "HTMLCollection.h"
 #include "HTMLDocument.h"
 #include "HTMLElementFactory.h"
 #include "HTMLFormControlElement.h"
@@ -4772,50 +4772,51 @@ bool Document::hasSVGRootNode() const
     return documentElement() && documentElement()->hasTagName(SVGNames::svgTag);
 }
 
-Ref<HTMLCollection> Document::ensureCachedCollection(CollectionType type)
+template <CollectionType collectionType>
+Ref<HTMLCollection> Document::ensureCachedCollection()
 {
-    return ensureRareData().ensureNodeLists().addCachedCollection<HTMLCollection>(*this, type);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<collectionType>::traversalType>>(*this, collectionType);
 }
 
 Ref<HTMLCollection> Document::images()
 {
-    return ensureCachedCollection(DocImages);
+    return ensureCachedCollection<DocImages>();
 }
 
 Ref<HTMLCollection> Document::applets()
 {
-    return ensureCachedCollection(DocApplets);
+    return ensureCachedCollection<DocApplets>();
 }
 
 Ref<HTMLCollection> Document::embeds()
 {
-    return ensureCachedCollection(DocEmbeds);
+    return ensureCachedCollection<DocEmbeds>();
 }
 
 Ref<HTMLCollection> Document::plugins()
 {
     // This is an alias for embeds() required for the JS DOM bindings.
-    return ensureCachedCollection(DocEmbeds);
+    return ensureCachedCollection<DocEmbeds>();
 }
 
 Ref<HTMLCollection> Document::scripts()
 {
-    return ensureCachedCollection(DocScripts);
+    return ensureCachedCollection<DocScripts>();
 }
 
 Ref<HTMLCollection> Document::links()
 {
-    return ensureCachedCollection(DocLinks);
+    return ensureCachedCollection<DocLinks>();
 }
 
 Ref<HTMLCollection> Document::forms()
 {
-    return ensureCachedCollection(DocForms);
+    return ensureCachedCollection<DocForms>();
 }
 
 Ref<HTMLCollection> Document::anchors()
 {
-    return ensureCachedCollection(DocAnchors);
+    return ensureCachedCollection<DocAnchors>();
 }
 
 Ref<HTMLCollection> Document::all()
index 80fe7a4..e53bf3e 100644 (file)
@@ -113,7 +113,6 @@ class HTMLIFrameElement;
 class HTMLImageElement;
 class HTMLMapElement;
 class HTMLMediaElement;
-class HTMLNameCollection;
 class HTMLScriptElement;
 class HitTestRequest;
 class HitTestResult;
@@ -1345,7 +1344,8 @@ private:
 
     Node* nodeFromPoint(const LayoutPoint& clientPoint, LayoutPoint* localPoint = nullptr);
 
-    Ref<HTMLCollection> ensureCachedCollection(CollectionType);
+    template <CollectionType collectionType>
+    Ref<HTMLCollection> ensureCachedCollection();
 
 #if ENABLE(FULLSCREEN_API)
     void dispatchFullScreenChangeOrErrorEvent(Deque<RefPtr<Node>>&, const AtomicString& eventName, bool shouldNotifyMediaElement);
index 94cd313..1a946bb 100644 (file)
@@ -41,6 +41,7 @@ public:
 
     ElementChildIterator(const ContainerNode& parent);
     ElementChildIterator(const ContainerNode& parent, ElementType* current);
+    ElementChildIterator& operator--();
     ElementChildIterator& operator++();
 };
 
@@ -55,6 +56,7 @@ public:
 
     ElementChildConstIterator(const ContainerNode& parent);
     ElementChildConstIterator(const ContainerNode& parent, const ElementType* current);
+    ElementChildConstIterator& operator--();
     ElementChildConstIterator& operator++();
 };
 
@@ -108,6 +110,12 @@ inline ElementChildIterator<ElementType>::ElementChildIterator(const ContainerNo
 }
 
 template <typename ElementType>
+inline ElementChildIterator<ElementType>& ElementChildIterator<ElementType>::operator--()
+{
+    return static_cast<ElementChildIterator<ElementType>&>(ElementIterator<ElementType>::traversePreviousSibling());
+}
+
+template <typename ElementType>
 inline ElementChildIterator<ElementType>& ElementChildIterator<ElementType>::operator++()
 {
     return static_cast<ElementChildIterator<ElementType>&>(ElementIterator<ElementType>::traverseNextSibling());
@@ -128,6 +136,13 @@ inline ElementChildConstIterator<ElementType>::ElementChildConstIterator(const C
 }
 
 template <typename ElementType>
+inline ElementChildConstIterator<ElementType>& ElementChildConstIterator<ElementType>::operator--()
+{
+    return static_cast<ElementChildConstIterator<ElementType>&>(ElementConstIterator<ElementType>::traversePreviousSibling());
+}
+
+
+template <typename ElementType>
 inline ElementChildConstIterator<ElementType>& ElementChildConstIterator<ElementType>::operator++()
 {
     return static_cast<ElementChildConstIterator<ElementType>&>(ElementConstIterator<ElementType>::traverseNextSibling());
index 196e50b..0104266 100644 (file)
@@ -25,6 +25,7 @@
 #define LiveNodeList_h
 
 #include "CollectionIndexCache.h"
+#include "CollectionTraversal.h"
 #include "CollectionType.h"
 #include "Document.h"
 #include "ElementDescendantIterator.h"
@@ -80,25 +81,28 @@ class CachedLiveNodeList : public LiveNodeList {
 public:
     virtual ~CachedLiveNodeList();
 
-    virtual unsigned length() const override final;
-    virtual Node* item(unsigned offset) const override final;
+    unsigned length() const override final { return m_indexCache.nodeCount(nodeList()); }
+    Node* item(unsigned offset) const override final { return m_indexCache.nodeAt(nodeList(), offset); }
 
     // For CollectionIndexCache
-    ElementDescendantIterator collectionBegin() const;
-    ElementDescendantIterator collectionLast() const;
+    ElementDescendantIterator collectionBegin() const { return CollectionTraversal<CollectionTraversalType::Descendants>::begin(nodeList(), rootNode()); }
+    ElementDescendantIterator collectionLast() const { return CollectionTraversal<CollectionTraversalType::Descendants>::last(nodeList(), rootNode()); }
     ElementDescendantIterator collectionEnd() const { return ElementDescendantIterator(); }
-    void collectionTraverseForward(ElementDescendantIterator&, unsigned count, unsigned& traversedCount) const;
-    void collectionTraverseBackward(ElementDescendantIterator&, unsigned count) const;
+    void collectionTraverseForward(ElementDescendantIterator& current, unsigned count, unsigned& traversedCount) const { CollectionTraversal<CollectionTraversalType::Descendants>::traverseForward(nodeList(), current, count, traversedCount); }
+    void collectionTraverseBackward(ElementDescendantIterator& current, unsigned count) const { CollectionTraversal<CollectionTraversalType::Descendants>::traverseBackward(nodeList(), current, count); }
     bool collectionCanTraverseBackward() const { return true; }
-    void willValidateIndexCache() const;
+    void willValidateIndexCache() const { document().registerNodeListForInvalidation(const_cast<CachedLiveNodeList<NodeListType>&>(*this)); }
 
     virtual void invalidateCache(Document&) const override final;
-    virtual size_t memoryCost() const override final;
+    virtual size_t memoryCost() const override final { return m_indexCache.memoryCost(); }
 
 protected:
     CachedLiveNodeList(ContainerNode& rootNode, NodeListInvalidationType);
 
 private:
+    NodeListType& nodeList() { return static_cast<NodeListType&>(*this); }
+    const NodeListType& nodeList() const { return static_cast<const NodeListType&>(*this); }
+
     ContainerNode& rootNode() const;
 
     mutable CollectionIndexCache<NodeListType, ElementDescendantIterator> m_indexCache;
@@ -131,115 +135,33 @@ ALWAYS_INLINE bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationTyp
 template <class NodeListType>
 CachedLiveNodeList<NodeListType>::CachedLiveNodeList(ContainerNode& ownerNode, NodeListInvalidationType invalidationType)
     : LiveNodeList(ownerNode, invalidationType)
-    , m_indexCache(static_cast<NodeListType&>(*this))
+    , m_indexCache(nodeList())
 {
 }
 
 template <class NodeListType>
 CachedLiveNodeList<NodeListType>::~CachedLiveNodeList()
 {
-    auto& nodeList = static_cast<const NodeListType&>(*this);
-    if (m_indexCache.hasValidCache(nodeList))
+    if (m_indexCache.hasValidCache(nodeList()))
         document().unregisterNodeListForInvalidation(*this);
 }
 
 template <class NodeListType>
 inline ContainerNode& CachedLiveNodeList<NodeListType>::rootNode() const
 {
-    if (static_cast<const NodeListType&>(*this).isRootedAtDocument() && ownerNode().inDocument())
+    if (nodeList().isRootedAtDocument() && ownerNode().inDocument())
         return ownerNode().document();
 
     return ownerNode();
 }
 
 template <class NodeListType>
-ElementDescendantIterator CachedLiveNodeList<NodeListType>::collectionBegin() const
-{
-    auto& nodeList = static_cast<const NodeListType&>(*this);
-    auto descendants = elementDescendants(rootNode());
-    auto end = descendants.end();
-    for (auto it = descendants.begin(); it != end; ++it) {
-        if (nodeList.elementMatches(*it))
-            return it;
-    }
-    return end;
-}
-
-template <class NodeListType>
-ElementDescendantIterator CachedLiveNodeList<NodeListType>::collectionLast() const
-{
-    auto& nodeList = static_cast<const NodeListType&>(*this);
-    auto descendants = elementDescendants(rootNode());
-    auto end = descendants.end();
-    for (auto it = descendants.last(); it != end; --it) {
-        if (nodeList.elementMatches(*it))
-            return it;
-    }
-    return end;
-}
-
-template <class NodeListType>
-void CachedLiveNodeList<NodeListType>::collectionTraverseForward(ElementDescendantIterator& current, unsigned count, unsigned& traversedCount) const
-{
-    auto& nodeList = static_cast<const NodeListType&>(*this);
-    ASSERT(nodeList.elementMatches(*current));
-    auto end = collectionEnd();
-    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
-        do {
-            ++current;
-            if (current == end)
-                return;
-        } while (!nodeList.elementMatches(*current));
-    }
-}
-
-template <class NodeListType>
-void CachedLiveNodeList<NodeListType>::collectionTraverseBackward(ElementDescendantIterator& current, unsigned count) const
-{
-    auto& nodeList = static_cast<const NodeListType&>(*this);
-    ASSERT(nodeList.elementMatches(*current));
-    auto end = collectionEnd();
-    for (; count; --count) {
-        do {
-            --current;
-            if (current == end)
-                return;
-        } while (!nodeList.elementMatches(*current));
-    }
-}
-
-template <class NodeListType>
-void CachedLiveNodeList<NodeListType>::willValidateIndexCache() const
-{
-    document().registerNodeListForInvalidation(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
-}
-
-template <class NodeListType>
 void CachedLiveNodeList<NodeListType>::invalidateCache(Document& document) const
 {
-    auto& nodeList = static_cast<const NodeListType&>(*this);
-    if (!m_indexCache.hasValidCache(nodeList))
+    if (!m_indexCache.hasValidCache(nodeList()))
         return;
-    document.unregisterNodeListForInvalidation(const_cast<NodeListType&>(nodeList));
-    m_indexCache.invalidate(nodeList);
-}
-
-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();
+    document.unregisterNodeListForInvalidation(const_cast<NodeListType&>(nodeList()));
+    m_indexCache.invalidate(nodeList());
 }
 
 } // namespace WebCore
diff --git a/Source/WebCore/html/CachedHTMLCollection.h b/Source/WebCore/html/CachedHTMLCollection.h
new file mode 100644 (file)
index 0000000..8176020
--- /dev/null
@@ -0,0 +1,158 @@
+/*
+ * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``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 ITS 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 CachedHTMLCollection_h
+#define CachedHTMLCollection_h
+
+#include "CollectionTraversal.h"
+#include "HTMLCollection.h"
+#include "HTMLElement.h"
+
+namespace WebCore {
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+class CachedHTMLCollection : public HTMLCollection {
+public:
+    CachedHTMLCollection(ContainerNode& base, CollectionType);
+
+    virtual ~CachedHTMLCollection();
+
+    virtual unsigned length() const override final { return m_indexCache.nodeCount(collection()); }
+    virtual Element* item(unsigned offset) const override final { return m_indexCache.nodeAt(collection(), offset); }
+    virtual Element* namedItem(const AtomicString& name) const override;
+    virtual size_t memoryCost() const override final { return m_indexCache.memoryCost() + HTMLCollection::memoryCost(); }
+
+    // For CollectionIndexCache; do not use elsewhere.
+    using CollectionTraversalIterator = typename CollectionTraversal<traversalType>::Iterator;
+    CollectionTraversalIterator collectionBegin() const { return CollectionTraversal<traversalType>::begin(collection(), rootNode()); }
+    CollectionTraversalIterator collectionLast() const { return CollectionTraversal<traversalType>::last(collection(), rootNode()); }
+    CollectionTraversalIterator collectionEnd() const { return CollectionTraversal<traversalType>::end(rootNode()); }
+    void collectionTraverseForward(CollectionTraversalIterator& current, unsigned count, unsigned& traversedCount) const { CollectionTraversal<traversalType>::traverseForward(collection(), current, count, traversedCount); }
+    void collectionTraverseBackward(CollectionTraversalIterator& current, unsigned count) const { CollectionTraversal<traversalType>::traverseBackward(collection(), current, count); }
+    bool collectionCanTraverseBackward() const { return traversalType != CollectionTraversalType::CustomForwardOnly; }
+    void willValidateIndexCache() const { document().registerCollection(const_cast<CachedHTMLCollection<HTMLCollectionClass, traversalType>&>(*this)); }
+
+    virtual void invalidateCache(Document&) override;
+
+    bool elementMatches(Element&) const;
+
+private:
+    HTMLCollectionClass& collection() { return static_cast<HTMLCollectionClass&>(*this); }
+    const HTMLCollectionClass& collection() const { return static_cast<const HTMLCollectionClass&>(*this); }
+
+    mutable CollectionIndexCache<HTMLCollectionClass, CollectionTraversalIterator> m_indexCache;
+};
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+CachedHTMLCollection<HTMLCollectionClass, traversalType>::CachedHTMLCollection(ContainerNode& base, CollectionType collectionType)
+    : HTMLCollection(base, collectionType)
+    , m_indexCache(collection())
+{ }
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+CachedHTMLCollection<HTMLCollectionClass, traversalType>::~CachedHTMLCollection()
+{
+    if (m_indexCache.hasValidCache(collection()))
+        document().unregisterCollection(*this);
+}
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+void CachedHTMLCollection<HTMLCollectionClass, traversalType>::invalidateCache(Document& document)
+{
+    HTMLCollection::invalidateCache(document);
+    if (m_indexCache.hasValidCache(collection())) {
+        document.unregisterCollection(*this);
+        m_indexCache.invalidate(collection());
+    }
+}
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+bool CachedHTMLCollection<HTMLCollectionClass, traversalType>::elementMatches(Element&) const
+{
+    // We call the elementMatches() method directly on the subclass instead for performance.
+    ASSERT_NOT_REACHED();
+    return false;
+}
+
+static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement& element)
+{
+    // The document.all collection returns only certain types of elements by name,
+    // although it returns any type of element by id.
+    return element.hasTagName(HTMLNames::appletTag)
+        || element.hasTagName(HTMLNames::embedTag)
+        || element.hasTagName(HTMLNames::formTag)
+        || element.hasTagName(HTMLNames::imgTag)
+        || element.hasTagName(HTMLNames::inputTag)
+        || element.hasTagName(HTMLNames::objectTag)
+        || element.hasTagName(HTMLNames::selectTag);
+}
+
+static inline bool nameShouldBeVisibleInDocumentAll(Element& element)
+{
+    return is<HTMLElement>(element) && nameShouldBeVisibleInDocumentAll(downcast<HTMLElement>(element));
+}
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+Element* CachedHTMLCollection<HTMLCollectionClass, traversalType>::namedItem(const AtomicString& name) const
+{
+    // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
+    // This method first searches for an object with a matching id
+    // attribute. If a match is not found, the method then searches for an
+    // object with a matching name attribute, but only on those elements
+    // that are allowed a name attribute.
+
+    if (name.isEmpty())
+        return nullptr;
+
+    ContainerNode& root = rootNode();
+    if (traversalType != CollectionTraversalType::CustomForwardOnly && root.isInTreeScope()) {
+        Element* candidate = nullptr;
+
+        TreeScope& treeScope = root.treeScope();
+        if (treeScope.hasElementWithId(*name.impl())) {
+            if (!treeScope.containsMultipleElementsWithId(name))
+                candidate = treeScope.getElementById(name);
+        } else if (treeScope.hasElementWithName(*name.impl())) {
+            if (!treeScope.containsMultipleElementsWithName(name)) {
+                candidate = treeScope.getElementByName(name);
+                if (candidate && type() == DocAll && !nameShouldBeVisibleInDocumentAll(*candidate))
+                    candidate = nullptr;
+            }
+        } else
+            return nullptr;
+
+        if (candidate && collection().elementMatches(*candidate)) {
+            if (traversalType == CollectionTraversalType::ChildrenOnly ? candidate->parentNode() == &root : candidate->isDescendantOf(&root))
+                return candidate;
+        }
+    }
+
+    return namedItemSlow(name);
+}
+
+} // namespace WebCore
+
+#endif // CachedHTMLCollection_h
+
diff --git a/Source/WebCore/html/CollectionTraversal.h b/Source/WebCore/html/CollectionTraversal.h
new file mode 100644 (file)
index 0000000..dd7b92c
--- /dev/null
@@ -0,0 +1,236 @@
+/*
+ * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``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 ITS 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 CollectionTraversal_h
+#define CollectionTraversal_h
+
+#include "CollectionType.h"
+#include "ElementChildIterator.h"
+#include "ElementDescendantIterator.h"
+
+namespace WebCore {
+
+template <CollectionTraversalType traversalType>
+struct CollectionTraversal { };
+
+template <>
+struct CollectionTraversal<CollectionTraversalType::Descendants> {
+    using Iterator = ElementDescendantIterator;
+
+    static ElementDescendantIterator end(ContainerNode&) { return ElementDescendantIterator(); }
+
+    template <typename CollectionClass>
+    static ElementDescendantIterator begin(const CollectionClass&, ContainerNode& rootNode);
+
+    template <typename CollectionClass>
+    static ElementDescendantIterator last(const CollectionClass&, ContainerNode& rootNode);
+
+    template <typename CollectionClass>
+    static void traverseForward(const CollectionClass&, ElementDescendantIterator& current, unsigned count, unsigned& traversedCount);
+
+    template <typename CollectionClass>
+    static void traverseBackward(const CollectionClass&, ElementDescendantIterator& current, unsigned count);
+};
+
+template <typename CollectionClass>
+inline ElementDescendantIterator CollectionTraversal<CollectionTraversalType::Descendants>::begin(const CollectionClass& collection, ContainerNode& rootNode)
+{
+    auto descendants = elementDescendants(rootNode);
+    auto end = descendants.end();
+    for (auto it = descendants.begin(); it != end; ++it) {
+        if (collection.elementMatches(*it))
+            return it;
+    }
+    return end;
+}
+
+template <typename CollectionClass>
+inline ElementDescendantIterator CollectionTraversal<CollectionTraversalType::Descendants>::last(const CollectionClass& collection, ContainerNode& rootNode)
+{
+    auto descendants = elementDescendants(rootNode);
+    ElementDescendantIterator invalid;
+    for (auto it = descendants.last(); it != invalid; --it) {
+        if (collection.elementMatches(*it))
+            return it;
+    }
+    return invalid;
+}
+
+template <typename CollectionClass>
+inline void CollectionTraversal<CollectionTraversalType::Descendants>::traverseForward(const CollectionClass& collection, ElementDescendantIterator& current, unsigned count, unsigned& traversedCount)
+{
+    ASSERT(collection.elementMatches(*current));
+    ElementDescendantIterator invalid;
+    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+        do {
+            ++current;
+            if (current == invalid)
+                return;
+        } while (!collection.elementMatches(*current));
+    }
+}
+
+template <typename CollectionClass>
+inline void CollectionTraversal<CollectionTraversalType::Descendants>::traverseBackward(const CollectionClass& collection, ElementDescendantIterator& current, unsigned count)
+{
+    ASSERT(collection.elementMatches(*current));
+    ElementDescendantIterator invalid;
+    for (; count; --count) {
+        do {
+            --current;
+            if (current == invalid)
+                return;
+        } while (!collection.elementMatches(*current));
+    }
+}
+
+template <>
+struct CollectionTraversal<CollectionTraversalType::ChildrenOnly> {
+    using Iterator = ElementChildIterator<Element>;
+
+    static ElementChildIterator<Element> end(ContainerNode& rootNode) { return ElementChildIterator<Element>(rootNode); }
+
+    template <typename CollectionClass>
+    static ElementChildIterator<Element> begin(const CollectionClass&, ContainerNode& rootNode);
+
+    template <typename CollectionClass>
+    static ElementChildIterator<Element> last(const CollectionClass&, ContainerNode& rootNode);
+
+    template <typename CollectionClass>
+    static void traverseForward(const CollectionClass&, ElementChildIterator<Element>& current, unsigned count, unsigned& traversedCount);
+
+    template <typename CollectionClass>
+    static void traverseBackward(const CollectionClass&, ElementChildIterator<Element>& current, unsigned count);
+};
+
+template <typename CollectionClass>
+inline ElementChildIterator<Element> CollectionTraversal<CollectionTraversalType::ChildrenOnly>::begin(const CollectionClass& collection, ContainerNode& rootNode)
+{
+    auto children = childrenOfType<Element>(rootNode);
+    auto end = children.end();
+    for (auto it = children.begin(); it != end; ++it) {
+        if (collection.elementMatches(*it))
+            return it;
+    }
+    return end;
+}
+
+template <typename CollectionClass>
+inline ElementChildIterator<Element> CollectionTraversal<CollectionTraversalType::ChildrenOnly>::last(const CollectionClass& collection, ContainerNode& rootNode)
+{
+    auto children = childrenOfType<Element>(rootNode);
+    ElementChildIterator<Element> invalid(collection.rootNode());
+    ElementChildIterator<Element> last(rootNode, children.last());
+    for (auto it = last; it != invalid; --it) {
+        if (collection.elementMatches(*it))
+            return it;
+    }
+    return invalid;
+}
+
+template <typename CollectionClass>
+inline void CollectionTraversal<CollectionTraversalType::ChildrenOnly>::traverseForward(const CollectionClass& collection, ElementChildIterator<Element>& current, unsigned count, unsigned& traversedCount)
+{
+    ASSERT(collection.elementMatches(*current));
+    ElementChildIterator<Element> invalid(collection.rootNode());
+    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+        do {
+            ++current;
+            if (current == invalid)
+                return;
+        } while (!collection.elementMatches(*current));
+    }
+}
+
+template <typename CollectionClass>
+inline void CollectionTraversal<CollectionTraversalType::ChildrenOnly>::traverseBackward(const CollectionClass& collection, ElementChildIterator<Element>& current, unsigned count)
+{
+    ASSERT(collection.elementMatches(*current));
+    ElementChildIterator<Element> invalid(collection.rootNode());
+    for (; count; --count) {
+        do {
+            --current;
+            if (current == invalid)
+                return;
+        } while (!collection.elementMatches(*current));
+    }
+}
+
+template <>
+struct CollectionTraversal<CollectionTraversalType::CustomForwardOnly> {
+    using Iterator = Element*;
+
+    static Element* end(ContainerNode&) { return nullptr; }
+
+    template <typename CollectionClass>
+    static Element* begin(const CollectionClass&, ContainerNode&);
+
+    template <typename CollectionClass>
+    static Element* last(const CollectionClass&, ContainerNode&);
+
+    template <typename CollectionClass>
+    static void traverseForward(const CollectionClass&, Element*& current, unsigned count, unsigned& traversedCount);
+
+    template <typename CollectionClass>
+    static void traverseBackward(const CollectionClass&, Element*&, unsigned count);
+};
+
+template <typename CollectionClass>
+inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::begin(const CollectionClass& collection, ContainerNode&)
+{
+    return collection.customElementAfter(nullptr);
+}
+
+template <typename CollectionClass>
+inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::last(const CollectionClass&, ContainerNode&)
+{
+    ASSERT_NOT_REACHED();
+    return nullptr;
+}
+
+template <typename CollectionClass>
+inline void CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::traverseForward(const CollectionClass& collection, Element*& current, unsigned count, unsigned& traversedCount)
+{
+    Element* element = current;
+    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+        element = collection.customElementAfter(element);
+        if (!element) {
+            current = nullptr;
+            return;
+        }
+    }
+    current = element;
+}
+
+template <typename CollectionClass>
+inline void CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::traverseBackward(const CollectionClass&, Element*&, unsigned count)
+{
+    UNUSED_PARAM(count);
+    ASSERT_NOT_REACHED();
+}
+
+} // namespace WebCore
+
+#endif // CollectionTraversal_h
index 5130af9..1a922d0 100644 (file)
@@ -53,6 +53,42 @@ enum CollectionType {
     FormControls
 };
 
-} // namespace
+enum class CollectionTraversalType { Descendants, ChildrenOnly, CustomForwardOnly };
+template<CollectionType collectionType>
+struct CollectionTypeTraits {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::Descendants;
+};
+
+template<>
+struct CollectionTypeTraits<NodeChildren> {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::ChildrenOnly;
+};
+
+template<>
+struct CollectionTypeTraits<TRCells> {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::ChildrenOnly;
+};
+
+template<>
+struct CollectionTypeTraits<TSectionRows> {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::ChildrenOnly;
+};
+
+template<>
+struct CollectionTypeTraits<TableTBodies> {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::ChildrenOnly;
+};
+
+template<>
+struct CollectionTypeTraits<TableRows> {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::CustomForwardOnly;
+};
+
+template<>
+struct CollectionTypeTraits<FormControls> {
+    static const CollectionTraversalType traversalType = CollectionTraversalType::CustomForwardOnly;
+};
+
+} // namespace WebCore
 
 #endif
diff --git a/Source/WebCore/html/GenericCachedHTMLCollection.cpp b/Source/WebCore/html/GenericCachedHTMLCollection.cpp
new file mode 100644 (file)
index 0000000..b6bceda
--- /dev/null
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``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 ITS 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.
+ */
+
+#include "config.h"
+#include "GenericCachedHTMLCollection.h"
+
+#include "HTMLNames.h"
+#include "HTMLObjectElement.h"
+#include "HTMLOptionElement.h"
+
+namespace WebCore {
+
+using namespace HTMLNames;
+
+template <CollectionTraversalType traversalType>
+bool GenericCachedHTMLCollection<traversalType>::elementMatches(Element& element) const
+{
+    switch (this->type()) {
+    case NodeChildren:
+        return true;
+    case DocImages:
+        return element.hasTagName(imgTag);
+    case DocScripts:
+        return element.hasTagName(scriptTag);
+    case DocForms:
+        return element.hasTagName(formTag);
+    case TableTBodies:
+        return element.hasTagName(tbodyTag);
+    case TRCells:
+        return element.hasTagName(tdTag) || element.hasTagName(thTag);
+    case TSectionRows:
+        return element.hasTagName(trTag);
+    case SelectedOptions:
+        return is<HTMLOptionElement>(element) && downcast<HTMLOptionElement>(element).selected();
+    case DataListOptions:
+        if (is<HTMLOptionElement>(element)) {
+            HTMLOptionElement& option = downcast<HTMLOptionElement>(element);
+            if (!option.isDisabledFormControl() && !option.value().isEmpty())
+                return true;
+        }
+        return false;
+    case MapAreas:
+        return element.hasTagName(areaTag);
+    case DocApplets:
+        return is<HTMLAppletElement>(element) || (is<HTMLObjectElement>(element) && downcast<HTMLObjectElement>(element).containsJavaApplet());
+    case DocEmbeds:
+        return element.hasTagName(embedTag);
+    case DocLinks:
+        return (element.hasTagName(aTag) || element.hasTagName(areaTag)) && element.fastHasAttribute(hrefAttr);
+    case DocAnchors:
+        return element.hasTagName(aTag) && element.fastHasAttribute(nameAttr);
+    case DocAll:
+    case DocumentNamedItems:
+    case FormControls:
+    case SelectOptions:
+    case TableRows:
+    case WindowNamedItems:
+        break;
+    }
+    // Remaining collection types have their own CachedHTMLCollection subclasses and are not using GenericCachedHTMLCollection.
+    ASSERT_NOT_REACHED();
+    return false;
+}
+template bool GenericCachedHTMLCollection<CollectionTraversalType::Descendants>::elementMatches(Element&) const;
+template bool GenericCachedHTMLCollection<CollectionTraversalType::ChildrenOnly>::elementMatches(Element&) const;
+
+} // namespace WebCore
diff --git a/Source/WebCore/html/GenericCachedHTMLCollection.h b/Source/WebCore/html/GenericCachedHTMLCollection.h
new file mode 100644 (file)
index 0000000..c633133
--- /dev/null
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``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 ITS 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 GenericCachedHTMLCollection_h
+#define GenericCachedHTMLCollection_h
+
+#include "CachedHTMLCollection.h"
+
+namespace WebCore {
+
+template <CollectionTraversalType traversalType>
+class GenericCachedHTMLCollection final : public CachedHTMLCollection<GenericCachedHTMLCollection<traversalType>, traversalType> {
+public:
+    static Ref<GenericCachedHTMLCollection> create(ContainerNode& base, CollectionType collectionType)
+    {
+        return adoptRef(*new GenericCachedHTMLCollection(base, collectionType));
+    }
+
+    bool elementMatches(Element&) const;
+
+private:
+    GenericCachedHTMLCollection(ContainerNode& base, CollectionType collectionType)
+        : CachedHTMLCollection<GenericCachedHTMLCollection<traversalType>, traversalType>(base, collectionType)
+    { }
+};
+
+} // namespace WebCore
+
+#endif // GenericCachedHTMLCollection_h
+
index 0166871..dab0500 100644 (file)
@@ -36,7 +36,7 @@ Ref<HTMLAllCollection> HTMLAllCollection::create(Document& document, CollectionT
 }
 
 inline HTMLAllCollection::HTMLAllCollection(Document& document, CollectionType type)
-    : HTMLCollection(document, type)
+    : CachedHTMLCollection<HTMLAllCollection, CollectionTypeTraits<DocAll>::traversalType>(document, type)
 {
 }
 
index 5145117..b6011b4 100644 (file)
 #ifndef HTMLAllCollection_h
 #define HTMLAllCollection_h
 
-#include "HTMLCollection.h"
+#include "CachedHTMLCollection.h"
 
 namespace WebCore {
 
-class HTMLAllCollection final : public HTMLCollection {
+class HTMLAllCollection final : public CachedHTMLCollection<HTMLAllCollection, CollectionTypeTraits<DocAll>::traversalType> {
 public:
     static Ref<HTMLAllCollection> create(Document&, CollectionType);
 
     Element* namedItemWithIndex(const AtomicString& name, unsigned index) const;
 
+    // For CachedHTMLCollection.
+    bool elementMatches(Element&) const { return true; }
+
 private:
     HTMLAllCollection(Document&, CollectionType);
 };
index 3b4b62f..1182cfb 100644 (file)
 #include "config.h"
 #include "HTMLCollection.h"
 
-#include "ElementTraversal.h"
-#include "HTMLDocument.h"
-#include "HTMLNameCollection.h"
+#include "CachedHTMLCollection.h"
 #include "HTMLNames.h"
-#include "HTMLObjectElement.h"
-#include "HTMLOptionElement.h"
 #include "NodeRareData.h"
 
 namespace WebCore {
 
 using namespace HTMLNames;
 
-static bool shouldOnlyIncludeDirectChildren(CollectionType type)
-{
-    switch (type) {
-    case DocAll:
-    case DocAnchors:
-    case DocApplets:
-    case DocEmbeds:
-    case DocForms:
-    case DocImages:
-    case DocLinks:
-    case DocScripts:
-    case DocumentNamedItems:
-    case MapAreas:
-    case TableRows:
-    case SelectOptions:
-    case SelectedOptions:
-    case DataListOptions:
-    case WindowNamedItems:
-    case FormControls:
-        return false;
-    case NodeChildren:
-    case TRCells:
-    case TSectionRows:
-    case TableTBodies:
-        return true;
-    }
-    ASSERT_NOT_REACHED();
-    return false;
-}
-
 inline auto HTMLCollection::rootTypeFromCollectionType(CollectionType type) -> RootType
 {
     switch (type) {
@@ -131,262 +97,29 @@ static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(Col
     return DoNotInvalidateOnAttributeChanges;
 }
 
-HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType)
+HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type)
     : m_ownerNode(ownerNode)
-    , m_indexCache(*this)
     , m_collectionType(type)
     , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
     , m_rootType(rootTypeFromCollectionType(type))
-    , m_shouldOnlyIncludeDirectChildren(shouldOnlyIncludeDirectChildren(type))
-    , m_usesCustomForwardOnlyTraversal(traversalType == CustomForwardOnlyTraversal)
 {
     ASSERT(m_rootType == static_cast<unsigned>(rootTypeFromCollectionType(type)));
     ASSERT(m_invalidationType == static_cast<unsigned>(invalidationTypeExcludingIdAndNameAttributes(type)));
     ASSERT(m_collectionType == static_cast<unsigned>(type));
 }
 
-Ref<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
-{
-    return adoptRef(*new HTMLCollection(base, type));
-}
-
 HTMLCollection::~HTMLCollection()
 {
-    if (m_indexCache.hasValidCache(*this))
-        document().unregisterCollection(*this);
     if (hasNamedElementCache())
         document().collectionWillClearIdNameMap(*this);
+
     // HTMLNameCollection removes cache by itself.
     if (type() != WindowNamedItems && type() != DocumentNamedItems)
         ownerNode().nodeLists()->removeCachedCollection(this);
 }
 
-ContainerNode& HTMLCollection::rootNode() const
-{
-    if (isRootedAtDocument() && ownerNode().inDocument())
-        return ownerNode().document();
-
-    return ownerNode();
-}
-
-static inline bool isMatchingHTMLElement(const HTMLCollection& collection, HTMLElement& element)
+void HTMLCollection::invalidateCache(Document& document)
 {
-    switch (collection.type()) {
-    case DocImages:
-        return element.hasTagName(imgTag);
-    case DocScripts:
-        return element.hasTagName(scriptTag);
-    case DocForms:
-        return element.hasTagName(formTag);
-    case TableTBodies:
-        return element.hasTagName(tbodyTag);
-    case TRCells:
-        return element.hasTagName(tdTag) || element.hasTagName(thTag);
-    case TSectionRows:
-        return element.hasTagName(trTag);
-    case SelectOptions:
-        return element.hasTagName(optionTag);
-    case SelectedOptions:
-        return is<HTMLOptionElement>(element) && downcast<HTMLOptionElement>(element).selected();
-    case DataListOptions:
-        if (is<HTMLOptionElement>(element)) {
-            HTMLOptionElement& option = downcast<HTMLOptionElement>(element);
-            if (!option.isDisabledFormControl() && !option.value().isEmpty())
-                return true;
-        }
-        return false;
-    case MapAreas:
-        return element.hasTagName(areaTag);
-    case DocApplets:
-        return is<HTMLAppletElement>(element) || (is<HTMLObjectElement>(element) && downcast<HTMLObjectElement>(element).containsJavaApplet());
-    case DocEmbeds:
-        return element.hasTagName(embedTag);
-    case DocLinks:
-        return (element.hasTagName(aTag) || element.hasTagName(areaTag)) && element.fastHasAttribute(hrefAttr);
-    case DocAnchors:
-        return element.hasTagName(aTag) && element.fastHasAttribute(nameAttr);
-    case DocumentNamedItems:
-        return downcast<DocumentNameCollection>(collection).elementMatches(element);
-    case DocAll:
-    case NodeChildren:
-    case WindowNamedItems:
-    case FormControls:
-    case TableRows:
-        break;
-    }
-    ASSERT_NOT_REACHED();
-    return false;
-}
-
-static inline bool isMatchingElement(const HTMLCollection& collection, Element& element)
-{
-    // Collection types that deal with any type of Elements, not just HTMLElements.
-    switch (collection.type()) {
-    case DocAll:
-    case NodeChildren:
-        return true;
-    case WindowNamedItems:
-        return downcast<WindowNameCollection>(collection).elementMatches(element);
-    default:
-        // Collection types that only deal with HTMLElements.
-        return is<HTMLElement>(element) && isMatchingHTMLElement(collection, downcast<HTMLElement>(element));
-    }
-}
-
-static inline Element* previousElement(ContainerNode& base, Element& element, bool onlyIncludeDirectChildren)
-{
-    return onlyIncludeDirectChildren ? ElementTraversal::previousSibling(element) : ElementTraversal::previous(element, &base);
-}
-
-ALWAYS_INLINE Element* HTMLCollection::iterateForPreviousElement(Element* element) const
-{
-    bool onlyIncludeDirectChildren = m_shouldOnlyIncludeDirectChildren;
-    ContainerNode& rootNode = this->rootNode();
-    for (; element; element = previousElement(rootNode, *element, onlyIncludeDirectChildren)) {
-        if (isMatchingElement(*this, *element))
-            return element;
-    }
-    return nullptr;
-}
-
-static inline Element* firstMatchingElement(const HTMLCollection& collection, ContainerNode& root)
-{
-    Element* element = ElementTraversal::firstWithin(root);
-    while (element && !isMatchingElement(collection, *element))
-        element = ElementTraversal::next(*element, &root);
-    return element;
-}
-
-static inline Element* nextMatchingElement(const HTMLCollection& collection, Element& element, ContainerNode& root)
-{
-    Element* next = &element;
-    do {
-        next = ElementTraversal::next(*next, &root);
-    } while (next && !isMatchingElement(collection, *next));
-    return next;
-}
-
-unsigned HTMLCollection::length() const
-{
-    return m_indexCache.nodeCount(*this);
-}
-
-Element* HTMLCollection::item(unsigned offset) const
-{
-    return m_indexCache.nodeAt(*this, offset);
-}
-
-static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement& element)
-{
-    // The document.all collection returns only certain types of elements by name,
-    // although it returns any type of element by id.
-    return element.hasTagName(appletTag)
-        || element.hasTagName(embedTag)
-        || element.hasTagName(formTag)
-        || element.hasTagName(imgTag)
-        || element.hasTagName(inputTag)
-        || element.hasTagName(objectTag)
-        || element.hasTagName(selectTag);
-}
-
-static inline bool nameShouldBeVisibleInDocumentAll(Element& element)
-{
-    return is<HTMLElement>(element) && nameShouldBeVisibleInDocumentAll(downcast<HTMLElement>(element));
-}
-
-static inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, ContainerNode& root)
-{
-    Element* element = ElementTraversal::firstWithin(root);
-    while (element && !isMatchingElement(nodeList, *element))
-        element = ElementTraversal::nextSibling(*element);
-    return element;
-}
-
-static inline Element* nextMatchingSiblingElement(const HTMLCollection& nodeList, Element& element)
-{
-    Element* next = &element;
-    do {
-        next = ElementTraversal::nextSibling(*next);
-    } while (next && !isMatchingElement(nodeList, *next));
-    return next;
-}
-
-inline bool HTMLCollection::usesCustomForwardOnlyTraversal() const
-{
-    return m_usesCustomForwardOnlyTraversal;
-}
-
-inline Element* HTMLCollection::firstElement(ContainerNode& root) const
-{
-    if (usesCustomForwardOnlyTraversal())
-        return customElementAfter(nullptr);
-    if (m_shouldOnlyIncludeDirectChildren)
-        return firstMatchingChildElement(*this, root);
-    return firstMatchingElement(*this, root);
-}
-
-inline Element* HTMLCollection::traverseForward(Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root) const
-{
-    Element* element = &current;
-    if (usesCustomForwardOnlyTraversal()) {
-        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
-            element = customElementAfter(element);
-            if (!element)
-                return nullptr;
-        }
-    } else if (m_shouldOnlyIncludeDirectChildren) {
-        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
-            element = nextMatchingSiblingElement(*this, *element);
-            if (!element)
-                return nullptr;
-        }
-    } else {
-        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
-            element = nextMatchingElement(*this, *element, root);
-            if (!element)
-                return nullptr;
-        }
-    }
-    return element;
-}
-
-Element* HTMLCollection::collectionBegin() const
-{
-    return firstElement(rootNode());
-}
-
-Element* HTMLCollection::collectionLast() const
-{
-    // FIXME: This should be optimized similarly to the forward case.
-    auto& root = rootNode();
-    Element* last = m_shouldOnlyIncludeDirectChildren ? ElementTraversal::lastChild(root) : ElementTraversal::lastWithin(root);
-    return iterateForPreviousElement(last);
-}
-
-void HTMLCollection::collectionTraverseForward(Element*& current, unsigned count, unsigned& traversedCount) const
-{
-    current = traverseForward(*current, count, traversedCount, rootNode());
-}
-
-void HTMLCollection::collectionTraverseBackward(Element*& current, unsigned count) const
-{
-    // FIXME: This should be optimized similarly to the forward case.
-    if (m_shouldOnlyIncludeDirectChildren) {
-        for (; count && current; --count)
-            current = iterateForPreviousElement(ElementTraversal::previousSibling(*current));
-        return;
-    }
-    auto& root = rootNode();
-    for (; count && current; --count)
-        current = iterateForPreviousElement(ElementTraversal::previous(*current, &root));
-}
-
-void HTMLCollection::invalidateCache(Document& document) const
-{
-    if (m_indexCache.hasValidCache(*this)) {
-        document.unregisterCollection(const_cast<HTMLCollection&>(*this));
-        m_indexCache.invalidate(*this);
-    }
     if (hasNamedElementCache())
         invalidateNamedElementCache(document);
 }
@@ -398,40 +131,8 @@ void HTMLCollection::invalidateNamedElementCache(Document& document) const
     m_namedElementCache = nullptr;
 }
 
-Element* HTMLCollection::namedItem(const AtomicString& name) const
+Element* HTMLCollection::namedItemSlow(const AtomicString& name) const
 {
-    // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
-    // This method first searches for an object with a matching id
-    // attribute. If a match is not found, the method then searches for an
-    // object with a matching name attribute, but only on those elements
-    // that are allowed a name attribute.
-
-    if (name.isEmpty())
-        return nullptr;
-
-    ContainerNode& root = rootNode();
-    if (!usesCustomForwardOnlyTraversal() && root.isInTreeScope()) {
-        Element* candidate = nullptr;
-
-        TreeScope& treeScope = root.treeScope();
-        if (treeScope.hasElementWithId(*name.impl())) {
-            if (!treeScope.containsMultipleElementsWithId(name))
-                candidate = treeScope.getElementById(name);
-        } else if (treeScope.hasElementWithName(*name.impl())) {
-            if (!treeScope.containsMultipleElementsWithName(name)) {
-                candidate = treeScope.getElementByName(name);
-                if (candidate && type() == DocAll && !nameShouldBeVisibleInDocumentAll(*candidate))
-                    candidate = nullptr;
-            }
-        } else
-            return nullptr;
-
-        if (candidate && isMatchingElement(*this, *candidate)) {
-            if (m_shouldOnlyIncludeDirectChildren ? candidate->parentNode() == &root : candidate->isDescendantOf(&root))
-                return candidate;
-        }
-    }
-
     // The pathological case. We need to walk the entire subtree.
     updateNamedElementCache();
     ASSERT(m_namedElementCache);
@@ -456,9 +157,9 @@ void HTMLCollection::updateNamedElementCache() const
 
     auto cache = std::make_unique<CollectionNamedElementCache>();
 
-    unsigned size = m_indexCache.nodeCount(*this);
+    unsigned size = length();
     for (unsigned i = 0; i < size; ++i) {
-        Element& element = *m_indexCache.nodeAt(*this, i);
+        Element& element = *item(i);
         const AtomicString& id = element.getIdAttribute();
         if (!id.isEmpty())
             cache->appendToIdCache(id, element);
@@ -513,10 +214,4 @@ PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
     return ownerNode().getElementsByTagName(name);
 }
 
-Element* HTMLCollection::customElementAfter(Element*) const
-{
-    ASSERT_NOT_REACHED();
-    return nullptr;
-}
-
 } // namespace WebCore
index 4714e90..b42061a 100644 (file)
@@ -60,57 +60,39 @@ private:
 
 class HTMLCollection : public ScriptWrappable, public RefCounted<HTMLCollection> {
 public:
-    static Ref<HTMLCollection> create(ContainerNode& base, CollectionType);
     virtual ~HTMLCollection();
 
     // DOM API
-    unsigned length() const;
-    Element* item(unsigned offset) const;
-    virtual Element* namedItem(const AtomicString& name) const;
+    virtual unsigned length() const = 0;
+    virtual Element* item(unsigned offset) const = 0;
+    virtual Element* namedItem(const AtomicString& name) const = 0;
     PassRefPtr<NodeList> tags(const String&);
 
     // Non-DOM API
     bool hasNamedItem(const AtomicString& name) const;
     Vector<Ref<Element>> namedItems(const AtomicString& name) const;
-    size_t memoryCost() const;
+    virtual size_t memoryCost() const;
 
     bool isRootedAtDocument() const;
     NodeListInvalidationType invalidationType() const;
     CollectionType type() const;
     ContainerNode& ownerNode() const;
-    void invalidateCache(const QualifiedName* attributeName) const;
-    virtual void invalidateCache(Document&) const;
-
-    // For CollectionIndexCache; do not use elsewhere.
-    Element* collectionBegin() const;
-    Element* collectionLast() const;
-    Element* collectionEnd() const;
-    void collectionTraverseForward(Element*&, unsigned count, unsigned& traversedCount) const;
-    void collectionTraverseBackward(Element*&, unsigned count) const;
-    bool collectionCanTraverseBackward() const;
-    void willValidateIndexCache() const;
+    ContainerNode& rootNode() const;
+    void invalidateCache(const QualifiedName* attributeName);
+    virtual void invalidateCache(Document&);
 
     bool hasNamedElementCache() const;
 
 protected:
-    enum ElementTraversalType { NormalTraversal, CustomForwardOnlyTraversal };
-    HTMLCollection(ContainerNode& base, CollectionType, ElementTraversalType = NormalTraversal);
+    HTMLCollection(ContainerNode& base, CollectionType);
 
     virtual void updateNamedElementCache() const;
+    Element* namedItemSlow(const AtomicString& name) const;
 
     void setNamedItemCache(std::unique_ptr<CollectionNamedElementCache>) const;
     const CollectionNamedElementCache& namedItemCaches() const;
 
-private:
     Document& document() const;
-    ContainerNode& rootNode() const;
-    bool usesCustomForwardOnlyTraversal() const;
-
-    Element* iterateForPreviousElement(Element*) const;
-    Element* firstElement(ContainerNode& root) const;
-    Element* traverseForward(Element&, unsigned count, unsigned& traversedCount, ContainerNode& root) const;
-
-    virtual Element* customElementAfter(Element*) const;
 
     void invalidateNamedElementCache(Document&) const;
 
@@ -119,16 +101,21 @@ private:
 
     Ref<ContainerNode> m_ownerNode;
 
-    mutable CollectionIndexCache<HTMLCollection, Element*> m_indexCache;
     mutable std::unique_ptr<CollectionNamedElementCache> m_namedElementCache;
 
     const unsigned m_collectionType : 5;
     const unsigned m_invalidationType : 4;
     const unsigned m_rootType : 1;
-    const unsigned m_shouldOnlyIncludeDirectChildren : 1;
-    const unsigned m_usesCustomForwardOnlyTraversal : 1;
 };
 
+inline ContainerNode& HTMLCollection::rootNode() const
+{
+    if (isRootedAtDocument() && ownerNode().inDocument())
+        return ownerNode().document();
+
+    return ownerNode();
+}
+
 inline const Vector<Element*>* CollectionNamedElementCache::findElementsWithId(const AtomicString& id) const
 {
     return find(m_idMap, id);
@@ -177,7 +164,7 @@ inline void CollectionNamedElementCache::append(StringToElementsMap& map, const
 
 inline size_t HTMLCollection::memoryCost() const
 {
-    return m_indexCache.memoryCost() + (m_namedElementCache ? m_namedElementCache->memoryCost() : 0);
+    return m_namedElementCache ? m_namedElementCache->memoryCost() : 0;
 }
 
 inline bool HTMLCollection::isRootedAtDocument() const
@@ -205,7 +192,7 @@ inline Document& HTMLCollection::document() const
     return m_ownerNode->document();
 }
 
-inline void HTMLCollection::invalidateCache(const QualifiedName* attributeName) const
+inline void HTMLCollection::invalidateCache(const QualifiedName* attributeName)
 {
     if (!attributeName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attributeName))
         invalidateCache(document());
@@ -213,21 +200,6 @@ inline void HTMLCollection::invalidateCache(const QualifiedName* attributeName)
         invalidateNamedElementCache(document());
 }
 
-inline Element* HTMLCollection::collectionEnd() const
-{
-    return nullptr;
-}
-
-inline bool HTMLCollection::collectionCanTraverseBackward() const
-{
-    return !m_usesCustomForwardOnlyTraversal;
-}
-
-inline void HTMLCollection::willValidateIndexCache() const
-{
-    document().registerCollection(const_cast<HTMLCollection&>(*this));
-}
-
 inline bool HTMLCollection::hasNamedElementCache() const
 {
     return !!m_namedElementCache;
index fe5e76f..2846547 100644 (file)
 #if ENABLE(DATALIST_ELEMENT)
 #include "HTMLDataListElement.h"
 
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLNames.h"
 #include "IdTargetObserverRegistry.h"
+#include "NodeRareData.h"
 
 namespace WebCore {
 
@@ -50,7 +52,7 @@ Ref<HTMLDataListElement> HTMLDataListElement::create(const QualifiedName& tagNam
 
 Ref<HTMLCollection> HTMLDataListElement::options()
 {
-    return ensureCachedHTMLCollection(DataListOptions);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<DataListOptions>::traversalType>>(*this, DataListOptions);
 }
 
 void HTMLDataListElement::optionElementChildrenChanged()
index ac332e8..400a0ba 100644 (file)
 #include "HTMLFieldSetElement.h"
 
 #include "ElementIterator.h"
-#include "HTMLCollection.h"
+#include "HTMLFormControlsCollection.h"
 #include "HTMLLegendElement.h"
 #include "HTMLNames.h"
 #include "HTMLObjectElement.h"
+#include "NodeRareData.h"
 #include "RenderFieldset.h"
 #include <wtf/StdLibExtras.h>
 
@@ -161,7 +162,7 @@ HTMLLegendElement* HTMLFieldSetElement::legend() const
 
 Ref<HTMLCollection> HTMLFieldSetElement::elements()
 {
-    return ensureCachedHTMLCollection(FormControls);
+    return ensureRareData().ensureNodeLists().addCachedCollection<HTMLFormControlsCollection>(*this, FormControls);
 }
 
 void HTMLFieldSetElement::refreshElementsIfNeeded() const
index 0deecc2..30250bb 100644 (file)
@@ -36,7 +36,7 @@ using namespace HTMLNames;
 // calculation every time if anything has changed.
 
 HTMLFormControlsCollection::HTMLFormControlsCollection(ContainerNode& ownerNode)
-    : HTMLCollection(ownerNode, FormControls, CustomForwardOnlyTraversal)
+    : CachedHTMLCollection<HTMLFormControlsCollection, CollectionTypeTraits<FormControls>::traversalType>(ownerNode, FormControls)
     , m_cachedElement(nullptr)
     , m_cachedElementOffsetInArray(0)
 {
@@ -177,9 +177,9 @@ void HTMLFormControlsCollection::updateNamedElementCache() const
     setNamedItemCache(WTF::move(cache));
 }
 
-void HTMLFormControlsCollection::invalidateCache(Document& document) const
+void HTMLFormControlsCollection::invalidateCache(Document& document)
 {
-    HTMLCollection::invalidateCache(document);
+    CachedHTMLCollection<HTMLFormControlsCollection, CollectionTypeTraits<FormControls>::traversalType>::invalidateCache(document);
     m_cachedElement = nullptr;
     m_cachedElementOffsetInArray = 0;
 }
index b168ad9..c0d520f 100644 (file)
@@ -23,7 +23,7 @@
 #ifndef HTMLFormControlsCollection_h
 #define HTMLFormControlsCollection_h
 
-#include "HTMLCollection.h"
+#include "CachedHTMLCollection.h"
 #include "HTMLElement.h"
 
 namespace WebCore {
@@ -34,21 +34,23 @@ class HTMLImageElement;
 // This class is just a big hack to find form elements even in malformed HTML elements.
 // The famous <table><tr><form><td> problem.
 
-class HTMLFormControlsCollection final : public HTMLCollection {
+class HTMLFormControlsCollection final : public CachedHTMLCollection<HTMLFormControlsCollection, CollectionTypeTraits<FormControls>::traversalType> {
 public:
     static Ref<HTMLFormControlsCollection> create(ContainerNode&, CollectionType);
     virtual ~HTMLFormControlsCollection();
 
+    // For CachedHTMLCollection.
+    Element* customElementAfter(Element*) const;
+
 private:
     explicit HTMLFormControlsCollection(ContainerNode&);
 
     virtual HTMLElement* namedItem(const AtomicString& name) const override;
-    virtual void invalidateCache(Document&) const override;
+    virtual void invalidateCache(Document&) override;
     virtual void updateNamedElementCache() const override;
 
     const Vector<FormAssociatedElement*>& formControlElements() const;
     const Vector<HTMLImageElement*>& formImageElements() const;
-    virtual Element* customElementAfter(Element*) const override;
 
     mutable Element* m_cachedElement;
     mutable unsigned m_cachedElementOffsetInArray;
index 5ffa3a8..054279f 100644 (file)
 #include "Frame.h"
 #include "FrameLoader.h"
 #include "FrameLoaderClient.h"
-#include "HTMLCollection.h"
+#include "HTMLFormControlsCollection.h"
 #include "HTMLImageElement.h"
 #include "HTMLInputElement.h"
 #include "HTMLNames.h"
 #include "HTMLTableElement.h"
+#include "NodeRareData.h"
 #include "Page.h"
 #include "RenderTextControl.h"
 #include "ScriptController.h"
@@ -638,7 +639,7 @@ void HTMLFormElement::removeImgElement(HTMLImageElement* e)
 
 Ref<HTMLCollection> HTMLFormElement::elements()
 {
-    return ensureCachedHTMLCollection(FormControls);
+    return ensureRareData().ensureNodeLists().addCachedCollection<HTMLFormControlsCollection>(*this, FormControls);
 }
 
 String HTMLFormElement::name() const
index a3c9c33..3ee61ba 100644 (file)
 #include "Attribute.h"
 #include "Document.h"
 #include "ElementIterator.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLAreaElement.h"
-#include "HTMLCollection.h"
 #include "HTMLImageElement.h"
 #include "HitTestResult.h"
 #include "IntSize.h"
+#include "NodeRareData.h"
 
 namespace WebCore {
 
@@ -112,7 +113,7 @@ void HTMLMapElement::parseAttribute(const QualifiedName& name, const AtomicStrin
 
 Ref<HTMLCollection> HTMLMapElement::areas()
 {
-    return ensureCachedHTMLCollection(MapAreas);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<MapAreas>::traversalType>>(*this, MapAreas);
 }
 
 Node::InsertionNotificationRequest HTMLMapElement::insertedInto(ContainerNode& insertionPoint)
index 37f58c1..329749b 100644 (file)
@@ -36,19 +36,6 @@ namespace WebCore {
 
 using namespace HTMLNames;
 
-HTMLNameCollection::HTMLNameCollection(Document& document, CollectionType type, const AtomicString& name)
-    : HTMLCollection(document, type)
-    , m_name(name)
-{
-}
-
-HTMLNameCollection::~HTMLNameCollection()
-{
-    ASSERT(type() == WindowNamedItems || type() == DocumentNamedItems);
-
-    document().nodeLists()->removeCachedCollection(this, m_name);
-}
-
 bool WindowNameCollection::elementMatchesIfNameAttributeMatch(const Element& element)
 {
     return is<HTMLImageElement>(element) || is<HTMLFormElement>(element) || is<HTMLAppletElement>(element)
index 320743d..60466c8 100644 (file)
 #ifndef HTMLNameCollection_h
 #define HTMLNameCollection_h
 
-#include "HTMLCollection.h"
+#include "CachedHTMLCollection.h"
+#include "NodeRareData.h"
 #include <wtf/text/AtomicString.h>
 
 namespace WebCore {
 
 class Document;
 
-class HTMLNameCollection : public HTMLCollection {
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+class HTMLNameCollection : public CachedHTMLCollection<HTMLCollectionClass, traversalType> {
 public:
     virtual ~HTMLNameCollection();
 
-    Document& document() { return downcast<Document>(ownerNode()); }
+    Document& document() { return downcast<Document>(this->ownerNode()); }
 
 protected:
     HTMLNameCollection(Document&, CollectionType, const AtomicString& name);
@@ -42,13 +44,29 @@ protected:
     AtomicString m_name;
 };
 
-class WindowNameCollection final : public HTMLNameCollection {
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+HTMLNameCollection<HTMLCollectionClass, traversalType>::HTMLNameCollection(Document& document, CollectionType type, const AtomicString& name)
+    : CachedHTMLCollection<HTMLCollectionClass, traversalType>(document, type)
+    , m_name(name)
+{
+}
+
+template <typename HTMLCollectionClass, CollectionTraversalType traversalType>
+HTMLNameCollection<HTMLCollectionClass, traversalType>::~HTMLNameCollection()
+{
+    ASSERT(this->type() == WindowNamedItems || this->type() == DocumentNamedItems);
+
+    document().nodeLists()->removeCachedCollection(this, m_name);
+}
+
+class WindowNameCollection final : public HTMLNameCollection<WindowNameCollection, CollectionTraversalType::Descendants> {
 public:
     static Ref<WindowNameCollection> create(Document& document, CollectionType type, const AtomicString& name)
     {
         return adoptRef(*new WindowNameCollection(document, type, name));
     }
 
+    // For CachedHTMLCollection.
     bool elementMatches(const Element& element) const { return elementMatches(element, m_name.impl()); }
 
     static bool elementMatchesIfIdAttributeMatch(const Element&) { return true; }
@@ -57,13 +75,13 @@ public:
 
 private:
     WindowNameCollection(Document& document, CollectionType type, const AtomicString& name)
-        : HTMLNameCollection(document, type, name)
+        : HTMLNameCollection<WindowNameCollection, CollectionTraversalType::Descendants>(document, type, name)
     {
         ASSERT(type == WindowNamedItems);
     }
 };
 
-class DocumentNameCollection final : public HTMLNameCollection {
+class DocumentNameCollection final : public HTMLNameCollection<DocumentNameCollection, CollectionTraversalType::Descendants> {
 public:
     static Ref<DocumentNameCollection> create(Document& document, CollectionType type, const AtomicString& name)
     {
@@ -72,13 +90,15 @@ public:
 
     static bool elementMatchesIfIdAttributeMatch(const Element&);
     static bool elementMatchesIfNameAttributeMatch(const Element&);
+
+    // For CachedHTMLCollection.
     bool elementMatches(const Element& element) const { return elementMatches(element, m_name.impl()); }
 
     static bool elementMatches(const Element&, const AtomicStringImpl*);
 
 private:
     DocumentNameCollection(Document& document, CollectionType type, const AtomicString& name)
-        : HTMLNameCollection(document, type, name)
+        : HTMLNameCollection<DocumentNameCollection, CollectionTraversalType::Descendants>(document, type, name)
     {
         ASSERT(type == DocumentNamedItems);
     }
index 1508b41..d9ada06 100644 (file)
@@ -27,7 +27,7 @@
 namespace WebCore {
 
 HTMLOptionsCollection::HTMLOptionsCollection(HTMLSelectElement& select)
-    : HTMLCollection(select, SelectOptions)
+    : CachedHTMLCollection<HTMLOptionsCollection, CollectionTypeTraits<SelectOptions>::traversalType>(select, SelectOptions)
 {
 }
 
index 6366865..c5fd17b 100644 (file)
@@ -24,7 +24,7 @@
 #ifndef HTMLOptionsCollection_h
 #define HTMLOptionsCollection_h
 
-#include "HTMLCollection.h"
+#include "CachedHTMLCollection.h"
 #include "HTMLSelectElement.h"
 
 namespace WebCore {
@@ -33,7 +33,7 @@ class HTMLOptionElement;
 
 typedef int ExceptionCode;
 
-class HTMLOptionsCollection final : public HTMLCollection {
+class HTMLOptionsCollection final : public CachedHTMLCollection<HTMLOptionsCollection, CollectionTypeTraits<SelectOptions>::traversalType> {
 public:
     static Ref<HTMLOptionsCollection> create(HTMLSelectElement&, CollectionType);
 
@@ -50,10 +50,18 @@ public:
 
     void setLength(unsigned, ExceptionCode&);
 
+    // For CachedHTMLCollection.
+    bool elementMatches(Element&) const;
+
 private:
     explicit HTMLOptionsCollection(HTMLSelectElement&);
 };
 
+inline bool HTMLOptionsCollection::elementMatches(Element& element) const
+{
+    return element.hasTagName(HTMLNames::optionTag);
+}
+
 } // namespace WebCore
 
 SPECIALIZE_TYPE_TRAITS_HTMLCOLLECTION(HTMLOptionsCollection, SelectOptions)
index d505f3f..c8b4263 100644 (file)
@@ -38,6 +38,7 @@
 #include "FormController.h"
 #include "FormDataList.h"
 #include "Frame.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLFormElement.h"
 #include "HTMLNames.h"
 #include "HTMLOptGroupElement.h"
@@ -46,6 +47,7 @@
 #include "KeyboardEvent.h"
 #include "LocalizedStrings.h"
 #include "MouseEvent.h"
+#include "NodeRareData.h"
 #include "Page.h"
 #include "PlatformMouseEvent.h"
 #include "RenderListBox.h"
@@ -374,12 +376,12 @@ bool HTMLSelectElement::childShouldCreateRenderer(const Node& child) const
 
 Ref<HTMLCollection> HTMLSelectElement::selectedOptions()
 {
-    return ensureCachedHTMLCollection(SelectedOptions);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<SelectedOptions>::traversalType>>(*this, SelectedOptions);
 }
 
 Ref<HTMLOptionsCollection> HTMLSelectElement::options()
 {
-    return downcast<HTMLOptionsCollection>(ensureCachedHTMLCollection(SelectOptions).get());
+    return ensureRareData().ensureNodeLists().addCachedCollection<HTMLOptionsCollection>(*this, SelectOptions);
 }
 
 void HTMLSelectElement::updateListItemSelectedStates()
index 7457361..028086a 100644 (file)
 #include "CSSValuePool.h"
 #include "ExceptionCode.h"
 #include "ExceptionCodePlaceholder.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLNames.h"
 #include "HTMLParserIdioms.h"
 #include "HTMLTableCaptionElement.h"
 #include "HTMLTableRowElement.h"
 #include "HTMLTableRowsCollection.h"
 #include "HTMLTableSectionElement.h"
+#include "NodeRareData.h"
 #include "RenderTable.h"
 #include "StyleProperties.h"
 #include <wtf/Ref.h>
@@ -551,12 +553,12 @@ bool HTMLTableElement::isURLAttribute(const Attribute& attribute) const
 
 Ref<HTMLCollection> HTMLTableElement::rows()
 {
-    return ensureCachedHTMLCollection(TableRows);
+    return ensureRareData().ensureNodeLists().addCachedCollection<HTMLTableRowsCollection>(*this, TableRows);
 }
 
 Ref<HTMLCollection> HTMLTableElement::tBodies()
 {
-    return ensureCachedHTMLCollection(TableTBodies);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<TableTBodies>::traversalType>>(*this, TableTBodies);
 }
 
 const AtomicString& HTMLTableElement::rules() const
index d4351ea..c87259f 100644 (file)
 #include "HTMLTableRowElement.h"
 
 #include "ExceptionCode.h"
-#include "HTMLCollection.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLNames.h"
 #include "HTMLTableCellElement.h"
 #include "HTMLTableElement.h"
 #include "HTMLTableSectionElement.h"
 #include "NodeList.h"
+#include "NodeRareData.h"
 #include "Text.h"
 
 namespace WebCore {
@@ -156,7 +157,7 @@ void HTMLTableRowElement::deleteCell(int index, ExceptionCode& ec)
 
 Ref<HTMLCollection> HTMLTableRowElement::cells()
 {
-    return ensureCachedHTMLCollection(TRCells);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<TRCells>::traversalType>>(*this, TRCells);
 }
 
 void HTMLTableRowElement::setCells(HTMLCollection*, ExceptionCode& ec)
index bfa5f6d..2d91d9d 100644 (file)
@@ -149,7 +149,7 @@ HTMLTableRowElement* HTMLTableRowsCollection::lastRow(HTMLTableElement& table)
 }
 
 HTMLTableRowsCollection::HTMLTableRowsCollection(HTMLTableElement& table)
-    : HTMLCollection(table, TableRows, CustomForwardOnlyTraversal)
+    : CachedHTMLCollection<HTMLTableRowsCollection, CollectionTypeTraits<TableRows>::traversalType>(table, TableRows)
 {
 }
 
index 9eb5fa6..bf07a32 100644 (file)
 #ifndef HTMLTableRowsCollection_h
 #define HTMLTableRowsCollection_h
 
-#include "HTMLCollection.h"
+#include "CachedHTMLCollection.h"
 #include "HTMLTableElement.h"
 
 namespace WebCore {
 
 class HTMLTableRowElement;
 
-class HTMLTableRowsCollection final : public HTMLCollection {
+class HTMLTableRowsCollection final : public CachedHTMLCollection<HTMLTableRowsCollection, CollectionTypeTraits<TableRows>::traversalType> {
 public:
     static Ref<HTMLTableRowsCollection> create(HTMLTableElement&, CollectionType);
 
@@ -46,10 +46,11 @@ public:
     static HTMLTableRowElement* rowAfter(HTMLTableElement&, HTMLTableRowElement*);
     static HTMLTableRowElement* lastRow(HTMLTableElement&);
 
+    // For CachedHTMLCollection.
+    Element* customElementAfter(Element*) const;
+
 private:
     explicit HTMLTableRowsCollection(HTMLTableElement&);
-
-    virtual Element* customElementAfter(Element*) const override;
 };
 
 } // namespace WebCore
index f75717e..9e45316 100644 (file)
 #include "HTMLTableSectionElement.h"
 
 #include "ExceptionCode.h"
+#include "GenericCachedHTMLCollection.h"
 #include "HTMLCollection.h"
 #include "HTMLNames.h"
 #include "HTMLTableRowElement.h"
 #include "HTMLTableElement.h"
 #include "NodeList.h"
+#include "NodeRareData.h"
 #include "Text.h"
 
 namespace WebCore {
@@ -147,7 +149,7 @@ void HTMLTableSectionElement::setVAlign(const AtomicString& value)
 
 Ref<HTMLCollection> HTMLTableSectionElement::rows()
 {
-    return ensureCachedHTMLCollection(TSectionRows);
+    return ensureRareData().ensureNodeLists().addCachedCollection<GenericCachedHTMLCollection<CollectionTypeTraits<TSectionRows>::traversalType>>(*this, TSectionRows);
 }
 
 }