Quelle  nsINode.cpp   Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Base class for all DOM nodes.
 */

#include "nsINode.h"

#include "AccessCheck.h"
#include "jsapi.h"
#include "js/ForOfIterator.h"  // JS::ForOfIterator
#include "js/JSON.h"           // JS_ParseJSON
#include "mozAutoDocUpdate.h"
#include "mozilla/AsyncEventDispatcher.h"
#include "mozilla/ClearOnShutdown.h"
#include "mozilla/CORSMode.h"
#include "mozilla/EventDispatcher.h"
#include "mozilla/EventListenerManager.h"
#include "mozilla/HTMLEditor.h"
#include "mozilla/InternalMutationEvent.h"
#include "mozilla/Likely.h"
#include "mozilla/Maybe.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/PresShell.h"
#include "mozilla/ServoBindings.h"
#include "mozilla/Telemetry.h"
#include "mozilla/TextControlElement.h"
#include "mozilla/TextEditor.h"
#include "mozilla/TimeStamp.h"
#include "mozilla/dom/BindContext.h"
#include "mozilla/dom/CharacterData.h"
#include "mozilla/dom/ChildIterator.h"
#include "mozilla/dom/CustomElementRegistry.h"
#include "mozilla/dom/DebuggerNotificationBinding.h"
#include "mozilla/dom/DocumentType.h"
#include "mozilla/dom/Element.h"
#include "mozilla/dom/ElementBinding.h"
#include "mozilla/dom/Event.h"
#include "mozilla/dom/Exceptions.h"
#include "mozilla/dom/Link.h"
#include "mozilla/dom/HTMLImageElement.h"
#include "mozilla/dom/HTMLMediaElement.h"
#include "mozilla/dom/HTMLTemplateElement.h"
#include "mozilla/dom/MutationObservers.h"
#include "mozilla/dom/Selection.h"
#include "mozilla/dom/ShadowRoot.h"
#include "mozilla/dom/SVGUseElement.h"
#include "mozilla/dom/ScriptSettings.h"
#include "mozilla/dom/L10nOverlays.h"
#include "mozilla/ProfilerLabels.h"
#include "mozilla/StaticPrefs_layout.h"
#include "nsAttrValueOrString.h"
#include "nsCCUncollectableMarker.h"
#include "nsContentCreatorFunctions.h"
#include "nsContentList.h"
#include "nsContentUtils.h"
#include "nsCOMArray.h"
#include "nsCycleCollectionParticipant.h"
#include "mozilla/dom/Attr.h"
#include "nsDOMAttributeMap.h"
#include "nsDOMCID.h"
#include "nsDOMCSSAttrDeclaration.h"
#include "nsError.h"
#include "nsExpirationTracker.h"
#include "nsDOMMutationObserver.h"
#include "nsDOMString.h"
#include "nsDOMTokenList.h"
#include "nsFocusManager.h"
#include "nsFrameSelection.h"
#include "nsGenericHTMLElement.h"
#include "nsGkAtoms.h"
#include "nsIAnonymousContentCreator.h"
#include "nsAtom.h"
#include "nsIContentInlines.h"
#include "mozilla/dom/Document.h"
#include "mozilla/dom/DocumentInlines.h"
#include "nsIFrameInlines.h"
#include "mozilla/dom/NodeInfo.h"
#include "mozilla/dom/NodeInfoInlines.h"
#include "nsIScriptGlobalObject.h"
#include "nsView.h"
#include "nsViewManager.h"
#include "nsIWidget.h"
#include "nsLayoutUtils.h"
#include "nsNameSpaceManager.h"
#include "nsNodeInfoManager.h"
#include "nsObjectLoadingContent.h"
#include "nsPIDOMWindow.h"
#include "nsPresContext.h"
#include "nsPrintfCString.h"
#include "nsRange.h"
#include "nsString.h"
#include "nsStyleConsts.h"
#include "nsTextNode.h"
#include "nsUnicharUtils.h"
#include "nsWindowSizes.h"
#include "mozilla/Preferences.h"
#include "xpcpublic.h"
#include "HTMLLegendElement.h"
#include "nsWrapperCacheInlines.h"
#include "WrapperFactory.h"
#include <algorithm>
#include "nsGlobalWindowInner.h"
#include "GeometryUtils.h"
#include "nsIAnimationObserver.h"
#include "nsChildContentList.h"
#include "mozilla/dom/NodeBinding.h"
#include "mozilla/dom/BindingDeclarations.h"
#include "mozilla/dom/AncestorIterator.h"
#include "xpcprivate.h"

#include "XPathGenerator.h"

#ifdef ACCESSIBILITY
#  include "mozilla/dom/AccessibleNode.h"
#endif

using namespace mozilla;
using namespace mozilla::dom;

static bool ShouldUseNACScope(const nsINode* aNode) {
  return aNode->IsInNativeAnonymousSubtree();
}

static bool ShouldUseUAWidgetScope(const nsINode* aNode) {
  return aNode->HasBeenInUAWidget();
}

void* nsINode::operator new(size_t aSize, nsNodeInfoManager* aManager) {
  if (StaticPrefs::dom_arena_allocator_enabled_AtStartup()) {
    MOZ_ASSERT(aManager, "nsNodeInfoManager needs to be initialized");
    return aManager->Allocate(aSize);
  }
  return ::operator new(aSize);
}
void nsINode::operator delete(void* aPtr) { free_impl(aPtr); }

bool nsINode::IsInclusiveDescendantOf(const nsINode* aNode) const {
  MOZ_ASSERT(aNode, "The node is nullptr.");

  if (aNode == this) {
    return true;
  }

  if (!aNode->HasFlag(NODE_MAY_HAVE_ELEMENT_CHILDREN)) {
    return GetParentNode() == aNode;
  }

  for (nsINode* node : Ancestors(*this)) {
    if (node == aNode) {
      return true;
    }
  }
  return false;
}

bool nsINode::IsInclusiveFlatTreeDescendantOf(const nsINode* aNode) const {
  MOZ_ASSERT(aNode, "The node is nullptr.");

  for (nsINode* node : InclusiveFlatTreeAncestors(*this)) {
    if (node == aNode) {
      return true;
    }
  }
  return false;
}

bool nsINode::IsShadowIncludingInclusiveDescendantOf(
    const nsINode* aNode) const {
  MOZ_ASSERT(aNode, "The node is nullptr.");

  if (this->GetComposedDoc() == aNode) {
    return true;
  }

  const nsINode* node = this;
  do {
    if (node == aNode) {
      return true;
    }

    node = node->GetParentOrShadowHostNode();
  } while (node);

  return false;
}

nsINode::nsSlots::nsSlots() : mWeakReference(nullptr) {}

nsINode::nsSlots::~nsSlots() {
  if (mChildNodes) {
    mChildNodes->InvalidateCacheIfAvailable();
  }

  if (mWeakReference) {
    mWeakReference->NoticeNodeDestruction();
  }
}

void nsINode::nsSlots::Traverse(nsCycleCollectionTraversalCallback& cb) {
  NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(cb, "mSlots->mChildNodes");
  cb.NoteXPCOMChild(mChildNodes);
  for (auto& object : mBoundObjects) {
    NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(cb, "mSlots->mBoundObjects[i]");
    cb.NoteXPCOMChild(object.mObject);
  }
}

static void ClearBoundObjects(nsINode::nsSlots& aSlots, nsINode& aNode) {
  auto objects = std::move(aSlots.mBoundObjects);
  for (auto& object : objects) {
    if (object.mDtor) {
      object.mDtor(object.mObject, &aNode);
    }
  }
  MOZ_ASSERT(aSlots.mBoundObjects.IsEmpty());
}

void nsINode::nsSlots::Unlink(nsINode& aNode) {
  if (mChildNodes) {
    mChildNodes->InvalidateCacheIfAvailable();
    ImplCycleCollectionUnlink(mChildNodes);
  }
  ClearBoundObjects(*this, aNode);
}

//----------------------------------------------------------------------

#ifdef MOZILLA_INTERNAL_API
nsINode::nsINode(already_AddRefed<mozilla::dom::NodeInfo>&& aNodeInfo)
    : mNodeInfo(std::move(aNodeInfo)),
      mParent(nullptr)
#  ifndef BOOL_FLAGS_ON_WRAPPER_CACHE
      ,
      mBoolFlags(0)
#  endif
      ,
      mChildCount(0),
      mPreviousOrLastSibling(nullptr),
      mSubtreeRoot(this),
      mSlots(nullptr) {
  SetIsOnMainThread();
}
#endif

nsINode::~nsINode() {
  MOZ_ASSERT(!HasSlots(), "LastRelease was not called?");
  MOZ_ASSERT(mSubtreeRoot == this, "Didn't restore state properly?");
}

#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
void nsINode::AssertInvariantsOnNodeInfoChange() {
  MOZ_DIAGNOSTIC_ASSERT(!IsInComposedDoc());
  if (nsCOMPtr<Link> link = do_QueryInterface(this)) {
    MOZ_DIAGNOSTIC_ASSERT(!link->HasPendingLinkUpdate());
  }
}
#endif

#ifdef DEBUG
void nsINode::AssertIsRootElementSlow(bool aIsRoot) const {
  const bool isRootSlow = this == OwnerDoc()->GetRootElement();
  MOZ_ASSERT(aIsRoot == isRootSlow);
}
#endif

