Iterating backwards over HTMLCollection is O(n^2)
[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 #if ENABLE(MICRODATA)
34 #include "HTMLPropertiesCollection.h"
35 #endif
36
37 #include <utility>
38
39 namespace WebCore {
40
41 using namespace HTMLNames;
42
43 static bool shouldOnlyIncludeDirectChildren(CollectionType type)
44 {
45     switch (type) {
46     case DocAll:
47     case DocAnchors:
48     case DocApplets:
49     case DocEmbeds:
50     case DocForms:
51     case DocImages:
52     case DocLinks:
53     case DocObjects:
54     case DocScripts:
55     case DocumentNamedItems:
56     case MapAreas:
57     case TableRows:
58     case SelectOptions:
59     case SelectedOptions:
60     case DataListOptions:
61     case WindowNamedItems:
62 #if ENABLE(MICRODATA)
63     case ItemProperties:
64 #endif
65     case FormControls:
66         return false;
67     case NodeChildren:
68     case TRCells:
69     case TSectionRows:
70     case TableTBodies:
71         return true;
72     case InvalidCollectionType:
73         break;
74     }
75     ASSERT_NOT_REACHED();
76     return false;
77 }
78
79 static NodeListRootType rootTypeFromCollectionType(CollectionType type)
80 {
81     switch (type) {
82     case DocImages:
83     case DocApplets:
84     case DocEmbeds:
85     case DocObjects:
86     case DocForms:
87     case DocLinks:
88     case DocAnchors:
89     case DocScripts:
90     case DocAll:
91     case WindowNamedItems:
92     case DocumentNamedItems:
93 #if ENABLE(MICRODATA)
94     case ItemProperties:
95 #endif
96     case FormControls:
97         return NodeListIsRootedAtDocument;
98     case NodeChildren:
99     case TableTBodies:
100     case TSectionRows:
101     case TableRows:
102     case TRCells:
103     case SelectOptions:
104     case SelectedOptions:
105     case DataListOptions:
106     case MapAreas:
107     case InvalidCollectionType:
108         return NodeListIsRootedAtNode;
109     }
110     ASSERT_NOT_REACHED();
111     return NodeListIsRootedAtNode;
112 }
113
114 static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(CollectionType type)
115 {
116     switch (type) {
117     case DocImages:
118     case DocEmbeds:
119     case DocObjects:
120     case DocForms:
121     case DocAnchors: // Depends on name attribute.
122     case DocScripts:
123     case DocAll:
124     case WindowNamedItems: // Depends on id and name attributes.
125     case DocumentNamedItems: // Ditto.
126     case NodeChildren:
127     case TableTBodies:
128     case TSectionRows:
129     case TableRows:
130     case TRCells:
131     case SelectOptions:
132     case MapAreas:
133         return DoNotInvalidateOnAttributeChanges;
134     case DocApplets:
135     case SelectedOptions:
136     case DataListOptions:
137         // FIXME: We can do better some day.
138         return InvalidateOnAnyAttrChange;
139     case DocLinks:
140         return InvalidateOnHRefAttrChange;
141 #if ENABLE(MICRODATA)
142     case ItemProperties:
143         return InvalidateOnItemAttrChange;
144 #endif
145     case FormControls:
146         return InvalidateForFormControls;
147     case InvalidCollectionType:
148         break;
149     }
150     ASSERT_NOT_REACHED();
151     return DoNotInvalidateOnAttributeChanges;
152 }
153     
154
155 HTMLCollection::HTMLCollection(Node* base, CollectionType type, ItemBeforeSupportType itemBeforeSupportType)
156     : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type, itemBeforeSupportType)
157     , m_base(base)
158 {
159     ASSERT(m_base);
160     m_base->document()->registerNodeListCache(this);
161 }
162
163 PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
164 {
165     return adoptRef(new HTMLCollection(base, type, SupportItemBefore));
166 }
167
168 HTMLCollection::~HTMLCollection()
169 {
170     if (isUnnamedDocumentCachedType(type())) {
171         ASSERT(base()->isDocumentNode());
172         static_cast<Document*>(base())->removeCachedHTMLCollection(this, type());
173     } else if (isNodeCollectionType(type())) {
174         ASSERT(base()->isElementNode());
175         toElement(base())->removeCachedHTMLCollection(this, type());
176     } else // HTMLNameCollection removes cache by itself.
177         ASSERT(type() == WindowNamedItems || type() == DocumentNamedItems);
178
179     m_base->document()->unregisterNodeListCache(this);
180 }
181
182 static inline bool isAcceptableElement(CollectionType type, Element* element)
183 {
184     if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren))
185         return false;
186
187     switch (type) {
188     case DocImages:
189         return element->hasLocalName(imgTag);
190     case DocScripts:
191         return element->hasLocalName(scriptTag);
192     case DocForms:
193         return element->hasLocalName(formTag);
194     case TableTBodies:
195         return element->hasLocalName(tbodyTag);
196     case TRCells:
197         return element->hasLocalName(tdTag) || element->hasLocalName(thTag);
198     case TSectionRows:
199         return element->hasLocalName(trTag);
200     case SelectOptions:
201         return element->hasLocalName(optionTag);
202     case SelectedOptions:
203         return element->hasLocalName(optionTag) && toHTMLOptionElement(element)->selected();
204     case DataListOptions:
205         if (element->hasLocalName(optionTag)) {
206             HTMLOptionElement* option = static_cast<HTMLOptionElement*>(element);
207             if (!option->disabled() && !option->value().isEmpty())
208                 return true;
209         }
210         return false;
211     case MapAreas:
212         return element->hasLocalName(areaTag);
213     case DocApplets:
214         return element->hasLocalName(appletTag) || (element->hasLocalName(objectTag) && static_cast<HTMLObjectElement*>(element)->containsJavaApplet());
215     case DocEmbeds:
216         return element->hasLocalName(embedTag);
217     case DocObjects:
218         return element->hasLocalName(objectTag);
219     case DocLinks:
220         return (element->hasLocalName(aTag) || element->hasLocalName(areaTag)) && element->fastHasAttribute(hrefAttr);
221     case DocAnchors:
222         return element->hasLocalName(aTag) && element->fastHasAttribute(nameAttr);
223     case DocAll:
224     case NodeChildren:
225         return true;
226 #if ENABLE(MICRODATA)
227     case ItemProperties:
228         return element->fastHasAttribute(itempropAttr);
229 #endif
230     case FormControls:
231     case DocumentNamedItems:
232     case TableRows:
233     case WindowNamedItems:
234     case InvalidCollectionType:
235         ASSERT_NOT_REACHED();
236     }
237     return false;
238 }
239
240 template<bool forward>
241 static Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
242 {
243     if (forward)
244         return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base);
245     else
246         return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base);
247 }
248
249 template<bool forward>
250 static Element* itemBeforeOrAfter(CollectionType type, Node* base, unsigned& offsetInArray, Node* previous)
251 {
252     ASSERT_UNUSED(offsetInArray, !offsetInArray);
253     bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type);
254     Node* rootNode = base;
255     Node* current = previous ? nextNode<forward>(rootNode, previous, onlyIncludeDirectChildren) : (forward ? base->firstChild() : base->lastChild());
256
257     for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
258         if (current->isElementNode() && isAcceptableElement(type, toElement(current)))
259             return toElement(current);
260     }
261
262     return 0;
263 }
264
265 Element* HTMLCollection::itemBefore(unsigned& offsetInArray, Element* previous) const
266 {
267     return itemBeforeOrAfter<false>(type(), base(), offsetInArray, previous);
268 }
269
270 Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
271 {
272     return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
273 }
274     
275 bool ALWAYS_INLINE HTMLCollection::shouldSearchFromFirstItem(unsigned offset) const
276 {
277     if (!isItemCacheValid())
278         return true;
279
280     ASSERT(offset != cachedItemOffset());
281     if (offset > cachedItemOffset())
282         return false;
283
284     unsigned distanceFromCachedItem = cachedItemOffset() - offset;
285     return !supportsItemBefore() || offset < distanceFromCachedItem;
286 }
287
288 unsigned HTMLCollection::length() const
289 {
290     if (isLengthCacheValid())
291         return cachedLength();
292
293     if (!isItemCacheValid() && !item(0)) {
294         ASSERT(isLengthCacheValid());
295         return 0;
296     }
297
298     ASSERT(isItemCacheValid());
299     ASSERT(cachedItem());
300     unsigned offset = cachedItemOffset();
301     do {
302         offset++;
303     } while (itemBeforeOrAfterCachedItem(offset));
304
305     setLengthCache(offset);
306     return offset;
307 }
308
309 Node* HTMLCollection::item(unsigned offset) const
310 {
311     if (isItemCacheValid() && cachedItemOffset() == offset)
312         return cachedItem();
313
314     if (isLengthCacheValid() && cachedLength() <= offset)
315         return 0;
316
317 #if ENABLE(MICRODATA)
318     if (type() == ItemProperties)
319         static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
320 #endif
321
322     if (shouldSearchFromFirstItem(offset)) {
323         unsigned offsetInArray = 0;
324         Node* firstItem = itemAfter(offsetInArray, 0);
325         if (!firstItem) {
326             setLengthCache(0);
327             return 0;
328         }
329         setItemCache(firstItem, 0, offsetInArray);
330         ASSERT(!cachedItemOffset());
331         if (!offset)
332             return cachedItem();
333     }
334
335     return itemBeforeOrAfterCachedItem(offset);
336 }
337
338 Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
339 {
340     unsigned currentOffset = cachedItemOffset();
341     ASSERT(cachedItem()->isElementNode());
342     Element* currentItem = toElement(cachedItem());
343     ASSERT(currentOffset != offset);
344
345     unsigned offsetInArray = cachedElementsArrayOffset();
346
347     if (offset < cachedItemOffset()) {
348         ASSERT(supportsItemBefore());
349         while ((currentItem = itemBefore(offsetInArray, currentItem))) {
350             ASSERT(currentOffset);
351             currentOffset--;
352             if (currentOffset == offset) {
353                 setItemCache(currentItem, currentOffset, offsetInArray);
354                 return currentItem;
355             }
356         }
357         ASSERT_NOT_REACHED();
358         return 0;
359     }
360
361     while ((currentItem = itemAfter(offsetInArray, currentItem))) {
362         currentOffset++;
363         if (currentOffset == offset) {
364             setItemCache(currentItem, currentOffset, offsetInArray);
365             return currentItem;
366         }
367     }
368
369     setLengthCache(currentOffset);
370
371     return 0;
372 }
373
374 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
375 {
376     // The document.all collection returns only certain types of elements by name,
377     // although it returns any type of element by id.
378     return element->hasLocalName(appletTag)
379         || element->hasLocalName(embedTag)
380         || element->hasLocalName(formTag)
381         || element->hasLocalName(imgTag)
382         || element->hasLocalName(inputTag)
383         || element->hasLocalName(objectTag)
384         || element->hasLocalName(selectTag);
385 }
386
387 bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const AtomicString& name) const
388 {
389     if (!element->isHTMLElement())
390         return false;
391     
392     HTMLElement* e = toHTMLElement(element);
393     if (!checkName)
394         return e->getIdAttribute() == name;
395
396     if (type() == DocAll && !nameShouldBeVisibleInDocumentAll(e))
397         return false;
398
399     return e->getNameAttribute() == name && e->getIdAttribute() != name;
400 }
401
402 Node* HTMLCollection::namedItem(const AtomicString& name) const
403 {
404     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
405     // This method first searches for an object with a matching id
406     // attribute. If a match is not found, the method then searches for an
407     // object with a matching name attribute, but only on those elements
408     // that are allowed a name attribute.
409
410     unsigned arrayOffset = 0;
411     unsigned i = 0;
412     for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
413         if (checkForNameMatch(e, /* checkName */ false, name)) {
414             setItemCache(e, i, arrayOffset);
415             return e;
416         }
417         i++;
418     }
419
420     i = 0;
421     for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
422         if (checkForNameMatch(e, /* checkName */ true, name)) {
423             setItemCache(e, i, arrayOffset);
424             return e;
425         }
426         i++;
427     }
428
429     return 0;
430 }
431
432 void HTMLCollection::updateNameCache() const
433 {
434     if (hasNameCache())
435         return;
436
437     unsigned arrayOffset = 0;
438     for (Element* element = itemAfter(arrayOffset, 0); element; element = itemAfter(arrayOffset, element)) {
439         if (!element->isHTMLElement())
440             continue;
441         HTMLElement* e = toHTMLElement(element);
442         const AtomicString& idAttrVal = e->getIdAttribute();
443         const AtomicString& nameAttrVal = e->getNameAttribute();
444         if (!idAttrVal.isEmpty())
445             appendIdCache(idAttrVal, e);
446         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(e)))
447             appendNameCache(nameAttrVal, e);
448     }
449
450     setHasNameCache();
451 }
452
453 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
454 {
455     if (name.isEmpty())
456         return false;
457
458     updateNameCache();
459
460     if (Vector<Element*>* cache = idCache(name)) {
461         if (!cache->isEmpty())
462             return true;
463     }
464
465     if (Vector<Element*>* cache = nameCache(name)) {
466         if (!cache->isEmpty())
467             return true;
468     }
469
470     return false;
471 }
472
473 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >& result) const
474 {
475     ASSERT(result.isEmpty());
476     if (name.isEmpty())
477         return;
478
479     updateNameCache();
480
481     Vector<Element*>* idResults = idCache(name);
482     Vector<Element*>* nameResults = nameCache(name);
483
484     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
485         result.append(idResults->at(i));
486
487     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
488         result.append(nameResults->at(i));
489 }
490
491 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
492 {
493     return m_base->getElementsByTagName(name);
494 }
495
496 void HTMLCollectionCacheBase::append(NodeCacheMap& map, const AtomicString& key, Element* element)
497 {
498     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->second;
499     if (!vector)
500         vector = adoptPtr(new Vector<Element*>);
501     vector->append(element);
502 }
503
504 } // namespace WebCore