path: root/layout/painting/RetainedDisplayListBuilder.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 "RetainedDisplayListBuilder.h"

#include "mozilla/Attributes.h"
#include "mozilla/StaticPrefs_layout.h"
#include "nsIFrame.h"
#include "nsIFrameInlines.h"
#include "nsIScrollableFrame.h"
#include "nsPlaceholderFrame.h"
#include "nsSubDocumentFrame.h"
#include "nsViewManager.h"
#include "nsCanvasFrame.h"
#include "mozilla/AutoRestore.h"
#include "mozilla/DisplayPortUtils.h"
#include "mozilla/PresShell.h"
#include "mozilla/ProfilerLabels.h"

/**
 * Code for doing display list building for a modified subset of the window,
 * and then merging it into the existing display list (for the full window).
 *
 * The approach primarily hinges on the observation that the 'true' ordering
 * of display items is represented by a DAG (only items that intersect in 2d
 * space have a defined ordering). Our display list is just one of a many
 * possible linear representations of this ordering.
 *
 * Each time a frame changes (gets a new ComputedStyle, or has a size/position
 * change), we schedule a paint (as we do currently), but also reord the frame
 * that changed.
 *
 * When the next paint occurs we union the overflow areas (in screen space) of
 * the changed frames, and compute a rect/region that contains all changed
 * items. We then build a display list just for this subset of the screen and
 * merge it into the display list from last paint.
 *
 * Any items that exist in one list and not the other must not have a defined
 * ordering in the DAG, since they need to intersect to have an ordering and
 * we would have built both in the new list if they intersected. Given that, we
 * can align items that appear in both lists, and any items that appear between
 * matched items can be inserted into the merged list in any order.
 *
 * Frames that are a stacking context, containing blocks for position:fixed
 * descendants, and don't have any continuations (see
 * CanStoreDisplayListBuildingRect) trigger recursion into the algorithm with
 * separate retaining decisions made.
 *
 * RDL defines the concept of an AnimatedGeometryRoot (AGR), the nearest
 * ancestor frame which can be moved asynchronously on the compositor thread.
 * These are currently nsDisplayItems which return true from CanMoveAsync
 * (animated nsDisplayTransform and nsDisplayStickyPosition) and
 * ActiveScrolledRoots.
 *
 * For each context that we run the retaining algorithm, there can only be
 * mutations to one AnimatedGeometryRoot. This is because we are unable to
 * reason about intersections of items that might then move relative to each
 * other without RDL running again. If there are mutations to multiple
 * AnimatedGeometryRoots, then we bail out and rebuild all the items in the
 * context.
 *
 * Otherwise, when mutations are restricted to a single AGR, we pre-process the
 * old display list and mark the frames for all existing (unmodified!) items
 * that belong to a different AGR and ensure that we rebuild those items for
 * correct sorting with the modified ones.
 */