void* nsINode::GetProperty(const nsAtom* aPropertyName,
                           nsresult* aStatus) const {
  if (!HasProperties()) {  // a fast HasFlag() test
    if (aStatus) {
      *aStatus = NS_PROPTABLE_PROP_NOT_THERE;
    }
    return nullptr;
  }
  return OwnerDoc()->PropertyTable().GetProperty(this, aPropertyName, aStatus);
}

nsresult nsINode::SetProperty(nsAtom* aPropertyName, void* aValue,
                              NSPropertyDtorFunc aDtor, bool aTransfer) {
  nsresult rv = OwnerDoc()->PropertyTable().SetProperty(
      this, aPropertyName, aValue, aDtor, nullptr, aTransfer);
  if (NS_SUCCEEDED(rv)) {
    SetFlags(NODE_HAS_PROPERTIES);
  }

  return rv;
}

void nsINode::RemoveProperty(const nsAtom* aPropertyName) {
  OwnerDoc()->PropertyTable().RemoveProperty(this, aPropertyName);
}

void* nsINode::TakeProperty(const nsAtom* aPropertyName, nsresult* aStatus) {
  return OwnerDoc()->PropertyTable().TakeProperty(this, aPropertyName, aStatus);
}

nsIContentSecurityPolicy* nsINode::GetCsp() const {
  return OwnerDoc()->GetCsp();
}

nsINode::nsSlots* nsINode::CreateSlots() { return new nsSlots(); }

static const nsINode* GetClosestCommonInclusiveAncestorForRangeInSelection(
    const nsINode* aNode) {
  while (aNode &&
         !aNode->IsClosestCommonInclusiveAncestorForRangeInSelection()) {
    const bool isNodeInShadowTree =
        StaticPrefs::dom_shadowdom_selection_across_boundary_enabled() &&
        aNode->IsInShadowTree();
    if (!aNode
             ->IsDescendantOfClosestCommonInclusiveAncestorForRangeInSelection() &&
        !isNodeInShadowTree) {
      return nullptr;
    }
    aNode = StaticPrefs::dom_shadowdom_selection_across_boundary_enabled()
                ? aNode->GetParentOrShadowHostNode()
                : aNode->GetParentNode();
  }
  return aNode;
}

/**
 * A Comparator suitable for mozilla::BinarySearchIf for searching a collection
 * of nsRange* for an overlap of (mNode, mStartOffset) .. (mNode, mEndOffset).
 */
class IsItemInRangeComparator {
 public:
  // @param aStartOffset has to be less or equal to aEndOffset.
  IsItemInRangeComparator(const nsINode& aNode, const uint32_t aStartOffset,
                          const uint32_t aEndOffset,
                          nsContentUtils::NodeIndexCache* aCache)
      : mNode(aNode),
        mStartOffset(aStartOffset),
        mEndOffset(aEndOffset),
        mCache(aCache) {
    MOZ_ASSERT(aStartOffset <= aEndOffset);
  }

  int operator()(const AbstractRange* const aRange) const {
    int32_t cmp = nsContentUtils::ComparePoints_Deprecated(
        &mNode, mEndOffset, aRange->GetMayCrossShadowBoundaryStartContainer(),
        aRange->MayCrossShadowBoundaryStartOffset(), nullptr, mCache);
    if (cmp == 1) {
      cmp = nsContentUtils::ComparePoints_Deprecated(
          &mNode, mStartOffset, aRange->GetMayCrossShadowBoundaryEndContainer(),
          aRange->MayCrossShadowBoundaryEndOffset(), nullptr, mCache);
      if (cmp == -1) {
        return 0;
      }
      return 1;
    }
    return -1;
  }

 private:
  const nsINode& mNode;
  const uint32_t mStartOffset;
  const uint32_t mEndOffset;
  nsContentUtils::NodeIndexCache* mCache;
};

bool nsINode::IsSelected(const uint32_t aStartOffset, const uint32_t aEndOffset,
                         SelectionNodeCache* aCache) const {
  MOZ_ASSERT(aStartOffset <= aEndOffset);
  const nsINode* n = GetClosestCommonInclusiveAncestorForRangeInSelection(this);
  NS_ASSERTION(n || !IsMaybeSelected(),
               "A node without a common inclusive ancestor for a range in "
               "Selection is for sure not selected.");

  // Collect the selection objects for potential ranges.
  AutoTArray<Selection*, 1> ancestorSelections;
  for (; n; n = GetClosestCommonInclusiveAncestorForRangeInSelection(
                n->GetParentNode())) {
    const LinkedList<AbstractRange>* ranges =
        n->GetExistingClosestCommonInclusiveAncestorRanges();
    if (!ranges) {
      continue;
    }
    for (const AbstractRange* range : *ranges) {
      MOZ_ASSERT(range->IsInAnySelection(),
                 "Why is this range registered with a node?");
      // Looks like that IsInSelection() assert fails sometimes...
      if (range->IsInAnySelection()) {
        for (const WeakPtr<Selection>& selection : range->GetSelections()) {
          if (selection && !ancestorSelections.Contains(selection)) {
            ancestorSelections.AppendElement(selection);
          }
        }
      }
    }
  }
  if (aCache && aCache->MaybeCollectNodesAndCheckIfFullySelectedInAnyOf(
                    this, ancestorSelections)) {
    return true;
  }

  nsContentUtils::NodeIndexCache cache;
  IsItemInRangeComparator comparator{*this, aStartOffset, aEndOffset, &cache};
  for (Selection* selection : ancestorSelections) {
    // Binary search the sorted ranges in this selection.
    // (Selection::GetRangeAt returns its ranges ordered).
    size_t low = 0;
    size_t high = selection->RangeCount();

    while (high != low) {
      size_t middle = low + (high - low) / 2;

      const AbstractRange* const range = selection->GetAbstractRangeAt(middle);
      int result = comparator(range);
      if (result == 0) {
        if (!range->Collapsed()) {
          return true;
        }

        if (range->MayCrossShadowBoundary()) {
          MOZ_ASSERT(range->IsDynamicRange(),
                     "range->MayCrossShadowBoundary() can only return true for "
                     "dynamic range");
          StaticRange* crossBoundaryRange =
              range->AsDynamicRange()->GetCrossShadowBoundaryRange();
          MOZ_ASSERT(crossBoundaryRange);
          if (!crossBoundaryRange->Collapsed()) {
            return true;
          }
        }

        const AbstractRange* middlePlus1;
        const AbstractRange* middleMinus1;
        // if node end > start of middle+1, result = 1
        if (middle + 1 < high &&
            (middlePlus1 = selection->GetAbstractRangeAt(middle + 1)) &&
            nsContentUtils::ComparePoints_Deprecated(
                this, aEndOffset, middlePlus1->GetStartContainer(),
                middlePlus1->StartOffset(), nullptr, &cache) > 0) {
          result = 1;
          // if node start < end of middle - 1, result = -1
        } else if (middle >= 1 &&
                   (middleMinus1 = selection->GetAbstractRangeAt(middle - 1)) &&
                   nsContentUtils::ComparePoints_Deprecated(
                       this, aStartOffset, middleMinus1->GetEndContainer(),
                       middleMinus1->EndOffset(), nullptr, &cache) < 0) {
          result = -1;
        } else {
          break;
        }
      }

      if (result < 0) {
        high = middle;
      } else {
        low = middle + 1;
      }
    }
  }

  return false;
}

Element* nsINode::GetAnonymousRootElementOfTextEditor(
    TextEditor** aTextEditor) {
  if (aTextEditor) {
    *aTextEditor = nullptr;
  }
  RefPtr<TextControlElement> textControlElement;
  if (IsInNativeAnonymousSubtree()) {
    textControlElement = TextControlElement::FromNodeOrNull(
        GetClosestNativeAnonymousSubtreeRootParentOrHost());
  } else {
    textControlElement = TextControlElement::FromNode(this);
  }
  if (!textControlElement) {
    return nullptr;
  }
  RefPtr<TextEditor> textEditor = textControlElement->GetTextEditor();
  if (!textEditor) {
    // The found `TextControlElement` may be an input element which is not a
    // text control element.  In this case, such element must not be in a
    // native anonymous tree of a `TextEditor` so this node is not in any
    // `TextEditor`.
    return nullptr;
  }

  Element* rootElement = textEditor->GetRoot();
  if (aTextEditor) {
    textEditor.forget(aTextEditor);
  }
  return rootElement;
}

void nsINode::QueueDevtoolsAnonymousEvent(bool aIsRemove) {
  MOZ_ASSERT(IsRootOfNativeAnonymousSubtree());
  MOZ_ASSERT(OwnerDoc()->DevToolsAnonymousAndShadowEventsEnabled());
  AsyncEventDispatcher* dispatcher = new AsyncEventDispatcher(
      this, aIsRemove ? u"anonymousrootremoved"_ns : u"anonymousrootcreated"_ns,
      CanBubble::eYes, ChromeOnlyDispatch::eYes, Composed::eYes);
  dispatcher->PostDOMEvent();
}

