Replace WTF::move with WTFMove
[WebKit-https.git] / Source / WebCore / html / HTMLCollection.h
index c749b49..b7f4f78 100644 (file)
@@ -1,7 +1,7 @@
 /*
  * 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, 2004, 2005, 2006, 2007, 2008, 2011, 2012, 2013, 2014 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
 #ifndef HTMLCollection_h
 #define HTMLCollection_h
 
-#include "CollectionType.h"
-#include "ContainerNode.h"
-#include "Document.h"
+#include "CollectionIndexCache.h"
 #include "HTMLNames.h"
 #include "LiveNodeList.h"
 #include "ScriptWrappable.h"
-#include <wtf/Forward.h>
 #include <wtf/HashMap.h>
-#include <wtf/Vector.h>
 
 namespace WebCore {
 
 class Element;
 
-class HTMLCollection : public ScriptWrappable, public RefCounted<HTMLCollection> {
+class CollectionNamedElementCache {
 public:
-    enum ItemAfterOverrideType {
-        OverridesItemAfter,
-        DoesNotOverrideItemAfter,
-    };
+    const Vector<Element*>* findElementsWithId(const AtomicString& id) const;
+    const Vector<Element*>* findElementsWithName(const AtomicString& name) const;
+    const Vector<AtomicString>& propertyNames() const { return m_propertyNames; }
 
-    static PassRefPtr<HTMLCollection> create(ContainerNode& base, CollectionType);
+    void appendToIdCache(const AtomicString& id, Element&);
+    void appendToNameCache(const AtomicString& name, Element&);
+    void didPopulate();
+
+    size_t memoryCost() const;
+
+private:
+    typedef HashMap<AtomicStringImpl*, Vector<Element*>> StringToElementsMap;
+
+    const Vector<Element*>* find(const StringToElementsMap&, const AtomicString& key) const;
+    void append(StringToElementsMap&, const AtomicString& key, Element&);
+
+    StringToElementsMap m_idMap;
+    StringToElementsMap m_nameMap;
+    Vector<AtomicString> m_propertyNames;
+
+#if !ASSERT_DISABLED
+    bool m_didPopulate { false };
+#endif
+};
+
+// HTMLCollection subclasses NodeList to maintain legacy ObjC API compatibility.
+class HTMLCollection : public NodeList {
+public:
     virtual ~HTMLCollection();
 
     // DOM API
-    unsigned length() const;
-    Node* item(unsigned offset) const;
-    virtual Node* namedItem(const AtomicString& name) const;
-    PassRefPtr<NodeList> tags(const String&);
+    virtual Element* item(unsigned index) const override = 0; // Tighten return type from NodeList::item().
+    virtual Element* namedItem(const AtomicString& name) const = 0;
+    const Vector<AtomicString>& supportedPropertyNames();
+    RefPtr<NodeList> tags(const String&);
 
     // Non-DOM API
-    virtual bool hasNamedItem(const AtomicString& name) const;
-    void namedItems(const AtomicString& name, Vector<Ref<Element>>&) const;
-    bool isEmpty() const
-    {
-        if (isLengthCacheValid())
-            return !cachedLength();
-        if (isElementCacheValid())
-            return !cachedElement();
-        return !item(0);
-    }
-    bool hasExactlyOneItem() const
-    {
-        if (isLengthCacheValid())
-            return cachedLength() == 1;
-        if (isElementCacheValid())
-            return cachedElement() && !cachedElementOffset() && !item(1);
-        return item(0) && !item(1);
-    }
-
-    virtual Element* virtualItemAfter(unsigned& offsetInArray, Element*) const;
-
-    Element* traverseFirstElement(unsigned& offsetInArray, ContainerNode* root) const;
-    Element* traverseForwardToOffset(unsigned offset, Element* currentElement, unsigned& currentOffset, unsigned& offsetInArray, ContainerNode* root) const;
-
-    ALWAYS_INLINE bool isRootedAtDocument() const { return m_rootType == NodeListIsRootedAtDocument; }
-    ALWAYS_INLINE NodeListInvalidationType invalidationType() const { return static_cast<NodeListInvalidationType>(m_invalidationType); }
-    ALWAYS_INLINE CollectionType type() const { return static_cast<CollectionType>(m_collectionType); }
-    ContainerNode& ownerNode() const { return const_cast<ContainerNode&>(m_ownerNode.get()); }
-    ALWAYS_INLINE void invalidateCache(const QualifiedName* attrName) const
-    {
-        if (!attrName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attrName))
-            invalidateCache();
-        else if (*attrName == HTMLNames::idAttr || *attrName == HTMLNames::nameAttr)
-            invalidateIdNameCacheMaps();
-    }
-    void invalidateCache() const;
-    void invalidateIdNameCacheMaps() const;
+    Vector<Ref<Element>> namedItems(const AtomicString& name) const;
+    virtual size_t memoryCost() const override;
 
-protected:
-    HTMLCollection(ContainerNode& base, CollectionType, ItemAfterOverrideType);
+    bool isRootedAtDocument() const;
+    NodeListInvalidationType invalidationType() const;
+    CollectionType type() const;
+    ContainerNode& ownerNode() const;
+    ContainerNode& rootNode() const;
+    void invalidateCacheForAttribute(const QualifiedName* attributeName);
+    virtual void invalidateCache(Document&);
 
-    virtual void updateNameCache() const;
+    bool hasNamedElementCache() const;
 
-    typedef HashMap<AtomicStringImpl*, OwnPtr<Vector<Element*>>> NodeCacheMap;
-    Vector<Element*>* idCache(const AtomicString& name) const { return m_idCache.get(name.impl()); }
-    Vector<Element*>* nameCache(const AtomicString& name) const { return m_nameCache.get(name.impl()); }
-    void appendIdCache(const AtomicString& name, Element* element) const { append(m_idCache, name, element); }
-    void appendNameCache(const AtomicString& name, Element* element) const { append(m_nameCache, name, element); }
+protected:
+    HTMLCollection(ContainerNode& base, CollectionType);
 
-    Document& document() const { return m_ownerNode->document(); }
-    ContainerNode& rootNode() const;
-    bool overridesItemAfter() const { return m_overridesItemAfter; }
-
-    ALWAYS_INLINE bool isElementCacheValid() const { return m_isElementCacheValid; }
-    ALWAYS_INLINE Element* cachedElement() const { return m_cachedElement; }
-    ALWAYS_INLINE unsigned cachedElementOffset() const { return m_cachedElementOffset; }
-
-    ALWAYS_INLINE bool isLengthCacheValid() const { return m_isLengthCacheValid; }
-    ALWAYS_INLINE unsigned cachedLength() const { return m_cachedLength; }
-    ALWAYS_INLINE void setLengthCache(unsigned length) const
-    {
-        m_cachedLength = length;
-        m_isLengthCacheValid = true;
-    }
-    ALWAYS_INLINE void setCachedElement(Element& element, unsigned offset) const
-    {
-        m_cachedElement = &element;
-        m_cachedElementOffset = offset;
-        m_isElementCacheValid = true;
-    }
-    void setCachedElement(Element&, unsigned offset, unsigned elementsArrayOffset) const;
-
-    ALWAYS_INLINE bool isItemRefElementsCacheValid() const { return m_isItemRefElementsCacheValid; }
-    ALWAYS_INLINE void setItemRefElementsCacheValid() const { m_isItemRefElementsCacheValid = true; }
-
-    ALWAYS_INLINE NodeListRootType rootType() const { return static_cast<NodeListRootType>(m_rootType); }
-
-    bool hasNameCache() const { return m_isNameCacheValid; }
-    void setHasNameCache() const { m_isNameCacheValid = true; }
+    virtual void updateNamedElementCache() const;
+    Element* namedItemSlow(const AtomicString& name) const;
 
-private:
-    Element* traverseNextElement(unsigned& offsetInArray, Element* previous, ContainerNode* root) const;
+    void setNamedItemCache(std::unique_ptr<CollectionNamedElementCache>) const;
+    const CollectionNamedElementCache& namedItemCaches() const;
+
+    Document& document() const;
 
-    static void append(NodeCacheMap&, const AtomicString&, Element*);
+    void invalidateNamedElementCache(Document&) const;
 
-    Element* elementBeforeOrAfterCachedElement(unsigned offset, ContainerNode* root) const;
-    bool isLastItemCloserThanLastOrCachedItem(unsigned offset) const;
-    bool isFirstItemCloserThanCachedItem(unsigned offset) const;
-    Element* iterateForPreviousElement(Element* current) const;
-    Element* itemBefore(Element* previousItem) const;
+    enum RootType { IsRootedAtNode, IsRootedAtDocument };
+    static RootType rootTypeFromCollectionType(CollectionType);
 
     Ref<ContainerNode> m_ownerNode;
-    mutable Element* m_cachedElement;
-    mutable unsigned m_cachedLength;
-    mutable unsigned m_cachedElementOffset;
-    mutable unsigned m_isLengthCacheValid : 1;
-    mutable unsigned m_isElementCacheValid : 1;
-    const unsigned m_rootType : 2;
-    const unsigned m_invalidationType : 4;
-    const unsigned m_shouldOnlyIncludeDirectChildren : 1;
 
-    // From HTMLCollection
-    mutable unsigned m_isNameCacheValid : 1;
-    const unsigned m_collectionType : 5;
-    const unsigned m_overridesItemAfter : 1;
-    mutable unsigned m_isItemRefElementsCacheValid : 1;
+    mutable std::unique_ptr<CollectionNamedElementCache> m_namedElementCache;
 
-    mutable NodeCacheMap m_idCache;
-    mutable NodeCacheMap m_nameCache;
-    mutable unsigned m_cachedElementsArrayOffset;
+    const unsigned m_collectionType : 5;
+    const unsigned m_invalidationType : 4;
+    const unsigned m_rootType : 1;
 };
 
-} // namespace
-
+inline ContainerNode& HTMLCollection::rootNode() const
+{
+    if (isRootedAtDocument() && ownerNode().inDocument())
+        return ownerNode().document();
+
+    return ownerNode();
+}
+
+inline const Vector<Element*>* CollectionNamedElementCache::findElementsWithId(const AtomicString& id) const
+{
+    return find(m_idMap, id);
+}
+
+inline const Vector<Element*>* CollectionNamedElementCache::findElementsWithName(const AtomicString& name) const
+{
+    return find(m_nameMap, name);
+}
+
+inline void CollectionNamedElementCache::appendToIdCache(const AtomicString& id, Element& element)
+{
+    append(m_idMap, id, element);
+}
+
+inline void CollectionNamedElementCache::appendToNameCache(const AtomicString& name, Element& element)
+{
+    append(m_nameMap, name, element);
+}
+
+inline size_t CollectionNamedElementCache::memoryCost() const
+{
+    return (m_idMap.size() + m_nameMap.size()) * sizeof(Element*) + m_propertyNames.size() * sizeof(AtomicString);
+}
+
+inline void CollectionNamedElementCache::didPopulate()
+{
+#if !ASSERT_DISABLED
+    m_didPopulate = true;
 #endif
+    if (size_t cost = memoryCost())
+        reportExtraMemoryAllocatedForCollectionIndexCache(cost);
+}
+
+inline const Vector<Element*>* CollectionNamedElementCache::find(const StringToElementsMap& map, const AtomicString& key) const
+{
+    ASSERT(m_didPopulate);
+    auto it = map.find(key.impl());
+    return it != map.end() ? &it->value : nullptr;
+}
+
+inline void CollectionNamedElementCache::append(StringToElementsMap& map, const AtomicString& key, Element& element)
+{
+    if (!m_idMap.contains(key.impl()) && !m_nameMap.contains(key.impl()))
+        m_propertyNames.append(key);
+    map.add(key.impl(), Vector<Element*>()).iterator->value.append(&element);
+}
+
+inline size_t HTMLCollection::memoryCost() const
+{
+    return m_namedElementCache ? m_namedElementCache->memoryCost() : 0;
+}
+
+inline bool HTMLCollection::isRootedAtDocument() const
+{
+    return m_rootType == IsRootedAtDocument;
+}
+
+inline NodeListInvalidationType HTMLCollection::invalidationType() const
+{
+    return static_cast<NodeListInvalidationType>(m_invalidationType);
+}
+
+inline CollectionType HTMLCollection::type() const
+{
+    return static_cast<CollectionType>(m_collectionType);
+}
+
+inline ContainerNode& HTMLCollection::ownerNode() const
+{
+    return const_cast<ContainerNode&>(m_ownerNode.get());
+}
+
+inline Document& HTMLCollection::document() const
+{
+    return m_ownerNode->document();
+}
+
+inline void HTMLCollection::invalidateCacheForAttribute(const QualifiedName* attributeName)
+{
+    if (!attributeName || shouldInvalidateTypeOnAttributeChange(invalidationType(), *attributeName))
+        invalidateCache(document());
+    else if (hasNamedElementCache() && (*attributeName == HTMLNames::idAttr || *attributeName == HTMLNames::nameAttr))
+        invalidateNamedElementCache(document());
+}
+
+inline bool HTMLCollection::hasNamedElementCache() const
+{
+    return !!m_namedElementCache;
+}
+
+inline void HTMLCollection::setNamedItemCache(std::unique_ptr<CollectionNamedElementCache> cache) const
+{
+    ASSERT(cache);
+    ASSERT(!m_namedElementCache);
+    cache->didPopulate();
+    m_namedElementCache = WTFMove(cache);
+    document().collectionCachedIdNameMap(*this);
+}
+
+inline const CollectionNamedElementCache& HTMLCollection::namedItemCaches() const
+{
+    ASSERT(!!m_namedElementCache);
+    return *m_namedElementCache;
+}
+
+} // namespace WebCore
+
+#define SPECIALIZE_TYPE_TRAITS_HTMLCOLLECTION(ClassName, Type) \
+SPECIALIZE_TYPE_TRAITS_BEGIN(WebCore::ClassName) \
+    static bool isType(const WebCore::HTMLCollection& collection) { return collection.type() == WebCore::Type; } \
+SPECIALIZE_TYPE_TRAITS_END()
+
+#endif // HTMLCollection_h