layout/base/ServoRestyleManager.cpp

/* -*- 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/. */

#include "mozilla/ServoRestyleManager.h"

#include "mozilla/AutoRestyleTimelineMarker.h"
#include "mozilla/AutoTimelineMarker.h"
#include "mozilla/DocumentStyleRootIterator.h"
#include "mozilla/ServoBindings.h"
#include "mozilla/ServoStyleSet.h"
#include "mozilla/ServoStyleContext.h"
#include "mozilla/ServoStyleContextInlines.h"
#include "mozilla/Unused.h"
#include "mozilla/ViewportFrame.h"
#include "mozilla/dom/ChildIterator.h"
#include "mozilla/dom/ElementInlines.h"
#include "nsBlockFrame.h"
#include "nsBulletFrame.h"
#include "nsIFrameInlines.h"
#include "nsImageFrame.h"
#include "nsPlaceholderFrame.h"
#include "nsContentUtils.h"
#include "nsCSSFrameConstructor.h"
#include "nsPrintfCString.h"
#include "nsRefreshDriver.h"
#include "nsStyleChangeList.h"

#ifdef ACCESSIBILITY
#include "nsAccessibilityService.h"
#endif

using namespace mozilla::dom;

namespace mozilla {

#ifdef DEBUG
static bool IsAnonBox(const nsIFrame& aFrame) {
  return aFrame.StyleContext()->IsAnonBox();
}

static const nsIFrame* FirstContinuationOrPartOfIBSplit(
    const nsIFrame* aFrame) {
  if (!aFrame) {
    return nullptr;
  }

  return nsLayoutUtils::FirstContinuationOrIBSplitSibling(aFrame);
}

static const nsIFrame* ExpectedOwnerForChild(const nsIFrame& aFrame) {
  const nsIFrame* parent = aFrame.GetParent();
  if (aFrame.IsTableFrame()) {
    MOZ_ASSERT(parent->IsTableWrapperFrame());
    parent = parent->GetParent();
  }

  if (IsAnonBox(aFrame) && !aFrame.IsTextFrame()) {
    if (parent->IsLineFrame()) {
      parent = parent->GetParent();
    }
    return parent->IsViewportFrame() ? nullptr
                                     : FirstContinuationOrPartOfIBSplit(parent);
  }

  if (aFrame.IsBulletFrame()) {
    return FirstContinuationOrPartOfIBSplit(parent);
  }

  if (aFrame.IsLineFrame()) {
    // A ::first-line always ends up here via its block, which is therefore the
    // right expected owner.  That block can be an
    // anonymous box.  For example, we could have a ::first-line on a columnated
    // block; the blockframe is the column-content anonymous box in that case.
    // So we don't want to end up in the code below, which steps out of anon
    // boxes.  Just return the parent of the line frame, which is the block.
    return parent;
  }

  if (aFrame.IsLetterFrame()) {
    // Ditto for ::first-letter. A first-letter always arrives here via its
    // direct parent, except when it's parented to a ::first-line.
    if (parent->IsLineFrame()) {
      parent = parent->GetParent();
    }
    return FirstContinuationOrPartOfIBSplit(parent);
  }

  if (parent->IsLetterFrame()) {
    // Things never have ::first-letter as their expected parent.  Go
    // on up to the ::first-letter's parent.
    parent = parent->GetParent();
  }

  parent = FirstContinuationOrPartOfIBSplit(parent);

  // We've handled already anon boxes and bullet frames, so now we're looking at
  // a frame of a DOM element or pseudo. Hop through anon and line-boxes
  // generated by our DOM parent, and go find the owner frame for it.
  while (parent && (IsAnonBox(*parent) || parent->IsLineFrame())) {
    auto* pseudo = parent->StyleContext()->GetPseudo();
    if (pseudo == nsCSSAnonBoxes::tableWrapper) {
      const nsIFrame* tableFrame = parent->PrincipalChildList().FirstChild();
      MOZ_ASSERT(tableFrame->IsTableFrame());
      // Handle :-moz-table and :-moz-inline-table.
      parent = IsAnonBox(*tableFrame) ? parent->GetParent() : tableFrame;
    } else {
      // We get the in-flow parent here so that we can handle the OOF anonymous
      // boxed to get the correct parent.
      parent = parent->GetInFlowParent();
    }
    parent = FirstContinuationOrPartOfIBSplit(parent);
  }

  return parent;
}

void ServoRestyleState::AssertOwner(const ServoRestyleState& aParent) const {
  MOZ_ASSERT(mOwner);
  MOZ_ASSERT(!mOwner->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW));
  // We allow aParent.mOwner to be null, for cases when we're not starting at
  // the root of the tree.  We also allow aParent.mOwner to be somewhere up our
  // expected owner chain not our immediate owner, which allows us creating long
  // chains of ServoRestyleStates in some cases where it's just not worth it.
#ifdef DEBUG
  if (aParent.mOwner) {
    const nsIFrame* owner = ExpectedOwnerForChild(*mOwner);
    if (owner != aParent.mOwner) {
      MOZ_ASSERT(IsAnonBox(*owner),
                 "Should only have expected owner weirdness when anon boxes "
                 "are involved");
      bool found = false;
      for (; owner; owner = ExpectedOwnerForChild(*owner)) {
        if (owner == aParent.mOwner) {
          found = true;
          break;
        }
      }
      MOZ_ASSERT(found, "Must have aParent.mOwner on our expected owner chain");
    }
  }
#endif
}

nsChangeHint ServoRestyleState::ChangesHandledFor(
    const nsIFrame& aFrame) const {
  if (!mOwner) {
    MOZ_ASSERT(!mChangesHandled);
    return mChangesHandled;
  }

  MOZ_ASSERT(mOwner == ExpectedOwnerForChild(aFrame),
             "Missed some frame in the hierarchy?");
  return mChangesHandled;
}
#endif

void ServoRestyleState::AddPendingWrapperRestyle(nsIFrame* aWrapperFrame) {
  MOZ_ASSERT(aWrapperFrame->StyleContext()->IsWrapperAnonBox(),
             "All our wrappers are anon boxes, and why would we restyle "
             "non-inheriting ones?");
  MOZ_ASSERT(aWrapperFrame->StyleContext()->IsInheritingAnonBox(),
             "All our wrappers are anon boxes, and why would we restyle "
             "non-inheriting ones?");
  MOZ_ASSERT(
      aWrapperFrame->StyleContext()->GetPseudo() != nsCSSAnonBoxes::cellContent,
      "Someone should be using TableAwareParentFor");
  MOZ_ASSERT(aWrapperFrame->StyleContext()->GetPseudo() !=
                 nsCSSAnonBoxes::tableWrapper,
             "Someone should be using TableAwareParentFor");
  // Make sure we only add first continuations.
  aWrapperFrame = aWrapperFrame->FirstContinuation();
  nsIFrame* last = mPendingWrapperRestyles.SafeLastElement(nullptr);
  if (last == aWrapperFrame) {
    // Already queued up, nothing to do.
    return;
  }

  // Make sure to queue up parents before children.  But don't queue up
  // ancestors of non-anonymous boxes here; those are handled when we traverse
  // their non-anonymous kids.
  if (aWrapperFrame->ParentIsWrapperAnonBox()) {
    AddPendingWrapperRestyle(TableAwareParentFor(aWrapperFrame));
  }

  // If the append fails, we'll fail to restyle properly, but that's probably
  // better than crashing.
  if (mPendingWrapperRestyles.AppendElement(aWrapperFrame, fallible)) {
    aWrapperFrame->SetIsWrapperAnonBoxNeedingRestyle(true);
  }
}

void ServoRestyleState::ProcessWrapperRestyles(nsIFrame* aParentFrame) {
  size_t i = mPendingWrapperRestyleOffset;
  while (i < mPendingWrapperRestyles.Length()) {
    i += ProcessMaybeNestedWrapperRestyle(aParentFrame, i);
  }

  mPendingWrapperRestyles.TruncateLength(mPendingWrapperRestyleOffset);
}

