webkitgtk-2.4.11webkitgtk-2.4.11

1 files changed, 337 insertions, 87 deletions

diff --git a/Source/WebCore/html/HTMLCollection.cpp b/Source/WebCore/html/HTMLCollection.cpp
index 6a2f15f6d..58a9eeca2 100644
--- a/Source/WebCore/html/HTMLCollection.cpp
+++ b/Source/WebCore/html/HTMLCollection.cpp
@@ -23,15 +23,49 @@
 #include "config.h"
 #include "HTMLCollection.h"
 
-#include "CachedHTMLCollection.h"
+#include "ElementTraversal.h"
+#include "HTMLDocument.h"
+#include "HTMLNameCollection.h"
 #include "HTMLNames.h"
+#include "HTMLObjectElement.h"
+#include "HTMLOptionElement.h"
 #include "NodeRareData.h"
 
 namespace WebCore {
 
 using namespace HTMLNames;
 
-inline auto HTMLCollection::rootTypeFromCollectionType(CollectionType type) -> RootType
+static bool shouldOnlyIncludeDirectChildren(CollectionType type)
+{
+    switch (type) {
+    case DocAll:
+    case DocAnchors:
+    case DocApplets:
+    case DocEmbeds:
+    case DocForms:
+    case DocImages:
+    case DocLinks:
+    case DocScripts:
+    case DocumentNamedItems:
+    case MapAreas:
+    case TableRows:
+    case SelectOptions:
+    case SelectedOptions:
+    case DataListOptions:
+    case WindowNamedItems:
+    case FormControls:
+        return false;
+    case NodeChildren:
+    case TRCells:
+    case TSectionRows:
+    case TableTBodies:
+        return true;
+    }
+    ASSERT_NOT_REACHED();
+    return false;
+}
+
+static NodeListRootType rootTypeFromCollectionType(CollectionType type)
 {
     switch (type) {
     case DocImages:
@@ -45,10 +79,7 @@ inline auto HTMLCollection::rootTypeFromCollectionType(CollectionType type) -> R
     case WindowNamedItems:
     case DocumentNamedItems:
     case FormControls:
-        return HTMLCollection::IsRootedAtDocument;
-    case ByClass:
-    case ByTag:
-    case ByHTMLTag:
+        return NodeListIsRootedAtDocument;
     case NodeChildren:
     case TableTBodies:
     case TSectionRows:
@@ -58,17 +89,15 @@ inline auto HTMLCollection::rootTypeFromCollectionType(CollectionType type) -> R
     case SelectedOptions:
     case DataListOptions:
     case MapAreas:
-        return HTMLCollection::IsRootedAtNode;
+        return NodeListIsRootedAtNode;
     }
     ASSERT_NOT_REACHED();
-    return HTMLCollection::IsRootedAtNode;
+    return NodeListIsRootedAtNode;
 }
 
 static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(CollectionType type)
 {
     switch (type) {
-    case ByTag:
-    case ByHTMLTag:
     case DocImages:
     case DocEmbeds:
     case DocForms:
@@ -87,8 +116,6 @@ static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(Col
     case DataListOptions:
         // FIXME: We can do better some day.
         return InvalidateOnAnyAttrChange;
-    case ByClass:
-        return InvalidateOnClassAttrChange;
     case DocAnchors:
         return InvalidateOnNameAttrChange;
     case DocLinks:
@@ -104,136 +131,359 @@ static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(Col
     return DoNotInvalidateOnAttributeChanges;
 }
 
-HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type)
+HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType)
     : m_ownerNode(ownerNode)
-    , m_collectionType(type)
-    , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
     , m_rootType(rootTypeFromCollectionType(type))
+    , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type))
+    , m_shouldOnlyIncludeDirectChildren(shouldOnlyIncludeDirectChildren(type))
+    , m_isNameCacheValid(false)
+    , m_collectionType(type)
+    , m_usesCustomForwardOnlyTraversal(traversalType == CustomForwardOnlyTraversal)
+    , m_isItemRefElementsCacheValid(false)
 {
     ASSERT(m_rootType == static_cast<unsigned>(rootTypeFromCollectionType(type)));
     ASSERT(m_invalidationType == static_cast<unsigned>(invalidationTypeExcludingIdAndNameAttributes(type)));
     ASSERT(m_collectionType == static_cast<unsigned>(type));
+
+    document().registerCollection(*this);
+}
+
+PassRefPtr<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type)
+{
+    return adoptRef(new HTMLCollection(base, type));
 }
 
 HTMLCollection::~HTMLCollection()
 {
-    if (hasNamedElementCache())
-        document().collectionWillClearIdNameMap(*this);
+    document().unregisterCollection(*this);
+    // HTMLNameCollection removes cache by itself.
+    if (type() != WindowNamedItems && type() != DocumentNamedItems)
+        ownerNode().nodeLists()->removeCachedCollection(this);
+}
 
