2b53edd98a23221d6329132e7d7e2e7a441e5fa6
[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 static inline Node* lastDescendent(Node* node)
250 {
251     node = node->lastChild();
252     for (Node* current = node; current; current = current->lastChild())
253         node = current;
254     return node;
255 }
256
257 template<bool forward>
258 static Element* itemBeforeOrAfter(CollectionType type, Node* base, unsigned& offsetInArray, Node* previous)
259 {
260     ASSERT_UNUSED(offsetInArray, !offsetInArray);
261     bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren(type);
262     Node* rootNode = base;
263     Node* current;
264     if (previous)
265         current = nextNode<forward>(rootNode, previous, onlyIncludeDirectChildren);
266     else {
267         if (forward)
268             current = rootNode->firstChild();
269         else
270             current = onlyIncludeDirectChildren ? rootNode->lastChild() : lastDescendent(rootNode);
271     }
272
273     for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
274         if (current->isElementNode() && isAcceptableElement(type, toElement(current)))
275             return toElement(current);
276     }
277
278     return 0;
279 }
280
281 Element* HTMLCollection::itemBefore(unsigned& offsetInArray, Element* previous) const
282 {
283     return itemBeforeOrAfter<false>(type(), base(), offsetInArray, previous);
284 }
285
286 Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
287 {
288     return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
289 }
290
291 bool ALWAYS_INLINE HTMLCollection::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
292 {
293     ASSERT(isLengthCacheValid());
294     unsigned distanceFromLastItem = cachedLength() - offset;
295     if (!isItemCacheValid())
296         return distanceFromLastItem < offset;
297
298     return cachedItemOffset() < offset && distanceFromLastItem < offset - cachedItemOffset();
299 }
300     
301 bool ALWAYS_INLINE HTMLCollection::isFirstItemCloserThanCachedItem(unsigned offset) const
302 {
303     ASSERT(isItemCacheValid());
304     if (cachedItemOffset() < offset)
305         return false;
306
307     unsigned distanceFromCachedItem = cachedItemOffset() - offset;
308     return offset < distanceFromCachedItem;
309 }
310
311 unsigned HTMLCollection::length() const
312 {
313     if (isLengthCacheValid())
314         return cachedLength();
315
316     if (!isItemCacheValid() && !item(0)) {
317         ASSERT(isLengthCacheValid());
318         return 0;
319     }
320
321     ASSERT(isItemCacheValid());
322     ASSERT(cachedItem());
323     unsigned offset = cachedItemOffset();
324     do {
325         offset++;
326     } while (itemBeforeOrAfterCachedItem(offset));
327     ASSERT(isLengthCacheValid());
328
329     return offset;
330 }
331
332 Node* HTMLCollection::item(unsigned offset) const
333 {
334     if (isItemCacheValid() && cachedItemOffset() == offset)
335         return cachedItem();
336
337     if (isLengthCacheValid() && cachedLength() <= offset)
338         return 0;
339
340 #if ENABLE(MICRODATA)
341     if (type() == ItemProperties)
342         static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
343 #endif
344
345     if (isLengthCacheValid() && supportsItemBefore() && isLastItemCloserThanLastOrCachedItem(offset)) {
346         // FIXME: Need to figure out the last offset in array for HTMLFormCollection and HTMLPropertiesCollection
347         unsigned unusedOffsetInArray = 0;
348         Node* lastItem = itemBefore(unusedOffsetInArray, 0);
349         ASSERT(!unusedOffsetInArray);
350         ASSERT(lastItem);
351         setItemCache(lastItem, cachedLength() - 1, 0);
352     } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (!supportsItemBefore() && offset < cachedItemOffset())) {
353         unsigned offsetInArray = 0;
354         Node* firstItem = itemAfter(offsetInArray, 0);
355         if (!firstItem) {
356             setLengthCache(0);
357             return 0;
358         }
359         setItemCache(firstItem, 0, offsetInArray);
360         ASSERT(!cachedItemOffset());
361     }
362
363     if (cachedItemOffset() == offset)
364         return cachedItem();
365
366     return itemBeforeOrAfterCachedItem(offset);
367 }
368
369 Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
370 {
371     unsigned currentOffset = cachedItemOffset();
372     ASSERT(cachedItem()->isElementNode());
373     Element* currentItem = toElement(cachedItem());
374     ASSERT(currentOffset != offset);
375
376     unsigned offsetInArray = cachedElementsArrayOffset();
377
378     if (offset < cachedItemOffset()) {
379         ASSERT(supportsItemBefore());
380         while ((currentItem = itemBefore(offsetInArray, currentItem))) {
381             ASSERT(currentOffset);
382             currentOffset--;
383             if (currentOffset == offset) {
384                 setItemCache(currentItem, currentOffset, offsetInArray);
385                 return currentItem;
386             }
387         }
388         ASSERT_NOT_REACHED();
389         return 0;
390     }
391
392     while ((currentItem = itemAfter(offsetInArray, currentItem))) {
393         currentOffset++;
394         if (currentOffset == offset) {
395             setItemCache(currentItem, currentOffset, offsetInArray);
396             return currentItem;
397         }
398     }
399
400     unsigned offsetOfLastItem = currentOffset;
401     setLengthCache(offsetOfLastItem + 1);
402
403     return 0;
404 }
405
406 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
407 {
408     // The document.all collection returns only certain types of elements by name,
409     // although it returns any type of element by id.
410     return element->hasLocalName(appletTag)
411         || element->hasLocalName(embedTag)
412         || element->hasLocalName(formTag)
413         || element->hasLocalName(imgTag)
414         || element->hasLocalName(inputTag)
415         || element->hasLocalName(objectTag)
416         || element->hasLocalName(selectTag);
417 }
418
419 bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const AtomicString& name) const
420 {
421     if (!element->isHTMLElement())
422         return false;
423     
424     HTMLElement* e = toHTMLElement(element);
425     if (!checkName)
426         return e->getIdAttribute() == name;
427
428     if (type() == DocAll && !nameShouldBeVisibleInDocumentAll(e))
429         return false;
430
431     return e->getNameAttribute() == name && e->getIdAttribute() != name;
432 }
433
434 Node* HTMLCollection::namedItem(const AtomicString& name) const
435 {
436     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
437     // This method first searches for an object with a matching id
438     // attribute. If a match is not found, the method then searches for an
439     // object with a matching name attribute, but only on those elements
440     // that are allowed a name attribute.
441
442     unsigned arrayOffset = 0;
443     unsigned i = 0;
444     for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
445         if (checkForNameMatch(e, /* checkName */ false, name)) {
446             setItemCache(e, i, arrayOffset);
447             return e;
448         }
449         i++;
450     }
451
452     i = 0;
453     for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
454         if (checkForNameMatch(e, /* checkName */ true, name)) {
455             setItemCache(e, i, arrayOffset);
456             return e;
457         }
458         i++;
459     }
460
461     return 0;
462 }
463
464 void HTMLCollection::updateNameCache() const
465 {
466     if (hasNameCache())
467         return;
468
469     unsigned arrayOffset = 0;
470     for (Element* element = itemAfter(arrayOffset, 0); element; element = itemAfter(arrayOffset, element)) {
471         if (!element->isHTMLElement())
472             continue;
473         HTMLElement* e = toHTMLElement(element);
474         const AtomicString& idAttrVal = e->getIdAttribute();
475         const AtomicString& nameAttrVal = e->getNameAttribute();
476         if (!idAttrVal.isEmpty())
477             appendIdCache(idAttrVal, e);
478         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(e)))
479             appendNameCache(nameAttrVal, e);
480     }
481
482     setHasNameCache();
483 }
484
485 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
486 {
487     if (name.isEmpty())
488         return false;
489
490     updateNameCache();
491
492     if (Vector<Element*>* cache = idCache(name)) {
493         if (!cache->isEmpty())
494             return true;
495     }
496
497     if (Vector<Element*>* cache = nameCache(name)) {
498         if (!cache->isEmpty())
499             return true;
500     }
501
502     return false;
503 }
504
505 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >& result) const
506 {
507     ASSERT(result.isEmpty());
508     if (name.isEmpty())
509         return;
510
511     updateNameCache();
512
513     Vector<Element*>* idResults = idCache(name);
514     Vector<Element*>* nameResults = nameCache(name);
515
516     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
517         result.append(idResults->at(i));
518
519     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
520         result.append(nameResults->at(i));
521 }
522
523 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
524 {
525     return m_base->getElementsByTagName(name);
526 }
527
528 void HTMLCollectionCacheBase::append(NodeCacheMap& map, const AtomicString& key, Element* element)
529 {
530     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->second;
531     if (!vector)
532         vector = adoptPtr(new Vector<Element*>);
533     vector->append(element);
534 }
535
536 } // namespace WebCore