size_t ServoRestyleState::ProcessMaybeNestedWrapperRestyle(nsIFrame* aParent,
                                                           size_t aIndex) {
  // The frame at index aIndex is something we should restyle ourselves, but
  // following frames may need separate ServoRestyleStates to restyle.
  MOZ_ASSERT(aIndex < mPendingWrapperRestyles.Length());

  nsIFrame* cur = mPendingWrapperRestyles[aIndex];
  MOZ_ASSERT(cur->StyleContext()->IsWrapperAnonBox());

  // Where is cur supposed to inherit from?  From its parent frame, except in
  // the case when cur is a table, in which case it should be its grandparent.
  // Also, not in the case when the resulting frame would be a first-line; in
  // that case we should be inheriting from the block, and the first-line will
  // do its fixup later if needed.
  //
  // Note that after we do all that fixup the parent we get might still not be
  // aParent; for example aParent could be a scrollframe, in which case we
  // should inherit from the scrollcontent frame.  Or the parent might be some
  // continuation of aParent.
  //
  // Try to assert as much as we can about the parent we actually end up using
  // without triggering bogus asserts in all those various edge cases.
  nsIFrame* parent = cur->GetParent();
  if (cur->IsTableFrame()) {
    MOZ_ASSERT(parent->IsTableWrapperFrame());
    parent = parent->GetParent();
  }
  if (parent->IsLineFrame()) {
    parent = parent->GetParent();
  }
  MOZ_ASSERT(FirstContinuationOrPartOfIBSplit(parent) == aParent ||
             (parent->StyleContext()->IsInheritingAnonBox() &&
              parent->GetContent() == aParent->GetContent()));

  // Now "this" is a ServoRestyleState for aParent, so if parent is not a next
  // continuation (possibly across ib splits) of aParent we need a new
  // ServoRestyleState for the kid.
  Maybe<ServoRestyleState> parentRestyleState;
  nsIFrame* parentForRestyle =
      nsLayoutUtils::FirstContinuationOrIBSplitSibling(parent);
  if (parentForRestyle != aParent) {
    parentRestyleState.emplace(*parentForRestyle, *this, nsChangeHint_Empty,
                               Type::InFlow);
  }
  ServoRestyleState& curRestyleState =
      parentRestyleState ? *parentRestyleState : *this;

  // This frame may already have been restyled.  Even if it has, we can't just
  // return, because the next frame may be a kid of it that does need restyling.
  if (cur->IsWrapperAnonBoxNeedingRestyle()) {
    parentForRestyle->UpdateStyleOfChildAnonBox(cur, curRestyleState);
    cur->SetIsWrapperAnonBoxNeedingRestyle(false);
  }

  size_t numProcessed = 1;

  // Note: no overflow possible here, since aIndex < length.
  if (aIndex + 1 < mPendingWrapperRestyles.Length()) {
    nsIFrame* next = mPendingWrapperRestyles[aIndex + 1];
    if (TableAwareParentFor(next) == cur &&
        next->IsWrapperAnonBoxNeedingRestyle()) {
      // It might be nice if we could do better than nsChangeHint_Empty.  On
      // the other hand, presumably our mChangesHandled already has the bits
      // we really want here so in practice it doesn't matter.
      ServoRestyleState childState(*cur, curRestyleState, nsChangeHint_Empty,
                                   Type::InFlow,
                                   /* aAssertWrapperRestyleLength = */ false);
      numProcessed +=
          childState.ProcessMaybeNestedWrapperRestyle(cur, aIndex + 1);
    }
  }

  return numProcessed;
}

nsIFrame* ServoRestyleState::TableAwareParentFor(const nsIFrame* aChild) {
  // We want to get the anon box parent for aChild. where aChild has
  // ParentIsWrapperAnonBox().
  //
  // For the most part this is pretty straightforward, but there are two
  // wrinkles.  First, if aChild is a table, then we really want the parent of
  // its table wrapper.
  if (aChild->IsTableFrame()) {
    aChild = aChild->GetParent();
    MOZ_ASSERT(aChild->IsTableWrapperFrame());
  }

  nsIFrame* parent = aChild->GetParent();
  // Now if parent is a cell-content frame, we actually want the cellframe.
  if (parent->StyleContext()->GetPseudo() == nsCSSAnonBoxes::cellContent) {
    parent = parent->GetParent();
  } else if (parent->IsTableWrapperFrame()) {
    // Must be a caption.  In that case we want the table here.
    MOZ_ASSERT(aChild->StyleDisplay()->mDisplay == StyleDisplay::TableCaption);
    parent = parent->PrincipalChildList().FirstChild();
  }
  return parent;
}

ServoRestyleManager::ServoRestyleManager(nsPresContext* aPresContext)
    : RestyleManager(StyleBackendType::Servo, aPresContext),
      mReentrantChanges(nullptr) {}

void ServoRestyleManager::PostRestyleEvent(Element* aElement,
                                           nsRestyleHint aRestyleHint,
                                           nsChangeHint aMinChangeHint) {
  MOZ_ASSERT(!(aMinChangeHint & nsChangeHint_NeutralChange),
             "Didn't expect explicit change hints to be neutral!");
  if (MOZ_UNLIKELY(IsDisconnected()) ||
      MOZ_UNLIKELY(PresContext()->PresShell()->IsDestroying())) {
    return;
  }

  // We allow posting restyles from within change hint handling, but not from
  // within the restyle algorithm itself.
  MOZ_ASSERT(!ServoStyleSet::IsInServoTraversal());

  if (aRestyleHint == 0 && !aMinChangeHint) {
    return;  // Nothing to do.
  }

  // Assuming the restyle hints will invalidate cached style for
  // getComputedStyle, since we don't know if any of the restyling that we do
  // would affect undisplayed elements.
  if (aRestyleHint) {
    IncrementUndisplayedRestyleGeneration();
  }

  // Processing change hints sometimes causes new change hints to be generated,
  // and very occasionally, additional restyle hints. We collect the change
  // hints manually to avoid re-traversing the DOM to find them.
  if (mReentrantChanges && !aRestyleHint) {
    mReentrantChanges->AppendElement(ReentrantChange{aElement, aMinChangeHint});
    return;
  }

  if (aRestyleHint & ~eRestyle_AllHintsWithAnimations) {
    mHaveNonAnimationRestyles = true;
  }

  if (aRestyleHint & eRestyle_LaterSiblings) {
    aRestyleHint &= ~eRestyle_LaterSiblings;

    nsRestyleHint siblingHint = eRestyle_Subtree;
    Element* current = aElement->GetNextElementSibling();
    while (current) {
      Servo_NoteExplicitHints(current, siblingHint, nsChangeHint(0));
      current = current->GetNextElementSibling();
    }
  }

  if (aRestyleHint || aMinChangeHint) {
    Servo_NoteExplicitHints(aElement, aRestyleHint, aMinChangeHint);
  }
}

void ServoRestyleManager::PostRestyleEventForCSSRuleChanges() {
  mRestyleForCSSRuleChanges = true;
  mPresContext->PresShell()->EnsureStyleFlush();
}

void ServoRestyleManager::PostRestyleEventForAnimations(
    Element* aElement, CSSPseudoElementType aPseudoType,
    nsRestyleHint aRestyleHint) {
  Element* elementToRestyle =
      EffectCompositor::GetElementToRestyle(aElement, aPseudoType);

  if (!elementToRestyle) {
    // FIXME: Bug 1371107: When reframing happens,
    // EffectCompositor::mElementsToRestyle still has unbinded old pseudo
    // element. We should drop it.
    return;
  }

  AutoRestyleTimelineMarker marker(mPresContext->GetDocShell(),
                                   true /* animation-only */);
  Servo_NoteExplicitHints(elementToRestyle, aRestyleHint, nsChangeHint(0));
}

void ServoRestyleManager::RebuildAllStyleData(nsChangeHint aExtraHint,
                                              nsRestyleHint aRestyleHint) {
  // NOTE(emilio): GeckoRestlyeManager does a sync style flush, which seems not
  // to be needed in my testing.
  PostRebuildAllStyleDataEvent(aExtraHint, aRestyleHint);
}

void ServoRestyleManager::PostRebuildAllStyleDataEvent(
    nsChangeHint aExtraHint, nsRestyleHint aRestyleHint) {
  // NOTE(emilio): The semantics of these methods are quite funny, in the sense
  // that we're not supposed to need to rebuild the actual stylist data.
  //
  // That's handled as part of the MediumFeaturesChanged stuff, if needed.
  StyleSet()->ClearCachedStyleData();

  DocumentStyleRootIterator iter(mPresContext->Document());
  while (Element* root = iter.GetNextStyleRoot()) {
    PostRestyleEvent(root, aRestyleHint, aExtraHint);
  }

  // TODO(emilio, bz): Extensions can add/remove stylesheets that can affect
  // non-inheriting anon boxes. It's not clear if we want to support that, but
  // if we do, we need to re-selector-match them here.
}