namespace mozilla {

RetainedDisplayListData::RetainedDisplayListData()
    : mModifiedFrameLimit(
          StaticPrefs::layout_display_list_rebuild_frame_limit()) {}

void RetainedDisplayListData::AddModifiedFrame(nsIFrame* aFrame) {
  MOZ_ASSERT(!aFrame->IsFrameModified());
  Flags(aFrame) += RetainedDisplayListData::FrameFlag::Modified;
  aFrame->SetFrameIsModified(true);
  mModifiedFrameCount++;
}

static void MarkFramesWithItemsAndImagesModified(nsDisplayList* aList) {
  for (nsDisplayItem* i : *aList) {
    if (!i->HasDeletedFrame() && i->CanBeReused() &&
        !i->Frame()->IsFrameModified()) {
      // If we have existing cached geometry for this item, then check that for
      // whether we need to invalidate for a sync decode. If we don't, then
      // use the item's flags.
      // XXX: handle webrender case by looking up retained data for the item
      // and checking InvalidateForSyncDecodeImages
      bool invalidate = false;
      if (!(i->GetFlags() & TYPE_RENDERS_NO_IMAGES)) {
        invalidate = true;
      }

      if (invalidate) {
        DL_LOGV("RDL - Invalidating item %p (%s)", i, i->Name());
        i->FrameForInvalidation()->MarkNeedsDisplayItemRebuild();
        if (i->GetDependentFrame()) {
          i->GetDependentFrame()->MarkNeedsDisplayItemRebuild();
        }
      }
    }
    if (i->GetChildren()) {
      MarkFramesWithItemsAndImagesModified(i->GetChildren());
    }
  }
}

static nsIFrame* SelectAGRForFrame(nsIFrame* aFrame, nsIFrame* aParentAGR) {
  if (!aFrame->IsStackingContext() || !aFrame->IsFixedPosContainingBlock()) {
    return aParentAGR;
  }

  if (!aFrame->HasOverrideDirtyRegion()) {
    return nullptr;
  }

  nsDisplayListBuilder::DisplayListBuildingData* data =
      aFrame->GetProperty(nsDisplayListBuilder::DisplayListBuildingRect());

  return data && data->mModifiedAGR ? data->mModifiedAGR : nullptr;
}

void RetainedDisplayListBuilder::AddSizeOfIncludingThis(
    nsWindowSizes& aSizes) const {
  aSizes.mLayoutRetainedDisplayListSize += aSizes.mState.mMallocSizeOf(this);
  mBuilder.AddSizeOfExcludingThis(aSizes);
  mList.AddSizeOfExcludingThis(aSizes);
}

bool AnyContentAncestorModified(nsIFrame* aFrame, nsIFrame* aStopAtFrame) {
  nsIFrame* f = aFrame;
  while (f) {
    if (f->IsFrameModified()) {
      return true;
    }

    if (aStopAtFrame && f == aStopAtFrame) {
      break;
    }

    f = nsLayoutUtils::GetDisplayListParent(f);
  }

  return false;
}

// Removes any display items that belonged to a frame that was deleted,
// and mark frames that belong to a different AGR so that get their
// items built again.
// TODO: We currently descend into all children even if we don't have an AGR
// to mark, as child stacking contexts might. It would be nice if we could
// jump into those immediately rather than walking the entire thing.
bool RetainedDisplayListBuilder::PreProcessDisplayList(
    RetainedDisplayList* aList, nsIFrame* aAGR, PartialUpdateResult& aUpdated,
    nsIFrame* aAsyncAncestor, const ActiveScrolledRoot* aAsyncAncestorASR,
    nsIFrame* aOuterFrame, uint32_t aCallerKey, uint32_t aNestingDepth,
    bool aKeepLinked) {
  // The DAG merging algorithm does not have strong mechanisms in place to keep
  // the complexity of the resulting DAG under control. In some cases we can
  // build up edges very quickly. Detect those cases and force a full display
  // list build if we hit them.
  static const uint32_t kMaxEdgeRatio = 5;
  const bool initializeDAG = !aList->mDAG.Length();
  if (!aKeepLinked && !initializeDAG &&
      aList->mDAG.mDirectPredecessorList.Length() >
          (aList->mDAG.mNodesInfo.Length() * kMaxEdgeRatio)) {
    return false;
  }

  // If we had aKeepLinked=true for this list on the previous paint, then
  // mOldItems will already be initialized as it won't have been consumed during
  // a merge.
  const bool initializeOldItems = aList->mOldItems.IsEmpty();
  if (initializeOldItems) {
    aList->mOldItems.SetCapacity(aList->Length());
  } else {
    MOZ_RELEASE_ASSERT(!initializeDAG);
  }

  MOZ_RELEASE_ASSERT(
      initializeDAG ||
      aList->mDAG.Length() ==
          (initializeOldItems ? aList->Length() : aList->mOldItems.Length()));

  nsDisplayList out(Builder());

  size_t i = 0;
  while (nsDisplayItem* item = aList->RemoveBottom()) {
#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
    item->SetMergedPreProcessed(false, true);
#endif

    // If we have a previously initialized old items list, then it can differ
    // from the current list due to items removed for having a deleted frame.
    // We can't easily remove these, since the DAG has entries for those indices
    // and it's hard to rewrite in-place.
    // Skip over entries with no current item to keep the iterations in sync.
    if (!initializeOldItems) {
      while (!aList->mOldItems[i].mItem) {
        i++;
      }
    }

    if (initializeDAG) {
      if (i == 0) {
        aList->mDAG.AddNode(Span<const MergedListIndex>());
      } else {
        MergedListIndex previous(i - 1);
        aList->mDAG.AddNode(Span<const MergedListIndex>(&previous, 1));
      }
    }

    if (!item->CanBeReused() || item->HasDeletedFrame() ||
        AnyContentAncestorModified(item->FrameForInvalidation(), aOuterFrame)) {
      if (initializeOldItems) {
        aList->mOldItems.AppendElement(OldItemInfo(nullptr));
      } else {
        MOZ_RELEASE_ASSERT(aList->mOldItems[i].mItem == item);
        aList->mOldItems[i].mItem = nullptr;
      }

      if (item->IsGlassItem() && item == mBuilder.GetGlassDisplayItem()) {
        mBuilder.ClearGlassDisplayItem();
      }

      item->Destroy(&mBuilder);
      Metrics()->mRemovedItems++;

      i++;
      aUpdated = PartialUpdateResult::Updated;
      continue;
    }

    if (initializeOldItems) {
      aList->mOldItems.AppendElement(OldItemInfo(item));
    }

    // If we're not going to keep the list linked, then this old item entry
    // is the only pointer to the item. Let it know that it now strongly
    // owns the item, so it can destroy it if it goes away.
    aList->mOldItems[i].mOwnsItem = !aKeepLinked;

    item->SetOldListIndex(aList, OldListIndex(i), aCallerKey, aNestingDepth);

    nsIFrame* f = item->Frame();

    if (item->GetChildren()) {
      // If children inside this list were invalid, then we'd have walked the
      // ancestors and set ForceDescendIntoVisible on the current frame. If an
      // ancestor is modified, then we'll throw this away entirely. Either way,
      // we won't need to run merging on this sublist, and we can keep the items
      // linked into their display list.
      // The caret can move without invalidating, but we always set the force
      // descend into frame state bit on that frame, so check for that too.
      // TODO: AGR marking below can call MarkFrameForDisplayIfVisible and make
      // us think future siblings need to be merged, even though we don't really
      // need to.
      bool keepLinked = aKeepLinked;
      nsIFrame* invalid = item->FrameForInvalidation();
      if (!invalid->ForceDescendIntoIfVisible() &&
          !invalid->HasAnyStateBits(NS_FRAME_FORCE_DISPLAY_LIST_DESCEND_INTO)) {
        keepLinked = true;
      }

      // If this item's frame is an AGR (can be moved asynchronously by the
      // compositor), then use that frame for descendants. Also pass the ASR
      // for that item, so that descendants can compare to see if any new
      // ASRs have been pushed since.
      nsIFrame* asyncAncestor = aAsyncAncestor;
      const ActiveScrolledRoot* asyncAncestorASR = aAsyncAncestorASR;
      if (item->CanMoveAsync()) {
        asyncAncestor = item->Frame();
        asyncAncestorASR = item->GetActiveScrolledRoot();
      }

      if (!PreProcessDisplayList(
              item->GetChildren(), SelectAGRForFrame(f, aAGR), aUpdated,
              asyncAncestor, asyncAncestorASR, item->Frame(),
              item->GetPerFrameKey(), aNestingDepth + 1, keepLinked)) {
        MOZ_RELEASE_ASSERT(
            !aKeepLinked,
            "Can't early return since we need to move the out list back");
        return false;
      }
    }

    // TODO: We should be able to check the clipped bounds relative
    // to the common AGR (of both the existing item and the invalidated
    // frame) and determine if they can ever intersect.
    // TODO: We only really need to build the ancestor container item that is a
    // sibling of the changed thing to get correct ordering. The changed content
    // is a frame though, and it's hard to map that to container items in this
    // list.
    // If an ancestor display item is an AGR, and our ASR matches the ASR
    // of that item, then there can't have been any new ASRs pushed since that
    // item, so that item is our AGR. Otherwise, our AGR is our ASR.
    // TODO: If aAsyncAncestorASR is non-null, then item->GetActiveScrolledRoot
    // should be the same or a descendant and also non-null. Unfortunately an
    // RDL bug means this can be wrong for sticky items after a partial update,
    // so we have to work around it. Bug 1730749 and bug 1730826 should resolve
    // this.
    nsIFrame* agrFrame = nullptr;
    if (aAsyncAncestorASR == item->GetActiveScrolledRoot() ||
        !item->GetActiveScrolledRoot()) {
      agrFrame = aAsyncAncestor;
    } else {
      agrFrame =
          item->GetActiveScrolledRoot()->mScrollableFrame->GetScrolledFrame();
    }

    if (aAGR && agrFrame != aAGR) {
      mBuilder.MarkFrameForDisplayIfVisible(f, RootReferenceFrame());
    }

    // If we're going to keep this linked list and not merge it, then mark the
    // item as used and put it back into the list.
    if (aKeepLinked) {
      item->SetReused(true);
      if (item->GetChildren()) {
        item->UpdateBounds(Builder());
      }
      if (item->GetType() == DisplayItemType::TYPE_SUBDOCUMENT) {
        IncrementSubDocPresShellPaintCount(item);
      }
      out.AppendToTop(item);
    }
    i++;
  }

  MOZ_RELEASE_ASSERT(aList->mOldItems.Length() == aList->mDAG.Length());

  if (aKeepLinked) {
    aList->AppendToTop(&out);
  }

  return true;
}

void IncrementPresShellPaintCount(nsDisplayListBuilder* aBuilder,
                                  nsDisplayItem* aItem) {
  MOZ_ASSERT(aItem->GetType() == DisplayItemType::TYPE_SUBDOCUMENT);

  nsSubDocumentFrame* subDocFrame =
      static_cast<nsDisplaySubDocument*>(aItem)->SubDocumentFrame();
  MOZ_ASSERT(subDocFrame);

  PresShell* presShell = subDocFrame->GetSubdocumentPresShellForPainting(0);
  MOZ_ASSERT(presShell);

  aBuilder->IncrementPresShellPaintCount(presShell);
}

void RetainedDisplayListBuilder::IncrementSubDocPresShellPaintCount(
    nsDisplayItem* aItem) {
  IncrementPresShellPaintCount(&mBuilder, aItem);
}

static Maybe<const ActiveScrolledRoot*> SelectContainerASR(
    const DisplayItemClipChain* aClipChain, const ActiveScrolledRoot* aItemASR,
    Maybe<const ActiveScrolledRoot*>& aContainerASR) {
  const ActiveScrolledRoot* itemClipASR =
      aClipChain ? aClipChain->mASR : nullptr;

  const ActiveScrolledRoot* finiteBoundsASR =
      ActiveScrolledRoot::PickDescendant(itemClipASR, aItemASR);

  if (!aContainerASR) {
    return Some(finiteBoundsASR);
  }

  return Some(
      ActiveScrolledRoot::PickAncestor(*aContainerASR, finiteBoundsASR));
}

static void UpdateASR(nsDisplayItem* aItem,
                      Maybe<const ActiveScrolledRoot*>& aContainerASR) {
  if (!aContainerASR) {
    return;
  }

  nsDisplayWrapList* wrapList = aItem->AsDisplayWrapList();
  if (!wrapList) {
    aItem->SetActiveScrolledRoot(*aContainerASR);
    return;
  }

  wrapList->SetActiveScrolledRoot(ActiveScrolledRoot::PickAncestor(
      wrapList->GetFrameActiveScrolledRoot(), *aContainerASR));
}

static void CopyASR(nsDisplayItem* aOld, nsDisplayItem* aNew) {
  aNew->SetActiveScrolledRoot(aOld->GetActiveScrolledRoot());
}

OldItemInfo::OldItemInfo(nsDisplayItem* aItem)
    : mItem(aItem), mUsed(false), mDiscarded(false), mOwnsItem(false) {
  if (mItem) {
    // Clear cached modified frame state when adding an item to the old list.
    mItem->SetModifiedFrame(false);
  }
}

void OldItemInfo::AddedMatchToMergedList(RetainedDisplayListBuilder* aBuilder,
                                         MergedListIndex aIndex) {
  AddedToMergedList(aIndex);
}

void OldItemInfo::Discard(RetainedDisplayListBuilder* aBuilder,
                          nsTArray<MergedListIndex>&& aDirectPredecessors) {
  MOZ_ASSERT(!IsUsed());
  mUsed = mDiscarded = true;
  mDirectPredecessors = std::move(aDirectPredecessors);
  if (mItem) {
    MOZ_ASSERT(mOwnsItem);
    mItem->Destroy(aBuilder->Builder());
    aBuilder->Metrics()->mRemovedItems++;
  }
  mItem = nullptr;
}

bool OldItemInfo::IsChanged() {
  return !mItem || !mItem->CanBeReused() || mItem->HasDeletedFrame();
}

/**
 * A C++ implementation of Markus Stange's merge-dags algorithm.
 * https://github.com/mstange/merge-dags
 *
 * MergeState handles combining a new list of display items into an existing
 * DAG and computes the new DAG in a single pass.
 * Each time we add a new item, we resolve all dependencies for it, so that the
 * resulting list and DAG are built in topological ordering.
 */
class MergeState {
 public:
  MergeState(RetainedDisplayListBuilder* aBuilder,
             RetainedDisplayList& aOldList, nsDisplayItem* aOuterItem)
      : mBuilder(aBuilder),
        mOldList(&aOldList),
        mOldItems(std::move(aOldList.mOldItems)),
        mOldDAG(
            std::move(*reinterpret_cast<DirectedAcyclicGraph<OldListUnits>*>(
                &aOldList.mDAG))),
        mMergedItems(aBuilder->Builder()),
        mOuterItem(aOuterItem),
        mResultIsModified(false) {
    mMergedDAG.EnsureCapacityFor(mOldDAG);
    MOZ_RELEASE_ASSERT(mOldItems.Length() == mOldDAG.Length());
  }