nsINode* nsINode::GetRootNode(const GetRootNodeOptions& aOptions) {
  if (aOptions.mComposed) {
    if (Document* doc = GetComposedDoc()) {
      return doc;
    }

    nsINode* node = this;
    while (node) {
      node = node->SubtreeRoot();
      ShadowRoot* shadow = ShadowRoot::FromNode(node);
      if (!shadow) {
        break;
      }
      node = shadow->GetHost();
    }

    return node;
  }

  return SubtreeRoot();
}

nsIContent* nsINode::GetFirstChildOfTemplateOrNode() {
  if (IsTemplateElement()) {
    DocumentFragment* frag = static_cast<HTMLTemplateElement*>(this)->Content();
    return frag->GetFirstChild();
  }

  return GetFirstChild();
}

nsINode* nsINode::SubtreeRoot() const {
  auto RootOfNode = [](const nsINode* aStart) -> nsINode* {
    const nsINode* node = aStart;
    const nsINode* iter = node;
    while ((iter = iter->GetParentNode())) {
      node = iter;
    }
    return const_cast<nsINode*>(node);
  };

  // There are four cases of interest here.  nsINodes that are really:
  // 1. Document nodes - Are always in the document.
  // 2.a nsIContent nodes not in a shadow tree - Are either in the document,
  //     or mSubtreeRoot is updated in BindToTree/UnbindFromTree.
  // 2.b nsIContent nodes in a shadow tree - Are never in the document,
  //     ignore mSubtreeRoot and return the containing shadow root.
  // 4. Attr nodes - Are never in the document, and mSubtreeRoot
  //    is always 'this' (as set in nsINode's ctor).
  nsINode* node;
  if (IsInUncomposedDoc()) {
    node = OwnerDocAsNode();
  } else if (IsContent()) {
    ShadowRoot* containingShadow = AsContent()->GetContainingShadow();
    node = containingShadow ? containingShadow : mSubtreeRoot;
    if (!node) {
      NS_WARNING("Using SubtreeRoot() on unlinked element?");
      node = RootOfNode(this);
    }
  } else {
    node = mSubtreeRoot;
  }
  MOZ_ASSERT(node, "Should always have a node here!");
#ifdef DEBUG
  {
    const nsINode* slowNode = RootOfNode(this);
    MOZ_ASSERT(slowNode == node, "These should always be in sync!");
  }
#endif
  return node;
}

static nsIContent* GetRootForContentSubtree(nsIContent* aContent) {
  NS_ENSURE_TRUE(aContent, nullptr);

  // Special case for ShadowRoot because the ShadowRoot itself is
  // the root. This is necessary to prevent selection from crossing
  // the ShadowRoot boundary.
  //
  // FIXME(emilio): The NAC check should probably be done before this? We can
  // have NAC inside shadow DOM.
  if (ShadowRoot* containingShadow = aContent->GetContainingShadow()) {
    return containingShadow;
  }
  if (nsIContent* nativeAnonRoot =
          aContent->GetClosestNativeAnonymousSubtreeRoot()) {
    return nativeAnonRoot;
  }
  if (Document* doc = aContent->GetUncomposedDoc()) {
    return doc->GetRootElement();
  }
  return nsIContent::FromNode(aContent->SubtreeRoot());
}

nsIContent* nsINode::GetSelectionRootContent(PresShell* aPresShell,
                                             bool aAllowCrossShadowBoundary) {
  NS_ENSURE_TRUE(aPresShell, nullptr);

  const bool isContent = IsContent();

  if (!isContent && !IsDocument()) {
    return nullptr;
  }

  if (isContent) {
    if (GetComposedDoc() != aPresShell->GetDocument()) {
      return nullptr;
    }

    if (AsContent()->HasIndependentSelection() ||
        IsInNativeAnonymousSubtree()) {
      // This node should be an inclusive descendant of input/textarea editor.
      // In that case, the anonymous <div> for TextEditor should be always the
      // selection root.
      // FIXME: If Selection for the document is collapsed in <input> or
      // <textarea>, returning anonymous <div> may make the callers confused.
      // Perhaps, we should do this only when this is in the native anonymous
      // subtree unless the callers explicitly want to retrieve the anonymous
      // <div> from a text control element.
      if (Element* anonymousDivElement =
              GetAnonymousRootElementOfTextEditor()) {
        return anonymousDivElement;
      }
    }
  }

  if (nsPresContext* presContext = aPresShell->GetPresContext()) {
    if (nsContentUtils::GetHTMLEditor(presContext)) {
      // When there is an HTMLEditor, selection root should be one of focused
      // editing host, <body> or root of the (sub)tree which this node belong.

      // If this node is in design mode or this node is not editable, selection
      // root should be the <body> if this node is not in any subtrees and there
      // is a <body> or the root of the shadow DOM if this node is in a shadow
      // or the document element.
      // XXX If this node is not connected, it seems that this should return
      // nullptr because this node is not selectable.
      if (!IsInComposedDoc() || IsInDesignMode() ||
          !HasFlag(NODE_IS_EDITABLE)) {
        Element* const bodyOrDocumentElement = [&]() -> Element* {
          if (Element* const bodyElement = OwnerDoc()->GetBodyElement()) {
            return bodyElement;
          }
          return OwnerDoc()->GetDocumentElement();
        }();
        NS_ENSURE_TRUE(bodyOrDocumentElement, nullptr);
        return nsContentUtils::IsInSameAnonymousTree(this,
                                                     bodyOrDocumentElement)
                   ? bodyOrDocumentElement
                   : GetRootForContentSubtree(AsContent());
      }
      // If this node is editable but not in the design mode, this is always an
      // editable node in an editing host of contenteditable.  In this case,
      // let's use the editing host element as selection root.
      MOZ_ASSERT(IsEditable());
      MOZ_ASSERT(!IsInDesignMode());
      MOZ_ASSERT(IsContent());
      return static_cast<nsIContent*>(this)->GetEditingHost();
    }
  }

  if (!isContent) {
    return nullptr;
  }

  RefPtr<nsFrameSelection> fs = aPresShell->FrameSelection();
  nsCOMPtr<nsIContent> content = fs->GetLimiter();
  if (!content) {
    content = fs->GetAncestorLimiter();
    if (!content) {
      Document* doc = aPresShell->GetDocument();
      NS_ENSURE_TRUE(doc, nullptr);
      content = doc->GetRootElement();
      if (!content) return nullptr;
    }
  }

  // This node might be in another subtree, if so, we should find this subtree's
  // root.  Otherwise, we can return the content simply.
  NS_ENSURE_TRUE(content, nullptr);
  if (!nsContentUtils::IsInSameAnonymousTree(this, content)) {
    content = GetRootForContentSubtree(AsContent());
    // Fixup for ShadowRoot because the ShadowRoot itself does not have a frame.
    // Use the host as the root.
    if (ShadowRoot* shadowRoot = ShadowRoot::FromNode(content)) {
      content = shadowRoot->GetHost();
      if (content && aAllowCrossShadowBoundary) {
        content = content->GetSelectionRootContent(aPresShell,
                                                   aAllowCrossShadowBoundary);
      }
    }
  }

  return content;
}

nsINodeList* nsINode::ChildNodes() {
  nsSlots* slots = Slots();
  if (!slots->mChildNodes) {
    slots->mChildNodes = IsAttr() ? new nsAttrChildContentList(this)
                                  : new nsParentNodeChildContentList(this);
  }

  return slots->mChildNodes;
}

nsIContent* nsINode::GetLastChild() const {
  return mFirstChild ? mFirstChild->mPreviousOrLastSibling : nullptr;
}

void nsINode::InvalidateChildNodes() {
  MOZ_ASSERT(!IsAttr());

  nsSlots* slots = GetExistingSlots();
  if (!slots || !slots->mChildNodes) {
    return;
  }

  auto childNodes =
      static_cast<nsParentNodeChildContentList*>(slots->mChildNodes.get());
  childNodes->InvalidateCache();
}

void nsINode::GetTextContentInternal(nsAString& aTextContent,
                                     OOMReporter& aError) {
  SetDOMStringToNull(aTextContent);
}

DocumentOrShadowRoot* nsINode::GetContainingDocumentOrShadowRoot() const {
  if (IsInUncomposedDoc()) {
    return OwnerDoc();
  }

  if (IsInShadowTree()) {
    return AsContent()->GetContainingShadow();
  }

  return nullptr;
}

DocumentOrShadowRoot* nsINode::GetUncomposedDocOrConnectedShadowRoot() const {
  if (IsInUncomposedDoc()) {
    return OwnerDoc();
  }

  if (IsInComposedDoc() && IsInShadowTree()) {
    return AsContent()->GetContainingShadow();
  }

  return nullptr;
}

mozilla::SafeDoublyLinkedList<nsIMutationObserver>*
nsINode::GetMutationObservers() {
  return HasSlots() ? &GetExistingSlots()->mMutationObservers : nullptr;
}