/* static */ void ServoRestyleManager::ClearServoDataFromSubtree(
    Element* aElement, IncludeRoot aIncludeRoot) {
  if (aElement->HasServoData()) {
    StyleChildrenIterator it(aElement);
    for (nsIContent* n = it.GetNextChild(); n; n = it.GetNextChild()) {
      if (n->IsElement()) {
        ClearServoDataFromSubtree(n->AsElement(), IncludeRoot::Yes);
      }
    }
  }

  if (MOZ_LIKELY(aIncludeRoot == IncludeRoot::Yes)) {
    aElement->ClearServoData();
    MOZ_ASSERT(!aElement->HasAnyOfFlags(Element::kAllServoDescendantBits |
                                        NODE_NEEDS_FRAME));
    MOZ_ASSERT(aElement != aElement->OwnerDoc()->GetServoRestyleRoot());
  }
}

/* static */ void ServoRestyleManager::ClearRestyleStateFromSubtree(
    Element* aElement) {
  if (aElement->HasAnyOfFlags(Element::kAllServoDescendantBits)) {
    StyleChildrenIterator it(aElement);
    for (nsIContent* n = it.GetNextChild(); n; n = it.GetNextChild()) {
      if (n->IsElement()) {
        ClearRestyleStateFromSubtree(n->AsElement());
      }
    }
  }

  bool wasRestyled;
  Unused << Servo_TakeChangeHint(aElement, &wasRestyled);
  aElement->UnsetFlags(Element::kAllServoDescendantBits);
}

/**
 * This struct takes care of encapsulating some common state that text nodes may
 * need to track during the post-traversal.
 *
 * This is currently used to properly compute change hints when the parent
 * element of this node is a display: contents node, and also to avoid computing
 * the style for text children more than once per element.
 */
struct ServoRestyleManager::TextPostTraversalState {
 public:
  TextPostTraversalState(Element& aParentElement,
                         ServoStyleContext* aParentContext,
                         bool aDisplayContentsParentStyleChanged,
                         ServoRestyleState& aParentRestyleState)
      : mParentElement(aParentElement),
        mParentContext(aParentContext),
        mParentRestyleState(aParentRestyleState),
        mStyle(nullptr),
        mShouldPostHints(aDisplayContentsParentStyleChanged),
        mShouldComputeHints(aDisplayContentsParentStyleChanged),
        mComputedHint(nsChangeHint_Empty) {}

  nsStyleChangeList& ChangeList() { return mParentRestyleState.ChangeList(); }

  nsStyleContext& ComputeStyle(nsIContent* aTextNode) {
    if (!mStyle) {
      mStyle = mParentRestyleState.StyleSet().ResolveStyleForText(
          aTextNode, &ParentStyle());
    }
    MOZ_ASSERT(mStyle);
    return *mStyle;
  }

  void ComputeHintIfNeeded(nsIContent* aContent, nsIFrame* aTextFrame,
                           nsStyleContext& aNewContext) {
    MOZ_ASSERT(aTextFrame);
    MOZ_ASSERT(aNewContext.GetPseudo() == nsCSSAnonBoxes::mozText);

    if (MOZ_LIKELY(!mShouldPostHints)) {
      return;
    }

    ServoStyleContext* oldContext = aTextFrame->StyleContext()->AsServo();
    MOZ_ASSERT(oldContext->GetPseudo() == nsCSSAnonBoxes::mozText);

    // We rely on the fact that all the text children for the same element share
    // style to avoid recomputing style differences for all of them.
    //
    // TODO(emilio): The above may not be true for ::first-{line,letter}, but
    // we'll cross that bridge when we support those in stylo.
    if (mShouldComputeHints) {
      mShouldComputeHints = false;
      uint32_t equalStructs, samePointerStructs;
      mComputedHint = oldContext->CalcStyleDifference(
          &aNewContext, &equalStructs, &samePointerStructs);
      mComputedHint = NS_RemoveSubsumedHints(
          mComputedHint, mParentRestyleState.ChangesHandledFor(*aTextFrame));
    }

    if (mComputedHint) {
      mParentRestyleState.ChangeList().AppendChange(aTextFrame, aContent,
                                                    mComputedHint);
    }
  }

 private:
  ServoStyleContext& ParentStyle() {
    if (!mParentContext) {
      mLazilyResolvedParentContext =
          mParentRestyleState.StyleSet().ResolveServoStyle(&mParentElement);
      mParentContext = mLazilyResolvedParentContext;
    }
    return *mParentContext;
  }

  Element& mParentElement;
  ServoStyleContext* mParentContext;
  RefPtr<ServoStyleContext> mLazilyResolvedParentContext;
  ServoRestyleState& mParentRestyleState;
  RefPtr<nsStyleContext> mStyle;
  bool mShouldPostHints;
  bool mShouldComputeHints;
  nsChangeHint mComputedHint;
};

static void UpdateBackdropIfNeeded(nsIFrame* aFrame, ServoStyleSet& aStyleSet,
                                   nsStyleChangeList& aChangeList) {
  const nsStyleDisplay* display = aFrame->StyleContext()->StyleDisplay();
  if (display->mTopLayer != NS_STYLE_TOP_LAYER_TOP) {
    return;
  }

  // Elements in the top layer are guaranteed to have absolute or fixed
  // position per https://fullscreen.spec.whatwg.org/#new-stacking-layer.
  MOZ_ASSERT(display->IsAbsolutelyPositionedStyle());

  nsIFrame* backdropPlaceholder =
      aFrame->GetChildList(nsIFrame::kBackdropList).FirstChild();
  if (!backdropPlaceholder) {
    return;
  }

  MOZ_ASSERT(backdropPlaceholder->IsPlaceholderFrame());
  nsIFrame* backdropFrame =
      nsPlaceholderFrame::GetRealFrameForPlaceholder(backdropPlaceholder);
  MOZ_ASSERT(backdropFrame->IsBackdropFrame());
  MOZ_ASSERT(backdropFrame->StyleContext()->GetPseudoType() ==
             CSSPseudoElementType::backdrop);

  RefPtr<nsStyleContext> newContext = aStyleSet.ResolvePseudoElementStyle(
      aFrame->GetContent()->AsElement(), CSSPseudoElementType::backdrop,
      aFrame->StyleContext()->AsServo(),
      /* aPseudoElement = */ nullptr);

  // NOTE(emilio): We can't use the changes handled for the owner of the
  // backdrop frame, since it's out of flow, and parented to the viewport or
  // canvas frame (depending on the `position` value).
  MOZ_ASSERT(backdropFrame->GetParent()->IsViewportFrame() ||
             backdropFrame->GetParent()->IsCanvasFrame());
  nsTArray<nsIFrame*> wrappersToRestyle;
  ServoRestyleState state(aStyleSet, aChangeList, wrappersToRestyle);
  aFrame->UpdateStyleOfOwnedChildFrame(backdropFrame, newContext, state);
}

static void UpdateFirstLetterIfNeeded(nsIFrame* aFrame,
                                      ServoRestyleState& aRestyleState) {
  MOZ_ASSERT(
      !aFrame->IsFrameOfType(nsIFrame::eBlockFrame),
      "You're probably duplicating work with UpdatePseudoElementStyles!");
  if (!aFrame->HasFirstLetterChild()) {
    return;
  }

  // We need to find the block the first-letter is associated with so we can
  // find the right element for the first-letter's style resolution.  Might as
  // well just delegate the whole thing to that block.
  nsIFrame* block = aFrame->GetParent();
  while (!block->IsFrameOfType(nsIFrame::eBlockFrame)) {
    block = block->GetParent();
  }

  static_cast<nsBlockFrame*>(block->FirstContinuation())
      ->UpdateFirstLetterStyle(aRestyleState);
}

static void UpdateOneAdditionalStyleContext(nsIFrame* aFrame, uint32_t aIndex,
                                            ServoStyleContext& aOldContext,
                                            ServoRestyleState& aRestyleState) {
  auto pseudoType = aOldContext.GetPseudoType();
  MOZ_ASSERT(pseudoType != CSSPseudoElementType::NotPseudo);
  MOZ_ASSERT(
      !nsCSSPseudoElements::PseudoElementSupportsUserActionState(pseudoType));

  RefPtr<ServoStyleContext> newContext =
      aRestyleState.StyleSet().ResolvePseudoElementStyle(
          aFrame->GetContent()->AsElement(), pseudoType,
          aFrame->StyleContext()->AsServo(),
          /* aPseudoElement = */ nullptr);

  uint32_t equalStructs, samePointerStructs;  // Not used, actually.
  nsChangeHint childHint = aOldContext.CalcStyleDifference(
      newContext, &equalStructs, &samePointerStructs);
  if (!aFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW)) {
    childHint = NS_RemoveSubsumedHints(
        childHint, aRestyleState.ChangesHandledFor(*aFrame));
  }

  if (childHint) {
    if (childHint & nsChangeHint_ReconstructFrame) {
      // If we generate a reconstruct here, remove any non-reconstruct hints we
      // may have already generated for this content.
      aRestyleState.ChangeList().PopChangesForContent(aFrame->GetContent());
    }
    aRestyleState.ChangeList().AppendChange(aFrame, aFrame->GetContent(),
                                            childHint);
  }

  aFrame->SetAdditionalStyleContext(aIndex, newContext);
}

