michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: /* michael@0: * nsBaseContentList is a basic list of content nodes; nsContentList michael@0: * is a commonly used NodeList implementation (used for michael@0: * getElementsByTagName, some properties on nsIDOMHTMLDocument, etc). michael@0: */ michael@0: michael@0: #ifndef nsContentList_h___ michael@0: #define nsContentList_h___ michael@0: michael@0: #include "mozilla/Attributes.h" michael@0: #include "nsContentListDeclarations.h" michael@0: #include "nsISupports.h" michael@0: #include "nsTArray.h" michael@0: #include "nsString.h" michael@0: #include "nsIHTMLCollection.h" michael@0: #include "nsIDOMNodeList.h" michael@0: #include "nsINodeList.h" michael@0: #include "nsStubMutationObserver.h" michael@0: #include "nsIAtom.h" michael@0: #include "nsCycleCollectionParticipant.h" michael@0: #include "nsNameSpaceManager.h" michael@0: #include "nsWrapperCache.h" michael@0: #include "nsHashKeys.h" michael@0: #include "mozilla/HashFunctions.h" michael@0: michael@0: namespace mozilla { michael@0: namespace dom { michael@0: class Element; michael@0: } michael@0: } michael@0: michael@0: michael@0: class nsBaseContentList : public nsINodeList michael@0: { michael@0: public: michael@0: nsBaseContentList() michael@0: { michael@0: SetIsDOMBinding(); michael@0: } michael@0: virtual ~nsBaseContentList(); michael@0: michael@0: NS_DECL_CYCLE_COLLECTING_ISUPPORTS michael@0: michael@0: // nsIDOMNodeList michael@0: NS_DECL_NSIDOMNODELIST michael@0: michael@0: // nsINodeList michael@0: virtual int32_t IndexOf(nsIContent* aContent) MOZ_OVERRIDE; michael@0: virtual nsIContent* Item(uint32_t aIndex) MOZ_OVERRIDE; michael@0: michael@0: uint32_t Length() const { michael@0: return mElements.Length(); michael@0: } michael@0: michael@0: NS_DECL_CYCLE_COLLECTION_SKIPPABLE_SCRIPT_HOLDER_CLASS(nsBaseContentList) michael@0: michael@0: void AppendElement(nsIContent *aContent) michael@0: { michael@0: mElements.AppendElement(aContent); michael@0: } michael@0: void MaybeAppendElement(nsIContent* aContent) michael@0: { michael@0: if (aContent) michael@0: AppendElement(aContent); michael@0: } michael@0: michael@0: /** michael@0: * Insert the element at a given index, shifting the objects at michael@0: * the given index and later to make space. michael@0: * @param aContent Element to insert, must not be null michael@0: * @param aIndex Index to insert the element at. michael@0: */ michael@0: void InsertElementAt(nsIContent* aContent, int32_t aIndex) michael@0: { michael@0: NS_ASSERTION(aContent, "Element to insert must not be null"); michael@0: mElements.InsertElementAt(aIndex, aContent); michael@0: } michael@0: michael@0: void RemoveElement(nsIContent *aContent) michael@0: { michael@0: mElements.RemoveElement(aContent); michael@0: } michael@0: michael@0: void Reset() { michael@0: mElements.Clear(); michael@0: } michael@0: michael@0: virtual int32_t IndexOf(nsIContent *aContent, bool aDoFlush); michael@0: michael@0: virtual JSObject* WrapObject(JSContext *cx) michael@0: MOZ_OVERRIDE = 0; michael@0: michael@0: void SetCapacity(uint32_t aCapacity) michael@0: { michael@0: mElements.SetCapacity(aCapacity); michael@0: } michael@0: protected: michael@0: /** michael@0: * To be called from non-destructor locations (e.g. unlink) that want to michael@0: * remove from caches. Cacheable subclasses should override. michael@0: */ michael@0: virtual void RemoveFromCaches() michael@0: { michael@0: } michael@0: michael@0: nsTArray< nsCOMPtr > mElements; michael@0: }; michael@0: michael@0: michael@0: class nsSimpleContentList : public nsBaseContentList michael@0: { michael@0: public: michael@0: nsSimpleContentList(nsINode *aRoot) : nsBaseContentList(), michael@0: mRoot(aRoot) michael@0: { michael@0: } michael@0: michael@0: NS_DECL_ISUPPORTS_INHERITED michael@0: NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsSimpleContentList, michael@0: nsBaseContentList) michael@0: michael@0: virtual nsINode* GetParentObject() MOZ_OVERRIDE michael@0: { michael@0: return mRoot; michael@0: } michael@0: virtual JSObject* WrapObject(JSContext *cx) MOZ_OVERRIDE; michael@0: michael@0: private: michael@0: // This has to be a strong reference, the root might go away before the list. michael@0: nsCOMPtr mRoot; michael@0: }; michael@0: michael@0: /** michael@0: * Class that's used as the key to hash nsContentList implementations michael@0: * for fast retrieval michael@0: */ michael@0: struct nsContentListKey michael@0: { michael@0: nsContentListKey(nsINode* aRootNode, michael@0: int32_t aMatchNameSpaceId, michael@0: const nsAString& aTagname) michael@0: : mRootNode(aRootNode), michael@0: mMatchNameSpaceId(aMatchNameSpaceId), michael@0: mTagname(aTagname), michael@0: mHash(mozilla::AddToHash(mozilla::HashString(aTagname), mRootNode, michael@0: mMatchNameSpaceId)) michael@0: { michael@0: } michael@0: michael@0: nsContentListKey(const nsContentListKey& aContentListKey) michael@0: : mRootNode(aContentListKey.mRootNode), michael@0: mMatchNameSpaceId(aContentListKey.mMatchNameSpaceId), michael@0: mTagname(aContentListKey.mTagname), michael@0: mHash(aContentListKey.mHash) michael@0: { michael@0: } michael@0: michael@0: inline uint32_t GetHash(void) const michael@0: { michael@0: return mHash; michael@0: } michael@0: michael@0: nsINode* const mRootNode; // Weak ref michael@0: const int32_t mMatchNameSpaceId; michael@0: const nsAString& mTagname; michael@0: const uint32_t mHash; michael@0: }; michael@0: michael@0: /** michael@0: * LIST_UP_TO_DATE means that the list is up to date and need not do michael@0: * any walking to be able to answer any questions anyone may have. michael@0: */ michael@0: #define LIST_UP_TO_DATE 0 michael@0: /** michael@0: * LIST_DIRTY means that the list contains no useful information and michael@0: * if anyone asks it anything it will have to populate itself before michael@0: * answering. michael@0: */ michael@0: #define LIST_DIRTY 1 michael@0: /** michael@0: * LIST_LAZY means that the list has populated itself to a certain michael@0: * extent and that that part of the list is still valid. Requests for michael@0: * things outside that part of the list will require walking the tree michael@0: * some more. When a list is in this state, the last thing in michael@0: * mElements is the last node in the tree that the list looked at. michael@0: */ michael@0: #define LIST_LAZY 2 michael@0: michael@0: /** michael@0: * Class that implements a live NodeList that matches Elements in the michael@0: * tree based on some criterion. michael@0: */ michael@0: class nsContentList : public nsBaseContentList, michael@0: public nsIHTMLCollection, michael@0: public nsStubMutationObserver michael@0: { michael@0: public: michael@0: NS_DECL_ISUPPORTS_INHERITED michael@0: michael@0: /** michael@0: * @param aRootNode The node under which to limit our search. michael@0: * @param aMatchAtom An atom whose meaning depends on aMatchNameSpaceId. michael@0: * The special value "*" always matches whatever aMatchAtom michael@0: * is matched against. michael@0: * @param aMatchNameSpaceId If kNameSpaceID_Unknown, then aMatchAtom is the michael@0: * tagName to match. michael@0: * If kNameSpaceID_Wildcard, then aMatchAtom is the michael@0: * localName to match. michael@0: * Otherwise we match nodes whose namespace is michael@0: * aMatchNameSpaceId and localName matches michael@0: * aMatchAtom. michael@0: * @param aDeep If false, then look only at children of the root, nothing michael@0: * deeper. If true, then look at the whole subtree rooted at michael@0: * our root. michael@0: */ michael@0: nsContentList(nsINode* aRootNode, michael@0: int32_t aMatchNameSpaceId, michael@0: nsIAtom* aHTMLMatchAtom, michael@0: nsIAtom* aXMLMatchAtom, michael@0: bool aDeep = true); michael@0: michael@0: /** michael@0: * @param aRootNode The node under which to limit our search. michael@0: * @param aFunc the function to be called to determine whether we match. michael@0: * This function MUST NOT ever cause mutation of the DOM. michael@0: * The nsContentList implementation guarantees that everything michael@0: * passed to the function will be IsElement(). michael@0: * @param aDestroyFunc the function that will be called to destroy aData michael@0: * @param aData closure data that will need to be passed back to aFunc michael@0: * @param aDeep If false, then look only at children of the root, nothing michael@0: * deeper. If true, then look at the whole subtree rooted at michael@0: * our root. michael@0: * @param aMatchAtom an atom to be passed back to aFunc michael@0: * @param aMatchNameSpaceId a namespace id to be passed back to aFunc michael@0: * @param aFuncMayDependOnAttr a boolean that indicates whether this list is michael@0: * sensitive to attribute changes. michael@0: */ michael@0: nsContentList(nsINode* aRootNode, michael@0: nsContentListMatchFunc aFunc, michael@0: nsContentListDestroyFunc aDestroyFunc, michael@0: void* aData, michael@0: bool aDeep = true, michael@0: nsIAtom* aMatchAtom = nullptr, michael@0: int32_t aMatchNameSpaceId = kNameSpaceID_None, michael@0: bool aFuncMayDependOnAttr = true); michael@0: virtual ~nsContentList(); michael@0: michael@0: // nsWrapperCache michael@0: using nsWrapperCache::GetWrapperPreserveColor; michael@0: virtual JSObject* WrapObject(JSContext* aCx) MOZ_OVERRIDE; michael@0: protected: michael@0: virtual JSObject* GetWrapperPreserveColorInternal() MOZ_OVERRIDE michael@0: { michael@0: return nsWrapperCache::GetWrapperPreserveColor(); michael@0: } michael@0: public: michael@0: michael@0: // nsIDOMHTMLCollection michael@0: NS_DECL_NSIDOMHTMLCOLLECTION michael@0: michael@0: // nsBaseContentList overrides michael@0: virtual int32_t IndexOf(nsIContent *aContent, bool aDoFlush) MOZ_OVERRIDE; michael@0: virtual int32_t IndexOf(nsIContent* aContent) MOZ_OVERRIDE; michael@0: virtual nsINode* GetParentObject() MOZ_OVERRIDE michael@0: { michael@0: return mRootNode; michael@0: } michael@0: michael@0: virtual nsIContent* Item(uint32_t aIndex) MOZ_OVERRIDE; michael@0: virtual mozilla::dom::Element* GetElementAt(uint32_t index) MOZ_OVERRIDE; michael@0: virtual mozilla::dom::Element* michael@0: GetFirstNamedElement(const nsAString& aName, bool& aFound) MOZ_OVERRIDE michael@0: { michael@0: mozilla::dom::Element* item = NamedItem(aName, true); michael@0: aFound = !!item; michael@0: return item; michael@0: } michael@0: virtual void GetSupportedNames(unsigned aFlags, michael@0: nsTArray& aNames) MOZ_OVERRIDE; michael@0: michael@0: // nsContentList public methods michael@0: NS_HIDDEN_(uint32_t) Length(bool aDoFlush); michael@0: NS_HIDDEN_(nsIContent*) Item(uint32_t aIndex, bool aDoFlush); michael@0: NS_HIDDEN_(mozilla::dom::Element*) michael@0: NamedItem(const nsAString& aName, bool aDoFlush); michael@0: michael@0: // nsIMutationObserver michael@0: NS_DECL_NSIMUTATIONOBSERVER_ATTRIBUTECHANGED michael@0: NS_DECL_NSIMUTATIONOBSERVER_CONTENTAPPENDED michael@0: NS_DECL_NSIMUTATIONOBSERVER_CONTENTINSERTED michael@0: NS_DECL_NSIMUTATIONOBSERVER_CONTENTREMOVED michael@0: NS_DECL_NSIMUTATIONOBSERVER_NODEWILLBEDESTROYED michael@0: michael@0: static nsContentList* FromSupports(nsISupports* aSupports) michael@0: { michael@0: nsINodeList* list = static_cast(aSupports); michael@0: #ifdef DEBUG michael@0: { michael@0: nsCOMPtr list_qi = do_QueryInterface(aSupports); michael@0: michael@0: // If this assertion fires the QI implementation for the object in michael@0: // question doesn't use the nsINodeList pointer as the nsISupports michael@0: // pointer. That must be fixed, or we'll crash... michael@0: NS_ASSERTION(list_qi == list, "Uh, fix QI!"); michael@0: } michael@0: #endif michael@0: return static_cast(list); michael@0: } michael@0: michael@0: bool MatchesKey(const nsContentListKey& aKey) const michael@0: { michael@0: // The root node is most commonly the same: the document. And the michael@0: // most common namespace id is kNameSpaceID_Unknown. So check the michael@0: // string first. michael@0: NS_PRECONDITION(mXMLMatchAtom, michael@0: "How did we get here with a null match atom on our list?"); michael@0: return michael@0: mXMLMatchAtom->Equals(aKey.mTagname) && michael@0: mRootNode == aKey.mRootNode && michael@0: mMatchNameSpaceId == aKey.mMatchNameSpaceId; michael@0: } michael@0: michael@0: /** michael@0: * Sets the state to LIST_DIRTY and clears mElements array. michael@0: * @note This is the only acceptable way to set state to LIST_DIRTY. michael@0: */ michael@0: void SetDirty() michael@0: { michael@0: mState = LIST_DIRTY; michael@0: Reset(); michael@0: } michael@0: michael@0: protected: michael@0: /** michael@0: * Returns whether the element matches our criterion michael@0: * michael@0: * @param aElement the element to attempt to match michael@0: * @return whether we match michael@0: */ michael@0: bool Match(mozilla::dom::Element *aElement); michael@0: /** michael@0: * See if anything in the subtree rooted at aContent, including michael@0: * aContent itself, matches our criterion. michael@0: * michael@0: * @param aContent the root of the subtree to match against michael@0: * @return whether we match something in the tree rooted at aContent michael@0: */ michael@0: bool MatchSelf(nsIContent *aContent); michael@0: michael@0: /** michael@0: * Populate our list. Stop once we have at least aNeededLength michael@0: * elements. At the end of PopulateSelf running, either the last michael@0: * node we examined is the last node in our array or we have michael@0: * traversed the whole document (or both). michael@0: * michael@0: * @param aNeededLength the length the list should have when we are michael@0: * done (unless it exhausts the document) michael@0: */ michael@0: void PopulateSelf(uint32_t aNeededLength); michael@0: michael@0: /** michael@0: * @param aContainer a content node which must be a descendant of michael@0: * mRootNode michael@0: * @return true if children or descendants of aContainer could match our michael@0: * criterion. michael@0: * false otherwise. michael@0: */ michael@0: bool MayContainRelevantNodes(nsINode* aContainer) michael@0: { michael@0: return mDeep || aContainer == mRootNode; michael@0: } michael@0: michael@0: /** michael@0: * Remove ourselves from the hashtable that caches commonly accessed michael@0: * content lists. Generally done on destruction. michael@0: */ michael@0: void RemoveFromHashtable(); michael@0: /** michael@0: * If state is not LIST_UP_TO_DATE, fully populate ourselves with michael@0: * all the nodes we can find. michael@0: */ michael@0: inline void BringSelfUpToDate(bool aDoFlush); michael@0: michael@0: /** michael@0: * To be called from non-destructor locations that want to remove from caches. michael@0: * Needed because if subclasses want to have cache behavior they can't just michael@0: * override RemoveFromHashtable(), since we call that in our destructor. michael@0: */ michael@0: virtual void RemoveFromCaches() MOZ_OVERRIDE michael@0: { michael@0: RemoveFromHashtable(); michael@0: } michael@0: michael@0: nsINode* mRootNode; // Weak ref michael@0: int32_t mMatchNameSpaceId; michael@0: nsCOMPtr mHTMLMatchAtom; michael@0: nsCOMPtr mXMLMatchAtom; michael@0: michael@0: /** michael@0: * Function to use to determine whether a piece of content matches michael@0: * our criterion michael@0: */ michael@0: nsContentListMatchFunc mFunc; michael@0: /** michael@0: * Cleanup closure data with this. michael@0: */ michael@0: nsContentListDestroyFunc mDestroyFunc; michael@0: /** michael@0: * Closure data to pass to mFunc when we call it michael@0: */ michael@0: void* mData; michael@0: /** michael@0: * The current state of the list (possible values are: michael@0: * LIST_UP_TO_DATE, LIST_LAZY, LIST_DIRTY michael@0: */ michael@0: uint8_t mState; michael@0: michael@0: // The booleans have to use uint8_t to pack with mState, because MSVC won't michael@0: // pack different typedefs together. Once we no longer have to worry about michael@0: // flushes in XML documents, we can go back to using bool for the michael@0: // booleans. michael@0: michael@0: /** michael@0: * True if we are looking for elements named "*" michael@0: */ michael@0: uint8_t mMatchAll : 1; michael@0: /** michael@0: * Whether to actually descend the tree. If this is false, we won't michael@0: * consider grandkids of mRootNode. michael@0: */ michael@0: uint8_t mDeep : 1; michael@0: /** michael@0: * Whether the return value of mFunc could depend on the values of michael@0: * attributes. michael@0: */ michael@0: uint8_t mFuncMayDependOnAttr : 1; michael@0: /** michael@0: * Whether we actually need to flush to get our state correct. michael@0: */ michael@0: uint8_t mFlushesNeeded : 1; michael@0: michael@0: #ifdef DEBUG_CONTENT_LIST michael@0: void AssertInSync(); michael@0: #endif michael@0: }; michael@0: michael@0: /** michael@0: * A class of cacheable content list; cached on the combination of aRootNode + aFunc + aDataString michael@0: */ michael@0: class nsCacheableFuncStringContentList; michael@0: michael@0: class MOZ_STACK_CLASS nsFuncStringCacheKey { michael@0: public: michael@0: nsFuncStringCacheKey(nsINode* aRootNode, michael@0: nsContentListMatchFunc aFunc, michael@0: const nsAString& aString) : michael@0: mRootNode(aRootNode), michael@0: mFunc(aFunc), michael@0: mString(aString) michael@0: {} michael@0: michael@0: uint32_t GetHash(void) const michael@0: { michael@0: uint32_t hash = mozilla::HashString(mString); michael@0: return mozilla::AddToHash(hash, mRootNode, mFunc); michael@0: } michael@0: michael@0: private: michael@0: friend class nsCacheableFuncStringContentList; michael@0: michael@0: nsINode* const mRootNode; michael@0: const nsContentListMatchFunc mFunc; michael@0: const nsAString& mString; michael@0: }; michael@0: michael@0: // aDestroyFunc is allowed to be null michael@0: // aDataAllocator must always return a non-null pointer michael@0: class nsCacheableFuncStringContentList : public nsContentList { michael@0: public: michael@0: virtual ~nsCacheableFuncStringContentList(); michael@0: michael@0: bool Equals(const nsFuncStringCacheKey* aKey) { michael@0: return mRootNode == aKey->mRootNode && mFunc == aKey->mFunc && michael@0: mString == aKey->mString; michael@0: } michael@0: michael@0: #ifdef DEBUG michael@0: enum ContentListType { michael@0: eNodeList, michael@0: eHTMLCollection michael@0: }; michael@0: ContentListType mType; michael@0: #endif michael@0: michael@0: protected: michael@0: nsCacheableFuncStringContentList(nsINode* aRootNode, michael@0: nsContentListMatchFunc aFunc, michael@0: nsContentListDestroyFunc aDestroyFunc, michael@0: nsFuncStringContentListDataAllocator aDataAllocator, michael@0: const nsAString& aString) : michael@0: nsContentList(aRootNode, aFunc, aDestroyFunc, nullptr), michael@0: mString(aString) michael@0: { michael@0: mData = (*aDataAllocator)(aRootNode, &mString); michael@0: MOZ_ASSERT(mData); michael@0: } michael@0: michael@0: virtual void RemoveFromCaches() MOZ_OVERRIDE { michael@0: RemoveFromFuncStringHashtable(); michael@0: } michael@0: void RemoveFromFuncStringHashtable(); michael@0: michael@0: nsString mString; michael@0: }; michael@0: michael@0: class nsCacheableFuncStringNodeList michael@0: : public nsCacheableFuncStringContentList michael@0: { michael@0: public: michael@0: nsCacheableFuncStringNodeList(nsINode* aRootNode, michael@0: nsContentListMatchFunc aFunc, michael@0: nsContentListDestroyFunc aDestroyFunc, michael@0: nsFuncStringContentListDataAllocator aDataAllocator, michael@0: const nsAString& aString) michael@0: : nsCacheableFuncStringContentList(aRootNode, aFunc, aDestroyFunc, michael@0: aDataAllocator, aString) michael@0: { michael@0: #ifdef DEBUG michael@0: mType = eNodeList; michael@0: #endif michael@0: } michael@0: michael@0: virtual JSObject* WrapObject(JSContext *cx) MOZ_OVERRIDE; michael@0: michael@0: #ifdef DEBUG michael@0: static const ContentListType sType; michael@0: #endif michael@0: }; michael@0: michael@0: class nsCacheableFuncStringHTMLCollection michael@0: : public nsCacheableFuncStringContentList michael@0: { michael@0: public: michael@0: nsCacheableFuncStringHTMLCollection(nsINode* aRootNode, michael@0: nsContentListMatchFunc aFunc, michael@0: nsContentListDestroyFunc aDestroyFunc, michael@0: nsFuncStringContentListDataAllocator aDataAllocator, michael@0: const nsAString& aString) michael@0: : nsCacheableFuncStringContentList(aRootNode, aFunc, aDestroyFunc, michael@0: aDataAllocator, aString) michael@0: { michael@0: #ifdef DEBUG michael@0: mType = eHTMLCollection; michael@0: #endif michael@0: } michael@0: michael@0: virtual JSObject* WrapObject(JSContext *cx) MOZ_OVERRIDE; michael@0: michael@0: #ifdef DEBUG michael@0: static const ContentListType sType; michael@0: #endif michael@0: }; michael@0: michael@0: #endif // nsContentList_h___