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
34namespace WebCore {
35
36using namespace HTMLNames;
37
38static 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
68static 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
98static 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
134HTMLCollection::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
148PassRef<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
149{
150    return adoptRef(*new HTMLCollection(base, type));
151}
152
153HTMLCollection::~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
164ContainerNode& HTMLCollection::rootNode() const
165{
166    if (isRootedAtDocument() && ownerNode().inDocument())
167        return ownerNode().document();
168
169    return ownerNode();
170}
171
172inline 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 element.hasTagName(optionTag) && toHTMLOptionElement(element).selected();
195    case DataListOptions:
196        if (element.hasTagName(optionTag)) {
197            HTMLOptionElement& option = toHTMLOptionElement(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 element.hasTagName(appletTag) || (element.hasTagName(objectTag) && toHTMLObjectElement(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).nodeMatches(&element);
217    case WindowNamedItems:
218        return static_cast<const WindowNameCollection&>(htmlCollection).nodeMatches(&element);
219    case FormControls:
220    case TableRows:
221        break;
222    }
223    ASSERT_NOT_REACHED();
224    return false;
225}
226
227static Element* previousElement(ContainerNode& base, Element* previous, bool onlyIncludeDirectChildren)
228{
229    return onlyIncludeDirectChildren ? ElementTraversal::previousSibling(previous) : ElementTraversal::previous(previous, &base);
230}
231
232ALWAYS_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
243inline 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
251inline 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
259unsigned HTMLCollection::length() const
260{
261    return m_indexCache.nodeCount(*this);
262}
263
264Node* HTMLCollection::item(unsigned offset) const
265{
266    return m_indexCache.nodeAt(*this, offset);
267}
268
269static 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
282inline 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
290inline 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
298inline 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
307inline 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
334Element* HTMLCollection::collectionBegin() const
335{
336    return firstElement(rootNode());
337}
338
339Element* 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
347void HTMLCollection::collectionTraverseForward(Element*& current, unsigned count, unsigned& traversedCount) const
348{
349    current = traverseForward(*current, count, traversedCount, rootNode());
350}
351
352void 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
365void 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
375void HTMLCollection::invalidateNamedElementCache(Document& document) const
376{
377    ASSERT(hasNamedElementCache());
378    document.collectionWillClearIdNameMap(*this);
379    m_namedElementCache = nullptr;
380}
381
382Node* 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 0;
392
393    ContainerNode& root = rootNode();
394    if (!usesCustomForwardOnlyTraversal() && root.isInTreeScope()) {
395        TreeScope& treeScope = root.treeScope();
396        Element* candidate = 0;
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 && (!candidate->isHTMLElement() || !nameShouldBeVisibleInDocumentAll(toHTMLElement(*candidate))))
404                    candidate = 0;
405            }
406        } else
407            return 0;
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 0;
429}
430
431void 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 (!element->isHTMLElement())
447            continue;
448        const AtomicString& nameAttrVal = element->getNameAttribute();
449        if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element))))
450            cache->appendNameCache(nameAttrVal, element);
451    }
452
453    cache->didPopulate();
454    setNameItemCache(WTF::move(cache));
455}
456
457bool 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
463void 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
482PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
483{
484    return ownerNode().getElementsByTagName(name);
485}
486
487} // namespace WebCore
488