src/third_party/WebKit/Source/core/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  * 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 "HTMLNames.h"
  28 #include "core/dom/ClassCollection.h"
  29 #include "core/dom/ElementTraversal.h"
  30 #include "core/dom/NodeRareData.h"
  31 #include "core/html/HTMLElement.h"
  32 #include "core/html/HTMLObjectElement.h"
  33 #include "core/html/HTMLOptionElement.h"
  34 #include "wtf/HashSet.h"
  35
  36 namespace WebCore {
  37
  38 using namespace HTMLNames;
  39
  40 static bool shouldTypeOnlyIncludeDirectChildren(CollectionType type)
  41 {
  42     switch (type) {
  43     case ClassCollectionType:
  44     case TagCollectionType:
  45     case HTMLTagCollectionType:
  46     case DocAll:
  47     case DocAnchors:
  48     case DocApplets:
  49     case DocEmbeds:
  50     case DocForms:
  51     case DocImages:
  52     case DocLinks:
  53     case DocScripts:
  54     case DocumentNamedItems:
  55     case MapAreas:
  56     case TableRows:
  57     case SelectOptions:
  58     case SelectedOptions:
  59     case DataListOptions:
  60     case WindowNamedItems:
  61     case FormControls:
  62         return false;
  63     case NodeChildren:
  64     case TRCells:
  65     case TSectionRows:
  66     case TableTBodies:
  67         return true;
  68     case NameNodeListType:
  69     case RadioNodeListType:
  70     case RadioImgNodeListType:
  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 ClassCollectionType:
  94     case TagCollectionType:
  95     case HTMLTagCollectionType:
  96     case NodeChildren:
  97     case TableTBodies:
  98     case TSectionRows:
  99     case TableRows:
 100     case TRCells:
 101     case SelectOptions:
 102     case SelectedOptions:
 103     case DataListOptions:
 104     case MapAreas:
 105         return NodeListIsRootedAtNode;
 106     case NameNodeListType:
 107     case RadioNodeListType:
 108     case RadioImgNodeListType:
 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 TagCollectionType:
 120     case HTMLTagCollectionType:
 121     case DocImages:
 122     case DocEmbeds:
 123     case DocForms:
 124     case DocScripts:
 125     case DocAll:
 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 DocAnchors:
 140         return InvalidateOnNameAttrChange;
 141     case DocLinks:
 142         return InvalidateOnHRefAttrChange;
 143     case WindowNamedItems:
 144         return InvalidateOnIdNameAttrChange;
 145     case DocumentNamedItems:
 146         return InvalidateOnIdNameAttrChange;
 147     case FormControls:
 148         return InvalidateForFormControls;
 149     case ClassCollectionType:
 150         return InvalidateOnClassAttrChange;
 151     case NameNodeListType:
 152     case RadioNodeListType:
 153     case RadioImgNodeListType:
 154     case LabelsNodeListType:
 155         break;
 156     }
 157     ASSERT_NOT_REACHED();
 158     return DoNotInvalidateOnAttributeChanges;
 159 }
 160
 161 HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
 162     : LiveNodeListBase(ownerNode, rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type)
 163     , m_overridesItemAfter(itemAfterOverrideType == OverridesItemAfter)
 164     , m_shouldOnlyIncludeDirectChildren(shouldTypeOnlyIncludeDirectChildren(type))
 165     , m_hasValidIdNameCache(false)
 166 {
 167     ScriptWrappable::init(this);
 168 }
 169
 170 PassRefPtr<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
 171 {
 172     return adoptRef(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
 173 }
 174
 175 HTMLCollection::~HTMLCollection()
 176 {
 177     if (hasValidIdNameCache())
 178         unregisterIdNameCacheFromDocument(document());
 179     // HTMLNameCollection, ClassCollection and TagCollection remove cache by themselves.
 180     if (type() != WindowNamedItems && type() != DocumentNamedItems && type() != ClassCollectionType
 181         && type() != HTMLTagCollectionType && type() != TagCollectionType) {
 182         ownerNode().nodeLists()->removeCache(this, type());
 183     }
 184 }
 185
 186 void HTMLCollection::invalidateCache(Document* oldDocument) const
 187 {
 188     m_collectionIndexCache.invalidate();
 189     invalidateIdNameCacheMaps(oldDocument);
 190 }
 191
 192 template <class NodeListType>
 193 inline bool isMatchingElement(const NodeListType&, const Element&);
 194
 195 template <> inline bool isMatchingElement(const HTMLCollection& htmlCollection, const Element& element)
 196 {
 197     CollectionType type = htmlCollection.type();
 198
 199     // These collections apply to any kind of Elements, not just HTMLElements.
 200     switch (type) {
 201     case DocAll:
 202     case NodeChildren:
 203         return true;
 204     case ClassCollectionType:
 205         return static_cast<const ClassCollection&>(htmlCollection).elementMatches(element);
 206     case TagCollectionType:
 207         return static_cast<const TagCollection&>(htmlCollection).elementMatches(element);
 208     case HTMLTagCollectionType:
 209         return static_cast<const HTMLTagCollection&>(htmlCollection).elementMatches(element);
 210     default:
 211         break;
 212     }
 213
 214     // The following only applies to HTMLElements.
 215     if (!element.isHTMLElement())
 216         return false;
 217
 218     switch (type) {
 219     case DocImages:
 220         return element.hasLocalName(imgTag);
 221     case DocScripts:
 222         return element.hasLocalName(scriptTag);
 223     case DocForms:
 224         return element.hasLocalName(formTag);
 225     case TableTBodies:
 226         return element.hasLocalName(tbodyTag);
 227     case TRCells:
 228         return element.hasLocalName(tdTag) || element.hasLocalName(thTag);
 229     case TSectionRows:
 230         return element.hasLocalName(trTag);
 231     case SelectOptions:
 232         return element.hasLocalName(optionTag);
 233     case SelectedOptions:
 234         return element.hasLocalName(optionTag) && toHTMLOptionElement(element).selected();
 235     case DataListOptions:
 236         if (element.hasLocalName(optionTag)) {
 237             const HTMLOptionElement& option = toHTMLOptionElement(element);
 238             if (!option.isDisabledFormControl() && !option.value().isEmpty())
 239                 return true;
 240         }
 241         return false;
 242     case MapAreas:
 243         return element.hasLocalName(areaTag);
 244     case DocApplets:
 245         return element.hasLocalName(appletTag) || (element.hasLocalName(objectTag) && toHTMLObjectElement(element).containsJavaApplet());
 246     case DocEmbeds:
 247         return element.hasLocalName(embedTag);
 248     case DocLinks:
 249         return (element.hasLocalName(aTag) || element.hasLocalName(areaTag)) && element.fastHasAttribute(hrefAttr);
 250     case DocAnchors:
 251         return element.hasLocalName(aTag) && element.fastHasAttribute(nameAttr);
 252     case ClassCollectionType:
 253     case TagCollectionType:
 254     case HTMLTagCollectionType:
 255     case DocAll:
 256     case NodeChildren:
 257     case FormControls:
 258     case DocumentNamedItems:
 259     case TableRows:
 260     case WindowNamedItems:
 261     case NameNodeListType:
 262     case RadioNodeListType:
 263     case RadioImgNodeListType:
 264     case LabelsNodeListType:
 265         ASSERT_NOT_REACHED();
 266     }
 267     return false;
 268 }
 269
 270 template <> inline bool isMatchingElement(const ClassCollection& collection, const Element& element)
 271 {
 272     return collection.elementMatches(element);
 273 }
 274
 275 template <> inline bool isMatchingElement(const HTMLTagCollection& collection, const Element& element)
 276 {
 277     return collection.elementMatches(element);
 278 }
 279
 280 Element* HTMLCollection::itemBefore(const Element* previous) const
 281 {
 282     return LiveNodeListBase::itemBefore(*this, previous);
 283 }
 284
 285 Element* HTMLCollection::virtualItemAfter(Element*) const
 286 {
 287     ASSERT_NOT_REACHED();
 288     return 0;
 289 }
 290
 291 static inline bool nameShouldBeVisibleInDocumentAll(const HTMLElement& element)
 292 {
 293     // http://www.whatwg.org/specs/web-apps/current-work/multipage/common-dom-interfaces.html#dom-htmlallcollection-nameditem:
 294     // The document.all collection returns only certain types of elements by name,
 295     // although it returns any type of element by id.
 296     return element.hasLocalName(aTag)
 297         || element.hasLocalName(appletTag)
 298         || element.hasLocalName(areaTag)
 299         || element.hasLocalName(embedTag)
 300         || element.hasLocalName(formTag)
 301         || element.hasLocalName(frameTag)
 302         || element.hasLocalName(framesetTag)
 303         || element.hasLocalName(iframeTag)
 304         || element.hasLocalName(imgTag)
 305         || element.hasLocalName(inputTag)
 306         || element.hasLocalName(objectTag)
 307         || element.hasLocalName(selectTag);
 308 }
 309
 310 inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, const ContainerNode& root)
 311 {
 312     Element* element = ElementTraversal::firstChild(root);
 313     while (element && !isMatchingElement(nodeList, *element))
 314         element = ElementTraversal::nextSibling(*element);
 315     return element;
 316 }
 317
 318 inline Element* nextMatchingChildElement(const HTMLCollection& nodeList, Element& current)
 319 {
 320     Element* next = &current;
 321     do {
 322         next = ElementTraversal::nextSibling(*next);
 323     } while (next && !isMatchingElement(nodeList, *next));
 324     return next;
 325 }
 326
 327 Element* HTMLCollection::traverseToFirstElement(const ContainerNode& root) const
 328 {
 329     switch (type()) {
 330     case HTMLTagCollectionType:
 331         return firstMatchingElement(static_cast<const HTMLTagCollection&>(*this), root);
 332     case ClassCollectionType:
 333         return firstMatchingElement(static_cast<const ClassCollection&>(*this), root);
 334     default:
 335         if (overridesItemAfter())
 336             return virtualItemAfter(0);
 337         if (shouldOnlyIncludeDirectChildren())
 338             return firstMatchingChildElement(*this, root);
 339         return firstMatchingElement(*this, root);
 340     }
 341 }
 342
 343 inline Element* HTMLCollection::traverseNextElement(Element& previous, const ContainerNode& root) const
 344 {
 345     if (overridesItemAfter())
 346         return virtualItemAfter(&previous);
 347     if (shouldOnlyIncludeDirectChildren())
 348         return nextMatchingChildElement(*this, previous);
 349     return nextMatchingElement(*this, previous, root);
 350 }
 351
 352 Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset, const ContainerNode& root) const
 353 {
 354     ASSERT(currentOffset < offset);
 355     switch (type()) {
 356     case HTMLTagCollectionType:
 357         return traverseMatchingElementsForwardToOffset(static_cast<const HTMLTagCollection&>(*this), offset, currentElement, currentOffset, root);
 358     case ClassCollectionType:
 359         return traverseMatchingElementsForwardToOffset(static_cast<const ClassCollection&>(*this), offset, currentElement, currentOffset, root);
 360     default:
 361         if (overridesItemAfter()) {
 362             Element* next = &currentElement;
 363             while ((next = virtualItemAfter(next))) {
 364                 if (++currentOffset == offset)
 365                     return next;
 366             }
 367             return 0;
 368         }
 369         if (shouldOnlyIncludeDirectChildren()) {
 370             Element* next = &currentElement;
 371             while ((next = nextMatchingChildElement(*this, *next))) {
 372                 if (++currentOffset == offset)
 373                     return next;
 374             }
 375             return 0;
 376         }
 377         return traverseMatchingElementsForwardToOffset(*this, offset, currentElement, currentOffset, root);
 378     }
 379 }
 380
 381 Element* HTMLCollection::namedItem(const AtomicString& name) const
 382 {
 383     // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
 384     // This method first searches for an object with a matching id
 385     // attribute. If a match is not found, the method then searches for an
 386     // object with a matching name attribute, but only on those elements
 387     // that are allowed a name attribute.
 388     updateIdNameCache();
 389
 390     Vector<Element*>* idResults = idCache(name);
 391     if (idResults && !idResults->isEmpty())
 392         return idResults->first();
 393
 394     Vector<Element*>* nameResults = nameCache(name);
 395     if (nameResults && !nameResults->isEmpty())
 396         return nameResults->first();
 397
 398     return 0;
 399 }
 400
 401 bool HTMLCollection::namedPropertyQuery(const AtomicString& name, ExceptionState&)
 402 {
 403     return namedItem(name);
 404 }
 405
 406 void HTMLCollection::supportedPropertyNames(Vector<String>& names)
 407 {
 408     // As per the specification (http://dom.spec.whatwg.org/#htmlcollection):
 409     // The supported property names are the values from the list returned by these steps:
 410     // 1. Let result be an empty list.
 411     // 2. For each element represented by the collection, in tree order, run these substeps:
 412     //   1. If element has an ID which is neither the empty string nor is in result, append element's ID to result.
 413     //   2. If element is in the HTML namespace and has a name attribute whose value is neither the empty string
 414     //      nor is in result, append element's name attribute value to result.
 415     // 3. Return result.
 416     HashSet<AtomicString> existingNames;
 417     ContainerNode& root = rootNode();
 418     for (Element* element = traverseToFirstElement(root); element; element = traverseNextElement(*element, root)) {
 419         const AtomicString& idAttribute = element->getIdAttribute();
 420         if (!idAttribute.isEmpty()) {
 421             HashSet<AtomicString>::AddResult addResult = existingNames.add(idAttribute);
 422             if (addResult.isNewEntry)
 423                 names.append(idAttribute);
 424         }
 425         if (!element->isHTMLElement())
 426             continue;
 427         const AtomicString& nameAttribute = element->getNameAttribute();
 428         if (!nameAttribute.isEmpty() && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element)))) {
 429             HashSet<AtomicString>::AddResult addResult = existingNames.add(nameAttribute);
 430             if (addResult.isNewEntry)
 431                 names.append(nameAttribute);
 432         }
 433     }
 434 }
 435
 436 void HTMLCollection::namedPropertyEnumerator(Vector<String>& names, ExceptionState&)
 437 {
 438     supportedPropertyNames(names);
 439 }
 440
 441 void HTMLCollection::updateIdNameCache() const
 442 {
 443     if (hasValidIdNameCache())
 444         return;
 445
 446     ContainerNode& root = rootNode();
 447     for (Element* element = traverseToFirstElement(root); element; element = traverseNextElement(*element, root)) {
 448         const AtomicString& idAttrVal = element->getIdAttribute();
 449         if (!idAttrVal.isEmpty())
 450             appendIdCache(idAttrVal, element);
 451         if (!element->isHTMLElement())
 452             continue;
 453         const AtomicString& nameAttrVal = element->getNameAttribute();
 454         if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element))))
 455             appendNameCache(nameAttrVal, element);
 456     }
 457
 458     setHasValidIdNameCache();
 459 }
 460
 461 void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Element> >& result) const
 462 {
 463     ASSERT(result.isEmpty());
 464     if (name.isEmpty())
 465         return;
 466
 467     updateIdNameCache();
 468
 469     Vector<Element*>* idResults = idCache(name);
 470     Vector<Element*>* nameResults = nameCache(name);
 471
 472     for (unsigned i = 0; idResults && i < idResults->size(); ++i)
 473         result.append(idResults->at(i));
 474
 475     for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
 476         result.append(nameResults->at(i));
 477 }
 478
 479 void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element)
 480 {
 481     OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).storedValue->value;
 482     if (!vector)
 483         vector = adoptPtr(new Vector<Element*>);
 484     vector->append(element);
 485 }
 486
 487 } // namespace WebCore