7ac86934349f270aeabbbaba2e960fd7a50cd2a8
[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 "ElementTraversal.h"
27 #include "HTMLDocument.h"
28 #include "HTMLNameCollection.h"
29 #include "HTMLNames.h"
30 #include "HTMLObjectElement.h"
31 #include "HTMLOptionElement.h"
32 #include "NodeRareData.h"
33
34 namespace WebCore {
35
36 using namespace HTMLNames;
37
38 static bool shouldOnlyIncludeDirectChildren(CollectionType type)
39 {
40     switch (type) {
41     case DocAll:
42     case DocAnchors:
43     case DocApplets:
44     case DocEmbeds:
45     case DocForms:
46     case DocImages:
47     case DocLinks:
48     case DocScripts:
49     case DocumentNamedItems:
50     case MapAreas:
51     case TableRows:
52     case SelectOptions:
53     case SelectedOptions:
54     case DataListOptions:
55     case WindowNamedItems:
56     case FormControls:
57         return false;
58     case NodeChildren:
59     case TRCells:
60     case TSectionRows:
61     case TableTBodies:
62         return true;
63     }
64     ASSERT_NOT_REACHED();
65     return false;
66 }
67
68 static HTMLCollection::RootType rootTypeFromCollectionType(CollectionType type)
69 {
70     switch (type) {
71     case DocImages:
72     case DocApplets:
73     case DocEmbeds:
74     case DocForms:
75     case DocLinks:
76     case DocAnchors:
77     case DocScripts:
78     case DocAll:
79     case WindowNamedItems:
80     case DocumentNamedItems:
81     case FormControls:
82         return HTMLCollection::IsRootedAtDocument;
83     case NodeChildren:
84     case TableTBodies:
85     case TSectionRows:
86     case TableRows:
87     case TRCells:
88     case SelectOptions:
89     case SelectedOptions:
90     case DataListOptions:
91     case MapAreas:
92         return HTMLCollection::IsRootedAtNode;
93     }
94     ASSERT_NOT_REACHED();
95     return HTMLCollection::IsRootedAtNode;
96 }
97
98 static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(CollectionType type)
99 {
100     switch (type) {
101     case DocImages:
102     case DocEmbeds:
103     case DocForms:
104     case DocScripts:
105     case DocAll:
106     case NodeChildren:
107     case TableTBodies:
108     case TSectionRows:
109     case TableRows:
110     case TRCells:
111     case SelectOptions:
112     case MapAreas:
113         return DoNotInvalidateOnAttributeChanges;
114     case DocApplets:
115     case SelectedOptions:
116     case DataListOptions:
117         // FIXME: We can do better some day.
118         return InvalidateOnAnyAttrChange;
119     case DocAnchors:
120         return InvalidateOnNameAttrChange;
121     case DocLinks:
122         return InvalidateOnHRefAttrChange;
123     case WindowNamedItems:
124         return InvalidateOnIdNameAttrChange;
125     case DocumentNamedItems:
126         return InvalidateOnIdNameAttrChange;
127     case FormControls:
128         return InvalidateForFormControls;
129     }
130     ASSERT_NOT_REACHED();
131     return DoNotInvalidateOnAttributeChanges;
132 }
133
134 HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType)
135     : m_ownerNode(ownerNode)
136     , m_indexCache(*this)
137     , m_collectionType(type)
138     , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
139     , m_rootType(rootTypeFromCollectionType(type))
140     , m_shouldOnlyIncludeDirectChildren(shouldOnlyIncludeDirectChildren(type))
141     , m_usesCustomForwardOnlyTraversal(traversalType == CustomForwardOnlyTraversal)
142 {
143     ASSERT(m_rootType == static_cast<unsigned>(rootTypeFromCollectionType(type)));
144     ASSERT(m_invalidationType == static_cast<unsigned>(invalidationTypeExcludingIdAndNameAttributes(type)));
145     ASSERT(m_collectionType == static_cast<unsigned>(type));
146 }
147
148 PassRef<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
149 {
150     return adoptRef(*new HTMLCollection(base, type));
151 }
152
153 HTMLCollection::~HTMLCollection()
154 {
155     if (m_indexCache.hasValidCache(*this))
156         document().unregisterCollection(*this);
157     if (hasNamedElementCache())
158         document().collectionWillClearIdNameMap(*this);
159     // HTMLNameCollection removes cache by itself.
160     if (type() != WindowNamedItems && type() != DocumentNamedItems)
161         ownerNode().nodeLists()->removeCachedCollection(this);
162 }
163
164 ContainerNode& HTMLCollection::rootNode() const
165 {
166     if (isRootedAtDocument() && ownerNode().inDocument())
167         return ownerNode().document();
168
169     return ownerNode();
170 }
171
172 inline bool isMatchingElement(const HTMLCollection& htmlCollection, Element& element)
173 {
174     CollectionType type = htmlCollection.type();
175     if (!element.isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems))
176         return false;
177
178     switch (type) {
179     case DocImages:
180         return element.hasTagName(imgTag);
181     case DocScripts:
182         return element.hasTagName(scriptTag);
183     case DocForms:
184         return element.hasTagName(formTag);
185     case TableTBodies:
186         return element.hasTagName(tbodyTag);
187     case TRCells:
188         return element.hasTagName(tdTag) || element.hasTagName(thTag);
189     case TSectionRows:
190         return element.hasTagName(trTag);
191     case SelectOptions:
192         return element.hasTagName(optionTag);
193     case SelectedOptions:
194         return is<HTMLOptionElement>(element) && downcast<HTMLOptionElement>(element).selected();
195     case DataListOptions:
196         if (is<HTMLOptionElement>(element)) {
197             HTMLOptionElement& option = downcast<HTMLOptionElement>(element);
198             if (!option.isDisabledFormControl() && !option.value().isEmpty())
199                 return true;
200         }
201         return false;
202     case MapAreas:
203         return element.hasTagName(areaTag);
204     case DocApplets:
205         return is<HTMLAppletElement>(element) || (is<HTMLObjectElement>(element) && downcast<HTMLObjectElement>(element).containsJavaApplet());
206     case DocEmbeds:
207         return element.hasTagName(embedTag);
208     case DocLinks:
209         return (element.hasTagName(aTag) || element.hasTagName(areaTag)) && element.fastHasAttribute(hrefAttr);
210     case DocAnchors:
211         return element.hasTagName(aTag) && element.fastHasAttribute(nameAttr);
212     case DocAll:
213     case NodeChildren:
214         return true;
215     case DocumentNamedItems:
216         return static_cast<const DocumentNameCollection&>(htmlCollection).elementMatches(element);
217     case WindowNamedItems:
218         return static_cast<const WindowNameCollection&>(htmlCollection).elementMatches(element);
219     case FormControls:
220     case TableRows:
221         break;
222     }
223     ASSERT_NOT_REACHED();
224     return false;
225 }
226
227 static Element* previousElement(ContainerNode& base, Element* previous, bool onlyIncludeDirectChildren)
228 {
229     return onlyIncludeDirectChildren ? ElementTraversal::previousSibling(previous) : ElementTraversal::previous(previous, &base);
230 }
231
232 ALWAYS_INLINE Element* HTMLCollection::iterateForPreviousElement(Element* current) const
233 {
234     bool onlyIncludeDirectChildren = m_shouldOnlyIncludeDirectChildren;
235     ContainerNode& rootNode = this->rootNode();
236     for (; current; current = previousElement(rootNode, current, onlyIncludeDirectChildren)) {
237         if (isMatchingElement(*this, *current))
238             return current;
239     }
240     return nullptr;
241 }
242
243 inline Element* firstMatchingElement(const HTMLCollection& collection, ContainerNode& root)
244 {
245     Element* element = ElementTraversal::firstWithin(&root);
246     while (element && !isMatchingElement(collection, *element))
247         element = ElementTraversal::next(element, &root);
248     return element;
249 }
250
251 inline Element* nextMatchingElement(const HTMLCollection& collection, Element* current, ContainerNode& root)
252 {
253     do {
254         current = ElementTraversal::next(current, &root);
255     } while (current && !isMatchingElement(collection, *current));
256     return current;
257 }
258
259 unsigned HTMLCollection::length() const
260 {
261     return m_indexCache.nodeCount(*this);
262 }
263
264 Node* HTMLCollection::item(unsigned offset) const
265 {
266     return m_indexCache.nodeAt(*this, offset);
267 }
268
269 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement& element)
270 {
271     // The document.all collection returns only certain types of elements by name,
272     // although it returns any type of element by id.
273     return element.hasTagName(appletTag)
274         || element.hasTagName(embedTag)
275         || element.hasTagName(formTag)
276         || element.hasTagName(imgTag)
277         || element.hasTagName(inputTag)
278         || element.hasTagName(objectTag)
279         || element.hasTagName(selectTag);
280 }
281
282 inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, ContainerNode& root)
283 {
284     Element* element = ElementTraversal::firstWithin(&root);
285     while (element && !isMatchingElement(nodeList, *element))
286         element = ElementTraversal::nextSibling(element);
287     return element;
288 }
289
290 inline Element* nextMatchingSiblingElement(const HTMLCollection& nodeList, Element* current)
291 {
292     do {
293         current = ElementTraversal::nextSibling(current);
294     } while (current && !isMatchingElement(nodeList, *current));
295     return current;
296 }
297
298 inline Element* HTMLCollection::firstElement(ContainerNode& root) const
299 {
300     if (usesCustomForwardOnlyTraversal())
301         return customElementAfter(nullptr);
302     if (m_shouldOnlyIncludeDirectChildren)
303         return firstMatchingChildElement(*this, root);
304     return firstMatchingElement(*this, root);
305 }
306
307 inline Element* HTMLCollection::traverseForward(Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root) const
308 {
309     Element* element = &current;
310     if (usesCustomForwardOnlyTraversal()) {
311         for (traversedCount = 0; traversedCount < count; ++traversedCount) {
312             element = customElementAfter(element);
313             if (!element)
314                 return nullptr;
315         }
316         return element;
317     }
318     if (m_shouldOnlyIncludeDirectChildren) {
319         for (traversedCount = 0; traversedCount < count; ++traversedCount) {
320             element = nextMatchingSiblingElement(*this, element);
321             if (!element)
322                 return nullptr;
323         }
324         return element;
325     }
326     for (traversedCount = 0; traversedCount < count; ++traversedCount) {
327         element = nextMatchingElement(*this, element, root);
328         if (!element)
329             return nullptr;
330     }
331     return element;
332 }
333
334 Element* HTMLCollection::collectionBegin() const
335 {
336     return firstElement(rootNode());
337 }
338
339 Element* HTMLCollection::collectionLast() const
340 {
341     // FIXME: This should be optimized similarly to the forward case.
342     auto& root = rootNode();
343     Element* last = m_shouldOnlyIncludeDirectChildren ? ElementTraversal::lastChild(&root) : ElementTraversal::lastWithin(&root);
344     return iterateForPreviousElement(last);
345 }
346
347 void HTMLCollection::collectionTraverseForward(Element*& current, unsigned count, unsigned& traversedCount) const
348 {
349     current = traverseForward(*current, count, traversedCount, rootNode());
350 }
351
352 void HTMLCollection::collectionTraverseBackward(Element*& current, unsigned count) const
353 {
354     // FIXME: This should be optimized similarly to the forward case.
355     auto& root = rootNode();
356     if (m_shouldOnlyIncludeDirectChildren) {
357         for (; count && current ; --count)
358             current = iterateForPreviousElement(ElementTraversal::previousSibling(current));
359         return;
360     }
361     for (; count && current ; --count)
362         current = iterateForPreviousElement(ElementTraversal::previous(current, &root));
363 }
364
365 void HTMLCollection::invalidateCache(Document& document) const
366 {
367     if (m_indexCache.hasValidCache(*this)) {
368         document.unregisterCollection(const_cast<HTMLCollection&>(*this));
369         m_indexCache.invalidate(*this);
370     }
371     if (hasNamedElementCache())
372         invalidateNamedElementCache(document);
373 }
374
375 void HTMLCollection::invalidateNamedElementCache(Document& document) const
376 {
377     ASSERT(hasNamedElementCache());
378     document.collectionWillClearIdNameMap(*this);
379     m_namedElementCache = nullptr;
380 }
381
382 Node* HTMLCollection::namedItem(const AtomicString& name) const
383 {
384     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
385     // This method first searches for an object with a matching id
386     // attribute. If a match is not found, the method then searches for an
387     // object with a matching name attribute, but only on those elements
388     // that are allowed a name attribute.
389
390     if (name.isEmpty())
391         return nullptr;
392
393     ContainerNode& root = rootNode();
394     if (!usesCustomForwardOnlyTraversal() && root.isInTreeScope()) {
395         TreeScope& treeScope = root.treeScope();
396         Element* candidate = nullptr;
397         if (treeScope.hasElementWithId(*name.impl())) {
398             if (!treeScope.containsMultipleElementsWithId(name))
399                 candidate = treeScope.getElementById(name);
400         } else if (treeScope.hasElementWithName(*name.impl())) {
401             if (!treeScope.containsMultipleElementsWithName(name)) {
402                 candidate = treeScope.getElementByName(name);
403                 if (candidate && type() == DocAll && (!is<HTMLElement>(candidate) || !nameShouldBeVisibleInDocumentAll(downcast<HTMLElement>(*candidate))))
404                     candidate = nullptr;
405             }
406         } else
407             return nullptr;
408
409         if (candidate && isMatchingElement(*this, *candidate)
410             && (m_shouldOnlyIncludeDirectChildren ? candidate->parentNode() == &root : candidate->isDescendantOf(&root)))
411             return candidate;
412     }
413
414     // The pathological case. We need to walk the entire subtree.
415     updateNamedElementCache();
416     ASSERT(m_namedElementCache);
417
418     if (const Vector<Element*>* idResults = m_namedElementCache->findElementsWithId(name)) {
419         if (idResults->size())
420             return idResults->at(0);
421     }
422
423     if (const Vector<Element*>* nameResults = m_namedElementCache->findElementsWithName(name)) {
424         if (nameResults->size())
425             return nameResults->at(0);
426     }
427
428     return nullptr;
429 }
430
431 void HTMLCollection::updateNamedElementCache() const
432 {
433     if (hasNamedElementCache())
434         return;
435
436
437     auto cache = std::make_unique<CollectionNamedElementCache>();
438
439     unsigned size = m_indexCache.nodeCount(*this);
440     for (unsigned i = 0; i < size; i++) {
441         Element* element = m_indexCache.nodeAt(*this, i);
442         ASSERT(element);
443         const AtomicString& idAttrVal = element->getIdAttribute();
444         if (!idAttrVal.isEmpty())
445             cache->appendIdCache(idAttrVal, element);
446         if (!is<HTMLElement>(element))
447             continue;
448         const AtomicString& nameAttrVal = element->getNameAttribute();
449         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(downcast<HTMLElement>(*element))))
450             cache->appendNameCache(nameAttrVal, element);
451     }
452
453     cache->didPopulate();
454     setNameItemCache(WTF::move(cache));
455 }
456
457 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
458 {
459     // FIXME: We can do better when there are multiple elements of the same name.
460     return namedItem(name);
461 }
462
463 void HTMLCollection::namedItems(const AtomicString& name, Vector<Ref<Element>>& result) const
464 {
465     ASSERT(result.isEmpty());
466     if (name.isEmpty())
467         return;
468
469     updateNamedElementCache();
470     ASSERT(m_namedElementCache);
471
472     const Vector<Element*>* idResults = m_namedElementCache->findElementsWithId(name);
473     const Vector<Element*>* nameResults = m_namedElementCache->findElementsWithName(name);
474
475     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
476         result.append(*idResults->at(i));
477
478     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
479         result.append(*nameResults->at(i));
480 }
481
482 PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
483 {
484     return ownerNode().getElementsByTagName(name);
485 }
486
487 } // namespace WebCore