void nsINode::LastRelease() {
  if (nsSlots* slots = GetExistingSlots()) {
    if (!slots->mMutationObservers.isEmpty()) {
      for (auto iter = slots->mMutationObservers.begin();
           iter != slots->mMutationObservers.end(); ++iter) {
        iter->NodeWillBeDestroyed(this);
      }
    }
    ClearBoundObjects(*slots, *this);
    if (IsContent()) {
      nsIContent* content = AsContent();
      if (HTMLSlotElement* slot = content->GetManualSlotAssignment()) {
        content->SetManualSlotAssignment(nullptr);
        slot->RemoveManuallyAssignedNode(*content);
      }
    }

    if (Element* element = Element::FromNode(this)) {
      if (CustomElementData* data = element->GetCustomElementData()) {
        data->Unlink();
      }
    }

    delete slots;
    mSlots = nullptr;
  }

  // Kill properties first since that may run external code, so we want to
  // be in as complete state as possible at that time.
  if (IsDocument()) {
    // Delete all properties before tearing down the document. Some of the
    // properties are bound to nsINode objects and the destructor functions of
    // the properties may want to use the owner document of the nsINode.
    AsDocument()->RemoveAllProperties();
    AsDocument()->DropStyleSet();
  } else {
    if (HasProperties()) {
      // Strong reference to the document so that deleting properties can't
      // delete the document.
      nsCOMPtr<Document> document = OwnerDoc();
      document->RemoveAllPropertiesFor(this);
    }

    if (HasFlag(ADDED_TO_FORM)) {
      if (auto* formControl = nsGenericHTMLFormControlElement::FromNode(this)) {
        // Tell the form (if any) this node is going away.  Don't
        // notify, since we're being destroyed in any case.
        formControl->ClearForm(true, true);
      } else if (auto* imageElem = HTMLImageElement::FromNode(this)) {
        imageElem->ClearForm(true);
      }
    }
    if (HasFlag(NODE_HAS_LISTENERMANAGER)) {
#ifdef DEBUG
      if (nsContentUtils::IsInitialized()) {
        EventListenerManager* manager =
            nsContentUtils::GetExistingListenerManagerForNode(this);
        if (!manager) {
          NS_ERROR(
              "Huh, our bit says we have a listener manager list, "
              "but there's nothing in the hash!?!!");
        }
      }
#endif

      nsContentUtils::RemoveListenerManager(this);
      UnsetFlags(NODE_HAS_LISTENERMANAGER);
    }

    if (Element* element = Element::FromNode(this)) {
      element->ClearAttributes();
    }
  }

  UnsetFlags(NODE_HAS_PROPERTIES);
  ReleaseWrapper(this);

  FragmentOrElement::RemoveBlackMarkedNode(this);
}

std::ostream& operator<<(std::ostream& aStream, const nsINode& aNode) {
  nsAutoString elemDesc;
  const nsINode* curr = &aNode;
  while (curr) {
    nsString id, cls;
    if (curr->IsElement()) {
      curr->AsElement()->GetId(id);
      if (const nsAttrValue* attrValue = curr->AsElement()->GetClasses()) {
        attrValue->ToString(cls);
      }
    }

    if (!elemDesc.IsEmpty()) {
      elemDesc = elemDesc + u"."_ns;
    }

    if (!curr->LocalName().IsEmpty()) {
      elemDesc.Append(curr->LocalName());
    } else {
      elemDesc.Append(curr->NodeName());
    }

    if (!id.IsEmpty()) {
      elemDesc = elemDesc + u"['"_ns + id + u"']"_ns;
    } else if (!cls.IsEmpty()) {
      elemDesc = elemDesc + u"[class=\""_ns + cls + u"\"]"_ns;
    }

    if (curr->IsElement() &&
        curr->AsElement()->HasAttr(nsGkAtoms::contenteditable)) {
      nsAutoString val;
      curr->AsElement()->GetAttr(nsGkAtoms::contenteditable, val);
      elemDesc = elemDesc + u"[contenteditable=\""_ns + val + u"\"]"_ns;
    }
    if (curr->IsDocument() && curr->IsInDesignMode()) {
      elemDesc.Append(u"[designMode=\"on\"]"_ns);
    }

    curr = curr->GetParentNode();
  }

  NS_ConvertUTF16toUTF8 str(elemDesc);
  return aStream << str.get();
}

nsIContent* nsINode::DoGetShadowHost() const {
  MOZ_ASSERT(IsShadowRoot());
  return static_cast<const ShadowRoot*>(this)->GetHost();
}

ShadowRoot* nsINode::GetContainingShadow() const {
  if (!IsInShadowTree()) {
    return nullptr;
  }
  return AsContent()->GetContainingShadow();
}

Element* nsINode::GetContainingShadowHost() const {
  if (ShadowRoot* shadow = GetContainingShadow()) {
    return shadow->GetHost();
  }
  return nullptr;
}

SVGUseElement* nsINode::DoGetContainingSVGUseShadowHost() const {
  MOZ_ASSERT(IsInShadowTree());
  return SVGUseElement::FromNodeOrNull(GetContainingShadowHost());
}

void nsINode::GetNodeValueInternal(nsAString& aNodeValue) {
  SetDOMStringToNull(aNodeValue);
}

static const char* NodeTypeAsString(nsINode* aNode) {
  static const char* NodeTypeStrings[] = {
      "",  // No nodes of type 0
      "an Element",
      "an Attribute",
      "a Text",
      "a CDATASection",
      "an EntityReference",
      "an Entity",
      "a ProcessingInstruction",
      "a Comment",
      "a Document",
      "a DocumentType",
      "a DocumentFragment",
      "a Notation",
  };
  static_assert(std::size(NodeTypeStrings) == nsINode::MAX_NODE_TYPE + 1,
                "Max node type out of range for our array");

  uint16_t nodeType = aNode->NodeType();
  MOZ_RELEASE_ASSERT(nodeType < std::size(NodeTypeStrings),
                     "Uknown out-of-range node type");
  return NodeTypeStrings[nodeType];
}

nsINode* nsINode::RemoveChild(nsINode& aOldChild, ErrorResult& aError) {
  if (!aOldChild.IsContent()) {
    // aOldChild can't be one of our children.
    aError.ThrowNotFoundError(
        "The node to be removed is not a child of this node");
    return nullptr;
  }

  if (aOldChild.GetParentNode() == this) {
    nsContentUtils::MaybeFireNodeRemoved(&aOldChild, this);
  }

  // Check again, we may not be the child's parent anymore.
  // Can be triggered by dom/base/crashtests/293388-1.html
  if (aOldChild.IsRootOfNativeAnonymousSubtree() ||
      aOldChild.GetParentNode() != this) {
    // aOldChild isn't one of our children.
    aError.ThrowNotFoundError(
        "The node to be removed is not a child of this node");
    return nullptr;
  }

  RemoveChildNode(aOldChild.AsContent(), true);
  return &aOldChild;
}

void nsINode::Normalize() {
  // First collect list of nodes to be removed
  AutoTArray<nsCOMPtr<nsIContent>, 50> nodes;

  bool canMerge = false;
  for (nsIContent* node = this->GetFirstChild(); node;
       node = node->GetNextNode(this)) {
    if (node->NodeType() != TEXT_NODE) {
      canMerge = false;
      continue;
    }

    if (canMerge || node->TextLength() == 0) {
      // No need to touch canMerge. That way we can merge across empty
      // textnodes if and only if the node before is a textnode
      nodes.AppendElement(node);
    } else {
      canMerge = true;
    }

    // If there's no following sibling, then we need to ensure that we don't
    // collect following siblings of our (grand)parent as to-be-removed
    canMerge = canMerge && !!node->GetNextSibling();
  }

  if (nodes.IsEmpty()) {
    return;
  }

  // We're relying on mozAutoSubtreeModified to keep the doc alive here.
  RefPtr<Document> doc = OwnerDoc();

  // Batch possible DOMSubtreeModified events.
  mozAutoSubtreeModified subtree(doc, nullptr);

  // Fire all DOMNodeRemoved events. Optimize the common case of there being
  // no listeners
  bool hasRemoveListeners = nsContentUtils::HasMutationListeners(
      doc, NS_EVENT_BITS_MUTATION_NODEREMOVED);
  if (hasRemoveListeners) {
    for (nsCOMPtr<nsIContent>& node : nodes) {
      // Node may have already been removed.
      if (nsCOMPtr<nsINode> parentNode = node->GetParentNode()) {
        // TODO: Bug 1622253
        nsContentUtils::MaybeFireNodeRemoved(MOZ_KnownLive(node), parentNode);
      }
    }
  }

  mozAutoDocUpdate batch(doc, true);

  // Merge and remove all nodes
  nsAutoString tmpStr;
  for (uint32_t i = 0; i < nodes.Length(); ++i) {
    nsIContent* node = nodes[i];
    // Merge with previous node unless empty
    const nsTextFragment* text = node->GetText();
    if (text->GetLength()) {
      nsIContent* target = node->GetPreviousSibling();
      NS_ASSERTION(
          (target && target->NodeType() == TEXT_NODE) || hasRemoveListeners,
          "Should always have a previous text sibling unless "
          "mutation events messed us up");
      if (!hasRemoveListeners || (target && target->NodeType() == TEXT_NODE)) {
        nsTextNode* t = static_cast<nsTextNode*>(target);
        if (text->Is2b()) {
          t->AppendTextForNormalize(text->Get2b(), text->GetLength(), true,
                                    node);
        } else {
          tmpStr.Truncate();
          text->AppendTo(tmpStr);
          t->AppendTextForNormalize(tmpStr.get(), tmpStr.Length(), true, node);
        }
      }
    }

    // Remove node
    nsCOMPtr<nsINode> parent = node->GetParentNode();
    NS_ASSERTION(parent || hasRemoveListeners,
                 "Should always have a parent unless "
                 "mutation events messed us up");
    if (parent) {
      parent->RemoveChildNode(node, true);
    }
  }
}