  Maybe<MergedListIndex> ProcessItemFromNewList(
      nsDisplayItem* aNewItem, const Maybe<MergedListIndex>& aPreviousItem) {
    OldListIndex oldIndex;
    MOZ_DIAGNOSTIC_ASSERT(aNewItem->HasModifiedFrame() ==
                          HasModifiedFrame(aNewItem));
    if (!aNewItem->HasModifiedFrame() &&
        HasMatchingItemInOldList(aNewItem, &oldIndex)) {
      mBuilder->Metrics()->mRebuiltItems++;
      nsDisplayItem* oldItem = mOldItems[oldIndex.val].mItem;
      MOZ_DIAGNOSTIC_ASSERT(oldItem->GetPerFrameKey() ==
                                aNewItem->GetPerFrameKey() &&
                            oldItem->Frame() == aNewItem->Frame());
      if (!mOldItems[oldIndex.val].IsChanged()) {
        MOZ_DIAGNOSTIC_ASSERT(!mOldItems[oldIndex.val].IsUsed());
        nsDisplayItem* destItem;
        if (ShouldUseNewItem(aNewItem)) {
          destItem = aNewItem;
        } else {
          destItem = oldItem;
          // The building rect can depend on the overflow rect (when the parent
          // frame is position:fixed), which can change without invalidating
          // the frame/items. If we're using the old item, copy the building
          // rect across from the new item.
          oldItem->SetBuildingRect(aNewItem->GetBuildingRect());
        }

        if (destItem == aNewItem) {
          if (oldItem->IsGlassItem() &&
              oldItem == mBuilder->Builder()->GetGlassDisplayItem()) {
            mBuilder->Builder()->ClearGlassDisplayItem();
          }
        }  // aNewItem can't be the glass item on the builder yet.

        if (destItem->IsGlassItem()) {
          if (destItem != oldItem ||
              destItem != mBuilder->Builder()->GetGlassDisplayItem()) {
            mBuilder->Builder()->SetGlassDisplayItem(destItem);
          }
        }

        MergeChildLists(aNewItem, oldItem, destItem);

        AutoTArray<MergedListIndex, 2> directPredecessors =
            ProcessPredecessorsOfOldNode(oldIndex);
        MergedListIndex newIndex = AddNewNode(
            destItem, Some(oldIndex), directPredecessors, aPreviousItem);
        mOldItems[oldIndex.val].AddedMatchToMergedList(mBuilder, newIndex);
        if (destItem == aNewItem) {
          oldItem->Destroy(mBuilder->Builder());
        } else {
          aNewItem->Destroy(mBuilder->Builder());
        }
        return Some(newIndex);
      }
    }
    mResultIsModified = true;
    if (aNewItem->IsGlassItem()) {
      mBuilder->Builder()->SetGlassDisplayItem(aNewItem);
    }
    return Some(AddNewNode(aNewItem, Nothing(), Span<MergedListIndex>(),
                           aPreviousItem));
  }

  void MergeChildLists(nsDisplayItem* aNewItem, nsDisplayItem* aOldItem,
                       nsDisplayItem* aOutItem) {
    if (!aOutItem->GetChildren()) {
      return;
    }

    Maybe<const ActiveScrolledRoot*> containerASRForChildren;
    nsDisplayList empty(mBuilder->Builder());
    const bool modified = mBuilder->MergeDisplayLists(
        aNewItem ? aNewItem->GetChildren() : &empty, aOldItem->GetChildren(),
        aOutItem->GetChildren(), containerASRForChildren, aOutItem);
    if (modified) {
      aOutItem->InvalidateCachedChildInfo(mBuilder->Builder());
      UpdateASR(aOutItem, containerASRForChildren);
      mResultIsModified = true;
    } else if (aOutItem == aNewItem) {
      // If nothing changed, but we copied the contents across to
      // the new item, then also copy the ASR data.
      CopyASR(aOldItem, aNewItem);
    }
    // Ideally we'd only UpdateBounds if something changed, but
    // nsDisplayWrapList also uses this to update the clip chain for the
    // current ASR, which gets reset during RestoreState(), so we always need
    // to run it again.
    aOutItem->UpdateBounds(mBuilder->Builder());
  }

  bool ShouldUseNewItem(nsDisplayItem* aNewItem) {
    // Generally we want to use the old item when the frame isn't marked as
    // modified so that any cached information on the item (or referencing the
    // item) gets retained. Quite a few FrameLayerBuilder performance
    // improvements benefit by this. Sometimes, however, we can end up where the
    // new item paints something different from the old item, even though we
    // haven't modified the frame, and it's hard to fix. In these cases we just
    // always use the new item to be safe.
    DisplayItemType type = aNewItem->GetType();
    if (type == DisplayItemType::TYPE_CANVAS_BACKGROUND_COLOR ||
        type == DisplayItemType::TYPE_SOLID_COLOR) {
      // The canvas background color item can paint the color from another
      // frame, and even though we schedule a paint, we don't mark the canvas
      // frame as invalid.
      return true;
    }

    if (type == DisplayItemType::TYPE_TABLE_BORDER_COLLAPSE) {
      // We intentionally don't mark the root table frame as modified when a
      // subframe changes, even though the border collapse item for the root
      // frame is what paints the changed border. Marking the root frame as
      // modified would rebuild display items for the whole table area, and we
      // don't want that.
      return true;
    }

    if (type == DisplayItemType::TYPE_TEXT_OVERFLOW) {
      // Text overflow marker items are created with the wrapping block as their
      // frame, and have an index value to note which line they are created for.
      // Their rendering can change if the items on that line change, which may
      // not mark the block as modified. We rebuild them if we build any item on
      // the line, so we should always get new items if they might have changed
      // rendering, and it's easier to just use the new items rather than
      // computing if we actually need them.
      return true;
    }

    if (type == DisplayItemType::TYPE_SUBDOCUMENT ||
        type == DisplayItemType::TYPE_STICKY_POSITION) {
      // nsDisplaySubDocument::mShouldFlatten can change without an invalidation
      // (and is the reason we unconditionally build the subdocument item), so
      // always use the new one to make sure we get the right value.
      // Same for |nsDisplayStickyPosition::mShouldFlatten|.
      return true;
    }

    if (type == DisplayItemType::TYPE_CARET) {
      // The caret can change position while still being owned by the same frame
      // and we don't invalidate in that case. Use the new version since the
      // changed bounds are needed for DLBI.
      return true;
    }

    if (type == DisplayItemType::TYPE_MASK ||
        type == DisplayItemType::TYPE_FILTER ||
        type == DisplayItemType::TYPE_SVG_WRAPPER) {
      // SVG items have some invalidation issues, see bugs 1494110 and 1494663.
      return true;
    }

    if (type == DisplayItemType::TYPE_TRANSFORM) {
      // Prerendering of transforms can change without frame invalidation.
      return true;
    }

    return false;
  }

  RetainedDisplayList Finalize() {
    for (size_t i = 0; i < mOldDAG.Length(); i++) {
      if (mOldItems[i].IsUsed()) {
        continue;
      }

      AutoTArray<MergedListIndex, 2> directPredecessors =
          ResolveNodeIndexesOldToMerged(
              mOldDAG.GetDirectPredecessors(OldListIndex(i)));
      ProcessOldNode(OldListIndex(i), std::move(directPredecessors));
    }

    RetainedDisplayList result(mBuilder->Builder());
    result.AppendToTop(&mMergedItems);
    result.mDAG = std::move(mMergedDAG);
    MOZ_RELEASE_ASSERT(result.mDAG.Length() == result.Length());
    return result;
  }

  bool HasMatchingItemInOldList(nsDisplayItem* aItem, OldListIndex* aOutIndex) {
    // Look for an item that matches aItem's frame and per-frame-key, but isn't
    // the same item.
    uint32_t outerKey = mOuterItem ? mOuterItem->GetPerFrameKey() : 0;
    nsIFrame* frame = aItem->Frame();
    for (nsDisplayItem* i : frame->DisplayItems()) {
      if (i != aItem && i->Frame() == frame &&
          i->GetPerFrameKey() == aItem->GetPerFrameKey()) {
        if (i->GetOldListIndex(mOldList, outerKey, aOutIndex)) {
          return true;
        }
      }
    }
    return false;
  }

#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
  bool HasModifiedFrame(nsDisplayItem* aItem) {
    nsIFrame* stopFrame = mOuterItem ? mOuterItem->Frame() : nullptr;
    return AnyContentAncestorModified(aItem->FrameForInvalidation(), stopFrame);
  }
#endif