static void UpdateAdditionalStyleContexts(nsIFrame* aFrame,
                                          ServoRestyleState& aRestyleState) {
  MOZ_ASSERT(aFrame);
  MOZ_ASSERT(aFrame->GetContent() && aFrame->GetContent()->IsElement());

  // FIXME(emilio): Consider adding a bit or something to avoid the initial
  // virtual call?
  uint32_t index = 0;
  while (auto* oldContext = aFrame->GetAdditionalStyleContext(index)) {
    UpdateOneAdditionalStyleContext(aFrame, index++, *oldContext->AsServo(),
                                    aRestyleState);
  }
}

static void UpdateFramePseudoElementStyles(nsIFrame* aFrame,
                                           ServoRestyleState& aRestyleState) {
  if (aFrame->IsFrameOfType(nsIFrame::eBlockFrame)) {
    static_cast<nsBlockFrame*>(aFrame)->UpdatePseudoElementStyles(
        aRestyleState);
  } else {
    UpdateFirstLetterIfNeeded(aFrame, aRestyleState);
  }

  UpdateBackdropIfNeeded(aFrame, aRestyleState.StyleSet(),
                         aRestyleState.ChangeList());
}

enum class ServoPostTraversalFlags : uint32_t {
  Empty = 0,
  // Whether parent was restyled.
  ParentWasRestyled = 1 << 0,
  // Skip sending accessibility notifications for all descendants.
  SkipA11yNotifications = 1 << 1,
  // Always send accessibility notifications if the element is shown.
  // The SkipA11yNotifications flag above overrides this flag.
  SendA11yNotificationsIfShown = 1 << 2,
};

MOZ_MAKE_ENUM_CLASS_BITWISE_OPERATORS(ServoPostTraversalFlags)

// Send proper accessibility notifications and return post traversal
// flags for kids.
static ServoPostTraversalFlags SendA11yNotifications(
    nsPresContext* aPresContext, Element* aElement,
    nsStyleContext* aOldStyleContext, nsStyleContext* aNewStyleContext,
    ServoPostTraversalFlags aFlags) {
  using Flags = ServoPostTraversalFlags;
  MOZ_ASSERT(!(aFlags & Flags::SkipA11yNotifications) ||
                 !(aFlags & Flags::SendA11yNotificationsIfShown),
             "The two a11y flags should never be set together");

#ifdef ACCESSIBILITY
  nsAccessibilityService* accService = GetAccService();
  if (!accService) {
    // If we don't have accessibility service, accessibility is not
    // enabled. Just skip everything.
    return Flags::Empty;
  }
  if (aFlags & Flags::SkipA11yNotifications) {
    // Propogate the skipping flag to descendants.
    return Flags::SkipA11yNotifications;
  }

  bool needsNotify = false;
  bool isVisible = aNewStyleContext->StyleVisibility()->IsVisible();
  if (aFlags & Flags::SendA11yNotificationsIfShown) {
    if (!isVisible) {
      // Propagate the sending-if-shown flag to descendants.
      return Flags::SendA11yNotificationsIfShown;
    }
    // We have asked accessibility service to remove the whole subtree
    // of element which becomes invisible from the accessible tree, but
    // this element is visible, so we need to add it back.
    needsNotify = true;
  } else {
    // If we shouldn't skip in any case, we need to check whether our
    // own visibility has changed.
    bool wasVisible = aOldStyleContext->StyleVisibility()->IsVisible();
    needsNotify = wasVisible != isVisible;
  }

  if (needsNotify) {
    nsIPresShell* presShell = aPresContext->PresShell();
    if (isVisible) {
      accService->ContentRangeInserted(presShell, aElement->GetParent(),
                                       aElement, aElement->GetNextSibling());
      // We are adding the subtree. Accessibility service would handle
      // descendants, so we should just skip them from notifying.
      return Flags::SkipA11yNotifications;
    }
    // Remove the subtree of this invisible element, and ask any shown
    // descendant to add themselves back.
    accService->ContentRemoved(presShell, aElement);
    return Flags::SendA11yNotificationsIfShown;
  }
#endif

  return Flags::Empty;
}

