Home | History | Annotate | Download | only in html 
      1 /*
      2  * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org)
      3  *           (C) 1999 Antti Koivisto (koivisto (at) kde.org)
      4  * Copyright (C) 2003-2008, 2011, 2012, 2014 Apple Inc. All rights reserved.
      5  * Copyright (C) 2014 Samsung Electronics. All rights reserved.
      6  *
      7  * This library is free software; you can redistribute it and/or
      8  * modify it under the terms of the GNU Library General Public
      9  * License as published by the Free Software Foundation; either
     10  * version 2 of the License, or (at your option) any later version.
     11  *
     12  * This library is distributed in the hope that it will be useful,
     13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     15  * Library General Public License for more details.
     16  *
     17  * You should have received a copy of the GNU Library General Public License
     18  * along with this library; see the file COPYING.LIB.  If not, write to
     19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     20  * Boston, MA 02110-1301, USA.
     21  *
     22  */
     23 
     24 #include "config.h"
     25 #include "core/html/HTMLCollection.h"
     26 
     27 #include "core/HTMLNames.h"
     28 #include "core/dom/ClassCollection.h"
     29 #include "core/dom/ElementTraversal.h"
     30 #include "core/dom/NodeRareData.h"
     31 #include "core/html/DocumentNameCollection.h"
     32 #include "core/html/HTMLDataListOptionsCollection.h"
     33 #include "core/html/HTMLElement.h"
     34 #include "core/html/HTMLObjectElement.h"
     35 #include "core/html/HTMLOptionElement.h"
     36 #include "core/html/HTMLOptionsCollection.h"
     37 #include "core/html/HTMLTagCollection.h"
     38 #include "core/html/WindowNameCollection.h"
     39 #include "wtf/HashSet.h"
     40 
     41 namespace blink {
     42 
     43 using namespace HTMLNames;
     44 
     45 static bool shouldTypeOnlyIncludeDirectChildren(CollectionType type)
     46 {
     47     switch (type) {
     48     case ClassCollectionType:
     49     case TagCollectionType:
     50     case HTMLTagCollectionType:
     51     case DocAll:
     52     case DocAnchors:
     53     case DocApplets:
     54     case DocEmbeds:
     55     case DocForms:
     56     case DocImages:
     57     case DocLinks:
     58     case DocScripts:
     59     case DocumentNamedItems:
     60     case MapAreas:
     61     case TableRows:
     62     case SelectOptions:
     63     case SelectedOptions:
     64     case DataListOptions:
     65     case WindowNamedItems:
     66     case FormControls:
     67         return false;
     68     case NodeChildren:
     69     case TRCells:
     70     case TSectionRows:
     71     case TableTBodies:
     72         return true;
     73     case NameNodeListType:
     74     case RadioNodeListType:
     75     case RadioImgNodeListType:
     76     case LabelsNodeListType:
     77         break;
     78     }
     79     ASSERT_NOT_REACHED();
     80     return false;
     81 }
     82 
     83 static NodeListRootType rootTypeFromCollectionType(CollectionType type)
     84 {
     85     switch (type) {
     86     case DocImages:
     87     case DocApplets:
     88     case DocEmbeds:
     89     case DocForms:
     90     case DocLinks:
     91     case DocAnchors:
     92     case DocScripts:
     93     case DocAll:
     94     case WindowNamedItems:
     95     case DocumentNamedItems:
     96     case FormControls:
     97         return NodeListIsRootedAtDocument;
     98     case ClassCollectionType:
     99     case TagCollectionType:
    100     case HTMLTagCollectionType:
    101     case NodeChildren:
    102     case TableTBodies:
    103     case TSectionRows:
    104     case TableRows:
    105     case TRCells:
    106     case SelectOptions:
    107     case SelectedOptions:
    108     case DataListOptions:
    109     case MapAreas:
    110         return NodeListIsRootedAtNode;
    111     case NameNodeListType:
    112     case RadioNodeListType:
    113     case RadioImgNodeListType:
    114     case LabelsNodeListType:
    115         break;
    116     }
    117     ASSERT_NOT_REACHED();
    118     return NodeListIsRootedAtNode;
    119 }
    120 
    121 static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(CollectionType type)
    122 {
    123     switch (type) {
    124     case TagCollectionType:
    125     case HTMLTagCollectionType:
    126     case DocImages:
    127     case DocEmbeds:
    128     case DocForms:
    129     case DocScripts:
    130     case DocAll:
    131     case NodeChildren:
    132     case TableTBodies:
    133     case TSectionRows:
    134     case TableRows:
    135     case TRCells:
    136     case SelectOptions:
    137     case MapAreas:
    138         return DoNotInvalidateOnAttributeChanges;
    139     case DocApplets:
    140     case SelectedOptions:
    141     case DataListOptions:
    142         // FIXME: We can do better some day.
    143         return InvalidateOnAnyAttrChange;
    144     case DocAnchors:
    145         return InvalidateOnNameAttrChange;
    146     case DocLinks:
    147         return InvalidateOnHRefAttrChange;
    148     case WindowNamedItems:
    149         return InvalidateOnIdNameAttrChange;
    150     case DocumentNamedItems:
    151         return InvalidateOnIdNameAttrChange;
    152     case FormControls:
    153         return InvalidateForFormControls;
    154     case ClassCollectionType:
    155         return InvalidateOnClassAttrChange;
    156     case NameNodeListType:
    157     case RadioNodeListType:
    158     case RadioImgNodeListType:
    159     case LabelsNodeListType:
    160         break;
    161     }
    162     ASSERT_NOT_REACHED();
    163     return DoNotInvalidateOnAttributeChanges;
    164 }
    165 
    166 HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
    167     : LiveNodeListBase(ownerNode, rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type)
    168     , m_overridesItemAfter(itemAfterOverrideType == OverridesItemAfter)
    169     , m_shouldOnlyIncludeDirectChildren(shouldTypeOnlyIncludeDirectChildren(type))
    170 {
    171 }
    172 
    173 PassRefPtrWillBeRawPtr<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
    174 {
    175     return adoptRefWillBeNoop(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
    176 }
    177 
    178 HTMLCollection::~HTMLCollection()
    179 {
    180 #if !ENABLE(OILPAN)
    181     if (hasValidIdNameCache())
    182         unregisterIdNameCacheFromDocument(document());
    183     // Named HTMLCollection types remove cache by themselves.
    184     if (isUnnamedHTMLCollectionType(type()))
    185         ownerNode().nodeLists()->removeCache(this, type());
    186 #endif
    187 }
    188 
    189 void HTMLCollection::invalidateCache(Document* oldDocument) const
    190 {
    191     m_collectionItemsCache.invalidate();
    192     invalidateIdNameCacheMaps(oldDocument);
    193 }
    194 
    195 unsigned HTMLCollection::length() const
    196 {
    197     return m_collectionItemsCache.nodeCount(*this);
    198 }
    199 
    200 Element* HTMLCollection::item(unsigned offset) const
    201 {
    202     return m_collectionItemsCache.nodeAt(*this, offset);
    203 }
    204 
    205 static inline bool isMatchingHTMLElement(const HTMLCollection& htmlCollection, const HTMLElement& element)
    206 {
    207     switch (htmlCollection.type()) {
    208     case DocImages:
    209         return element.hasTagName(imgTag);
    210     case DocScripts:
    211         return element.hasTagName(scriptTag);
    212     case DocForms:
    213         return element.hasTagName(formTag);
    214     case DocumentNamedItems:
    215         return toDocumentNameCollection(htmlCollection).elementMatches(element);
    216     case TableTBodies:
    217         return element.hasTagName(tbodyTag);
    218     case TRCells:
    219         return element.hasTagName(tdTag) || element.hasTagName(thTag);
    220     case TSectionRows:
    221         return element.hasTagName(trTag);
    222     case SelectOptions:
    223         return toHTMLOptionsCollection(htmlCollection).elementMatches(element);
    224     case SelectedOptions:
    225         return isHTMLOptionElement(element) && toHTMLOptionElement(element).selected();
    226     case DataListOptions:
    227         return toHTMLDataListOptionsCollection(htmlCollection).elementMatches(element);
    228     case MapAreas:
    229         return element.hasTagName(areaTag);
    230     case DocApplets:
    231         return element.hasTagName(appletTag) || (isHTMLObjectElement(element) && toHTMLObjectElement(element).containsJavaApplet());
    232     case DocEmbeds:
    233         return element.hasTagName(embedTag);
    234     case DocLinks:
    235         return (element.hasTagName(aTag) || element.hasTagName(areaTag)) && element.fastHasAttribute(hrefAttr);
    236     case DocAnchors:
    237         return element.hasTagName(aTag) && element.fastHasAttribute(nameAttr);
    238     case ClassCollectionType:
    239     case TagCollectionType:
    240     case HTMLTagCollectionType:
    241     case DocAll:
    242     case NodeChildren:
    243     case FormControls:
    244     case TableRows:
    245     case WindowNamedItems:
    246     case NameNodeListType:
    247     case RadioNodeListType:
    248     case RadioImgNodeListType:
    249     case LabelsNodeListType:
    250         ASSERT_NOT_REACHED();
    251     }
    252     return false;
    253 }
    254 
    255 inline bool HTMLCollection::elementMatches(const Element& element) const
    256 {
    257     // These collections apply to any kind of Elements, not just HTMLElements.
    258     switch (type()) {
    259     case DocAll:
    260     case NodeChildren:
    261         return true;
    262     case ClassCollectionType:
    263         return toClassCollection(*this).elementMatches(element);
    264     case TagCollectionType:
    265         return toTagCollection(*this).elementMatches(element);
    266     case HTMLTagCollectionType:
    267         return toHTMLTagCollection(*this).elementMatches(element);
    268     case WindowNamedItems:
    269         return toWindowNameCollection(*this).elementMatches(element);
    270     default:
    271         break;
    272     }
    273 
    274     // The following only applies to HTMLElements.
    275     return element.isHTMLElement() && isMatchingHTMLElement(*this, toHTMLElement(element));
    276 }
    277 
    278 namespace {
    279 
    280 template <class HTMLCollectionType>
    281 class IsMatch {
    282 public:
    283     IsMatch(const HTMLCollectionType& list)
    284         : m_list(list)
    285     { }
    286 
    287     bool operator() (const Element& element) const
    288     {
    289         return m_list.elementMatches(element);
    290     }
    291 
    292 private:
    293     const HTMLCollectionType& m_list;
    294 };
    295 
    296 } // namespace
    297 
    298 template <class HTMLCollectionType>
    299 static inline IsMatch<HTMLCollectionType> makeIsMatch(const HTMLCollectionType& list) { return IsMatch<HTMLCollectionType>(list); }
    300 
    301 Element* HTMLCollection::virtualItemAfter(Element*) const
    302 {
    303     ASSERT_NOT_REACHED();
    304     return 0;
    305 }
    306 
    307 static inline bool nameShouldBeVisibleInDocumentAll(const HTMLElement& element)
    308 {
    309     // http://www.whatwg.org/specs/web-apps/current-work/multipage/common-dom-interfaces.html#dom-htmlallcollection-nameditem:
    310     // The document.all collection returns only certain types of elements by name,
    311     // although it returns any type of element by id.
    312     return element.hasTagName(aTag)
    313         || element.hasTagName(appletTag)
    314         || element.hasTagName(areaTag)
    315         || element.hasTagName(embedTag)
    316         || element.hasTagName(formTag)
    317         || element.hasTagName(frameTag)
    318         || element.hasTagName(framesetTag)
    319         || element.hasTagName(iframeTag)
    320         || element.hasTagName(imgTag)
    321         || element.hasTagName(inputTag)
    322         || element.hasTagName(objectTag)
    323         || element.hasTagName(selectTag);
    324 }
    325 
    326 Element* HTMLCollection::traverseToFirst() const
    327 {
    328     switch (type()) {
    329     case HTMLTagCollectionType:
    330         return ElementTraversal::firstWithin(rootNode(), makeIsMatch(toHTMLTagCollection(*this)));
    331     case ClassCollectionType:
    332         return ElementTraversal::firstWithin(rootNode(), makeIsMatch(toClassCollection(*this)));
    333     default:
    334         if (overridesItemAfter())
    335             return virtualItemAfter(0);
    336         if (shouldOnlyIncludeDirectChildren())
    337             return ElementTraversal::firstChild(rootNode(), makeIsMatch(*this));
    338         return ElementTraversal::firstWithin(rootNode(), makeIsMatch(*this));
    339     }
    340 }
    341 
    342 Element* HTMLCollection::traverseToLast() const
    343 {
    344     ASSERT(canTraverseBackward());
    345     if (shouldOnlyIncludeDirectChildren())
    346         return ElementTraversal::lastChild(rootNode(), makeIsMatch(*this));
    347     return ElementTraversal::lastWithin(rootNode(), makeIsMatch(*this));
    348 }
    349 
    350 Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset) const
    351 {
    352     ASSERT(currentOffset < offset);
    353     switch (type()) {
    354     case HTMLTagCollectionType:
    355         return traverseMatchingElementsForwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(toHTMLTagCollection(*this)));
    356     case ClassCollectionType:
    357         return traverseMatchingElementsForwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(toClassCollection(*this)));
    358     default:
    359         if (overridesItemAfter()) {
    360             for (Element* next = virtualItemAfter(&currentElement); next; next = virtualItemAfter(next)) {
    361                 if (++currentOffset == offset)
    362                     return next;
    363             }
    364             return 0;
    365         }
    366         if (shouldOnlyIncludeDirectChildren()) {
    367             IsMatch<HTMLCollection> isMatch(*this);
    368             for (Element* next = ElementTraversal::nextSibling(currentElement, isMatch); next; next = ElementTraversal::nextSibling(*next, isMatch)) {
    369                 if (++currentOffset == offset)
    370                     return next;
    371             }
    372             return 0;
    373         }
    374         return traverseMatchingElementsForwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(*this));
    375     }
    376 }
    377 
    378 Element* HTMLCollection::traverseBackwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset) const
    379 {
    380     ASSERT(currentOffset > offset);
    381     ASSERT(canTraverseBackward());
    382     if (shouldOnlyIncludeDirectChildren()) {
    383         IsMatch<HTMLCollection> isMatch(*this);
    384         for (Element* previous = ElementTraversal::previousSibling(currentElement, isMatch); previous; previous = ElementTraversal::previousSibling(*previous, isMatch)) {
    385             if (--currentOffset == offset)
    386                 return previous;
    387         }
    388         return 0;
    389     }
    390     return traverseMatchingElementsBackwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(*this));
    391 }
    392 
    393 Element* HTMLCollection::namedItem(const AtomicString& name) const
    394 {
    395     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
    396     // This method first searches for an object with a matching id
    397     // attribute. If a match is not found, the method then searches for an
    398     // object with a matching name attribute, but only on those elements
    399     // that are allowed a name attribute.
    400     updateIdNameCache();
    401 
    402     const NamedItemCache& cache = namedItemCache();
    403     WillBeHeapVector<RawPtrWillBeMember<Element> >* idResults = cache.getElementsById(name);
    404     if (idResults && !idResults->isEmpty())
    405         return idResults->first();
    406 
    407     WillBeHeapVector<RawPtrWillBeMember<Element> >* nameResults = cache.getElementsByName(name);
    408     if (nameResults && !nameResults->isEmpty())
    409         return nameResults->first();
    410 
    411     return 0;
    412 }
    413 
    414 bool HTMLCollection::namedPropertyQuery(const AtomicString& name, ExceptionState&)
    415 {
    416     return namedItem(name);
    417 }
    418 
    419 void HTMLCollection::supportedPropertyNames(Vector<String>& names)
    420 {
    421     // As per the specification (http://dom.spec.whatwg.org/#htmlcollection):
    422     // The supported property names are the values from the list returned by these steps:
    423     // 1. Let result be an empty list.
    424     // 2. For each element represented by the collection, in tree order, run these substeps:
    425     //   1. If element has an ID which is neither the empty string nor is in result, append element's ID to result.
    426     //   2. If element is in the HTML namespace and has a name attribute whose value is neither the empty string
    427     //      nor is in result, append element's name attribute value to result.
    428     // 3. Return result.
    429     HashSet<AtomicString> existingNames;
    430     unsigned length = this->length();
    431     for (unsigned i = 0; i < length; ++i) {
    432         Element* element = item(i);
    433         const AtomicString& idAttribute = element->getIdAttribute();
    434         if (!idAttribute.isEmpty()) {
    435             HashSet<AtomicString>::AddResult addResult = existingNames.add(idAttribute);
    436             if (addResult.isNewEntry)
    437                 names.append(idAttribute);
    438         }
    439         if (!element->isHTMLElement())
    440             continue;
    441         const AtomicString& nameAttribute = element->getNameAttribute();
    442         if (!nameAttribute.isEmpty() && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element)))) {
    443             HashSet<AtomicString>::AddResult addResult = existingNames.add(nameAttribute);
    444             if (addResult.isNewEntry)
    445                 names.append(nameAttribute);
    446         }
    447     }
    448 }
    449 
    450 void HTMLCollection::namedPropertyEnumerator(Vector<String>& names, ExceptionState&)
    451 {
    452     supportedPropertyNames(names);
    453 }
    454 
    455 void HTMLCollection::updateIdNameCache() const
    456 {
    457     if (hasValidIdNameCache())
    458         return;
    459 
    460     OwnPtrWillBeRawPtr<NamedItemCache> cache = NamedItemCache::create();
    461     unsigned length = this->length();
    462     for (unsigned i = 0; i < length; ++i) {
    463         Element* element = item(i);
    464         const AtomicString& idAttrVal = element->getIdAttribute();
    465         if (!idAttrVal.isEmpty())
    466             cache->addElementWithId(idAttrVal, element);
    467         if (!element->isHTMLElement())
    468             continue;
    469         const AtomicString& nameAttrVal = element->getNameAttribute();
    470         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element))))
    471             cache->addElementWithName(nameAttrVal, element);
    472     }
    473     // Set the named item cache last as traversing the tree may cause cache invalidation.
    474     setNamedItemCache(cache.release());
    475 }
    476 
    477 void HTMLCollection::namedItems(const AtomicString& name, WillBeHeapVector<RefPtrWillBeMember<Element> >& result) const
    478 {
    479     ASSERT(result.isEmpty());
    480     if (name.isEmpty())
    481         return;
    482 
    483     updateIdNameCache();
    484 
    485     const NamedItemCache& cache = namedItemCache();
    486     if (WillBeHeapVector<RawPtrWillBeMember<Element> >* idResults = cache.getElementsById(name)) {
    487         for (unsigned i = 0; i < idResults->size(); ++i)
    488             result.append(idResults->at(i));
    489     }
    490     if (WillBeHeapVector<RawPtrWillBeMember<Element> >* nameResults = cache.getElementsByName(name)) {
    491         for (unsigned i = 0; i < nameResults->size(); ++i)
    492             result.append(nameResults->at(i));
    493     }
    494 }
    495 
    496 HTMLCollection::NamedItemCache::NamedItemCache()
    497 {
    498 }
    499 
    500 void HTMLCollection::trace(Visitor* visitor)
    501 {
    502     visitor->trace(m_namedItemCache);
    503     visitor->trace(m_collectionItemsCache);
    504     LiveNodeListBase::trace(visitor);
    505 }
    506 
    507 } // namespace blink
    508