diff options
Diffstat (limited to 'layout/painting/RetainedDisplayListBuilder.cpp')
| -rw-r--r-- | layout/painting/RetainedDisplayListBuilder.cpp | 1702 |
1 files changed, 1702 insertions, 0 deletions
diff --git a/layout/painting/RetainedDisplayListBuilder.cpp b/layout/painting/RetainedDisplayListBuilder.cpp new file mode 100644 index 0000000000..2834213789 --- /dev/null +++ b/layout/painting/RetainedDisplayListBuilder.cpp @@ -0,0 +1,1702 @@ +/* -*- 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, + ¤tFrame); + 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); + } +} + +/** + * 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()); + } + } + + modifiedDirty.IntersectRect( + modifiedDirty, RootReferenceFrame()->InkOverflowRectRelativeToSelf()); + + 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), RootReferenceFrame()->GetSize()), + RootReferenceFrame()->InkOverflowRectRelativeToSelf(), 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; +} + +} // namespace mozilla |