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