  void UpdateContainerASR(nsDisplayItem* aItem) {
    mContainerASR = SelectContainerASR(
        aItem->GetClipChain(), aItem->GetActiveScrolledRoot(), mContainerASR);
  }

  MergedListIndex AddNewNode(
      nsDisplayItem* aItem, const Maybe<OldListIndex>& aOldIndex,
      Span<const MergedListIndex> aDirectPredecessors,
      const Maybe<MergedListIndex>& aExtraDirectPredecessor) {
    UpdateContainerASR(aItem);
    aItem->NotifyUsed(mBuilder->Builder());

#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
    for (nsDisplayItem* i : aItem->Frame()->DisplayItems()) {
      if (i->Frame() == aItem->Frame() &&
          i->GetPerFrameKey() == aItem->GetPerFrameKey()) {
        MOZ_DIAGNOSTIC_ASSERT(!i->IsMergedItem());
      }
    }

    aItem->SetMergedPreProcessed(true, false);
#endif

    mMergedItems.AppendToTop(aItem);
    mBuilder->Metrics()->mTotalItems++;

    MergedListIndex newIndex =
        mMergedDAG.AddNode(aDirectPredecessors, aExtraDirectPredecessor);
    return newIndex;
  }

  void ProcessOldNode(OldListIndex aNode,
                      nsTArray<MergedListIndex>&& aDirectPredecessors) {
    nsDisplayItem* item = mOldItems[aNode.val].mItem;
    if (mOldItems[aNode.val].IsChanged()) {
      if (item && item->IsGlassItem() &&
          item == mBuilder->Builder()->GetGlassDisplayItem()) {
        mBuilder->Builder()->ClearGlassDisplayItem();
      }

      mOldItems[aNode.val].Discard(mBuilder, std::move(aDirectPredecessors));
      mResultIsModified = true;
    } else {
      MergeChildLists(nullptr, item, item);

      if (item->GetType() == DisplayItemType::TYPE_SUBDOCUMENT) {
        mBuilder->IncrementSubDocPresShellPaintCount(item);
      }
      item->SetReused(true);
      mBuilder->Metrics()->mReusedItems++;
      mOldItems[aNode.val].AddedToMergedList(
          AddNewNode(item, Some(aNode), aDirectPredecessors, Nothing()));
    }
  }

  struct PredecessorStackItem {
    PredecessorStackItem(OldListIndex aNode, Span<OldListIndex> aPredecessors)
        : mNode(aNode),
          mDirectPredecessors(aPredecessors),
          mCurrentPredecessorIndex(0) {}

    bool IsFinished() {
      return mCurrentPredecessorIndex == mDirectPredecessors.Length();
    }

    OldListIndex GetAndIncrementCurrentPredecessor() {
      return mDirectPredecessors[mCurrentPredecessorIndex++];
    }

    OldListIndex mNode;
    Span<OldListIndex> mDirectPredecessors;
    size_t mCurrentPredecessorIndex;
  };

  AutoTArray<MergedListIndex, 2> ProcessPredecessorsOfOldNode(
      OldListIndex aNode) {
    AutoTArray<PredecessorStackItem, 256> mStack;
    mStack.AppendElement(
        PredecessorStackItem(aNode, mOldDAG.GetDirectPredecessors(aNode)));

    while (true) {
      if (mStack.LastElement().IsFinished()) {
        // If we've finished processing all the entries in the current set, then
        // pop it off the processing stack and process it.
        PredecessorStackItem item = mStack.PopLastElement();
        AutoTArray<MergedListIndex, 2> result =
            ResolveNodeIndexesOldToMerged(item.mDirectPredecessors);

        if (mStack.IsEmpty()) {
          return result;
        }

        ProcessOldNode(item.mNode, std::move(result));
      } else {
        // Grab the current predecessor, push predecessors of that onto the
        // processing stack (if it hasn't already been processed), and then
        // advance to the next entry.
        OldListIndex currentIndex =
            mStack.LastElement().GetAndIncrementCurrentPredecessor();
        if (!mOldItems[currentIndex.val].IsUsed()) {
          mStack.AppendElement(PredecessorStackItem(
              currentIndex, mOldDAG.GetDirectPredecessors(currentIndex)));
        }
      }
    }
  }

  AutoTArray<MergedListIndex, 2> ResolveNodeIndexesOldToMerged(
      Span<OldListIndex> aDirectPredecessors) {
    AutoTArray<MergedListIndex, 2> result;
    result.SetCapacity(aDirectPredecessors.Length());
    for (OldListIndex index : aDirectPredecessors) {
      OldItemInfo& oldItem = mOldItems[index.val];
      if (oldItem.IsDiscarded()) {
        for (MergedListIndex inner : oldItem.mDirectPredecessors) {
          if (!result.Contains(inner)) {
            result.AppendElement(inner);
          }
        }
      } else {
        result.AppendElement(oldItem.mIndex);
      }
    }
    return result;
  }