-    // HTMLNameCollection & ClassCollection remove cache by themselves.
-    // FIXME: We need a cleaner way to handle this.
-    switch (type()) {
-    case ByClass:
-    case ByTag:
-    case ByHTMLTag:
-    case WindowNamedItems:
+ContainerNode& HTMLCollection::rootNode() const
+{
+    if (isRootedAtDocument() && ownerNode().inDocument())
+        return ownerNode().document();
+
+    return ownerNode();
+}
+
+inline bool isMatchingElement(const HTMLCollection& htmlCollection, Element& element)
+{
+    CollectionType type = htmlCollection.type();
+    if (!element.isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems))
+        return false;
+
+    switch (type) {
+    case DocImages:
+        return element.hasLocalName(imgTag);
+    case DocScripts:
+        return element.hasLocalName(scriptTag);
+    case DocForms:
+        return element.hasLocalName(formTag);
+    case TableTBodies:
+        return element.hasLocalName(tbodyTag);
+    case TRCells:
+        return element.hasLocalName(tdTag) || element.hasLocalName(thTag);
+    case TSectionRows:
+        return element.hasLocalName(trTag);
+    case SelectOptions:
+        return element.hasLocalName(optionTag);
+    case SelectedOptions:
+        return element.hasLocalName(optionTag) && toHTMLOptionElement(element).selected();
+    case DataListOptions:
+        if (element.hasLocalName(optionTag)) {
+            HTMLOptionElement& option = toHTMLOptionElement(element);
+            if (!option.isDisabledFormControl() && !option.value().isEmpty())
+                return true;
+        }
+        return false;
+    case MapAreas:
+        return element.hasLocalName(areaTag);
+    case DocApplets:
+        return element.hasLocalName(appletTag) || (element.hasLocalName(objectTag) && toHTMLObjectElement(element).containsJavaApplet());
+    case DocEmbeds:
+        return element.hasLocalName(embedTag);
+    case DocLinks:
+        return (element.hasLocalName(aTag) || element.hasLocalName(areaTag)) && element.fastHasAttribute(hrefAttr);
+    case DocAnchors:
+        return element.hasLocalName(aTag) && element.fastHasAttribute(nameAttr);
+    case DocAll:
+    case NodeChildren:
+        return true;
     case DocumentNamedItems:
+        return static_cast<const DocumentNameCollection&>(htmlCollection).nodeMatches(&element);
+    case WindowNamedItems:
+        return static_cast<const WindowNameCollection&>(htmlCollection).nodeMatches(&element);
+    case FormControls:
+    case TableRows:
         break;
-    default:
-        ownerNode().nodeLists()->removeCachedCollection(this);
     }
+    ASSERT_NOT_REACHED();
+    return false;
+}
+
+static Element* previousElement(ContainerNode& base, Element* previous, bool onlyIncludeDirectChildren)
+{
+    return onlyIncludeDirectChildren ? ElementTraversal::previousSibling(previous) : ElementTraversal::previous(previous, &base);
+}
+
+ALWAYS_INLINE Element* HTMLCollection::iterateForPreviousElement(Element* current) const
+{
+    bool onlyIncludeDirectChildren = m_shouldOnlyIncludeDirectChildren;
+    ContainerNode& rootNode = this->rootNode();
+    for (; current; current = previousElement(rootNode, current, onlyIncludeDirectChildren)) {
+        if (isMatchingElement(*this, *current))
+            return current;
+    }
+    return nullptr;
+}
+
+inline Element* firstMatchingElement(const HTMLCollection& collection, ContainerNode& root)
+{
+    Element* element = ElementTraversal::firstWithin(&root);
+    while (element && !isMatchingElement(collection, *element))
+        element = ElementTraversal::next(element, &root);
+    return element;
+}
+
+inline Element* nextMatchingElement(const HTMLCollection& collection, Element* current, ContainerNode& root)
+{
+    do {
+        current = ElementTraversal::next(current, &root);
+    } while (current && !isMatchingElement(collection, *current));
+    return current;
+}
+
+unsigned HTMLCollection::length() const
+{
+    return m_indexCache.nodeCount(*this);
+}
+
+Node* HTMLCollection::item(unsigned offset) const
+{
+    return m_indexCache.nodeAt(*this, offset);
+}
+
+static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement& element)
+{
+    // The document.all collection returns only certain types of elements by name,
+    // although it returns any type of element by id.
+    return element.hasLocalName(appletTag)
+        || element.hasLocalName(embedTag)
+        || element.hasLocalName(formTag)
+        || element.hasLocalName(imgTag)
+        || element.hasLocalName(inputTag)
+        || element.hasLocalName(objectTag)
+        || element.hasLocalName(selectTag);
+}
+
+inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, ContainerNode& root)
+{
+    Element* element = ElementTraversal::firstWithin(&root);
+    while (element && !isMatchingElement(nodeList, *element))
+        element = ElementTraversal::nextSibling(element);
+    return element;
+}
+
+inline Element* nextMatchingSiblingElement(const HTMLCollection& nodeList, Element* current)
+{
+    do {
+        current = ElementTraversal::nextSibling(current);
+    } while (current && !isMatchingElement(nodeList, *current));
+    return current;
+}
+
+inline Element* HTMLCollection::firstElement(ContainerNode& root) const
+{
+    if (usesCustomForwardOnlyTraversal())
+        return customElementAfter(nullptr);
+    if (m_shouldOnlyIncludeDirectChildren)
+        return firstMatchingChildElement(*this, root);
+    return firstMatchingElement(*this, root);
+}
+
+inline Element* HTMLCollection::traverseForward(Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root) const
+{
+    Element* element = &current;
+    if (usesCustomForwardOnlyTraversal()) {
+        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+            element = customElementAfter(element);
+            if (!element)
+                return nullptr;
+        }
+        return element;
+    }
+    if (m_shouldOnlyIncludeDirectChildren) {
+        for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+            element = nextMatchingSiblingElement(*this, element);
+            if (!element)
+                return nullptr;
+        }
+        return element;
+    }
+    for (traversedCount = 0; traversedCount < count; ++traversedCount) {
+        element = nextMatchingElement(*this, element, root);
+        if (!element)
+            return nullptr;
+    }
+    return element;
 }
 