bool ServoRestyleManager::ProcessPostTraversal(
    Element* aElement, ServoStyleContext* aParentContext,
    ServoRestyleState& aRestyleState, ServoPostTraversalFlags aFlags) {
  nsIFrame* styleFrame = nsLayoutUtils::GetStyleFrame(aElement);
  nsIFrame* primaryFrame = aElement->GetPrimaryFrame();

  // NOTE(emilio): This is needed because for table frames the bit is set on the
  // table wrapper (which is the primary frame), not on the table itself.
  const bool isOutOfFlow =
      primaryFrame && primaryFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW);

  // Grab the change hint from Servo.
  bool wasRestyled;
  nsChangeHint changeHint =
      static_cast<nsChangeHint>(Servo_TakeChangeHint(aElement, &wasRestyled));

  // We should really fix the weird primary frame mapping for image maps
  // (bug 135040)...
  if (styleFrame && styleFrame->GetContent() != aElement) {
    MOZ_ASSERT(static_cast<nsImageFrame*>(do_QueryFrame(styleFrame)));
    styleFrame = nullptr;
  }

  // Handle lazy frame construction by posting a reconstruct for any lazily-
  // constructed roots.
  if (aElement->HasFlag(NODE_NEEDS_FRAME)) {
    changeHint |= nsChangeHint_ReconstructFrame;
    MOZ_ASSERT(!styleFrame);
  }

  if (styleFrame) {
    MOZ_ASSERT(primaryFrame);

    nsIFrame* maybeAnonBoxChild;
    if (isOutOfFlow) {
      maybeAnonBoxChild = primaryFrame->GetPlaceholderFrame();
    } else {
      maybeAnonBoxChild = primaryFrame;
      changeHint = NS_RemoveSubsumedHints(
          changeHint, aRestyleState.ChangesHandledFor(*styleFrame));
    }

    // If the parent wasn't restyled, the styles of our anon box parents won't
    // change either.
    if ((aFlags & ServoPostTraversalFlags::ParentWasRestyled) &&
        maybeAnonBoxChild->ParentIsWrapperAnonBox()) {
      aRestyleState.AddPendingWrapperRestyle(
          ServoRestyleState::TableAwareParentFor(maybeAnonBoxChild));
    }
  }

  // Although we shouldn't generate non-ReconstructFrame hints for elements with
  // no frames, we can still get them here if they were explicitly posted by
  // PostRestyleEvent, such as a RepaintFrame hint when a :link changes to be
  // :visited.  Skip processing these hints if there is no frame.
  if ((styleFrame || (changeHint & nsChangeHint_ReconstructFrame)) &&
      changeHint) {
    aRestyleState.ChangeList().AppendChange(styleFrame, aElement, changeHint);
  }

  // If our change hint is reconstruct, we delegate to the frame constructor,
  // which consumes the new style and expects the old style to be on the frame.
  //
  // XXXbholley: We should teach the frame constructor how to clear the dirty
  // descendants bit to avoid the traversal here.
  if (changeHint & nsChangeHint_ReconstructFrame) {
    ClearRestyleStateFromSubtree(aElement);
    return true;
  }

  // TODO(emilio): We could avoid some refcount traffic here, specially in the
  // ServoStyleContext case, which uses atomic refcounting.
  //
  // Hold the old style context alive, because it could become a dangling
  // pointer during the replacement. In practice it's not a huge deal, but
  // better not playing with dangling pointers if not needed.
  RefPtr<ServoStyleContext> oldStyleContext =
      styleFrame ? styleFrame->StyleContext()->AsServo() : nullptr;

  nsStyleContext* displayContentsStyle = nullptr;
  // FIXME(emilio, bug 1303605): This can be simpler for Servo.
  // Note that we intentionally don't check for display: none content.
  if (!oldStyleContext) {
    displayContentsStyle =
        PresContext()->FrameConstructor()->GetDisplayContentsStyleFor(aElement);
    if (displayContentsStyle) {
      oldStyleContext = displayContentsStyle->AsServo();
    }
  }

  Maybe<ServoRestyleState> thisFrameRestyleState;
  if (styleFrame) {
    auto type = isOutOfFlow ? ServoRestyleState::Type::OutOfFlow
                            : ServoRestyleState::Type::InFlow;

    thisFrameRestyleState.emplace(*styleFrame, aRestyleState, changeHint, type);
  }

  // We can't really assume as used changes from display: contents elements (or
  // other elements without frames).
  ServoRestyleState& childrenRestyleState =
      thisFrameRestyleState ? *thisFrameRestyleState : aRestyleState;

  RefPtr<ServoStyleContext> upToDateContext =
      wasRestyled ? aRestyleState.StyleSet().ResolveServoStyle(aElement)
                  : oldStyleContext;

  ServoPostTraversalFlags childrenFlags =
      wasRestyled ? ServoPostTraversalFlags::ParentWasRestyled
                  : ServoPostTraversalFlags::Empty;

  if (wasRestyled && oldStyleContext) {
    MOZ_ASSERT(styleFrame || displayContentsStyle);
    MOZ_ASSERT(oldStyleContext->ComputedData() !=
               upToDateContext->ComputedData());

    upToDateContext->ResolveSameStructsAs(oldStyleContext);

    // We want to walk all the continuations here, even the ones with different
    // styles.  In practice, the only reason we get continuations with different
    // styles here is ::first-line (::first-letter never affects element
    // styles).  But in that case, newContext is the right context for the
    // _later_ continuations anyway (the ones not affected by ::first-line), not
    // the earlier ones, so there is no point stopping right at the point when
    // we'd actually be setting the right style context.
    //
    // This does mean that we may be setting the wrong style context on our
    // initial continuations; ::first-line fixes that up after the fact.
    for (nsIFrame* f = styleFrame; f; f = f->GetNextContinuation()) {
      MOZ_ASSERT_IF(f != styleFrame, !f->GetAdditionalStyleContext(0));
      f->SetStyleContext(upToDateContext);
    }

    if (MOZ_UNLIKELY(displayContentsStyle)) {
      MOZ_ASSERT(!styleFrame);
      PresContext()
          ->FrameConstructor()
          ->ChangeRegisteredDisplayContentsStyleFor(aElement, upToDateContext);
    }

    if (styleFrame) {
      UpdateAdditionalStyleContexts(styleFrame, aRestyleState);
    }

    if (!aElement->GetParent()) {
      // This is the root.  Update styles on the viewport as needed.
      ViewportFrame* viewport =
          do_QueryFrame(mPresContext->PresShell()->GetRootFrame());
      if (viewport) {
        // NB: The root restyle state, not the one for our children!
        viewport->UpdateStyle(aRestyleState);
      }
    }

    // Some changes to animations don't affect the computed style and yet still
    // require the layer to be updated. For example, pausing an animation via
    // the Web Animations API won't affect an element's style but still
    // requires to update the animation on the layer.
    //
    // We can sometimes reach this when the animated style is being removed.
    // Since AddLayerChangesForAnimation checks if |styleFrame| has a transform
    // style or not, we need to call it *after* setting |newContext| to
    // |styleFrame| to ensure the animated transform has been removed first.
    AddLayerChangesForAnimation(styleFrame, aElement,
                                aRestyleState.ChangeList());

    childrenFlags |= SendA11yNotifications(
        mPresContext, aElement, oldStyleContext, upToDateContext, aFlags);
  }

  const bool traverseElementChildren =
      aElement->HasAnyOfFlags(Element::kAllServoDescendantBits);
  const bool traverseTextChildren =
      wasRestyled || aElement->HasFlag(NODE_DESCENDANTS_NEED_FRAMES);
  bool recreatedAnyContext = wasRestyled;
  if (traverseElementChildren || traverseTextChildren) {
    StyleChildrenIterator it(aElement);
    TextPostTraversalState textState(*aElement, upToDateContext,
                                     displayContentsStyle && wasRestyled,
                                     childrenRestyleState);
    for (nsIContent* n = it.GetNextChild(); n; n = it.GetNextChild()) {
      if (traverseElementChildren && n->IsElement()) {
        recreatedAnyContext |=
            ProcessPostTraversal(n->AsElement(), upToDateContext,
                                 childrenRestyleState, childrenFlags);
      } else if (traverseTextChildren && n->IsNodeOfType(nsINode::eTEXT)) {
        recreatedAnyContext |= ProcessPostTraversalForText(
            n, textState, childrenRestyleState, childrenFlags);
      }
    }
  }

  // We want to update frame pseudo-element styles after we've traversed our
  // kids, because some of those updates (::first-line/::first-letter) need to
  // modify the styles of the kids, and the child traversal above would just
  // clobber those modifications.
  if (styleFrame) {
    if (wasRestyled) {
      // Make sure to update anon boxes and pseudo bits after updating text,
      // otherwise ProcessPostTraversalForText could clobber first-letter
      // styles, for example.
      styleFrame->UpdateStyleOfOwnedAnonBoxes(childrenRestyleState);
    }
    // Process anon box wrapper frames before ::first-line bits, but _after_
    // owned anon boxes, since the children wrapper anon boxes could be
    // inheriting from our own owned anon boxes.
    childrenRestyleState.ProcessWrapperRestyles(styleFrame);
    if (wasRestyled) {
      UpdateFramePseudoElementStyles(styleFrame, childrenRestyleState);
    } else if (traverseElementChildren &&
               styleFrame->IsFrameOfType(nsIFrame::eBlockFrame)) {
      // Even if we were not restyled, if we're a block with a first-line and
      // one of our descendant elements which is on the first line was restyled,
      // we need to update the styles of things on the first line, because
      // they're wrong now.
      //
      // FIXME(bz) Could we do better here?  For example, could we keep track of
      // frames that are "block with a ::first-line so we could avoid
      // IsFrameOfType() and digging about for the first-line frame if not?
      // Could we keep track of whether the element children we actually restyle
      // are affected by first-line?  Something else?  Bug 1385443 tracks making
      // this better.
      nsIFrame* firstLineFrame =
          static_cast<nsBlockFrame*>(styleFrame)->GetFirstLineFrame();
      if (firstLineFrame) {
        for (nsIFrame* kid : firstLineFrame->PrincipalChildList()) {
          ReparentStyleContext(kid);
        }
      }
    }
  }

  aElement->UnsetFlags(Element::kAllServoDescendantBits);
  return recreatedAnyContext;
}

bool ServoRestyleManager::ProcessPostTraversalForText(
    nsIContent* aTextNode, TextPostTraversalState& aPostTraversalState,
    ServoRestyleState& aRestyleState, ServoPostTraversalFlags aFlags) {
  // Handle lazy frame construction.
  if (aTextNode->HasFlag(NODE_NEEDS_FRAME)) {
    aPostTraversalState.ChangeList().AppendChange(
        nullptr, aTextNode, nsChangeHint_ReconstructFrame);
    return true;
  }

  // Handle restyle.
  nsIFrame* primaryFrame = aTextNode->GetPrimaryFrame();
  if (!primaryFrame) {
    return false;
  }

  // If the parent wasn't restyled, the styles of our anon box parents won't
  // change either.
  if ((aFlags & ServoPostTraversalFlags::ParentWasRestyled) &&
      primaryFrame->ParentIsWrapperAnonBox()) {
    aRestyleState.AddPendingWrapperRestyle(
        ServoRestyleState::TableAwareParentFor(primaryFrame));
  }

  nsStyleContext& newContext = aPostTraversalState.ComputeStyle(aTextNode);
  aPostTraversalState.ComputeHintIfNeeded(aTextNode, primaryFrame, newContext);

  // We want to walk all the continuations here, even the ones with different
  // styles.  In practice, the only reasons we get continuations with different
  // styles are ::first-line and ::first-letter.  But in those cases,
  // newContext is the right context for the _later_ continuations anyway (the
  // ones not affected by ::first-line/::first-letter), not the earlier ones,
  // so there is no point stopping right at the point when we'd actually be
  // setting the right style context.
  //
  // This does mean that we may be setting the wrong style context on our
  // initial continuations; ::first-line/::first-letter fix that up after the
  // fact.
  for (nsIFrame* f = primaryFrame; f; f = f->GetNextContinuation()) {
    f->SetStyleContext(&newContext);
  }

  return true;
}

