HTMLCollection's caches should be owned by either ElementRareData or Document
[WebKit-https.git] / Source / WebCore / html / HTMLCollection.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #include "config.h"
24 #include "HTMLCollection.h"
25
26 #include "HTMLDocument.h"
27 #include "HTMLElement.h"
28 #include "HTMLNames.h"
29 #include "HTMLObjectElement.h"
30 #include "HTMLOptionElement.h"
31 #include "NodeList.h"
32
33 #include <utility>
34
35 namespace WebCore {
36
37 using namespace HTMLNames;
38
39 static bool shouldIncludeChildren(CollectionType type)
40 {
41     switch (type) {
42     case DocAll:
43     case DocAnchors:
44     case DocApplets:
45     case DocEmbeds:
46     case DocForms:
47     case DocImages:
48     case DocLinks:
49     case DocObjects:
50     case DocScripts:
51     case DocumentNamedItems:
52     case MapAreas:
53     case TableRows:
54     case SelectOptions:
55     case SelectedOptions:
56     case DataListOptions:
57     case WindowNamedItems:
58 #if ENABLE(MICRODATA)
59     case ItemProperties:
60 #endif
61     case FormControls:
62         return true;
63     case NodeChildren:
64     case TRCells:
65     case TSectionRows:
66     case TableTBodies:
67         return false;
68     }
69     ASSERT_NOT_REACHED();
70     return false;
71 }
72
73 HTMLCollection::HTMLCollection(Node* base, CollectionType type)
74     : HTMLCollectionCacheBase(type, shouldIncludeChildren(type))
75     , m_base(base)
76 {
77     ASSERT(m_base);
78 }
79
80 PassOwnPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
81 {
82     return adoptPtr(new HTMLCollection(base, type));
83 }
84
85 HTMLCollection::~HTMLCollection()
86 {
87 }
88
89 void HTMLCollection::invalidateCacheIfNeeded() const
90 {
91     uint64_t docversion = static_cast<HTMLDocument*>(m_base->document())->domTreeVersion();
92
93     if (cacheTreeVersion() == docversion)
94         return;
95
96     clearCache(docversion);
97 }
98
99 void HTMLCollection::invalidateCache()
100 {
101     clearCache(static_cast<HTMLDocument*>(m_base->document())->domTreeVersion());
102 }
103
104 inline bool HTMLCollection::isAcceptableElement(Element* element) const
105 {
106     if (!element->isHTMLElement() && !(type() == DocAll || type() == NodeChildren))
107         return false;
108
109     switch (type()) {
110     case DocImages:
111         return element->hasLocalName(imgTag);
112     case DocScripts:
113         return element->hasLocalName(scriptTag);
114     case DocForms:
115         return element->hasLocalName(formTag);
116     case TableTBodies:
117         return element->hasLocalName(tbodyTag);
118     case TRCells:
119         return element->hasLocalName(tdTag) || element->hasLocalName(thTag);
120     case TSectionRows:
121         return element->hasLocalName(trTag);
122     case SelectOptions:
123         return element->hasLocalName(optionTag);
124     case SelectedOptions:
125         return element->hasLocalName(optionTag) && toHTMLOptionElement(element)->selected();
126     case DataListOptions:
127         if (element->hasLocalName(optionTag)) {
128             HTMLOptionElement* option = static_cast<HTMLOptionElement*>(element);
129             if (!option->disabled() && !option->value().isEmpty())
130                 return true;
131         }
132         return false;
133     case MapAreas:
134         return element->hasLocalName(areaTag);
135     case DocApplets:
136         return element->hasLocalName(appletTag) || (element->hasLocalName(objectTag) && static_cast<HTMLObjectElement*>(element)->containsJavaApplet());
137     case DocEmbeds:
138         return element->hasLocalName(embedTag);
139     case DocObjects:
140         return element->hasLocalName(objectTag);
141     case DocLinks:
142         return (element->hasLocalName(aTag) || element->hasLocalName(areaTag)) && element->fastHasAttribute(hrefAttr);
143     case DocAnchors:
144         return element->hasLocalName(aTag) && element->fastHasAttribute(nameAttr);
145     case DocAll:
146     case NodeChildren:
147         return true;
148 #if ENABLE(MICRODATA)
149     case ItemProperties:
150         return element->fastHasAttribute(itempropAttr);
151 #endif
152     case FormControls:
153     case DocumentNamedItems:
154     case TableRows:
155     case WindowNamedItems:
156         ASSERT_NOT_REACHED();
157     }
158     return false;
159 }
160
161 static Node* nextNodeOrSibling(Node* base, Node* node, bool includeChildren)
162 {
163     return includeChildren ? node->traverseNextNode(base) : node->traverseNextSibling(base);
164 }
165
166 Element* HTMLCollection::itemAfter(Node* previous) const
167 {
168     Node* current;
169     if (!previous)
170         current = m_base->firstChild();
171     else
172         current = nextNodeOrSibling(m_base, previous, includeChildren());
173
174     for (; current; current = nextNodeOrSibling(m_base, current, includeChildren())) {
175         if (!current->isElementNode())
176             continue;
177         Element* element = static_cast<Element*>(current);
178         if (isAcceptableElement(element))
179             return element;
180     }
181
182     return 0;
183 }
184
185 unsigned HTMLCollection::calcLength() const
186 {
187     unsigned len = 0;
188     for (Element* current = itemAfter(0); current; current = itemAfter(current))
189         ++len;
190     return len;
191 }
192
193 // since the collections are to be "live", we have to do the
194 // calculation every time if anything has changed
195 unsigned HTMLCollection::length() const
196 {
197     invalidateCacheIfNeeded();
198     if (!isLengthCacheValid())
199         setLengthCache(calcLength());
200     return cachedLength();
201 }
202
203 Node* HTMLCollection::item(unsigned index) const
204 {
205     invalidateCacheIfNeeded();
206     if (isItemCacheValid() && cachedItemOffset() == index)
207         return cachedItem();
208     if (isLengthCacheValid() && cachedLength() <= index)
209         return 0;
210     if (!isItemCacheValid() || cachedItemOffset() > index) {
211         setItemCache(itemAfter(0), 0);
212         if (!cachedItem())
213             return 0;
214     }
215     Node* e = cachedItem();
216     for (unsigned pos = cachedItemOffset(); e && pos < index; pos++)
217         e = itemAfter(e);
218     setItemCache(e, index);
219     return cachedItem();
220 }
221
222 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
223 {
224     // The document.all collection returns only certain types of elements by name,
225     // although it returns any type of element by id.
226     return element->hasLocalName(appletTag)
227         || element->hasLocalName(embedTag)
228         || element->hasLocalName(formTag)
229         || element->hasLocalName(imgTag)
230         || element->hasLocalName(inputTag)
231         || element->hasLocalName(objectTag)
232         || element->hasLocalName(selectTag);
233 }
234
235 bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const AtomicString& name) const
236 {
237     if (!element->isHTMLElement())
238         return false;
239     
240     HTMLElement* e = toHTMLElement(element);
241     if (!checkName)
242         return e->getIdAttribute() == name;
243
244     if (type() == DocAll && !nameShouldBeVisibleInDocumentAll(e))
245         return false;
246
247     return e->getNameAttribute() == name && e->getIdAttribute() != name;
248 }
249
250 Node* HTMLCollection::namedItem(const AtomicString& name) const
251 {
252     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
253     // This method first searches for an object with a matching id
254     // attribute. If a match is not found, the method then searches for an
255     // object with a matching name attribute, but only on those elements
256     // that are allowed a name attribute.
257     invalidateCacheIfNeeded();
258
259     unsigned i = 0;
260     for (Element* e = itemAfter(0); e; e = itemAfter(e)) {
261         if (checkForNameMatch(e, /* checkName */ false, name)) {
262             setItemCache(e, i);
263             return e;
264         }
265         i++;
266     }
267
268     i = 0;
269     for (Element* e = itemAfter(0); e; e = itemAfter(e)) {
270         if (checkForNameMatch(e, /* checkName */ true, name)) {
271             setItemCache(e, i);
272             return e;
273         }
274         i++;
275     }
276
277     return 0;
278 }
279
280 void HTMLCollection::updateNameCache() const
281 {
282     if (hasNameCache())
283         return;
284
285     for (Element* element = itemAfter(0); element; element = itemAfter(element)) {
286         if (!element->isHTMLElement())
287             continue;
288         HTMLElement* e = toHTMLElement(element);
289         const AtomicString& idAttrVal = e->getIdAttribute();
290         const AtomicString& nameAttrVal = e->getNameAttribute();
291         if (!idAttrVal.isEmpty())
292             appendIdCache(idAttrVal, e);
293         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(e)))
294             appendNameCache(nameAttrVal, e);
295     }
296
297     setHasNameCache();
298 }
299
300 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
301 {
302     if (name.isEmpty())
303         return false;
304
305     invalidateCacheIfNeeded();
306     updateNameCache();
307
308     if (Vector<Element*>* cache = idCache(name)) {
309         if (!cache->isEmpty())
310             return true;
311     }
312
313     if (Vector<Element*>* cache = nameCache(name)) {
314         if (!cache->isEmpty())
315             return true;
316     }
317
318     return false;
319 }
320
321 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >& result) const
322 {
323     ASSERT(result.isEmpty());
324     if (name.isEmpty())
325         return;
326
327     invalidateCacheIfNeeded();
328     updateNameCache();
329
330     Vector<Element*>* idResults = idCache(name);
331     Vector<Element*>* nameResults = nameCache(name);
332
333     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
334         result.append(idResults->at(i));
335
336     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
337         result.append(nameResults->at(i));
338 }
339
340 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
341 {
342     return m_base->getElementsByTagName(name);
343 }
344
345 void HTMLCollectionCacheBase::append(NodeCacheMap& map, const AtomicString& key, Element* element)
346 {
347     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->second;
348     if (!vector)
349         vector = adoptPtr(new Vector<Element*>);
350     vector->append(element);
351 }
352
353 } // namespace WebCore