nsresult nsINode::GetBaseURI(nsAString& aURI) const {
  nsIURI* baseURI = GetBaseURI();

  nsAutoCString spec;
  if (baseURI) {
    nsresult rv = baseURI->GetSpec(spec);
    NS_ENSURE_SUCCESS(rv, rv);
  }

  CopyUTF8toUTF16(spec, aURI);
  return NS_OK;
}

void nsINode::GetBaseURIFromJS(nsAString& aURI, CallerType aCallerType,
                               ErrorResult& aRv) const {
  nsIURI* baseURI = GetBaseURI(aCallerType == CallerType::System);
  nsAutoCString spec;
  if (baseURI) {
    nsresult res = baseURI->GetSpec(spec);
    if (NS_FAILED(res)) {
      aRv.Throw(res);
      return;
    }
  }
  CopyUTF8toUTF16(spec, aURI);
}

nsIURI* nsINode::GetBaseURIObject() const { return GetBaseURI(true); }

void nsINode::LookupPrefix(const nsAString& aNamespaceURI, nsAString& aPrefix) {
  if (Element* nsElement = GetNameSpaceElement()) {
    // XXX Waiting for DOM spec to list error codes.

    // Trace up the content parent chain looking for the namespace
    // declaration that defines the aNamespaceURI namespace. Once found,
    // return the prefix (i.e. the attribute localName).
    for (Element* element : nsElement->InclusiveAncestorsOfType<Element>()) {
      uint32_t attrCount = element->GetAttrCount();

      for (uint32_t i = 0; i < attrCount; ++i) {
        const nsAttrName* name = element->GetAttrNameAt(i);

        if (name->NamespaceEquals(kNameSpaceID_XMLNS) &&
            element->AttrValueIs(kNameSpaceID_XMLNS, name->LocalName(),
                                 aNamespaceURI, eCaseMatters)) {
          // If the localName is "xmlns", the prefix we output should be
          // null.
          nsAtom* localName = name->LocalName();

          if (localName != nsGkAtoms::xmlns) {
            localName->ToString(aPrefix);
          } else {
            SetDOMStringToNull(aPrefix);
          }
          return;
        }
      }
    }
  }

  SetDOMStringToNull(aPrefix);
}

uint16_t nsINode::CompareDocumentPosition(nsINode& aOtherNode,
                                          Maybe<uint32_t>* aThisIndex,
                                          Maybe<uint32_t>* aOtherIndex) const {
  if (this == &aOtherNode) {
    return 0;
  }
  if (GetPreviousSibling() == &aOtherNode) {
    MOZ_ASSERT(GetParentNode() == aOtherNode.GetParentNode());
    return Node_Binding::DOCUMENT_POSITION_PRECEDING;
  }
  if (GetNextSibling() == &aOtherNode) {
    MOZ_ASSERT(GetParentNode() == aOtherNode.GetParentNode());
    return Node_Binding::DOCUMENT_POSITION_FOLLOWING;
  }

  AutoTArray<const nsINode*, 32> parents1, parents2;

  const nsINode* node1 = &aOtherNode;
  const nsINode* node2 = this;

  // Check if either node is an attribute
  const Attr* attr1 = Attr::FromNode(node1);
  if (attr1) {
    const Element* elem = attr1->GetElement();
    // If there is an owner element add the attribute
    // to the chain and walk up to the element
    if (elem) {
      node1 = elem;
      parents1.AppendElement(attr1);
    }
  }
  if (auto* attr2 = Attr::FromNode(node2)) {
    const Element* elem = attr2->GetElement();
    if (elem == node1 && attr1) {
      // Both nodes are attributes on the same element.
      // Compare position between the attributes.

      uint32_t i;
      const nsAttrName* attrName;
      for (i = 0; (attrName = elem->GetAttrNameAt(i)); ++i) {
        if (attrName->Equals(attr1->NodeInfo())) {
          NS_ASSERTION(!attrName->Equals(attr2->NodeInfo()),
                       "Different attrs at same position");
          return Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC |
                 Node_Binding::DOCUMENT_POSITION_PRECEDING;
        }
        if (attrName->Equals(attr2->NodeInfo())) {
          return Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC |
                 Node_Binding::DOCUMENT_POSITION_FOLLOWING;
        }
      }
      MOZ_ASSERT_UNREACHABLE("neither attribute in the element");
      return Node_Binding::DOCUMENT_POSITION_DISCONNECTED;
    }

    if (elem) {
      node2 = elem;
      parents2.AppendElement(attr2);
    }
  }

  // We now know that both nodes are either nsIContents or Documents.
  // If either node started out as an attribute, that attribute will have
  // the same relative position as its ownerElement, except if the
  // ownerElement ends up being the container for the other node

  // Build the chain of parents
  do {
    parents1.AppendElement(node1);
    node1 = node1->GetParentNode();
  } while (node1);
  do {
    parents2.AppendElement(node2);
    node2 = node2->GetParentNode();
  } while (node2);

  // Check if the nodes are disconnected.
  uint32_t pos1 = parents1.Length();
  uint32_t pos2 = parents2.Length();
  const nsINode* top1 = parents1.ElementAt(--pos1);
  const nsINode* top2 = parents2.ElementAt(--pos2);
  if (top1 != top2) {
    return top1 < top2
               ? (Node_Binding::DOCUMENT_POSITION_PRECEDING |
                  Node_Binding::DOCUMENT_POSITION_DISCONNECTED |
                  Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC)
               : (Node_Binding::DOCUMENT_POSITION_FOLLOWING |
                  Node_Binding::DOCUMENT_POSITION_DISCONNECTED |
                  Node_Binding::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC);
  }

  // Find where the parent chain differs and check indices in the parent.
  const nsINode* parent = top1;
  uint32_t len;
  for (len = std::min(pos1, pos2); len > 0; --len) {
    const nsINode* child1 = parents1.ElementAt(--pos1);
    const nsINode* child2 = parents2.ElementAt(--pos2);
    if (child1 != child2) {
      // child1 or child2 can be an attribute here. This will work fine since
      // ComputeIndexOf will return Nothing for the attribute making the
      // attribute be considered before any child.
      Maybe<uint32_t> child1Index;
      bool cachedChild1Index = false;
      if (&aOtherNode == child1 && aOtherIndex) {
        cachedChild1Index = true;
        child1Index = aOtherIndex->isSome() ? *aOtherIndex
                                            : parent->ComputeIndexOf(child1);
      } else {
        child1Index = parent->ComputeIndexOf(child1);
      }

      Maybe<uint32_t> child2Index;
      bool cachedChild2Index = false;
      if (this == child2 && aThisIndex) {
        cachedChild2Index = true;
        child2Index =
            aThisIndex->isSome() ? *aThisIndex : parent->ComputeIndexOf(child2);
      } else {
        child2Index = parent->ComputeIndexOf(child2);
      }

      uint16_t retVal = child1Index < child2Index
                            ? Node_Binding::DOCUMENT_POSITION_PRECEDING
                            : Node_Binding::DOCUMENT_POSITION_FOLLOWING;

      if (cachedChild1Index) {
        *aOtherIndex = child1Index;
      }
      if (cachedChild2Index) {
        *aThisIndex = child2Index;
      }

      return retVal;
    }
    parent = child1;
  }

  // We hit the end of one of the parent chains without finding a difference
  // between the chains. That must mean that one node is an ancestor of the
  // other. The one with the shortest chain must be the ancestor.
  return pos1 < pos2 ? (Node_Binding::DOCUMENT_POSITION_PRECEDING |
                        Node_Binding::DOCUMENT_POSITION_CONTAINS)
                     : (Node_Binding::DOCUMENT_POSITION_FOLLOWING |
                        Node_Binding::DOCUMENT_POSITION_CONTAINED_BY);
}

bool nsINode::IsSameNode(nsINode* other) { return other == this; }