  RetainedDisplayListBuilder* mBuilder;
  RetainedDisplayList* mOldList;
  Maybe<const ActiveScrolledRoot*> mContainerASR;
  nsTArray<OldItemInfo> mOldItems;
  DirectedAcyclicGraph<OldListUnits> mOldDAG;
  // Unfortunately we can't use strong typing for the hashtables
  // since they internally encode the type with the mOps pointer,
  // and assert when we try swap the contents
  nsDisplayList mMergedItems;
  DirectedAcyclicGraph<MergedListUnits> mMergedDAG;
  nsDisplayItem* mOuterItem;
  bool mResultIsModified;
};

#ifdef DEBUG
void VerifyNotModified(nsDisplayList* aList) {
  for (nsDisplayItem* item : *aList) {
    MOZ_ASSERT(!AnyContentAncestorModified(item->FrameForInvalidation()));

    if (item->GetChildren()) {
      VerifyNotModified(item->GetChildren());
    }
  }
}
#endif

/**
 * Takes two display lists and merges them into an output list.
 *
 * Display lists wthout an explicit DAG are interpreted as linear DAGs (with a
 * maximum of one direct predecessor and one direct successor per node). We add
 * the two DAGs together, and then output the topological sorted ordering as the
 * final display list.
 *
 * Once we've merged a list, we then retain the DAG (as part of the
 * RetainedDisplayList object) to use for future merges.
 */
bool RetainedDisplayListBuilder::MergeDisplayLists(
    nsDisplayList* aNewList, RetainedDisplayList* aOldList,
    RetainedDisplayList* aOutList,
    mozilla::Maybe<const mozilla::ActiveScrolledRoot*>& aOutContainerASR,
    nsDisplayItem* aOuterItem) {
  AUTO_PROFILER_LABEL_CATEGORY_PAIR(GRAPHICS_DisplayListMerging);

  if (!aOldList->IsEmpty()) {
    // If we still have items in the actual list, then it is because
    // PreProcessDisplayList decided that it was sure it can't be modified. We
    // can just use it directly, and throw any new items away.

    aNewList->DeleteAll(&mBuilder);
#ifdef DEBUG
    VerifyNotModified(aOldList);
#endif

    if (aOldList != aOutList) {
      *aOutList = std::move(*aOldList);
    }

    return false;
  }

  MergeState merge(this, *aOldList, aOuterItem);

  Maybe<MergedListIndex> previousItemIndex;
  for (nsDisplayItem* item : aNewList->TakeItems()) {
    Metrics()->mNewItems++;
    previousItemIndex = merge.ProcessItemFromNewList(item, previousItemIndex);
  }

  *aOutList = merge.Finalize();
  aOutContainerASR = merge.mContainerASR;
  return merge.mResultIsModified;
}

void RetainedDisplayListBuilder::GetModifiedAndFramesWithProps(
    nsTArray<nsIFrame*>* aOutModifiedFrames,
    nsTArray<nsIFrame*>* aOutFramesWithProps) {
  for (auto it = Data()->ConstIterator(); !it.Done(); it.Next()) {
    nsIFrame* frame = it.Key();
    const RetainedDisplayListData::FrameFlags& flags = it.Data();

    if (flags.contains(RetainedDisplayListData::FrameFlag::Modified)) {
      aOutModifiedFrames->AppendElement(frame);
    }

    if (flags.contains(RetainedDisplayListData::FrameFlag::HasProps)) {
      aOutFramesWithProps->AppendElement(frame);
    }

    if (flags.contains(RetainedDisplayListData::FrameFlag::HadWillChange)) {
      Builder()->RemoveFromWillChangeBudgets(frame);
    }
  }

  Data()->Clear();
}

// ComputeRebuildRegion  debugging
// #define CRR_DEBUG 1
#if CRR_DEBUG
#  define CRR_LOG(...) printf_stderr(__VA_ARGS__)
#else
#  define CRR_LOG(...)
#endif

static nsDisplayItem* GetFirstDisplayItemWithChildren(nsIFrame* aFrame) {
  for (nsDisplayItem* i : aFrame->DisplayItems()) {
    if (i->HasDeletedFrame() || i->Frame() != aFrame) {
      // The main frame for the display item has been deleted or the display
      // item belongs to another frame.
      continue;
    }

    if (i->HasChildren()) {
      return static_cast<nsDisplayItem*>(i);
    }
  }
  return nullptr;
}

static bool IsInPreserve3DContext(const nsIFrame* aFrame) {
  return aFrame->Extend3DContext() ||
         aFrame->Combines3DTransformWithAncestors();
}

// Returns true if |aFrame| can store a display list building rect.
// These limitations are necessary to guarantee that
// 1) Just enough items are rebuilt to properly update display list
// 2) Modified frames will be visited during a partial display list build.
static bool CanStoreDisplayListBuildingRect(nsDisplayListBuilder* aBuilder,
                                            nsIFrame* aFrame) {
  return aFrame != aBuilder->RootReferenceFrame() &&
         aFrame->IsStackingContext() && aFrame->IsFixedPosContainingBlock() &&
         // Split frames might have placeholders for modified frames in their
         // unmodified continuation frame.
         !aFrame->GetPrevContinuation() && !aFrame->GetNextContinuation();
}

static bool ProcessFrameInternal(nsIFrame* aFrame,
                                 nsDisplayListBuilder* aBuilder,
                                 nsIFrame** aAGR, nsRect& aOverflow,
                                 const nsIFrame* aStopAtFrame,
                                 nsTArray<nsIFrame*>& aOutFramesWithProps,
                                 const bool aStopAtStackingContext) {
  nsIFrame* currentFrame = aFrame;

  while (currentFrame != aStopAtFrame) {
    CRR_LOG("currentFrame: %p (placeholder=%d), aOverflow: %d %d %d %d\n",
            currentFrame, !aStopAtStackingContext, aOverflow.x, aOverflow.y,
            aOverflow.width, aOverflow.height);

    // If the current frame is an OOF frame, DisplayListBuildingData needs to be
    // set on all the ancestor stacking contexts of the  placeholder frame, up
    // to the containing block of the OOF frame. This is done to ensure that the
    // content that might be behind the OOF frame is built for merging.
    nsIFrame* placeholder = currentFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW)
                                ? currentFrame->GetPlaceholderFrame()
                                : nullptr;

    if (placeholder) {
      nsRect placeholderOverflow = aOverflow;
      auto rv = nsLayoutUtils::TransformRect(currentFrame, placeholder,
                                             placeholderOverflow);
      if (rv != nsLayoutUtils::TRANSFORM_SUCCEEDED) {
        placeholderOverflow = nsRect();
      }

      CRR_LOG("Processing placeholder %p for OOF frame %p\n", placeholder,
              currentFrame);

      CRR_LOG("OOF frame draw area: %d %d %d %d\n", placeholderOverflow.x,
              placeholderOverflow.y, placeholderOverflow.width,
              placeholderOverflow.height);

      // Tracking AGRs for the placeholder processing is not necessary, as the
      // goal is to only modify the DisplayListBuildingData rect.
      nsIFrame* dummyAGR = nullptr;

      // Find a common ancestor frame to handle frame continuations.
      // TODO: It might be possible to write a more specific and efficient
      // function for this.
      const nsIFrame* ancestor = nsLayoutUtils::FindNearestCommonAncestorFrame(
          currentFrame->GetParent(), placeholder->GetParent());

      if (!ProcessFrameInternal(placeholder, aBuilder, &dummyAGR,
                                placeholderOverflow, ancestor,
                                aOutFramesWithProps, false)) {
        return false;
      }
    }

    // Convert 'aOverflow' into the coordinate space of the nearest stacking
    // context or display port ancestor and update 'currentFrame' to point to
    // that frame.
    aOverflow = nsLayoutUtils::TransformFrameRectToAncestor(
        currentFrame, aOverflow, aStopAtFrame, nullptr, nullptr,
        /* aStopAtStackingContextAndDisplayPortAndOOFFrame = */ true,
        &currentFrame);
    if (IsInPreserve3DContext(currentFrame)) {
      return false;
    }

    MOZ_ASSERT(currentFrame);

    // Check whether the current frame is a scrollable frame with display port.
    nsRect displayPort;
    nsIScrollableFrame* sf = do_QueryFrame(currentFrame);
    nsIContent* content = sf ? currentFrame->GetContent() : nullptr;

    if (content && DisplayPortUtils::GetDisplayPort(content, &displayPort)) {
      CRR_LOG("Frame belongs to displayport frame %p\n", currentFrame);

      // Get overflow relative to the scrollport (from the scrollframe)
      nsRect r = aOverflow - sf->GetScrollPortRect().TopLeft();
      r.IntersectRect(r, displayPort);
      if (!r.IsEmpty()) {
        nsRect* rect = currentFrame->GetProperty(
            nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
        if (!rect) {
          rect = new nsRect();
          currentFrame->SetProperty(
              nsDisplayListBuilder::DisplayListBuildingDisplayPortRect(), rect);
          currentFrame->SetHasOverrideDirtyRegion(true);
          aOutFramesWithProps.AppendElement(currentFrame);
        }
        rect->UnionRect(*rect, r);
        CRR_LOG("Adding area to displayport draw area: %d %d %d %d\n", r.x, r.y,
                r.width, r.height);

        // TODO: Can we just use MarkFrameForDisplayIfVisible, plus
        // MarkFramesForDifferentAGR to ensure that this displayport, plus any
        // items that move relative to it get rebuilt, and then not contribute
        // to the root dirty area?
        aOverflow = sf->GetScrollPortRect();
      } else {
        // Don't contribute to the root dirty area at all.
        aOverflow.SetEmpty();
      }
    } else {
      aOverflow.IntersectRect(aOverflow,
                              currentFrame->InkOverflowRectRelativeToSelf());
    }

    if (aOverflow.IsEmpty()) {
      break;
    }

    if (CanStoreDisplayListBuildingRect(aBuilder, currentFrame)) {
      CRR_LOG("Frame belongs to stacking context frame %p\n", currentFrame);
      // If we found an intermediate stacking context with an existing display
      // item then we can store the dirty rect there and stop. If we couldn't
      // find one then we need to keep bubbling up to the next stacking context.
      nsDisplayItem* wrapperItem =
          GetFirstDisplayItemWithChildren(currentFrame);
      if (!wrapperItem) {
        continue;
      }

      // Store the stacking context relative dirty area such
      // that display list building will pick it up when it
      // gets to it.
      nsDisplayListBuilder::DisplayListBuildingData* data =
          currentFrame->GetProperty(
              nsDisplayListBuilder::DisplayListBuildingRect());
      if (!data) {
        data = new nsDisplayListBuilder::DisplayListBuildingData();
        currentFrame->SetProperty(
            nsDisplayListBuilder::DisplayListBuildingRect(), data);
        currentFrame->SetHasOverrideDirtyRegion(true);
        aOutFramesWithProps.AppendElement(currentFrame);
      }
      CRR_LOG("Adding area to stacking context draw area: %d %d %d %d\n",
              aOverflow.x, aOverflow.y, aOverflow.width, aOverflow.height);
      data->mDirtyRect.UnionRect(data->mDirtyRect, aOverflow);

      if (!aStopAtStackingContext) {
        // Continue ascending the frame tree until we reach aStopAtFrame.
        continue;
      }

      // Grab the visible (display list building) rect for children of this
      // wrapper item and convert into into coordinate relative to the current
      // frame.
      nsRect previousVisible = wrapperItem->GetBuildingRectForChildren();
      if (wrapperItem->ReferenceFrameForChildren() != wrapperItem->Frame()) {
        previousVisible -= wrapperItem->ToReferenceFrame();
      }

      if (!previousVisible.Contains(aOverflow)) {
        // If the overflow area of the changed frame isn't contained within the
        // old item, then we might change the size of the item and need to
        // update its sorting accordingly. Keep propagating the overflow area up
        // so that we build intersecting items for sorting.
        continue;
      }

      if (!data->mModifiedAGR) {
        data->mModifiedAGR = *aAGR;
      } else if (data->mModifiedAGR != *aAGR) {
        data->mDirtyRect = currentFrame->InkOverflowRectRelativeToSelf();
        CRR_LOG(
            "Found multiple modified AGRs within this stacking context, "
            "giving up\n");
      }

      // Don't contribute to the root dirty area at all.
      aOverflow.SetEmpty();
      *aAGR = nullptr;

      break;
    }
  }
  return true;
}

bool RetainedDisplayListBuilder::ProcessFrame(
    nsIFrame* aFrame, nsDisplayListBuilder* aBuilder, nsIFrame* aStopAtFrame,
    nsTArray<nsIFrame*>& aOutFramesWithProps, const bool aStopAtStackingContext,
    nsRect* aOutDirty, nsIFrame** aOutModifiedAGR) {
  if (aFrame->HasOverrideDirtyRegion()) {
    aOutFramesWithProps.AppendElement(aFrame);
  }

  if (aFrame->HasAnyStateBits(NS_FRAME_IN_POPUP)) {
    return true;
  }

  // TODO: There is almost certainly a faster way of doing this, probably can be
  // combined with the ancestor walk for TransformFrameRectToAncestor.
  nsIFrame* agrFrame = aBuilder->FindAnimatedGeometryRootFrameFor(aFrame);

  CRR_LOG("Processing frame %p with agr %p\n", aFrame, agr->mFrame);

  // Convert the frame's overflow rect into the coordinate space
  // of the nearest stacking context that has an existing display item.
  // We store that as a dirty rect on that stacking context so that we build
  // all items that intersect the changed frame within the stacking context,
  // and then we use MarkFrameForDisplayIfVisible to make sure the stacking
  // context itself gets built. We don't need to build items that intersect
  // outside of the stacking context, since we know the stacking context item
  // exists in the old list, so we can trivially merge without needing other
  // items.
  nsRect overflow = aFrame->InkOverflowRectRelativeToSelf();

  // If the modified frame is also a caret frame, include the caret area.
  // This is needed because some frames (for example text frames without text)
  // might have an empty overflow rect.
  if (aFrame == aBuilder->GetCaretFrame()) {
    overflow.UnionRect(overflow, aBuilder->GetCaretRect());
  }

  if (!ProcessFrameInternal(aFrame, aBuilder, &agrFrame, overflow, aStopAtFrame,
                            aOutFramesWithProps, aStopAtStackingContext)) {
    return false;
  }

  if (!overflow.IsEmpty()) {
    aOutDirty->UnionRect(*aOutDirty, overflow);
    CRR_LOG("Adding area to root draw area: %d %d %d %d\n", overflow.x,
            overflow.y, overflow.width, overflow.height);

    // If we get changed frames from multiple AGRS, then just give up as it gets
    // really complex to track which items would need to be marked in
    // MarkFramesForDifferentAGR.
    if (!*aOutModifiedAGR) {
      CRR_LOG("Setting %p as root stacking context AGR\n", agrFrame);
      *aOutModifiedAGR = agrFrame;
    } else if (agrFrame && *aOutModifiedAGR != agrFrame) {
      CRR_LOG("Found multiple AGRs in root stacking context, giving up\n");
      return false;
    }
  }
  return true;
}

static void AddFramesForContainingBlock(nsIFrame* aBlock,
                                        const nsFrameList& aFrames,
                                        nsTArray<nsIFrame*>& aExtraFrames) {
  for (nsIFrame* f : aFrames) {
    if (!f->IsFrameModified() && AnyContentAncestorModified(f, aBlock)) {
      CRR_LOG("Adding invalid OOF %p\n", f);
      aExtraFrames.AppendElement(f);
    }
  }
}

// Placeholder descendants of aFrame don't contribute to aFrame's overflow area.
// Find all the containing blocks that might own placeholders under us, walk
// their OOF frames list, and manually invalidate any frames that are
// descendants of a modified frame (us, or another frame we'll get to soon).
// This is combined with the work required for MarkFrameForDisplayIfVisible,
// so that we can avoid an extra ancestor walk, and we can reuse the flag
// to detect when we've already visited an ancestor (and thus all further
// ancestors must also be visited).
static void FindContainingBlocks(nsIFrame* aFrame,
                                 nsTArray<nsIFrame*>& aExtraFrames) {
  for (nsIFrame* f = aFrame; f; f = nsLayoutUtils::GetDisplayListParent(f)) {
    if (f->ForceDescendIntoIfVisible()) {
      return;
    }
    f->SetForceDescendIntoIfVisible(true);
    CRR_LOG("Considering OOFs for %p\n", f);

    AddFramesForContainingBlock(f, f->GetChildList(FrameChildListID::Float),
                                aExtraFrames);
    AddFramesForContainingBlock(f, f->GetChildList(f->GetAbsoluteListID()),
                                aExtraFrames);

    // This condition must match the condition in
    // nsLayoutUtils::GetParentOrPlaceholderFor which is used by
    // nsLayoutUtils::GetDisplayListParent
    if (f->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW) && !f->GetPrevInFlow()) {
      nsIFrame* parent = f->GetParent();
      if (parent && !parent->ForceDescendIntoIfVisible()) {
        // If the GetDisplayListParent call is going to walk to a placeholder,
        // in rare cases the placeholder might be contained in a different
        // continuation from the oof. So we have to make sure to mark the oofs
        // parent. In the common case this doesn't make us do any extra work,
        // just changes the order in which we visit the frames since walking
        // through placeholders will walk through the parent, and we stop when
        // we find a ForceDescendIntoIfVisible bit set.
        FindContainingBlocks(parent, aExtraFrames);
      }
    }
  }
}