-void HTMLCollection::invalidateCache(Document& document)
+Element* HTMLCollection::collectionFirst() const
 {
-    if (hasNamedElementCache())
-        invalidateNamedElementCache(document);
+    return firstElement(rootNode());
 }
 
-void HTMLCollection::invalidateNamedElementCache(Document& document) const
+Element* HTMLCollection::collectionLast() const
 {
-    ASSERT(hasNamedElementCache());
-    document.collectionWillClearIdNameMap(*this);
-    m_namedElementCache = nullptr;
+    // FIXME: This should be optimized similarly to the forward case.
+    auto& root = rootNode();
+    Element* last = m_shouldOnlyIncludeDirectChildren ? ElementTraversal::lastChild(&root) : ElementTraversal::lastWithin(&root);
+    return iterateForPreviousElement(last);
 }
 
-Element* HTMLCollection::namedItemSlow(const AtomicString& name) const
+Element* HTMLCollection::collectionTraverseForward(Element& current, unsigned count, unsigned& traversedCount) const
 {
+    return traverseForward(current, count, traversedCount, rootNode());
+}
+
+Element* HTMLCollection::collectionTraverseBackward(Element& current, unsigned count) const
+{
+    // FIXME: This should be optimized similarly to the forward case.
+    auto& root = rootNode();
+    Element* element = &current;
+    if (m_shouldOnlyIncludeDirectChildren) {
+        for (; count && element ; --count)
+            element = iterateForPreviousElement(ElementTraversal::previousSibling(element));
+        return element;
+    }
+    for (; count && element ; --count)
+        element = iterateForPreviousElement(ElementTraversal::previous(element, &root));
+    return element;
+}
+
+void HTMLCollection::invalidateCache() const
+{
+    m_indexCache.invalidate();
+    m_isNameCacheValid = false;
+    m_isItemRefElementsCacheValid = false;
+    m_idCache.clear();
+    m_nameCache.clear();
+}
+
+void HTMLCollection::invalidateIdNameCacheMaps() const
+{
+    m_idCache.clear();
+    m_nameCache.clear();
+}
+
+Node* HTMLCollection::namedItem(const AtomicString& name) const
+{
+    // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp
+    // This method first searches for an object with a matching id
+    // attribute. If a match is not found, the method then searches for an
+    // object with a matching name attribute, but only on those elements
+    // that are allowed a name attribute.
+
+    if (name.isEmpty())
+        return 0;
+
+    ContainerNode& root = rootNode();
+    if (!usesCustomForwardOnlyTraversal() && root.isInTreeScope()) {
+        TreeScope& treeScope = root.treeScope();
+        Element* candidate = 0;
+        if (treeScope.hasElementWithId(*name.impl())) {
+            if (!treeScope.containsMultipleElementsWithId(name))
+                candidate = treeScope.getElementById(name);
+        } else if (treeScope.hasElementWithName(*name.impl())) {
+            if (!treeScope.containsMultipleElementsWithName(name)) {
+                candidate = treeScope.getElementByName(name);
+                if (candidate && type() == DocAll && (!candidate->isHTMLElement() || !nameShouldBeVisibleInDocumentAll(toHTMLElement(*candidate))))
+                    candidate = 0;
+            }
+        } else
+            return 0;
+
+        if (candidate && isMatchingElement(*this, *candidate)
+            && (m_shouldOnlyIncludeDirectChildren ? candidate->parentNode() == &root : candidate->isDescendantOf(&root)))
+            return candidate;
+    }
+
     // The pathological case. We need to walk the entire subtree.
-    updateNamedElementCache();
-    ASSERT(m_namedElementCache);
+    updateNameCache();
 
-    if (const Vector<Element*>* idResults = m_namedElementCache->findElementsWithId(name)) {
+    if (Vector<Element*>* idResults = idCache(name)) {
         if (idResults->size())
             return idResults->at(0);
     }
 
-    if (const Vector<Element*>* nameResults = m_namedElementCache->findElementsWithName(name)) {
+    if (Vector<Element*>* nameResults = nameCache(name)) {
         if (nameResults->size())
             return nameResults->at(0);
     }
 
-    return nullptr;
+    return 0;
 }
 
-// Documented in https://dom.spec.whatwg.org/#interface-htmlcollection.
-const Vector<AtomicString>& HTMLCollection::supportedPropertyNames()
+void HTMLCollection::updateNameCache() const
 {
-    updateNamedElementCache();
-    ASSERT(m_namedElementCache);
-
-    return m_namedElementCache->propertyNames();
-}
-
-void HTMLCollection::updateNamedElementCache() const
-{
-    if (hasNamedElementCache())
+    if (hasNameCache())
         return;
 
-    auto cache = std::make_unique<CollectionNamedElementCache>();
+    ContainerNode& root = rootNode();
 
-    unsigned size = length();
-    for (unsigned i = 0; i < size; ++i) {
-        Element& element = *item(i);
-        const AtomicString& id = element.getIdAttribute();
-        if (!id.isEmpty())
-            cache->appendToIdCache(id, element);
-        if (!is<HTMLElement>(element))
+    unsigned count;
+    for (Element* element = firstElement(root); element; element = traverseForward(*element, 1, count, root)) {
+        const AtomicString& idAttrVal = element->getIdAttribute();
+        if (!idAttrVal.isEmpty())
+            appendIdCache(idAttrVal, element);
+        if (!element->isHTMLElement())
             continue;
-        const AtomicString& name = element.getNameAttribute();
-        if (!name.isEmpty() && id != name && (type() != DocAll || nameShouldBeVisibleInDocumentAll(downcast<HTMLElement>(element))))
-            cache->appendToNameCache(name, element);
+        const AtomicString& nameAttrVal = element->getNameAttribute();
+        if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element))))
+            appendNameCache(nameAttrVal, element);
     }
 