bool nsINode::IsEqualNode(nsINode* aOther) {
  if (!aOther) {
    return false;
  }

  // Might as well do a quick check to avoid walking our kids if we're
  // obviously the same.
  if (aOther == this) {
    return true;
  }

  nsAutoString string1, string2;

  nsINode* node1 = this;
  nsINode* node2 = aOther;
  do {
    uint16_t nodeType = node1->NodeType();
    if (nodeType != node2->NodeType()) {
      return false;
    }

    mozilla::dom::NodeInfo* nodeInfo1 = node1->mNodeInfo;
    mozilla::dom::NodeInfo* nodeInfo2 = node2->mNodeInfo;
    if (!nodeInfo1->Equals(nodeInfo2) ||
        nodeInfo1->GetExtraName() != nodeInfo2->GetExtraName()) {
      return false;
    }

    switch (nodeType) {
      case ELEMENT_NODE: {
        // Both are elements (we checked that their nodeinfos are equal). Do the
        // check on attributes.
        Element* element1 = node1->AsElement();
        Element* element2 = node2->AsElement();
        uint32_t attrCount = element1->GetAttrCount();
        if (attrCount != element2->GetAttrCount()) {
          return false;
        }

        // Iterate over attributes.
        for (uint32_t i = 0; i < attrCount; ++i) {
          const nsAttrName* attrName = element1->GetAttrNameAt(i);
#ifdef DEBUG
          bool hasAttr =
#endif
              element1->GetAttr(attrName->NamespaceID(), attrName->LocalName(),
                                string1);
          NS_ASSERTION(hasAttr, "Why don't we have an attr?");

          if (!element2->AttrValueIs(attrName->NamespaceID(),
                                     attrName->LocalName(), string1,
                                     eCaseMatters)) {
            return false;
          }
        }
        break;
      }
      case TEXT_NODE:
      case COMMENT_NODE:
      case CDATA_SECTION_NODE:
      case PROCESSING_INSTRUCTION_NODE: {
        MOZ_ASSERT(node1->IsCharacterData());
        MOZ_ASSERT(node2->IsCharacterData());
        auto* data1 = static_cast<CharacterData*>(node1);
        auto* data2 = static_cast<CharacterData*>(node2);

        if (!data1->TextEquals(data2)) {
          return false;
        }

        break;
      }
      case DOCUMENT_NODE:
      case DOCUMENT_FRAGMENT_NODE:
        break;
      case ATTRIBUTE_NODE: {
        NS_ASSERTION(node1 == this && node2 == aOther,
                     "Did we come upon an attribute node while walking a "
                     "subtree?");
        node1->GetNodeValue(string1);
        node2->GetNodeValue(string2);

        // Returning here as to not bother walking subtree. And there is no
        // risk that we're half way through walking some other subtree since
        // attribute nodes doesn't appear in subtrees.
        return string1.Equals(string2);
      }
      case DOCUMENT_TYPE_NODE: {
        DocumentType* docType1 = static_cast<DocumentType*>(node1);
        DocumentType* docType2 = static_cast<DocumentType*>(node2);

        // Public ID
        docType1->GetPublicId(string1);
        docType2->GetPublicId(string2);
        if (!string1.Equals(string2)) {
          return false;
        }

        // System ID
        docType1->GetSystemId(string1);
        docType2->GetSystemId(string2);
        if (!string1.Equals(string2)) {
          return false;
        }

        break;
      }
      default:
        MOZ_ASSERT(false, "Unknown node type");
    }

    nsINode* nextNode = node1->GetFirstChild();
    if (nextNode) {
      node1 = nextNode;
      node2 = node2->GetFirstChild();
    } else {
      if (node2->GetFirstChild()) {
        // node2 has a firstChild, but node1 doesn't
        return false;
      }

      // Find next sibling, possibly walking parent chain.
      while (1) {
        if (node1 == this) {
          NS_ASSERTION(node2 == aOther,
                       "Should have reached the start node "
                       "for both trees at the same time");
          return true;
        }

        nextNode = node1->GetNextSibling();
        if (nextNode) {
          node1 = nextNode;
          node2 = node2->GetNextSibling();
          break;
        }

        if (node2->GetNextSibling()) {
          // node2 has a nextSibling, but node1 doesn't
          return false;
        }

        node1 = node1->GetParentNode();
        node2 = node2->GetParentNode();
        NS_ASSERTION(node1 && node2, "no parent while walking subtree");
      }
    }
  } while (node2);

  return false;
}

void nsINode::LookupNamespaceURI(const nsAString& aNamespacePrefix,
                                 nsAString& aNamespaceURI) {
  Element* element = GetNameSpaceElement();
  if (!element || NS_FAILED(element->LookupNamespaceURIInternal(
                      aNamespacePrefix, aNamespaceURI))) {
    SetDOMStringToNull(aNamespaceURI);
  }
}

mozilla::Maybe<mozilla::dom::EventCallbackDebuggerNotificationType>
nsINode::GetDebuggerNotificationType() const {
  return mozilla::Some(
      mozilla::dom::EventCallbackDebuggerNotificationType::Node);
}

bool nsINode::ComputeDefaultWantsUntrusted(ErrorResult& aRv) {
  return !nsContentUtils::IsChromeDoc(OwnerDoc());
}

void nsINode::GetBoxQuads(const BoxQuadOptions& aOptions,
                          nsTArray<RefPtr<DOMQuad>>& aResult,
                          CallerType aCallerType, mozilla::ErrorResult& aRv) {
  mozilla::GetBoxQuads(this, aOptions, aResult, aCallerType, aRv);
}

void nsINode::GetBoxQuadsFromWindowOrigin(const BoxQuadOptions& aOptions,
                                          nsTArray<RefPtr<DOMQuad>>& aResult,
                                          mozilla::ErrorResult& aRv) {
  mozilla::GetBoxQuadsFromWindowOrigin(this, aOptions, aResult, aRv);
}

already_AddRefed<DOMQuad> nsINode::ConvertQuadFromNode(
    DOMQuad& aQuad, const GeometryNode& aFrom,
    const ConvertCoordinateOptions& aOptions, CallerType aCallerType,
    ErrorResult& aRv) {
  return mozilla::ConvertQuadFromNode(this, aQuad, aFrom, aOptions, aCallerType,
                                      aRv);
}

already_AddRefed<DOMQuad> nsINode::ConvertRectFromNode(
    DOMRectReadOnly& aRect, const GeometryNode& aFrom,
    const ConvertCoordinateOptions& aOptions, CallerType aCallerType,
    ErrorResult& aRv) {
  return mozilla::ConvertRectFromNode(this, aRect, aFrom, aOptions, aCallerType,
                                      aRv);
}

already_AddRefed<DOMPoint> nsINode::ConvertPointFromNode(
    const DOMPointInit& aPoint, const GeometryNode& aFrom,
    const ConvertCoordinateOptions& aOptions, CallerType aCallerType,
    ErrorResult& aRv) {
  return mozilla::ConvertPointFromNode(this, aPoint, aFrom, aOptions,
                                       aCallerType, aRv);
}

bool nsINode::DispatchEvent(Event& aEvent, CallerType aCallerType,
                            ErrorResult& aRv) {
  // XXX sXBL/XBL2 issue -- do we really want the owner here?  What
  // if that's the XBL document?  Would we want its presshell?  Or what?
  nsCOMPtr<Document> document = OwnerDoc();

  // Do nothing if the element does not belong to a document
  if (!document) {
    return true;
  }

  // Obtain a presentation shell
  RefPtr<nsPresContext> context = document->GetPresContext();

  nsEventStatus status = nsEventStatus_eIgnore;
  nsresult rv = EventDispatcher::DispatchDOMEvent(this, nullptr, &aEvent,
                                                  context, &status);
  bool retval = !aEvent.DefaultPrevented(aCallerType);
  if (NS_FAILED(rv)) {
    aRv.Throw(rv);
  }
  return retval;
}

nsresult nsINode::PostHandleEvent(EventChainPostVisitor& /*aVisitor*/) {
  return NS_OK;
}

EventListenerManager* nsINode::GetOrCreateListenerManager() {
  return nsContentUtils::GetListenerManagerForNode(this);
}

EventListenerManager* nsINode::GetExistingListenerManager() const {
  return nsContentUtils::GetExistingListenerManagerForNode(this);
}

nsPIDOMWindowOuter* nsINode::GetOwnerGlobalForBindingsInternal() {
  bool dummy;
  // FIXME(bz): This cast is a bit bogus.  See
  // https://bugzilla.mozilla.org/show_bug.cgi?id=1515709
  auto* window = static_cast<nsGlobalWindowInner*>(
      OwnerDoc()->GetScriptHandlingObject(dummy));
  return window ? nsPIDOMWindowOuter::GetFromCurrentInner(window) : nullptr;
}

nsIGlobalObject* nsINode::GetOwnerGlobal() const {
  bool dummy;
  return OwnerDoc()->GetScriptHandlingObject(dummy);
}

bool nsINode::UnoptimizableCCNode() const {
  return IsInNativeAnonymousSubtree() || IsAttr();
}

/* static */
bool nsINode::Traverse(nsINode* tmp, nsCycleCollectionTraversalCallback& cb) {
  if (MOZ_LIKELY(!cb.WantAllTraces())) {
    Document* currentDoc = tmp->GetComposedDoc();
    if (currentDoc && nsCCUncollectableMarker::InGeneration(
                          currentDoc->GetMarkedCCGeneration())) {
      return false;
    }

    if (nsCCUncollectableMarker::sGeneration) {
      // If we're black no need to traverse.
      if (tmp->HasKnownLiveWrapper() || tmp->InCCBlackTree()) {
        return false;
      }

      if (!tmp->UnoptimizableCCNode()) {
        // If we're in a black document, return early.
        if ((currentDoc && currentDoc->HasKnownLiveWrapper())) {
          return false;
        }
        // If we're not in anonymous content and we have a black parent,
        // return early.
        nsIContent* parent = tmp->GetParent();
        if (parent && !parent->UnoptimizableCCNode() &&
            parent->HasKnownLiveWrapper()) {
          MOZ_ASSERT(parent->ComputeIndexOf(tmp).isSome(),
                     "Parent doesn't own us?");
          return false;
        }
      }
    }
  }

  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mNodeInfo)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mFirstChild)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mNextSibling)
  NS_IMPL_CYCLE_COLLECTION_TRAVERSE_RAWPTR(GetParent())

  if (nsSlots* slots = tmp->GetExistingSlots()) {
    slots->Traverse(cb);
  }

  if (tmp->HasProperties()) {
#ifdef ACCESSIBILITY
    auto* anode = static_cast<AccessibleNode*>(
        tmp->GetProperty(nsGkAtoms::accessiblenode));
    if (anode) {
      cb.NoteXPCOMChild(anode);
    }
#endif
  }

  if (tmp->NodeType() != DOCUMENT_NODE &&
      tmp->HasFlag(NODE_HAS_LISTENERMANAGER)) {
    nsContentUtils::TraverseListenerManager(tmp, cb);
  }

  return true;
}

