dom/base/nsContentList.cpp

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