Remove some unnecessary branches from LiveNodeList traversal
[WebKit-https.git] / Source / WebCore / dom / LiveNodeList.h
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
5  * Copyright (C) 2004, 2006, 2007, 2013 Apple Inc. All rights reserved.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #ifndef LiveNodeList_h
25 #define LiveNodeList_h
26
27 #include "CollectionIndexCache.h"
28 #include "CollectionType.h"
29 #include "Document.h"
30 #include "ElementTraversal.h"
31 #include "HTMLNames.h"
32 #include "NodeList.h"
33 #include <wtf/Forward.h>
34 #include <wtf/RefPtr.h>
35
36 namespace WebCore {
37
38 class Element;
39
40 enum NodeListRootType {
41     NodeListIsRootedAtNode,
42     NodeListIsRootedAtDocument
43 };
44
45 static bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType, const QualifiedName&);
46
47 class LiveNodeList : public NodeList {
48 public:
49     enum class Type {
50         ClassNodeListType,
51         NameNodeListType,
52         TagNodeListType,
53         HTMLTagNodeListType,
54         RadioNodeListType,
55         LabelsNodeListType,
56     };
57
58     LiveNodeList(ContainerNode& ownerNode, Type, NodeListInvalidationType, NodeListRootType);
59     virtual Node* namedItem(const AtomicString&) const override final;
60     virtual bool nodeMatches(Element*) const = 0;
61
62     virtual ~LiveNodeList();
63
64     ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootType == NodeListIsRootedAtDocument; }
65     ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
66     ALWAYS_INLINE Type type() const { return static_cast<Type>(m_type); }
67     ContainerNode& ownerNode() const { return const_cast<ContainerNode&>(m_ownerNode.get()); }
68     ALWAYS_INLINE void invalidateCacheForAttribute(const QualifiedName* attrName) const
69     {
70         if (!attrName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attrName))
71             invalidateCache(document());
72     }
73     virtual void invalidateCache(Document&) const = 0;
74
75 protected:
76     Document& document() const { return m_ownerNode->document(); }
77     ContainerNode& rootNode() const;
78
79     ALWAYS_INLINE NodeListRootType rootType() const { return static_cast<NodeListRootType>(m_rootType); }
80
81 private:
82     virtual bool isLiveNodeList() const override { return true; }
83
84     Element* iterateForPreviousElement(Element* current) const;
85
86     Ref<ContainerNode> m_ownerNode;
87
88     const unsigned m_rootType : 1;
89     const unsigned m_invalidationType : 4;
90     const unsigned m_type : 3;
91 };
92
93 template <class NodeListType>
94 class CachedLiveNodeList : public LiveNodeList {
95 public:
96     virtual ~CachedLiveNodeList();
97
98     virtual unsigned length() const override final;
99     virtual Node* item(unsigned offset) const override final;
100
101     // For CollectionIndexCache
102     Element* collectionFirst() const;
103     Element* collectionLast() const;
104     Element* collectionTraverseForward(Element&, unsigned count, unsigned& traversedCount) const;
105     Element* collectionTraverseBackward(Element&, unsigned count) const;
106     bool collectionCanTraverseBackward() const { return true; }
107     void willValidateIndexCache() const;
108
109     virtual void invalidateCache(Document&) const;
110     virtual size_t memoryCost() const override;
111
112 protected:
113     CachedLiveNodeList(ContainerNode& rootNode, Type, NodeListInvalidationType, NodeListRootType = NodeListIsRootedAtNode);
114
115 private:
116     mutable CollectionIndexCache<NodeListType, Element> m_indexCache;
117 };
118
119 ALWAYS_INLINE bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
120 {
121     switch (type) {
122     case InvalidateOnClassAttrChange:
123         return attrName == HTMLNames::classAttr;
124     case InvalidateOnNameAttrChange:
125         return attrName == HTMLNames::nameAttr;
126     case InvalidateOnIdNameAttrChange:
127         return attrName == HTMLNames::idAttr || attrName == HTMLNames::nameAttr;
128     case InvalidateOnForAttrChange:
129         return attrName == HTMLNames::forAttr;
130     case InvalidateForFormControls:
131         return attrName == HTMLNames::nameAttr || attrName == HTMLNames::idAttr || attrName == HTMLNames::forAttr
132             || attrName == HTMLNames::formAttr || attrName == HTMLNames::typeAttr;
133     case InvalidateOnHRefAttrChange:
134         return attrName == HTMLNames::hrefAttr;
135     case DoNotInvalidateOnAttributeChanges:
136         return false;
137     case InvalidateOnAnyAttrChange:
138         return true;
139     }
140     return false;
141 }
142
143 inline ContainerNode& LiveNodeList::rootNode() const
144 {
145     if (isRootedAtDocument() && ownerNode().inDocument())
146         return ownerNode().document();
147
148     return ownerNode();
149 }
150
151 template <class NodeListType>
152 CachedLiveNodeList<NodeListType>::CachedLiveNodeList(ContainerNode& ownerNode, Type type, NodeListInvalidationType invalidationType, NodeListRootType rootType)
153     : LiveNodeList(ownerNode, type, invalidationType, rootType)
154 {
155 }
156
157 template <class NodeListType>
158 CachedLiveNodeList<NodeListType>::~CachedLiveNodeList()
159 {
160     if (m_indexCache.hasValidCache())
161         document().unregisterNodeList(*this);
162 }
163
164 template <class NodeListType>
165 Element* CachedLiveNodeList<NodeListType>::collectionFirst() const
166 {
167     auto& root = rootNode();
168     Element* element = ElementTraversal::firstWithin(&root);
169     while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
170         element = ElementTraversal::next(element, &root);
171     return element;
172 }
173
174 template <class NodeListType>
175 Element* CachedLiveNodeList<NodeListType>::collectionLast() const
176 {
177     auto& root = rootNode();
178     Element* element = ElementTraversal::lastWithin(&root);
179     while (element && !static_cast<const NodeListType*>(this)->nodeMatches(element))
180         element = ElementTraversal::previous(element, &root);
181     return element;
182 }
183
184 template <class NodeListType>
185 inline Element* nextMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
186 {
187     do {
188         current = ElementTraversal::next(current, &root);
189     } while (current && !static_cast<const NodeListType*>(nodeList)->nodeMatches(current));
190     return current;
191 }
192
193 template <class NodeListType>
194 Element* CachedLiveNodeList<NodeListType>::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
195 {
196     auto& root = rootNode();
197     Element* element = &current;
198     for (traversedCount = 0; traversedCount < count; ++traversedCount) {
199         element = nextMatchingElement(static_cast<const NodeListType*>(this), element, root);
200         if (!element)
201             return nullptr;
202     }
203     return element;
204 }
205
206 template <class NodeListType>
207 inline Element* previousMatchingElement(const NodeListType* nodeList, Element* current, ContainerNode& root)
208 {
209     do {
210         current = ElementTraversal::previous(current, &root);
211     } while (current && !nodeList->nodeMatches(current));
212     return current;
213 }
214
215 template <class NodeListType>
216 Element* CachedLiveNodeList<NodeListType>::collectionTraverseBackward(Element& current, unsigned count) const
217 {
218     auto& root = rootNode();
219     Element* element = &current;
220     for (; count; --count) {
221         element = previousMatchingElement(static_cast<const NodeListType*>(this), element, root);
222         if (!element)
223             return nullptr;
224     }
225     return element;
226 }
227 template <class NodeListType>
228 void CachedLiveNodeList<NodeListType>::willValidateIndexCache() const
229 {
230     document().registerNodeList(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
231 }
232
233 template <class NodeListType>
234 void CachedLiveNodeList<NodeListType>::invalidateCache(Document& document) const
235 {
236     if (!m_indexCache.hasValidCache())
237         return;
238     document.unregisterNodeList(const_cast<NodeListType&>(static_cast<const NodeListType&>(*this)));
239     m_indexCache.invalidate();
240 }
241
242 template <class NodeListType>
243 unsigned CachedLiveNodeList<NodeListType>::length() const
244 {
245     return m_indexCache.nodeCount(static_cast<const NodeListType&>(*this));
246 }
247
248 template <class NodeListType>
249 Node* CachedLiveNodeList<NodeListType>::item(unsigned offset) const
250 {
251     return m_indexCache.nodeAt(static_cast<const NodeListType&>(*this), offset);
252 }
253
254 template <class NodeListType>
255 size_t CachedLiveNodeList<NodeListType>::memoryCost() const
256 {
257     return m_indexCache.memoryCost();
258 }
259
260 } // namespace WebCore
261
262 #endif // LiveNodeList_h