/**
 * Given a list of frames that has been modified, computes the region that we
 * need to do display list building for in order to build all modified display
 * items.
 *
 * When a modified frame is within a stacking context (with an existing display
 * item), then we only contribute to the build area within the stacking context,
 * as well as forcing display list building to descend to the stacking context.
 * We don't need to add build area outside of the stacking context (and force
 * items above/below the stacking context container item to be built), since
 * just matching the position of the stacking context container item is
 * sufficient to ensure correct ordering during merging.
 *
 * We need to rebuild all items that might intersect with the modified frame,
 * both now and during async changes on the compositor. We do this by rebuilding
 * the area covered by the changed frame, as well as rebuilding all items that
 * have a different (async) AGR to the changed frame. If we have changes to
 * multiple AGRs (within a stacking context), then we rebuild that stacking
 * context entirely.
 *
 * @param aModifiedFrames The list of modified frames.
 * @param aOutDirty The result region to use for display list building.
 * @param aOutModifiedAGR The modified AGR for the root stacking context.
 * @param aOutFramesWithProps The list of frames to which we attached partial
 * build data so that it can be cleaned up.
 *
 * @return true if we succesfully computed a partial rebuild region, false if a
 * full build is required.
 */
bool RetainedDisplayListBuilder::ComputeRebuildRegion(
    nsTArray<nsIFrame*>& aModifiedFrames, nsRect* aOutDirty,
    nsIFrame** aOutModifiedAGR, nsTArray<nsIFrame*>& aOutFramesWithProps) {
  CRR_LOG("Computing rebuild regions for %zu frames:\n",
          aModifiedFrames.Length());
  nsTArray<nsIFrame*> extraFrames;
  for (nsIFrame* f : aModifiedFrames) {
    MOZ_ASSERT(f);

    mBuilder.AddFrameMarkedForDisplayIfVisible(f);
    FindContainingBlocks(f, extraFrames);

    if (!ProcessFrame(f, &mBuilder, RootReferenceFrame(), aOutFramesWithProps,
                      true, aOutDirty, aOutModifiedAGR)) {
      return false;
    }
  }

  // Since we set modified to true on the extraFrames, add them to
  // aModifiedFrames so that it will get reverted.
  aModifiedFrames.AppendElements(extraFrames);

  for (nsIFrame* f : extraFrames) {
    f->SetFrameIsModified(true);

    if (!ProcessFrame(f, &mBuilder, RootReferenceFrame(), aOutFramesWithProps,
                      true, aOutDirty, aOutModifiedAGR)) {
      return false;
    }
  }

  return true;
}