-    setNamedItemCache(WTFMove(cache));
+    setHasNameCache();
 }
 
-Vector<Ref<Element>> HTMLCollection::namedItems(const AtomicString& name) const
+bool HTMLCollection::hasNamedItem(const AtomicString& name) const
 {
-    // FIXME: This non-virtual function can't possibly be doing the correct thing for
-    // any derived class that overrides the virtual namedItem function.
-
-    Vector<Ref<Element>> elements;
+    // FIXME: We can do better when there are multiple elements of the same name.
+    return namedItem(name);
+}
 
+void HTMLCollection::namedItems(const AtomicString& name, Vector<Ref<Element>>& result) const
+{
+    ASSERT(result.isEmpty());
     if (name.isEmpty())
-        return elements;
-
-    updateNamedElementCache();
-    ASSERT(m_namedElementCache);
+        return;
 
-    auto* elementsWithId = m_namedElementCache->findElementsWithId(name);
-    auto* elementsWithName = m_namedElementCache->findElementsWithName(name);
+    updateNameCache();
 
-    elements.reserveInitialCapacity((elementsWithId ? elementsWithId->size() : 0) + (elementsWithName ? elementsWithName->size() : 0));
+    Vector<Element*>* idResults = idCache(name);
+    Vector<Element*>* nameResults = nameCache(name);
 
-    if (elementsWithId) {
-        for (auto& element : *elementsWithId)
-            elements.uncheckedAppend(*element);
-    }
-    if (elementsWithName) {
-        for (auto& element : *elementsWithName)
-            elements.uncheckedAppend(*element);
-    }
+    for (unsigned i = 0; idResults && i < idResults->size(); ++i)
+        result.append(*idResults->at(i));
 
-    return elements;
+    for (unsigned i = 0; nameResults && i < nameResults->size(); ++i)
+        result.append(*nameResults->at(i));
 }
 
-RefPtr<NodeList> HTMLCollection::tags(const String& name)
+PassRefPtr<NodeList> HTMLCollection::tags(const String& name)
 {
-    if (name.isNull())
-        return nullptr;
-
     return ownerNode().getElementsByTagName(name);
 }
 
+void HTMLCollection::append(NodeCacheMap& map, const AtomicString& key, Element* element)
+{
+    OwnPtr<Vector<Element*>>& vector = map.add(key.impl(), nullptr).iterator->value;
+    if (!vector)
+        vector = adoptPtr(new Vector<Element*>);
+    vector->append(element);
+}
+
 } // namespace WebCore