/* static */
void nsINode::Unlink(nsINode* tmp) {
  tmp->ReleaseWrapper(tmp);

  if (nsSlots* slots = tmp->GetExistingSlots()) {
    slots->Unlink(*tmp);
  }

  if (tmp->NodeType() != DOCUMENT_NODE &&
      tmp->HasFlag(NODE_HAS_LISTENERMANAGER)) {
    nsContentUtils::RemoveListenerManager(tmp);
    tmp->UnsetFlags(NODE_HAS_LISTENERMANAGER);
  }

  if (tmp->HasProperties()) {
    tmp->RemoveProperty(nsGkAtoms::accessiblenode);
  }
}

static void AdoptNodeIntoOwnerDoc(nsINode* aParent, nsINode* aNode,
                                  ErrorResult& aError) {
  NS_ASSERTION(!aNode->GetParentNode(),
               "Should have removed from parent already");

  Document* doc = aParent->OwnerDoc();

  DebugOnly<nsINode*> adoptedNode = doc->AdoptNode(*aNode, aError, true);

#ifdef DEBUG
  if (!aError.Failed()) {
    MOZ_ASSERT(aParent->OwnerDoc() == doc, "ownerDoc chainged while adopting");
    MOZ_ASSERT(adoptedNode == aNode, "Uh, adopt node changed nodes?");
    MOZ_ASSERT(aParent->OwnerDoc() == aNode->OwnerDoc(),
               "ownerDocument changed again after adopting!");
  }
#endif  // DEBUG
}

static nsresult UpdateGlobalsInSubtree(nsIContent* aRoot) {
  MOZ_ASSERT(ShouldUseNACScope(aRoot));
  // Start off with no global so we don't fire any error events on failure.
  AutoJSAPI jsapi;
  jsapi.Init();

  JSContext* cx = jsapi.cx();

  ErrorResult rv;
  JS::Rooted<JSObject*> reflector(cx);
  for (nsIContent* cur = aRoot; cur; cur = cur->GetNextNode(aRoot)) {
    if ((reflector = cur->GetWrapper())) {
      JSAutoRealm ar(cx, reflector);
      UpdateReflectorGlobal(cx, reflector, rv);
      rv.WouldReportJSException();
      if (rv.Failed()) {
        // We _could_ consider BlastSubtreeToPieces here, but it's not really
        // needed.  Having some nodes in here accessible to content while others
        // are not is probably OK.  We just need to fail out of the actual
        // insertion, so they're not in the DOM.  Returning a failure here will
        // do that.
        return rv.StealNSResult();
      }
    }
  }

  return NS_OK;
}

void nsINode::InsertChildBefore(nsIContent* aKid, nsIContent* aBeforeThis,
                                bool aNotify, ErrorResult& aRv) {
  if (!IsContainerNode()) {
    aRv.ThrowHierarchyRequestError(
        "Parent is not a Document, DocumentFragment, or Element node.");
    return;
  }

  MOZ_ASSERT(!aKid->GetParentNode(), "Inserting node that already has parent");
  MOZ_ASSERT(!IsAttr());

  // The id-handling code, and in the future possibly other code, need to
  // react to unexpected attribute changes.
  nsMutationGuard::DidMutate();

  // Do this before checking the child-count since this could cause mutations
  mozAutoDocUpdate updateBatch(GetComposedDoc(), aNotify);

  if (OwnerDoc() != aKid->OwnerDoc()) {
    AdoptNodeIntoOwnerDoc(this, aKid, aRv);
    if (NS_WARN_IF(aRv.Failed())) {
      return;
    }
  }

  if (!aBeforeThis) {
    AppendChildToChildList(aKid);
  } else {
    InsertChildToChildList(aKid, aBeforeThis);
  }

  nsIContent* parent = IsContent() ? AsContent() : nullptr;

  // XXXbz Do we even need this code anymore?
  bool wasInNACScope = ShouldUseNACScope(aKid);
  BindContext context(*this);
  aRv = aKid->BindToTree(context, *this);
  if (!aRv.Failed() && !wasInNACScope && ShouldUseNACScope(aKid)) {
    MOZ_ASSERT(ShouldUseNACScope(this),
               "Why does the kid need to use an the anonymous content scope?");
    aRv = UpdateGlobalsInSubtree(aKid);
  }
  if (aRv.Failed()) {
    DisconnectChild(aKid);
    aKid->UnbindFromTree();
    return;
  }

  // Invalidate cached array of child nodes
  InvalidateChildNodes();

  NS_ASSERTION(aKid->GetParentNode() == this,
               "Did we run script inappropriately?");

  if (aNotify) {
    // Note that we always want to call ContentInserted when things are added
    // as kids to documents
    if (parent && !aBeforeThis) {
      MutationObservers::NotifyContentAppended(parent, aKid);
    } else {
      MutationObservers::NotifyContentInserted(this, aKid);
    }

    if (nsContentUtils::WantMutationEvents(
            aKid, NS_EVENT_BITS_MUTATION_NODEINSERTED, this)) {
      InternalMutationEvent mutation(true, eLegacyNodeInserted);
      mutation.mRelatedNode = this;

      mozAutoSubtreeModified subtree(OwnerDoc(), this);
      AsyncEventDispatcher::RunDOMEventWhenSafe(*aKid, mutation);
    }
  }
}

nsIContent* nsINode::GetPreviousSibling() const {
  // Do not expose circular linked list
  if (mPreviousOrLastSibling && !mPreviousOrLastSibling->mNextSibling) {
    return nullptr;
  }
  return mPreviousOrLastSibling;
}

// CACHE_POINTER_SHIFT indicates how many steps to downshift the |this| pointer.
// It should be small enough to not cause collisions between adjecent objects,
// and large enough to make sure that all indexes are used.
#define CACHE_POINTER_SHIFT 6
#define CACHE_NUM_SLOTS 128
#define CACHE_CHILD_LIMIT 10

#define CACHE_GET_INDEX(_parent) \
  ((NS_PTR_TO_INT32(_parent) >> CACHE_POINTER_SHIFT) & (CACHE_NUM_SLOTS - 1))

struct IndexCacheSlot {
  const nsINode* mParent;
  const nsINode* mChild;
  uint32_t mChildIndex;
};

static IndexCacheSlot sIndexCache[CACHE_NUM_SLOTS];

static inline void AddChildAndIndexToCache(const nsINode* aParent,
                                           const nsINode* aChild,
                                           uint32_t aChildIndex) {
  uint32_t index = CACHE_GET_INDEX(aParent);
  sIndexCache[index].mParent = aParent;
  sIndexCache[index].mChild = aChild;
  sIndexCache[index].mChildIndex = aChildIndex;
}

static inline void GetChildAndIndexFromCache(const nsINode* aParent,
                                             const nsINode** aChild,
                                             Maybe<uint32_t>* aChildIndex) {
  uint32_t index = CACHE_GET_INDEX(aParent);
  if (sIndexCache[index].mParent == aParent) {
    *aChild = sIndexCache[index].mChild;
    *aChildIndex = Some(sIndexCache[index].mChildIndex);
  } else {
    *aChild = nullptr;
    *aChildIndex = Nothing();
  }
}

static inline void RemoveFromCache(const nsINode* aParent) {
  uint32_t index = CACHE_GET_INDEX(aParent);
  if (sIndexCache[index].mParent == aParent) {
    sIndexCache[index] = {nullptr, nullptr, UINT32_MAX};
  }
}

void nsINode::AppendChildToChildList(nsIContent* aKid) {
  MOZ_ASSERT(aKid);
  MOZ_ASSERT(!aKid->mNextSibling);

  RemoveFromCache(this);

  if (mFirstChild) {
    nsIContent* lastChild = GetLastChild();
    lastChild->mNextSibling = aKid;
    aKid->mPreviousOrLastSibling = lastChild;
  } else {
    mFirstChild = aKid;
  }

  // Maintain link to the last child
  mFirstChild->mPreviousOrLastSibling = aKid;
  ++mChildCount;
}

void nsINode::InsertChildToChildList(nsIContent* aKid,
                                     nsIContent* aNextSibling) {
  MOZ_ASSERT(aKid);
  MOZ_ASSERT(aNextSibling);

  RemoveFromCache(this);

  nsIContent* previousSibling = aNextSibling->mPreviousOrLastSibling;
  aNextSibling->mPreviousOrLastSibling = aKid;
  aKid->mPreviousOrLastSibling = previousSibling;
  aKid->mNextSibling = aNextSibling;

  if (aNextSibling == mFirstChild) {
    MOZ_ASSERT(!previousSibling->mNextSibling);
    mFirstChild = aKid;
  } else {
    previousSibling->mNextSibling = aKid;
  }

  ++mChildCount;
}