void ServoRestyleManager::ClearSnapshots() {
  for (auto iter = mSnapshots.Iter(); !iter.Done(); iter.Next()) {
    iter.Key()->UnsetFlags(ELEMENT_HAS_SNAPSHOT | ELEMENT_HANDLED_SNAPSHOT);
    iter.Remove();
  }
}

ServoElementSnapshot& ServoRestyleManager::SnapshotFor(Element* aElement) {
  MOZ_ASSERT(!mInStyleRefresh);

  // NOTE(emilio): We can handle snapshots from a one-off restyle of those that
  // we do to restyle stuff for reconstruction, for example.
  //
  // It seems to be the case that we always flush in between that happens and
  // the next attribute change, so we can assert that we haven't handled the
  // snapshot here yet. If this assertion didn't hold, we'd need to unset that
  // flag from here too.
  //
  // Can't wait to make ProcessPendingRestyles the only entry-point for styling,
  // so this becomes much easier to reason about. Today is not that day though.
  MOZ_ASSERT(aElement->HasServoData());
  MOZ_ASSERT(!aElement->HasFlag(ELEMENT_HANDLED_SNAPSHOT));

  ServoElementSnapshot* snapshot = mSnapshots.LookupOrAdd(aElement, aElement);
  aElement->SetFlags(ELEMENT_HAS_SNAPSHOT);

  // Now that we have a snapshot, make sure a restyle is triggered.
  aElement->NoteDirtyForServo();
  return *snapshot;
}

void ServoRestyleManager::DoProcessPendingRestyles(ServoTraversalFlags aFlags) {
  nsPresContext* presContext = PresContext();

  MOZ_ASSERT(presContext->Document(), "No document?  Pshaw!");
  // FIXME(emilio): In the "flush animations" case, ideally, we should only
  // recascade animation styles running on the compositor, so we shouldn't care
  // about other styles, or new rules that apply to the page...
  //
  // However, that's not true as of right now, see bug 1388031 and bug 1388692.
  MOZ_ASSERT((aFlags & ServoTraversalFlags::FlushThrottledAnimations) ||
                 !presContext->HasPendingMediaQueryUpdates(),
             "Someone forgot to update media queries?");
  MOZ_ASSERT(!nsContentUtils::IsSafeToRunScript(), "Missing a script blocker!");
  MOZ_ASSERT(!mInStyleRefresh, "Reentrant call?");

  if (MOZ_UNLIKELY(!presContext->PresShell()->DidInitialize())) {
    // PresShell::FlushPendingNotifications doesn't early-return in the case
    // where the PresShell hasn't yet been initialized (and therefore we haven't
    // yet done the initial style traversal of the DOM tree). We should arguably
    // fix up the callers and assert against this case, but we just detect and
    // handle it for now.
    return;
  }

  // Create a AnimationsWithDestroyedFrame during restyling process to
  // stop animations and transitions on elements that have no frame at the end
  // of the restyling process.
  AnimationsWithDestroyedFrame animationsWithDestroyedFrame(this);

  ServoStyleSet* styleSet = StyleSet();
  nsIDocument* doc = presContext->Document();

  // Ensure the refresh driver is active during traversal to avoid mutating
  // mActiveTimer and mMostRecentRefresh time.
  presContext->RefreshDriver()->MostRecentRefresh();

  // Perform the Servo traversal, and the post-traversal if required. We do this
  // in a loop because certain rare paths in the frame constructor (like
  // uninstalling XBL bindings) can trigger additional style validations.
  mInStyleRefresh = true;
  if (mHaveNonAnimationRestyles) {
    ++mAnimationGeneration;
  }

  if (mRestyleForCSSRuleChanges) {
    aFlags |= ServoTraversalFlags::ForCSSRuleChanges;
  }

  while (styleSet->StyleDocument(aFlags)) {
    ClearSnapshots();

    nsStyleChangeList currentChanges(StyleBackendType::Servo);
    bool anyStyleChanged = false;

    // Recreate style contexts, and queue up change hints (which also handle
    // lazy frame construction).
    {
      AutoRestyleTimelineMarker marker(presContext->GetDocShell(), false);
      DocumentStyleRootIterator iter(doc->GetServoRestyleRoot());
      while (Element* root = iter.GetNextStyleRoot()) {
        nsTArray<nsIFrame*> wrappersToRestyle;
        ServoRestyleState state(*styleSet, currentChanges, wrappersToRestyle);
        ServoPostTraversalFlags flags = ServoPostTraversalFlags::Empty;
        anyStyleChanged |= ProcessPostTraversal(root, nullptr, state, flags);
      }
    }

    doc->ClearServoRestyleRoot();

    // Process the change hints.
    //
    // Unfortunately, the frame constructor can generate new change hints while
    // processing existing ones. We redirect those into a secondary queue and
    // iterate until there's nothing left.
    {
      AutoTimelineMarker marker(presContext->GetDocShell(),
                                "StylesApplyChanges");
      ReentrantChangeList newChanges;
      mReentrantChanges = &newChanges;
      while (!currentChanges.IsEmpty()) {
        ProcessRestyledFrames(currentChanges);
        MOZ_ASSERT(currentChanges.IsEmpty());
        for (ReentrantChange& change : newChanges) {
          if (!(change.mHint & nsChangeHint_ReconstructFrame) &&
              !change.mContent->GetPrimaryFrame()) {
            // SVG Elements post change hints without ensuring that the primary
            // frame will be there after that (see bug 1366142).
            //
            // Just ignore those, since we can't really process them.
            continue;
          }
          currentChanges.AppendChange(change.mContent->GetPrimaryFrame(),
                                      change.mContent, change.mHint);
        }
        newChanges.Clear();
      }
      mReentrantChanges = nullptr;
    }

    if (anyStyleChanged) {
      // Maybe no styles changed when:
      //
      //  * Only explicit change hints were posted in the first place.
      //  * When an attribute or state change in the content happens not to need
      //    a restyle after all.
      //
      // In any case, we don't need to increment the restyle generation in that
      // case.
      IncrementRestyleGeneration();
    }
  }

  doc->ClearServoRestyleRoot();

  FlushOverflowChangedTracker();

  ClearSnapshots();
  styleSet->AssertTreeIsClean();
  mHaveNonAnimationRestyles = false;
  mRestyleForCSSRuleChanges = false;
  mInStyleRefresh = false;

  // Now that everything has settled, see if we have enough free rule nodes in
  // the tree to warrant sweeping them.
  styleSet->MaybeGCRuleTree();

  // Note: We are in the scope of |animationsWithDestroyedFrame|, so
  //       |mAnimationsWithDestroyedFrame| is still valid.
  MOZ_ASSERT(mAnimationsWithDestroyedFrame);
  mAnimationsWithDestroyedFrame->StopAnimationsForElementsWithoutFrames();
}

#ifdef DEBUG
static void VerifyFlatTree(const nsIContent& aContent) {
  StyleChildrenIterator iter(&aContent);

  for (auto* content = iter.GetNextChild(); content;
       content = iter.GetNextChild()) {
    MOZ_ASSERT(content->GetFlattenedTreeParentNodeForStyle() == &aContent);
    VerifyFlatTree(*content);
  }
}
#endif

void ServoRestyleManager::ProcessPendingRestyles() {
#ifdef DEBUG
  if (auto* root = mPresContext->Document()->GetRootElement()) {
    VerifyFlatTree(*root);
  }
#endif

  DoProcessPendingRestyles(ServoTraversalFlags::Empty);
}

void ServoRestyleManager::ProcessAllPendingAttributeAndStateInvalidations() {
  if (mSnapshots.IsEmpty()) {
    return;
  }
  for (auto iter = mSnapshots.Iter(); !iter.Done(); iter.Next()) {
    // Servo data for the element might have been dropped. (e.g. by removing
    // from its document)
    if (iter.Key()->HasFlag(ELEMENT_HAS_SNAPSHOT)) {
      Servo_ProcessInvalidations(StyleSet()->RawSet(), iter.Key(), &mSnapshots);
    }
  }
  ClearSnapshots();
}

bool ServoRestyleManager::HasPendingRestyleAncestor(Element* aElement) const {
  return Servo_HasPendingRestyleAncestor(aElement);
}

