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, 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 "core/html/HTMLCollection.h"
     25 
     26 #include "HTMLNames.h"
     27 #include "core/dom/ClassNodeList.h"
     28 #include "core/dom/ElementTraversal.h"
     29 #include "core/dom/NodeList.h"
     30 #include "core/dom/NodeRareData.h"
     31 #include "core/dom/NodeTraversal.h"
     32 #include "core/html/HTMLElement.h"
     33 #include "core/html/HTMLObjectElement.h"
     34 #include "core/html/HTMLOptionElement.h"
     35 
     36 namespace WebCore {
     37 
     38 using namespace HTMLNames;
     39 
     40 static bool shouldOnlyIncludeDirectChildren(CollectionType type)
     41 {
     42     switch (type) {
     43     case DocAll:
     44     case DocAnchors:
     45     case DocApplets:
     46     case DocEmbeds:
     47     case DocForms:
     48     case DocImages:
     49     case DocLinks:
     50     case DocScripts:
     51     case DocumentNamedItems:
     52     case MapAreas:
     53     case TableRows:
     54     case SelectOptions:
     55     case SelectedOptions:
     56     case DataListOptions:
     57     case WindowNamedItems:
     58     case FormControls:
     59         return false;
     60     case NodeChildren:
     61     case TRCells:
     62     case TSectionRows:
     63     case TableTBodies:
     64         return true;
     65     case ChildNodeListType:
     66     case ClassNodeListType:
     67     case NameNodeListType:
     68     case TagNodeListType:
     69     case HTMLTagNodeListType:
     70     case RadioNodeListType:
     71     case LabelsNodeListType:
     72         break;
     73     }
     74     ASSERT_NOT_REACHED();
     75     return false;
     76 }
     77 
     78 static NodeListRootType rootTypeFromCollectionType(CollectionType type)
     79 {
     80     switch (type) {
     81     case DocImages:
     82     case DocApplets:
     83     case DocEmbeds:
     84     case DocForms:
     85     case DocLinks:
     86     case DocAnchors:
     87     case DocScripts:
     88     case DocAll:
     89     case WindowNamedItems:
     90     case DocumentNamedItems:
     91     case FormControls:
     92         return NodeListIsRootedAtDocument;
     93     case NodeChildren:
     94     case TableTBodies:
     95     case TSectionRows:
     96     case TableRows:
     97     case TRCells:
     98     case SelectOptions:
     99     case SelectedOptions:
    100     case DataListOptions:
    101     case MapAreas:
    102         return NodeListIsRootedAtNode;
    103     case ChildNodeListType:
    104     case ClassNodeListType:
    105     case NameNodeListType:
    106     case TagNodeListType:
    107     case HTMLTagNodeListType:
    108     case RadioNodeListType:
    109     case LabelsNodeListType:
    110         break;
    111     }
    112     ASSERT_NOT_REACHED();
    113     return NodeListIsRootedAtNode;
    114 }
    115 
    116 static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(CollectionType type)
    117 {
    118     switch (type) {
    119     case DocImages:
    120     case DocEmbeds:
    121     case DocForms:
    122     case DocScripts:
    123     case DocAll:
    124     case NodeChildren:
    125     case TableTBodies:
    126     case TSectionRows:
    127     case TableRows:
    128     case TRCells:
    129     case SelectOptions:
    130     case MapAreas:
    131         return DoNotInvalidateOnAttributeChanges;
    132     case DocApplets:
    133     case SelectedOptions:
    134     case DataListOptions:
    135         // FIXME: We can do better some day.
    136         return InvalidateOnAnyAttrChange;
    137     case DocAnchors:
    138         return InvalidateOnNameAttrChange;
    139     case DocLinks:
    140         return InvalidateOnHRefAttrChange;
    141     case WindowNamedItems:
    142         return InvalidateOnIdNameAttrChange;
    143     case DocumentNamedItems:
    144         return InvalidateOnIdNameAttrChange;
    145     case FormControls:
    146         return InvalidateForFormControls;
    147     case ChildNodeListType:
    148     case ClassNodeListType:
    149     case NameNodeListType:
    150     case TagNodeListType:
    151     case HTMLTagNodeListType:
    152     case RadioNodeListType:
    153     case LabelsNodeListType:
    154         break;
    155     }
    156     ASSERT_NOT_REACHED();
    157     return DoNotInvalidateOnAttributeChanges;
    158 }
    159 
    160 HTMLCollection::HTMLCollection(Node* ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
    161     : LiveNodeListBase(ownerNode, rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type),
    162         WebCore::shouldOnlyIncludeDirectChildren(type), type, itemAfterOverrideType)
    163 {
    164     ScriptWrappable::init(this);
    165 }
    166 
    167 PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
    168 {
    169     return adoptRef(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
    170 }
    171 
    172 HTMLCollection::~HTMLCollection()
    173 {
    174     // HTMLNameCollection removes cache by itself.
    175     if (type() != WindowNamedItems && type() != DocumentNamedItems)
    176         ownerNode()->nodeLists()->removeCacheWithAtomicName(this, type());
    177 }
    178 
    179 template <class NodeListType>
    180 inline bool isMatchingElement(const NodeListType*, Element*);
    181 
    182 template <> inline bool isMatchingElement(const HTMLCollection* htmlCollection, Element* element)
    183 {
    184     CollectionType type = htmlCollection->type();
    185     if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems))
    186         return false;
    187 
    188     switch (type) {
    189     case DocImages:
    190         return element->hasLocalName(imgTag);
    191     case DocScripts:
    192         return element->hasLocalName(scriptTag);
    193     case DocForms:
    194         return element->hasLocalName(formTag);
    195     case TableTBodies:
    196         return element->hasLocalName(tbodyTag);
    197     case TRCells:
    198         return element->hasLocalName(tdTag) || element->hasLocalName(thTag);
    199     case TSectionRows:
    200         return element->hasLocalName(trTag);
    201     case SelectOptions:
    202         return element->hasLocalName(optionTag);
    203     case SelectedOptions:
    204         return element->hasLocalName(optionTag) && toHTMLOptionElement(element)->selected();
    205     case DataListOptions:
    206         if (element->hasLocalName(optionTag)) {
    207             HTMLOptionElement* option = toHTMLOptionElement(element);
    208             if (!option->isDisabledFormControl() && !option->value().isEmpty())
    209                 return true;
    210         }
    211         return false;
    212     case MapAreas:
    213         return element->hasLocalName(areaTag);
    214     case DocApplets:
    215         return element->hasLocalName(appletTag) || (element->hasLocalName(objectTag) && toHTMLObjectElement(element)->containsJavaApplet());
    216     case DocEmbeds:
    217         return element->hasLocalName(embedTag);
    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     case FormControls:
    226     case DocumentNamedItems:
    227     case TableRows:
    228     case WindowNamedItems:
    229     case ChildNodeListType:
    230     case ClassNodeListType:
    231     case NameNodeListType:
    232     case TagNodeListType:
    233     case HTMLTagNodeListType:
    234     case RadioNodeListType:
    235     case LabelsNodeListType:
    236         ASSERT_NOT_REACHED();
    237     }
    238     return false;
    239 }
    240 
    241 template <> inline bool isMatchingElement(const LiveNodeList* nodeList, Element* element)
    242 {
    243     return nodeList->nodeMatches(element);
    244 }
    245 
    246 template <> inline bool isMatchingElement(const HTMLTagNodeList* nodeList, Element* element)
    247 {
    248     return nodeList->nodeMatchesInlined(element);
    249 }
    250 
    251 template <> inline bool isMatchingElement(const ClassNodeList* nodeList, Element* element)
    252 {
    253     return nodeList->nodeMatchesInlined(element);
    254 }
    255 
    256 static Node* previousNode(Node& base, Node& previous, bool onlyIncludeDirectChildren)
    257 {
    258     return onlyIncludeDirectChildren ? previous.previousSibling() : NodeTraversal::previous(previous, &base);
    259 }
    260 
    261 static inline Node* lastDescendent(Node& node)
    262 {
    263     Node* descendent = node.lastChild();
    264     for (Node* current = descendent; current; current = current->lastChild())
    265         descendent = current;
    266     return descendent;
    267 }
    268 
    269 static Node* lastNode(Node& rootNode, bool onlyIncludeDirectChildren)
    270 {
    271     return onlyIncludeDirectChildren ? rootNode.lastChild() : lastDescendent(rootNode);
    272 }
    273 
    274 ALWAYS_INLINE Node* LiveNodeListBase::iterateForPreviousNode(Node* current) const
    275 {
    276     bool onlyIncludeDirectChildren = shouldOnlyIncludeDirectChildren();
    277     CollectionType collectionType = type();
    278     Node& rootNode = this->rootNode();
    279     for (; current; current = previousNode(rootNode, *current, onlyIncludeDirectChildren)) {
    280         if (isNodeList(collectionType)) {
    281             if (current->isElementNode() && isMatchingElement(static_cast<const LiveNodeList*>(this), toElement(current)))
    282                 return toElement(current);
    283         } else {
    284             if (current->isElementNode() && isMatchingElement(static_cast<const HTMLCollection*>(this), toElement(current)))
    285                 return toElement(current);
    286         }
    287     }
    288     return 0;
    289 }
    290 
    291 ALWAYS_INLINE Node* LiveNodeListBase::itemBefore(Node* previous) const
    292 {
    293     Node* current;
    294     if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
    295         current = previousNode(rootNode(), *previous, shouldOnlyIncludeDirectChildren());
    296     else
    297         current = lastNode(rootNode(), shouldOnlyIncludeDirectChildren());
    298 
    299     if (type() == ChildNodeListType)
    300         return current;
    301     return iterateForPreviousNode(current);
    302 }
    303 
    304 template <class NodeListType>
    305 inline Element* firstMatchingElement(const NodeListType* nodeList, ContainerNode& root)
    306 {
    307     Element* element = ElementTraversal::firstWithin(root);
    308     while (element && !isMatchingElement(nodeList, element))
    309         element = ElementTraversal::next(*element, &root);
    310     return element;
    311 }
    312 
    313 template <class NodeListType>
    314 inline Element* nextMatchingElement(const NodeListType* nodeList, Element& current, ContainerNode* root)
    315 {
    316     Element* next = &current;
    317     do {
    318         next = ElementTraversal::next(*next, root);
    319     } while (next && !isMatchingElement(nodeList, next));
    320     return next;
    321 }
    322 
    323 template <class NodeListType>
    324 inline Element* traverseMatchingElementsForwardToOffset(const NodeListType* nodeList, unsigned offset, Element& currentElement, unsigned& currentOffset, ContainerNode* root)
    325 {
    326     ASSERT(currentOffset < offset);
    327     Element* next = &currentElement;
    328     while ((next = nextMatchingElement(nodeList, *next, root))) {
    329         if (++currentOffset == offset)
    330             return next;
    331     }
    332     return 0;
    333 }
    334 
    335 // FIXME: This should be in ChildNodeList
    336 inline Node* LiveNodeListBase::traverseChildNodeListForwardToOffset(unsigned offset, Node* currentNode, unsigned& currentOffset) const
    337 {
    338     ASSERT(type() == ChildNodeListType);
    339     ASSERT(currentOffset < offset);
    340     while ((currentNode = currentNode->nextSibling())) {
    341         if (++currentOffset == offset)
    342             return currentNode;
    343     }
    344     return 0;
    345 }
    346 
    347 // FIXME: This should be in LiveNodeList
    348 inline Element* LiveNodeListBase::traverseLiveNodeListFirstElement(ContainerNode& root) const
    349 {
    350     ASSERT(isNodeList(type()));
    351     ASSERT(type() != ChildNodeListType);
    352     if (type() == HTMLTagNodeListType)
    353         return firstMatchingElement(static_cast<const HTMLTagNodeList*>(this), root);
    354     if (type() == ClassNodeListType)
    355         return firstMatchingElement(static_cast<const ClassNodeList*>(this), root);
    356     return firstMatchingElement(static_cast<const LiveNodeList*>(this), root);
    357 }
    358 
    359 // FIXME: This should be in LiveNodeList
    360 inline Element* LiveNodeListBase::traverseLiveNodeListForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset, ContainerNode* root) const
    361 {
    362     ASSERT(isNodeList(type()));
    363     ASSERT(type() != ChildNodeListType);
    364     if (type() == HTMLTagNodeListType)
    365         return traverseMatchingElementsForwardToOffset(static_cast<const HTMLTagNodeList*>(this), offset, currentElement, currentOffset, root);
    366     if (type() == ClassNodeListType)
    367         return traverseMatchingElementsForwardToOffset(static_cast<const ClassNodeList*>(this), offset, currentElement, currentOffset, root);
    368     return traverseMatchingElementsForwardToOffset(static_cast<const LiveNodeList*>(this), offset, currentElement, currentOffset, root);
    369 }
    370 
    371 bool ALWAYS_INLINE LiveNodeListBase::isLastItemCloserThanLastOrCachedItem(unsigned offset) const
    372 {
    373     ASSERT(isLengthCacheValid());
    374     unsigned distanceFromLastItem = cachedLength() - offset;
    375     if (!isItemCacheValid())
    376         return distanceFromLastItem < offset;
    377 
    378     return cachedItemOffset() < offset && distanceFromLastItem < offset - cachedItemOffset();
    379 }
    380 
    381 bool ALWAYS_INLINE LiveNodeListBase::isFirstItemCloserThanCachedItem(unsigned offset) const
    382 {
    383     ASSERT(isItemCacheValid());
    384     if (cachedItemOffset() < offset)
    385         return false;
    386 
    387     unsigned distanceFromCachedItem = cachedItemOffset() - offset;
    388     return offset < distanceFromCachedItem;
    389 }
    390 
    391 ALWAYS_INLINE void LiveNodeListBase::setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const
    392 {
    393     setItemCache(item, offset);
    394     if (overridesItemAfter()) {
    395         ASSERT_WITH_SECURITY_IMPLICATION(item->isElementNode());
    396         static_cast<const HTMLCollection*>(this)->m_cachedElementsArrayOffset = elementsArrayOffset;
    397     } else
    398         ASSERT(!elementsArrayOffset);
    399 }
    400 
    401 unsigned LiveNodeListBase::length() const
    402 {
    403     if (isLengthCacheValid())
    404         return cachedLength();
    405 
    406     item(UINT_MAX);
    407     ASSERT(isLengthCacheValid());
    408 
    409     return cachedLength();
    410 }
    411 
    412 // FIXME: It is silly that these functions are in HTMLCollection.cpp.
    413 Node* LiveNodeListBase::item(unsigned offset) const
    414 {
    415     if (isItemCacheValid() && cachedItemOffset() == offset)
    416         return cachedItem();
    417 
    418     if (isLengthCacheValid() && cachedLength() <= offset)
    419         return 0;
    420 
    421     ContainerNode* root = rootContainerNode();
    422     if (!root) {
    423         // FIMXE: In someTextNode.childNodes case the root is Text. We shouldn't even make a LiveNodeList for that.
    424         setLengthCache(0);
    425         return 0;
    426     }
    427 
    428     if (isLengthCacheValid() && !overridesItemAfter() && isLastItemCloserThanLastOrCachedItem(offset)) {
    429         Node* lastItem = itemBefore(0);
    430         ASSERT(lastItem);
    431         setItemCache(lastItem, cachedLength() - 1, 0);
    432     } else if (!isItemCacheValid() || isFirstItemCloserThanCachedItem(offset) || (overridesItemAfter() && offset < cachedItemOffset())) {
    433         unsigned offsetInArray = 0;
    434         Node* firstItem;
    435         if (type() == ChildNodeListType)
    436             firstItem = root->firstChild();
    437         else if (isNodeList(type()))
    438             firstItem = traverseLiveNodeListFirstElement(*root);
    439         else
    440             firstItem = static_cast<const HTMLCollection*>(this)->traverseFirstElement(offsetInArray, *root);
    441 
    442         if (!firstItem) {
    443             setLengthCache(0);
    444             return 0;
    445         }
    446         setItemCache(firstItem, 0, offsetInArray);
    447         ASSERT(!cachedItemOffset());
    448     }
    449 
    450     if (cachedItemOffset() == offset)
    451         return cachedItem();
    452 
    453     return itemBeforeOrAfterCachedItem(offset, root);
    454 }
    455 
    456 inline Node* LiveNodeListBase::itemBeforeOrAfterCachedItem(unsigned offset, ContainerNode* root) const
    457 {
    458     unsigned currentOffset = cachedItemOffset();
    459     Node* currentItem = cachedItem();
    460     ASSERT(currentItem);
    461     ASSERT(currentOffset != offset);
    462 
    463     if (offset < cachedItemOffset()) {
    464         ASSERT(!overridesItemAfter());
    465         while ((currentItem = itemBefore(currentItem))) {
    466             ASSERT(currentOffset);
    467             currentOffset--;
    468             if (currentOffset == offset) {
    469                 setItemCache(currentItem, currentOffset, 0);
    470                 return currentItem;
    471             }
    472         }
    473         ASSERT_NOT_REACHED();
    474         return 0;
    475     }
    476 
    477     unsigned offsetInArray = 0;
    478     if (type() == ChildNodeListType)
    479         currentItem = traverseChildNodeListForwardToOffset(offset, currentItem, currentOffset);
    480     else if (isNodeList(type()))
    481         currentItem = traverseLiveNodeListForwardToOffset(offset, toElement(*currentItem), currentOffset, root);
    482     else
    483         currentItem = static_cast<const HTMLCollection*>(this)->traverseForwardToOffset(offset, toElement(*currentItem), currentOffset, offsetInArray, root);
    484 
    485     if (!currentItem) {
    486         // Did not find the item. On plus side, we now know the length.
    487         setLengthCache(currentOffset + 1);
    488         return 0;
    489     }
    490     setItemCache(currentItem, currentOffset, offsetInArray);
    491     return currentItem;
    492 }
    493 
    494 Element* HTMLCollection::virtualItemAfter(unsigned&, Element*) const
    495 {
    496     ASSERT_NOT_REACHED();
    497     return 0;
    498 }
    499 
    500 static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement* element)
    501 {
    502     // The document.all collection returns only certain types of elements by name,
    503     // although it returns any type of element by id.
    504     return element->hasLocalName(appletTag)
    505         || element->hasLocalName(embedTag)
    506         || element->hasLocalName(formTag)
    507         || element->hasLocalName(imgTag)
    508         || element->hasLocalName(inputTag)
    509         || element->hasLocalName(objectTag)
    510         || element->hasLocalName(selectTag);
    511 }
    512 
    513 bool HTMLCollection::checkForNameMatch(Element* element, bool checkName, const AtomicString& name) const
    514 {
    515     if (!element->isHTMLElement())
    516         return false;
    517 
    518     HTMLElement* e = toHTMLElement(element);
    519     if (!checkName)
    520         return e->getIdAttribute() == name;
    521 
    522     if (type() == DocAll && !nameShouldBeVisibleInDocumentAll(e))
    523         return false;
    524 
    525     return e->getNameAttribute() == name && e->getIdAttribute() != name;
    526 }
    527 
    528 inline Element* firstMatchingChildElement(const HTMLCollection* nodeList, ContainerNode& root)
    529 {
    530     Element* element = ElementTraversal::firstWithin(root);
    531     while (element && !isMatchingElement(nodeList, element))
    532         element = ElementTraversal::nextSkippingChildren(*element, &root);
    533     return element;
    534 }
    535 
    536 inline Element* nextMatchingChildElement(const HTMLCollection* nodeList, Element& current, ContainerNode* root)
    537 {
    538     Element* next = &current;
    539     do {
    540         next = ElementTraversal::nextSkippingChildren(*next, root);
    541     } while (next && !isMatchingElement(nodeList, next));
    542     return next;
    543 }
    544 
    545 inline Element* HTMLCollection::traverseFirstElement(unsigned& offsetInArray, ContainerNode& root) const
    546 {
    547     if (overridesItemAfter())
    548         return virtualItemAfter(offsetInArray, 0);
    549     ASSERT(!offsetInArray);
    550     if (shouldOnlyIncludeDirectChildren())
    551         return firstMatchingChildElement(static_cast<const HTMLCollection*>(this), root);
    552     return firstMatchingElement(static_cast<const HTMLCollection*>(this), root);
    553 }
    554 
    555 inline Element* HTMLCollection::traverseNextElement(unsigned& offsetInArray, Element& previous, ContainerNode* root) const
    556 {
    557     if (overridesItemAfter())
    558         return virtualItemAfter(offsetInArray, &previous);
    559     ASSERT(!offsetInArray);
    560     if (shouldOnlyIncludeDirectChildren())
    561         return nextMatchingChildElement(this, previous, root);
    562     return nextMatchingElement(this, previous, root);
    563 }
    564 
    565 inline Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset, unsigned& offsetInArray, ContainerNode* root) const
    566 {
    567     ASSERT(currentOffset < offset);
    568     if (overridesItemAfter()) {
    569         offsetInArray = m_cachedElementsArrayOffset;
    570         Element* next = &currentElement;
    571         while ((next = virtualItemAfter(offsetInArray, next))) {
    572             if (++currentOffset == offset)
    573                 return next;
    574         }
    575         return 0;
    576     }
    577     if (shouldOnlyIncludeDirectChildren()) {
    578         Element* next = &currentElement;
    579         while ((next = nextMatchingChildElement(this, *next, root))) {
    580             if (++currentOffset == offset)
    581                 return next;
    582         }
    583         return 0;
    584     }
    585     return traverseMatchingElementsForwardToOffset(this, offset, currentElement, currentOffset, root);
    586 }
    587 
    588 Node* HTMLCollection::namedItem(const AtomicString& name) const
    589 {
    590     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
    591     // This method first searches for an object with a matching id
    592     // attribute. If a match is not found, the method then searches for an
    593     // object with a matching name attribute, but only on those elements
    594     // that are allowed a name attribute.
    595 
    596     ContainerNode* root = rootContainerNode();
    597     if (!root)
    598         return 0;
    599 
    600     unsigned arrayOffset = 0;
    601     unsigned i = 0;
    602     for (Element* element = traverseFirstElement(arrayOffset, *root); element; element = traverseNextElement(arrayOffset, *element, root)) {
    603         if (checkForNameMatch(element, /* checkName */ false, name)) {
    604             setItemCache(element, i, arrayOffset);
    605             return element;
    606         }
    607         i++;
    608     }
    609 
    610     i = 0;
    611     for (Element* element = traverseFirstElement(arrayOffset, *root); element; element = traverseNextElement(arrayOffset, *element, root)) {
    612         if (checkForNameMatch(element, /* checkName */ true, name)) {
    613             setItemCache(element, i, arrayOffset);
    614             return element;
    615         }
    616         i++;
    617     }
    618 
    619     return 0;
    620 }
    621 
    622 void HTMLCollection::updateNameCache() const
    623 {
    624     if (hasNameCache())
    625         return;
    626 
    627     ContainerNode* root = rootContainerNode();
    628     if (!root)
    629         return;
    630 
    631     unsigned arrayOffset = 0;
    632     for (Element* element = traverseFirstElement(arrayOffset, *root); element; element = traverseNextElement(arrayOffset, *element, root)) {
    633         const AtomicString& idAttrVal = element->getIdAttribute();
    634         if (!idAttrVal.isEmpty())
    635             appendIdCache(idAttrVal, element);
    636         if (!element->isHTMLElement())
    637             continue;
    638         const AtomicString& nameAttrVal = element->getNameAttribute();
    639         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(element))))
    640             appendNameCache(nameAttrVal, element);
    641     }
    642 
    643     setHasNameCache();
    644 }
    645 
    646 bool HTMLCollection::hasNamedItem(const AtomicString& name) const
    647 {
    648     if (name.isEmpty())
    649         return false;
    650 
    651     updateNameCache();
    652 
    653     if (Vector<Element*>* cache = idCache(name)) {
    654         if (!cache->isEmpty())
    655             return true;
    656     }
    657 
    658     if (Vector<Element*>* cache = nameCache(name)) {
    659         if (!cache->isEmpty())
    660             return true;
    661     }
    662 
    663     return false;
    664 }
    665 
    666 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Node> >& result) const
    667 {
    668     ASSERT(result.isEmpty());
    669     if (name.isEmpty())
    670         return;
    671 
    672     updateNameCache();
    673 
    674     Vector<Element*>* idResults = idCache(name);
    675     Vector<Element*>* nameResults = nameCache(name);
    676 
    677     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
    678         result.append(idResults->at(i));
    679 
    680     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
    681         result.append(nameResults->at(i));
    682 }
    683 
    684 void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element)
    685 {
    686     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).iterator->value;
    687     if (!vector)
    688         vector = adoptPtr(new Vector<Element*>);
    689     vector->append(element);
    690 }
    691 
    692 } // namespace WebCore
    693