dom/base/nsINode.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  * Base class for all DOM nodes.
   9  */
  10
  11 #include "nsINode.h"
  12
  13 #include "AccessCheck.h"
  14 #include "jsapi.h"
  15 #include "js/ForOfIterator.h"  // JS::ForOfIterator
  16 #include "js/JSON.h"           // JS_ParseJSON
  17 #include "mozAutoDocUpdate.h"
  18 #include "mozilla/AsyncEventDispatcher.h"
  19 #include "mozilla/CORSMode.h"
  20 #include "mozilla/EventDispatcher.h"
  21 #include "mozilla/EventListenerManager.h"
  22 #include "mozilla/HTMLEditor.h"
  23 #include "mozilla/InternalMutationEvent.h"
  24 #include "mozilla/Likely.h"
  25 #include "mozilla/Maybe.h"
  26 #include "mozilla/MemoryReporting.h"
  27 #include "mozilla/PresShell.h"
  28 #include "mozilla/ServoBindings.h"
  29 #include "mozilla/Telemetry.h"
  30 #include "mozilla/TextControlElement.h"
  31 #include "mozilla/TextEditor.h"
  32 #include "mozilla/TimeStamp.h"
  33 #include "mozilla/dom/BindContext.h"
  34 #include "mozilla/dom/CharacterData.h"
  35 #include "mozilla/dom/ChildIterator.h"
  36 #include "mozilla/dom/CustomElementRegistry.h"
  37 #include "mozilla/dom/DebuggerNotificationBinding.h"
  38 #include "mozilla/dom/DocumentType.h"
  39 #include "mozilla/dom/Element.h"
  40 #include "mozilla/dom/Event.h"
  41 #include "mozilla/dom/Exceptions.h"
  42 #include "mozilla/dom/Link.h"
  43 #include "mozilla/dom/HTMLImageElement.h"
  44 #include "mozilla/dom/HTMLMediaElement.h"
  45 #include "mozilla/dom/HTMLTemplateElement.h"
  46 #include "mozilla/dom/MutationObservers.h"
  47 #include "mozilla/dom/Selection.h"
  48 #include "mozilla/dom/ShadowRoot.h"
  49 #include "mozilla/dom/SVGUseElement.h"
  50 #include "mozilla/dom/ScriptSettings.h"
  51 #include "mozilla/dom/L10nOverlays.h"
  52 #include "mozilla/ProfilerLabels.h"
  53 #include "mozilla/StaticPrefs_layout.h"
  54 #include "nsAttrValueOrString.h"
  55 #include "nsCCUncollectableMarker.h"
  56 #include "nsContentCreatorFunctions.h"
  57 #include "nsContentList.h"
  58 #include "nsContentUtils.h"
  59 #include "nsCOMArray.h"
  60 #include "nsCycleCollectionParticipant.h"
  61 #include "mozilla/dom/Attr.h"
  62 #include "nsDOMAttributeMap.h"
  63 #include "nsDOMCID.h"
  64 #include "nsDOMCSSAttrDeclaration.h"
  65 #include "nsError.h"
  66 #include "nsExpirationTracker.h"
  67 #include "nsDOMMutationObserver.h"
  68 #include "nsDOMString.h"
  69 #include "nsDOMTokenList.h"
  70 #include "nsFocusManager.h"
  71 #include "nsFrameSelection.h"
  72 #include "nsGenericHTMLElement.h"
  73 #include "nsGkAtoms.h"
  74 #include "nsIAnonymousContentCreator.h"
  75 #include "nsAtom.h"
  76 #include "nsIContentInlines.h"
  77 #include "mozilla/dom/Document.h"
  78 #include "mozilla/dom/DocumentInlines.h"
  79 #include "nsIFrameInlines.h"
  80 #include "mozilla/dom/NodeInfo.h"
  81 #include "mozilla/dom/NodeInfoInlines.h"
  82 #include "nsIScriptGlobalObject.h"
  83 #include "nsIScrollableFrame.h"
  84 #include "nsView.h"
  85 #include "nsViewManager.h"
  86 #include "nsIWidget.h"
  87 #include "nsLayoutUtils.h"
  88 #include "nsNameSpaceManager.h"
  89 #include "nsNodeInfoManager.h"
  90 #include "nsObjectLoadingContent.h"
  91 #include "nsPIDOMWindow.h"
  92 #include "nsPresContext.h"
  93 #include "nsPrintfCString.h"
  94 #include "nsRange.h"
  95 #include "nsString.h"
  96 #include "nsStyleConsts.h"
  97 #include "nsTextNode.h"
  98 #include "nsUnicharUtils.h"
  99 #include "nsWindowSizes.h"
 100 #include "mozilla/Preferences.h"
 101 #include "xpcpublic.h"
 102 #include "HTMLLegendElement.h"
 103 #include "nsWrapperCacheInlines.h"
 104 #include "WrapperFactory.h"
 105 #include <algorithm>
 106 #include "nsGlobalWindowInner.h"
 107 #include "GeometryUtils.h"
 108 #include "nsIAnimationObserver.h"
 109 #include "nsChildContentList.h"
 110 #include "mozilla/dom/NodeBinding.h"
 111 #include "mozilla/dom/BindingDeclarations.h"
 112 #include "mozilla/dom/AncestorIterator.h"
 113 #include "xpcprivate.h"
 114
 115 #include "XPathGenerator.h"
 116
 117 #ifdef ACCESSIBILITY
 118 #  include "mozilla/dom/AccessibleNode.h"
 119 #endif
 120
 121 using namespace mozilla;
 122 using namespace mozilla::dom;
 123
 124 static bool ShouldUseNACScope(const nsINode* aNode) {
 125   return aNode->IsInNativeAnonymousSubtree();
 126 }
 127
 128 static bool ShouldUseUAWidgetScope(const nsINode* aNode) {
 129   return aNode->HasBeenInUAWidget();
 130 }
 131
 132 void* nsINode::operator new(size_t aSize, nsNodeInfoManager* aManager) {
 133   if (StaticPrefs::dom_arena_allocator_enabled_AtStartup()) {
 134     MOZ_ASSERT(aManager, "nsNodeInfoManager needs to be initialized");
 135     return aManager->Allocate(aSize);
 136   }
 137   return ::operator new(aSize);
 138 }
 139 void nsINode::operator delete(void* aPtr) { free_impl(aPtr); }
 140
 141 bool nsINode::IsInclusiveDescendantOf(const nsINode* aNode) const {
 142   MOZ_ASSERT(aNode, "The node is nullptr.");
 143
 144   if (aNode == this) {
 145     return true;
 146   }
 147
 148   if (!aNode->HasFlag(NODE_MAY_HAVE_ELEMENT_CHILDREN)) {
 149     return GetParentNode() == aNode;
 150   }
 151
 152   for (nsINode* node : Ancestors(*this)) {
 153     if (node == aNode) {
 154       return true;
 155     }
 156   }
 157   return false;
 158 }
 159
 160 bool nsINode::IsInclusiveFlatTreeDescendantOf(const nsINode* aNode) const {
 161   MOZ_ASSERT(aNode, "The node is nullptr.");
 162
 163   for (nsINode* node : InclusiveFlatTreeAncestors(*this)) {
 164     if (node == aNode) {
 165       return true;
 166     }
 167   }
 168   return false;
 169 }
 170
 171 bool nsINode::IsShadowIncludingInclusiveDescendantOf(
 172     const nsINode* aNode) const {
 173   MOZ_ASSERT(aNode, "The node is nullptr.");
 174
 175   if (this->GetComposedDoc() == aNode) {
 176     return true;
 177   }
 178
 179   const nsINode* node = this;
 180   do {
 181     if (node == aNode) {
 182       return true;
 183     }
 184
 185     node = node->GetParentOrShadowHostNode();
 186   } while (node);
 187
 188   return false;
 189 }
 190
 191 nsINode::nsSlots::nsSlots() : mWeakReference(nullptr) {}
 192
 193 nsINode::nsSlots::~nsSlots() {
 194   if (mChildNodes) {
 195     mChildNodes->InvalidateCacheIfAvailable();
 196   }
 197
 198   if (mWeakReference) {
 199     mWeakReference->NoticeNodeDestruction();
 200   }
 201 }
 202
 203 void nsINode::nsSlots::Traverse(nsCycleCollectionTraversalCallback& cb) {
 204   NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(cb, "mSlots->mChildNodes");
 205   cb.NoteXPCOMChild(mChildNodes);
 206 }
 207
 208 void nsINode::nsSlots::Unlink(nsINode&) {
 209   if (mChildNodes) {
 210     mChildNodes->InvalidateCacheIfAvailable();
 211     ImplCycleCollectionUnlink(mChildNodes);
 212   }
 213 }
 214
 215 //----------------------------------------------------------------------
 216
 217 #ifdef MOZILLA_INTERNAL_API
 218 nsINode::nsINode(already_AddRefed<mozilla::dom::NodeInfo>&& aNodeInfo)
 219     : mNodeInfo(std::move(aNodeInfo)),
 220       mParent(nullptr)
 221 #  ifndef BOOL_FLAGS_ON_WRAPPER_CACHE
 222       ,
 223       mBoolFlags(0)
 224 #  endif
 225       ,
 226       mChildCount(0),
 227       mPreviousOrLastSibling(nullptr),
 228       mSubtreeRoot(this),
 229       mSlots(nullptr) {
 230 }
 231 #endif
 232
 233 nsINode::~nsINode() {
 234   MOZ_ASSERT(!HasSlots(), "LastRelease was not called?");
 235   MOZ_ASSERT(mSubtreeRoot == this, "Didn't restore state properly?");
 236 }
 237
 238 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
 239 void nsINode::AssertInvariantsOnNodeInfoChange() {
 240   MOZ_DIAGNOSTIC_ASSERT(!IsInComposedDoc());
 241   if (nsCOMPtr<Link> link = do_QueryInterface(this)) {
 242     MOZ_DIAGNOSTIC_ASSERT(!link->HasPendingLinkUpdate());
 243   }
 244 }
 245 #endif
 246
 247 void* nsINode::GetProperty(const nsAtom* aPropertyName,
 248                            nsresult* aStatus) const {
 249   if (!HasProperties()) {  // a fast HasFlag() test
 250     if (aStatus) {
 251       *aStatus = NS_PROPTABLE_PROP_NOT_THERE;
 252     }
 253     return nullptr;
 254   }
 255   return OwnerDoc()->PropertyTable().GetProperty(this, aPropertyName, aStatus);
 256 }
 257
 258 nsresult nsINode::SetProperty(nsAtom* aPropertyName, void* aValue,
 259                               NSPropertyDtorFunc aDtor, bool aTransfer) {
 260   nsresult rv = OwnerDoc()->PropertyTable().SetProperty(
 261       this, aPropertyName, aValue, aDtor, nullptr, aTransfer);
 262   if (NS_SUCCEEDED(rv)) {
 263     SetFlags(NODE_HAS_PROPERTIES);
 264   }
 265
 266   return rv;
 267 }
 268
 269 void nsINode::RemoveProperty(const nsAtom* aPropertyName) {
 270   OwnerDoc()->PropertyTable().RemoveProperty(this, aPropertyName);
 271 }
 272
 273 void* nsINode::TakeProperty(const nsAtom* aPropertyName, nsresult* aStatus) {
 274   return OwnerDoc()->PropertyTable().TakeProperty(this, aPropertyName, aStatus);
 275 }
 276
 277 nsIContentSecurityPolicy* nsINode::GetCsp() const {
 278   return OwnerDoc()->GetCsp();
 279 }
 280
 281 nsINode::nsSlots* nsINode::CreateSlots() { return new nsSlots(); }
 282
 283 static const nsINode* GetClosestCommonInclusiveAncestorForRangeInSelection(
 284     const nsINode* aNode) {
 285   while (aNode &&
 286          !aNode->IsClosestCommonInclusiveAncestorForRangeInSelection()) {
 287     if (!aNode
 288              ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection()) {
 289       return nullptr;
 290     }
 291     aNode = aNode->GetParentNode();
 292   }
 293   return aNode;
 294 }
 295
 296 /**
 297  * A Comparator suitable for mozilla::BinarySearchIf for searching a collection
 298  * of nsRange* for an overlap of (mNode, mStartOffset) .. (mNode, mEndOffset).
 299  */
 300 class IsItemInRangeComparator {
 301  public:
 302   // @param aStartOffset has to be less or equal to aEndOffset.
 303   IsItemInRangeComparator(const nsINode& aNode, const uint32_t aStartOffset,
 304                           const uint32_t aEndOffset,
 305                           nsContentUtils::ComparePointsCache* aCache)
 306       : mNode(aNode),
 307         mStartOffset(aStartOffset),
 308         mEndOffset(aEndOffset),
 309         mCache(aCache) {
 310     MOZ_ASSERT(aStartOffset <= aEndOffset);
 311   }
 312
 313   int operator()(const AbstractRange* const aRange) const {
 314     int32_t cmp = nsContentUtils::ComparePoints_Deprecated(
 315         &mNode, mEndOffset, aRange->GetStartContainer(), aRange->StartOffset(),
 316         nullptr, mCache);
 317     if (cmp == 1) {
 318       cmp = nsContentUtils::ComparePoints_Deprecated(
 319           &mNode, mStartOffset, aRange->GetEndContainer(), aRange->EndOffset(),
 320           nullptr, mCache);
 321       if (cmp == -1) {
 322         return 0;
 323       }
 324       return 1;
 325     }
 326     return -1;
 327   }
 328
 329  private:
 330   const nsINode& mNode;
 331   const uint32_t mStartOffset;
 332   const uint32_t mEndOffset;
 333   nsContentUtils::ComparePointsCache* mCache;
 334 };
 335
 336 bool nsINode::IsSelected(const uint32_t aStartOffset,
 337                          const uint32_t aEndOffset) const {
 338   MOZ_ASSERT(aStartOffset <= aEndOffset);
 339
 340   const nsINode* n = GetClosestCommonInclusiveAncestorForRangeInSelection(this);
 341   NS_ASSERTION(n || !IsMaybeSelected(),
 342                "A node without a common inclusive ancestor for a range in "
 343                "Selection is for sure not selected.");
 344
 345   // Collect the selection objects for potential ranges.
 346   nsTHashSet<Selection*> ancestorSelections;
 347   for (; n; n = GetClosestCommonInclusiveAncestorForRangeInSelection(
 348                 n->GetParentNode())) {
 349     const LinkedList<AbstractRange>* ranges =
 350         n->GetExistingClosestCommonInclusiveAncestorRanges();
 351     if (!ranges) {
 352       continue;
 353     }
 354     for (const AbstractRange* range : *ranges) {
 355       MOZ_ASSERT(range->IsInAnySelection(),
 356                  "Why is this range registered with a node?");
 357       // Looks like that IsInSelection() assert fails sometimes...
 358       if (range->IsInAnySelection()) {
 359         for (const WeakPtr<Selection>& selection : range->GetSelections()) {
 360           ancestorSelections.Insert(selection);
 361         }
 362       }
 363     }
 364   }
 365
 366   nsContentUtils::ComparePointsCache cache;
 367   IsItemInRangeComparator comparator{*this, aStartOffset, aEndOffset, &cache};
 368   for (Selection* selection : ancestorSelections) {
 369     // Binary search the sorted ranges in this selection.
 370     // (Selection::GetRangeAt returns its ranges ordered).
 371     size_t low = 0;
 372     size_t high = selection->RangeCount();
 373
 374     while (high != low) {
 375       size_t middle = low + (high - low) / 2;
 376
 377       const AbstractRange* const range = selection->GetAbstractRangeAt(middle);
 378       int result = comparator(range);
 379       if (result == 0) {
 380         if (!range->Collapsed()) {
 381           return true;
 382         }
 383
 384         const AbstractRange* middlePlus1;
 385         const AbstractRange* middleMinus1;
 386         // if node end > start of middle+1, result = 1
 387         if (middle + 1 < high &&
 388             (middlePlus1 = selection->GetAbstractRangeAt(middle + 1)) &&
 389             nsContentUtils::ComparePoints_Deprecated(
 390                 this, aEndOffset, middlePlus1->GetStartContainer(),
 391                 middlePlus1->StartOffset(), nullptr, &cache) > 0) {
 392           result = 1;
 393           // if node start < end of middle - 1, result = -1
 394         } else if (middle >= 1 &&
 395                    (middleMinus1 = selection->GetAbstractRangeAt(middle - 1)) &&
 396                    nsContentUtils::ComparePoints_Deprecated(
 397                        this, aStartOffset, middleMinus1->GetEndContainer(),
 398                        middleMinus1->EndOffset(), nullptr, &cache) < 0) {
 399           result = -1;
 400         } else {
 401           break;
 402         }
 403       }
 404
 405       if (result < 0) {
 406         high = middle;
 407       } else {
 408         low = middle + 1;
 409       }
 410     }
 411   }
 412
 413   return false;
 414 }
 415
 416 Element* nsINode::GetAnonymousRootElementOfTextEditor(
 417     TextEditor** aTextEditor) {
 418   if (aTextEditor) {
 419     *aTextEditor = nullptr;
 420   }
 421   RefPtr<TextControlElement> textControlElement;
 422   if (IsInNativeAnonymousSubtree()) {
 423     textControlElement = TextControlElement::FromNodeOrNull(
 424         GetClosestNativeAnonymousSubtreeRootParentOrHost());
 425   } else {
 426     textControlElement = TextControlElement::FromNode(this);
 427   }
 428   if (!textControlElement) {
 429     return nullptr;
 430   }
 431   RefPtr<TextEditor> textEditor = textControlElement->GetTextEditor();
 432   if (!textEditor) {
 433     // The found `TextControlElement` may be an input element which is not a
 434     // text control element.  In this case, such element must not be in a
 435     // native anonymous tree of a `TextEditor` so this node is not in any
 436     // `TextEditor`.
 437     return nullptr;
 438   }
 439
 440   Element* rootElement = textEditor->GetRoot();
 441   if (aTextEditor) {
 442     textEditor.forget(aTextEditor);
 443   }
 444   return rootElement;
 445 }
 446
 447 void nsINode::QueueDevtoolsAnonymousEvent(bool aIsRemove) {
 448   MOZ_ASSERT(IsRootOfNativeAnonymousSubtree());
 449   MOZ_ASSERT(OwnerDoc()->DevToolsAnonymousAndShadowEventsEnabled());
 450   AsyncEventDispatcher* dispatcher = new AsyncEventDispatcher(
 451       this, aIsRemove ? u"anonymousrootremoved"_ns : u"anonymousrootcreated"_ns,
 452       CanBubble::eYes, ChromeOnlyDispatch::eYes, Composed::eYes);
 453   dispatcher->PostDOMEvent();
 454 }
 455
 456 nsINode* nsINode::GetRootNode(const GetRootNodeOptions& aOptions) {
 457   if (aOptions.mComposed) {
 458     if (Document* doc = GetComposedDoc()) {
 459       return doc;
 460     }
 461
 462     nsINode* node = this;
 463     while (node) {
 464       node = node->SubtreeRoot();
 465       ShadowRoot* shadow = ShadowRoot::FromNode(node);
 466       if (!shadow) {
 467         break;
 468       }
 469       node = shadow->GetHost();
 470     }
 471
 472     return node;
 473   }
 474
 475   return SubtreeRoot();
 476 }
 477
 478 nsIContent* nsINode::GetFirstChildOfTemplateOrNode() {
 479   if (IsTemplateElement()) {
 480     DocumentFragment* frag = static_cast<HTMLTemplateElement*>(this)->Content();
 481     return frag->GetFirstChild();
 482   }
 483
 484   return GetFirstChild();
 485 }
 486
 487 nsINode* nsINode::SubtreeRoot() const {
 488   auto RootOfNode = [](const nsINode* aStart) -> nsINode* {
 489     const nsINode* node = aStart;
 490     const nsINode* iter = node;
 491     while ((iter = iter->GetParentNode())) {
 492       node = iter;
 493     }
 494     return const_cast<nsINode*>(node);
 495   };
 496
 497   // There are four cases of interest here.  nsINodes that are really:
 498   // 1. Document nodes - Are always in the document.
 499   // 2.a nsIContent nodes not in a shadow tree - Are either in the document,
 500   //     or mSubtreeRoot is updated in BindToTree/UnbindFromTree.
 501   // 2.b nsIContent nodes in a shadow tree - Are never in the document,
 502   //     ignore mSubtreeRoot and return the containing shadow root.
 503   // 4. Attr nodes - Are never in the document, and mSubtreeRoot
 504   //    is always 'this' (as set in nsINode's ctor).
 505   nsINode* node;
 506   if (IsInUncomposedDoc()) {
 507     node = OwnerDocAsNode();
 508   } else if (IsContent()) {
 509     ShadowRoot* containingShadow = AsContent()->GetContainingShadow();
 510     node = containingShadow ? containingShadow : mSubtreeRoot;
 511     if (!node) {
 512       NS_WARNING("Using SubtreeRoot() on unlinked element?");
 513       node = RootOfNode(this);
 514     }
 515   } else {
 516     node = mSubtreeRoot;
 517   }
 518   MOZ_ASSERT(node, "Should always have a node here!");
 519 #ifdef DEBUG
 520   {
 521     const nsINode* slowNode = RootOfNode(this);
 522     MOZ_ASSERT(slowNode == node, "These should always be in sync!");
 523   }
 524 #endif
 525   return node;
 526 }
 527
 528 static nsIContent* GetRootForContentSubtree(nsIContent* aContent) {
 529   NS_ENSURE_TRUE(aContent, nullptr);
 530
 531   // Special case for ShadowRoot because the ShadowRoot itself is
 532   // the root. This is necessary to prevent selection from crossing
 533   // the ShadowRoot boundary.
 534   //
 535   // FIXME(emilio): The NAC check should probably be done before this? We can
 536   // have NAC inside shadow DOM.
 537   if (ShadowRoot* containingShadow = aContent->GetContainingShadow()) {
 538     return containingShadow;
 539   }
 540   if (nsIContent* nativeAnonRoot =
 541           aContent->GetClosestNativeAnonymousSubtreeRoot()) {
 542     return nativeAnonRoot;
 543   }
 544   if (Document* doc = aContent->GetUncomposedDoc()) {
 545     return doc->GetRootElement();
 546   }
 547   return nsIContent::FromNode(aContent->SubtreeRoot());
 548 }
 549
 550 nsIContent* nsINode::GetSelectionRootContent(PresShell* aPresShell) {
 551   NS_ENSURE_TRUE(aPresShell, nullptr);
 552
 553   if (IsDocument()) return AsDocument()->GetRootElement();
 554   if (!IsContent()) return nullptr;
 555
 556   if (GetComposedDoc() != aPresShell->GetDocument()) {
 557     return nullptr;
 558   }
 559
 560   if (AsContent()->HasIndependentSelection() || IsInNativeAnonymousSubtree()) {
 561     // This node should be an inclusive descendant of input/textarea editor.
 562     // In that case, the anonymous <div> for TextEditor should be always the
 563     // selection root.
 564     // FIXME: If Selection for the document is collapsed in <input> or
 565     // <textarea>, returning anonymous <div> may make the callers confused.
 566     // Perhaps, we should do this only when this is in the native anonymous
 567     // subtree unless the callers explicitly want to retrieve the anonymous
 568     // <div> from a text control element.
 569     if (Element* anonymousDivElement = GetAnonymousRootElementOfTextEditor()) {
 570       return anonymousDivElement;
 571     }
 572   }
 573
 574   nsPresContext* presContext = aPresShell->GetPresContext();
 575   if (presContext) {
 576     HTMLEditor* htmlEditor = nsContentUtils::GetHTMLEditor(presContext);
 577     if (htmlEditor) {
 578       // This node is in HTML editor.
 579       if (!IsInComposedDoc() || IsInDesignMode() ||
 580           !HasFlag(NODE_IS_EDITABLE)) {
 581         nsIContent* editorRoot = htmlEditor->GetRoot();
 582         NS_ENSURE_TRUE(editorRoot, nullptr);
 583         return nsContentUtils::IsInSameAnonymousTree(this, editorRoot)
 584                    ? editorRoot
 585                    : GetRootForContentSubtree(AsContent());
 586       }
 587       // If the document isn't editable but this is editable, this is in
 588       // contenteditable.  Use the editing host element for selection root.
 589       return static_cast<nsIContent*>(this)->GetEditingHost();
 590     }
 591   }
 592
 593   RefPtr<nsFrameSelection> fs = aPresShell->FrameSelection();
 594   nsIContent* content = fs->GetLimiter();
 595   if (!content) {
 596     content = fs->GetAncestorLimiter();
 597     if (!content) {
 598       Document* doc = aPresShell->GetDocument();
 599       NS_ENSURE_TRUE(doc, nullptr);
 600       content = doc->GetRootElement();
 601       if (!content) return nullptr;
 602     }
 603   }
 604
 605   // This node might be in another subtree, if so, we should find this subtree's
 606   // root.  Otherwise, we can return the content simply.
 607   NS_ENSURE_TRUE(content, nullptr);
 608   if (!nsContentUtils::IsInSameAnonymousTree(this, content)) {
 609     content = GetRootForContentSubtree(AsContent());
 610     // Fixup for ShadowRoot because the ShadowRoot itself does not have a frame.
 611     // Use the host as the root.
 612     if (ShadowRoot* shadowRoot = ShadowRoot::FromNode(content)) {
 613       content = shadowRoot->GetHost();
 614     }
 615   }
 616
 617   return content;
 618 }
 619
 620 nsINodeList* nsINode::ChildNodes() {
 621   nsSlots* slots = Slots();
 622   if (!slots->mChildNodes) {
 623     slots->mChildNodes = IsAttr() ? new nsAttrChildContentList(this)
 624                                   : new nsParentNodeChildContentList(this);
 625   }
 626
 627   return slots->mChildNodes;
 628 }
 629
 630 nsIContent* nsINode::GetLastChild() const {
 631   return mFirstChild ? mFirstChild->mPreviousOrLastSibling : nullptr;
 632 }
 633
 634 void nsINode::InvalidateChildNodes() {
 635   MOZ_ASSERT(!IsAttr());
 636
 637   nsSlots* slots = GetExistingSlots();
 638   if (!slots || !slots->mChildNodes) {
 639     return;
 640   }
 641
 642   auto childNodes =
 643       static_cast<nsParentNodeChildContentList*>(slots->mChildNodes.get());
 644   childNodes->InvalidateCache();
 645 }
 646
 647 void nsINode::GetTextContentInternal(nsAString& aTextContent,
 648                                      OOMReporter& aError) {
 649   SetDOMStringToNull(aTextContent);
 650 }
 651
 652 DocumentOrShadowRoot* nsINode::GetContainingDocumentOrShadowRoot() const {
 653   if (IsInUncomposedDoc()) {
 654     return OwnerDoc();
 655   }
 656
 657   if (IsInShadowTree()) {
 658     return AsContent()->GetContainingShadow();
 659   }
 660
 661   return nullptr;
 662 }
 663
 664 DocumentOrShadowRoot* nsINode::GetUncomposedDocOrConnectedShadowRoot() const {
 665   if (IsInUncomposedDoc()) {
 666     return OwnerDoc();
 667   }
 668
 669   if (IsInComposedDoc() && IsInShadowTree()) {
 670     return AsContent()->GetContainingShadow();
 671   }
 672
 673   return nullptr;
 674 }
 675
 676 mozilla::SafeDoublyLinkedList<nsIMutationObserver>*
 677 nsINode::GetMutationObservers() {
 678   return HasSlots() ? &GetExistingSlots()->mMutationObservers : nullptr;
 679 }
 680
 681 void nsINode::LastRelease() {
 682   nsINode::nsSlots* slots = GetExistingSlots();
 683   if (slots) {
 684     if (!slots->mMutationObservers.isEmpty()) {
 685       for (auto iter = slots->mMutationObservers.begin();
 686            iter != slots->mMutationObservers.end(); ++iter) {
 687         iter->NodeWillBeDestroyed(this);
 688       }
 689     }
 690
 691     if (IsContent()) {
 692       nsIContent* content = AsContent();
 693       if (HTMLSlotElement* slot = content->GetManualSlotAssignment()) {
 694         content->SetManualSlotAssignment(nullptr);
 695         slot->RemoveManuallyAssignedNode(*content);
 696       }
 697     }
 698
 699     if (Element* element = Element::FromNode(this)) {
 700       if (CustomElementData* data = element->GetCustomElementData()) {
 701         data->Unlink();
 702       }
 703     }
 704
 705     delete slots;
 706     mSlots = nullptr;
 707   }
 708
 709   // Kill properties first since that may run external code, so we want to
 710   // be in as complete state as possible at that time.
 711   if (IsDocument()) {
 712     // Delete all properties before tearing down the document. Some of the
 713     // properties are bound to nsINode objects and the destructor functions of
 714     // the properties may want to use the owner document of the nsINode.
 715     AsDocument()->RemoveAllProperties();
 716   } else {
 717     if (HasProperties()) {
 718       // Strong reference to the document so that deleting properties can't
 719       // delete the document.
 720       nsCOMPtr<Document> document = OwnerDoc();
 721       document->RemoveAllPropertiesFor(this);
 722     }
 723
 724     if (HasFlag(ADDED_TO_FORM)) {
 725       if (nsGenericHTMLFormControlElement* formControl =
 726               nsGenericHTMLFormControlElement::FromNode(this)) {
 727         // Tell the form (if any) this node is going away.  Don't
 728         // notify, since we're being destroyed in any case.
 729         formControl->ClearForm(true, true);
 730       } else if (HTMLImageElement* imageElem =
 731                      HTMLImageElement::FromNode(this)) {
 732         imageElem->ClearForm(true);
 733       }
 734     }
 735   }
 736   UnsetFlags(NODE_HAS_PROPERTIES);
 737
 738   if (NodeType() != nsINode::DOCUMENT_NODE &&
 739       HasFlag(NODE_HAS_LISTENERMANAGER)) {
 740 #ifdef DEBUG
 741     if (nsContentUtils::IsInitialized()) {
 742       EventListenerManager* manager =
 743           nsContentUtils::GetExistingListenerManagerForNode(this);
 744       if (!manager) {
 745         NS_ERROR(
 746             "Huh, our bit says we have a listener manager list, "
 747             "but there's nothing in the hash!?!!");
 748       }
 749     }
 750 #endif
 751
 752     nsContentUtils::RemoveListenerManager(this);
 753     UnsetFlags(NODE_HAS_LISTENERMANAGER);
 754   }
 755
 756   ReleaseWrapper(this);
 757
 758   FragmentOrElement::RemoveBlackMarkedNode(this);
 759 }
 760
 761 std::ostream& operator<<(std::ostream& aStream, const nsINode& aNode) {
 762   nsAutoString elemDesc;
 763   const nsINode* curr = &aNode;
 764   while (curr) {
 765     nsString id;
 766     if (curr->IsElement()) {
 767       curr->AsElement()->GetId(id);
 768     }
 769
 770     if (!elemDesc.IsEmpty()) {
 771       elemDesc = elemDesc + u"."_ns;
 772     }
 773
 774     if (!curr->LocalName().IsEmpty()) {
 775       elemDesc.Append(curr->LocalName());
 776     } else {
 777       elemDesc.Append(curr->NodeName());
 778     }
 779
 780     if (!id.IsEmpty()) {
 781       elemDesc = elemDesc + u"['"_ns + id + u"']"_ns;
 782     }
 783
 784     if (curr->IsElement() &&
 785         curr->AsElement()->HasAttr(nsGkAtoms::contenteditable)) {
 786       nsAutoString val;
 787       curr->AsElement()->GetAttr(nsGkAtoms::contenteditable, val);
 788       elemDesc = elemDesc + u"[contenteditable=\""_ns + val + u"\"]"_ns;
 789     }
 790     if (curr->IsDocument() && curr->IsInDesignMode()) {
 791       elemDesc.Append(u"[designMode=\"on\"]"_ns);
 792     }
 793
 794     curr = curr->GetParentNode();
 795   }
 796
 797   NS_ConvertUTF16toUTF8 str(elemDesc);
 798   return aStream << str.get();
 799 }
 800
 801 nsIContent* nsINode::DoGetShadowHost() const {
 802   MOZ_ASSERT(IsShadowRoot());
 803   return static_cast<const ShadowRoot*>(this)->GetHost();
 804 }
 805
 806 ShadowRoot* nsINode::GetContainingShadow() const {
 807   if (!IsInShadowTree()) {
 808     return nullptr;
 809   }
 810   return AsContent()->GetContainingShadow();
 811 }
 812
 813 nsIContent* nsINode::GetContainingShadowHost() const {
 814   if (ShadowRoot* shadow = GetContainingShadow()) {
 815     return shadow->GetHost();
 816   }
 817   return nullptr;
 818 }
 819
 820 SVGUseElement* nsINode::DoGetContainingSVGUseShadowHost() const {
 821   MOZ_ASSERT(IsInShadowTree());
 822   return SVGUseElement::FromNodeOrNull(GetContainingShadowHost());
 823 }
 824
 825 void nsINode::GetNodeValueInternal(nsAString& aNodeValue) {
 826   SetDOMStringToNull(aNodeValue);
 827 }
 828
 829 static const char* NodeTypeAsString(nsINode* aNode) {
 830   static const char* NodeTypeStrings[] = {
 831       "",  // No nodes of type 0
 832       "an Element",
 833       "an Attribute",
 834       "a Text",
 835       "a CDATASection",
 836       "an EntityReference",
 837       "an Entity",
 838       "a ProcessingInstruction",
 839       "a Comment",
 840       "a Document",
 841       "a DocumentType",
 842       "a DocumentFragment",
 843       "a Notation",
 844   };
 845   static_assert(ArrayLength(NodeTypeStrings) == nsINode::MAX_NODE_TYPE + 1,
 846                 "Max node type out of range for our array");
 847
 848   uint16_t nodeType = aNode->NodeType();
 849   MOZ_RELEASE_ASSERT(nodeType < ArrayLength(NodeTypeStrings),
 850                      "Uknown out-of-range node type");
 851   return NodeTypeStrings[nodeType];
 852 }
 853
 854 nsINode* nsINode::RemoveChild(nsINode& aOldChild, ErrorResult& aError) {
 855   if (!aOldChild.IsContent()) {
 856     // aOldChild can't be one of our children.
 857     aError.ThrowNotFoundError(
 858         "The node to be removed is not a child of this node");
 859     return nullptr;
 860   }
 861
 862   if (aOldChild.GetParentNode() == this) {
 863     nsContentUtils::MaybeFireNodeRemoved(&aOldChild, this);
 864   }
 865
 866   // Check again, we may not be the child's parent anymore.
 867   // Can be triggered by dom/base/crashtests/293388-1.html
 868   if (aOldChild.IsRootOfNativeAnonymousSubtree() ||
 869       aOldChild.GetParentNode() != this) {
 870     // aOldChild isn't one of our children.
 871     aError.ThrowNotFoundError(
 872         "The node to be removed is not a child of this node");
 873     return nullptr;
 874   }
 875
 876   RemoveChildNode(aOldChild.AsContent(), true);
 877   return &aOldChild;
 878 }
 879
 880 void nsINode::Normalize() {
 881   // First collect list of nodes to be removed
 882   AutoTArray<nsCOMPtr<nsIContent>, 50> nodes;
 883
 884   bool canMerge = false;
 885   for (nsIContent* node = this->GetFirstChild(); node;
 886        node = node->GetNextNode(this)) {
 887     if (node->NodeType() != TEXT_NODE) {
 888       canMerge = false;
 889       continue;
 890     }
 891
 892     if (canMerge || node->TextLength() == 0) {
 893       // No need to touch canMerge. That way we can merge across empty
 894       // textnodes if and only if the node before is a textnode
 895       nodes.AppendElement(node);
 896     } else {
 897       canMerge = true;
 898     }
 899
 900     // If there's no following sibling, then we need to ensure that we don't
 901     // collect following siblings of our (grand)parent as to-be-removed
 902     canMerge = canMerge && !!node->GetNextSibling();
 903   }
 904
 905   if (nodes.IsEmpty()) {
 906     return;
 907   }
 908
 909   // We're relying on mozAutoSubtreeModified to keep the doc alive here.
 910   RefPtr<Document> doc = OwnerDoc();
 911
 912   // Batch possible DOMSubtreeModified events.
 913   mozAutoSubtreeModified subtree(doc, nullptr);
 914
 915   // Fire all DOMNodeRemoved events. Optimize the common case of there being
 916   // no listeners
 917   bool hasRemoveListeners = nsContentUtils::HasMutationListeners(
 918       doc, NS_EVENT_BITS_MUTATION_NODEREMOVED);
 919   if (hasRemoveListeners) {
 920     for (nsCOMPtr<nsIContent>& node : nodes) {
 921       // Node may have already been removed.
 922       if (nsCOMPtr<nsINode> parentNode = node->GetParentNode()) {
 923         // TODO: Bug 1622253
 924         nsContentUtils::MaybeFireNodeRemoved(MOZ_KnownLive(node), parentNode);
 925       }
 926     }
 927   }
 928
 929   mozAutoDocUpdate batch(doc, true);
 930
 931   // Merge and remove all nodes
 932   nsAutoString tmpStr;
 933   for (uint32_t i = 0; i < nodes.Length(); ++i) {
 934     nsIContent* node = nodes[i];
 935     // Merge with previous node unless empty
 936     const nsTextFragment* text = node->GetText();
 937     if (text->GetLength()) {
 938       nsIContent* target = node->GetPreviousSibling();
 939       NS_ASSERTION(
 940           (target && target->NodeType() == TEXT_NODE) || hasRemoveListeners,
 941           "Should always have a previous text sibling unless "
 942           "mutation events messed us up");
 943       if (!hasRemoveListeners || (target && target->NodeType() == TEXT_NODE)) {
 944         nsTextNode* t = static_cast<nsTextNode*>(target);
 945         if (text->Is2b()) {
 946           t->AppendTextForNormalize(text->Get2b(), text->GetLength(), true,
 947                                     node);
 948         } else {
 949           tmpStr.Truncate();
 950           text->AppendTo(tmpStr);
 951           t->AppendTextForNormalize(tmpStr.get(), tmpStr.Length(), true, node);
 952         }
 953       }
 954     }
 955
 956     // Remove node
 957     nsCOMPtr<nsINode> parent = node->GetParentNode();
 958     NS_ASSERTION(parent || hasRemoveListeners,
 959                  "Should always have a parent unless "
 960                  "mutation events messed us up");
 961     if (parent) {
 962       parent->RemoveChildNode(node, true);
 963     }
 964   }
 965 }
 966
 967 nsresult nsINode::GetBaseURI(nsAString& aURI) const {
 968   nsIURI* baseURI = GetBaseURI();
 969
 970   nsAutoCString spec;
 971   if (baseURI) {
 972     nsresult rv = baseURI->GetSpec(spec);
 973     NS_ENSURE_SUCCESS(rv, rv);
 974   }
 975
 976   CopyUTF8toUTF16(spec, aURI);
 977   return NS_OK;
 978 }
 979
 980 void nsINode::GetBaseURIFromJS(nsAString& aURI, CallerType aCallerType,
 981                                ErrorResult& aRv) const {
 982   nsIURI* baseURI = GetBaseURI(aCallerType == CallerType::System);
 983   nsAutoCString spec;
 984   if (baseURI) {
 985     nsresult res = baseURI->GetSpec(spec);
 986     if (NS_FAILED(res)) {
 987       aRv.Throw(res);
 988       return;
 989     }
 990   }
 991   CopyUTF8toUTF16(spec, aURI);
 992 }
 993
 994 nsIURI* nsINode::GetBaseURIObject() const { return GetBaseURI(true); }
 995
 996 void nsINode::LookupPrefix(const nsAString& aNamespaceURI, nsAString& aPrefix) {
 997   if (Element* nsElement = GetNameSpaceElement()) {
 998     // XXX Waiting for DOM spec to list error codes.
 999
1000     // Trace up the content parent chain looking for the namespace
1001     // declaration that defines the aNamespaceURI namespace. Once found,
1002     // return the prefix (i.e. the attribute localName).
1003     for (Element* element : nsElement->InclusiveAncestorsOfType<Element>()) {
1004       uint32_t attrCount = element->GetAttrCount();
1005
1006       for (uint32_t i = 0; i < attrCount; ++i) {
1007         const nsAttrName* name = element->GetAttrNameAt(i);
1008
1009         if (name->NamespaceEquals(kNameSpaceID_XMLNS) &&
1010             element->AttrValueIs(kNameSpaceID_XMLNS, name->LocalName(),
1011                                  aNamespaceURI, eCaseMatters)) {
1012           // If the localName is "xmlns", the prefix we output should be
1013           // null.
1014           nsAtom* localName = name->LocalName();
1015
1016           if (localName != nsGkAtoms::xmlns) {
1017             localName->ToString(aPrefix);
1018           } else {
1019             SetDOMStringToNull(aPrefix);
1020           }
1021           return;
1022         }
1023       }
1024     }
1025   }
1026
1027   SetDOMStringToNull(aPrefix);
1028 }
1029
1030 uint16_t nsINode::CompareDocumentPosition(nsINode& aOtherNode,
1031                                           Maybe<uint32_t>* aThisIndex,
1032                                           Maybe<uint32_t>* aOtherIndex) const {
1033   if (this == &aOtherNode) {
1034     return 0;
1035   }
1036   if (GetPreviousSibling() == &aOtherNode) {
1037     MOZ_ASSERT(GetParentNode() == aOtherNode.GetParentNode());
1038     return Node_Binding::DOCUMENT_POSITION_PRECEDING;
1039   }
1040   if (GetNextSibling() == &aOtherNode) {
1041     MOZ_ASSERT(GetParentNode() == aOtherNode.GetParentNode());
1042     return Node_Binding::DOCUMENT_POSITION_FOLLOWING;
1043   }
1044
1045   AutoTArray<const nsINode*, 32> parents1, parents2;
1046
1047   const nsINode* node1 = &aOtherNode;
1048   const nsINode* node2 = this;
1049
1050   // Check if either node is an attribute
1051   const Attr* attr1 = Attr::FromNode(node1);
1052   if (attr1) {
1053     const Element* elem = attr1->GetElement();
1054     // If there is an owner element add the attribute
1055     // to the chain and walk up to the element
1056     if (elem) {
1057       node1 = elem;
1058       parents1.AppendElement(attr1);
1059     }
1060   }
1061   if (auto* attr2 = Attr::FromNode(node2)) {
1062     const Element* elem = attr2->GetElement();
1063     if (elem == node1 && attr1) {
1064       // Both nodes are attributes on the same element.
1065       // Compare position between the attributes.
1066
1067       uint32_t i;
1068       const nsAttrName* attrName;
1069       for (i = 0; (attrName = elem->GetAttrNameAt(i)); ++i) {
1070         if (attrName->Equals(attr1->NodeInfo())) {
1071           NS_ASSERTION(!attrName->Equals(attr2->NodeInfo()),
1072                        "Different attrs at same position");
1073           return Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC |
1074                  Node_Binding::DOCUMENT_POSITION_PRECEDING;
1075         }
1076         if (attrName->Equals(attr2->NodeInfo())) {
1077           return Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC |
1078                  Node_Binding::DOCUMENT_POSITION_FOLLOWING;
1079         }
1080       }
1081       MOZ_ASSERT_UNREACHABLE("neither attribute in the element");
1082       return Node_Binding::DOCUMENT_POSITION_DISCONNECTED;
1083     }
1084
1085     if (elem) {
1086       node2 = elem;
1087       parents2.AppendElement(attr2);
1088     }
1089   }
1090
1091   // We now know that both nodes are either nsIContents or Documents.
1092   // If either node started out as an attribute, that attribute will have
1093   // the same relative position as its ownerElement, except if the
1094   // ownerElement ends up being the container for the other node
1095
1096   // Build the chain of parents
1097   do {
1098     parents1.AppendElement(node1);
1099     node1 = node1->GetParentNode();
1100   } while (node1);
1101   do {
1102     parents2.AppendElement(node2);
1103     node2 = node2->GetParentNode();
1104   } while (node2);
1105
1106   // Check if the nodes are disconnected.
1107   uint32_t pos1 = parents1.Length();
1108   uint32_t pos2 = parents2.Length();
1109   const nsINode* top1 = parents1.ElementAt(--pos1);
1110   const nsINode* top2 = parents2.ElementAt(--pos2);
1111   if (top1 != top2) {
1112     return top1 < top2
1113                ? (Node_Binding::DOCUMENT_POSITION_PRECEDING |
1114                   Node_Binding::DOCUMENT_POSITION_DISCONNECTED |
1115                   Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC)
1116                : (Node_Binding::DOCUMENT_POSITION_FOLLOWING |
1117                   Node_Binding::DOCUMENT_POSITION_DISCONNECTED |
1118                   Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC);
1119   }
1120
1121   // Find where the parent chain differs and check indices in the parent.
1122   const nsINode* parent = top1;
1123   uint32_t len;
1124   for (len = std::min(pos1, pos2); len > 0; --len) {
1125     const nsINode* child1 = parents1.ElementAt(--pos1);
1126     const nsINode* child2 = parents2.ElementAt(--pos2);
1127     if (child1 != child2) {
1128       // child1 or child2 can be an attribute here. This will work fine since
1129       // ComputeIndexOf will return Nothing for the attribute making the
1130       // attribute be considered before any child.
1131       Maybe<uint32_t> child1Index;
1132       bool cachedChild1Index = false;
1133       if (&aOtherNode == child1 && aOtherIndex) {
1134         cachedChild1Index = true;
1135         child1Index = aOtherIndex->isSome() ? *aOtherIndex
1136                                             : parent->ComputeIndexOf(child1);
1137       } else {
1138         child1Index = parent->ComputeIndexOf(child1);
1139       }
1140
1141       Maybe<uint32_t> child2Index;
1142       bool cachedChild2Index = false;
1143       if (this == child2 && aThisIndex) {
1144         cachedChild2Index = true;
1145         child2Index =
1146             aThisIndex->isSome() ? *aThisIndex : parent->ComputeIndexOf(child2);
1147       } else {
1148         child2Index = parent->ComputeIndexOf(child2);
1149       }
1150
1151       uint16_t retVal = child1Index < child2Index
1152                             ? Node_Binding::DOCUMENT_POSITION_PRECEDING
1153                             : Node_Binding::DOCUMENT_POSITION_FOLLOWING;
1154
1155       if (cachedChild1Index) {
1156         *aOtherIndex = child1Index;
1157       }
1158       if (cachedChild2Index) {
1159         *aThisIndex = child2Index;
1160       }
1161
1162       return retVal;
1163     }
1164     parent = child1;
1165   }
1166
1167   // We hit the end of one of the parent chains without finding a difference
1168   // between the chains. That must mean that one node is an ancestor of the
1169   // other. The one with the shortest chain must be the ancestor.
1170   return pos1 < pos2 ? (Node_Binding::DOCUMENT_POSITION_PRECEDING |
1171                         Node_Binding::DOCUMENT_POSITION_CONTAINS)
1172                      : (Node_Binding::DOCUMENT_POSITION_FOLLOWING |
1173                         Node_Binding::DOCUMENT_POSITION_CONTAINED_BY);
1174 }
1175
1176 bool nsINode::IsSameNode(nsINode* other) { return other == this; }
1177
1178 bool nsINode::IsEqualNode(nsINode* aOther) {
1179   if (!aOther) {
1180     return false;
1181   }
1182
1183   // Might as well do a quick check to avoid walking our kids if we're
1184   // obviously the same.
1185   if (aOther == this) {
1186     return true;
1187   }
1188
1189   nsAutoString string1, string2;
1190
1191   nsINode* node1 = this;
1192   nsINode* node2 = aOther;
1193   do {
1194     uint16_t nodeType = node1->NodeType();
1195     if (nodeType != node2->NodeType()) {
1196       return false;
1197     }
1198
1199     mozilla::dom::NodeInfo* nodeInfo1 = node1->mNodeInfo;
1200     mozilla::dom::NodeInfo* nodeInfo2 = node2->mNodeInfo;
1201     if (!nodeInfo1->Equals(nodeInfo2) ||
1202         nodeInfo1->GetExtraName() != nodeInfo2->GetExtraName()) {
1203       return false;
1204     }
1205
1206     switch (nodeType) {
1207       case ELEMENT_NODE: {
1208         // Both are elements (we checked that their nodeinfos are equal). Do the
1209         // check on attributes.
1210         Element* element1 = node1->AsElement();
1211         Element* element2 = node2->AsElement();
1212         uint32_t attrCount = element1->GetAttrCount();
1213         if (attrCount != element2->GetAttrCount()) {
1214           return false;
1215         }
1216
1217         // Iterate over attributes.
1218         for (uint32_t i = 0; i < attrCount; ++i) {
1219           const nsAttrName* attrName = element1->GetAttrNameAt(i);
1220 #ifdef DEBUG
1221           bool hasAttr =
1222 #endif
1223               element1->GetAttr(attrName->NamespaceID(), attrName->LocalName(),
1224                                 string1);
1225           NS_ASSERTION(hasAttr, "Why don't we have an attr?");
1226
1227           if (!element2->AttrValueIs(attrName->NamespaceID(),
1228                                      attrName->LocalName(), string1,
1229                                      eCaseMatters)) {
1230             return false;
1231           }
1232         }
1233         break;
1234       }
1235       case TEXT_NODE:
1236       case COMMENT_NODE:
1237       case CDATA_SECTION_NODE:
1238       case PROCESSING_INSTRUCTION_NODE: {
1239         MOZ_ASSERT(node1->IsCharacterData());
1240         MOZ_ASSERT(node2->IsCharacterData());
1241         auto* data1 = static_cast<CharacterData*>(node1);
1242         auto* data2 = static_cast<CharacterData*>(node2);
1243
1244         if (!data1->TextEquals(data2)) {
1245           return false;
1246         }
1247
1248         break;
1249       }
1250       case DOCUMENT_NODE:
1251       case DOCUMENT_FRAGMENT_NODE:
1252         break;
1253       case ATTRIBUTE_NODE: {
1254         NS_ASSERTION(node1 == this && node2 == aOther,
1255                      "Did we come upon an attribute node while walking a "
1256                      "subtree?");
1257         node1->GetNodeValue(string1);
1258         node2->GetNodeValue(string2);
1259
1260         // Returning here as to not bother walking subtree. And there is no
1261         // risk that we're half way through walking some other subtree since
1262         // attribute nodes doesn't appear in subtrees.
1263         return string1.Equals(string2);
1264       }
1265       case DOCUMENT_TYPE_NODE: {
1266         DocumentType* docType1 = static_cast<DocumentType*>(node1);
1267         DocumentType* docType2 = static_cast<DocumentType*>(node2);
1268
1269         // Public ID
1270         docType1->GetPublicId(string1);
1271         docType2->GetPublicId(string2);
1272         if (!string1.Equals(string2)) {
1273           return false;
1274         }
1275
1276         // System ID
1277         docType1->GetSystemId(string1);
1278         docType2->GetSystemId(string2);
1279         if (!string1.Equals(string2)) {
1280           return false;
1281         }
1282
1283         break;
1284       }
1285       default:
1286         MOZ_ASSERT(false, "Unknown node type");
1287     }
1288
1289     nsINode* nextNode = node1->GetFirstChild();
1290     if (nextNode) {
1291       node1 = nextNode;
1292       node2 = node2->GetFirstChild();
1293     } else {
1294       if (node2->GetFirstChild()) {
1295         // node2 has a firstChild, but node1 doesn't
1296         return false;
1297       }
1298
1299       // Find next sibling, possibly walking parent chain.
1300       while (1) {
1301         if (node1 == this) {
1302           NS_ASSERTION(node2 == aOther,
1303                        "Should have reached the start node "
1304                        "for both trees at the same time");
1305           return true;
1306         }
1307
1308         nextNode = node1->GetNextSibling();
1309         if (nextNode) {
1310           node1 = nextNode;
1311           node2 = node2->GetNextSibling();
1312           break;
1313         }
1314
1315         if (node2->GetNextSibling()) {
1316           // node2 has a nextSibling, but node1 doesn't
1317           return false;
1318         }
1319
1320         node1 = node1->GetParentNode();
1321         node2 = node2->GetParentNode();
1322         NS_ASSERTION(node1 && node2, "no parent while walking subtree");
1323       }
1324     }
1325   } while (node2);
1326
1327   return false;
1328 }
1329
1330 void nsINode::LookupNamespaceURI(const nsAString& aNamespacePrefix,
1331                                  nsAString& aNamespaceURI) {
1332   Element* element = GetNameSpaceElement();
1333   if (!element || NS_FAILED(element->LookupNamespaceURIInternal(
1334                       aNamespacePrefix, aNamespaceURI))) {
1335     SetDOMStringToNull(aNamespaceURI);
1336   }
1337 }
1338
1339 mozilla::Maybe<mozilla::dom::EventCallbackDebuggerNotificationType>
1340 nsINode::GetDebuggerNotificationType() const {
1341   return mozilla::Some(
1342       mozilla::dom::EventCallbackDebuggerNotificationType::Node);
1343 }
1344
1345 bool nsINode::ComputeDefaultWantsUntrusted(ErrorResult& aRv) {
1346   return !nsContentUtils::IsChromeDoc(OwnerDoc());
1347 }
1348
1349 void nsINode::GetBoxQuads(const BoxQuadOptions& aOptions,
1350                           nsTArray<RefPtr<DOMQuad>>& aResult,
1351                           CallerType aCallerType, mozilla::ErrorResult& aRv) {
1352   mozilla::GetBoxQuads(this, aOptions, aResult, aCallerType, aRv);
1353 }
1354
1355 void nsINode::GetBoxQuadsFromWindowOrigin(const BoxQuadOptions& aOptions,
1356                                           nsTArray<RefPtr<DOMQuad>>& aResult,
1357                                           mozilla::ErrorResult& aRv) {
1358   mozilla::GetBoxQuadsFromWindowOrigin(this, aOptions, aResult, aRv);
1359 }
1360
1361 already_AddRefed<DOMQuad> nsINode::ConvertQuadFromNode(
1362     DOMQuad& aQuad, const GeometryNode& aFrom,
1363     const ConvertCoordinateOptions& aOptions, CallerType aCallerType,
1364     ErrorResult& aRv) {
1365   return mozilla::ConvertQuadFromNode(this, aQuad, aFrom, aOptions, aCallerType,
1366                                       aRv);
1367 }
1368
1369 already_AddRefed<DOMQuad> nsINode::ConvertRectFromNode(
1370     DOMRectReadOnly& aRect, const GeometryNode& aFrom,
1371     const ConvertCoordinateOptions& aOptions, CallerType aCallerType,
1372     ErrorResult& aRv) {
1373   return mozilla::ConvertRectFromNode(this, aRect, aFrom, aOptions, aCallerType,
1374                                       aRv);
1375 }
1376
1377 already_AddRefed<DOMPoint> nsINode::ConvertPointFromNode(
1378     const DOMPointInit& aPoint, const GeometryNode& aFrom,
1379     const ConvertCoordinateOptions& aOptions, CallerType aCallerType,
1380     ErrorResult& aRv) {
1381   return mozilla::ConvertPointFromNode(this, aPoint, aFrom, aOptions,
1382                                        aCallerType, aRv);
1383 }
1384
1385 bool nsINode::DispatchEvent(Event& aEvent, CallerType aCallerType,
1386                             ErrorResult& aRv) {
1387   // XXX sXBL/XBL2 issue -- do we really want the owner here?  What
1388   // if that's the XBL document?  Would we want its presshell?  Or what?
1389   nsCOMPtr<Document> document = OwnerDoc();
1390
1391   // Do nothing if the element does not belong to a document
1392   if (!document) {
1393     return true;
1394   }
1395
1396   // Obtain a presentation shell
1397   RefPtr<nsPresContext> context = document->GetPresContext();
1398
1399   nsEventStatus status = nsEventStatus_eIgnore;
1400   nsresult rv = EventDispatcher::DispatchDOMEvent(this, nullptr, &aEvent,
1401                                                   context, &status);
1402   bool retval = !aEvent.DefaultPrevented(aCallerType);
1403   if (NS_FAILED(rv)) {
1404     aRv.Throw(rv);
1405   }
1406   return retval;
1407 }
1408
1409 nsresult nsINode::PostHandleEvent(EventChainPostVisitor& /*aVisitor*/) {
1410   return NS_OK;
1411 }
1412
1413 EventListenerManager* nsINode::GetOrCreateListenerManager() {
1414   return nsContentUtils::GetListenerManagerForNode(this);
1415 }
1416
1417 EventListenerManager* nsINode::GetExistingListenerManager() const {
1418   return nsContentUtils::GetExistingListenerManagerForNode(this);
1419 }
1420
1421 nsPIDOMWindowOuter* nsINode::GetOwnerGlobalForBindingsInternal() {
1422   bool dummy;
1423   // FIXME(bz): This cast is a bit bogus.  See
1424   // https://bugzilla.mozilla.org/show_bug.cgi?id=1515709
1425   auto* window = static_cast<nsGlobalWindowInner*>(
1426       OwnerDoc()->GetScriptHandlingObject(dummy));
1427   return window ? nsPIDOMWindowOuter::GetFromCurrentInner(window) : nullptr;
1428 }
1429
1430 nsIGlobalObject* nsINode::GetOwnerGlobal() const {
1431   bool dummy;
1432   return OwnerDoc()->GetScriptHandlingObject(dummy);
1433 }
1434
1435 bool nsINode::UnoptimizableCCNode() const {
1436   return IsInNativeAnonymousSubtree() || IsAttr();
1437 }
1438
1439 /* static */
1440 bool nsINode::Traverse(nsINode* tmp, nsCycleCollectionTraversalCallback& cb) {
1441   if (MOZ_LIKELY(!cb.WantAllTraces())) {
1442     Document* currentDoc = tmp->GetComposedDoc();
1443     if (currentDoc && nsCCUncollectableMarker::InGeneration(
1444                           currentDoc->GetMarkedCCGeneration())) {
1445       return false;
1446     }
1447
1448     if (nsCCUncollectableMarker::sGeneration) {
1449       // If we're black no need to traverse.
1450       if (tmp->HasKnownLiveWrapper() || tmp->InCCBlackTree()) {
1451         return false;
1452       }
1453
1454       if (!tmp->UnoptimizableCCNode()) {
1455         // If we're in a black document, return early.
1456         if ((currentDoc && currentDoc->HasKnownLiveWrapper())) {
1457           return false;
1458         }
1459         // If we're not in anonymous content and we have a black parent,
1460         // return early.
1461         nsIContent* parent = tmp->GetParent();
1462         if (parent && !parent->UnoptimizableCCNode() &&
1463             parent->HasKnownLiveWrapper()) {
1464           MOZ_ASSERT(parent->ComputeIndexOf(tmp).isSome(),
1465                      "Parent doesn't own us?");
1466           return false;
1467         }
1468       }
1469     }
1470   }
1471
1472   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mNodeInfo)
1473   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mFirstChild)
1474   NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mNextSibling)
1475   NS_IMPL_CYCLE_COLLECTION_TRAVERSE_RAWPTR(GetParent())
1476
1477   nsSlots* slots = tmp->GetExistingSlots();
1478   if (slots) {
1479     slots->Traverse(cb);
1480   }
1481
1482   if (tmp->HasProperties()) {
1483     nsCOMArray<nsISupports>* objects = static_cast<nsCOMArray<nsISupports>*>(
1484         tmp->GetProperty(nsGkAtoms::keepobjectsalive));
1485     if (objects) {
1486       for (int32_t i = 0; i < objects->Count(); ++i) {
1487         cb.NoteXPCOMChild(objects->ObjectAt(i));
1488       }
1489     }
1490
1491 #ifdef ACCESSIBILITY
1492     AccessibleNode* anode = static_cast<AccessibleNode*>(
1493         tmp->GetProperty(nsGkAtoms::accessiblenode));
1494     if (anode) {
1495       cb.NoteXPCOMChild(anode);
1496     }
1497 #endif
1498   }
1499
1500   if (tmp->NodeType() != DOCUMENT_NODE &&
1501       tmp->HasFlag(NODE_HAS_LISTENERMANAGER)) {
1502     nsContentUtils::TraverseListenerManager(tmp, cb);
1503   }
1504
1505   return true;
1506 }
1507
1508 /* static */
1509 void nsINode::Unlink(nsINode* tmp) {
1510   tmp->ReleaseWrapper(tmp);
1511
1512   if (nsSlots* slots = tmp->GetExistingSlots()) {
1513     slots->Unlink(*tmp);
1514   }
1515
1516   if (tmp->NodeType() != DOCUMENT_NODE &&
1517       tmp->HasFlag(NODE_HAS_LISTENERMANAGER)) {
1518     nsContentUtils::RemoveListenerManager(tmp);
1519     tmp->UnsetFlags(NODE_HAS_LISTENERMANAGER);
1520   }
1521
1522   if (tmp->HasProperties()) {
1523     tmp->RemoveProperty(nsGkAtoms::keepobjectsalive);
1524     tmp->RemoveProperty(nsGkAtoms::accessiblenode);
1525   }
1526 }
1527
1528 static void AdoptNodeIntoOwnerDoc(nsINode* aParent, nsINode* aNode,
1529                                   ErrorResult& aError) {
1530   NS_ASSERTION(!aNode->GetParentNode(),
1531                "Should have removed from parent already");
1532
1533   Document* doc = aParent->OwnerDoc();
1534
1535   DebugOnly<nsINode*> adoptedNode = doc->AdoptNode(*aNode, aError, true);
1536
1537 #ifdef DEBUG
1538   if (!aError.Failed()) {
1539     MOZ_ASSERT(aParent->OwnerDoc() == doc, "ownerDoc chainged while adopting");
1540     MOZ_ASSERT(adoptedNode == aNode, "Uh, adopt node changed nodes?");
1541     MOZ_ASSERT(aParent->OwnerDoc() == aNode->OwnerDoc(),
1542                "ownerDocument changed again after adopting!");
1543   }
1544 #endif  // DEBUG
1545 }
1546
1547 static nsresult UpdateGlobalsInSubtree(nsIContent* aRoot) {
1548   MOZ_ASSERT(ShouldUseNACScope(aRoot));
1549   // Start off with no global so we don't fire any error events on failure.
1550   AutoJSAPI jsapi;
1551   jsapi.Init();
1552
1553   JSContext* cx = jsapi.cx();
1554
1555   ErrorResult rv;
1556   JS::Rooted<JSObject*> reflector(cx);
1557   for (nsIContent* cur = aRoot; cur; cur = cur->GetNextNode(aRoot)) {
1558     if ((reflector = cur->GetWrapper())) {
1559       JSAutoRealm ar(cx, reflector);
1560       UpdateReflectorGlobal(cx, reflector, rv);
1561       rv.WouldReportJSException();
1562       if (rv.Failed()) {
1563         // We _could_ consider BlastSubtreeToPieces here, but it's not really
1564         // needed.  Having some nodes in here accessible to content while others
1565         // are not is probably OK.  We just need to fail out of the actual
1566         // insertion, so they're not in the DOM.  Returning a failure here will
1567         // do that.
1568         return rv.StealNSResult();
1569       }
1570     }
1571   }
1572
1573   return NS_OK;
1574 }
1575
1576 void nsINode::InsertChildBefore(nsIContent* aKid, nsIContent* aBeforeThis,
1577                                 bool aNotify, ErrorResult& aRv) {
1578   if (!IsContainerNode()) {
1579     aRv.ThrowHierarchyRequestError(
1580         "Parent is not a Document, DocumentFragment, or Element node.");
1581     return;
1582   }
1583
1584   MOZ_ASSERT(!aKid->GetParentNode(), "Inserting node that already has parent");
1585   MOZ_ASSERT(!IsAttr());
1586
1587   // The id-handling code, and in the future possibly other code, need to
1588   // react to unexpected attribute changes.
1589   nsMutationGuard::DidMutate();
1590
1591   // Do this before checking the child-count since this could cause mutations
1592   mozAutoDocUpdate updateBatch(GetComposedDoc(), aNotify);
1593
1594   if (OwnerDoc() != aKid->OwnerDoc()) {
1595     AdoptNodeIntoOwnerDoc(this, aKid, aRv);
1596     if (NS_WARN_IF(aRv.Failed())) {
1597       return;
1598     }
1599   }
1600
1601   if (!aBeforeThis) {
1602     AppendChildToChildList(aKid);
1603   } else {
1604     InsertChildToChildList(aKid, aBeforeThis);
1605   }
1606
1607   nsIContent* parent = IsContent() ? AsContent() : nullptr;
1608
1609   // XXXbz Do we even need this code anymore?
1610   bool wasInNACScope = ShouldUseNACScope(aKid);
1611   BindContext context(*this);
1612   aRv = aKid->BindToTree(context, *this);
1613   if (!aRv.Failed() && !wasInNACScope && ShouldUseNACScope(aKid)) {
1614     MOZ_ASSERT(ShouldUseNACScope(this),
1615                "Why does the kid need to use an the anonymous content scope?");
1616     aRv = UpdateGlobalsInSubtree(aKid);
1617   }
1618   if (aRv.Failed()) {
1619     DisconnectChild(aKid);
1620     aKid->UnbindFromTree();
1621     return;
1622   }
1623
1624   // Invalidate cached array of child nodes
1625   InvalidateChildNodes();
1626
1627   NS_ASSERTION(aKid->GetParentNode() == this,
1628                "Did we run script inappropriately?");
1629
1630   if (aNotify) {
1631     // Note that we always want to call ContentInserted when things are added
1632     // as kids to documents
1633     if (parent && !aBeforeThis) {
1634       MutationObservers::NotifyContentAppended(parent, aKid);
1635     } else {
1636       MutationObservers::NotifyContentInserted(this, aKid);
1637     }
1638
1639     if (nsContentUtils::HasMutationListeners(
1640             aKid, NS_EVENT_BITS_MUTATION_NODEINSERTED, this)) {
1641       InternalMutationEvent mutation(true, eLegacyNodeInserted);
1642       mutation.mRelatedNode = this;
1643
1644       mozAutoSubtreeModified subtree(OwnerDoc(), this);
1645       AsyncEventDispatcher::RunDOMEventWhenSafe(*aKid, mutation);
1646     }
1647   }
1648 }
1649
1650 nsIContent* nsINode::GetPreviousSibling() const {
1651   // Do not expose circular linked list
1652   if (mPreviousOrLastSibling && !mPreviousOrLastSibling->mNextSibling) {
1653     return nullptr;
1654   }
1655   return mPreviousOrLastSibling;
1656 }
1657
1658 // CACHE_POINTER_SHIFT indicates how many steps to downshift the |this| pointer.
1659 // It should be small enough to not cause collisions between adjecent objects,
1660 // and large enough to make sure that all indexes are used.
1661 #define CACHE_POINTER_SHIFT 6
1662 #define CACHE_NUM_SLOTS 128
1663 #define CACHE_CHILD_LIMIT 10
1664
1665 #define CACHE_GET_INDEX(_parent) \
1666   ((NS_PTR_TO_INT32(_parent) >> CACHE_POINTER_SHIFT) & (CACHE_NUM_SLOTS - 1))
1667
1668 struct IndexCacheSlot {
1669   const nsINode* mParent;
1670   const nsINode* mChild;
1671   uint32_t mChildIndex;
1672 };
1673
1674 static IndexCacheSlot sIndexCache[CACHE_NUM_SLOTS];
1675
1676 static inline void AddChildAndIndexToCache(const nsINode* aParent,
1677                                            const nsINode* aChild,
1678                                            uint32_t aChildIndex) {
1679   uint32_t index = CACHE_GET_INDEX(aParent);
1680   sIndexCache[index].mParent = aParent;
1681   sIndexCache[index].mChild = aChild;
1682   sIndexCache[index].mChildIndex = aChildIndex;
1683 }
1684
1685 static inline void GetChildAndIndexFromCache(const nsINode* aParent,
1686                                              const nsINode** aChild,
1687                                              Maybe<uint32_t>* aChildIndex) {
1688   uint32_t index = CACHE_GET_INDEX(aParent);
1689   if (sIndexCache[index].mParent == aParent) {
1690     *aChild = sIndexCache[index].mChild;
1691     *aChildIndex = Some(sIndexCache[index].mChildIndex);
1692   } else {
1693     *aChild = nullptr;
1694     *aChildIndex = Nothing();
1695   }
1696 }
1697
1698 static inline void RemoveFromCache(const nsINode* aParent) {
1699   uint32_t index = CACHE_GET_INDEX(aParent);
1700   if (sIndexCache[index].mParent == aParent) {
1701     sIndexCache[index] = {nullptr, nullptr, UINT32_MAX};
1702   }
1703 }
1704
1705 void nsINode::AppendChildToChildList(nsIContent* aKid) {
1706   MOZ_ASSERT(aKid);
1707   MOZ_ASSERT(!aKid->mNextSibling);
1708
1709   RemoveFromCache(this);
1710
1711   if (mFirstChild) {
1712     nsIContent* lastChild = GetLastChild();
1713     lastChild->mNextSibling = aKid;
1714     aKid->mPreviousOrLastSibling = lastChild;
1715   } else {
1716     mFirstChild = aKid;
1717   }
1718
1719   // Maintain link to the last child
1720   mFirstChild->mPreviousOrLastSibling = aKid;
1721   ++mChildCount;
1722 }
1723
1724 void nsINode::InsertChildToChildList(nsIContent* aKid,
1725                                      nsIContent* aNextSibling) {
1726   MOZ_ASSERT(aKid);
1727   MOZ_ASSERT(aNextSibling);
1728
1729   RemoveFromCache(this);
1730
1731   nsIContent* previousSibling = aNextSibling->mPreviousOrLastSibling;
1732   aNextSibling->mPreviousOrLastSibling = aKid;
1733   aKid->mPreviousOrLastSibling = previousSibling;
1734   aKid->mNextSibling = aNextSibling;
1735
1736   if (aNextSibling == mFirstChild) {
1737     MOZ_ASSERT(!previousSibling->mNextSibling);
1738     mFirstChild = aKid;
1739   } else {
1740     previousSibling->mNextSibling = aKid;
1741   }
1742
1743   ++mChildCount;
1744 }
1745
1746 void nsINode::DisconnectChild(nsIContent* aKid) {
1747   MOZ_ASSERT(aKid);
1748   MOZ_ASSERT(GetChildCount() > 0);
1749
1750   RemoveFromCache(this);
1751
1752   nsIContent* previousSibling = aKid->GetPreviousSibling();
1753   nsCOMPtr<nsIContent> ref = aKid;
1754
1755   if (aKid->mNextSibling) {
1756     aKid->mNextSibling->mPreviousOrLastSibling = aKid->mPreviousOrLastSibling;
1757   } else {
1758     // aKid is the last child in the list
1759     mFirstChild->mPreviousOrLastSibling = aKid->mPreviousOrLastSibling;
1760   }
1761   aKid->mPreviousOrLastSibling = nullptr;
1762
1763   if (previousSibling) {
1764     previousSibling->mNextSibling = std::move(aKid->mNextSibling);
1765   } else {
1766     // aKid is the first child in the list
1767     mFirstChild = std::move(aKid->mNextSibling);
1768   }
1769
1770   --mChildCount;
1771 }
1772
1773 nsIContent* nsINode::GetChildAt_Deprecated(uint32_t aIndex) const {
1774   if (aIndex >= GetChildCount()) {
1775     return nullptr;
1776   }
1777
1778   nsIContent* child = mFirstChild;
1779   while (aIndex--) {
1780     child = child->GetNextSibling();
1781   }
1782
1783   return child;
1784 }
1785
1786 int32_t nsINode::ComputeIndexOf_Deprecated(
1787     const nsINode* aPossibleChild) const {
1788   Maybe<uint32_t> maybeIndex = ComputeIndexOf(aPossibleChild);
1789   if (!maybeIndex) {
1790     return -1;
1791   }
1792   MOZ_ASSERT(*maybeIndex <= INT32_MAX,
1793              "ComputeIndexOf_Deprecated() returns unsupported index value, use "
1794              "ComputeIndex() instead");
1795   return static_cast<int32_t>(*maybeIndex);
1796 }
1797
1798 Maybe<uint32_t> nsINode::ComputeIndexOf(const nsINode* aPossibleChild) const {
1799   if (!aPossibleChild) {
1800     return Nothing();
1801   }
1802
1803   if (aPossibleChild->GetParentNode() != this) {
1804     return Nothing();
1805   }
1806
1807   if (aPossibleChild == GetLastChild()) {
1808     MOZ_ASSERT(GetChildCount());
1809     return Some(GetChildCount() - 1);
1810   }
1811
1812   if (mChildCount >= CACHE_CHILD_LIMIT) {
1813     const nsINode* child;
1814     Maybe<uint32_t> maybeChildIndex;
1815     GetChildAndIndexFromCache(this, &child, &maybeChildIndex);
1816     if (child) {
1817       if (child == aPossibleChild) {
1818         return maybeChildIndex;
1819       }
1820
1821       uint32_t nextIndex = *maybeChildIndex;
1822       uint32_t prevIndex = *maybeChildIndex;
1823       nsINode* prev = child->GetPreviousSibling();
1824       nsINode* next = child->GetNextSibling();
1825       do {
1826         if (next) {
1827           MOZ_ASSERT(nextIndex < UINT32_MAX);
1828           ++nextIndex;
1829           if (next == aPossibleChild) {
1830             AddChildAndIndexToCache(this, aPossibleChild, nextIndex);
1831             return Some(nextIndex);
1832           }
1833           next = next->GetNextSibling();
1834         }
1835         if (prev) {
1836           MOZ_ASSERT(prevIndex > 0);
1837           --prevIndex;
1838           if (prev == aPossibleChild) {
1839             AddChildAndIndexToCache(this, aPossibleChild, prevIndex);
1840             return Some(prevIndex);
1841           }
1842           prev = prev->GetPreviousSibling();
1843         }
1844       } while (prev || next);
1845     }
1846   }
1847
1848   uint32_t index = 0u;
1849   nsINode* current = mFirstChild;
1850   while (current) {
1851     MOZ_ASSERT(current->GetParentNode() == this);
1852     if (current == aPossibleChild) {
1853       if (mChildCount >= CACHE_CHILD_LIMIT) {
1854         AddChildAndIndexToCache(this, current, index);
1855       }
1856       return Some(index);
1857     }
1858     current = current->GetNextSibling();
1859     MOZ_ASSERT(index < UINT32_MAX);
1860     ++index;
1861   }
1862
1863   return Nothing();
1864 }
1865
1866 Maybe<uint32_t> nsINode::ComputeIndexInParentNode() const {
1867   nsINode* parent = GetParentNode();
1868   if (MOZ_UNLIKELY(!parent)) {
1869     return Nothing();
1870   }
1871   return parent->ComputeIndexOf(this);
1872 }
1873
1874 Maybe<uint32_t> nsINode::ComputeIndexInParentContent() const {
1875   nsIContent* parent = GetParent();
1876   if (MOZ_UNLIKELY(!parent)) {
1877     return Nothing();
1878   }
1879   return parent->ComputeIndexOf(this);
1880 }
1881
1882 static already_AddRefed<nsINode> GetNodeFromNodeOrString(
1883     const OwningNodeOrString& aNode, Document* aDocument) {
1884   if (aNode.IsNode()) {
1885     nsCOMPtr<nsINode> node = aNode.GetAsNode();
1886     return node.forget();
1887   }
1888
1889   if (aNode.IsString()) {
1890     RefPtr<nsTextNode> textNode =
1891         aDocument->CreateTextNode(aNode.GetAsString());
1892     return textNode.forget();
1893   }
1894
1895   MOZ_CRASH("Impossible type");
1896 }
1897
1898 /**
1899  * Implement the algorithm specified at
1900  * https://dom.spec.whatwg.org/#converting-nodes-into-a-node for |prepend()|,
1901  * |append()|, |before()|, |after()|, and |replaceWith()| APIs.
1902  */
1903 MOZ_CAN_RUN_SCRIPT static already_AddRefed<nsINode>
1904 ConvertNodesOrStringsIntoNode(const Sequence<OwningNodeOrString>& aNodes,
1905                               Document* aDocument, ErrorResult& aRv) {
1906   if (aNodes.Length() == 1) {
1907     return GetNodeFromNodeOrString(aNodes[0], aDocument);
1908   }
1909
1910   nsCOMPtr<nsINode> fragment = aDocument->CreateDocumentFragment();
1911
1912   for (const auto& node : aNodes) {
1913     nsCOMPtr<nsINode> childNode = GetNodeFromNodeOrString(node, aDocument);
1914     fragment->AppendChild(*childNode, aRv);
1915     if (aRv.Failed()) {
1916       return nullptr;
1917     }
1918   }
1919
1920   return fragment.forget();
1921 }
1922
1923 static void InsertNodesIntoHashset(const Sequence<OwningNodeOrString>& aNodes,
1924                                    nsTHashSet<nsINode*>& aHashset) {
1925   for (const auto& node : aNodes) {
1926     if (node.IsNode()) {
1927       aHashset.Insert(node.GetAsNode());
1928     }
1929   }
1930 }
1931
1932 static nsINode* FindViablePreviousSibling(
1933     const nsINode& aNode, const Sequence<OwningNodeOrString>& aNodes) {
1934   nsTHashSet<nsINode*> nodeSet(16);
1935   InsertNodesIntoHashset(aNodes, nodeSet);
1936
1937   nsINode* viablePreviousSibling = nullptr;
1938   for (nsINode* sibling = aNode.GetPreviousSibling(); sibling;
1939        sibling = sibling->GetPreviousSibling()) {
1940     if (!nodeSet.Contains(sibling)) {
1941       viablePreviousSibling = sibling;
1942       break;
1943     }
1944   }
1945
1946   return viablePreviousSibling;
1947 }
1948
1949 static nsINode* FindViableNextSibling(
1950     const nsINode& aNode, const Sequence<OwningNodeOrString>& aNodes) {
1951   nsTHashSet<nsINode*> nodeSet(16);
1952   InsertNodesIntoHashset(aNodes, nodeSet);
1953
1954   nsINode* viableNextSibling = nullptr;
1955   for (nsINode* sibling = aNode.GetNextSibling(); sibling;
1956        sibling = sibling->GetNextSibling()) {
1957     if (!nodeSet.Contains(sibling)) {
1958       viableNextSibling = sibling;
1959       break;
1960     }
1961   }
1962
1963   return viableNextSibling;
1964 }
1965
1966 void nsINode::Before(const Sequence<OwningNodeOrString>& aNodes,
1967                      ErrorResult& aRv) {
1968   nsCOMPtr<nsINode> parent = GetParentNode();
1969   if (!parent) {
1970     return;
1971   }
1972
1973   nsCOMPtr<nsINode> viablePreviousSibling =
1974       FindViablePreviousSibling(*this, aNodes);
1975
1976   nsCOMPtr<Document> doc = OwnerDoc();
1977   nsCOMPtr<nsINode> node = ConvertNodesOrStringsIntoNode(aNodes, doc, aRv);
1978   if (aRv.Failed()) {
1979     return;
1980   }
1981
1982   viablePreviousSibling = viablePreviousSibling
1983                               ? viablePreviousSibling->GetNextSibling()
1984                               : parent->GetFirstChild();
1985
1986   parent->InsertBefore(*node, viablePreviousSibling, aRv);
1987 }
1988
1989 void nsINode::After(const Sequence<OwningNodeOrString>& aNodes,
1990                     ErrorResult& aRv) {
1991   nsCOMPtr<nsINode> parent = GetParentNode();
1992   if (!parent) {
1993     return;
1994   }
1995
1996   nsCOMPtr<nsINode> viableNextSibling = FindViableNextSibling(*this, aNodes);
1997
1998   nsCOMPtr<Document> doc = OwnerDoc();
1999   nsCOMPtr<nsINode> node = ConvertNodesOrStringsIntoNode(aNodes, doc, aRv);
2000   if (aRv.Failed()) {
2001     return;
2002   }
2003
2004   parent->InsertBefore(*node, viableNextSibling, aRv);
2005 }
2006
2007 void nsINode::ReplaceWith(const Sequence<OwningNodeOrString>& aNodes,
2008                           ErrorResult& aRv) {
2009   nsCOMPtr<nsINode> parent = GetParentNode();
2010   if (!parent) {
2011     return;
2012   }
2013
2014   nsCOMPtr<nsINode> viableNextSibling = FindViableNextSibling(*this, aNodes);
2015
2016   nsCOMPtr<Document> doc = OwnerDoc();
2017   nsCOMPtr<nsINode> node = ConvertNodesOrStringsIntoNode(aNodes, doc, aRv);
2018   if (aRv.Failed()) {
2019     return;
2020   }
2021
2022   if (parent == GetParentNode()) {
2023     parent->ReplaceChild(*node, *this, aRv);
2024   } else {
2025     parent->InsertBefore(*node, viableNextSibling, aRv);
2026   }
2027 }
2028
2029 void nsINode::Remove() {
2030   nsCOMPtr<nsINode> parent = GetParentNode();
2031   if (!parent) {
2032     return;
2033   }
2034
2035   parent->RemoveChild(*this, IgnoreErrors());
2036 }
2037
2038 Element* nsINode::GetFirstElementChild() const {
2039   for (nsIContent* child = GetFirstChild(); child;
2040        child = child->GetNextSibling()) {
2041     if (child->IsElement()) {
2042       return child->AsElement();
2043     }
2044   }
2045
2046   return nullptr;
2047 }
2048
2049 Element* nsINode::GetLastElementChild() const {
2050   for (nsIContent* child = GetLastChild(); child;
2051        child = child->GetPreviousSibling()) {
2052     if (child->IsElement()) {
2053       return child->AsElement();
2054     }
2055   }
2056
2057   return nullptr;
2058 }
2059
2060 static bool MatchAttribute(Element* aElement, int32_t aNamespaceID,
2061                            nsAtom* aAttrName, void* aData) {
2062   MOZ_ASSERT(aElement, "Must have content node to work with!");
2063   nsString* attrValue = static_cast<nsString*>(aData);
2064   if (aNamespaceID != kNameSpaceID_Unknown &&
2065       aNamespaceID != kNameSpaceID_Wildcard) {
2066     return attrValue->EqualsLiteral("*")
2067                ? aElement->HasAttr(aNamespaceID, aAttrName)
2068                : aElement->AttrValueIs(aNamespaceID, aAttrName, *attrValue,
2069                                        eCaseMatters);
2070   }
2071
2072   // Qualified name match. This takes more work.
2073   uint32_t count = aElement->GetAttrCount();
2074   for (uint32_t i = 0; i < count; ++i) {
2075     const nsAttrName* name = aElement->GetAttrNameAt(i);
2076     bool nameMatch;
2077     if (name->IsAtom()) {
2078       nameMatch = name->Atom() == aAttrName;
2079     } else if (aNamespaceID == kNameSpaceID_Wildcard) {
2080       nameMatch = name->NodeInfo()->Equals(aAttrName);
2081     } else {
2082       nameMatch = name->NodeInfo()->QualifiedNameEquals(aAttrName);
2083     }
2084
2085     if (nameMatch) {
2086       return attrValue->EqualsLiteral("*") ||
2087              aElement->AttrValueIs(name->NamespaceID(), name->LocalName(),
2088                                    *attrValue, eCaseMatters);
2089     }
2090   }
2091
2092   return false;
2093 }
2094
2095 already_AddRefed<nsIHTMLCollection> nsINode::GetElementsByAttribute(
2096     const nsAString& aAttribute, const nsAString& aValue) {
2097   RefPtr<nsAtom> attrAtom(NS_Atomize(aAttribute));
2098   RefPtr<nsContentList> list = new nsContentList(
2099       this, MatchAttribute, nsContentUtils::DestroyMatchString,
2100       new nsString(aValue), true, attrAtom, kNameSpaceID_Unknown);
2101
2102   return list.forget();
2103 }
2104
2105 already_AddRefed<nsIHTMLCollection> nsINode::GetElementsByAttributeNS(
2106     const nsAString& aNamespaceURI, const nsAString& aAttribute,
2107     const nsAString& aValue, ErrorResult& aRv) {
2108   RefPtr<nsAtom> attrAtom(NS_Atomize(aAttribute));
2109
2110   int32_t nameSpaceId = kNameSpaceID_Wildcard;
2111   if (!aNamespaceURI.EqualsLiteral("*")) {
2112     nsresult rv = nsNameSpaceManager::GetInstance()->RegisterNameSpace(
2113         aNamespaceURI, nameSpaceId);
2114     if (NS_FAILED(rv)) {
2115       aRv.Throw(rv);
2116       return nullptr;
2117     }
2118   }
2119
2120   RefPtr<nsContentList> list = new nsContentList(
2121       this, MatchAttribute, nsContentUtils::DestroyMatchString,
2122       new nsString(aValue), true, attrAtom, nameSpaceId);
2123   return list.forget();
2124 }
2125
2126 void nsINode::Prepend(const Sequence<OwningNodeOrString>& aNodes,
2127                       ErrorResult& aRv) {
2128   nsCOMPtr<Document> doc = OwnerDoc();
2129   nsCOMPtr<nsINode> node = ConvertNodesOrStringsIntoNode(aNodes, doc, aRv);
2130   if (aRv.Failed()) {
2131     return;
2132   }
2133
2134   nsCOMPtr<nsIContent> refNode = mFirstChild;
2135   InsertBefore(*node, refNode, aRv);
2136 }
2137
2138 void nsINode::Append(const Sequence<OwningNodeOrString>& aNodes,
2139                      ErrorResult& aRv) {
2140   nsCOMPtr<Document> doc = OwnerDoc();
2141   nsCOMPtr<nsINode> node = ConvertNodesOrStringsIntoNode(aNodes, doc, aRv);
2142   if (aRv.Failed()) {
2143     return;
2144   }
2145
2146   AppendChild(*node, aRv);
2147 }
2148
2149 // https://dom.spec.whatwg.org/#dom-parentnode-replacechildren
2150 void nsINode::ReplaceChildren(const Sequence<OwningNodeOrString>& aNodes,
2151                               ErrorResult& aRv) {
2152   nsCOMPtr<Document> doc = OwnerDoc();
2153   nsCOMPtr<nsINode> node = ConvertNodesOrStringsIntoNode(aNodes, doc, aRv);
2154   if (aRv.Failed()) {
2155     return;
2156   }
2157   MOZ_ASSERT(node);
2158   return ReplaceChildren(node, aRv);
2159 }
2160
2161 void nsINode::ReplaceChildren(nsINode* aNode, ErrorResult& aRv) {
2162   if (aNode) {
2163     EnsurePreInsertionValidity(*aNode, nullptr, aRv);
2164     if (aRv.Failed()) {
2165       return;
2166     }
2167   }
2168   nsCOMPtr<nsINode> node = aNode;
2169
2170   // Batch possible DOMSubtreeModified events.
2171   mozAutoSubtreeModified subtree(OwnerDoc(), nullptr);
2172
2173   if (nsContentUtils::HasMutationListeners(
2174           OwnerDoc(), NS_EVENT_BITS_MUTATION_NODEREMOVED)) {
2175     FireNodeRemovedForChildren();
2176     if (node) {
2177       if (node->NodeType() == DOCUMENT_FRAGMENT_NODE) {
2178         node->FireNodeRemovedForChildren();
2179       } else if (nsCOMPtr<nsINode> parent = node->GetParentNode()) {
2180         nsContentUtils::MaybeFireNodeRemoved(node, parent);
2181       }
2182     }
2183   }
2184
2185   // Needed when used in combination with contenteditable (maybe)
2186   mozAutoDocUpdate updateBatch(OwnerDoc(), true);
2187
2188   nsAutoMutationBatch mb(this, true, true);
2189
2190   // The code above explicitly dispatched DOMNodeRemoved events if needed.
2191   nsAutoScriptBlockerSuppressNodeRemoved scriptBlocker;
2192
2193   // Replace all with node within this.
2194   while (mFirstChild) {
2195     RemoveChildNode(mFirstChild, true);
2196   }
2197   mb.RemovalDone();
2198
2199   if (aNode) {
2200     AppendChild(*aNode, aRv);
2201     mb.NodesAdded();
2202   }
2203 }
2204
2205 void nsINode::RemoveChildNode(nsIContent* aKid, bool aNotify) {
2206   // NOTE: This function must not trigger any calls to
2207   // Document::GetRootElement() calls until *after* it has removed aKid from
2208   // aChildArray. Any calls before then could potentially restore a stale
2209   // value for our cached root element, per note in
2210   // Document::RemoveChildNode().
2211   MOZ_ASSERT(aKid && aKid->GetParentNode() == this, "Bogus aKid");
2212   MOZ_ASSERT(!IsAttr());
2213
2214   nsMutationGuard::DidMutate();
2215   mozAutoDocUpdate updateBatch(GetComposedDoc(), aNotify);
2216
2217   nsIContent* previousSibling = aKid->GetPreviousSibling();
2218
2219   // Since aKid is use also after DisconnectChild, ensure it stays alive.
2220   nsCOMPtr<nsIContent> kungfuDeathGrip = aKid;
2221   DisconnectChild(aKid);
2222
2223   // Invalidate cached array of child nodes
2224   InvalidateChildNodes();
2225
2226   if (aNotify) {
2227     MutationObservers::NotifyContentRemoved(this, aKid, previousSibling);
2228   }
2229
2230   aKid->UnbindFromTree();
2231 }
2232
2233 // When replacing, aRefChild is the content being replaced; when
2234 // inserting it's the content before which we're inserting.  In the
2235 // latter case it may be null.
2236 //
2237 // If aRv is a failure after this call, the insertion should not happen.
2238 //
2239 // This implements the parts of
2240 // https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity and
2241 // the checks in https://dom.spec.whatwg.org/#concept-node-replace that
2242 // depend on the child nodes or come after steps that depend on the child nodes
2243 // (steps 2-6 in both cases).
2244 static void EnsureAllowedAsChild(nsINode* aNewChild, nsINode* aParent,
2245                                  bool aIsReplace, nsINode* aRefChild,
2246                                  ErrorResult& aRv) {
2247   MOZ_ASSERT(aNewChild, "Must have new child");
2248   MOZ_ASSERT_IF(aIsReplace, aRefChild);
2249   MOZ_ASSERT(aParent);
2250   MOZ_ASSERT(aParent->IsDocument() || aParent->IsDocumentFragment() ||
2251                  aParent->IsElement(),
2252              "Nodes that are not documents, document fragments or elements "
2253              "can't be parents!");
2254
2255   // Step 2.
2256   // A common case is that aNewChild has no kids, in which case
2257   // aParent can't be a descendant of aNewChild unless they're
2258   // actually equal to each other.  Fast-path that case, since aParent
2259   // could be pretty deep in the DOM tree.
2260   if (aNewChild == aParent ||
2261       ((aNewChild->GetFirstChild() ||
2262         // HTML template elements and ShadowRoot hosts need
2263         // to be checked to ensure that they are not inserted into
2264         // the hosted content.
2265         aNewChild->NodeInfo()->NameAtom() == nsGkAtoms::_template ||
2266         (aNewChild->IsElement() && aNewChild->AsElement()->GetShadowRoot())) &&
2267        nsContentUtils::ContentIsHostIncludingDescendantOf(aParent,
2268                                                           aNewChild))) {
2269     aRv.ThrowHierarchyRequestError(
2270         "The new child is an ancestor of the parent");
2271     return;
2272   }
2273
2274   // Step 3.
2275   if (aRefChild && aRefChild->GetParentNode() != aParent) {
2276     if (aIsReplace) {
2277       if (aNewChild->GetParentNode() == aParent) {
2278         aRv.ThrowNotFoundError(
2279             "New child already has this parent and old child does not. Please "
2280             "check the order of replaceChild's arguments.");
2281       } else {
2282         aRv.ThrowNotFoundError(
2283             "Child to be replaced is not a child of this node");
2284       }
2285     } else {
2286       aRv.ThrowNotFoundError(
2287           "Child to insert before is not a child of this node");
2288     }
2289     return;
2290   }
2291
2292   // Step 4.
2293   if (!aNewChild->IsContent()) {
2294     aRv.ThrowHierarchyRequestError(nsPrintfCString(
2295         "May not add %s as a child", NodeTypeAsString(aNewChild)));
2296     return;
2297   }
2298
2299   // Steps 5 and 6 combined.
2300   // The allowed child nodes differ for documents and elements
2301   switch (aNewChild->NodeType()) {
2302     case nsINode::COMMENT_NODE:
2303     case nsINode::PROCESSING_INSTRUCTION_NODE:
2304       // OK in both cases
2305       return;
2306     case nsINode::TEXT_NODE:
2307     case nsINode::CDATA_SECTION_NODE:
2308     case nsINode::ENTITY_REFERENCE_NODE:
2309       // Allowed under Elements and DocumentFragments
2310       if (aParent->NodeType() == nsINode::DOCUMENT_NODE) {
2311         aRv.ThrowHierarchyRequestError(
2312             nsPrintfCString("Cannot insert %s as a child of a Document",
2313                             NodeTypeAsString(aNewChild)));
2314       }
2315       return;
2316     case nsINode::ELEMENT_NODE: {
2317       if (!aParent->IsDocument()) {
2318         // Always ok to have elements under other elements or document fragments
2319         return;
2320       }
2321
2322       Document* parentDocument = aParent->AsDocument();
2323       Element* rootElement = parentDocument->GetRootElement();
2324       if (rootElement) {
2325         // Already have a documentElement, so this is only OK if we're
2326         // replacing it.
2327         if (!aIsReplace || rootElement != aRefChild) {
2328           aRv.ThrowHierarchyRequestError(
2329               "Cannot have more than one Element child of a Document");
2330         }
2331         return;
2332       }
2333
2334       // We don't have a documentElement yet.  Our one remaining constraint is
2335       // that the documentElement must come after the doctype.
2336       if (!aRefChild) {
2337         // Appending is just fine.
2338         return;
2339       }
2340
2341       nsIContent* docTypeContent = parentDocument->GetDoctype();
2342       if (!docTypeContent) {
2343         // It's all good.
2344         return;
2345       }
2346
2347       // The docTypeContent is retrived from the child list of the Document
2348       // node so that doctypeIndex is never Nothing.
2349       const Maybe<uint32_t> doctypeIndex =
2350           aParent->ComputeIndexOf(docTypeContent);
2351       MOZ_ASSERT(doctypeIndex.isSome());
2352       // If aRefChild is an NAC, its index can be Nothing.
2353       const Maybe<uint32_t> insertIndex = aParent->ComputeIndexOf(aRefChild);
2354
2355       // Now we're OK in the following two cases only:
2356       // 1) We're replacing something that's not before the doctype
2357       // 2) We're inserting before something that comes after the doctype
2358       const bool ok = MOZ_LIKELY(insertIndex.isSome()) &&
2359                       (aIsReplace ? *insertIndex >= *doctypeIndex
2360                                   : *insertIndex > *doctypeIndex);
2361       if (!ok) {
2362         aRv.ThrowHierarchyRequestError(
2363             "Cannot insert a root element before the doctype");
2364       }
2365       return;
2366     }
2367     case nsINode::DOCUMENT_TYPE_NODE: {
2368       if (!aParent->IsDocument()) {
2369         // doctypes only allowed under documents
2370         aRv.ThrowHierarchyRequestError(
2371             nsPrintfCString("Cannot insert a DocumentType as a child of %s",
2372                             NodeTypeAsString(aParent)));
2373         return;
2374       }
2375
2376       Document* parentDocument = aParent->AsDocument();
2377       nsIContent* docTypeContent = parentDocument->GetDoctype();
2378       if (docTypeContent) {
2379         // Already have a doctype, so this is only OK if we're replacing it
2380         if (!aIsReplace || docTypeContent != aRefChild) {
2381           aRv.ThrowHierarchyRequestError(
2382               "Cannot have more than one DocumentType child of a Document");
2383         }
2384         return;
2385       }
2386
2387       // We don't have a doctype yet.  Our one remaining constraint is
2388       // that the doctype must come before the documentElement.
2389       Element* rootElement = parentDocument->GetRootElement();
2390       if (!rootElement) {
2391         // It's all good
2392         return;
2393       }
2394
2395       if (!aRefChild) {
2396         // Trying to append a doctype, but have a documentElement
2397         aRv.ThrowHierarchyRequestError(
2398             "Cannot have a DocumentType node after the root element");
2399         return;
2400       }
2401
2402       // rootElement is now in the child list of the Document node so that
2403       // ComputeIndexOf must success to find it.
2404       const Maybe<uint32_t> rootIndex = aParent->ComputeIndexOf(rootElement);
2405       MOZ_ASSERT(rootIndex.isSome());
2406       const Maybe<uint32_t> insertIndex = aParent->ComputeIndexOf(aRefChild);
2407
2408       // Now we're OK if and only if insertIndex <= rootIndex.  Indeed, either
2409       // we end up replacing aRefChild or we end up before it.  Either one is
2410       // ok as long as aRefChild is not after rootElement.
2411       if (MOZ_LIKELY(insertIndex.isSome()) && *insertIndex > *rootIndex) {
2412         aRv.ThrowHierarchyRequestError(
2413             "Cannot have a DocumentType node after the root element");
2414       }
2415       return;
2416     }
2417     case nsINode::DOCUMENT_FRAGMENT_NODE: {
2418       // Note that for now we only allow nodes inside document fragments if
2419       // they're allowed inside elements.  If we ever change this to allow
2420       // doctype nodes in document fragments, we'll need to update this code.
2421       // Also, there's a version of this code in ReplaceOrInsertBefore.  If you
2422       // change this code, change that too.
2423       if (!aParent->IsDocument()) {
2424         // All good here
2425         return;
2426       }
2427
2428       bool sawElement = false;
2429       for (nsIContent* child = aNewChild->GetFirstChild(); child;
2430            child = child->GetNextSibling()) {
2431         if (child->IsElement()) {
2432           if (sawElement) {
2433             // Can't put two elements into a document
2434             aRv.ThrowHierarchyRequestError(
2435                 "Cannot have more than one Element child of a Document");
2436             return;
2437           }
2438           sawElement = true;
2439         }
2440         // If we can put this content at the right place, we might be ok;
2441         // if not, we bail out.
2442         EnsureAllowedAsChild(child, aParent, aIsReplace, aRefChild, aRv);
2443         if (aRv.Failed()) {
2444           return;
2445         }
2446       }
2447
2448       // Everything in the fragment checked out ok, so we can stick it in here
2449       return;
2450     }
2451     default:
2452       /*
2453        * aNewChild is of invalid type.
2454        */
2455       break;
2456   }
2457
2458   // XXXbz when can we reach this?
2459   aRv.ThrowHierarchyRequestError(nsPrintfCString("Cannot insert %s inside %s",
2460                                                  NodeTypeAsString(aNewChild),
2461                                                  NodeTypeAsString(aParent)));
2462 }
2463
2464 // Implements
2465 // https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity
2466 void nsINode::EnsurePreInsertionValidity(nsINode& aNewChild, nsINode* aRefChild,
2467                                          ErrorResult& aError) {
2468   EnsurePreInsertionValidity1(aError);
2469   if (aError.Failed()) {
2470     return;
2471   }
2472   EnsurePreInsertionValidity2(false, aNewChild, aRefChild, aError);
2473 }
2474
2475 // Implements the parts of
2476 // https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity and
2477 // the checks in https://dom.spec.whatwg.org/#concept-node-replace that can be
2478 // evaluated before ever looking at the child nodes (step 1 in both cases).
2479 void nsINode::EnsurePreInsertionValidity1(ErrorResult& aError) {
2480   if (!IsDocument() && !IsDocumentFragment() && !IsElement()) {
2481     aError.ThrowHierarchyRequestError(
2482         nsPrintfCString("Cannot add children to %s", NodeTypeAsString(this)));
2483     return;
2484   }
2485 }
2486
2487 void nsINode::EnsurePreInsertionValidity2(bool aReplace, nsINode& aNewChild,
2488                                           nsINode* aRefChild,
2489                                           ErrorResult& aError) {
2490   if (aNewChild.IsRootOfNativeAnonymousSubtree()) {
2491     // This is anonymous content.  Don't allow its insertion
2492     // anywhere, since it might have UnbindFromTree calls coming
2493     // its way.
2494     aError.ThrowNotSupportedError(
2495         "Inserting anonymous content manually is not supported");
2496     return;
2497   }
2498
2499   // Make sure that the inserted node is allowed as a child of its new parent.
2500   EnsureAllowedAsChild(&aNewChild, this, aReplace, aRefChild, aError);
2501 }
2502
2503 nsINode* nsINode::ReplaceOrInsertBefore(bool aReplace, nsINode* aNewChild,
2504                                         nsINode* aRefChild,
2505                                         ErrorResult& aError) {
2506   // XXXbz I wish I could assert that nsContentUtils::IsSafeToRunScript() so we
2507   // could rely on scriptblockers going out of scope to actually run XBL
2508   // teardown, but various crud adds nodes under scriptblockers (e.g. native
2509   // anonymous content).  The only good news is those insertions can't trigger
2510   // the bad XBL cases.
2511   MOZ_ASSERT_IF(aReplace, aRefChild);
2512
2513   // Before firing DOMNodeRemoved events, make sure this is actually an insert
2514   // we plan to do.
2515   EnsurePreInsertionValidity1(aError);
2516   if (aError.Failed()) {
2517     return nullptr;
2518   }
2519
2520   EnsurePreInsertionValidity2(aReplace, *aNewChild, aRefChild, aError);
2521   if (aError.Failed()) {
2522     return nullptr;
2523   }
2524
2525   uint16_t nodeType = aNewChild->NodeType();
2526
2527   // Before we do anything else, fire all DOMNodeRemoved mutation events
2528   // We do this up front as to avoid having to deal with script running
2529   // at random places further down.
2530   // Scope firing mutation events so that we don't carry any state that
2531   // might be stale
2532   {
2533     nsMutationGuard guard;
2534
2535     // If we're replacing, fire for node-to-be-replaced.
2536     // If aRefChild == aNewChild then we'll fire for it in check below
2537     if (aReplace && aRefChild != aNewChild) {
2538       nsContentUtils::MaybeFireNodeRemoved(aRefChild, this);
2539     }
2540
2541     // If the new node already has a parent, fire for removing from old
2542     // parent
2543     if (nsCOMPtr<nsINode> oldParent = aNewChild->GetParentNode()) {
2544       nsContentUtils::MaybeFireNodeRemoved(aNewChild, oldParent);
2545     }
2546
2547     // If we're inserting a fragment, fire for all the children of the
2548     // fragment
2549     if (nodeType == DOCUMENT_FRAGMENT_NODE) {
2550       static_cast<FragmentOrElement*>(aNewChild)->FireNodeRemovedForChildren();
2551     }
2552
2553     if (guard.Mutated(0)) {
2554       // Re-check the parts of our pre-insertion validity that might depend on
2555       // the tree shape.
2556       EnsurePreInsertionValidity2(aReplace, *aNewChild, aRefChild, aError);
2557       if (aError.Failed()) {
2558         return nullptr;
2559       }
2560     }
2561   }
2562
2563   // Record the node to insert before, if any
2564   nsIContent* nodeToInsertBefore;
2565   if (aReplace) {
2566     nodeToInsertBefore = aRefChild->GetNextSibling();
2567   } else {
2568     // Since aRefChild is our child, it must be an nsIContent object.
2569     nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;
2570   }
2571   if (nodeToInsertBefore == aNewChild) {
2572     // We're going to remove aNewChild from its parent, so use its next sibling
2573     // as the node to insert before.
2574     nodeToInsertBefore = nodeToInsertBefore->GetNextSibling();
2575   }
2576
2577   Maybe<AutoTArray<nsCOMPtr<nsIContent>, 50>> fragChildren;
2578
2579   // Remove the new child from the old parent if one exists
2580   nsIContent* newContent = aNewChild->AsContent();
2581   nsCOMPtr<nsINode> oldParent = newContent->GetParentNode();
2582   if (oldParent) {
2583     // Hold a strong ref to nodeToInsertBefore across the removal of newContent
2584     nsCOMPtr<nsINode> kungFuDeathGrip = nodeToInsertBefore;
2585
2586     // Removing a child can run script, via XBL destructors.
2587     nsMutationGuard guard;
2588
2589     // Scope for the mutation batch and scriptblocker, so they go away
2590     // while kungFuDeathGrip is still alive.
2591     {
2592       mozAutoDocUpdate batch(newContent->GetComposedDoc(), true);
2593       nsAutoMutationBatch mb(oldParent, true, true);
2594       // ScriptBlocker ensures previous and next stay alive.
2595       nsIContent* previous = aNewChild->GetPreviousSibling();
2596       nsIContent* next = aNewChild->GetNextSibling();
2597       oldParent->RemoveChildNode(aNewChild->AsContent(), true);
2598       if (nsAutoMutationBatch::GetCurrentBatch() == &mb) {
2599         mb.RemovalDone();
2600         mb.SetPrevSibling(previous);
2601         mb.SetNextSibling(next);
2602       }
2603     }
2604
2605     // We expect one mutation (the removal) to have happened.
2606     if (guard.Mutated(1)) {
2607       // XBL destructors, yuck.
2608
2609       // Verify that newContent has no parent.
2610       if (newContent->GetParentNode()) {
2611         aError.ThrowHierarchyRequestError(
2612             "New child was inserted somewhere else");
2613         return nullptr;
2614       }
2615
2616       // And verify that newContent is still allowed as our child.
2617       if (aNewChild == aRefChild) {
2618         // We've already removed aRefChild.  So even if we were doing a replace,
2619         // now we're doing a simple insert before nodeToInsertBefore.
2620         EnsureAllowedAsChild(newContent, this, false, nodeToInsertBefore,
2621                              aError);
2622         if (aError.Failed()) {
2623           return nullptr;
2624         }
2625       } else {
2626         EnsureAllowedAsChild(newContent, this, aReplace, aRefChild, aError);
2627         if (aError.Failed()) {
2628           return nullptr;
2629         }
2630
2631         // And recompute nodeToInsertBefore, just in case.
2632         if (aReplace) {
2633           nodeToInsertBefore = aRefChild->GetNextSibling();
2634         } else {
2635           nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;
2636         }
2637       }
2638     }
2639   } else if (nodeType == DOCUMENT_FRAGMENT_NODE) {
2640     // Make sure to remove all the fragment's kids.  We need to do this before
2641     // we start inserting anything, so we will run out XBL destructors and
2642     // binding teardown (GOD, I HATE THESE THINGS) before we insert anything
2643     // into the DOM.
2644     uint32_t count = newContent->GetChildCount();
2645
2646     fragChildren.emplace();
2647
2648     // Copy the children into a separate array to avoid having to deal with
2649     // mutations to the fragment later on here.
2650     fragChildren->SetCapacity(count);
2651     for (nsIContent* child = newContent->GetFirstChild(); child;
2652          child = child->GetNextSibling()) {
2653       NS_ASSERTION(child->GetUncomposedDoc() == nullptr,
2654                    "How did we get a child with a current doc?");
2655       fragChildren->AppendElement(child);
2656     }
2657
2658     // Hold a strong ref to nodeToInsertBefore across the removals
2659     nsCOMPtr<nsINode> kungFuDeathGrip = nodeToInsertBefore;
2660
2661     nsMutationGuard guard;
2662
2663     // Scope for the mutation batch and scriptblocker, so they go away
2664     // while kungFuDeathGrip is still alive.
2665     {
2666       mozAutoDocUpdate batch(newContent->GetComposedDoc(), true);
2667       nsAutoMutationBatch mb(newContent, false, true);
2668
2669       while (newContent->HasChildren()) {
2670         newContent->RemoveChildNode(newContent->GetLastChild(), true);
2671       }
2672     }
2673
2674     // We expect |count| removals
2675     if (guard.Mutated(count)) {
2676       // XBL destructors, yuck.
2677
2678       // Verify that nodeToInsertBefore, if non-null, is still our child.  If
2679       // it's not, there's no way we can do this insert sanely; just bail out.
2680       if (nodeToInsertBefore && nodeToInsertBefore->GetParent() != this) {
2681         aError.ThrowHierarchyRequestError("Don't know where to insert child");
2682         return nullptr;
2683       }
2684
2685       // Verify that all the things in fragChildren have no parent.
2686       for (uint32_t i = 0; i < count; ++i) {
2687         if (fragChildren->ElementAt(i)->GetParentNode()) {
2688           aError.ThrowHierarchyRequestError(
2689               "New child was inserted somewhere else");
2690           return nullptr;
2691         }
2692       }
2693
2694       // Note that unlike the single-element case above, none of our kids can
2695       // be aRefChild, so we can always pass through aReplace in the
2696       // EnsureAllowedAsChild checks below and don't have to worry about whether
2697       // recomputing nodeToInsertBefore is OK.
2698
2699       // Verify that our aRefChild is still sensible
2700       if (aRefChild && aRefChild->GetParent() != this) {
2701         aError.ThrowHierarchyRequestError("Don't know where to insert child");
2702         return nullptr;
2703       }
2704
2705       // Recompute nodeToInsertBefore, just in case.
2706       if (aReplace) {
2707         nodeToInsertBefore = aRefChild->GetNextSibling();
2708       } else {
2709         // If aRefChild has 'this' as a parent, it must be an nsIContent.
2710         nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;
2711       }
2712
2713       // And verify that newContent is still allowed as our child.  Sadly, we
2714       // need to reimplement the relevant part of EnsureAllowedAsChild() because
2715       // now our nodes are in an array and all.  If you change this code,
2716       // change the code there.
2717       if (IsDocument()) {
2718         bool sawElement = false;
2719         for (uint32_t i = 0; i < count; ++i) {
2720           nsIContent* child = fragChildren->ElementAt(i);
2721           if (child->IsElement()) {
2722             if (sawElement) {
2723               // No good
2724               aError.ThrowHierarchyRequestError(
2725                   "Cannot have more than one Element child of a Document");
2726               return nullptr;
2727             }
2728             sawElement = true;
2729           }
2730           EnsureAllowedAsChild(child, this, aReplace, aRefChild, aError);
2731           if (aError.Failed()) {
2732             return nullptr;
2733           }
2734         }
2735       }
2736     }
2737   }
2738
2739   mozAutoDocUpdate batch(GetComposedDoc(), true);
2740   nsAutoMutationBatch mb;
2741
2742   // If we're replacing and we haven't removed aRefChild yet, do so now
2743   if (aReplace && aRefChild != aNewChild) {
2744     mb.Init(this, true, true);
2745
2746     // Since aRefChild is never null in the aReplace case, we know that at
2747     // this point nodeToInsertBefore is the next sibling of aRefChild.
2748     NS_ASSERTION(aRefChild->GetNextSibling() == nodeToInsertBefore,
2749                  "Unexpected nodeToInsertBefore");
2750
2751     nsIContent* toBeRemoved = nodeToInsertBefore
2752                                   ? nodeToInsertBefore->GetPreviousSibling()
2753                                   : GetLastChild();
2754     MOZ_ASSERT(toBeRemoved);
2755
2756     RemoveChildNode(toBeRemoved, true);
2757   }
2758
2759   // Move new child over to our document if needed. Do this after removing
2760   // it from its parent so that AdoptNode doesn't fire DOMNodeRemoved
2761   // DocumentType nodes are the only nodes that can have a null
2762   // ownerDocument according to the DOM spec, and we need to allow
2763   // inserting them w/o calling AdoptNode().
2764   Document* doc = OwnerDoc();
2765   if (doc != newContent->OwnerDoc() && nodeType != DOCUMENT_FRAGMENT_NODE) {
2766     AdoptNodeIntoOwnerDoc(this, aNewChild, aError);
2767     if (aError.Failed()) {
2768       return nullptr;
2769     }
2770   }
2771
2772   /*
2773    * Check if we're inserting a document fragment. If we are, we need
2774    * to actually add its children individually (i.e. we don't add the
2775    * actual document fragment).
2776    */
2777   nsINode* result = aReplace ? aRefChild : aNewChild;
2778   if (nodeType == DOCUMENT_FRAGMENT_NODE) {
2779     nsAutoMutationBatch* mutationBatch = nsAutoMutationBatch::GetCurrentBatch();
2780     if (mutationBatch && mutationBatch != &mb) {
2781       mutationBatch = nullptr;
2782     } else if (!aReplace) {
2783       mb.Init(this, true, true);
2784       mutationBatch = nsAutoMutationBatch::GetCurrentBatch();
2785     }
2786
2787     if (mutationBatch) {
2788       mutationBatch->RemovalDone();
2789       mutationBatch->SetPrevSibling(
2790           nodeToInsertBefore ? nodeToInsertBefore->GetPreviousSibling()
2791                              : GetLastChild());
2792       mutationBatch->SetNextSibling(nodeToInsertBefore);
2793     }
2794
2795     uint32_t count = fragChildren->Length();
2796     if (!count) {
2797       return result;
2798     }
2799
2800     bool appending = !IsDocument() && !nodeToInsertBefore;
2801     nsIContent* firstInsertedContent = fragChildren->ElementAt(0);
2802
2803     // Iterate through the fragment's children, and insert them in the new
2804     // parent
2805     for (uint32_t i = 0; i < count; ++i) {
2806       // XXXbz how come no reparenting here?  That seems odd...
2807       // Insert the child.
2808       InsertChildBefore(fragChildren->ElementAt(i), nodeToInsertBefore,
2809                         !appending, aError);
2810       if (aError.Failed()) {
2811         // Make sure to notify on any children that we did succeed to insert
2812         if (appending && i != 0) {
2813           MutationObservers::NotifyContentAppended(
2814               static_cast<nsIContent*>(this), firstInsertedContent);
2815         }
2816         return nullptr;
2817       }
2818     }
2819
2820     if (mutationBatch && !appending) {
2821       mutationBatch->NodesAdded();
2822     }
2823
2824     // Notify and fire mutation events when appending
2825     if (appending) {
2826       MutationObservers::NotifyContentAppended(static_cast<nsIContent*>(this),
2827                                                firstInsertedContent);
2828       if (mutationBatch) {
2829         mutationBatch->NodesAdded();
2830       }
2831       // Optimize for the case when there are no listeners
2832       if (nsContentUtils::HasMutationListeners(
2833               doc, NS_EVENT_BITS_MUTATION_NODEINSERTED)) {
2834         Element::FireNodeInserted(doc, this, *fragChildren);
2835       }
2836     }
2837   } else {
2838     // Not inserting a fragment but rather a single node.
2839
2840     // FIXME https://bugzilla.mozilla.org/show_bug.cgi?id=544654
2841     //       We need to reparent here for nodes for which the parent of their
2842     //       wrapper is not the wrapper for their ownerDocument (XUL elements,
2843     //       form controls, ...). Also applies in the fragment code above.
2844     if (nsAutoMutationBatch::GetCurrentBatch() == &mb) {
2845       mb.RemovalDone();
2846       mb.SetPrevSibling(nodeToInsertBefore
2847                             ? nodeToInsertBefore->GetPreviousSibling()
2848                             : GetLastChild());
2849       mb.SetNextSibling(nodeToInsertBefore);
2850     }
2851     InsertChildBefore(newContent, nodeToInsertBefore, true, aError);
2852     if (aError.Failed()) {
2853       return nullptr;
2854     }
2855   }
2856
2857   return result;
2858 }
2859
2860 void nsINode::BindObject(nsISupports* aObject) {
2861   nsCOMArray<nsISupports>* objects = static_cast<nsCOMArray<nsISupports>*>(
2862       GetProperty(nsGkAtoms::keepobjectsalive));
2863   if (!objects) {
2864     objects = new nsCOMArray<nsISupports>();
2865     SetProperty(nsGkAtoms::keepobjectsalive, objects,
2866                 nsINode::DeleteProperty<nsCOMArray<nsISupports>>, true);
2867   }
2868   objects->AppendObject(aObject);
2869 }
2870
2871 void nsINode::UnbindObject(nsISupports* aObject) {
2872   nsCOMArray<nsISupports>* objects = static_cast<nsCOMArray<nsISupports>*>(
2873       GetProperty(nsGkAtoms::keepobjectsalive));
2874   if (objects) {
2875     objects->RemoveObject(aObject);
2876   }
2877 }
2878
2879 already_AddRefed<AccessibleNode> nsINode::GetAccessibleNode() {
2880 #ifdef ACCESSIBILITY
2881   nsresult rv = NS_OK;
2882
2883   RefPtr<AccessibleNode> anode =
2884       static_cast<AccessibleNode*>(GetProperty(nsGkAtoms::accessiblenode, &rv));
2885   if (NS_FAILED(rv)) {
2886     anode = new AccessibleNode(this);
2887     RefPtr<AccessibleNode> temp = anode;
2888     rv = SetProperty(nsGkAtoms::accessiblenode, temp.forget().take(),
2889                      nsPropertyTable::SupportsDtorFunc, true);
2890     if (NS_FAILED(rv)) {
2891       NS_WARNING("SetProperty failed");
2892       return nullptr;
2893     }
2894   }
2895   return anode.forget();
2896 #else
2897   return nullptr;
2898 #endif
2899 }
2900
2901 void nsINode::AddSizeOfExcludingThis(nsWindowSizes& aSizes,
2902                                      size_t* aNodeSize) const {
2903   EventListenerManager* elm = GetExistingListenerManager();
2904   if (elm) {
2905     *aNodeSize += elm->SizeOfIncludingThis(aSizes.mState.mMallocSizeOf);
2906   }
2907
2908   // Measurement of the following members may be added later if DMD finds it is
2909   // worthwhile:
2910   // - mNodeInfo
2911   // - mSlots
2912   //
2913   // The following members are not measured:
2914   // - mParent, mNextSibling, mPreviousOrLastSibling, mFirstChild: because
2915   //   they're non-owning, from "exclusive ownership" point of view.
2916 }
2917
2918 void nsINode::AddSizeOfIncludingThis(nsWindowSizes& aSizes,
2919                                      size_t* aNodeSize) const {
2920   *aNodeSize += aSizes.mState.mMallocSizeOf(this);
2921   AddSizeOfExcludingThis(aSizes, aNodeSize);
2922 }
2923
2924 bool nsINode::Contains(const nsINode* aOther) const {
2925   if (aOther == this) {
2926     return true;
2927   }
2928
2929   if (!aOther || OwnerDoc() != aOther->OwnerDoc() ||
2930       IsInUncomposedDoc() != aOther->IsInUncomposedDoc() ||
2931       !aOther->IsContent() || !HasChildren()) {
2932     return false;
2933   }
2934
2935   if (IsDocument()) {
2936     // document.contains(aOther) returns true if aOther is in the document,
2937     // but is not in any anonymous subtree.
2938     // IsInUncomposedDoc() check is done already before this.
2939     return !aOther->IsInNativeAnonymousSubtree();
2940   }
2941
2942   if (!IsElement() && !IsDocumentFragment()) {
2943     return false;
2944   }
2945
2946   if (IsInShadowTree() != aOther->IsInShadowTree() ||
2947       IsInNativeAnonymousSubtree() != aOther->IsInNativeAnonymousSubtree()) {
2948     return false;
2949   }
2950
2951   if (IsInNativeAnonymousSubtree()) {
2952     if (GetClosestNativeAnonymousSubtreeRoot() !=
2953         aOther->GetClosestNativeAnonymousSubtreeRoot()) {
2954       return false;
2955     }
2956   }
2957
2958   if (IsInShadowTree()) {
2959     ShadowRoot* otherRoot = aOther->GetContainingShadow();
2960     if (IsShadowRoot()) {
2961       return otherRoot == this;
2962     }
2963     if (otherRoot != GetContainingShadow()) {
2964       return false;
2965     }
2966   }
2967
2968   return aOther->IsInclusiveDescendantOf(this);
2969 }
2970
2971 uint32_t nsINode::Length() const {
2972   switch (NodeType()) {
2973     case DOCUMENT_TYPE_NODE:
2974       return 0;
2975
2976     case TEXT_NODE:
2977     case CDATA_SECTION_NODE:
2978     case PROCESSING_INSTRUCTION_NODE:
2979     case COMMENT_NODE:
2980       MOZ_ASSERT(IsContent());
2981       return AsContent()->TextLength();
2982
2983     default:
2984       return GetChildCount();
2985   }
2986 }
2987
2988 namespace {
2989 class SelectorCacheKey {
2990  public:
2991   explicit SelectorCacheKey(const nsACString& aString) : mKey(aString) {
2992     MOZ_COUNT_CTOR(SelectorCacheKey);
2993   }
2994
2995   nsCString mKey;
2996   nsExpirationState mState;
2997
2998   nsExpirationState* GetExpirationState() { return &mState; }
2999
3000   MOZ_COUNTED_DTOR(SelectorCacheKey)
3001 };
3002
3003 class SelectorCache final : public nsExpirationTracker<SelectorCacheKey, 4> {
3004  public:
3005   using SelectorList = UniquePtr<StyleSelectorList>;
3006   using Table = nsTHashMap<nsCStringHashKey, SelectorList>;
3007
3008   SelectorCache()
3009       : nsExpirationTracker<SelectorCacheKey, 4>(
3010             1000, "SelectorCache", GetMainThreadSerialEventTarget()) {}
3011
3012   void NotifyExpired(SelectorCacheKey* aSelector) final {
3013     MOZ_ASSERT(NS_IsMainThread());
3014     MOZ_ASSERT(aSelector);
3015
3016     // There is no guarantee that this method won't be re-entered when selector
3017     // matching is ongoing because "memory-pressure" could be notified
3018     // immediately when OOM happens according to the design of
3019     // nsExpirationTracker. The perfect solution is to delete the |aSelector|
3020     // and its StyleSelectorList in mTable asynchronously. We remove these
3021     // objects synchronously for now because NotifyExpired() will never be
3022     // triggered by "memory-pressure" which is not implemented yet in the stage
3023     // 2 of mozalloc_handle_oom(). Once these objects are removed
3024     // asynchronously, we should update the warning added in
3025     // mozalloc_handle_oom() as well.
3026     RemoveObject(aSelector);
3027     mTable.Remove(aSelector->mKey);
3028     delete aSelector;
3029   }
3030
3031   // We do not call MarkUsed because it would just slow down lookups and
3032   // because we're OK expiring things after a few seconds even if they're
3033   // being used.  Returns whether we actually had an entry for aSelector.
3034   //
3035   // If we have an entry and the selector list returned has a null
3036   // StyleSelectorList*, that indicates that aSelector has already been
3037   // parsed and is not a syntactically valid selector.
3038   template <typename F>
3039   StyleSelectorList* GetListOrInsertFrom(const nsACString& aSelector,
3040                                          F&& aFrom) {
3041     MOZ_ASSERT(NS_IsMainThread());
3042     return mTable.LookupOrInsertWith(aSelector, std::forward<F>(aFrom)).get();
3043   }
3044
3045   ~SelectorCache() { AgeAllGenerations(); }
3046
3047  private:
3048   Table mTable;
3049 };
3050
3051 SelectorCache& GetSelectorCache(bool aChromeRulesEnabled) {
3052   static StaticAutoPtr<SelectorCache> sSelectorCache;
3053   static StaticAutoPtr<SelectorCache> sChromeSelectorCache;
3054   auto& cache = aChromeRulesEnabled ? sChromeSelectorCache : sSelectorCache;
3055   if (!cache) {
3056     cache = new SelectorCache();
3057     ClearOnShutdown(&cache);
3058   }
3059   return *cache;
3060 }
3061 }  // namespace
3062
3063 const StyleSelectorList* nsINode::ParseSelectorList(
3064     const nsACString& aSelectorString, ErrorResult& aRv) {
3065   Document* doc = OwnerDoc();
3066   const bool chromeRulesEnabled = doc->ChromeRulesEnabled();
3067
3068   SelectorCache& cache = GetSelectorCache(chromeRulesEnabled);
3069   StyleSelectorList* list = cache.GetListOrInsertFrom(aSelectorString, [&] {
3070     // Note that we want to cache even if null was returned, because we
3071     // want to cache the "This is not a valid selector" result.
3072     return WrapUnique(
3073         Servo_SelectorList_Parse(&aSelectorString, chromeRulesEnabled));
3074   });
3075
3076   if (!list) {
3077     // Invalid selector.
3078     aRv.ThrowSyntaxError("'"_ns + aSelectorString +
3079                          "' is not a valid selector"_ns);
3080   }
3081
3082   return list;
3083 }
3084
3085 // Given an id, find first element with that id under aRoot.
3086 // If none found, return nullptr. aRoot must be in the document.
3087 inline static Element* FindMatchingElementWithId(
3088     const nsAString& aId, const Element& aRoot,
3089     const DocumentOrShadowRoot& aContainingDocOrShadowRoot) {
3090   MOZ_ASSERT(aRoot.SubtreeRoot() == &aContainingDocOrShadowRoot.AsNode());
3091   MOZ_ASSERT(
3092       aRoot.IsInUncomposedDoc() || aRoot.IsInShadowTree(),
3093       "Don't call me if the root is not in the document or in a shadow tree");
3094
3095   const nsTArray<Element*>* elements =
3096       aContainingDocOrShadowRoot.GetAllElementsForId(aId);
3097   if (!elements) {
3098     // Nothing to do; we're done
3099     return nullptr;
3100   }
3101
3102   // XXXbz: Should we fall back to the tree walk if |elements| is long,
3103   // for some value of "long"?
3104   for (Element* element : *elements) {
3105     if (MOZ_UNLIKELY(element == &aRoot)) {
3106       continue;
3107     }
3108
3109     if (!element->IsInclusiveDescendantOf(&aRoot)) {
3110       continue;
3111     }
3112
3113     // We have an element with the right id and it's a strict descendant
3114     // of aRoot.
3115     return element;
3116   }
3117
3118   return nullptr;
3119 }
3120
3121 Element* nsINode::QuerySelector(const nsACString& aSelector,
3122                                 ErrorResult& aResult) {
3123   AUTO_PROFILER_LABEL_DYNAMIC_NSCSTRING("nsINode::QuerySelector",
3124                                         LAYOUT_SelectorQuery, aSelector);
3125
3126   const StyleSelectorList* list = ParseSelectorList(aSelector, aResult);
3127   if (!list) {
3128     return nullptr;
3129   }
3130   const bool useInvalidation = false;
3131   return const_cast<Element*>(
3132       Servo_SelectorList_QueryFirst(this, list, useInvalidation));
3133 }
3134
3135 already_AddRefed<nsINodeList> nsINode::QuerySelectorAll(
3136     const nsACString& aSelector, ErrorResult& aResult) {
3137   AUTO_PROFILER_LABEL_DYNAMIC_NSCSTRING("nsINode::QuerySelectorAll",
3138                                         LAYOUT_SelectorQuery, aSelector);
3139
3140   RefPtr<nsSimpleContentList> contentList = new nsSimpleContentList(this);
3141   const StyleSelectorList* list = ParseSelectorList(aSelector, aResult);
3142   if (!list) {
3143     return contentList.forget();
3144   }
3145
3146   const bool useInvalidation = false;
3147   Servo_SelectorList_QueryAll(this, list, contentList.get(), useInvalidation);
3148   return contentList.forget();
3149 }
3150
3151 Element* nsINode::GetElementById(const nsAString& aId) {
3152   MOZ_ASSERT(!IsShadowRoot(), "Should use the faster version");
3153   MOZ_ASSERT(IsElement() || IsDocumentFragment(),
3154              "Bogus this object for GetElementById call");
3155   if (IsInUncomposedDoc()) {
3156     MOZ_ASSERT(IsElement(), "Huh? A fragment in a document?");
3157     return FindMatchingElementWithId(aId, *AsElement(), *OwnerDoc());
3158   }
3159
3160   if (ShadowRoot* containingShadow = AsContent()->GetContainingShadow()) {
3161     MOZ_ASSERT(IsElement(), "Huh? A fragment in a ShadowRoot?");
3162     return FindMatchingElementWithId(aId, *AsElement(), *containingShadow);
3163   }
3164
3165   for (nsIContent* kid = GetFirstChild(); kid; kid = kid->GetNextNode(this)) {
3166     if (!kid->IsElement()) {
3167       continue;
3168     }
3169     nsAtom* id = kid->AsElement()->GetID();
3170     if (id && id->Equals(aId)) {
3171       return kid->AsElement();
3172     }
3173   }
3174   return nullptr;
3175 }
3176
3177 JSObject* nsINode::WrapObject(JSContext* aCx,
3178                               JS::Handle<JSObject*> aGivenProto) {
3179   // Make sure one of these is true
3180   // (1) our owner document has a script handling object,
3181   // (2) Our owner document has had a script handling object, or has been marked
3182   //     to have had one,
3183   // (3) we are running a privileged script.
3184   // Event handling is possible only if (1). If (2) event handling is
3185   // prevented.
3186   // If the document has never had a script handling object, untrusted
3187   // scripts (3) shouldn't touch it!
3188   bool hasHadScriptHandlingObject = false;
3189   if (!OwnerDoc()->GetScriptHandlingObject(hasHadScriptHandlingObject) &&
3190       !hasHadScriptHandlingObject && !nsContentUtils::IsSystemCaller(aCx)) {
3191     Throw(aCx, NS_ERROR_UNEXPECTED);
3192     return nullptr;
3193   }
3194
3195   JS::Rooted<JSObject*> obj(aCx, WrapNode(aCx, aGivenProto));
3196   if (obj && ChromeOnlyAccess()) {
3197     MOZ_RELEASE_ASSERT(
3198         xpc::IsUnprivilegedJunkScope(JS::GetNonCCWObjectGlobal(obj)) ||
3199         xpc::IsInUAWidgetScope(obj) || xpc::AccessCheck::isChrome(obj));
3200   }
3201   return obj;
3202 }
3203
3204 already_AddRefed<nsINode> nsINode::CloneNode(bool aDeep, ErrorResult& aError) {
3205   return Clone(aDeep, nullptr, aError);
3206 }
3207
3208 nsDOMAttributeMap* nsINode::GetAttributes() {
3209   if (!IsElement()) {
3210     return nullptr;
3211   }
3212   return AsElement()->Attributes();
3213 }
3214
3215 Element* nsINode::GetParentElementCrossingShadowRoot() const {
3216   if (!mParent) {
3217     return nullptr;
3218   }
3219
3220   if (mParent->IsElement()) {
3221     return mParent->AsElement();
3222   }
3223
3224   if (ShadowRoot* shadowRoot = ShadowRoot::FromNode(mParent)) {
3225     MOZ_ASSERT(shadowRoot->GetHost(), "ShowRoots should always have a host");
3226     return shadowRoot->GetHost();
3227   }
3228
3229   return nullptr;
3230 }
3231
3232 bool nsINode::HasBoxQuadsSupport(JSContext* aCx, JSObject* /* unused */) {
3233   return xpc::AccessCheck::isChrome(js::GetContextCompartment(aCx)) ||
3234          StaticPrefs::layout_css_getBoxQuads_enabled();
3235 }
3236
3237 nsINode* nsINode::GetScopeChainParent() const { return nullptr; }
3238
3239 Element* nsINode::GetParentFlexElement() {
3240   if (!IsContent()) {
3241     return nullptr;
3242   }
3243
3244   nsIFrame* primaryFrame = AsContent()->GetPrimaryFrame(FlushType::Frames);
3245
3246   // Walk up the parent chain and pierce through any anonymous boxes
3247   // that might be between this frame and a possible flex parent.
3248   for (nsIFrame* f = primaryFrame; f; f = f->GetParent()) {
3249     if (f != primaryFrame && !f->Style()->IsAnonBox()) {
3250       // We hit a non-anonymous ancestor before finding a flex item.
3251       // Bail out.
3252       break;
3253     }
3254     if (f->IsFlexItem()) {
3255       return f->GetParent()->GetContent()->AsElement();
3256     }
3257   }
3258
3259   return nullptr;
3260 }
3261
3262 Element* nsINode::GetNearestInclusiveOpenPopover() const {
3263   for (auto* el : InclusiveFlatTreeAncestorsOfType<Element>()) {
3264     if (el->IsAutoPopover() && el->IsPopoverOpen()) {
3265       return el;
3266     }
3267   }
3268   return nullptr;
3269 }
3270
3271 Element* nsINode::GetNearestInclusiveTargetPopoverForInvoker() const {
3272   for (auto* el : InclusiveFlatTreeAncestorsOfType<Element>()) {
3273     if (auto* popover = el->GetEffectivePopoverTargetElement()) {
3274       if (popover->IsAutoPopover() && popover->IsPopoverOpen()) {
3275         return popover;
3276       }
3277     }
3278   }
3279   return nullptr;
3280 }
3281
3282 nsGenericHTMLElement* nsINode::GetEffectivePopoverTargetElement() const {
3283   const auto* formControl =
3284       nsGenericHTMLFormControlElementWithState::FromNode(this);
3285   if (!formControl || formControl->IsDisabled() ||
3286       !formControl->IsButtonControl()) {
3287     return nullptr;
3288   }
3289   if (auto* popover = nsGenericHTMLElement::FromNodeOrNull(
3290           formControl->GetPopoverTargetElement())) {
3291     if (popover->GetPopoverAttributeState() != PopoverAttributeState::None) {
3292       return popover;
3293     }
3294   }
3295   return nullptr;
3296 }
3297
3298 Element* nsINode::GetTopmostClickedPopover() const {
3299   Element* clickedPopover = GetNearestInclusiveOpenPopover();
3300   Element* invokedPopover = GetNearestInclusiveTargetPopoverForInvoker();
3301   if (!clickedPopover) {
3302     return invokedPopover;
3303   }
3304   auto autoPopoverList = clickedPopover->OwnerDoc()->AutoPopoverList();
3305   for (Element* el : Reversed(autoPopoverList)) {
3306     if (el == clickedPopover || el == invokedPopover) {
3307       return el;
3308     }
3309   }
3310   return nullptr;
3311 }
3312
3313 void nsINode::AddAnimationObserver(nsIAnimationObserver* aAnimationObserver) {
3314   AddMutationObserver(aAnimationObserver);
3315   OwnerDoc()->SetMayHaveAnimationObservers();
3316 }
3317
3318 void nsINode::AddAnimationObserverUnlessExists(
3319     nsIAnimationObserver* aAnimationObserver) {
3320   AddMutationObserverUnlessExists(aAnimationObserver);
3321   OwnerDoc()->SetMayHaveAnimationObservers();
3322 }
3323
3324 already_AddRefed<nsINode> nsINode::CloneAndAdopt(
3325     nsINode* aNode, bool aClone, bool aDeep,
3326     nsNodeInfoManager* aNewNodeInfoManager,
3327     JS::Handle<JSObject*> aReparentScope, nsINode* aParent,
3328     ErrorResult& aError) {
3329   MOZ_ASSERT((!aClone && aNewNodeInfoManager) || !aReparentScope,
3330              "If cloning or not getting a new nodeinfo we shouldn't rewrap");
3331   MOZ_ASSERT(!aParent || aNode->IsContent(),
3332              "Can't insert document or attribute nodes into a parent");
3333
3334   // First deal with aNode and walk its attributes (and their children). Then,
3335   // if aDeep is true, deal with aNode's children (and recurse into their
3336   // attributes and children).
3337
3338   nsAutoScriptBlocker scriptBlocker;
3339
3340   nsNodeInfoManager* nodeInfoManager = aNewNodeInfoManager;
3341
3342   // aNode.
3343   class NodeInfo* nodeInfo = aNode->mNodeInfo;
3344   RefPtr<class NodeInfo> newNodeInfo;
3345   if (nodeInfoManager) {
3346     // Don't allow importing/adopting nodes from non-privileged "scriptable"
3347     // documents to "non-scriptable" documents.
3348     Document* newDoc = nodeInfoManager->GetDocument();
3349     if (NS_WARN_IF(!newDoc)) {
3350       aError.Throw(NS_ERROR_UNEXPECTED);
3351       return nullptr;
3352     }
3353     bool hasHadScriptHandlingObject = false;
3354     if (!newDoc->GetScriptHandlingObject(hasHadScriptHandlingObject) &&
3355         !hasHadScriptHandlingObject) {
3356       Document* currentDoc = aNode->OwnerDoc();
3357       if (NS_WARN_IF(!nsContentUtils::IsChromeDoc(currentDoc) &&
3358                      (currentDoc->GetScriptHandlingObject(
3359                           hasHadScriptHandlingObject) ||
3360                       hasHadScriptHandlingObject))) {
3361         aError.Throw(NS_ERROR_UNEXPECTED);
3362         return nullptr;
3363       }
3364     }
3365
3366     newNodeInfo = nodeInfoManager->GetNodeInfo(
3367         nodeInfo->NameAtom(), nodeInfo->GetPrefixAtom(),
3368         nodeInfo->NamespaceID(), nodeInfo->NodeType(),
3369         nodeInfo->GetExtraName());
3370
3371     nodeInfo = newNodeInfo;
3372   }
3373
3374   Element* elem = Element::FromNode(aNode);
3375
3376   nsCOMPtr<nsINode> clone;
3377   if (aClone) {
3378     nsresult rv = aNode->Clone(nodeInfo, getter_AddRefs(clone));
3379     if (NS_WARN_IF(NS_FAILED(rv))) {
3380       aError.Throw(rv);
3381       return nullptr;
3382     }
3383
3384     if (aParent) {
3385       // If we're cloning we need to insert the cloned children into the cloned
3386       // parent.
3387       aParent->AppendChildTo(static_cast<nsIContent*>(clone.get()),
3388                              /* aNotify = */ true, aError);
3389       if (NS_WARN_IF(aError.Failed())) {
3390         return nullptr;
3391       }
3392     } else if (aDeep && clone->IsDocument()) {
3393       // After cloning the document itself, we want to clone the children into
3394       // the cloned document (somewhat like cloning and importing them into the
3395       // cloned document).
3396       nodeInfoManager = clone->mNodeInfo->NodeInfoManager();
3397     }
3398   } else if (nodeInfoManager) {
3399     Document* oldDoc = aNode->OwnerDoc();
3400
3401     DOMArena* domArenaToStore =
3402         !aNode->HasFlag(NODE_KEEPS_DOMARENA)
3403             ? aNode->NodeInfo()->NodeInfoManager()->GetArenaAllocator()
3404             : nullptr;
3405
3406     Document* newDoc = nodeInfoManager->GetDocument();
3407     MOZ_ASSERT(newDoc);
3408
3409     bool wasRegistered = false;
3410     if (elem) {
3411       wasRegistered = oldDoc->UnregisterActivityObserver(elem);
3412     }
3413
3414     const bool hadProperties = aNode->HasProperties();
3415     if (hadProperties) {
3416       // NOTE: We want this to happen before NodeInfoChanged so that
3417       // NodeInfoChanged can use node properties normally.
3418       //
3419       // When this fails, it removes all properties for the node anyway, so no
3420       // extra error handling needed.
3421       Unused << oldDoc->PropertyTable().TransferOrRemoveAllPropertiesFor(
3422           aNode, newDoc->PropertyTable());
3423     }
3424
3425     aNode->mNodeInfo.swap(newNodeInfo);
3426     aNode->NodeInfoChanged(oldDoc);
3427
3428     MOZ_ASSERT(newDoc != oldDoc);
3429     if (elem) {
3430       // Adopted callback must be enqueued whenever a node’s
3431       // shadow-including inclusive descendants that is custom.
3432       CustomElementData* data = elem->GetCustomElementData();
3433       if (data && data->mState == CustomElementData::State::eCustom) {
3434         LifecycleCallbackArgs args;
3435         args.mOldDocument = oldDoc;
3436         args.mNewDocument = newDoc;
3437
3438         nsContentUtils::EnqueueLifecycleCallback(ElementCallbackType::eAdopted,
3439                                                  elem, args);
3440       }
3441     }
3442
3443     // XXX what if oldDoc is null, we don't know if this should be
3444     // registered or not! Can that really happen?
3445     if (wasRegistered) {
3446       newDoc->RegisterActivityObserver(aNode->AsElement());
3447     }
3448
3449     if (nsPIDOMWindowInner* window = newDoc->GetInnerWindow()) {
3450       EventListenerManager* elm = aNode->GetExistingListenerManager();
3451       if (elm) {
3452         window->SetMutationListeners(elm->MutationListenerBits());
3453         if (elm->MayHaveDOMActivateListeners()) {
3454           window->SetHasDOMActivateEventListeners();
3455         }
3456         if (elm->MayHavePaintEventListener()) {
3457           window->SetHasPaintEventListeners();
3458         }
3459         if (elm->MayHaveTouchEventListener()) {
3460           window->SetHasTouchEventListeners();
3461         }
3462         if (elm->MayHaveMouseEnterLeaveEventListener()) {
3463           window->SetHasMouseEnterLeaveEventListeners();
3464         }
3465         if (elm->MayHavePointerEnterLeaveEventListener()) {
3466           window->SetHasPointerEnterLeaveEventListeners();
3467         }
3468         if (elm->MayHaveSelectionChangeEventListener()) {
3469           window->SetHasSelectionChangeEventListeners();
3470         }
3471         if (elm->MayHaveFormSelectEventListener()) {
3472           window->SetHasFormSelectEventListeners();
3473         }
3474         if (elm->MayHaveTransitionEventListener()) {
3475           window->SetHasTransitionEventListeners();
3476         }
3477       }
3478     }
3479     if (wasRegistered) {
3480       nsIContent* content = aNode->AsContent();
3481       if (auto* mediaElem = HTMLMediaElement::FromNodeOrNull(content)) {
3482         mediaElem->NotifyOwnerDocumentActivityChanged();
3483       }
3484       nsCOMPtr<nsIObjectLoadingContent> objectLoadingContent(
3485           do_QueryInterface(aNode));
3486       if (objectLoadingContent) {
3487         nsObjectLoadingContent* olc =
3488             static_cast<nsObjectLoadingContent*>(objectLoadingContent.get());
3489         olc->NotifyOwnerDocumentActivityChanged();
3490       } else {
3491         // HTMLImageElement::FromNode is insufficient since we need this for
3492         // <svg:image> as well.
3493         nsCOMPtr<nsIImageLoadingContent> imageLoadingContent(
3494             do_QueryInterface(aNode));
3495         if (imageLoadingContent) {
3496           auto ilc =
3497               static_cast<nsImageLoadingContent*>(imageLoadingContent.get());
3498           ilc->NotifyOwnerDocumentActivityChanged();
3499         }
3500       }
3501     }
3502
3503     if (oldDoc->MayHaveDOMMutationObservers()) {
3504       newDoc->SetMayHaveDOMMutationObservers();
3505     }
3506
3507     if (oldDoc->MayHaveAnimationObservers()) {
3508       newDoc->SetMayHaveAnimationObservers();
3509     }
3510
3511     if (elem) {
3512       elem->RecompileScriptEventListeners();
3513     }
3514
3515     if (aReparentScope) {
3516       AutoJSContext cx;
3517       JS::Rooted<JSObject*> wrapper(cx);
3518       if ((wrapper = aNode->GetWrapper())) {
3519         MOZ_ASSERT(IsDOMObject(wrapper));
3520         JSAutoRealm ar(cx, wrapper);
3521         UpdateReflectorGlobal(cx, wrapper, aError);
3522         if (aError.Failed()) {
3523           if (wasRegistered) {
3524             newDoc->UnregisterActivityObserver(aNode->AsElement());
3525           }
3526           if (hadProperties) {
3527             // NOTE: When it fails it removes all properties for the node
3528             // anyway, so no extra error handling needed.
3529             Unused << newDoc->PropertyTable().TransferOrRemoveAllPropertiesFor(
3530                 aNode, oldDoc->PropertyTable());
3531           }
3532           aNode->mNodeInfo.swap(newNodeInfo);
3533           aNode->NodeInfoChanged(newDoc);
3534           if (wasRegistered) {
3535             oldDoc->RegisterActivityObserver(aNode->AsElement());
3536           }
3537           return nullptr;
3538         }
3539       }
3540     }
3541
3542     // At this point, a new node is added to the document, and this
3543     // node isn't allocated by the NodeInfoManager of this document,
3544     // so we need to do this SetArenaAllocator logic to bypass
3545     // the !HasChildren() check in NodeInfoManager::Allocate.
3546     if (mozilla::StaticPrefs::dom_arena_allocator_enabled_AtStartup()) {
3547       if (!newDoc->NodeInfoManager()->HasAllocated()) {
3548         if (DocGroup* docGroup = newDoc->GetDocGroup()) {
3549           newDoc->NodeInfoManager()->SetArenaAllocator(
3550               docGroup->ArenaAllocator());
3551         }
3552       }
3553
3554       if (domArenaToStore && newDoc->GetDocGroup() != oldDoc->GetDocGroup()) {
3555         nsContentUtils::AddEntryToDOMArenaTable(aNode, domArenaToStore);
3556       }
3557     }
3558   }
3559
3560   if (aDeep && (!aClone || !aNode->IsAttr())) {
3561     // aNode's children.
3562     for (nsIContent* cloneChild = aNode->GetFirstChild(); cloneChild;
3563          cloneChild = cloneChild->GetNextSibling()) {
3564       nsCOMPtr<nsINode> child =
3565           CloneAndAdopt(cloneChild, aClone, true, nodeInfoManager,
3566                         aReparentScope, clone, aError);
3567       if (NS_WARN_IF(aError.Failed())) {
3568         return nullptr;
3569       }
3570     }
3571   }
3572
3573   if (aDeep && aNode->IsElement()) {
3574     if (aClone) {
3575       if (nodeInfo->GetDocument()->IsStaticDocument()) {
3576         // Clone any animations to the node in the static document, including
3577         // the current timing. They will need to be paused later after the new
3578         // document's pres shell gets initialized.
3579         //
3580         // This needs to be done here rather than in Element::CopyInnerTo
3581         // because the animations clone code relies on the target (that is,
3582         // `clone`) being connected already.
3583         clone->AsElement()->CloneAnimationsFrom(*aNode->AsElement());
3584
3585         // Clone the Shadow DOM
3586         ShadowRoot* originalShadowRoot = aNode->AsElement()->GetShadowRoot();
3587         if (originalShadowRoot) {
3588           RefPtr<ShadowRoot> newShadowRoot =
3589               clone->AsElement()->AttachShadowWithoutNameChecks(
3590                   originalShadowRoot->Mode());
3591
3592           newShadowRoot->CloneInternalDataFrom(originalShadowRoot);
3593           for (nsIContent* origChild = originalShadowRoot->GetFirstChild();
3594                origChild; origChild = origChild->GetNextSibling()) {
3595             nsCOMPtr<nsINode> child =
3596                 CloneAndAdopt(origChild, aClone, aDeep, nodeInfoManager,
3597                               aReparentScope, newShadowRoot, aError);
3598             if (NS_WARN_IF(aError.Failed())) {
3599               return nullptr;
3600             }
3601           }
3602         }
3603       }
3604     } else {
3605       if (ShadowRoot* shadowRoot = aNode->AsElement()->GetShadowRoot()) {
3606         nsCOMPtr<nsINode> child =
3607             CloneAndAdopt(shadowRoot, aClone, aDeep, nodeInfoManager,
3608                           aReparentScope, clone, aError);
3609         if (NS_WARN_IF(aError.Failed())) {
3610           return nullptr;
3611         }
3612       }
3613     }
3614   }
3615
3616   // Cloning template element.
3617   if (aDeep && aClone && aNode->IsTemplateElement()) {
3618     DocumentFragment* origContent =
3619         static_cast<HTMLTemplateElement*>(aNode)->Content();
3620     DocumentFragment* cloneContent =
3621         static_cast<HTMLTemplateElement*>(clone.get())->Content();
3622
3623     // Clone the children into the clone's template content owner
3624     // document's nodeinfo manager.
3625     nsNodeInfoManager* ownerNodeInfoManager =
3626         cloneContent->mNodeInfo->NodeInfoManager();
3627
3628     for (nsIContent* cloneChild = origContent->GetFirstChild(); cloneChild;
3629          cloneChild = cloneChild->GetNextSibling()) {
3630       nsCOMPtr<nsINode> child =
3631           CloneAndAdopt(cloneChild, aClone, aDeep, ownerNodeInfoManager,
3632                         aReparentScope, cloneContent, aError);
3633       if (NS_WARN_IF(aError.Failed())) {
3634         return nullptr;
3635       }
3636     }
3637   }
3638
3639   return clone.forget();
3640 }
3641
3642 void nsINode::Adopt(nsNodeInfoManager* aNewNodeInfoManager,
3643                     JS::Handle<JSObject*> aReparentScope,
3644                     mozilla::ErrorResult& aError) {
3645   if (aNewNodeInfoManager) {
3646     Document* beforeAdoptDoc = OwnerDoc();
3647     Document* afterAdoptDoc = aNewNodeInfoManager->GetDocument();
3648
3649     MOZ_ASSERT(beforeAdoptDoc);
3650     MOZ_ASSERT(afterAdoptDoc);
3651     MOZ_ASSERT(beforeAdoptDoc != afterAdoptDoc);
3652
3653     if (afterAdoptDoc->GetDocGroup() != beforeAdoptDoc->GetDocGroup()) {
3654       // This is a temporary solution for Bug 1590526 to only limit
3655       // the restriction to chrome level documents because web extensions
3656       // rely on content to content node adoption.
3657       if (nsContentUtils::IsChromeDoc(afterAdoptDoc) ||
3658           nsContentUtils::IsChromeDoc(beforeAdoptDoc)) {
3659         return aError.ThrowSecurityError(
3660             "Adopting nodes across docgroups in chrome documents "
3661             "is unsupported");
3662       }
3663     }
3664   }
3665
3666   // Just need to store the return value of CloneAndAdopt in a
3667   // temporary nsCOMPtr to make sure we release it.
3668   nsCOMPtr<nsINode> node = CloneAndAdopt(this, false, true, aNewNodeInfoManager,
3669                                          aReparentScope, nullptr, aError);
3670
3671   nsMutationGuard::DidMutate();
3672 }
3673
3674 already_AddRefed<nsINode> nsINode::Clone(bool aDeep,
3675                                          nsNodeInfoManager* aNewNodeInfoManager,
3676                                          ErrorResult& aError) {
3677   return CloneAndAdopt(this, true, aDeep, aNewNodeInfoManager, nullptr, nullptr,
3678                        aError);
3679 }
3680
3681 void nsINode::GenerateXPath(nsAString& aResult) {
3682   XPathGenerator::Generate(this, aResult);
3683 }
3684
3685 bool nsINode::IsApzAware() const { return IsNodeApzAware(); }
3686
3687 bool nsINode::IsNodeApzAwareInternal() const {
3688   return EventTarget::IsApzAware();
3689 }
3690
3691 DocGroup* nsINode::GetDocGroup() const { return OwnerDoc()->GetDocGroup(); }
3692
3693 nsINode* nsINode::GetFlattenedTreeParentNodeNonInline() const {
3694   return GetFlattenedTreeParentNode();
3695 }
3696
3697 ParentObject nsINode::GetParentObject() const {
3698   ParentObject p(OwnerDoc());
3699   // Note that mReflectionScope is a no-op for chrome, and other places where we
3700   // don't check this value.
3701   if (IsInNativeAnonymousSubtree()) {
3702     if (ShouldUseUAWidgetScope(this)) {
3703       p.mReflectionScope = ReflectionScope::UAWidget;
3704     } else {
3705       MOZ_ASSERT(ShouldUseNACScope(this));
3706       p.mReflectionScope = ReflectionScope::NAC;
3707     }
3708   } else {
3709     MOZ_ASSERT(!ShouldUseNACScope(this));
3710     MOZ_ASSERT(!ShouldUseUAWidgetScope(this));
3711   }
3712   return p;
3713 }
3714
3715 void nsINode::AddMutationObserver(
3716     nsMultiMutationObserver* aMultiMutationObserver) {
3717   if (aMultiMutationObserver) {
3718     NS_ASSERTION(!aMultiMutationObserver->ContainsNode(this),
3719                  "Observer already in the list");
3720     aMultiMutationObserver->AddMutationObserverToNode(this);
3721   }
3722 }
3723
3724 void nsINode::AddMutationObserverUnlessExists(
3725     nsMultiMutationObserver* aMultiMutationObserver) {
3726   if (aMultiMutationObserver && !aMultiMutationObserver->ContainsNode(this)) {
3727     aMultiMutationObserver->AddMutationObserverToNode(this);
3728   }
3729 }
3730
3731 void nsINode::RemoveMutationObserver(
3732     nsMultiMutationObserver* aMultiMutationObserver) {
3733   if (aMultiMutationObserver) {
3734     aMultiMutationObserver->RemoveMutationObserverFromNode(this);
3735   }
3736 }
3737
3738 void nsINode::FireNodeRemovedForChildren() {
3739   Document* doc = OwnerDoc();
3740   // Optimize the common case
3741   if (!nsContentUtils::HasMutationListeners(
3742           doc, NS_EVENT_BITS_MUTATION_NODEREMOVED)) {
3743     return;
3744   }
3745
3746   nsCOMPtr<nsINode> child;
3747   for (child = GetFirstChild(); child && child->GetParentNode() == this;
3748        child = child->GetNextSibling()) {
3749     nsContentUtils::MaybeFireNodeRemoved(child, this);
3750   }
3751 }
3752
3753 NS_IMPL_ISUPPORTS(nsNodeWeakReference, nsIWeakReference)
3754
3755 nsNodeWeakReference::nsNodeWeakReference(nsINode* aNode)
3756     : nsIWeakReference(aNode) {}
3757
3758 nsNodeWeakReference::~nsNodeWeakReference() {
3759   nsINode* node = static_cast<nsINode*>(mObject);
3760
3761   if (node) {
3762     NS_ASSERTION(node->Slots()->mWeakReference == this,
3763                  "Weak reference has wrong value");
3764     node->Slots()->mWeakReference = nullptr;
3765   }
3766 }
3767
3768 NS_IMETHODIMP
3769 nsNodeWeakReference::QueryReferentFromScript(const nsIID& aIID,
3770                                              void** aInstancePtr) {
3771   return QueryReferent(aIID, aInstancePtr);
3772 }
3773
3774 size_t nsNodeWeakReference::SizeOfOnlyThis(
3775     mozilla::MallocSizeOf aMallocSizeOf) {
3776   return aMallocSizeOf(this);
3777 }