void ServoRestyleManager::UpdateOnlyAnimationStyles() {
  bool doCSS = PresContext()->EffectCompositor()->HasPendingStyleUpdates();
  if (!doCSS) {
    return;
  }

  DoProcessPendingRestyles(ServoTraversalFlags::FlushThrottledAnimations);
}

void ServoRestyleManager::ContentStateChanged(nsIContent* aContent,
                                              EventStates aChangedBits) {
  MOZ_ASSERT(!mInStyleRefresh);

  if (!aContent->IsElement()) {
    return;
  }

  Element* aElement = aContent->AsElement();
  if (!aElement->HasServoData()) {
    return;
  }

  const EventStates kVisitedAndUnvisited =
      NS_EVENT_STATE_VISITED | NS_EVENT_STATE_UNVISITED;
  if (aChangedBits.HasAllStates(kVisitedAndUnvisited) &&
      !Gecko_VisitedStylesEnabled(aElement->OwnerDoc())) {
    aChangedBits &= ~kVisitedAndUnvisited;
    if (aChangedBits.IsEmpty()) {
      return;
    }
  }

  nsChangeHint changeHint;
  ContentStateChangedInternal(aElement, aChangedBits, &changeHint);

  // Don't bother taking a snapshot if no rules depend on these state bits.
  //
  // We always take a snapshot for the LTR/RTL event states, since Servo doesn't
  // track those bits in the same way, and we know that :dir() rules are always
  // present in UA style sheets.
  if (!aChangedBits.HasAtLeastOneOfStates(DIRECTION_STATES) &&
      !StyleSet()->HasStateDependency(*aElement, aChangedBits)) {
    return;
  }

  ServoElementSnapshot& snapshot = SnapshotFor(aElement);
  EventStates previousState = aElement->StyleState() ^ aChangedBits;
  snapshot.AddState(previousState);

  if (changeHint) {
    Servo_NoteExplicitHints(aElement, nsRestyleHint(0), changeHint);
  }

  // Assuming we need to invalidate cached style in getComputedStyle for
  // undisplayed elements, since we don't know if it is needed.
  IncrementUndisplayedRestyleGeneration();
}

static inline bool AttributeInfluencesOtherPseudoClassState(
    const Element& aElement, const nsAtom* aAttribute) {
  // We must record some state for :-moz-browser-frame and
  // :-moz-table-border-nonzero.
  if (aAttribute == nsGkAtoms::mozbrowser) {
    return aElement.IsAnyOfHTMLElements(nsGkAtoms::iframe, nsGkAtoms::frame);
  }

  if (aAttribute == nsGkAtoms::border) {
    return aElement.IsHTMLElement(nsGkAtoms::table);
  }

  return false;
}

static inline bool NeedToRecordAttrChange(
    const ServoStyleSet& aStyleSet, const Element& aElement,
    int32_t aNameSpaceID, nsAtom* aAttribute,
    bool* aInfluencesOtherPseudoClassState) {
  *aInfluencesOtherPseudoClassState =
      AttributeInfluencesOtherPseudoClassState(aElement, aAttribute);

  // If the attribute influences one of the pseudo-classes that are backed by
  // attributes, we just record it.
  if (*aInfluencesOtherPseudoClassState) {
    return true;
  }

  // We assume that id and class attributes are used in class/id selectors, and
  // thus record them.
  //
  // TODO(emilio): We keep a filter of the ids in use somewhere in the StyleSet,
  // presumably we could try to filter the old and new id, but it's not clear
  // it's worth it.
  if (aNameSpaceID == kNameSpaceID_None &&
      (aAttribute == nsGkAtoms::id || aAttribute == nsGkAtoms::_class)) {
    return true;
  }

  // We always record lang="", even though we force a subtree restyle when it
  // changes, since it can change how its siblings match :lang(..) due to
  // selectors like :lang(..) + div.
  if (aAttribute == nsGkAtoms::lang) {
    return true;
  }

  // Otherwise, just record the attribute change if a selector in the page may
  // reference it from an attribute selector.
  return aStyleSet.MightHaveAttributeDependency(aElement, aAttribute);
}

void ServoRestyleManager::AttributeWillChange(Element* aElement,
                                              int32_t aNameSpaceID,
                                              nsAtom* aAttribute,
                                              int32_t aModType,
                                              const nsAttrValue* aNewValue) {
  TakeSnapshotForAttributeChange(aElement, aNameSpaceID, aAttribute);
}

void ServoRestyleManager::ClassAttributeWillBeChangedBySMIL(Element* aElement) {
  TakeSnapshotForAttributeChange(aElement, kNameSpaceID_None,
                                 nsGkAtoms::_class);
}

void ServoRestyleManager::TakeSnapshotForAttributeChange(Element* aElement,
                                                         int32_t aNameSpaceID,
                                                         nsAtom* aAttribute) {
  MOZ_ASSERT(!mInStyleRefresh);

  if (!aElement->HasServoData()) {
    return;
  }

  bool influencesOtherPseudoClassState;
  if (!NeedToRecordAttrChange(*StyleSet(), *aElement, aNameSpaceID, aAttribute,
                              &influencesOtherPseudoClassState)) {
    return;
  }

  // We cannot tell if the attribute change will affect the styles of
  // undisplayed elements, because we don't actually restyle those elements
  // during the restyle traversal. So just assume that the attribute change can
  // cause the style to change.
  IncrementUndisplayedRestyleGeneration();

  // Some other random attribute changes may also affect the transitions,
  // so we also set this true here.
  mHaveNonAnimationRestyles = true;

  ServoElementSnapshot& snapshot = SnapshotFor(aElement);
  snapshot.AddAttrs(aElement, aNameSpaceID, aAttribute);

  if (influencesOtherPseudoClassState) {
    snapshot.AddOtherPseudoClassState(aElement);
  }
}

// For some attribute changes we must restyle the whole subtree:
//
// * <td> is affected by the cellpadding on its ancestor table
// * lwtheme and lwthemetextcolor on root element of XUL document
//   affects all descendants due to :-moz-lwtheme* pseudo-classes
// * lang="" and xml:lang="" can affect all descendants due to :lang()
//
static inline bool AttributeChangeRequiresSubtreeRestyle(
    const Element& aElement, nsAtom* aAttr) {
  if (aAttr == nsGkAtoms::cellpadding) {
    return aElement.IsHTMLElement(nsGkAtoms::table);
  }
  if (aAttr == nsGkAtoms::lwtheme || aAttr == nsGkAtoms::lwthemetextcolor) {
    return aElement.GetNameSpaceID() == kNameSpaceID_XUL &&
           &aElement == aElement.OwnerDoc()->GetRootElement();
  }

  return aAttr == nsGkAtoms::lang;
}

void ServoRestyleManager::AttributeChanged(Element* aElement,
                                           int32_t aNameSpaceID,
                                           nsAtom* aAttribute, int32_t aModType,
                                           const nsAttrValue* aOldValue) {
  MOZ_ASSERT(!mInStyleRefresh);

  auto changeHint = nsChangeHint(0);
  auto restyleHint = nsRestyleHint(0);

  changeHint |= aElement->GetAttributeChangeHint(aAttribute, aModType);

  if (aAttribute == nsGkAtoms::style) {
    restyleHint |= eRestyle_StyleAttribute;
  } else if (AttributeChangeRequiresSubtreeRestyle(*aElement, aAttribute)) {
    restyleHint |= eRestyle_Subtree;
  } else if (aElement->IsAttributeMapped(aAttribute)) {
    restyleHint |= eRestyle_Self;
  }

  if (nsIFrame* primaryFrame = aElement->GetPrimaryFrame()) {
    // See if we have appearance information for a theme.
    const nsStyleDisplay* disp = primaryFrame->StyleDisplay();
    if (disp->mAppearance) {
      nsITheme* theme = PresContext()->GetTheme();
      if (theme && theme->ThemeSupportsWidget(PresContext(), primaryFrame,
                                              disp->mAppearance)) {
        bool repaint = false;
        theme->WidgetStateChanged(primaryFrame, disp->mAppearance, aAttribute,
                                  &repaint, aOldValue);
        if (repaint) {
          changeHint |= nsChangeHint_RepaintFrame;
        }
      }
    }

    primaryFrame->AttributeChanged(aNameSpaceID, aAttribute, aModType);
  }

  if (restyleHint || changeHint) {
    Servo_NoteExplicitHints(aElement, restyleHint, changeHint);
  }

  if (restyleHint) {
    // Assuming we need to invalidate cached style in getComputedStyle for
    // undisplayed elements, since we don't know if it is needed.
    IncrementUndisplayedRestyleGeneration();

    // If we change attributes, we have to mark this to be true, so we will
    // increase the animation generation for the new created transition if any.
    mHaveNonAnimationRestyles = true;
  }
}