void nsINode::DisconnectChild(nsIContent* aKid) {
  MOZ_ASSERT(aKid);
  MOZ_ASSERT(GetChildCount() > 0);

  RemoveFromCache(this);

  nsIContent* previousSibling = aKid->GetPreviousSibling();
  nsCOMPtr<nsIContent> ref = aKid;

  if (aKid->mNextSibling) {
    aKid->mNextSibling->mPreviousOrLastSibling = aKid->mPreviousOrLastSibling;
  } else {
    // aKid is the last child in the list
    mFirstChild->mPreviousOrLastSibling = aKid->mPreviousOrLastSibling;
  }
  aKid->mPreviousOrLastSibling = nullptr;

  if (previousSibling) {
    previousSibling->mNextSibling = std::move(aKid->mNextSibling);
  } else {
    // aKid is the first child in the list
    mFirstChild = std::move(aKid->mNextSibling);
  }

  --mChildCount;
}

nsIContent* nsINode::GetChildAt_Deprecated(uint32_t aIndex) const {
  if (aIndex >= GetChildCount()) {
    return nullptr;
  }

  nsIContent* child = mFirstChild;
  while (aIndex--) {
    child = child->GetNextSibling();
  }

  return child;
}

int32_t nsINode::ComputeIndexOf_Deprecated(
    const nsINode* aPossibleChild) const {
  Maybe<uint32_t> maybeIndex = ComputeIndexOf(aPossibleChild);
  if (!maybeIndex) {
    return -1;
  }
  MOZ_ASSERT(*maybeIndex <= INT32_MAX,
             "ComputeIndexOf_Deprecated() returns unsupported index value, use "
             "ComputeIndex() instead");
  return static_cast<int32_t>(*maybeIndex);
}

Maybe<uint32_t> nsINode::ComputeIndexOf(const nsINode* aPossibleChild) const {
  if (!aPossibleChild) {
    return Nothing();
  }

  if (aPossibleChild->GetParentNode() != this) {
    return Nothing();
  }

  if (aPossibleChild == GetFirstChild()) {
    return Some(0);
  }

  if (aPossibleChild == GetLastChild()) {
    MOZ_ASSERT(GetChildCount());
    return Some(GetChildCount() - 1);
  }

  if (mChildCount >= CACHE_CHILD_LIMIT) {
    const nsINode* child;
    Maybe<uint32_t> maybeChildIndex;
    GetChildAndIndexFromCache(this, &child, &maybeChildIndex);
    if (child) {
      if (child == aPossibleChild) {
        return maybeChildIndex;
      }

      uint32_t nextIndex = *maybeChildIndex;
      uint32_t prevIndex = *maybeChildIndex;
      nsINode* prev = child->GetPreviousSibling();
      nsINode* next = child->GetNextSibling();
      do {
        if (next) {
          MOZ_ASSERT(nextIndex < UINT32_MAX);
          ++nextIndex;
          if (next == aPossibleChild) {
            AddChildAndIndexToCache(this, aPossibleChild, nextIndex);
            return Some(nextIndex);
          }
          next = next->GetNextSibling();
        }
        if (prev) {
          MOZ_ASSERT(prevIndex > 0);
          --prevIndex;
          if (prev == aPossibleChild) {
            AddChildAndIndexToCache(this, aPossibleChild, prevIndex);
            return Some(prevIndex);
          }
          prev = prev->GetPreviousSibling();
        }
      } while (prev || next);
    }
  }

  uint32_t index = 0u;
  nsINode* current = mFirstChild;
  while (current) {
    MOZ_ASSERT(current->GetParentNode() == this);
    if (current == aPossibleChild) {
      if (mChildCount >= CACHE_CHILD_LIMIT) {
        AddChildAndIndexToCache(this, current, index);
      }
      return Some(index);
    }
    current = current->GetNextSibling();
    MOZ_ASSERT(index < UINT32_MAX);
    ++index;
  }

  return Nothing();
}

Maybe<uint32_t> nsINode::ComputeIndexInParentNode() const {
  nsINode* parent = GetParentNode();
  if (MOZ_UNLIKELY(!parent)) {
    return Nothing();
  }
  return parent->ComputeIndexOf(this);
}

Maybe<uint32_t> nsINode::ComputeIndexInParentContent() const {
  nsIContent* parent = GetParent();
  if (MOZ_UNLIKELY(!parent)) {
    return Nothing();
  }
  return parent->ComputeIndexOf(this);
}

static Maybe<uint32_t> DoComputeFlatTreeIndexOf(FlattenedChildIterator& aIter,
                                                const nsINode* aPossibleChild) {
  if (aPossibleChild->GetFlattenedTreeParentNode() != aIter.Parent()) {
    return Nothing();
  }

  uint32_t index = 0u;
  for (nsIContent* child = aIter.GetNextChild(); child;
       child = aIter.GetNextChild()) {
    if (child == aPossibleChild) {
      return Some(index);
    }

    ++index;
  }

  return Nothing();
}

Maybe<uint32_t> nsINode::ComputeFlatTreeIndexOf(
    const nsINode* aPossibleChild) const {
  if (!aPossibleChild) {
    return Nothing();
  }

  if (!IsContent()) {
    return ComputeIndexOf(aPossibleChild);
  }

  FlattenedChildIterator iter(AsContent());
  if (!iter.ShadowDOMInvolved()) {
    auto index = ComputeIndexOf(aPossibleChild);
    MOZ_ASSERT(DoComputeFlatTreeIndexOf(iter, aPossibleChild) == index);
    return index;
  }

  return DoComputeFlatTreeIndexOf(iter, aPossibleChild);
}

static already_AddRefed<nsINode> GetNodeFromNodeOrString(
    const OwningNodeOrString& aNode, Document* aDocument) {
  if (aNode.IsNode()) {
    nsCOMPtr<nsINode> node = aNode.GetAsNode();
    return node.forget();
  }

  if (aNode.IsString()) {
    RefPtr<nsTextNode> textNode =
        aDocument->CreateTextNode(aNode.GetAsString());
    return textNode.forget();
  }

  MOZ_CRASH("Impossible type");
}

/**
 * Implement the algorithm specified at
 * https://dom.spec.whatwg.org/#converting-nodes-into-a-node for |prepend()|,
 * |append()|, |before()|, |after()|, and |replaceWith()| APIs.
 */
MOZ_CAN_RUN_SCRIPT static already_AddRefed<nsINode>
ConvertNodesOrStringsIntoNode(const Sequence<OwningNodeOrString>& aNodes,
                              Document* aDocument, ErrorResult& aRv) {
  if (aNodes.Length() == 1) {
    return GetNodeFromNodeOrString(aNodes[0], aDocument);
  }

  nsCOMPtr<nsINode> fragment = aDocument->CreateDocumentFragment();

  for (const auto& node : aNodes) {
    nsCOMPtr<nsINode> childNode = GetNodeFromNodeOrString(node, aDocument);
    fragment->AppendChild(*childNode, aRv);
    if (aRv.Failed()) {
      return nullptr;
    }
  }

  return fragment.forget();
}

static void InsertNodesIntoHashset(const Sequence<OwningNodeOrString>& aNodes,
                                   nsTHashSet<nsINode*>& aHashset) {
  for (const auto& node : aNodes) {
    if (node.IsNode()) {
      aHashset.Insert(node.GetAsNode());
    }
  }
}

static nsINode* FindViablePreviousSibling(
    const nsINode& aNode, const Sequence<OwningNodeOrString>& aNodes) {
  nsTHashSet<nsINode*> nodeSet(16);
  InsertNodesIntoHashset(aNodes, nodeSet);

  nsINode* viablePreviousSibling = nullptr;
  for (nsINode* sibling = aNode.GetPreviousSibling(); sibling;
       sibling = sibling->GetPreviousSibling()) {
    if (!nodeSet.Contains(sibling)) {
      viablePreviousSibling = sibling;
      break;
    }
  }

  return viablePreviousSibling;
}

static nsINode* FindViableNextSibling(
    const nsINode& aNode, const Sequence<OwningNodeOrString>& aNodes) {
  nsTHashSet<nsINode*> nodeSet(16);
  InsertNodesIntoHashset(aNodes, nodeSet);

  nsINode* viableNextSibling = nullptr;
  for (nsINode* sibling = aNode.GetNextSibling(); sibling;
       sibling = sibling->GetNextSibling()) {
    if (!nodeSet.Contains(sibling)) {
      viableNextSibling = sibling;
      break;
    }
  }

  return viableNextSibling;
}

void nsINode::Before(const Sequence<OwningNodeOrString>& aNodes,
                     ErrorResult& aRv) {
  nsCOMPtr<nsINode> parent = GetParentNode();
  if (!parent) {
    return;
  }

  nsCOMPtr<nsINode> viablePreviousSibling =
      FindViablePreviousSibling(*this, aNodes);

  nsCOMPtr<Document> doc = OwnerDoc();
--> --------------------

--> maximum size reached

--> --------------------