1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
8 * nsBaseContentList is a basic list of content nodes; nsContentList
9 * is a commonly used NodeList implementation (used for
10 * getElementsByTagName, some properties on HTMLDocument/Document, etc).
13 #ifndef nsContentList_h___
14 #define nsContentList_h___
16 #include "mozilla/Attributes.h"
17 #include "nsContentListDeclarations.h"
18 #include "nsISupports.h"
21 #include "nsIHTMLCollection.h"
22 #include "nsINodeList.h"
23 #include "nsStubMutationObserver.h"
24 #include "nsAtomHashKeys.h"
25 #include "nsCycleCollectionParticipant.h"
26 #include "nsNameSpaceManager.h"
27 #include "nsWrapperCache.h"
28 #include "nsHashKeys.h"
29 #include "mozilla/HashFunctions.h"
30 #include "mozilla/MemoryReporting.h"
31 #include "mozilla/dom/NameSpaceConstants.h"
33 // XXX Avoid including this here by moving function bodies to the cpp file.
34 #include "nsIContent.h"
36 namespace mozilla::dom
{
38 } // namespace mozilla::dom
40 class nsBaseContentList
: public nsINodeList
{
42 using Element
= mozilla::dom::Element
;
45 NS_DECL_CYCLE_COLLECTING_ISUPPORTS
48 int32_t IndexOf(nsIContent
* aContent
) override
;
49 nsIContent
* Item(uint32_t aIndex
) override
;
51 uint32_t Length() override
{ return mElements
.Length(); }
53 NS_DECL_CYCLE_COLLECTION_SKIPPABLE_WRAPPERCACHE_CLASS(nsBaseContentList
)
55 void AppendElement(nsIContent
* aContent
) {
57 mElements
.AppendElement(aContent
);
59 void MaybeAppendElement(nsIContent
* aContent
) {
61 AppendElement(aContent
);
66 * Insert the element at a given index, shifting the objects at
67 * the given index and later to make space.
68 * @param aContent Element to insert, must not be null
69 * @param aIndex Index to insert the element at.
71 void InsertElementAt(nsIContent
* aContent
, int32_t aIndex
) {
72 NS_ASSERTION(aContent
, "Element to insert must not be null");
73 mElements
.InsertElementAt(aIndex
, aContent
);
76 void RemoveElement(nsIContent
* aContent
) {
77 mElements
.RemoveElement(aContent
);
80 void Reset() { mElements
.Clear(); }
82 virtual int32_t IndexOf(nsIContent
* aContent
, bool aDoFlush
);
84 JSObject
* WrapObject(JSContext
* cx
,
85 JS::Handle
<JSObject
*> aGivenProto
) override
= 0;
87 void SetCapacity(uint32_t aCapacity
) { mElements
.SetCapacity(aCapacity
); }
89 virtual void LastRelease() {}
91 // Memory reporting. For now, subclasses of nsBaseContentList don't really
92 // need to report any members that are not part of the object itself, so we
93 // don't need to make this virtual.
94 size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf
) const;
97 virtual ~nsBaseContentList();
100 * To be called from non-destructor locations (e.g. unlink) that want to
101 * remove from caches. Cacheable subclasses should override.
103 virtual void RemoveFromCaches() {}
105 AutoTArray
<nsCOMPtr
<nsIContent
>, 10> mElements
;
108 class nsSimpleContentList
: public nsBaseContentList
{
110 explicit nsSimpleContentList(nsINode
* aRoot
)
111 : nsBaseContentList(), mRoot(aRoot
) {}
113 NS_DECL_ISUPPORTS_INHERITED
114 NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsSimpleContentList
,
117 nsINode
* GetParentObject() override
{ return mRoot
; }
118 JSObject
* WrapObject(JSContext
* cx
,
119 JS::Handle
<JSObject
*> aGivenProto
) override
;
122 virtual ~nsSimpleContentList() = default;
125 // This has to be a strong reference, the root might go away before the list.
126 nsCOMPtr
<nsINode
> mRoot
;
129 // Used for returning lists that will always be empty, such as the applets list
131 class nsEmptyContentList final
: public nsBaseContentList
,
132 public nsIHTMLCollection
{
134 explicit nsEmptyContentList(nsINode
* aRoot
)
135 : nsBaseContentList(), mRoot(aRoot
) {}
137 NS_DECL_ISUPPORTS_INHERITED
138 NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsEmptyContentList
,
141 nsINode
* GetParentObject() override
{ return mRoot
; }
143 JSObject
* WrapObject(JSContext
* cx
,
144 JS::Handle
<JSObject
*> aGivenProto
) override
;
146 JSObject
* GetWrapperPreserveColorInternal() override
{
147 return nsWrapperCache::GetWrapperPreserveColor();
149 void PreserveWrapperInternal(nsISupports
* aScriptObjectHolder
) override
{
150 nsWrapperCache::PreserveWrapper(aScriptObjectHolder
);
153 uint32_t Length() final
{ return 0; }
154 nsIContent
* Item(uint32_t aIndex
) override
;
155 Element
* GetElementAt(uint32_t index
) override
;
156 Element
* GetFirstNamedElement(const nsAString
& aName
, bool& aFound
) override
;
157 void GetSupportedNames(nsTArray
<nsString
>& aNames
) override
;
160 virtual ~nsEmptyContentList() = default;
163 // This has to be a strong reference, the root might go away before the list.
164 nsCOMPtr
<nsINode
> mRoot
;
168 * Class that's used as the key to hash nsContentList implementations
171 struct nsContentListKey
{
172 // We have to take an aIsHTMLDocument arg for two reasons:
173 // 1) We don't want to include Document.h in this header.
174 // 2) We need to do that to make nsContentList::RemoveFromHashtable
175 // work, because by the time it's called the document of the
176 // list's root node might have changed.
177 nsContentListKey(nsINode
* aRootNode
, int32_t aMatchNameSpaceId
,
178 const nsAString
& aTagname
, bool aIsHTMLDocument
)
179 : mRootNode(aRootNode
),
180 mMatchNameSpaceId(aMatchNameSpaceId
),
182 mIsHTMLDocument(aIsHTMLDocument
),
183 mHash(mozilla::AddToHash(mozilla::HashString(aTagname
), mRootNode
,
184 mMatchNameSpaceId
, mIsHTMLDocument
)) {}
186 nsContentListKey(const nsContentListKey
& aContentListKey
) = default;
188 inline uint32_t GetHash(void) const { return mHash
; }
190 nsINode
* const mRootNode
; // Weak ref
191 const int32_t mMatchNameSpaceId
;
192 const nsAString
& mTagname
;
193 bool mIsHTMLDocument
;
194 const uint32_t mHash
;
198 * Class that implements a possibly live NodeList that matches Elements
199 * in the tree based on some criterion.
201 class nsContentList
: public nsBaseContentList
,
202 public nsIHTMLCollection
,
203 public nsStubMutationObserver
{
205 enum class State
: uint8_t {
206 // The list is up to date and need not do any walking to be able to answer
207 // any questions anyone may have.
209 // The list contains no useful information and if anyone asks it anything it
210 // will have to populate itself before answering.
212 // The list has populated itself to a certain extent and that that part of
213 // the list is still valid. Requests for things outside that part of the
214 // list will require walking the tree some more. When a list is in this
215 // state, the last thing in mElements is the last node in the tree that the
221 NS_DECL_ISUPPORTS_INHERITED
224 * @param aRootNode The node under which to limit our search.
225 * @param aMatchAtom An atom whose meaning depends on aMatchNameSpaceId.
226 * The special value "*" always matches whatever aMatchAtom
227 * is matched against.
228 * @param aMatchNameSpaceId If kNameSpaceID_Unknown, then aMatchAtom is the
230 * If kNameSpaceID_Wildcard, then aMatchAtom is the
231 * localName to match.
232 * Otherwise we match nodes whose namespace is
233 * aMatchNameSpaceId and localName matches
235 * @param aDeep If false, then look only at children of the root, nothing
236 * deeper. If true, then look at the whole subtree rooted at
238 * @param aLiveList Whether the created list should be a live list observing
239 * mutations to the DOM tree.
241 nsContentList(nsINode
* aRootNode
, int32_t aMatchNameSpaceId
,
242 nsAtom
* aHTMLMatchAtom
, nsAtom
* aXMLMatchAtom
,
243 bool aDeep
= true, bool aLiveList
= true);
246 * @param aRootNode The node under which to limit our search.
247 * @param aFunc the function to be called to determine whether we match.
248 * This function MUST NOT ever cause mutation of the DOM.
249 * The nsContentList implementation guarantees that everything
250 * passed to the function will be IsElement().
251 * @param aDestroyFunc the function that will be called to destroy aData
252 * @param aData closure data that will need to be passed back to aFunc
253 * @param aDeep If false, then look only at children of the root, nothing
254 * deeper. If true, then look at the whole subtree rooted at
256 * @param aMatchAtom an atom to be passed back to aFunc
257 * @param aMatchNameSpaceId a namespace id to be passed back to aFunc
258 * @param aFuncMayDependOnAttr a boolean that indicates whether this list is
259 * sensitive to attribute changes.
260 * @param aLiveList Whether the created list should be a live list observing
261 * mutations to the DOM tree.
263 nsContentList(nsINode
* aRootNode
, nsContentListMatchFunc aFunc
,
264 nsContentListDestroyFunc aDestroyFunc
, void* aData
,
265 bool aDeep
= true, nsAtom
* aMatchAtom
= nullptr,
266 int32_t aMatchNameSpaceId
= kNameSpaceID_None
,
267 bool aFuncMayDependOnAttr
= true, bool aLiveList
= true);
270 using nsWrapperCache::GetWrapperPreserveColor
;
271 using nsWrapperCache::PreserveWrapper
;
272 JSObject
* WrapObject(JSContext
* aCx
,
273 JS::Handle
<JSObject
*> aGivenProto
) override
;
276 virtual ~nsContentList();
278 JSObject
* GetWrapperPreserveColorInternal() override
{
279 return nsWrapperCache::GetWrapperPreserveColor();
281 void PreserveWrapperInternal(nsISupports
* aScriptObjectHolder
) override
{
282 nsWrapperCache::PreserveWrapper(aScriptObjectHolder
);
286 // nsBaseContentList overrides
287 int32_t IndexOf(nsIContent
* aContent
, bool aDoFlush
) override
;
288 int32_t IndexOf(nsIContent
* aContent
) override
;
289 nsINode
* GetParentObject() override
{ return mRootNode
; }
291 uint32_t Length() final
{ return Length(true); }
292 nsIContent
* Item(uint32_t aIndex
) final
;
293 Element
* GetElementAt(uint32_t index
) override
;
294 Element
* GetFirstNamedElement(const nsAString
& aName
, bool& aFound
) override
{
295 Element
* item
= NamedItem(aName
, true);
299 void GetSupportedNames(nsTArray
<nsString
>& aNames
) override
;
301 // nsContentList public methods
302 uint32_t Length(bool aDoFlush
);
303 nsIContent
* Item(uint32_t aIndex
, bool aDoFlush
);
304 Element
* NamedItem(const nsAString
& aName
, bool aDoFlush
);
306 // nsIMutationObserver
307 NS_DECL_NSIMUTATIONOBSERVER_ATTRIBUTECHANGED
308 NS_DECL_NSIMUTATIONOBSERVER_CONTENTAPPENDED
309 NS_DECL_NSIMUTATIONOBSERVER_CONTENTINSERTED
310 NS_DECL_NSIMUTATIONOBSERVER_CONTENTREMOVED
311 NS_DECL_NSIMUTATIONOBSERVER_NODEWILLBEDESTROYED
313 static nsContentList
* FromSupports(nsISupports
* aSupports
) {
314 nsINodeList
* list
= static_cast<nsINodeList
*>(aSupports
);
317 nsCOMPtr
<nsINodeList
> list_qi
= do_QueryInterface(aSupports
);
319 // If this assertion fires the QI implementation for the object in
320 // question doesn't use the nsINodeList pointer as the nsISupports
321 // pointer. That must be fixed, or we'll crash...
322 NS_ASSERTION(list_qi
== list
, "Uh, fix QI!");
325 return static_cast<nsContentList
*>(list
);
328 bool MatchesKey(const nsContentListKey
& aKey
) const {
329 // The root node is most commonly the same: the document. And the
330 // most common namespace id is kNameSpaceID_Unknown. So check the
331 // string first. Cases in which whether our root's ownerDocument
332 // is HTML changes are extremely rare, so check those last.
333 MOZ_ASSERT(mXMLMatchAtom
,
334 "How did we get here with a null match atom on our list?");
335 return mXMLMatchAtom
->Equals(aKey
.mTagname
) &&
336 mRootNode
== aKey
.mRootNode
&&
337 mMatchNameSpaceId
== aKey
.mMatchNameSpaceId
&&
338 mIsHTMLDocument
== aKey
.mIsHTMLDocument
;
342 * Sets the state to LIST_DIRTY and clears mElements array.
343 * @note This is the only acceptable way to set state to LIST_DIRTY.
346 mState
= State::Dirty
;
347 InvalidateNamedItemsCache();
349 SetEnabledCallbacks(nsIMutationObserver::kNodeWillBeDestroyed
);
352 void LastRelease() override
;
357 // A cache from name to the first named item in mElements. Only possibly
358 // non-null when mState is State::UpToDate. Elements are kept alive by our
360 using NamedItemsCache
= nsTHashMap
<nsAtomHashKey
, Element
*>;
362 void InvalidateNamedItemsCache() {
363 mNamedItemsCache
= nullptr;
364 mNamedItemsCacheValid
= false;
367 inline void InsertElementInNamedItemsCache(nsIContent
&);
368 inline void InvalidateNamedItemsCacheForAttributeChange(int32_t aNameSpaceID
,
370 inline void InvalidateNamedItemsCacheForInsertion(Element
&);
371 inline void InvalidateNamedItemsCacheForDeletion(Element
&);
373 void EnsureNamedItemsCacheValid(bool aDoFlush
);
376 * Returns whether the element matches our criterion
378 * @param aElement the element to attempt to match
379 * @return whether we match
381 bool Match(Element
* aElement
);
383 * See if anything in the subtree rooted at aContent, including
384 * aContent itself, matches our criterion.
386 * @param aContent the root of the subtree to match against
387 * @return whether we match something in the tree rooted at aContent
389 bool MatchSelf(nsIContent
* aContent
);
392 * Populate our list. Stop once we have at least aNeededLength
393 * elements. At the end of PopulateSelf running, either the last
394 * node we examined is the last node in our array or we have
395 * traversed the whole document (or both).
397 * @param aNeededLength the length the list should have when we are
398 * done (unless it exhausts the document)
399 * @param aExpectedElementsIfDirty is for debugging only to
400 * assert that mElements has expected number of entries.
402 virtual void PopulateSelf(uint32_t aNeededLength
,
403 uint32_t aExpectedElementsIfDirty
= 0);
406 * @param aContainer a content node which must be a descendant of
408 * @return true if children or descendants of aContainer could match our
412 bool MayContainRelevantNodes(nsINode
* aContainer
) {
413 return mDeep
|| aContainer
== mRootNode
;
417 * Remove ourselves from the hashtable that caches commonly accessed
418 * content lists. Generally done on destruction.
420 void RemoveFromHashtable();
422 * If state is not LIST_UP_TO_DATE, fully populate ourselves with
423 * all the nodes we can find.
425 inline void BringSelfUpToDate(bool aDoFlush
);
428 * To be called from non-destructor locations that want to remove from caches.
429 * Needed because if subclasses want to have cache behavior they can't just
430 * override RemoveFromHashtable(), since we call that in our destructor.
432 void RemoveFromCaches() override
{ RemoveFromHashtable(); }
434 void MaybeMarkDirty() {
435 if (mState
!= State::Dirty
&& ++mMissedUpdates
> 128) {
441 nsINode
* mRootNode
; // Weak ref
442 int32_t mMatchNameSpaceId
;
443 RefPtr
<nsAtom
> mHTMLMatchAtom
;
444 RefPtr
<nsAtom
> mXMLMatchAtom
;
447 * Function to use to determine whether a piece of content matches
450 nsContentListMatchFunc mFunc
= nullptr;
452 * Cleanup closure data with this.
454 nsContentListDestroyFunc mDestroyFunc
= nullptr;
456 * Closure data to pass to mFunc when we call it
458 void* mData
= nullptr;
460 mozilla::UniquePtr
<NamedItemsCache
> mNamedItemsCache
;
462 uint8_t mMissedUpdates
= 0;
464 // The current state of the list.
468 * True if we are looking for elements named "*"
472 * Whether to actually descend the tree. If this is false, we won't
473 * consider grandkids of mRootNode.
477 * Whether the return value of mFunc could depend on the values of
480 bool mFuncMayDependOnAttr
: 1;
482 * Whether we actually need to flush to get our state correct.
484 bool mFlushesNeeded
: 1;
486 * Whether the ownerDocument of our root node at list creation time was an
487 * HTML document. Only needed when we're doing a namespace/atom match, not
488 * when doing function matching, always false otherwise.
490 bool mIsHTMLDocument
: 1;
492 * True mNamedItemsCache is valid. Note mNamedItemsCache might still be null
493 * if there's no named items at all.
495 bool mNamedItemsCacheValid
: 1;
497 * Whether the list observes mutations to the DOM tree.
499 const bool mIsLiveList
: 1;
501 * True if this content list is cached in a hash table.
502 * For nsContentList (but not its subclasses), the hash table is
503 * gContentListHashTable.
504 * For nsCacheableFuncStringContentList, the hash table is
505 * gFuncStringContentListHashTable.
506 * Other subclasses of nsContentList can't be in hash tables.
508 bool mInHashtable
: 1;
510 #ifdef DEBUG_CONTENT_LIST
516 * A class of cacheable content list; cached on the combination of aRootNode +
517 * aFunc + aDataString
519 class nsCacheableFuncStringContentList
;
521 class MOZ_STACK_CLASS nsFuncStringCacheKey
{
523 nsFuncStringCacheKey(nsINode
* aRootNode
, nsContentListMatchFunc aFunc
,
524 const nsAString
& aString
)
525 : mRootNode(aRootNode
), mFunc(aFunc
), mString(aString
) {}
527 uint32_t GetHash(void) const {
528 uint32_t hash
= mozilla::HashString(mString
);
529 return mozilla::AddToHash(hash
, mRootNode
, mFunc
);
533 friend class nsCacheableFuncStringContentList
;
535 nsINode
* const mRootNode
;
536 const nsContentListMatchFunc mFunc
;
537 const nsAString
& mString
;
540 // aDestroyFunc is allowed to be null
541 // aDataAllocator must always return a non-null pointer
542 class nsCacheableFuncStringContentList
: public nsContentList
{
544 virtual ~nsCacheableFuncStringContentList();
546 bool Equals(const nsFuncStringCacheKey
* aKey
) {
547 return mRootNode
== aKey
->mRootNode
&& mFunc
== aKey
->mFunc
&&
548 mString
== aKey
->mString
;
551 enum ContentListType
{ eNodeList
, eHTMLCollection
};
553 ContentListType mType
;
559 nsCacheableFuncStringContentList(
560 nsINode
* aRootNode
, nsContentListMatchFunc aFunc
,
561 nsContentListDestroyFunc aDestroyFunc
,
562 nsFuncStringContentListDataAllocator aDataAllocator
,
563 const nsAString
& aString
, mozilla::DebugOnly
<ContentListType
> aType
)
564 : nsContentList(aRootNode
, aFunc
, aDestroyFunc
, nullptr),
569 mData
= (*aDataAllocator
)(aRootNode
, &mString
);
573 void RemoveFromCaches() override
{ RemoveFromFuncStringHashtable(); }
574 void RemoveFromFuncStringHashtable();
579 class nsCachableElementsByNameNodeList
580 : public nsCacheableFuncStringContentList
{
582 nsCachableElementsByNameNodeList(
583 nsINode
* aRootNode
, nsContentListMatchFunc aFunc
,
584 nsContentListDestroyFunc aDestroyFunc
,
585 nsFuncStringContentListDataAllocator aDataAllocator
,
586 const nsAString
& aString
)
587 : nsCacheableFuncStringContentList(aRootNode
, aFunc
, aDestroyFunc
,
588 aDataAllocator
, aString
, eNodeList
) {}
590 NS_DECL_NSIMUTATIONOBSERVER_ATTRIBUTECHANGED
592 JSObject
* WrapObject(JSContext
* cx
,
593 JS::Handle
<JSObject
*> aGivenProto
) override
;
596 static const ContentListType sType
;
600 class nsCacheableFuncStringHTMLCollection
601 : public nsCacheableFuncStringContentList
{
603 nsCacheableFuncStringHTMLCollection(
604 nsINode
* aRootNode
, nsContentListMatchFunc aFunc
,
605 nsContentListDestroyFunc aDestroyFunc
,
606 nsFuncStringContentListDataAllocator aDataAllocator
,
607 const nsAString
& aString
)
608 : nsCacheableFuncStringContentList(aRootNode
, aFunc
, aDestroyFunc
,
609 aDataAllocator
, aString
,
612 JSObject
* WrapObject(JSContext
* cx
,
613 JS::Handle
<JSObject
*> aGivenProto
) override
;
616 static const ContentListType sType
;
620 class nsLabelsNodeList final
: public nsContentList
{
622 nsLabelsNodeList(nsINode
* aRootNode
, nsContentListMatchFunc aFunc
,
623 nsContentListDestroyFunc aDestroyFunc
, void* aData
)
624 : nsContentList(aRootNode
, aFunc
, aDestroyFunc
, aData
) {}
626 NS_DECL_NSIMUTATIONOBSERVER_ATTRIBUTECHANGED
627 NS_DECL_NSIMUTATIONOBSERVER_CONTENTAPPENDED
628 NS_DECL_NSIMUTATIONOBSERVER_CONTENTINSERTED
629 NS_DECL_NSIMUTATIONOBSERVER_CONTENTREMOVED
631 JSObject
* WrapObject(JSContext
* cx
,
632 JS::Handle
<JSObject
*> aGivenProto
) override
;
635 * Reset root, mutation observer, and clear content list
636 * if the root has been changed.
638 * @param aRootNode The node under which to limit our search.
640 void MaybeResetRoot(nsINode
* aRootNode
);
644 * Start searching at the last one if we already have nodes, otherwise
645 * start searching at the root.
647 * @param aNeededLength The list of length should have when we are
648 * done (unless it exhausts the document).
649 * @param aExpectedElementsIfDirty is for debugging only to
650 * assert that mElements has expected number of entries.
652 void PopulateSelf(uint32_t aNeededLength
,
653 uint32_t aExpectedElementsIfDirty
= 0) override
;
655 #endif // nsContentList_h___