bool RetainedDisplayListBuilder::ShouldBuildPartial(
    nsTArray<nsIFrame*>& aModifiedFrames) {
  if (mList.IsEmpty()) {
    // Partial builds without a previous display list do not make sense.
    Metrics()->mPartialUpdateFailReason = PartialUpdateFailReason::EmptyList;
    return false;
  }

  if (aModifiedFrames.Length() >
      StaticPrefs::layout_display_list_rebuild_frame_limit()) {
    // Computing a dirty rect with too many modified frames can be slow.
    Metrics()->mPartialUpdateFailReason = PartialUpdateFailReason::RebuildLimit;
    return false;
  }

  // We don't support retaining with overlay scrollbars, since they require
  // us to look at the display list and pick the highest z-index, which
  // we can't do during partial building.
  if (mBuilder.DisablePartialUpdates()) {
    mBuilder.SetDisablePartialUpdates(false);
    Metrics()->mPartialUpdateFailReason = PartialUpdateFailReason::Disabled;
    return false;
  }

  for (nsIFrame* f : aModifiedFrames) {
    MOZ_ASSERT(f);

    const LayoutFrameType type = f->Type();

    // If we have any modified frames of the following types, it is likely that
    // doing a partial rebuild of the display list will be slower than doing a
    // full rebuild.
    // This is because these frames either intersect or may intersect with most
    // of the page content. This is either due to display port size or different
    // async AGR.
    if (type == LayoutFrameType::Viewport ||
        type == LayoutFrameType::PageContent ||
        type == LayoutFrameType::Canvas || type == LayoutFrameType::Scrollbar) {
      Metrics()->mPartialUpdateFailReason = PartialUpdateFailReason::FrameType;
      return false;
    }

    // Detect root scroll frame and do a full rebuild for them too for the same
    // reasons as above, but also because top layer items should to be marked
    // modified if the root scroll frame is modified. Putting this check here
    // means we don't need to check everytime a frame is marked modified though.
    if (type == LayoutFrameType::Scroll && f->GetParent() &&
        !f->GetParent()->GetParent()) {
      Metrics()->mPartialUpdateFailReason = PartialUpdateFailReason::FrameType;
      return false;
    }
  }

  return true;
}

void RetainedDisplayListBuilder::InvalidateCaretFramesIfNeeded() {
  if (mPreviousCaret == mBuilder.GetCaretFrame()) {
    // The current caret frame is the same as the previous one.
    return;
  }

  if (mPreviousCaret) {
    mPreviousCaret->MarkNeedsDisplayItemRebuild();
  }

  if (mBuilder.GetCaretFrame()) {
    mBuilder.GetCaretFrame()->MarkNeedsDisplayItemRebuild();
  }

  mPreviousCaret = mBuilder.GetCaretFrame();
}

