Iterating backwards over HTMLCollection is O(n^2)
[WebKit-https.git] / Source / WebCore / dom / DynamicNodeList.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 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 DynamicNodeList_h
25 #define DynamicNodeList_h
26
27 #include "CollectionType.h"
28 #include "Document.h"
29 #include "HTMLNames.h"
30 #include "NodeList.h"
31 #include <wtf/Forward.h>
32 #include <wtf/RefPtr.h>
33
34 namespace WebCore {
35
36 class Element;
37 class Node;
38
39 enum NodeListRootType {
40     NodeListIsRootedAtNode,
41     NodeListIsRootedAtDocument,
42 };
43
44 class DynamicNodeListCacheBase {
45 public:
46     enum ItemBeforeSupportType {
47         DoNotSupportItemBefore,
48         SupportItemBefore,
49     };
50
51     DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType,
52         CollectionType collectionType = InvalidCollectionType, ItemBeforeSupportType itemBeforeSupportType = DoNotSupportItemBefore)
53         : m_cachedItem(0)
54         , m_isLengthCacheValid(false)
55         , m_isItemCacheValid(false)
56         , m_rootedAtDocument(rootType == NodeListIsRootedAtDocument)
57         , m_invalidationType(invalidationType)
58         , m_isNameCacheValid(false)
59         , m_collectionType(collectionType)
60         , m_supportsItemBefore(itemBeforeSupportType == SupportItemBefore)
61     {
62         ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
63         ASSERT(m_collectionType == static_cast<unsigned>(collectionType));
64     }
65
66 public:
67     ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootedAtDocument; }
68     ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
69     ALWAYS_INLINE CollectionType type() const { return static_cast<CollectionType>(m_collectionType); }
70
71     void invalidateCache() const;
72
73     static bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType, const QualifiedName&);
74
75 protected:
76     bool supportsItemBefore() const { return m_supportsItemBefore; }
77
78     ALWAYS_INLINE bool isItemCacheValid() const { return m_isItemCacheValid; }
79     ALWAYS_INLINE Node* cachedItem() const { return m_cachedItem; }
80     ALWAYS_INLINE unsigned cachedItemOffset() const { return m_cachedItemOffset; }
81
82     ALWAYS_INLINE bool isLengthCacheValid() const { return m_isLengthCacheValid; }
83     ALWAYS_INLINE unsigned cachedLength() const { return m_cachedLength; }
84     ALWAYS_INLINE void setLengthCache(unsigned length) const
85     {
86         m_cachedLength = length;
87         m_isLengthCacheValid = true;
88     }
89     ALWAYS_INLINE void setItemCache(Node* item, unsigned offset) const
90     {
91         ASSERT(item);
92         m_cachedItem = item;
93         m_cachedItemOffset = offset;
94         m_isItemCacheValid = true;
95     }
96
97     bool hasNameCache() const { return m_isNameCacheValid; }
98     void setHasNameCache() const { m_isNameCacheValid = true; }
99
100 private:
101     mutable Node* m_cachedItem;
102     mutable unsigned m_cachedLength;
103     mutable unsigned m_cachedItemOffset;
104     mutable unsigned m_isLengthCacheValid : 1;
105     mutable unsigned m_isItemCacheValid : 1;
106     const unsigned m_rootedAtDocument : 1;
107     const unsigned m_invalidationType : 4;
108
109     // From HTMLCollection
110     mutable unsigned m_isNameCacheValid : 1;
111     const unsigned m_collectionType : 5;
112     const unsigned m_supportsItemBefore : 1;
113 };
114
115 ALWAYS_INLINE bool DynamicNodeListCacheBase::shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
116 {
117     switch (type) {
118     case InvalidateOnClassAttrChange:
119         return attrName == HTMLNames::classAttr;
120     case InvalidateOnNameAttrChange:
121         return attrName == HTMLNames::nameAttr;
122     case InvalidateOnIdNameAttrChange:
123         return attrName == HTMLNames::idAttr || attrName == HTMLNames::nameAttr;
124     case InvalidateOnForAttrChange:
125         return attrName == HTMLNames::forAttr;
126     case InvalidateForFormControls:
127         return attrName == HTMLNames::nameAttr || attrName == HTMLNames::idAttr || attrName == HTMLNames::forAttr || attrName == HTMLNames::typeAttr;
128     case InvalidateOnHRefAttrChange:
129         return attrName == HTMLNames::hrefAttr;
130     case InvalidateOnItemAttrChange:
131 #if ENABLE(MICRODATA)
132         return attrName == HTMLNames::itemscopeAttr || attrName == HTMLNames::itempropAttr || attrName == HTMLNames::itemtypeAttr;
133 #endif // Intentionally fall through
134     case DoNotInvalidateOnAttributeChanges:
135         return false;
136     case InvalidateOnAnyAttrChange:
137         return true;
138     }
139     return false;
140 }
141
142 class DynamicNodeList : public NodeList, public DynamicNodeListCacheBase {
143 public:
144     enum NodeListType {
145         ChildNodeListType,
146         ClassNodeListType,
147         NameNodeListType,
148         TagNodeListType,
149         RadioNodeListType,
150         LabelsNodeListType,
151         MicroDataItemListType,
152     };
153     DynamicNodeList(PassRefPtr<Node> ownerNode, NodeListRootType rootType, NodeListInvalidationType invalidationType)
154         : DynamicNodeListCacheBase(rootType, invalidationType)
155         , m_ownerNode(ownerNode)
156     { }
157     virtual ~DynamicNodeList() { }
158
159     // DOM methods & attributes for NodeList
160     virtual unsigned length() const = 0;
161     virtual Node* item(unsigned index) const = 0;
162     virtual Node* itemWithName(const AtomicString&) const;
163
164     // Other methods (not part of DOM)
165     Node* ownerNode() const { return m_ownerNode.get(); }
166
167 protected:
168     Node* rootNode() const
169     {
170         if (isRootedAtDocument() && m_ownerNode->inDocument())
171             return m_ownerNode->document();
172         return m_ownerNode.get();
173     }
174     Document* document() const { return m_ownerNode->document(); }
175     virtual bool nodeMatches(Element*) const = 0;
176
177 private:
178     virtual bool isDynamicNodeList() const OVERRIDE { return true; }
179     RefPtr<Node> m_ownerNode;
180 };
181
182 class DynamicSubtreeNodeList : public DynamicNodeList {
183 public:
184     virtual ~DynamicSubtreeNodeList()
185     {
186         document()->unregisterNodeListCache(this);
187     }
188     virtual unsigned length() const OVERRIDE;
189     virtual Node* item(unsigned index) const OVERRIDE;
190
191 protected:
192     DynamicSubtreeNodeList(PassRefPtr<Node> node, NodeListInvalidationType invalidationType, NodeListRootType rootType = NodeListIsRootedAtNode)
193         : DynamicNodeList(node, rootType, invalidationType)
194     {
195         document()->registerNodeListCache(this);
196     }
197
198 private:
199     Node* itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
200     Node* itemBackwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const;
201 };
202
203 } // namespace WebCore
204
205 #endif // DynamicNodeList_h