nsresult ServoRestyleManager::ReparentStyleContext(nsIFrame* aFrame) {
// This is only called when moving frames in or out of the first-line
// pseudo-element (or one of its descendants).  We can't say much about
// aFrame's ancestors, unfortunately (e.g. during a dynamic insert into
// something inside an inline-block on the first line the ancestors could be
// totally arbitrary), but we will definitely find a line frame on the
// ancestor chain.  Note that the lineframe may not actually be the one that
// corresponds to ::first-line; when we're moving _out_ of the ::first-line it
// will be one of the continuations instead.
#ifdef DEBUG
  {
    nsIFrame* f = aFrame->GetParent();
    while (f && !f->IsLineFrame()) {
      f = f->GetParent();
    }
    MOZ_ASSERT(f, "Must have found a first-line frame");
  }
#endif

  DoReparentStyleContext(aFrame, *StyleSet());

  return NS_OK;
}

void ServoRestyleManager::DoReparentStyleContext(nsIFrame* aFrame,
                                                 ServoStyleSet& aStyleSet) {
  if (aFrame->IsBackdropFrame()) {
    // Style context of backdrop frame has no parent style context, and
    // thus we do not need to reparent it.
    return;
  }

  if (aFrame->IsPlaceholderFrame()) {
    // Also reparent the out-of-flow and all its continuations.  We're doing
    // this to match Gecko for now, but it's not clear that this behavior is
    // correct per spec.  It's certainly pretty odd for out-of-flows whose
    // containing block is not within the first line.
    //
    // Right now we're somewhat inconsistent in this testcase:
    //
    //  <style>
    //    div { color: orange; clear: left; }
    //    div::first-line { color: blue; }
    //  </style>
    //  <div>
    //    <span style="float: left">What color is this text?</span>
    //  </div>
    //  <div>
    //    <span><span style="float: left">What color is this text?</span></span>
    //  </div>
    //
    // We make the first float orange and the second float blue.  On the other
    // hand, if the float were within an inline-block that was on the first
    // line, arguably it _should_ inherit from the ::first-line...
    nsIFrame* outOfFlow =
        nsPlaceholderFrame::GetRealFrameForPlaceholder(aFrame);
    MOZ_ASSERT(outOfFlow, "no out-of-flow frame");
    for (; outOfFlow; outOfFlow = outOfFlow->GetNextContinuation()) {
      DoReparentStyleContext(outOfFlow, aStyleSet);
    }
  }

  nsIFrame* providerFrame;
  nsStyleContext* newParentContext =
      aFrame->GetParentStyleContext(&providerFrame);
  // If our provider is our child, we want to reparent it first, because we
  // inherit style from it.
  bool isChild = providerFrame && providerFrame->GetParent() == aFrame;
  nsIFrame* providerChild = nullptr;
  if (isChild) {
    DoReparentStyleContext(providerFrame, aStyleSet);
    // Get the style context again after ReparentStyleContext() which might have
    // changed it.
    newParentContext = providerFrame->StyleContext();
    providerChild = providerFrame;
    MOZ_ASSERT(!providerFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW),
               "Out of flow provider?");
  }

  if (!newParentContext) {
    // No need to do anything here for this frame, but we should still reparent
    // its descendants, because those may have styles that inherit from the
    // parent of this frame (e.g. non-anonymous columns in an anonymous
    // colgroup).
    MOZ_ASSERT(aFrame->StyleContext()->IsNonInheritingAnonBox(),
               "Why did this frame not end up with a parent context?");
    ReparentFrameDescendants(aFrame, providerChild, aStyleSet);
    return;
  }

  bool isElement = aFrame->GetContent()->IsElement();

  // We probably don't want to initiate transitions from
  // ReparentStyleContext, since we call it during frame
  // construction rather than in response to dynamic changes.
  // Also see the comment at the start of
  // nsTransitionManager::ConsiderInitiatingTransition.
  //
  // We don't try to do the fancy copying from previous continuations that
  // GeckoRestyleManager does here, because that relies on knowing the parents
  // of style contexts, and we don't know those.
  ServoStyleContext* oldContext = aFrame->StyleContext()->AsServo();
  Element* ourElement =
      oldContext->GetPseudoType() == CSSPseudoElementType::NotPseudo &&
              isElement
          ? aFrame->GetContent()->AsElement()
          : nullptr;
  ServoStyleContext* newParent = newParentContext->AsServo();

  ServoStyleContext* newParentIgnoringFirstLine;
  if (newParent->GetPseudoType() == CSSPseudoElementType::firstLine) {
    MOZ_ASSERT(providerFrame && providerFrame->GetParent()->IsFrameOfType(
                                    nsIFrame::eBlockFrame),
               "How could we get a ::first-line parent style without having "
               "a ::first-line provider frame?");
    // If newParent is a ::first-line style, get the parent blockframe, and then
    // correct it for our pseudo as needed (e.g. stepping out of anon boxes).
    // Use the resulting style for the "parent style ignoring ::first-line".
    nsIFrame* blockFrame = providerFrame->GetParent();
    nsIFrame* correctedFrame =
        nsFrame::CorrectStyleParentFrame(blockFrame, oldContext->GetPseudo());
    newParentIgnoringFirstLine = correctedFrame->StyleContext()->AsServo();
  } else {
    newParentIgnoringFirstLine = newParent;
  }

  if (!providerFrame) {
    // No providerFrame means we inherited from a display:contents thing.  Our
    // layout parent style is the style of our nearest ancestor frame.  But we
    // have to be careful to do that with our placeholder, not with us, if we're
    // out of flow.
    if (aFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW)) {
      aFrame->GetPlaceholderFrame()->GetLayoutParentStyleForOutOfFlow(
          &providerFrame);
    } else {
      providerFrame = nsFrame::CorrectStyleParentFrame(aFrame->GetParent(),
                                                       oldContext->GetPseudo());
    }
  }
  ServoStyleContext* layoutParent = providerFrame->StyleContext()->AsServo();

  RefPtr<ServoStyleContext> newContext = aStyleSet.ReparentStyleContext(
      oldContext, newParent, newParentIgnoringFirstLine, layoutParent,
      ourElement);
  aFrame->SetStyleContext(newContext);

  // This logic somewhat mirrors the logic in
  // ServoRestyleManager::ProcessPostTraversal.
  if (isElement) {
    // We can't use UpdateAdditionalStyleContexts as-is because it needs a
    // ServoRestyleState and maintaining one of those during a _frametree_
    // traversal is basically impossible.
    uint32_t index = 0;
    while (nsStyleContext* oldAdditionalContext =
               aFrame->GetAdditionalStyleContext(index)) {
      RefPtr<ServoStyleContext> newAdditionalContext =
          aStyleSet.ReparentStyleContext(oldAdditionalContext->AsServo(),
                                         newContext, newContext, newContext,
                                         nullptr);
      aFrame->SetAdditionalStyleContext(index, newAdditionalContext);
      ++index;
    }
  }

  // Generally, owned anon boxes are our descendants.  The only exceptions are
  // tables (for the table wrapper) and inline frames (for the block part of the
  // block-in-inline split).  We're going to update our descendants when looping
  // over kids, and we don't want to update the block part of a block-in-inline
  // split if the inline is on the first line but the block is not (and if the
  // block is, it's the child of something else on the first line and will get
  // updated as a child).  And given how this method ends up getting called, if
  // we reach here for a table frame, we are already in the middle of
  // reparenting the table wrapper frame.  So no need to
  // UpdateStyleOfOwnedAnonBoxes() here.

  ReparentFrameDescendants(aFrame, providerChild, aStyleSet);

  // We do not need to do the equivalent of UpdateFramePseudoElementStyles,
  // because those are hadled by our descendant walk.
}

void ServoRestyleManager::ReparentFrameDescendants(nsIFrame* aFrame,
                                                   nsIFrame* aProviderChild,
                                                   ServoStyleSet& aStyleSet) {
  nsIFrame::ChildListIterator lists(aFrame);
  for (; !lists.IsDone(); lists.Next()) {
    for (nsIFrame* child : lists.CurrentList()) {
      // only do frames that are in flow
      if (!(child->GetStateBits() & NS_FRAME_OUT_OF_FLOW) &&
          child != aProviderChild) {
        DoReparentStyleContext(child, aStyleSet);
      }
    }
  }
}

}  // namespace mozilla