Unify HTMLCollection and DynamicNodeList
[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 NodeListCollectionType:
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 NodeListCollectionType:
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 NodeListCollectionType:
148         break;
149     }
150     ASSERT_NOT_REACHED();
151     return DoNotInvalidateOnAttributeChanges;
152 }
153     
154
155 HTMLCollection::HTMLCollection(Node* ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
156     : HTMLCollectionCacheBase(ownerNode, rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type),
157         WebCore::shouldOnlyIncludeDirectChildren(type), type, itemAfterOverrideType)
158 {
159     document()->registerNodeListCache(this);
160 }
161
162 PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
163 {
164     return adoptRef(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
165 }
166
167 HTMLCollection::~HTMLCollection()
168 {
169     if (isUnnamedDocumentCachedType(type())) {
170         ASSERT(base()->isDocumentNode());
171         static_cast<Document*>(base())->removeCachedHTMLCollection(this, type());
172     } else if (isNodeCollectionType(type())) {
173         ASSERT(base()->isElementNode());
174         toElement(base())->removeCachedHTMLCollection(this, type());
175     } else // HTMLNameCollection removes cache by itself.
176         ASSERT(type() == WindowNamedItems || type() == DocumentNamedItems);
177
178     document()->unregisterNodeListCache(this);
179 }
180
181 static inline bool isAcceptableElement(CollectionType type, Element* element)
182 {
183     if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren))
184         return false;
185
186     switch (type) {
187     case DocImages:
188         return element->hasLocalName(imgTag);
189     case DocScripts:
190         return element->hasLocalName(scriptTag);
191     case DocForms:
192         return element->hasLocalName(formTag);
193     case TableTBodies:
194         return element->hasLocalName(tbodyTag);
195     case TRCells:
196         return element->hasLocalName(tdTag) || element->hasLocalName(thTag);
197     case TSectionRows:
198         return element->hasLocalName(trTag);
199     case SelectOptions:
200         return element->hasLocalName(optionTag);
201     case SelectedOptions:
202         return element->hasLocalName(optionTag) && toHTMLOptionElement(element)->selected();
203     case DataListOptions:
204         if (element->hasLocalName(optionTag)) {
205             HTMLOptionElement* option = static_cast<HTMLOptionElement*>(element);
206             if (!option->disabled() && !option->value().isEmpty())
207                 return true;
208         }
209         return false;
210     case MapAreas:
211         return element->hasLocalName(areaTag);
212     case DocApplets:
213         return element->hasLocalName(appletTag) || (element->hasLocalName(objectTag) && static_cast<HTMLObjectElement*>(element)->containsJavaApplet());
214     case DocEmbeds:
215         return element->hasLocalName(embedTag);
216     case DocObjects:
217         return element->hasLocalName(objectTag);
218     case DocLinks:
219         return (element->hasLocalName(aTag) || element->hasLocalName(areaTag)) && element->fastHasAttribute(hrefAttr);
220     case DocAnchors:
221         return element->hasLocalName(aTag) && element->fastHasAttribute(nameAttr);
222     case DocAll:
223     case NodeChildren:
224         return true;
225 #if ENABLE(MICRODATA)
226     case ItemProperties:
227         return element->fastHasAttribute(itempropAttr);
228 #endif
229     case FormControls:
230     case DocumentNamedItems:
231     case TableRows:
232     case WindowNamedItems:
233     case NodeListCollectionType:
234         ASSERT_NOT_REACHED();
235     }
236     return false;
237 }
238
239 template<bool forward>
240 static Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
241 {
242     if (forward)
243         return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base);
244     else
245         return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base);
246 }
247
248 static inline Node* lastDescendent(Node* node)
249 {
250     node = node->lastChild();
251     for (Node* current = node; current; current = current->lastChild())
252         node = current;
253     return node;
254 }
255
256 static Node* firstNode(bool forward, Node* rootNode, bool onlyIncludeDirectChildren)
257 {
258     if (forward)
259         return rootNode->firstChild();
260     else
261         return onlyIncludeDirectChildren ? rootNode->lastChild() : lastDescendent(rootNode);
262 }
263
264 template <bool forward>
265 Node* DynamicNodeListCacheBase::iterateForNextNode(Node* current) const
266 {
267     bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren();
268     CollectionType collectionType = type();
269     Node* rootNode = this->rootNode();
270     for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
271         if (collectionType == NodeListCollectionType) {
272             if (current->isElementNode() && static_cast<const DynamicNodeList*>(this)->nodeMatches(toElement(current)))
273                 return toElement(current);
274         } else {
275             if (current->isElementNode() && isAcceptableElement(collectionType, toElement(current)))
276                 return toElement(current);
277         }
278     }
279
280     return 0;
281 }
282
283 // Without this ALWAYS_INLINE, length() and item() can be 100% slower.
284 template<bool forward> ALWAYS_INLINE
285 Node* DynamicNodeListCacheBase::itemBeforeOrAfter(Node* previous) const
286 {
287     Node* current;
288     if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
289         current = nextNode<forward>(rootNode(), previous, shouldOnlyIncludeDirectChildren());
290     else
291         current = firstNode(forward, rootNode(), previous);
292
293     if (type() == NodeListCollectionType && shouldOnlyIncludeDirectChildren()) // ChildNodeList
294         return current;
295
296     return iterateForNextNode<forward>(current);
297 }
298
299 // Without this ALWAYS_INLINE, length() and item() can be 100% slower.
300 ALWAYS_INLINE Node* DynamicNodeListCacheBase::itemBefore(Node* previous) const
301 {
302     return itemBeforeOrAfter<false>(previous);
303 }
304
305 // Without this ALWAYS_INLINE, length() and item() can be 100% slower.
306 ALWAYS_INLINE Node* DynamicNodeListCacheBase::itemAfter(unsigned& offsetInArray, Node* previous) const
307 {
308     if (UNLIKELY(overridesItemAfter())) // Without this UNLIKELY, length() can be 100% slower.
309         return static_cast<const HTMLCollection*>(this)->virtualItemAfter(offsetInArray, toElement(previous));
310     ASSERT(!offsetInArray);
311     return itemBeforeOrAfter<true>(previous);
312 }
313
314 bool ALWAYS_INLINE DynamicNodeListCacheBase::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
315 {
316     ASSERT(isLengthCacheValid());
317     unsigned distanceFromLastItem = cachedLength() - offset;
318     if (!isItemCacheValid())
319         return distanceFromLastItem < offset;
320
321     return cachedItemOffset() < offset && distanceFromLastItem < offset - cachedItemOffset();
322 }
323     
324 bool ALWAYS_INLINE DynamicNodeListCacheBase::isFirstItemCloserThanCachedItem(unsigned offset) const
325 {
326     ASSERT(isItemCacheValid());
327     if (cachedItemOffset() < offset)
328         return false;
329
330     unsigned distanceFromCachedItem = cachedItemOffset() - offset;
331     return offset < distanceFromCachedItem;
332 }
333
334 ALWAYS_INLINE void DynamicNodeListCacheBase::setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const
335 {
336     setItemCache(item, offset);
337     if (overridesItemAfter()) {
338         ASSERT(item->isElementNode());
339         static_cast<const HTMLCollectionCacheBase*>(this)->m_cachedElementsArrayOffset = elementsArrayOffset;
340     } else
341         ASSERT(!elementsArrayOffset);
342 }
343
344 ALWAYS_INLINE unsigned DynamicNodeListCacheBase::cachedElementsArrayOffset() const
345 {
346     return overridesItemAfter() ? static_cast<const HTMLCollectionCacheBase*>(this)->m_cachedElementsArrayOffset : 0;
347 }
348
349 unsigned DynamicNodeListCacheBase::lengthCommon() const
350 {
351     if (isLengthCacheValid())
352         return cachedLength();
353
354     itemCommon(UINT_MAX);
355     ASSERT(isLengthCacheValid());
356     
357     return cachedLength();
358 }
359
360 Node* DynamicNodeListCacheBase::itemCommon(unsigned offset) const
361 {
362     if (isItemCacheValid() && cachedItemOffset() == offset)
363         return cachedItem();
364
365     if (isLengthCacheValid() && cachedLength() <= offset)
366         return 0;
367
368 #if ENABLE(MICRODATA)
369     if (type() == ItemProperties)
370         static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
371 #endif
372
373     if (isLengthCacheValid() && !overridesItemAfter() && isLastItemCloserThanLastOrCachedItem(offset)) {
374         Node* lastItem = itemBefore(0);
375         ASSERT(lastItem);
376         setItemCache(lastItem, cachedLength() - 1, 0);
377     } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (overridesItemAfter() && offset < cachedItemOffset())) {
378         unsigned offsetInArray = 0;
379         Node* firstItem = itemAfter(offsetInArray, 0);
380         if (!firstItem) {
381             setLengthCache(0);
382             return 0;
383         }
384         setItemCache(firstItem, 0, offsetInArray);
385         ASSERT(!cachedItemOffset());
386     }
387
388     if (cachedItemOffset() == offset)
389         return cachedItem();
390
391     return itemBeforeOrAfterCachedItem(offset);
392 }
393
394 Node* DynamicNodeListCacheBase::itemBeforeOrAfterCachedItem(unsigned offset) const
395 {
396     unsigned currentOffset = cachedItemOffset();
397     Node* currentItem = cachedItem();
398     ASSERT(currentOffset != offset);
399
400     if (offset < cachedItemOffset()) {
401         ASSERT(!overridesItemAfter());
402         while ((currentItem = itemBefore(currentItem))) {
403             ASSERT(currentOffset);
404             currentOffset--;
405             if (currentOffset == offset) {
406                 setItemCache(currentItem, currentOffset, 0);
407                 return currentItem;
408             }
409         }
410         ASSERT_NOT_REACHED();
411         return 0;
412     }
413
414     unsigned offsetInArray = cachedElementsArrayOffset();
415     while ((currentItem = itemAfter(offsetInArray, currentItem))) {
416         currentOffset++;
417         if (currentOffset == offset) {
418             setItemCache(currentItem, currentOffset, offsetInArray);
419             return currentItem;
420         }
421     }
422
423     unsigned offsetOfLastItem = currentOffset;
424     setLengthCache(offsetOfLastItem + 1);
425
426     return 0;
427 }
428
429 Element* HTMLCollection::virtualItemAfter(unsigned&, Element*) const
430 {
431     ASSERT_NOT_REACHED();
432     return 0;
433 }
434
435 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
436 {
437     // The document.all collection returns only certain types of elements by name,
438     // although it returns any type of element by id.
439     return element->hasLocalName(appletTag)
440         || element->hasLocalName(embedTag)
441         || element->hasLocalName(formTag)
442         || element->hasLocalName(imgTag)
443         || element->hasLocalName(inputTag)
444         || element->hasLocalName(objectTag)
445         || element->hasLocalName(selectTag);
446 }
447
448 bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const AtomicString& name) const
449 {
450     if (!element->isHTMLElement())
451         return false;
452     
453     HTMLElement* e = toHTMLElement(element);
454     if (!checkName)
455         return e->getIdAttribute() == name;
456
457     if (type() == DocAll && !nameShouldBeVisibleInDocumentAll(e))
458         return false;
459
460     return e->getNameAttribute() == name && e->getIdAttribute() != name;
461 }
462
463 Node* HTMLCollection::namedItem(const AtomicString& name) const
464 {
465     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
466     // This method first searches for an object with a matching id
467     // attribute. If a match is not found, the method then searches for an
468     // object with a matching name attribute, but only on those elements
469     // that are allowed a name attribute.
470
471     unsigned arrayOffset = 0;
472     unsigned i = 0;
473     for (Node* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
474         if (checkForNameMatch(toElement(e), /* checkName */ false, name)) {
475             setItemCache(e, i, arrayOffset);
476             return e;
477         }
478         i++;
479     }
480
481     i = 0;
482     for (Node* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
483         if (checkForNameMatch(toElement(e), /* checkName */ true, name)) {
484             setItemCache(e, i, arrayOffset);
485             return toElement(e);
486         }
487         i++;
488     }
489
490     return 0;
491 }
492
493 void HTMLCollection::updateNameCache() const
494 {
495     if (hasNameCache())
496         return;
497
498     unsigned arrayOffset = 0;
499     for (Node* node = itemAfter(arrayOffset, 0); node; node = itemAfter(arrayOffset, node)) {
500         if (!node->isHTMLElement())
501             continue;
502         HTMLElement* e = toHTMLElement(node);
503         const AtomicString& idAttrVal = e->getIdAttribute();
504         const AtomicString& nameAttrVal = e->getNameAttribute();
505         if (!idAttrVal.isEmpty())
506             appendIdCache(idAttrVal, e);
507         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(e)))
508             appendNameCache(nameAttrVal, e);
509     }
510
511     setHasNameCache();
512 }
513
514 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
515 {
516     if (name.isEmpty())
517         return false;
518
519     updateNameCache();
520
521     if (Vector<Element*>* cache = idCache(name)) {
522         if (!cache->isEmpty())
523             return true;
524     }
525
526     if (Vector<Element*>* cache = nameCache(name)) {
527         if (!cache->isEmpty())
528             return true;
529     }
530
531     return false;
532 }
533
534 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >& result) const
535 {
536     ASSERT(result.isEmpty());
537     if (name.isEmpty())
538         return;
539
540     updateNameCache();
541
542     Vector<Element*>* idResults = idCache(name);
543     Vector<Element*>* nameResults = nameCache(name);
544
545     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
546         result.append(idResults->at(i));
547
548     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
549         result.append(nameResults->at(i));
550 }
551
552 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
553 {
554     return ownerNode()->getElementsByTagName(name);
555 }
556
557 void HTMLCollectionCacheBase::append(NodeCacheMap& map, const AtomicString& key, Element* element)
558 {
559     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->second;
560     if (!vector)
561         vector = adoptPtr(new Vector<Element*>);
562     vector->append(element);
563 }
564
565 } // namespace WebCore