/*
* Copyright (C) 1999 Lars Knoll (knoll@kde.org)
* (C) 1999 Antti Koivisto (koivisto@kde.org)
- * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
+ * Copyright (C) 2003-2008, 2011, 2012, 2014 Apple Inc. All rights reserved.
* Copyright (C) 2014 Samsung Electronics. All rights reserved.
*
* This library is free software; you can redistribute it and/or
#include "config.h"
#include "core/html/HTMLCollection.h"
-#include "HTMLNames.h"
+#include "core/HTMLNames.h"
#include "core/dom/ClassCollection.h"
#include "core/dom/ElementTraversal.h"
-#include "core/dom/NodeList.h"
#include "core/dom/NodeRareData.h"
-#include "core/dom/NodeTraversal.h"
+#include "core/html/DocumentNameCollection.h"
+#include "core/html/HTMLDataListOptionsCollection.h"
#include "core/html/HTMLElement.h"
#include "core/html/HTMLObjectElement.h"
#include "core/html/HTMLOptionElement.h"
+#include "core/html/HTMLOptionsCollection.h"
+#include "core/html/HTMLTagCollection.h"
+#include "core/html/WindowNameCollection.h"
#include "wtf/HashSet.h"
-namespace WebCore {
+namespace blink {
using namespace HTMLNames;
return DoNotInvalidateOnAttributeChanges;
}
-HTMLCollection::HTMLCollection(ContainerNode* ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
+HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ItemAfterOverrideType itemAfterOverrideType)
: LiveNodeListBase(ownerNode, rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type)
, m_overridesItemAfter(itemAfterOverrideType == OverridesItemAfter)
, m_shouldOnlyIncludeDirectChildren(shouldTypeOnlyIncludeDirectChildren(type))
- , m_hasValidIdNameCache(false)
{
- ScriptWrappable::init(this);
}
-PassRefPtr<HTMLCollection> HTMLCollection::create(ContainerNode* base, CollectionType type)
+PassRefPtrWillBeRawPtr<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
{
- return adoptRef(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
+ return adoptRefWillBeNoop(new HTMLCollection(base, type, DoesNotOverrideItemAfter));
}
HTMLCollection::~HTMLCollection()
{
+#if !ENABLE(OILPAN)
if (hasValidIdNameCache())
unregisterIdNameCacheFromDocument(document());
- // HTMLNameCollection, ClassCollection and TagCollection remove cache by themselves.
- if (type() != WindowNamedItems && type() != DocumentNamedItems && type() != ClassCollectionType
- && type() != HTMLTagCollectionType && type() != TagCollectionType) {
- ownerNode()->nodeLists()->removeCache(this, type());
- }
+ // Named HTMLCollection types remove cache by themselves.
+ if (isUnnamedHTMLCollectionType(type()))
+ ownerNode().nodeLists()->removeCache(this, type());
+#endif
}
void HTMLCollection::invalidateCache(Document* oldDocument) const
{
- m_collectionIndexCache.invalidate();
+ m_collectionItemsCache.invalidate();
invalidateIdNameCacheMaps(oldDocument);
}
-template <class NodeListType>
-inline bool isMatchingElement(const NodeListType&, const Element&);
-
-template <> inline bool isMatchingElement(const HTMLCollection& htmlCollection, const Element& element)
+unsigned HTMLCollection::length() const
{
- CollectionType type = htmlCollection.type();
-
- // These collections apply to any kind of Elements, not just HTMLElements.
- switch (type) {
- case DocAll:
- case NodeChildren:
- return true;
- case ClassCollectionType:
- return static_cast<const ClassCollection&>(htmlCollection).elementMatches(element);
- case TagCollectionType:
- return static_cast<const TagCollection&>(htmlCollection).elementMatches(element);
- case HTMLTagCollectionType:
- return static_cast<const HTMLTagCollection&>(htmlCollection).elementMatches(element);
- default:
- break;
- }
+ return m_collectionItemsCache.nodeCount(*this);
+}
- // The following only applies to HTMLElements.
- if (!element.isHTMLElement())
- return false;
+Element* HTMLCollection::item(unsigned offset) const
+{
+ return m_collectionItemsCache.nodeAt(*this, offset);
+}
- switch (type) {
+static inline bool isMatchingHTMLElement(const HTMLCollection& htmlCollection, const HTMLElement& element)
+{
+ switch (htmlCollection.type()) {
case DocImages:
- return element.hasLocalName(imgTag);
+ return element.hasTagName(imgTag);
case DocScripts:
- return element.hasLocalName(scriptTag);
+ return element.hasTagName(scriptTag);
case DocForms:
- return element.hasLocalName(formTag);
+ return element.hasTagName(formTag);
+ case DocumentNamedItems:
+ return toDocumentNameCollection(htmlCollection).elementMatches(element);
case TableTBodies:
- return element.hasLocalName(tbodyTag);
+ return element.hasTagName(tbodyTag);
case TRCells:
- return element.hasLocalName(tdTag) || element.hasLocalName(thTag);
+ return element.hasTagName(tdTag) || element.hasTagName(thTag);
case TSectionRows:
- return element.hasLocalName(trTag);
+ return element.hasTagName(trTag);
case SelectOptions:
- return element.hasLocalName(optionTag);
+ return toHTMLOptionsCollection(htmlCollection).elementMatches(element);
case SelectedOptions:
- return element.hasLocalName(optionTag) && toHTMLOptionElement(element).selected();
+ return isHTMLOptionElement(element) && toHTMLOptionElement(element).selected();
case DataListOptions:
- if (element.hasLocalName(optionTag)) {
- const HTMLOptionElement& option = toHTMLOptionElement(element);
- if (!option.isDisabledFormControl() && !option.value().isEmpty())
- return true;
- }
- return false;
+ return toHTMLDataListOptionsCollection(htmlCollection).elementMatches(element);
case MapAreas:
- return element.hasLocalName(areaTag);
+ return element.hasTagName(areaTag);
case DocApplets:
- return element.hasLocalName(appletTag) || (element.hasLocalName(objectTag) && toHTMLObjectElement(element).containsJavaApplet());
+ return element.hasTagName(appletTag) || (isHTMLObjectElement(element) && toHTMLObjectElement(element).containsJavaApplet());
case DocEmbeds:
- return element.hasLocalName(embedTag);
+ return element.hasTagName(embedTag);
case DocLinks:
- return (element.hasLocalName(aTag) || element.hasLocalName(areaTag)) && element.fastHasAttribute(hrefAttr);
+ return (element.hasTagName(aTag) || element.hasTagName(areaTag)) && element.fastHasAttribute(hrefAttr);
case DocAnchors:
- return element.hasLocalName(aTag) && element.fastHasAttribute(nameAttr);
+ return element.hasTagName(aTag) && element.fastHasAttribute(nameAttr);
case ClassCollectionType:
case TagCollectionType:
case HTMLTagCollectionType:
case DocAll:
case NodeChildren:
case FormControls:
- case DocumentNamedItems:
case TableRows:
case WindowNamedItems:
case NameNodeListType:
return false;
}
-template <> inline bool isMatchingElement(const ClassCollection& collection, const Element& element)
+inline bool HTMLCollection::elementMatches(const Element& element) const
{
- return collection.elementMatches(element);
-}
-
-template <> inline bool isMatchingElement(const HTMLTagCollection& collection, const Element& element)
-{
- return collection.elementMatches(element);
-}
-
-template <> inline bool isMatchingElement(const LiveNodeList& nodeList, const Element& element)
-{
- return nodeList.nodeMatches(element);
-}
-
-static Node* previousNode(const ContainerNode& base, const Node& previous, bool onlyIncludeDirectChildren)
-{
- return onlyIncludeDirectChildren ? previous.previousSibling() : NodeTraversal::previous(previous, &base);
-}
-
-static inline Node* lastDescendant(const ContainerNode& node)
-{
- Node* descendant = node.lastChild();
- for (Node* current = descendant; current; current = current->lastChild())
- descendant = current;
- return descendant;
-}
-
-static Node* lastNode(const ContainerNode& rootNode, bool onlyIncludeDirectChildren)
-{
- return onlyIncludeDirectChildren ? rootNode.lastChild() : lastDescendant(rootNode);
-}
-
-template <typename Collection>
-ALWAYS_INLINE Element* LiveNodeListBase::iterateForPreviousNode(const Collection& collection, Node* current)
-{
- bool onlyIncludeDirectChildren = collection.shouldOnlyIncludeDirectChildren();
- ContainerNode& rootNode = collection.rootNode();
- for (; current; current = previousNode(rootNode, *current, onlyIncludeDirectChildren)) {
- if (current->isElementNode() && isMatchingElement(collection, toElement(*current)))
- return toElement(current);
+ // These collections apply to any kind of Elements, not just HTMLElements.
+ switch (type()) {
+ case DocAll:
+ case NodeChildren:
+ return true;
+ case ClassCollectionType:
+ return toClassCollection(*this).elementMatches(element);
+ case TagCollectionType:
+ return toTagCollection(*this).elementMatches(element);
+ case HTMLTagCollectionType:
+ return toHTMLTagCollection(*this).elementMatches(element);
+ case WindowNamedItems:
+ return toWindowNameCollection(*this).elementMatches(element);
+ default:
+ break;
}
- return 0;
-}
-
-template <typename Collection>
-Element* LiveNodeListBase::itemBefore(const Collection& collection, const Element* previous)
-{
- Node* current;
- if (LIKELY(!!previous)) // Without this LIKELY, length() and item() can be 10% slower.
- current = previousNode(collection.rootNode(), *previous, collection.shouldOnlyIncludeDirectChildren());
- else
- current = lastNode(collection.rootNode(), collection.shouldOnlyIncludeDirectChildren());
-
- return iterateForPreviousNode(collection, current);
-}
-
-Element* LiveNodeList::itemBefore(const Element* previous) const
-{
- return LiveNodeListBase::itemBefore(*this, previous);
-}
-Element* HTMLCollection::itemBefore(const Element* previous) const
-{
- return LiveNodeListBase::itemBefore(*this, previous);
+ // The following only applies to HTMLElements.
+ return element.isHTMLElement() && isMatchingHTMLElement(*this, toHTMLElement(element));
}
-template <class NodeListType>
-inline Element* firstMatchingElement(const NodeListType& nodeList, const ContainerNode& root)
-{
- Element* element = ElementTraversal::firstWithin(root);
- while (element && !isMatchingElement(nodeList, *element))
- element = ElementTraversal::next(*element, &root);
- return element;
-}
+namespace {
-template <class NodeListType>
-inline Element* nextMatchingElement(const NodeListType& nodeList, Element& current, const ContainerNode& root)
-{
- Element* next = ¤t;
- do {
- next = ElementTraversal::next(*next, &root);
- } while (next && !isMatchingElement(nodeList, *next));
- return next;
-}
+template <class HTMLCollectionType>
+class IsMatch {
+public:
+ IsMatch(const HTMLCollectionType& list)
+ : m_list(list)
+ { }
-template <class NodeListType>
-inline Element* traverseMatchingElementsForwardToOffset(const NodeListType& nodeList, unsigned offset, Element& currentElement, unsigned& currentOffset, const ContainerNode& root)
-{
- ASSERT(currentOffset < offset);
- Element* next = ¤tElement;
- while ((next = nextMatchingElement(nodeList, *next, root))) {
- if (++currentOffset == offset)
- return next;
+ bool operator() (const Element& element) const
+ {
+ return m_list.elementMatches(element);
}
- return 0;
-}
-// FIXME: This should be in LiveNodeList.cpp but it needs to stay here until firstMatchingElement()
-// and others are moved to a separate header.
-Element* LiveNodeList::traverseToFirstElement(const ContainerNode& root) const
-{
- return firstMatchingElement(*this, root);
-}
+private:
+ const HTMLCollectionType& m_list;
+};
-// FIXME: This should be in LiveNodeList.cpp but it needs to stay here until traverseMatchingElementsForwardToOffset()
-// and others are moved to a separate header.
-Element* LiveNodeList::traverseForwardToOffset(unsigned offset, Element& currentNode, unsigned& currentOffset, const ContainerNode& root) const
-{
- return traverseMatchingElementsForwardToOffset(*this, offset, currentNode, currentOffset, root);
-}
+} // namespace
+
+template <class HTMLCollectionType>
+static inline IsMatch<HTMLCollectionType> makeIsMatch(const HTMLCollectionType& list) { return IsMatch<HTMLCollectionType>(list); }
Element* HTMLCollection::virtualItemAfter(Element*) const
{
// http://www.whatwg.org/specs/web-apps/current-work/multipage/common-dom-interfaces.html#dom-htmlallcollection-nameditem:
// The document.all collection returns only certain types of elements by name,
// although it returns any type of element by id.
- return element.hasLocalName(aTag)
- || element.hasLocalName(appletTag)
- || element.hasLocalName(areaTag)
- || element.hasLocalName(embedTag)
- || element.hasLocalName(formTag)
- || element.hasLocalName(frameTag)
- || element.hasLocalName(framesetTag)
- || element.hasLocalName(iframeTag)
- || element.hasLocalName(imgTag)
- || element.hasLocalName(inputTag)
- || element.hasLocalName(objectTag)
- || element.hasLocalName(selectTag);
-}
-
-inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, const ContainerNode& root)
-{
- Element* element = ElementTraversal::firstWithin(root);
- while (element && !isMatchingElement(nodeList, *element))
- element = ElementTraversal::nextSkippingChildren(*element, &root);
- return element;
-}
-
-inline Element* nextMatchingChildElement(const HTMLCollection& nodeList, Element& current, const ContainerNode& root)
-{
- Element* next = ¤t;
- do {
- next = ElementTraversal::nextSkippingChildren(*next, &root);
- } while (next && !isMatchingElement(nodeList, *next));
- return next;
-}
-
-Element* HTMLCollection::traverseToFirstElement(const ContainerNode& root) const
+ return element.hasTagName(aTag)
+ || element.hasTagName(appletTag)
+ || element.hasTagName(areaTag)
+ || element.hasTagName(embedTag)
+ || element.hasTagName(formTag)
+ || element.hasTagName(frameTag)
+ || element.hasTagName(framesetTag)
+ || element.hasTagName(iframeTag)
+ || element.hasTagName(imgTag)
+ || element.hasTagName(inputTag)
+ || element.hasTagName(objectTag)
+ || element.hasTagName(selectTag);
+}
+
+Element* HTMLCollection::traverseToFirst() const
{
switch (type()) {
case HTMLTagCollectionType:
- return firstMatchingElement(static_cast<const HTMLTagCollection&>(*this), root);
+ return ElementTraversal::firstWithin(rootNode(), makeIsMatch(toHTMLTagCollection(*this)));
case ClassCollectionType:
- return firstMatchingElement(static_cast<const ClassCollection&>(*this), root);
+ return ElementTraversal::firstWithin(rootNode(), makeIsMatch(toClassCollection(*this)));
default:
if (overridesItemAfter())
return virtualItemAfter(0);
if (shouldOnlyIncludeDirectChildren())
- return firstMatchingChildElement(*this, root);
- return firstMatchingElement(*this, root);
+ return ElementTraversal::firstChild(rootNode(), makeIsMatch(*this));
+ return ElementTraversal::firstWithin(rootNode(), makeIsMatch(*this));
}
}
-inline Element* HTMLCollection::traverseNextElement(Element& previous, const ContainerNode& root) const
+Element* HTMLCollection::traverseToLast() const
{
- if (overridesItemAfter())
- return virtualItemAfter(&previous);
+ ASSERT(canTraverseBackward());
if (shouldOnlyIncludeDirectChildren())
- return nextMatchingChildElement(*this, previous, root);
- return nextMatchingElement(*this, previous, root);
+ return ElementTraversal::lastChild(rootNode(), makeIsMatch(*this));
+ return ElementTraversal::lastWithin(rootNode(), makeIsMatch(*this));
}
-Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset, const ContainerNode& root) const
+Element* HTMLCollection::traverseForwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset) const
{
ASSERT(currentOffset < offset);
switch (type()) {
case HTMLTagCollectionType:
- return traverseMatchingElementsForwardToOffset(static_cast<const HTMLTagCollection&>(*this), offset, currentElement, currentOffset, root);
+ return traverseMatchingElementsForwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(toHTMLTagCollection(*this)));
case ClassCollectionType:
- return traverseMatchingElementsForwardToOffset(static_cast<const ClassCollection&>(*this), offset, currentElement, currentOffset, root);
+ return traverseMatchingElementsForwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(toClassCollection(*this)));
default:
if (overridesItemAfter()) {
- Element* next = ¤tElement;
- while ((next = virtualItemAfter(next))) {
+ for (Element* next = virtualItemAfter(¤tElement); next; next = virtualItemAfter(next)) {
if (++currentOffset == offset)
return next;
}
return 0;
}
if (shouldOnlyIncludeDirectChildren()) {
- Element* next = ¤tElement;
- while ((next = nextMatchingChildElement(*this, *next, root))) {
+ IsMatch<HTMLCollection> isMatch(*this);
+ for (Element* next = ElementTraversal::nextSibling(currentElement, isMatch); next; next = ElementTraversal::nextSibling(*next, isMatch)) {
if (++currentOffset == offset)
return next;
}
return 0;
}
- return traverseMatchingElementsForwardToOffset(*this, offset, currentElement, currentOffset, root);
+ return traverseMatchingElementsForwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(*this));
+ }
+}
+
+Element* HTMLCollection::traverseBackwardToOffset(unsigned offset, Element& currentElement, unsigned& currentOffset) const
+{
+ ASSERT(currentOffset > offset);
+ ASSERT(canTraverseBackward());
+ if (shouldOnlyIncludeDirectChildren()) {
+ IsMatch<HTMLCollection> isMatch(*this);
+ for (Element* previous = ElementTraversal::previousSibling(currentElement, isMatch); previous; previous = ElementTraversal::previousSibling(*previous, isMatch)) {
+ if (--currentOffset == offset)
+ return previous;
+ }
+ return 0;
}
+ return traverseMatchingElementsBackwardToOffset(currentElement, &rootNode(), offset, currentOffset, makeIsMatch(*this));
}
Element* HTMLCollection::namedItem(const AtomicString& name) const
// that are allowed a name attribute.
updateIdNameCache();
- Vector<Element*>* idResults = idCache(name);
+ const NamedItemCache& cache = namedItemCache();
+ WillBeHeapVector<RawPtrWillBeMember<Element> >* idResults = cache.getElementsById(name);
if (idResults && !idResults->isEmpty())
return idResults->first();
- Vector<Element*>* nameResults = nameCache(name);
+ WillBeHeapVector<RawPtrWillBeMember<Element> >* nameResults = cache.getElementsByName(name);
if (nameResults && !nameResults->isEmpty())
return nameResults->first();
// nor is in result, append element's name attribute value to result.
// 3. Return result.
HashSet<AtomicString> existingNames;
- ContainerNode& root = rootNode();
- for (Element* element = traverseToFirstElement(root); element; element = traverseNextElement(*element, root)) {
+ unsigned length = this->length();
+ for (unsigned i = 0; i < length; ++i) {
+ Element* element = item(i);
const AtomicString& idAttribute = element->getIdAttribute();
if (!idAttribute.isEmpty()) {
HashSet<AtomicString>::AddResult addResult = existingNames.add(idAttribute);
if (hasValidIdNameCache())
return;
- ContainerNode& root = rootNode();
- for (Element* element = traverseToFirstElement(root); element; element = traverseNextElement(*element, root)) {
+ OwnPtrWillBeRawPtr<NamedItemCache> cache = NamedItemCache::create();
+ unsigned length = this->length();
+ for (unsigned i = 0; i < length; ++i) {
+ Element* element = item(i);
const AtomicString& idAttrVal = element->getIdAttribute();
if (!idAttrVal.isEmpty())
- appendIdCache(idAttrVal, element);
+ cache->addElementWithId(idAttrVal, element);
if (!element->isHTMLElement())
continue;
const AtomicString& nameAttrVal = element->getNameAttribute();
if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element))))
- appendNameCache(nameAttrVal, element);
+ cache->addElementWithName(nameAttrVal, element);
}
-
- setHasValidIdNameCache();
+ // Set the named item cache last as traversing the tree may cause cache invalidation.
+ setNamedItemCache(cache.release());
}
-void HTMLCollection::namedItems(const AtomicString& name, Vector<RefPtr<Element> >& result) const
+void HTMLCollection::namedItems(const AtomicString& name, WillBeHeapVector<RefPtrWillBeMember<Element> >& result) const
{
ASSERT(result.isEmpty());
if (name.isEmpty())
updateIdNameCache();
- Vector<Element*>* idResults = idCache(name);
- Vector<Element*>* nameResults = nameCache(name);
-
- for (unsigned i = 0; idResults && i < idResults->size(); ++i)
- result.append(idResults->at(i));
+ const NamedItemCache& cache = namedItemCache();
+ if (WillBeHeapVector<RawPtrWillBeMember<Element> >* idResults = cache.getElementsById(name)) {
+ for (unsigned i = 0; i < idResults->size(); ++i)
+ result.append(idResults->at(i));
+ }
+ if (WillBeHeapVector<RawPtrWillBeMember<Element> >* nameResults = cache.getElementsByName(name)) {
+ for (unsigned i = 0; i < nameResults->size(); ++i)
+ result.append(nameResults->at(i));
+ }
+}
- for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
- result.append(nameResults->at(i));
+HTMLCollection::NamedItemCache::NamedItemCache()
+{
}
-void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element)
+void HTMLCollection::trace(Visitor* visitor)
{
- OwnPtr<Vector<Element*> >& vector = map.add(key.impl(), nullptr).storedValue->value;
- if (!vector)
- vector = adoptPtr(new Vector<Element*>);
- vector->append(element);
+ visitor->trace(m_namedItemCache);
+ visitor->trace(m_collectionItemsCache);
+ LiveNodeListBase::trace(visitor);
}
-} // namespace WebCore
+} // namespace blink