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