static void ClearFrameProps(nsTArray<nsIFrame*>& aFrames) {
  for (nsIFrame* f : aFrames) {
    DL_LOGV("RDL - Clearing modified flags for frame %p", f);
    if (f->HasOverrideDirtyRegion()) {
      f->SetHasOverrideDirtyRegion(false);
      f->RemoveProperty(nsDisplayListBuilder::DisplayListBuildingRect());
      f->RemoveProperty(
          nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
    }

    f->SetFrameIsModified(false);
    f->SetHasModifiedDescendants(false);
  }
}

class AutoClearFramePropsArray {
 public:
  explicit AutoClearFramePropsArray(size_t aCapacity) : mFrames(aCapacity) {}
  AutoClearFramePropsArray() = default;
  ~AutoClearFramePropsArray() { ClearFrameProps(mFrames); }

  nsTArray<nsIFrame*>& Frames() { return mFrames; }
  bool IsEmpty() const { return mFrames.IsEmpty(); }

 private:
  nsTArray<nsIFrame*> mFrames;
};

void RetainedDisplayListBuilder::ClearFramesWithProps() {
  AutoClearFramePropsArray modifiedFrames;
  AutoClearFramePropsArray framesWithProps;
  GetModifiedAndFramesWithProps(&modifiedFrames.Frames(),
                                &framesWithProps.Frames());
}

void RetainedDisplayListBuilder::ClearRetainedData() {
  DL_LOGI("(%p) RDL - Clearing retained display list builder data", this);
  List()->DeleteAll(Builder());
  ClearFramesWithProps();
  ClearReuseableDisplayItems();
}

namespace RDLUtils {

MOZ_NEVER_INLINE_DEBUG void AssertFrameSubtreeUnmodified(
    const nsIFrame* aFrame) {
  MOZ_ASSERT(!aFrame->IsFrameModified());
  MOZ_ASSERT(!aFrame->HasModifiedDescendants());

  for (const auto& childList : aFrame->ChildLists()) {
    for (nsIFrame* child : childList.mList) {
      AssertFrameSubtreeUnmodified(child);
    }
  }
}

MOZ_NEVER_INLINE_DEBUG void AssertDisplayListUnmodified(nsDisplayList* aList) {
  for (nsDisplayItem* item : *aList) {
    AssertDisplayItemUnmodified(item);
  }
}

MOZ_NEVER_INLINE_DEBUG void AssertDisplayItemUnmodified(nsDisplayItem* aItem) {
  MOZ_ASSERT(!aItem->HasDeletedFrame());
  MOZ_ASSERT(!AnyContentAncestorModified(aItem->FrameForInvalidation()));

  if (aItem->GetChildren()) {
    AssertDisplayListUnmodified(aItem->GetChildren());
  }
}

}  // namespace RDLUtils

namespace RDL {

void MarkAncestorFrames(nsIFrame* aFrame,
                        nsTArray<nsIFrame*>& aOutFramesWithProps) {
  nsIFrame* frame = nsLayoutUtils::GetDisplayListParent(aFrame);
  while (frame && !frame->HasModifiedDescendants()) {
    aOutFramesWithProps.AppendElement(frame);
    frame->SetHasModifiedDescendants(true);
    frame = nsLayoutUtils::GetDisplayListParent(frame);
  }
}

/**
 * Iterates over the modified frames array and updates the frame tree flags
 * so that container frames know whether they have modified descendant frames.
 * Frames that were marked modified are added to |aOutFramesWithProps|, so that
 * the modified status can be cleared after the display list build.
 */
void MarkAllAncestorFrames(const nsTArray<nsIFrame*>& aModifiedFrames,
                           nsTArray<nsIFrame*>& aOutFramesWithProps) {
  nsAutoString frameName;
  DL_LOGI("RDL - Modified frames: %zu", aModifiedFrames.Length());
  for (nsIFrame* frame : aModifiedFrames) {
#ifdef DEBUG
    frame->GetFrameName(frameName);
#endif
    DL_LOGV("RDL - Processing modified frame: %p (%s)", frame,
            NS_ConvertUTF16toUTF8(frameName).get());

    MarkAncestorFrames(frame, aOutFramesWithProps);
  }
}

/**
 * Marks the given display item |aItem| as reuseable container, and updates the
 * bounds in case some child items were destroyed.
 */
MOZ_NEVER_INLINE_DEBUG void ReuseStackingContextItem(
    nsDisplayListBuilder* aBuilder, nsDisplayItem* aItem) {
  aItem->SetPreProcessed();

  if (aItem->HasChildren()) {
    aItem->UpdateBounds(aBuilder);
  }

  aBuilder->AddReusableDisplayItem(aItem);
  DL_LOGD("Reusing display item %p", aItem);
}

bool IsSupportedFrameType(const nsIFrame* aFrame) {
  // The way table backgrounds are handled makes these frames incompatible with
  // this retained display list approach.
  if (aFrame->IsTableColFrame()) {
    return false;
  }

  if (aFrame->IsTableColGroupFrame()) {
    return false;
  }

  if (aFrame->IsTableRowFrame()) {
    return false;
  }

  if (aFrame->IsTableRowGroupFrame()) {
    return false;
  }

  if (aFrame->IsTableCellFrame()) {
    return false;
  }

  // Everything else should work.
  return true;
}

bool IsReuseableStackingContextItem(nsDisplayItem* aItem) {
  if (!IsSupportedFrameType(aItem->Frame())) {
    return false;
  }

  if (!aItem->IsReusable()) {
    return false;
  }

  const nsIFrame* frame = aItem->FrameForInvalidation();
  return !frame->HasModifiedDescendants() && !frame->GetPrevContinuation() &&
         !frame->GetNextContinuation();
}

/**
 * Recursively visits every display item of the display list and destroys all
 * display items that depend on deleted or modified frames.
 * The stacking context display items for unmodified frame subtrees are kept
 * linked and collected in given |aOutItems| array.
 */
void CollectStackingContextItems(nsDisplayListBuilder* aBuilder,
                                 nsDisplayList* aList, nsIFrame* aOuterFrame,
                                 int aDepth = 0, bool aParentReused = false) {
  for (nsDisplayItem* item : aList->TakeItems()) {
    if (DL_LOG_TEST(LogLevel::Debug)) {
      DL_LOGD(
          "%*s Preprocessing item %p (%s) (frame: %p) "
          "(children: %zu) (depth: %d) (parentReused: %d)",
          aDepth, "", item, item->Name(),
          item->HasDeletedFrame() ? nullptr : item->Frame(),
          item->GetChildren() ? item->GetChildren()->Length() : 0, aDepth,
          aParentReused);
    }

    if (!item->CanBeReused() || item->HasDeletedFrame() ||
        AnyContentAncestorModified(item->FrameForInvalidation(), aOuterFrame)) {
      DL_LOGD("%*s Deleted modified or temporary item %p", aDepth, "", item);
      item->Destroy(aBuilder);
      continue;
    }

    MOZ_ASSERT(!AnyContentAncestorModified(item->FrameForInvalidation()));
    MOZ_ASSERT(!item->IsPreProcessed());
    item->InvalidateCachedChildInfo(aBuilder);
#ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
    item->SetMergedPreProcessed(false, true);
#endif
    item->SetReused(true);

    const bool isStackingContextItem = IsReuseableStackingContextItem(item);

    if (item->GetChildren()) {
      CollectStackingContextItems(aBuilder, item->GetChildren(), item->Frame(),
                                  aDepth + 1,
                                  aParentReused || isStackingContextItem);
    }

    if (aParentReused) {
      // Keep the contents of the current container item linked.
#ifdef DEBUG
      RDLUtils::AssertDisplayItemUnmodified(item);
#endif
      aList->AppendToTop(item);
    } else if (isStackingContextItem) {
      // |item| is a stacking context item that can be reused.
      ReuseStackingContextItem(aBuilder, item);
    } else {
      // |item| is inside a container item that will be destroyed later.
      DL_LOGD("%*s Deleted unused item %p", aDepth, "", item);
      item->Destroy(aBuilder);
      continue;
    }

    if (item->GetType() == DisplayItemType::TYPE_SUBDOCUMENT) {
      IncrementPresShellPaintCount(aBuilder, item);
    }
  }
}

}  // namespace RDL

bool RetainedDisplayListBuilder::TrySimpleUpdate(
    const nsTArray<nsIFrame*>& aModifiedFrames,
    nsTArray<nsIFrame*>& aOutFramesWithProps) {
  if (!mBuilder.IsReusingStackingContextItems()) {
    return false;
  }

  RDL::MarkAllAncestorFrames(aModifiedFrames, aOutFramesWithProps);
  RDL::CollectStackingContextItems(&mBuilder, &mList, RootReferenceFrame());

  return true;
}

PartialUpdateResult RetainedDisplayListBuilder::AttemptPartialUpdate(
    nscolor aBackstop) {
  DL_LOGI("(%p) RDL - AttemptPartialUpdate, root frame: %p", this,
          RootReferenceFrame());

  mBuilder.RemoveModifiedWindowRegions();

  if (mBuilder.ShouldSyncDecodeImages()) {
    DL_LOGI("RDL - Sync decoding images");
    MarkFramesWithItemsAndImagesModified(&mList);
  }

  InvalidateCaretFramesIfNeeded();

  // We set the override dirty regions during ComputeRebuildRegion or in
  // DisplayPortUtils::InvalidateForDisplayPortChange. The display port change
  // also marks the frame modified, so those regions are cleared here as well.
  AutoClearFramePropsArray modifiedFrames(64);
  AutoClearFramePropsArray framesWithProps(64);
  GetModifiedAndFramesWithProps(&modifiedFrames.Frames(),
                                &framesWithProps.Frames());

  if (!ShouldBuildPartial(modifiedFrames.Frames())) {
    // Do not allow partial builds if the |ShouldBuildPartial()| heuristic
    // fails.
    mBuilder.SetPartialBuildFailed(true);
    return PartialUpdateResult::Failed;
  }

  nsRect modifiedDirty;
  nsDisplayList modifiedDL(&mBuilder);
  nsIFrame* modifiedAGR = nullptr;
  PartialUpdateResult result = PartialUpdateResult::NoChange;
  const bool simpleUpdate =
      TrySimpleUpdate(modifiedFrames.Frames(), framesWithProps.Frames());

  mBuilder.EnterPresShell(RootReferenceFrame());

  if (!simpleUpdate) {
    if (!ComputeRebuildRegion(modifiedFrames.Frames(), &modifiedDirty,
                              &modifiedAGR, framesWithProps.Frames()) ||
        !PreProcessDisplayList(&mList, modifiedAGR, result,
                               RootReferenceFrame(), nullptr)) {
      DL_LOGI("RDL - Partial update aborted");
      mBuilder.SetPartialBuildFailed(true);
      mBuilder.LeavePresShell(RootReferenceFrame(), nullptr);
      mList.DeleteAll(&mBuilder);
      return PartialUpdateResult::Failed;
    }
  } else {
    modifiedDirty = mBuilder.GetVisibleRect();
  }

  // This is normally handled by EnterPresShell, but we skipped it so that we
  // didn't call MarkFrameForDisplayIfVisible before ComputeRebuildRegion.
  nsIScrollableFrame* sf =
      RootReferenceFrame()->PresShell()->GetRootScrollFrameAsScrollable();
  if (sf) {
    nsCanvasFrame* canvasFrame = do_QueryFrame(sf->GetScrolledFrame());
    if (canvasFrame) {
      mBuilder.MarkFrameForDisplayIfVisible(canvasFrame, RootReferenceFrame());
    }
  }

  nsRect rootOverflow = RootOverflowRect();
  modifiedDirty.IntersectRect(modifiedDirty, rootOverflow);

  mBuilder.SetDirtyRect(modifiedDirty);
  mBuilder.SetPartialUpdate(true);
  mBuilder.SetPartialBuildFailed(false);

  DL_LOGI("RDL - Starting display list build");
  RootReferenceFrame()->BuildDisplayListForStackingContext(&mBuilder,
                                                           &modifiedDL);
  DL_LOGI("RDL - Finished display list build");

  if (!modifiedDL.IsEmpty()) {
    nsLayoutUtils::AddExtraBackgroundItems(
        &mBuilder, &modifiedDL, RootReferenceFrame(),
        nsRect(nsPoint(0, 0), rootOverflow.Size()), rootOverflow, aBackstop);
  }
  mBuilder.SetPartialUpdate(false);

  if (mBuilder.PartialBuildFailed()) {
    DL_LOGI("RDL - Partial update failed!");
    mBuilder.LeavePresShell(RootReferenceFrame(), nullptr);
    mBuilder.ClearReuseableDisplayItems();
    mList.DeleteAll(&mBuilder);
    modifiedDL.DeleteAll(&mBuilder);
    Metrics()->mPartialUpdateFailReason = PartialUpdateFailReason::Content;
    return PartialUpdateResult::Failed;
  }

  // printf_stderr("Painting --- Modified list (dirty %d,%d,%d,%d):\n",
  //              modifiedDirty.x, modifiedDirty.y, modifiedDirty.width,
  //              modifiedDirty.height);
  // nsIFrame::PrintDisplayList(&mBuilder, modifiedDL);

  // |modifiedDL| can sometimes be empty here. We still perform the
  // display list merging to prune unused items (for example, items that
  // are not visible anymore) from the old list.
  // TODO: Optimization opportunity. In this case, MergeDisplayLists()
  // unnecessarily creates a hashtable of the old items.
  // TODO: Ideally we could skip this if result is NoChange, but currently when
  // we call RestoreState on nsDisplayWrapList it resets the clip to the base
  // clip, and we need the UpdateBounds call (within MergeDisplayLists) to
  // move it to the correct inner clip.
  if (!simpleUpdate) {
    Maybe<const ActiveScrolledRoot*> dummy;
    if (MergeDisplayLists(&modifiedDL, &mList, &mList, dummy)) {
      result = PartialUpdateResult::Updated;
    }
  } else {
    MOZ_ASSERT(mList.IsEmpty());
    mList = std::move(modifiedDL);
    mBuilder.ClearReuseableDisplayItems();
    result = PartialUpdateResult::Updated;
  }

#if 0
  if (DL_LOG_TEST(LogLevel::Verbose)) {
    printf_stderr("Painting --- Display list:\n");
    nsIFrame::PrintDisplayList(&mBuilder, mList);
  }
#endif

  mBuilder.LeavePresShell(RootReferenceFrame(), List());
  return result;
}

nsRect RetainedDisplayListBuilder::RootOverflowRect() const {
  const nsIFrame* rootReferenceFrame = RootReferenceFrame();
  nsRect rootOverflowRect = rootReferenceFrame->InkOverflowRectRelativeToSelf();
  const nsPresContext* presContext = rootReferenceFrame->PresContext();
  if (!rootReferenceFrame->GetParent() &&
      presContext->IsRootContentDocumentCrossProcess() &&
      presContext->HasDynamicToolbar()) {
    rootOverflowRect.SizeTo(nsLayoutUtils::ExpandHeightForDynamicToolbar(
        presContext, rootOverflowRect.Size()));
  }

  return rootOverflowRect;
}

}  // namespace mozilla