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