dom/base/nsContentList.cpp

   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/. */
   6
   7 /*
   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).
  11  */
  12
  13 #include "nsContentList.h"
  14 #include "nsIContent.h"
  15 #include "mozilla/dom/Document.h"
  16 #include "mozilla/ContentIterator.h"
  17 #include "mozilla/dom/Element.h"
  18 #include "nsWrapperCacheInlines.h"
  19 #include "nsContentUtils.h"
  20 #include "nsCCUncollectableMarker.h"
  21 #include "nsGkAtoms.h"
  22 #include "mozilla/dom/HTMLCollectionBinding.h"
  23 #include "mozilla/dom/NodeListBinding.h"
  24 #include "mozilla/Likely.h"
  25 #include "nsGenericHTMLElement.h"
  26 #include "jsfriendapi.h"
  27 #include <algorithm>
  28 #include "mozilla/dom/NodeInfoInlines.h"
  29 #include "mozilla/MruCache.h"
  30 #include "mozilla/StaticPtr.h"
  31
  32 #include "PLDHashTable.h"
  33 #include "nsTHashtable.h"
  34
  35 #ifdef DEBUG_CONTENT_LIST
  36 #  define ASSERT_IN_SYNC AssertInSync()
  37 #else
  38 #  define ASSERT_IN_SYNC PR_BEGIN_MACRO PR_END_MACRO
  39 #endif
  40
  41 using namespace mozilla;
  42 using namespace mozilla::dom;
  43
  44 nsBaseContentList::~nsBaseContentList() = default;
  45
  46 NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE_CLASS(nsBaseContentList)
  47 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(nsBaseContentList)
  48   NS_IMPL_CYCLE_COLLECTION_UNLINK(mElements)
  49   NS_IMPL_CYCLE_COLLECTION_UNLINK_PRESERVED_WRAPPER
  50   tmp->RemoveFromCaches();
  51 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
  52 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(nsBaseContentList)
  53   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mElements)
  54 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
  55
  56 NS_IMPL_CYCLE_COLLECTION_CAN_SKIP_BEGIN(nsBaseContentList)
  57   if (nsCCUncollectableMarker::sGeneration && tmp->HasKnownLiveWrapper()) {
  58     for (uint32_t i = 0; i < tmp->mElements.Length(); ++i) {
  59       nsIContent* c = tmp->mElements[i];
  60       if (c->IsPurple()) {
  61         c->RemovePurple();
  62       }
  63       Element::MarkNodeChildren(c);
  64     }
  65     return true;
  66   }
  67 NS_IMPL_CYCLE_COLLECTION_CAN_SKIP_END
  68
  69 NS_IMPL_CYCLE_COLLECTION_CAN_SKIP_IN_CC_BEGIN(nsBaseContentList)
  70   return nsCCUncollectableMarker::sGeneration && tmp->HasKnownLiveWrapper();
  71 NS_IMPL_CYCLE_COLLECTION_CAN_SKIP_IN_CC_END
  72
  73 NS_IMPL_CYCLE_COLLECTION_CAN_SKIP_THIS_BEGIN(nsBaseContentList)
  74   return nsCCUncollectableMarker::sGeneration && tmp->HasKnownLiveWrapper();
  75 NS_IMPL_CYCLE_COLLECTION_CAN_SKIP_THIS_END
  76
  77 // QueryInterface implementation for nsBaseContentList
  78 NS_INTERFACE_TABLE_HEAD(nsBaseContentList)
  79   NS_WRAPPERCACHE_INTERFACE_TABLE_ENTRY
  80   NS_INTERFACE_TABLE(nsBaseContentList, nsINodeList)
  81   NS_INTERFACE_TABLE_TO_MAP_SEGUE_CYCLE_COLLECTION(nsBaseContentList)
  82 NS_INTERFACE_MAP_END
  83
  84 NS_IMPL_CYCLE_COLLECTING_ADDREF(nsBaseContentList)
  85 NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsBaseContentList,
  86                                                    LastRelease())
  87
  88 nsIContent* nsBaseContentList::Item(uint32_t aIndex) {
  89   return mElements.SafeElementAt(aIndex);
  90 }
  91
  92 int32_t nsBaseContentList::IndexOf(nsIContent* aContent, bool aDoFlush) {
  93   return mElements.IndexOf(aContent);
  94 }
  95
  96 int32_t nsBaseContentList::IndexOf(nsIContent* aContent) {
  97   return IndexOf(aContent, true);
  98 }
  99
 100 size_t nsBaseContentList::SizeOfIncludingThis(
 101     MallocSizeOf aMallocSizeOf) const {
 102   size_t n = aMallocSizeOf(this);
 103   n += mElements.ShallowSizeOfExcludingThis(aMallocSizeOf);
 104   return n;
 105 }
 106
 107 NS_IMPL_CYCLE_COLLECTION_INHERITED(nsSimpleContentList, nsBaseContentList,
 108                                    mRoot)
 109
 110 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsSimpleContentList)
 111 NS_INTERFACE_MAP_END_INHERITING(nsBaseContentList)
 112
 113 NS_IMPL_ADDREF_INHERITED(nsSimpleContentList, nsBaseContentList)
 114 NS_IMPL_RELEASE_INHERITED(nsSimpleContentList, nsBaseContentList)
 115
 116 JSObject* nsSimpleContentList::WrapObject(JSContext* cx,
 117                                           JS::Handle<JSObject*> aGivenProto) {
 118   return NodeList_Binding::Wrap(cx, this, aGivenProto);
 119 }
 120
 121 NS_IMPL_CYCLE_COLLECTION_INHERITED(nsEmptyContentList, nsBaseContentList, mRoot)
 122
 123 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsEmptyContentList)
 124   NS_INTERFACE_MAP_ENTRY(nsIHTMLCollection)
 125 NS_INTERFACE_MAP_END_INHERITING(nsBaseContentList)
 126
 127 NS_IMPL_ADDREF_INHERITED(nsEmptyContentList, nsBaseContentList)
 128 NS_IMPL_RELEASE_INHERITED(nsEmptyContentList, nsBaseContentList)
 129
 130 JSObject* nsEmptyContentList::WrapObject(JSContext* cx,
 131                                          JS::Handle<JSObject*> aGivenProto) {
 132   return HTMLCollection_Binding::Wrap(cx, this, aGivenProto);
 133 }
 134
 135 mozilla::dom::Element* nsEmptyContentList::GetElementAt(uint32_t index) {
 136   return nullptr;
 137 }
 138
 139 mozilla::dom::Element* nsEmptyContentList::GetFirstNamedElement(
 140     const nsAString& aName, bool& aFound) {
 141   aFound = false;
 142   return nullptr;
 143 }
 144
 145 void nsEmptyContentList::GetSupportedNames(nsTArray<nsString>& aNames) {}
 146
 147 nsIContent* nsEmptyContentList::Item(uint32_t aIndex) { return nullptr; }
 148
 149 struct ContentListCache
 150     : public MruCache<nsContentListKey, nsContentList*, ContentListCache> {
 151   static HashNumber Hash(const nsContentListKey& aKey) {
 152     return aKey.GetHash();
 153   }
 154   static bool Match(const nsContentListKey& aKey, const nsContentList* aVal) {
 155     return aVal->MatchesKey(aKey);
 156   }
 157 };
 158
 159 static ContentListCache sRecentlyUsedContentLists;
 160
 161 class nsContentList::HashEntry : public PLDHashEntryHdr {
 162  public:
 163   using KeyType = const nsContentListKey*;
 164   using KeyTypePointer = KeyType;
 165
 166   // Note that this is creating a blank entry, so you'll have to manually
 167   // initialize it after it has been inserted into the hash table.
 168   explicit HashEntry(KeyTypePointer aKey) : mContentList(nullptr) {}
 169
 170   HashEntry(HashEntry&& aEnt) : mContentList(std::move(aEnt.mContentList)) {}
 171
 172   ~HashEntry() {
 173     if (mContentList) {
 174       MOZ_RELEASE_ASSERT(mContentList->mInHashtable);
 175       mContentList->mInHashtable = false;
 176     }
 177   }
 178
 179   bool KeyEquals(KeyTypePointer aKey) const {
 180     return mContentList->MatchesKey(*aKey);
 181   }
 182
 183   static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; }
 184
 185   static PLDHashNumber HashKey(KeyTypePointer aKey) { return aKey->GetHash(); }
 186
 187   nsContentList* GetContentList() const { return mContentList; }
 188   void SetContentList(nsContentList* aContentList) {
 189     MOZ_RELEASE_ASSERT(!mContentList);
 190     MOZ_ASSERT(aContentList);
 191     MOZ_RELEASE_ASSERT(!aContentList->mInHashtable);
 192     mContentList = aContentList;
 193     mContentList->mInHashtable = true;
 194   }
 195
 196   enum { ALLOW_MEMMOVE = true };
 197
 198  private:
 199   nsContentList* MOZ_UNSAFE_REF(
 200       "This entry will be removed in nsContentList::RemoveFromHashtable "
 201       "before mContentList is destroyed") mContentList;
 202 };
 203
 204 // Hashtable for storing nsContentLists
 205 static StaticAutoPtr<nsTHashtable<nsContentList::HashEntry>>
 206     gContentListHashTable;
 207
 208 already_AddRefed<nsContentList> NS_GetContentList(nsINode* aRootNode,
 209                                                   int32_t aMatchNameSpaceId,
 210                                                   const nsAString& aTagname) {
 211   NS_ASSERTION(aRootNode, "content list has to have a root");
 212
 213   RefPtr<nsContentList> list;
 214   nsContentListKey hashKey(aRootNode, aMatchNameSpaceId, aTagname,
 215                            aRootNode->OwnerDoc()->IsHTMLDocument());
 216   auto p = sRecentlyUsedContentLists.Lookup(hashKey);
 217   if (p) {
 218     list = p.Data();
 219     return list.forget();
 220   }
 221
 222   // Initialize the hashtable if needed.
 223   if (!gContentListHashTable) {
 224     gContentListHashTable = new nsTHashtable<nsContentList::HashEntry>();
 225   }
 226
 227   // First we look in our hashtable.  Then we create a content list if needed
 228   auto entry = gContentListHashTable->PutEntry(&hashKey, fallible);
 229   if (entry) {
 230     list = entry->GetContentList();
 231   }
 232
 233   if (!list) {
 234     // We need to create a ContentList and add it to our new entry, if
 235     // we have an entry
 236     RefPtr<nsAtom> xmlAtom = NS_Atomize(aTagname);
 237     RefPtr<nsAtom> htmlAtom;
 238     if (aMatchNameSpaceId == kNameSpaceID_Unknown) {
 239       nsAutoString lowercaseName;
 240       nsContentUtils::ASCIIToLower(aTagname, lowercaseName);
 241       htmlAtom = NS_Atomize(lowercaseName);
 242     } else {
 243       htmlAtom = xmlAtom;
 244     }
 245     list = new nsContentList(aRootNode, aMatchNameSpaceId, htmlAtom, xmlAtom);
 246     if (entry) {
 247       entry->SetContentList(list);
 248     }
 249   }
 250
 251   p.Set(list);
 252   return list.forget();
 253 }
 254
 255 #ifdef DEBUG
 256 const nsCacheableFuncStringContentList::ContentListType
 257     nsCachableElementsByNameNodeList::sType =
 258         nsCacheableFuncStringContentList::eNodeList;
 259 const nsCacheableFuncStringContentList::ContentListType
 260     nsCacheableFuncStringHTMLCollection::sType =
 261         nsCacheableFuncStringContentList::eHTMLCollection;
 262 #endif
 263
 264 class nsCacheableFuncStringContentList::HashEntry : public PLDHashEntryHdr {
 265  public:
 266   using KeyType = const nsFuncStringCacheKey*;
 267   using KeyTypePointer = KeyType;
 268
 269   // Note that this is creating a blank entry, so you'll have to manually
 270   // initialize it after it has been inserted into the hash table.
 271   explicit HashEntry(KeyTypePointer aKey) : mContentList(nullptr) {}
 272
 273   HashEntry(HashEntry&& aEnt) : mContentList(std::move(aEnt.mContentList)) {}
 274
 275   ~HashEntry() {
 276     if (mContentList) {
 277       MOZ_RELEASE_ASSERT(mContentList->mInHashtable);
 278       mContentList->mInHashtable = false;
 279     }
 280   }
 281
 282   bool KeyEquals(KeyTypePointer aKey) const {
 283     return mContentList->Equals(aKey);
 284   }
 285
 286   static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; }
 287
 288   static PLDHashNumber HashKey(KeyTypePointer aKey) { return aKey->GetHash(); }
 289
 290   nsCacheableFuncStringContentList* GetContentList() const {
 291     return mContentList;
 292   }
 293   void SetContentList(nsCacheableFuncStringContentList* aContentList) {
 294     MOZ_RELEASE_ASSERT(!mContentList);
 295     MOZ_ASSERT(aContentList);
 296     MOZ_RELEASE_ASSERT(!aContentList->mInHashtable);
 297     mContentList = aContentList;
 298     mContentList->mInHashtable = true;
 299   }
 300
 301   enum { ALLOW_MEMMOVE = true };
 302
 303  private:
 304   nsCacheableFuncStringContentList* MOZ_UNSAFE_REF(
 305       "This entry will be removed in "
 306       "nsCacheableFuncStringContentList::RemoveFromFuncStringHashtable "
 307       "before mContentList is destroyed") mContentList;
 308 };
 309
 310 // Hashtable for storing nsCacheableFuncStringContentList
 311 static StaticAutoPtr<nsTHashtable<nsCacheableFuncStringContentList::HashEntry>>
 312     gFuncStringContentListHashTable;
 313
 314 template <class ListType>
 315 already_AddRefed<nsContentList> GetFuncStringContentList(
 316     nsINode* aRootNode, nsContentListMatchFunc aFunc,
 317     nsContentListDestroyFunc aDestroyFunc,
 318     nsFuncStringContentListDataAllocator aDataAllocator,
 319     const nsAString& aString) {
 320   NS_ASSERTION(aRootNode, "content list has to have a root");
 321
 322   RefPtr<nsCacheableFuncStringContentList> list;
 323
 324   // Initialize the hashtable if needed.
 325   if (!gFuncStringContentListHashTable) {
 326     gFuncStringContentListHashTable =
 327         new nsTHashtable<nsCacheableFuncStringContentList::HashEntry>();
 328   }
 329
 330   nsCacheableFuncStringContentList::HashEntry* entry = nullptr;
 331   // First we look in our hashtable.  Then we create a content list if needed
 332   if (gFuncStringContentListHashTable) {
 333     nsFuncStringCacheKey hashKey(aRootNode, aFunc, aString);
 334
 335     entry = gFuncStringContentListHashTable->PutEntry(&hashKey, fallible);
 336     if (entry) {
 337       list = entry->GetContentList();
 338 #ifdef DEBUG
 339       MOZ_ASSERT_IF(list, list->mType == ListType::sType);
 340 #endif
 341     }
 342   }
 343
 344   if (!list) {
 345     // We need to create a ContentList and add it to our new entry, if
 346     // we have an entry
 347     list =
 348         new ListType(aRootNode, aFunc, aDestroyFunc, aDataAllocator, aString);
 349     if (entry) {
 350       entry->SetContentList(list);
 351     }
 352   }
 353
 354   // Don't cache these lists globally
 355
 356   return list.forget();
 357 }
 358
 359 // Explicit instantiations to avoid link errors
 360 template already_AddRefed<nsContentList>
 361 GetFuncStringContentList<nsCachableElementsByNameNodeList>(
 362     nsINode* aRootNode, nsContentListMatchFunc aFunc,
 363     nsContentListDestroyFunc aDestroyFunc,
 364     nsFuncStringContentListDataAllocator aDataAllocator,
 365     const nsAString& aString);
 366 template already_AddRefed<nsContentList>
 367 GetFuncStringContentList<nsCacheableFuncStringHTMLCollection>(
 368     nsINode* aRootNode, nsContentListMatchFunc aFunc,
 369     nsContentListDestroyFunc aDestroyFunc,
 370     nsFuncStringContentListDataAllocator aDataAllocator,
 371     const nsAString& aString);
 372
 373 //-----------------------------------------------------
 374 // nsContentList implementation
 375
 376 nsContentList::nsContentList(nsINode* aRootNode, int32_t aMatchNameSpaceId,
 377                              nsAtom* aHTMLMatchAtom, nsAtom* aXMLMatchAtom,
 378                              bool aDeep, bool aLiveList)
 379     : nsBaseContentList(),
 380       mRootNode(aRootNode),
 381       mMatchNameSpaceId(aMatchNameSpaceId),
 382       mHTMLMatchAtom(aHTMLMatchAtom),
 383       mXMLMatchAtom(aXMLMatchAtom),
 384       mState(State::Dirty),
 385       mDeep(aDeep),
 386       mFuncMayDependOnAttr(false),
 387       mIsHTMLDocument(aRootNode->OwnerDoc()->IsHTMLDocument()),
 388       mNamedItemsCacheValid(false),
 389       mIsLiveList(aLiveList),
 390       mInHashtable(false) {
 391   NS_ASSERTION(mRootNode, "Must have root");
 392   if (nsGkAtoms::_asterisk == mHTMLMatchAtom) {
 393     NS_ASSERTION(mXMLMatchAtom == nsGkAtoms::_asterisk,
 394                  "HTML atom and XML atom are not both asterisk?");
 395     mMatchAll = true;
 396   } else {
 397     mMatchAll = false;
 398   }
 399   // This is aLiveList instead of mIsLiveList to avoid Valgrind errors.
 400   if (aLiveList) {
 401     SetEnabledCallbacks(nsIMutationObserver::kNodeWillBeDestroyed);
 402     mRootNode->AddMutationObserver(this);
 403   }
 404
 405   // We only need to flush if we're in an non-HTML document, since the
 406   // HTML5 parser doesn't need flushing.  Further, if we're not in a
 407   // document at all right now (in the GetUncomposedDoc() sense), we're
 408   // not parser-created and don't need to be flushing stuff under us
 409   // to get our kids right.
 410   Document* doc = mRootNode->GetUncomposedDoc();
 411   mFlushesNeeded = doc && !doc->IsHTMLDocument();
 412 }
 413
 414 nsContentList::nsContentList(nsINode* aRootNode, nsContentListMatchFunc aFunc,
 415                              nsContentListDestroyFunc aDestroyFunc, void* aData,
 416                              bool aDeep, nsAtom* aMatchAtom,
 417                              int32_t aMatchNameSpaceId,
 418                              bool aFuncMayDependOnAttr, bool aLiveList)
 419     : nsBaseContentList(),
 420       mRootNode(aRootNode),
 421       mMatchNameSpaceId(aMatchNameSpaceId),
 422       mHTMLMatchAtom(aMatchAtom),
 423       mXMLMatchAtom(aMatchAtom),
 424       mFunc(aFunc),
 425       mDestroyFunc(aDestroyFunc),
 426       mData(aData),
 427       mState(State::Dirty),
 428       mMatchAll(false),
 429       mDeep(aDeep),
 430       mFuncMayDependOnAttr(aFuncMayDependOnAttr),
 431       mIsHTMLDocument(false),
 432       mNamedItemsCacheValid(false),
 433       mIsLiveList(aLiveList),
 434       mInHashtable(false) {
 435   NS_ASSERTION(mRootNode, "Must have root");
 436   // This is aLiveList instead of mIsLiveList to avoid Valgrind errors.
 437   if (aLiveList) {
 438     SetEnabledCallbacks(nsIMutationObserver::kNodeWillBeDestroyed);
 439     mRootNode->AddMutationObserver(this);
 440   }
 441
 442   // We only need to flush if we're in an non-HTML document, since the
 443   // HTML5 parser doesn't need flushing.  Further, if we're not in a
 444   // document at all right now (in the GetUncomposedDoc() sense), we're
 445   // not parser-created and don't need to be flushing stuff under us
 446   // to get our kids right.
 447   Document* doc = mRootNode->GetUncomposedDoc();
 448   mFlushesNeeded = doc && !doc->IsHTMLDocument();
 449 }
 450
 451 nsContentList::~nsContentList() {
 452   RemoveFromHashtable();
 453   if (mIsLiveList && mRootNode) {
 454     mRootNode->RemoveMutationObserver(this);
 455   }
 456
 457   if (mDestroyFunc) {
 458     // Clean up mData
 459     (*mDestroyFunc)(mData);
 460   }
 461 }
 462
 463 JSObject* nsContentList::WrapObject(JSContext* cx,
 464                                     JS::Handle<JSObject*> aGivenProto) {
 465   return HTMLCollection_Binding::Wrap(cx, this, aGivenProto);
 466 }
 467
 468 NS_IMPL_ISUPPORTS_INHERITED(nsContentList, nsBaseContentList, nsIHTMLCollection,
 469                             nsIMutationObserver)
 470
 471 uint32_t nsContentList::Length(bool aDoFlush) {
 472   BringSelfUpToDate(aDoFlush);
 473
 474   return mElements.Length();
 475 }
 476
 477 nsIContent* nsContentList::Item(uint32_t aIndex, bool aDoFlush) {
 478   if (mRootNode && aDoFlush && mFlushesNeeded) {
 479     // XXX sXBL/XBL2 issue
 480     Document* doc = mRootNode->GetUncomposedDoc();
 481     if (doc) {
 482       // Flush pending content changes Bug 4891.
 483       doc->FlushPendingNotifications(FlushType::ContentAndNotify);
 484     }
 485   }
 486
 487   if (mState != State::UpToDate) {
 488     PopulateSelf(std::min(aIndex, UINT32_MAX - 1) + 1);
 489   }
 490
 491   ASSERT_IN_SYNC;
 492   NS_ASSERTION(!mRootNode || mState != State::Dirty,
 493                "PopulateSelf left the list in a dirty (useless) state!");
 494
 495   return mElements.SafeElementAt(aIndex);
 496 }
 497
 498 inline void nsContentList::InsertElementInNamedItemsCache(
 499     nsIContent& aContent) {
 500   const bool hasName = aContent.HasName();
 501   const bool hasId = aContent.HasID();
 502   if (!hasName && !hasId) {
 503     return;
 504   }
 505
 506   Element* el = aContent.AsElement();
 507   MOZ_ASSERT_IF(hasName, el->IsHTMLElement());
 508
 509   uint32_t i = 0;
 510   while (BorrowedAttrInfo info = el->GetAttrInfoAt(i++)) {
 511     const bool valid = (info.mName->Equals(nsGkAtoms::name) && hasName) ||
 512                        (info.mName->Equals(nsGkAtoms::id) && hasId);
 513     if (!valid) {
 514       continue;
 515     }
 516
 517     if (!mNamedItemsCache) {
 518       mNamedItemsCache = MakeUnique<NamedItemsCache>();
 519     }
 520
 521     nsAtom* name = info.mValue->GetAtomValue();
 522     // NOTE: LookupOrInsert makes sure we keep the first element we find for a
 523     // given name.
 524     mNamedItemsCache->LookupOrInsert(name, el);
 525   }
 526 }
 527
 528 inline void nsContentList::InvalidateNamedItemsCacheForAttributeChange(
 529     int32_t aNamespaceID, nsAtom* aAttribute) {
 530   if (!mNamedItemsCacheValid) {
 531     return;
 532   }
 533   if ((aAttribute == nsGkAtoms::id || aAttribute == nsGkAtoms::name) &&
 534       aNamespaceID == kNameSpaceID_None) {
 535     InvalidateNamedItemsCache();
 536   }
 537 }
 538
 539 inline void nsContentList::InvalidateNamedItemsCacheForInsertion(
 540     Element& aElement) {
 541   if (!mNamedItemsCacheValid) {
 542     return;
 543   }
 544
 545   InsertElementInNamedItemsCache(aElement);
 546 }
 547
 548 inline void nsContentList::InvalidateNamedItemsCacheForDeletion(
 549     Element& aElement) {
 550   if (!mNamedItemsCacheValid) {
 551     return;
 552   }
 553   if (aElement.HasName() || aElement.HasID()) {
 554     InvalidateNamedItemsCache();
 555   }
 556 }
 557
 558 void nsContentList::EnsureNamedItemsCacheValid(bool aDoFlush) {
 559   BringSelfUpToDate(aDoFlush);
 560
 561   if (mNamedItemsCacheValid) {
 562     return;
 563   }
 564
 565   MOZ_ASSERT(!mNamedItemsCache);
 566
 567   // https://dom.spec.whatwg.org/#dom-htmlcollection-nameditem-key
 568   // XXX: Blink/WebKit don't follow the spec here, and searches first-by-id,
 569   // then by name.
 570   for (const nsCOMPtr<nsIContent>& content : mElements) {
 571     InsertElementInNamedItemsCache(*content);
 572   }
 573
 574   mNamedItemsCacheValid = true;
 575 }
 576
 577 Element* nsContentList::NamedItem(const nsAString& aName, bool aDoFlush) {
 578   if (aName.IsEmpty()) {
 579     return nullptr;
 580   }
 581
 582   EnsureNamedItemsCacheValid(aDoFlush);
 583
 584   if (!mNamedItemsCache) {
 585     return nullptr;
 586   }
 587
 588   // Typically IDs and names are atomized
 589   RefPtr<nsAtom> name = NS_Atomize(aName);
 590   NS_ENSURE_TRUE(name, nullptr);
 591
 592   return mNamedItemsCache->Get(name);
 593 }
 594
 595 void nsContentList::GetSupportedNames(nsTArray<nsString>& aNames) {
 596   BringSelfUpToDate(true);
 597
 598   AutoTArray<nsAtom*, 8> atoms;
 599   for (uint32_t i = 0; i < mElements.Length(); ++i) {
 600     nsIContent* content = mElements.ElementAt(i);
 601     if (content->HasID()) {
 602       nsAtom* id = content->GetID();
 603       MOZ_ASSERT(id != nsGkAtoms::_empty, "Empty ids don't get atomized");
 604       if (!atoms.Contains(id)) {
 605         atoms.AppendElement(id);
 606       }
 607     }
 608
 609     nsGenericHTMLElement* el = nsGenericHTMLElement::FromNode(content);
 610     if (el) {
 611       // XXXbz should we be checking for particular tags here?  How
 612       // stable is this part of the spec?
 613       // Note: nsINode::HasName means the name is exposed on the document,
 614       // which is false for options, so we don't check it here.
 615       const nsAttrValue* val = el->GetParsedAttr(nsGkAtoms::name);
 616       if (val && val->Type() == nsAttrValue::eAtom) {
 617         nsAtom* name = val->GetAtomValue();
 618         MOZ_ASSERT(name != nsGkAtoms::_empty, "Empty names don't get atomized");
 619         if (!atoms.Contains(name)) {
 620           atoms.AppendElement(name);
 621         }
 622       }
 623     }
 624   }
 625
 626   uint32_t atomsLen = atoms.Length();
 627   nsString* names = aNames.AppendElements(atomsLen);
 628   for (uint32_t i = 0; i < atomsLen; ++i) {
 629     atoms[i]->ToString(names[i]);
 630   }
 631 }
 632
 633 int32_t nsContentList::IndexOf(nsIContent* aContent, bool aDoFlush) {
 634   BringSelfUpToDate(aDoFlush);
 635
 636   return mElements.IndexOf(aContent);
 637 }
 638
 639 int32_t nsContentList::IndexOf(nsIContent* aContent) {
 640   return IndexOf(aContent, true);
 641 }
 642
 643 void nsContentList::NodeWillBeDestroyed(nsINode* aNode) {
 644   // We shouldn't do anything useful from now on
 645
 646   RemoveFromCaches();
 647   mRootNode = nullptr;
 648
 649   // We will get no more updates, so we can never know we're up to
 650   // date
 651   SetDirty();
 652 }
 653
 654 void nsContentList::LastRelease() {
 655   RemoveFromCaches();
 656   if (mIsLiveList && mRootNode) {
 657     mRootNode->RemoveMutationObserver(this);
 658     mRootNode = nullptr;
 659   }
 660   SetDirty();
 661 }
 662
 663 Element* nsContentList::GetElementAt(uint32_t aIndex) {
 664   return static_cast<Element*>(Item(aIndex, true));
 665 }
 666
 667 nsIContent* nsContentList::Item(uint32_t aIndex) {
 668   return GetElementAt(aIndex);
 669 }
 670
 671 void nsContentList::AttributeChanged(Element* aElement, int32_t aNameSpaceID,
 672                                      nsAtom* aAttribute, int32_t aModType,
 673                                      const nsAttrValue* aOldValue) {
 674   MOZ_ASSERT(aElement, "Must have a content node to work with");
 675
 676   if (mState == State::Dirty ||
 677       !MayContainRelevantNodes(aElement->GetParentNode()) ||
 678       !nsContentUtils::IsInSameAnonymousTree(mRootNode, aElement)) {
 679     // Either we're already dirty or aElement will never match us.
 680     return;
 681   }
 682
 683   InvalidateNamedItemsCacheForAttributeChange(aNameSpaceID, aAttribute);
 684
 685   if (!mFunc || !mFuncMayDependOnAttr) {
 686     // aElement might be relevant but the attribute change doesn't affect
 687     // whether we match it.
 688     return;
 689   }
 690
 691   if (Match(aElement)) {
 692     if (mElements.IndexOf(aElement) == mElements.NoIndex) {
 693       // We match aElement now, and it's not in our list already.  Just dirty
 694       // ourselves; this is simpler than trying to figure out where to insert
 695       // aElement.
 696       SetDirty();
 697     }
 698   } else {
 699     // We no longer match aElement.  Remove it from our list.  If it's
 700     // already not there, this is a no-op (though a potentially
 701     // expensive one).  Either way, no change of mState is required
 702     // here.
 703     if (mElements.RemoveElement(aElement)) {
 704       InvalidateNamedItemsCacheForDeletion(*aElement);
 705     }
 706   }
 707 }
 708
 709 void nsContentList::ContentAppended(nsIContent* aFirstNewContent) {
 710   nsIContent* container = aFirstNewContent->GetParent();
 711   MOZ_ASSERT(container, "Can't get at the new content if no container!");
 712
 713   /*
 714    * If the state is State::Dirty then we have no useful information in our list
 715    * and we want to put off doing work as much as possible.
 716    *
 717    * Also, if container is anonymous from our point of view, we know that we
 718    * can't possibly be matching any of the kids.
 719    *
 720    * Optimize out also the common case when just one new node is appended and
 721    * it doesn't match us.
 722    */
 723   if (mState == State::Dirty ||
 724       !nsContentUtils::IsInSameAnonymousTree(mRootNode, container) ||
 725       !MayContainRelevantNodes(container) ||
 726       (!aFirstNewContent->HasChildren() &&
 727        !aFirstNewContent->GetNextSibling() && !MatchSelf(aFirstNewContent))) {
 728     MaybeMarkDirty();
 729     return;
 730   }
 731
 732   /*
 733    * We want to handle the case of ContentAppended by sometimes
 734    * appending the content to our list, not just setting state to
 735    * State::Dirty, since most of our ContentAppended notifications
 736    * should come during pageload and be at the end of the document.
 737    * Do a bit of work to see whether we could just append to what we
 738    * already have.
 739    */
 740
 741   uint32_t ourCount = mElements.Length();
 742   const bool appendingToList = [&] {
 743     if (ourCount == 0) {
 744       return true;
 745     }
 746     if (mRootNode == container) {
 747       return true;
 748     }
 749     return nsContentUtils::PositionIsBefore(mElements.LastElement(),
 750                                             aFirstNewContent);
 751   }();
 752
 753   if (!appendingToList) {
 754     // The new stuff is somewhere in the middle of our list; check
 755     // whether we need to invalidate
 756     for (nsIContent* cur = aFirstNewContent; cur; cur = cur->GetNextSibling()) {
 757       if (MatchSelf(cur)) {
 758         // Uh-oh.  We're gonna have to add elements into the middle
 759         // of our list. That's not worth the effort.
 760         SetDirty();
 761         break;
 762       }
 763     }
 764
 765     ASSERT_IN_SYNC;
 766     return;
 767   }
 768
 769   /*
 770    * At this point we know we could append.  If we're not up to
 771    * date, however, that would be a bad idea -- it could miss some
 772    * content that we never picked up due to being lazy.  Further, we
 773    * may never get asked for this content... so don't grab it yet.
 774    */
 775   if (mState == State::Lazy) {
 776     return;
 777   }
 778
 779   /*
 780    * We're up to date.  That means someone's actively using us; we
 781    * may as well grab this content....
 782    */
 783   if (mDeep) {
 784     for (nsIContent* cur = aFirstNewContent; cur;
 785          cur = cur->GetNextNode(container)) {
 786       if (cur->IsElement() && Match(cur->AsElement())) {
 787         mElements.AppendElement(cur);
 788         InvalidateNamedItemsCacheForInsertion(*cur->AsElement());
 789       }
 790     }
 791   } else {
 792     for (nsIContent* cur = aFirstNewContent; cur; cur = cur->GetNextSibling()) {
 793       if (cur->IsElement() && Match(cur->AsElement())) {
 794         mElements.AppendElement(cur);
 795         InvalidateNamedItemsCacheForInsertion(*cur->AsElement());
 796       }
 797     }
 798   }
 799
 800   ASSERT_IN_SYNC;
 801 }
 802
 803 void nsContentList::ContentInserted(nsIContent* aChild) {
 804   // Note that aChild->GetParentNode() can be null here if we are inserting into
 805   // the document itself; any attempted optimizations to this method should deal
 806   // with that.
 807   if (mState != State::Dirty &&
 808       MayContainRelevantNodes(aChild->GetParentNode()) &&
 809       nsContentUtils::IsInSameAnonymousTree(mRootNode, aChild) &&
 810       MatchSelf(aChild)) {
 811     SetDirty();
 812   }
 813
 814   ASSERT_IN_SYNC;
 815 }
 816
 817 void nsContentList::ContentRemoved(nsIContent* aChild,
 818                                    nsIContent* aPreviousSibling) {
 819   if (mState != State::Dirty &&
 820       MayContainRelevantNodes(aChild->GetParentNode()) &&
 821       nsContentUtils::IsInSameAnonymousTree(mRootNode, aChild) &&
 822       MatchSelf(aChild)) {
 823     SetDirty();
 824   }
 825
 826   ASSERT_IN_SYNC;
 827 }
 828
 829 bool nsContentList::Match(Element* aElement) {
 830   if (mFunc) {
 831     return (*mFunc)(aElement, mMatchNameSpaceId, mXMLMatchAtom, mData);
 832   }
 833
 834   if (!mXMLMatchAtom) return false;
 835
 836   NodeInfo* ni = aElement->NodeInfo();
 837
 838   bool unknown = mMatchNameSpaceId == kNameSpaceID_Unknown;
 839   bool wildcard = mMatchNameSpaceId == kNameSpaceID_Wildcard;
 840   bool toReturn = mMatchAll;
 841   if (!unknown && !wildcard) toReturn &= ni->NamespaceEquals(mMatchNameSpaceId);
 842
 843   if (toReturn) return toReturn;
 844
 845   bool matchHTML =
 846       mIsHTMLDocument && aElement->GetNameSpaceID() == kNameSpaceID_XHTML;
 847
 848   if (unknown) {
 849     return matchHTML ? ni->QualifiedNameEquals(mHTMLMatchAtom)
 850                      : ni->QualifiedNameEquals(mXMLMatchAtom);
 851   }
 852
 853   if (wildcard) {
 854     return matchHTML ? ni->Equals(mHTMLMatchAtom) : ni->Equals(mXMLMatchAtom);
 855   }
 856
 857   return matchHTML ? ni->Equals(mHTMLMatchAtom, mMatchNameSpaceId)
 858                    : ni->Equals(mXMLMatchAtom, mMatchNameSpaceId);
 859 }
 860
 861 bool nsContentList::MatchSelf(nsIContent* aContent) {
 862   MOZ_ASSERT(aContent, "Can't match null stuff, you know");
 863   MOZ_ASSERT(mDeep || aContent->GetParentNode() == mRootNode,
 864              "MatchSelf called on a node that we can't possibly match");
 865
 866   if (!aContent->IsElement()) {
 867     return false;
 868   }
 869
 870   if (Match(aContent->AsElement())) return true;
 871
 872   if (!mDeep) return false;
 873
 874   for (nsIContent* cur = aContent->GetFirstChild(); cur;
 875        cur = cur->GetNextNode(aContent)) {
 876     if (cur->IsElement() && Match(cur->AsElement())) {
 877       return true;
 878     }
 879   }
 880
 881   return false;
 882 }
 883
 884 void nsContentList::PopulateSelf(uint32_t aNeededLength,
 885                                  uint32_t aExpectedElementsIfDirty) {
 886   if (!mRootNode) {
 887     return;
 888   }
 889
 890   ASSERT_IN_SYNC;
 891
 892   uint32_t count = mElements.Length();
 893   NS_ASSERTION(mState != State::Dirty || count == aExpectedElementsIfDirty,
 894                "Reset() not called when setting state to State::Dirty?");
 895
 896   if (count >= aNeededLength)  // We're all set
 897     return;
 898
 899   uint32_t elementsToAppend = aNeededLength - count;
 900 #ifdef DEBUG
 901   uint32_t invariant = elementsToAppend + mElements.Length();
 902 #endif
 903
 904   if (mDeep) {
 905     // If we already have nodes start searching at the last one, otherwise
 906     // start searching at the root.
 907     nsINode* cur = count ? mElements[count - 1].get() : mRootNode;
 908     do {
 909       cur = cur->GetNextNode(mRootNode);
 910       if (!cur) {
 911         break;
 912       }
 913       if (cur->IsElement() && Match(cur->AsElement())) {
 914         // Append AsElement() to get nsIContent instead of nsINode
 915         mElements.AppendElement(cur->AsElement());
 916         --elementsToAppend;
 917       }
 918     } while (elementsToAppend);
 919   } else {
 920     nsIContent* cur = count ? mElements[count - 1]->GetNextSibling()
 921                             : mRootNode->GetFirstChild();
 922     for (; cur && elementsToAppend; cur = cur->GetNextSibling()) {
 923       if (cur->IsElement() && Match(cur->AsElement())) {
 924         mElements.AppendElement(cur);
 925         --elementsToAppend;
 926       }
 927     }
 928   }
 929
 930   NS_ASSERTION(elementsToAppend + mElements.Length() == invariant,
 931                "Something is awry!");
 932
 933   if (elementsToAppend != 0) {
 934     mState = State::UpToDate;
 935   } else {
 936     mState = State::Lazy;
 937   }
 938
 939   SetEnabledCallbacks(nsIMutationObserver::kAll);
 940
 941   ASSERT_IN_SYNC;
 942 }
 943
 944 void nsContentList::RemoveFromHashtable() {
 945   if (mFunc) {
 946     // nsCacheableFuncStringContentList can be in a hash table without being
 947     // in gContentListHashTable, but it will have been removed from the hash
 948     // table in its dtor before it runs the nsContentList dtor.
 949     MOZ_RELEASE_ASSERT(!mInHashtable);
 950
 951     // This can't be in gContentListHashTable.
 952     return;
 953   }
 954
 955   nsDependentAtomString str(mXMLMatchAtom);
 956   nsContentListKey key(mRootNode, mMatchNameSpaceId, str, mIsHTMLDocument);
 957   sRecentlyUsedContentLists.Remove(key);
 958
 959   if (gContentListHashTable) {
 960     gContentListHashTable->RemoveEntry(&key);
 961
 962     if (gContentListHashTable->Count() == 0) {
 963       gContentListHashTable = nullptr;
 964     }
 965   }
 966
 967   MOZ_RELEASE_ASSERT(!mInHashtable);
 968 }
 969
 970 void nsContentList::BringSelfUpToDate(bool aDoFlush) {
 971   if (mFlushesNeeded && mRootNode && aDoFlush) {
 972     // XXX sXBL/XBL2 issue
 973     if (Document* doc = mRootNode->GetUncomposedDoc()) {
 974       // Flush pending content changes Bug 4891.
 975       doc->FlushPendingNotifications(FlushType::ContentAndNotify);
 976     }
 977   }
 978
 979   if (mState != State::UpToDate) {
 980     PopulateSelf(uint32_t(-1));
 981   }
 982
 983   mMissedUpdates = 0;
 984
 985   ASSERT_IN_SYNC;
 986   NS_ASSERTION(!mRootNode || mState == State::UpToDate,
 987                "PopulateSelf dod not bring content list up to date!");
 988 }
 989
 990 nsCacheableFuncStringContentList::~nsCacheableFuncStringContentList() {
 991   RemoveFromFuncStringHashtable();
 992 }
 993
 994 void nsCacheableFuncStringContentList::RemoveFromFuncStringHashtable() {
 995   if (!gFuncStringContentListHashTable) {
 996     MOZ_RELEASE_ASSERT(!mInHashtable);
 997     return;
 998   }
 999
1000   nsFuncStringCacheKey key(mRootNode, mFunc, mString);
1001   gFuncStringContentListHashTable->RemoveEntry(&key);
1002
1003   if (gFuncStringContentListHashTable->Count() == 0) {
1004     gFuncStringContentListHashTable = nullptr;
1005   }
1006
1007   MOZ_RELEASE_ASSERT(!mInHashtable);
1008 }
1009
1010 #ifdef DEBUG_CONTENT_LIST
1011 void nsContentList::AssertInSync() {
1012   if (mState == State::Dirty) {
1013     return;
1014   }
1015
1016   if (!mRootNode) {
1017     NS_ASSERTION(mElements.Length() == 0 && mState == State::Dirty,
1018                  "Empty iterator isn't quite empty?");
1019     return;
1020   }
1021
1022   // XXX This code will need to change if nsContentLists can ever match
1023   // elements that are outside of the document element.
1024   nsIContent* root = mRootNode->IsDocument()
1025                          ? mRootNode->AsDocument()->GetRootElement()
1026                          : mRootNode->AsContent();
1027
1028   PreContentIterator preOrderIter;
1029   if (mDeep) {
1030     preOrderIter.Init(root);
1031     preOrderIter.First();
1032   }
1033
1034   uint32_t cnt = 0, index = 0;
1035   while (true) {
1036     if (cnt == mElements.Length() && mState == State::Lazy) {
1037       break;
1038     }
1039
1040     nsIContent* cur =
1041         mDeep ? preOrderIter.GetCurrentNode() : mRootNode->GetChildAt(index++);
1042     if (!cur) {
1043       break;
1044     }
1045
1046     if (cur->IsElement() && Match(cur->AsElement())) {
1047       NS_ASSERTION(cnt < mElements.Length() && mElements[cnt] == cur,
1048                    "Elements is out of sync");
1049       ++cnt;
1050     }
1051
1052     if (mDeep) {
1053       preOrderIter.Next();
1054     }
1055   }
1056
1057   NS_ASSERTION(cnt == mElements.Length(), "Too few elements");
1058 }
1059 #endif
1060
1061 //-----------------------------------------------------
1062 // nsCachableElementsByNameNodeList
1063
1064 JSObject* nsCachableElementsByNameNodeList::WrapObject(
1065     JSContext* cx, JS::Handle<JSObject*> aGivenProto) {
1066   return NodeList_Binding::Wrap(cx, this, aGivenProto);
1067 }
1068
1069 void nsCachableElementsByNameNodeList::AttributeChanged(
1070     Element* aElement, int32_t aNameSpaceID, nsAtom* aAttribute,
1071     int32_t aModType, const nsAttrValue* aOldValue) {
1072   // No need to rebuild the list if the changed attribute is not the name
1073   // attribute.
1074   if (aAttribute != nsGkAtoms::name) {
1075     InvalidateNamedItemsCacheForAttributeChange(aNameSpaceID, aAttribute);
1076     return;
1077   }
1078
1079   nsCacheableFuncStringContentList::AttributeChanged(
1080       aElement, aNameSpaceID, aAttribute, aModType, aOldValue);
1081 }
1082
1083 //-----------------------------------------------------
1084 // nsCacheableFuncStringHTMLCollection
1085
1086 JSObject* nsCacheableFuncStringHTMLCollection::WrapObject(
1087     JSContext* cx, JS::Handle<JSObject*> aGivenProto) {
1088   return HTMLCollection_Binding::Wrap(cx, this, aGivenProto);
1089 }
1090
1091 //-----------------------------------------------------
1092 // nsLabelsNodeList
1093
1094 JSObject* nsLabelsNodeList::WrapObject(JSContext* cx,
1095                                        JS::Handle<JSObject*> aGivenProto) {
1096   return NodeList_Binding::Wrap(cx, this, aGivenProto);
1097 }
1098
1099 void nsLabelsNodeList::AttributeChanged(Element* aElement, int32_t aNameSpaceID,
1100                                         nsAtom* aAttribute, int32_t aModType,
1101                                         const nsAttrValue* aOldValue) {
1102   MOZ_ASSERT(aElement, "Must have a content node to work with");
1103   if (mState == State::Dirty ||
1104       !nsContentUtils::IsInSameAnonymousTree(mRootNode, aElement)) {
1105     return;
1106   }
1107
1108   InvalidateNamedItemsCacheForAttributeChange(aNameSpaceID, aAttribute);
1109
1110   // We need to handle input type changes to or from "hidden".
1111   if (aElement->IsHTMLElement(nsGkAtoms::input) &&
1112       aAttribute == nsGkAtoms::type && aNameSpaceID == kNameSpaceID_None) {
1113     SetDirty();
1114     return;
1115   }
1116 }
1117
1118 void nsLabelsNodeList::ContentAppended(nsIContent* aFirstNewContent) {
1119   nsIContent* container = aFirstNewContent->GetParent();
1120   // If a labelable element is moved to outside or inside of
1121   // nested associated labels, we're gonna have to modify
1122   // the content list.
1123   if (mState != State::Dirty ||
1124       nsContentUtils::IsInSameAnonymousTree(mRootNode, container)) {
1125     SetDirty();
1126     return;
1127   }
1128 }
1129
1130 void nsLabelsNodeList::ContentInserted(nsIContent* aChild) {
1131   // If a labelable element is moved to outside or inside of
1132   // nested associated labels, we're gonna have to modify
1133   // the content list.
1134   if (mState != State::Dirty ||
1135       nsContentUtils::IsInSameAnonymousTree(mRootNode, aChild)) {
1136     SetDirty();
1137     return;
1138   }
1139 }
1140
1141 void nsLabelsNodeList::ContentRemoved(nsIContent* aChild,
1142                                       nsIContent* aPreviousSibling) {
1143   // If a labelable element is removed, we're gonna have to clean
1144   // the content list.
1145   if (mState != State::Dirty ||
1146       nsContentUtils::IsInSameAnonymousTree(mRootNode, aChild)) {
1147     SetDirty();
1148     return;
1149   }
1150 }
1151
1152 void nsLabelsNodeList::MaybeResetRoot(nsINode* aRootNode) {
1153   MOZ_ASSERT(aRootNode, "Must have root");
1154   if (mRootNode == aRootNode) {
1155     return;
1156   }
1157
1158   MOZ_ASSERT(mIsLiveList, "nsLabelsNodeList is always a live list");
1159   if (mRootNode) {
1160     mRootNode->RemoveMutationObserver(this);
1161   }
1162   mRootNode = aRootNode;
1163   mRootNode->AddMutationObserver(this);
1164   SetDirty();
1165 }
1166
1167 void nsLabelsNodeList::PopulateSelf(uint32_t aNeededLength,
1168                                     uint32_t aExpectedElementsIfDirty) {
1169   if (!mRootNode) {
1170     return;
1171   }
1172
1173   // Start searching at the root.
1174   nsINode* cur = mRootNode;
1175   if (mElements.IsEmpty() && cur->IsElement() && Match(cur->AsElement())) {
1176     mElements.AppendElement(cur->AsElement());
1177     ++aExpectedElementsIfDirty;
1178   }
1179
1180   nsContentList::PopulateSelf(aNeededLength, aExpectedElementsIfDirty);
1181 }