1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 #include "RetainedDisplayListBuilder.h"
10 #include "mozilla/Attributes.h"
11 #include "mozilla/StaticPrefs_layout.h"
13 #include "nsIFrameInlines.h"
14 #include "nsIScrollableFrame.h"
15 #include "nsPlaceholderFrame.h"
16 #include "nsSubDocumentFrame.h"
17 #include "nsViewManager.h"
18 #include "nsCanvasFrame.h"
19 #include "mozilla/AutoRestore.h"
20 #include "mozilla/DisplayPortUtils.h"
21 #include "mozilla/PresShell.h"
22 #include "mozilla/ProfilerLabels.h"
25 * Code for doing display list building for a modified subset of the window,
26 * and then merging it into the existing display list (for the full window).
28 * The approach primarily hinges on the observation that the 'true' ordering
29 * of display items is represented by a DAG (only items that intersect in 2d
30 * space have a defined ordering). Our display list is just one of a many
31 * possible linear representations of this ordering.
33 * Each time a frame changes (gets a new ComputedStyle, or has a size/position
34 * change), we schedule a paint (as we do currently), but also reord the frame
37 * When the next paint occurs we union the overflow areas (in screen space) of
38 * the changed frames, and compute a rect/region that contains all changed
39 * items. We then build a display list just for this subset of the screen and
40 * merge it into the display list from last paint.
42 * Any items that exist in one list and not the other must not have a defined
43 * ordering in the DAG, since they need to intersect to have an ordering and
44 * we would have built both in the new list if they intersected. Given that, we
45 * can align items that appear in both lists, and any items that appear between
46 * matched items can be inserted into the merged list in any order.
48 * Frames that are a stacking context, containing blocks for position:fixed
49 * descendants, and don't have any continuations (see
50 * CanStoreDisplayListBuildingRect) trigger recursion into the algorithm with
51 * separate retaining decisions made.
53 * RDL defines the concept of an AnimatedGeometryRoot (AGR), the nearest
54 * ancestor frame which can be moved asynchronously on the compositor thread.
55 * These are currently nsDisplayItems which return true from CanMoveAsync
56 * (animated nsDisplayTransform and nsDisplayStickyPosition) and
57 * ActiveScrolledRoots.
59 * For each context that we run the retaining algorithm, there can only be
60 * mutations to one AnimatedGeometryRoot. This is because we are unable to
61 * reason about intersections of items that might then move relative to each
62 * other without RDL running again. If there are mutations to multiple
63 * AnimatedGeometryRoots, then we bail out and rebuild all the items in the
66 * Otherwise, when mutations are restricted to a single AGR, we pre-process the
67 * old display list and mark the frames for all existing (unmodified!) items
68 * that belong to a different AGR and ensure that we rebuild those items for
69 * correct sorting with the modified ones.
74 RetainedDisplayListData::RetainedDisplayListData()
75 : mModifiedFrameLimit(
76 StaticPrefs::layout_display_list_rebuild_frame_limit()) {}
78 void RetainedDisplayListData::AddModifiedFrame(nsIFrame
* aFrame
) {
79 MOZ_ASSERT(!aFrame
->IsFrameModified());
80 Flags(aFrame
) += RetainedDisplayListData::FrameFlag::Modified
;
81 aFrame
->SetFrameIsModified(true);
82 mModifiedFrameCount
++;
85 static void MarkFramesWithItemsAndImagesModified(nsDisplayList
* aList
) {
86 for (nsDisplayItem
* i
: *aList
) {
87 if (!i
->HasDeletedFrame() && i
->CanBeReused() &&
88 !i
->Frame()->IsFrameModified()) {
89 // If we have existing cached geometry for this item, then check that for
90 // whether we need to invalidate for a sync decode. If we don't, then
91 // use the item's flags.
92 // XXX: handle webrender case by looking up retained data for the item
93 // and checking InvalidateForSyncDecodeImages
94 bool invalidate
= false;
95 if (!(i
->GetFlags() & TYPE_RENDERS_NO_IMAGES
)) {
100 DL_LOGV("RDL - Invalidating item %p (%s)", i
, i
->Name());
101 i
->FrameForInvalidation()->MarkNeedsDisplayItemRebuild();
102 if (i
->GetDependentFrame()) {
103 i
->GetDependentFrame()->MarkNeedsDisplayItemRebuild();
107 if (i
->GetChildren()) {
108 MarkFramesWithItemsAndImagesModified(i
->GetChildren());
113 static nsIFrame
* SelectAGRForFrame(nsIFrame
* aFrame
, nsIFrame
* aParentAGR
) {
114 if (!aFrame
->IsStackingContext() || !aFrame
->IsFixedPosContainingBlock()) {
118 if (!aFrame
->HasOverrideDirtyRegion()) {
122 nsDisplayListBuilder::DisplayListBuildingData
* data
=
123 aFrame
->GetProperty(nsDisplayListBuilder::DisplayListBuildingRect());
125 return data
&& data
->mModifiedAGR
? data
->mModifiedAGR
: nullptr;
128 void RetainedDisplayListBuilder::AddSizeOfIncludingThis(
129 nsWindowSizes
& aSizes
) const {
130 aSizes
.mLayoutRetainedDisplayListSize
+= aSizes
.mState
.mMallocSizeOf(this);
131 mBuilder
.AddSizeOfExcludingThis(aSizes
);
132 mList
.AddSizeOfExcludingThis(aSizes
);
135 bool AnyContentAncestorModified(nsIFrame
* aFrame
, nsIFrame
* aStopAtFrame
) {
136 nsIFrame
* f
= aFrame
;
138 if (f
->IsFrameModified()) {
142 if (aStopAtFrame
&& f
== aStopAtFrame
) {
146 f
= nsLayoutUtils::GetDisplayListParent(f
);
152 // Removes any display items that belonged to a frame that was deleted,
153 // and mark frames that belong to a different AGR so that get their
154 // items built again.
155 // TODO: We currently descend into all children even if we don't have an AGR
156 // to mark, as child stacking contexts might. It would be nice if we could
157 // jump into those immediately rather than walking the entire thing.
158 bool RetainedDisplayListBuilder::PreProcessDisplayList(
159 RetainedDisplayList
* aList
, nsIFrame
* aAGR
, PartialUpdateResult
& aUpdated
,
160 nsIFrame
* aAsyncAncestor
, const ActiveScrolledRoot
* aAsyncAncestorASR
,
161 nsIFrame
* aOuterFrame
, uint32_t aCallerKey
, uint32_t aNestingDepth
,
163 // The DAG merging algorithm does not have strong mechanisms in place to keep
164 // the complexity of the resulting DAG under control. In some cases we can
165 // build up edges very quickly. Detect those cases and force a full display
166 // list build if we hit them.
167 static const uint32_t kMaxEdgeRatio
= 5;
168 const bool initializeDAG
= !aList
->mDAG
.Length();
169 if (!aKeepLinked
&& !initializeDAG
&&
170 aList
->mDAG
.mDirectPredecessorList
.Length() >
171 (aList
->mDAG
.mNodesInfo
.Length() * kMaxEdgeRatio
)) {
175 // If we had aKeepLinked=true for this list on the previous paint, then
176 // mOldItems will already be initialized as it won't have been consumed during
178 const bool initializeOldItems
= aList
->mOldItems
.IsEmpty();
179 if (initializeOldItems
) {
180 aList
->mOldItems
.SetCapacity(aList
->Length());
182 MOZ_RELEASE_ASSERT(!initializeDAG
);
187 aList
->mDAG
.Length() ==
188 (initializeOldItems
? aList
->Length() : aList
->mOldItems
.Length()));
190 nsDisplayList
out(Builder());
193 while (nsDisplayItem
* item
= aList
->RemoveBottom()) {
194 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
195 item
->SetMergedPreProcessed(false, true);
198 // If we have a previously initialized old items list, then it can differ
199 // from the current list due to items removed for having a deleted frame.
200 // We can't easily remove these, since the DAG has entries for those indices
201 // and it's hard to rewrite in-place.
202 // Skip over entries with no current item to keep the iterations in sync.
203 if (!initializeOldItems
) {
204 while (!aList
->mOldItems
[i
].mItem
) {
211 aList
->mDAG
.AddNode(Span
<const MergedListIndex
>());
213 MergedListIndex
previous(i
- 1);
214 aList
->mDAG
.AddNode(Span
<const MergedListIndex
>(&previous
, 1));
218 if (!item
->CanBeReused() || item
->HasDeletedFrame() ||
219 AnyContentAncestorModified(item
->FrameForInvalidation(), aOuterFrame
)) {
220 if (initializeOldItems
) {
221 aList
->mOldItems
.AppendElement(OldItemInfo(nullptr));
223 MOZ_RELEASE_ASSERT(aList
->mOldItems
[i
].mItem
== item
);
224 aList
->mOldItems
[i
].mItem
= nullptr;
227 item
->Destroy(&mBuilder
);
228 Metrics()->mRemovedItems
++;
231 aUpdated
= PartialUpdateResult::Updated
;
235 if (initializeOldItems
) {
236 aList
->mOldItems
.AppendElement(OldItemInfo(item
));
239 // If we're not going to keep the list linked, then this old item entry
240 // is the only pointer to the item. Let it know that it now strongly
241 // owns the item, so it can destroy it if it goes away.
242 aList
->mOldItems
[i
].mOwnsItem
= !aKeepLinked
;
244 item
->SetOldListIndex(aList
, OldListIndex(i
), aCallerKey
, aNestingDepth
);
246 nsIFrame
* f
= item
->Frame();
248 if (item
->GetChildren()) {
249 // If children inside this list were invalid, then we'd have walked the
250 // ancestors and set ForceDescendIntoVisible on the current frame. If an
251 // ancestor is modified, then we'll throw this away entirely. Either way,
252 // we won't need to run merging on this sublist, and we can keep the items
253 // linked into their display list.
254 // The caret can move without invalidating, but we always set the force
255 // descend into frame state bit on that frame, so check for that too.
256 // TODO: AGR marking below can call MarkFrameForDisplayIfVisible and make
257 // us think future siblings need to be merged, even though we don't really
259 bool keepLinked
= aKeepLinked
;
260 nsIFrame
* invalid
= item
->FrameForInvalidation();
261 if (!invalid
->ForceDescendIntoIfVisible() &&
262 !invalid
->HasAnyStateBits(NS_FRAME_FORCE_DISPLAY_LIST_DESCEND_INTO
)) {
266 // If this item's frame is an AGR (can be moved asynchronously by the
267 // compositor), then use that frame for descendants. Also pass the ASR
268 // for that item, so that descendants can compare to see if any new
269 // ASRs have been pushed since.
270 nsIFrame
* asyncAncestor
= aAsyncAncestor
;
271 const ActiveScrolledRoot
* asyncAncestorASR
= aAsyncAncestorASR
;
272 if (item
->CanMoveAsync()) {
273 asyncAncestor
= item
->Frame();
274 asyncAncestorASR
= item
->GetActiveScrolledRoot();
277 if (!PreProcessDisplayList(
278 item
->GetChildren(), SelectAGRForFrame(f
, aAGR
), aUpdated
,
279 asyncAncestor
, asyncAncestorASR
, item
->Frame(),
280 item
->GetPerFrameKey(), aNestingDepth
+ 1, keepLinked
)) {
283 "Can't early return since we need to move the out list back");
288 // TODO: We should be able to check the clipped bounds relative
289 // to the common AGR (of both the existing item and the invalidated
290 // frame) and determine if they can ever intersect.
291 // TODO: We only really need to build the ancestor container item that is a
292 // sibling of the changed thing to get correct ordering. The changed content
293 // is a frame though, and it's hard to map that to container items in this
295 // If an ancestor display item is an AGR, and our ASR matches the ASR
296 // of that item, then there can't have been any new ASRs pushed since that
297 // item, so that item is our AGR. Otherwise, our AGR is our ASR.
298 // TODO: If aAsyncAncestorASR is non-null, then item->GetActiveScrolledRoot
299 // should be the same or a descendant and also non-null. Unfortunately an
300 // RDL bug means this can be wrong for sticky items after a partial update,
301 // so we have to work around it. Bug 1730749 and bug 1730826 should resolve
303 nsIFrame
* agrFrame
= nullptr;
304 if (aAsyncAncestorASR
== item
->GetActiveScrolledRoot() ||
305 !item
->GetActiveScrolledRoot()) {
306 agrFrame
= aAsyncAncestor
;
309 item
->GetActiveScrolledRoot()->mScrollableFrame
->GetScrolledFrame();
312 if (aAGR
&& agrFrame
!= aAGR
) {
313 mBuilder
.MarkFrameForDisplayIfVisible(f
, RootReferenceFrame());
316 // If we're going to keep this linked list and not merge it, then mark the
317 // item as used and put it back into the list.
319 item
->SetReused(true);
320 if (item
->GetChildren()) {
321 item
->UpdateBounds(Builder());
323 if (item
->GetType() == DisplayItemType::TYPE_SUBDOCUMENT
) {
324 IncrementSubDocPresShellPaintCount(item
);
326 out
.AppendToTop(item
);
331 MOZ_RELEASE_ASSERT(aList
->mOldItems
.Length() == aList
->mDAG
.Length());
334 aList
->AppendToTop(&out
);
340 void IncrementPresShellPaintCount(nsDisplayListBuilder
* aBuilder
,
341 nsDisplayItem
* aItem
) {
342 MOZ_ASSERT(aItem
->GetType() == DisplayItemType::TYPE_SUBDOCUMENT
);
344 nsSubDocumentFrame
* subDocFrame
=
345 static_cast<nsDisplaySubDocument
*>(aItem
)->SubDocumentFrame();
346 MOZ_ASSERT(subDocFrame
);
348 PresShell
* presShell
= subDocFrame
->GetSubdocumentPresShellForPainting(0);
349 MOZ_ASSERT(presShell
);
351 aBuilder
->IncrementPresShellPaintCount(presShell
);
354 void RetainedDisplayListBuilder::IncrementSubDocPresShellPaintCount(
355 nsDisplayItem
* aItem
) {
356 IncrementPresShellPaintCount(&mBuilder
, aItem
);
359 static Maybe
<const ActiveScrolledRoot
*> SelectContainerASR(
360 const DisplayItemClipChain
* aClipChain
, const ActiveScrolledRoot
* aItemASR
,
361 Maybe
<const ActiveScrolledRoot
*>& aContainerASR
) {
362 const ActiveScrolledRoot
* itemClipASR
=
363 aClipChain
? aClipChain
->mASR
: nullptr;
365 MOZ_DIAGNOSTIC_ASSERT(!aClipChain
|| aClipChain
->mOnStack
|| !itemClipASR
||
366 itemClipASR
->mScrollableFrame
);
368 const ActiveScrolledRoot
* finiteBoundsASR
=
369 ActiveScrolledRoot::PickDescendant(itemClipASR
, aItemASR
);
371 if (!aContainerASR
) {
372 return Some(finiteBoundsASR
);
376 ActiveScrolledRoot::PickAncestor(*aContainerASR
, finiteBoundsASR
));
379 static void UpdateASR(nsDisplayItem
* aItem
,
380 Maybe
<const ActiveScrolledRoot
*>& aContainerASR
) {
381 if (!aContainerASR
) {
385 nsDisplayWrapList
* wrapList
= aItem
->AsDisplayWrapList();
387 aItem
->SetActiveScrolledRoot(*aContainerASR
);
391 wrapList
->SetActiveScrolledRoot(ActiveScrolledRoot::PickAncestor(
392 wrapList
->GetFrameActiveScrolledRoot(), *aContainerASR
));
395 static void CopyASR(nsDisplayItem
* aOld
, nsDisplayItem
* aNew
) {
396 aNew
->SetActiveScrolledRoot(aOld
->GetActiveScrolledRoot());
399 OldItemInfo::OldItemInfo(nsDisplayItem
* aItem
)
400 : mItem(aItem
), mUsed(false), mDiscarded(false), mOwnsItem(false) {
402 // Clear cached modified frame state when adding an item to the old list.
403 mItem
->SetModifiedFrame(false);
407 void OldItemInfo::AddedMatchToMergedList(RetainedDisplayListBuilder
* aBuilder
,
408 MergedListIndex aIndex
) {
409 AddedToMergedList(aIndex
);
412 void OldItemInfo::Discard(RetainedDisplayListBuilder
* aBuilder
,
413 nsTArray
<MergedListIndex
>&& aDirectPredecessors
) {
414 MOZ_ASSERT(!IsUsed());
415 mUsed
= mDiscarded
= true;
416 mDirectPredecessors
= std::move(aDirectPredecessors
);
418 MOZ_ASSERT(mOwnsItem
);
419 mItem
->Destroy(aBuilder
->Builder());
420 aBuilder
->Metrics()->mRemovedItems
++;
425 bool OldItemInfo::IsChanged() {
426 return !mItem
|| !mItem
->CanBeReused() || mItem
->HasDeletedFrame();
430 * A C++ implementation of Markus Stange's merge-dags algorithm.
431 * https://github.com/mstange/merge-dags
433 * MergeState handles combining a new list of display items into an existing
434 * DAG and computes the new DAG in a single pass.
435 * Each time we add a new item, we resolve all dependencies for it, so that the
436 * resulting list and DAG are built in topological ordering.
440 MergeState(RetainedDisplayListBuilder
* aBuilder
,
441 RetainedDisplayList
& aOldList
, nsDisplayItem
* aOuterItem
)
442 : mBuilder(aBuilder
),
444 mOldItems(std::move(aOldList
.mOldItems
)),
446 std::move(*reinterpret_cast<DirectedAcyclicGraph
<OldListUnits
>*>(
448 mMergedItems(aBuilder
->Builder()),
449 mOuterItem(aOuterItem
),
450 mResultIsModified(false) {
451 mMergedDAG
.EnsureCapacityFor(mOldDAG
);
452 MOZ_RELEASE_ASSERT(mOldItems
.Length() == mOldDAG
.Length());
455 Maybe
<MergedListIndex
> ProcessItemFromNewList(
456 nsDisplayItem
* aNewItem
, const Maybe
<MergedListIndex
>& aPreviousItem
) {
457 OldListIndex oldIndex
;
458 MOZ_DIAGNOSTIC_ASSERT(aNewItem
->HasModifiedFrame() ==
459 HasModifiedFrame(aNewItem
));
460 if (!aNewItem
->HasModifiedFrame() &&
461 HasMatchingItemInOldList(aNewItem
, &oldIndex
)) {
462 mBuilder
->Metrics()->mRebuiltItems
++;
463 nsDisplayItem
* oldItem
= mOldItems
[oldIndex
.val
].mItem
;
464 MOZ_DIAGNOSTIC_ASSERT(oldItem
->GetPerFrameKey() ==
465 aNewItem
->GetPerFrameKey() &&
466 oldItem
->Frame() == aNewItem
->Frame());
467 if (!mOldItems
[oldIndex
.val
].IsChanged()) {
468 MOZ_DIAGNOSTIC_ASSERT(!mOldItems
[oldIndex
.val
].IsUsed());
469 nsDisplayItem
* destItem
;
470 if (ShouldUseNewItem(aNewItem
)) {
474 // The building rect can depend on the overflow rect (when the parent
475 // frame is position:fixed), which can change without invalidating
476 // the frame/items. If we're using the old item, copy the building
477 // rect across from the new item.
478 oldItem
->SetBuildingRect(aNewItem
->GetBuildingRect());
481 MergeChildLists(aNewItem
, oldItem
, destItem
);
483 AutoTArray
<MergedListIndex
, 2> directPredecessors
=
484 ProcessPredecessorsOfOldNode(oldIndex
);
485 MergedListIndex newIndex
= AddNewNode(
486 destItem
, Some(oldIndex
), directPredecessors
, aPreviousItem
);
487 mOldItems
[oldIndex
.val
].AddedMatchToMergedList(mBuilder
, newIndex
);
488 if (destItem
== aNewItem
) {
489 oldItem
->Destroy(mBuilder
->Builder());
491 aNewItem
->Destroy(mBuilder
->Builder());
493 return Some(newIndex
);
496 mResultIsModified
= true;
497 return Some(AddNewNode(aNewItem
, Nothing(), Span
<MergedListIndex
>(),
501 void MergeChildLists(nsDisplayItem
* aNewItem
, nsDisplayItem
* aOldItem
,
502 nsDisplayItem
* aOutItem
) {
503 if (!aOutItem
->GetChildren()) {
507 Maybe
<const ActiveScrolledRoot
*> containerASRForChildren
;
508 nsDisplayList
empty(mBuilder
->Builder());
509 const bool modified
= mBuilder
->MergeDisplayLists(
510 aNewItem
? aNewItem
->GetChildren() : &empty
, aOldItem
->GetChildren(),
511 aOutItem
->GetChildren(), containerASRForChildren
, aOutItem
);
513 aOutItem
->InvalidateCachedChildInfo(mBuilder
->Builder());
514 UpdateASR(aOutItem
, containerASRForChildren
);
515 mResultIsModified
= true;
516 } else if (aOutItem
== aNewItem
) {
517 // If nothing changed, but we copied the contents across to
518 // the new item, then also copy the ASR data.
519 CopyASR(aOldItem
, aNewItem
);
521 // Ideally we'd only UpdateBounds if something changed, but
522 // nsDisplayWrapList also uses this to update the clip chain for the
523 // current ASR, which gets reset during RestoreState(), so we always need
525 aOutItem
->UpdateBounds(mBuilder
->Builder());
528 bool ShouldUseNewItem(nsDisplayItem
* aNewItem
) {
529 // Generally we want to use the old item when the frame isn't marked as
530 // modified so that any cached information on the item (or referencing the
531 // item) gets retained. Quite a few FrameLayerBuilder performance
532 // improvements benefit by this. Sometimes, however, we can end up where the
533 // new item paints something different from the old item, even though we
534 // haven't modified the frame, and it's hard to fix. In these cases we just
535 // always use the new item to be safe.
536 DisplayItemType type
= aNewItem
->GetType();
537 if (type
== DisplayItemType::TYPE_CANVAS_BACKGROUND_COLOR
||
538 type
== DisplayItemType::TYPE_SOLID_COLOR
) {
539 // The canvas background color item can paint the color from another
540 // frame, and even though we schedule a paint, we don't mark the canvas
545 if (type
== DisplayItemType::TYPE_TABLE_BORDER_COLLAPSE
) {
546 // We intentionally don't mark the root table frame as modified when a
547 // subframe changes, even though the border collapse item for the root
548 // frame is what paints the changed border. Marking the root frame as
549 // modified would rebuild display items for the whole table area, and we
554 if (type
== DisplayItemType::TYPE_TEXT_OVERFLOW
) {
555 // Text overflow marker items are created with the wrapping block as their
556 // frame, and have an index value to note which line they are created for.
557 // Their rendering can change if the items on that line change, which may
558 // not mark the block as modified. We rebuild them if we build any item on
559 // the line, so we should always get new items if they might have changed
560 // rendering, and it's easier to just use the new items rather than
561 // computing if we actually need them.
565 if (type
== DisplayItemType::TYPE_SUBDOCUMENT
||
566 type
== DisplayItemType::TYPE_STICKY_POSITION
) {
567 // nsDisplaySubDocument::mShouldFlatten can change without an invalidation
568 // (and is the reason we unconditionally build the subdocument item), so
569 // always use the new one to make sure we get the right value.
570 // Same for |nsDisplayStickyPosition::mShouldFlatten|.
574 if (type
== DisplayItemType::TYPE_CARET
) {
575 // The caret can change position while still being owned by the same frame
576 // and we don't invalidate in that case. Use the new version since the
577 // changed bounds are needed for DLBI.
581 if (type
== DisplayItemType::TYPE_MASK
||
582 type
== DisplayItemType::TYPE_FILTER
||
583 type
== DisplayItemType::TYPE_SVG_WRAPPER
) {
584 // SVG items have some invalidation issues, see bugs 1494110 and 1494663.
588 if (type
== DisplayItemType::TYPE_TRANSFORM
) {
589 // Prerendering of transforms can change without frame invalidation.
596 RetainedDisplayList
Finalize() {
597 for (size_t i
= 0; i
< mOldDAG
.Length(); i
++) {
598 if (mOldItems
[i
].IsUsed()) {
602 AutoTArray
<MergedListIndex
, 2> directPredecessors
=
603 ResolveNodeIndexesOldToMerged(
604 mOldDAG
.GetDirectPredecessors(OldListIndex(i
)));
605 ProcessOldNode(OldListIndex(i
), std::move(directPredecessors
));
608 RetainedDisplayList
result(mBuilder
->Builder());
609 result
.AppendToTop(&mMergedItems
);
610 result
.mDAG
= std::move(mMergedDAG
);
611 MOZ_RELEASE_ASSERT(result
.mDAG
.Length() == result
.Length());
615 bool HasMatchingItemInOldList(nsDisplayItem
* aItem
, OldListIndex
* aOutIndex
) {
616 // Look for an item that matches aItem's frame and per-frame-key, but isn't
618 uint32_t outerKey
= mOuterItem
? mOuterItem
->GetPerFrameKey() : 0;
619 nsIFrame
* frame
= aItem
->Frame();
620 for (nsDisplayItem
* i
: frame
->DisplayItems()) {
621 if (i
!= aItem
&& i
->Frame() == frame
&&
622 i
->GetPerFrameKey() == aItem
->GetPerFrameKey()) {
623 if (i
->GetOldListIndex(mOldList
, outerKey
, aOutIndex
)) {
631 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
632 bool HasModifiedFrame(nsDisplayItem
* aItem
) {
633 nsIFrame
* stopFrame
= mOuterItem
? mOuterItem
->Frame() : nullptr;
634 return AnyContentAncestorModified(aItem
->FrameForInvalidation(), stopFrame
);
638 void UpdateContainerASR(nsDisplayItem
* aItem
) {
639 mContainerASR
= SelectContainerASR(
640 aItem
->GetClipChain(), aItem
->GetActiveScrolledRoot(), mContainerASR
);
643 MergedListIndex
AddNewNode(
644 nsDisplayItem
* aItem
, const Maybe
<OldListIndex
>& aOldIndex
,
645 Span
<const MergedListIndex
> aDirectPredecessors
,
646 const Maybe
<MergedListIndex
>& aExtraDirectPredecessor
) {
647 UpdateContainerASR(aItem
);
648 aItem
->NotifyUsed(mBuilder
->Builder());
650 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
651 for (nsDisplayItem
* i
: aItem
->Frame()->DisplayItems()) {
652 if (i
->Frame() == aItem
->Frame() &&
653 i
->GetPerFrameKey() == aItem
->GetPerFrameKey()) {
654 MOZ_DIAGNOSTIC_ASSERT(!i
->IsMergedItem());
658 aItem
->SetMergedPreProcessed(true, false);
661 mMergedItems
.AppendToTop(aItem
);
662 mBuilder
->Metrics()->mTotalItems
++;
664 MergedListIndex newIndex
=
665 mMergedDAG
.AddNode(aDirectPredecessors
, aExtraDirectPredecessor
);
669 void ProcessOldNode(OldListIndex aNode
,
670 nsTArray
<MergedListIndex
>&& aDirectPredecessors
) {
671 nsDisplayItem
* item
= mOldItems
[aNode
.val
].mItem
;
672 if (mOldItems
[aNode
.val
].IsChanged()) {
673 mOldItems
[aNode
.val
].Discard(mBuilder
, std::move(aDirectPredecessors
));
674 mResultIsModified
= true;
676 MergeChildLists(nullptr, item
, item
);
678 if (item
->GetType() == DisplayItemType::TYPE_SUBDOCUMENT
) {
679 mBuilder
->IncrementSubDocPresShellPaintCount(item
);
681 item
->SetReused(true);
682 mBuilder
->Metrics()->mReusedItems
++;
683 mOldItems
[aNode
.val
].AddedToMergedList(
684 AddNewNode(item
, Some(aNode
), aDirectPredecessors
, Nothing()));
688 struct PredecessorStackItem
{
689 PredecessorStackItem(OldListIndex aNode
, Span
<OldListIndex
> aPredecessors
)
691 mDirectPredecessors(aPredecessors
),
692 mCurrentPredecessorIndex(0) {}
695 return mCurrentPredecessorIndex
== mDirectPredecessors
.Length();
698 OldListIndex
GetAndIncrementCurrentPredecessor() {
699 return mDirectPredecessors
[mCurrentPredecessorIndex
++];
703 Span
<OldListIndex
> mDirectPredecessors
;
704 size_t mCurrentPredecessorIndex
;
707 AutoTArray
<MergedListIndex
, 2> ProcessPredecessorsOfOldNode(
708 OldListIndex aNode
) {
709 AutoTArray
<PredecessorStackItem
, 256> mStack
;
710 mStack
.AppendElement(
711 PredecessorStackItem(aNode
, mOldDAG
.GetDirectPredecessors(aNode
)));
714 if (mStack
.LastElement().IsFinished()) {
715 // If we've finished processing all the entries in the current set, then
716 // pop it off the processing stack and process it.
717 PredecessorStackItem item
= mStack
.PopLastElement();
718 AutoTArray
<MergedListIndex
, 2> result
=
719 ResolveNodeIndexesOldToMerged(item
.mDirectPredecessors
);
721 if (mStack
.IsEmpty()) {
725 ProcessOldNode(item
.mNode
, std::move(result
));
727 // Grab the current predecessor, push predecessors of that onto the
728 // processing stack (if it hasn't already been processed), and then
729 // advance to the next entry.
730 OldListIndex currentIndex
=
731 mStack
.LastElement().GetAndIncrementCurrentPredecessor();
732 if (!mOldItems
[currentIndex
.val
].IsUsed()) {
733 mStack
.AppendElement(PredecessorStackItem(
734 currentIndex
, mOldDAG
.GetDirectPredecessors(currentIndex
)));
740 AutoTArray
<MergedListIndex
, 2> ResolveNodeIndexesOldToMerged(
741 Span
<OldListIndex
> aDirectPredecessors
) {
742 AutoTArray
<MergedListIndex
, 2> result
;
743 result
.SetCapacity(aDirectPredecessors
.Length());
744 for (OldListIndex index
: aDirectPredecessors
) {
745 OldItemInfo
& oldItem
= mOldItems
[index
.val
];
746 if (oldItem
.IsDiscarded()) {
747 for (MergedListIndex inner
: oldItem
.mDirectPredecessors
) {
748 if (!result
.Contains(inner
)) {
749 result
.AppendElement(inner
);
753 result
.AppendElement(oldItem
.mIndex
);
759 RetainedDisplayListBuilder
* mBuilder
;
760 RetainedDisplayList
* mOldList
;
761 Maybe
<const ActiveScrolledRoot
*> mContainerASR
;
762 nsTArray
<OldItemInfo
> mOldItems
;
763 DirectedAcyclicGraph
<OldListUnits
> mOldDAG
;
764 // Unfortunately we can't use strong typing for the hashtables
765 // since they internally encode the type with the mOps pointer,
766 // and assert when we try swap the contents
767 nsDisplayList mMergedItems
;
768 DirectedAcyclicGraph
<MergedListUnits
> mMergedDAG
;
769 nsDisplayItem
* mOuterItem
;
770 bool mResultIsModified
;
774 void VerifyNotModified(nsDisplayList
* aList
) {
775 for (nsDisplayItem
* item
: *aList
) {
776 MOZ_ASSERT(!AnyContentAncestorModified(item
->FrameForInvalidation()));
778 if (item
->GetChildren()) {
779 VerifyNotModified(item
->GetChildren());
786 * Takes two display lists and merges them into an output list.
788 * Display lists wthout an explicit DAG are interpreted as linear DAGs (with a
789 * maximum of one direct predecessor and one direct successor per node). We add
790 * the two DAGs together, and then output the topological sorted ordering as the
791 * final display list.
793 * Once we've merged a list, we then retain the DAG (as part of the
794 * RetainedDisplayList object) to use for future merges.
796 bool RetainedDisplayListBuilder::MergeDisplayLists(
797 nsDisplayList
* aNewList
, RetainedDisplayList
* aOldList
,
798 RetainedDisplayList
* aOutList
,
799 mozilla::Maybe
<const mozilla::ActiveScrolledRoot
*>& aOutContainerASR
,
800 nsDisplayItem
* aOuterItem
) {
801 AUTO_PROFILER_LABEL_CATEGORY_PAIR(GRAPHICS_DisplayListMerging
);
803 if (!aOldList
->IsEmpty()) {
804 // If we still have items in the actual list, then it is because
805 // PreProcessDisplayList decided that it was sure it can't be modified. We
806 // can just use it directly, and throw any new items away.
808 aNewList
->DeleteAll(&mBuilder
);
810 VerifyNotModified(aOldList
);
813 if (aOldList
!= aOutList
) {
814 *aOutList
= std::move(*aOldList
);
820 MergeState
merge(this, *aOldList
, aOuterItem
);
822 Maybe
<MergedListIndex
> previousItemIndex
;
823 for (nsDisplayItem
* item
: aNewList
->TakeItems()) {
824 Metrics()->mNewItems
++;
825 previousItemIndex
= merge
.ProcessItemFromNewList(item
, previousItemIndex
);
828 *aOutList
= merge
.Finalize();
829 aOutContainerASR
= merge
.mContainerASR
;
830 return merge
.mResultIsModified
;
833 void RetainedDisplayListBuilder::GetModifiedAndFramesWithProps(
834 nsTArray
<nsIFrame
*>* aOutModifiedFrames
,
835 nsTArray
<nsIFrame
*>* aOutFramesWithProps
) {
836 for (auto it
= Data()->ConstIterator(); !it
.Done(); it
.Next()) {
837 nsIFrame
* frame
= it
.Key();
838 const RetainedDisplayListData::FrameFlags
& flags
= it
.Data();
840 if (flags
.contains(RetainedDisplayListData::FrameFlag::Modified
)) {
841 aOutModifiedFrames
->AppendElement(frame
);
844 if (flags
.contains(RetainedDisplayListData::FrameFlag::HasProps
)) {
845 aOutFramesWithProps
->AppendElement(frame
);
848 if (flags
.contains(RetainedDisplayListData::FrameFlag::HadWillChange
)) {
849 Builder()->RemoveFromWillChangeBudgets(frame
);
856 // ComputeRebuildRegion debugging
857 // #define CRR_DEBUG 1
859 # define CRR_LOG(...) printf_stderr(__VA_ARGS__)
861 # define CRR_LOG(...)
864 static nsDisplayItem
* GetFirstDisplayItemWithChildren(nsIFrame
* aFrame
) {
865 for (nsDisplayItem
* i
: aFrame
->DisplayItems()) {
866 if (i
->HasDeletedFrame() || i
->Frame() != aFrame
) {
867 // The main frame for the display item has been deleted or the display
868 // item belongs to another frame.
872 if (i
->HasChildren()) {
873 return static_cast<nsDisplayItem
*>(i
);
879 static bool IsInPreserve3DContext(const nsIFrame
* aFrame
) {
880 return aFrame
->Extend3DContext() ||
881 aFrame
->Combines3DTransformWithAncestors();
884 // Returns true if |aFrame| can store a display list building rect.
885 // These limitations are necessary to guarantee that
886 // 1) Just enough items are rebuilt to properly update display list
887 // 2) Modified frames will be visited during a partial display list build.
888 static bool CanStoreDisplayListBuildingRect(nsDisplayListBuilder
* aBuilder
,
890 return aFrame
!= aBuilder
->RootReferenceFrame() &&
891 aFrame
->IsStackingContext() && aFrame
->IsFixedPosContainingBlock() &&
892 // Split frames might have placeholders for modified frames in their
893 // unmodified continuation frame.
894 !aFrame
->GetPrevContinuation() && !aFrame
->GetNextContinuation();
897 static bool ProcessFrameInternal(nsIFrame
* aFrame
,
898 nsDisplayListBuilder
* aBuilder
,
899 nsIFrame
** aAGR
, nsRect
& aOverflow
,
900 const nsIFrame
* aStopAtFrame
,
901 nsTArray
<nsIFrame
*>& aOutFramesWithProps
,
902 const bool aStopAtStackingContext
) {
903 nsIFrame
* currentFrame
= aFrame
;
905 while (currentFrame
!= aStopAtFrame
) {
906 CRR_LOG("currentFrame: %p (placeholder=%d), aOverflow: %d %d %d %d\n",
907 currentFrame
, !aStopAtStackingContext
, aOverflow
.x
, aOverflow
.y
,
908 aOverflow
.width
, aOverflow
.height
);
910 // If the current frame is an OOF frame, DisplayListBuildingData needs to be
911 // set on all the ancestor stacking contexts of the placeholder frame, up
912 // to the containing block of the OOF frame. This is done to ensure that the
913 // content that might be behind the OOF frame is built for merging.
914 nsIFrame
* placeholder
= currentFrame
->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW
)
915 ? currentFrame
->GetPlaceholderFrame()
919 nsRect placeholderOverflow
= aOverflow
;
920 auto rv
= nsLayoutUtils::TransformRect(currentFrame
, placeholder
,
921 placeholderOverflow
);
922 if (rv
!= nsLayoutUtils::TRANSFORM_SUCCEEDED
) {
923 placeholderOverflow
= nsRect();
926 CRR_LOG("Processing placeholder %p for OOF frame %p\n", placeholder
,
929 CRR_LOG("OOF frame draw area: %d %d %d %d\n", placeholderOverflow
.x
,
930 placeholderOverflow
.y
, placeholderOverflow
.width
,
931 placeholderOverflow
.height
);
933 // Tracking AGRs for the placeholder processing is not necessary, as the
934 // goal is to only modify the DisplayListBuildingData rect.
935 nsIFrame
* dummyAGR
= nullptr;
937 // Find a common ancestor frame to handle frame continuations.
938 // TODO: It might be possible to write a more specific and efficient
939 // function for this.
940 const nsIFrame
* ancestor
= nsLayoutUtils::FindNearestCommonAncestorFrame(
941 currentFrame
->GetParent(), placeholder
->GetParent());
943 if (!ProcessFrameInternal(placeholder
, aBuilder
, &dummyAGR
,
944 placeholderOverflow
, ancestor
,
945 aOutFramesWithProps
, false)) {
950 // Convert 'aOverflow' into the coordinate space of the nearest stacking
951 // context or display port ancestor and update 'currentFrame' to point to
953 aOverflow
= nsLayoutUtils::TransformFrameRectToAncestor(
954 currentFrame
, aOverflow
, aStopAtFrame
, nullptr, nullptr,
955 /* aStopAtStackingContextAndDisplayPortAndOOFFrame = */ true,
957 if (IsInPreserve3DContext(currentFrame
)) {
961 MOZ_ASSERT(currentFrame
);
963 // Check whether the current frame is a scrollable frame with display port.
965 nsIScrollableFrame
* sf
= do_QueryFrame(currentFrame
);
966 nsIContent
* content
= sf
? currentFrame
->GetContent() : nullptr;
968 if (content
&& DisplayPortUtils::GetDisplayPort(content
, &displayPort
)) {
969 CRR_LOG("Frame belongs to displayport frame %p\n", currentFrame
);
971 // Get overflow relative to the scrollport (from the scrollframe)
972 nsRect r
= aOverflow
- sf
->GetScrollPortRect().TopLeft();
973 r
.IntersectRect(r
, displayPort
);
975 nsRect
* rect
= currentFrame
->GetProperty(
976 nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
979 currentFrame
->SetProperty(
980 nsDisplayListBuilder::DisplayListBuildingDisplayPortRect(), rect
);
981 currentFrame
->SetHasOverrideDirtyRegion(true);
982 aOutFramesWithProps
.AppendElement(currentFrame
);
984 rect
->UnionRect(*rect
, r
);
985 CRR_LOG("Adding area to displayport draw area: %d %d %d %d\n", r
.x
, r
.y
,
988 // TODO: Can we just use MarkFrameForDisplayIfVisible, plus
989 // MarkFramesForDifferentAGR to ensure that this displayport, plus any
990 // items that move relative to it get rebuilt, and then not contribute
991 // to the root dirty area?
992 aOverflow
= sf
->GetScrollPortRect();
994 // Don't contribute to the root dirty area at all.
995 aOverflow
.SetEmpty();
998 aOverflow
.IntersectRect(aOverflow
,
999 currentFrame
->InkOverflowRectRelativeToSelf());
1002 if (aOverflow
.IsEmpty()) {
1006 if (CanStoreDisplayListBuildingRect(aBuilder
, currentFrame
)) {
1007 CRR_LOG("Frame belongs to stacking context frame %p\n", currentFrame
);
1008 // If we found an intermediate stacking context with an existing display
1009 // item then we can store the dirty rect there and stop. If we couldn't
1010 // find one then we need to keep bubbling up to the next stacking context.
1011 nsDisplayItem
* wrapperItem
=
1012 GetFirstDisplayItemWithChildren(currentFrame
);
1017 // Store the stacking context relative dirty area such
1018 // that display list building will pick it up when it
1020 nsDisplayListBuilder::DisplayListBuildingData
* data
=
1021 currentFrame
->GetProperty(
1022 nsDisplayListBuilder::DisplayListBuildingRect());
1024 data
= new nsDisplayListBuilder::DisplayListBuildingData();
1025 currentFrame
->SetProperty(
1026 nsDisplayListBuilder::DisplayListBuildingRect(), data
);
1027 currentFrame
->SetHasOverrideDirtyRegion(true);
1028 aOutFramesWithProps
.AppendElement(currentFrame
);
1030 CRR_LOG("Adding area to stacking context draw area: %d %d %d %d\n",
1031 aOverflow
.x
, aOverflow
.y
, aOverflow
.width
, aOverflow
.height
);
1032 data
->mDirtyRect
.UnionRect(data
->mDirtyRect
, aOverflow
);
1034 if (!aStopAtStackingContext
) {
1035 // Continue ascending the frame tree until we reach aStopAtFrame.
1039 // Grab the visible (display list building) rect for children of this
1040 // wrapper item and convert into into coordinate relative to the current
1042 nsRect previousVisible
= wrapperItem
->GetBuildingRectForChildren();
1043 if (wrapperItem
->ReferenceFrameForChildren() != wrapperItem
->Frame()) {
1044 previousVisible
-= wrapperItem
->ToReferenceFrame();
1047 if (!previousVisible
.Contains(aOverflow
)) {
1048 // If the overflow area of the changed frame isn't contained within the
1049 // old item, then we might change the size of the item and need to
1050 // update its sorting accordingly. Keep propagating the overflow area up
1051 // so that we build intersecting items for sorting.
1055 if (!data
->mModifiedAGR
) {
1056 data
->mModifiedAGR
= *aAGR
;
1057 } else if (data
->mModifiedAGR
!= *aAGR
) {
1058 data
->mDirtyRect
= currentFrame
->InkOverflowRectRelativeToSelf();
1060 "Found multiple modified AGRs within this stacking context, "
1064 // Don't contribute to the root dirty area at all.
1065 aOverflow
.SetEmpty();
1074 bool RetainedDisplayListBuilder::ProcessFrame(
1075 nsIFrame
* aFrame
, nsDisplayListBuilder
* aBuilder
, nsIFrame
* aStopAtFrame
,
1076 nsTArray
<nsIFrame
*>& aOutFramesWithProps
, const bool aStopAtStackingContext
,
1077 nsRect
* aOutDirty
, nsIFrame
** aOutModifiedAGR
) {
1078 if (aFrame
->HasOverrideDirtyRegion()) {
1079 aOutFramesWithProps
.AppendElement(aFrame
);
1082 if (aFrame
->HasAnyStateBits(NS_FRAME_IN_POPUP
)) {
1086 // TODO: There is almost certainly a faster way of doing this, probably can be
1087 // combined with the ancestor walk for TransformFrameRectToAncestor.
1088 nsIFrame
* agrFrame
= aBuilder
->FindAnimatedGeometryRootFrameFor(aFrame
);
1090 CRR_LOG("Processing frame %p with agr %p\n", aFrame
, agr
->mFrame
);
1092 // Convert the frame's overflow rect into the coordinate space
1093 // of the nearest stacking context that has an existing display item.
1094 // We store that as a dirty rect on that stacking context so that we build
1095 // all items that intersect the changed frame within the stacking context,
1096 // and then we use MarkFrameForDisplayIfVisible to make sure the stacking
1097 // context itself gets built. We don't need to build items that intersect
1098 // outside of the stacking context, since we know the stacking context item
1099 // exists in the old list, so we can trivially merge without needing other
1101 nsRect overflow
= aFrame
->InkOverflowRectRelativeToSelf();
1103 // If the modified frame is also a caret frame, include the caret area.
1104 // This is needed because some frames (for example text frames without text)
1105 // might have an empty overflow rect.
1106 if (aFrame
== aBuilder
->GetCaretFrame()) {
1107 overflow
.UnionRect(overflow
, aBuilder
->GetCaretRect());
1110 if (!ProcessFrameInternal(aFrame
, aBuilder
, &agrFrame
, overflow
, aStopAtFrame
,
1111 aOutFramesWithProps
, aStopAtStackingContext
)) {
1115 if (!overflow
.IsEmpty()) {
1116 aOutDirty
->UnionRect(*aOutDirty
, overflow
);
1117 CRR_LOG("Adding area to root draw area: %d %d %d %d\n", overflow
.x
,
1118 overflow
.y
, overflow
.width
, overflow
.height
);
1120 // If we get changed frames from multiple AGRS, then just give up as it gets
1121 // really complex to track which items would need to be marked in
1122 // MarkFramesForDifferentAGR.
1123 if (!*aOutModifiedAGR
) {
1124 CRR_LOG("Setting %p as root stacking context AGR\n", agrFrame
);
1125 *aOutModifiedAGR
= agrFrame
;
1126 } else if (agrFrame
&& *aOutModifiedAGR
!= agrFrame
) {
1127 CRR_LOG("Found multiple AGRs in root stacking context, giving up\n");
1134 static void AddFramesForContainingBlock(nsIFrame
* aBlock
,
1135 const nsFrameList
& aFrames
,
1136 nsTArray
<nsIFrame
*>& aExtraFrames
) {
1137 for (nsIFrame
* f
: aFrames
) {
1138 if (!f
->IsFrameModified() && AnyContentAncestorModified(f
, aBlock
)) {
1139 CRR_LOG("Adding invalid OOF %p\n", f
);
1140 aExtraFrames
.AppendElement(f
);
1145 // Placeholder descendants of aFrame don't contribute to aFrame's overflow area.
1146 // Find all the containing blocks that might own placeholders under us, walk
1147 // their OOF frames list, and manually invalidate any frames that are
1148 // descendants of a modified frame (us, or another frame we'll get to soon).
1149 // This is combined with the work required for MarkFrameForDisplayIfVisible,
1150 // so that we can avoid an extra ancestor walk, and we can reuse the flag
1151 // to detect when we've already visited an ancestor (and thus all further
1152 // ancestors must also be visited).
1153 static void FindContainingBlocks(nsIFrame
* aFrame
,
1154 nsTArray
<nsIFrame
*>& aExtraFrames
) {
1155 for (nsIFrame
* f
= aFrame
; f
; f
= nsLayoutUtils::GetDisplayListParent(f
)) {
1156 if (f
->ForceDescendIntoIfVisible()) {
1159 f
->SetForceDescendIntoIfVisible(true);
1160 CRR_LOG("Considering OOFs for %p\n", f
);
1162 AddFramesForContainingBlock(f
, f
->GetChildList(FrameChildListID::Float
),
1164 AddFramesForContainingBlock(f
, f
->GetChildList(f
->GetAbsoluteListID()),
1167 // This condition must match the condition in
1168 // nsLayoutUtils::GetParentOrPlaceholderFor which is used by
1169 // nsLayoutUtils::GetDisplayListParent
1170 if (f
->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW
) && !f
->GetPrevInFlow()) {
1171 nsIFrame
* parent
= f
->GetParent();
1172 if (parent
&& !parent
->ForceDescendIntoIfVisible()) {
1173 // If the GetDisplayListParent call is going to walk to a placeholder,
1174 // in rare cases the placeholder might be contained in a different
1175 // continuation from the oof. So we have to make sure to mark the oofs
1176 // parent. In the common case this doesn't make us do any extra work,
1177 // just changes the order in which we visit the frames since walking
1178 // through placeholders will walk through the parent, and we stop when
1179 // we find a ForceDescendIntoIfVisible bit set.
1180 FindContainingBlocks(parent
, aExtraFrames
);
1187 * Given a list of frames that has been modified, computes the region that we
1188 * need to do display list building for in order to build all modified display
1191 * When a modified frame is within a stacking context (with an existing display
1192 * item), then we only contribute to the build area within the stacking context,
1193 * as well as forcing display list building to descend to the stacking context.
1194 * We don't need to add build area outside of the stacking context (and force
1195 * items above/below the stacking context container item to be built), since
1196 * just matching the position of the stacking context container item is
1197 * sufficient to ensure correct ordering during merging.
1199 * We need to rebuild all items that might intersect with the modified frame,
1200 * both now and during async changes on the compositor. We do this by rebuilding
1201 * the area covered by the changed frame, as well as rebuilding all items that
1202 * have a different (async) AGR to the changed frame. If we have changes to
1203 * multiple AGRs (within a stacking context), then we rebuild that stacking
1206 * @param aModifiedFrames The list of modified frames.
1207 * @param aOutDirty The result region to use for display list building.
1208 * @param aOutModifiedAGR The modified AGR for the root stacking context.
1209 * @param aOutFramesWithProps The list of frames to which we attached partial
1210 * build data so that it can be cleaned up.
1212 * @return true if we succesfully computed a partial rebuild region, false if a
1213 * full build is required.
1215 bool RetainedDisplayListBuilder::ComputeRebuildRegion(
1216 nsTArray
<nsIFrame
*>& aModifiedFrames
, nsRect
* aOutDirty
,
1217 nsIFrame
** aOutModifiedAGR
, nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1218 CRR_LOG("Computing rebuild regions for %zu frames:\n",
1219 aModifiedFrames
.Length());
1220 nsTArray
<nsIFrame
*> extraFrames
;
1221 for (nsIFrame
* f
: aModifiedFrames
) {
1224 mBuilder
.AddFrameMarkedForDisplayIfVisible(f
);
1225 FindContainingBlocks(f
, extraFrames
);
1227 if (!ProcessFrame(f
, &mBuilder
, RootReferenceFrame(), aOutFramesWithProps
,
1228 true, aOutDirty
, aOutModifiedAGR
)) {
1233 // Since we set modified to true on the extraFrames, add them to
1234 // aModifiedFrames so that it will get reverted.
1235 aModifiedFrames
.AppendElements(extraFrames
);
1237 for (nsIFrame
* f
: extraFrames
) {
1238 f
->SetFrameIsModified(true);
1240 if (!ProcessFrame(f
, &mBuilder
, RootReferenceFrame(), aOutFramesWithProps
,
1241 true, aOutDirty
, aOutModifiedAGR
)) {
1249 bool RetainedDisplayListBuilder::ShouldBuildPartial(
1250 nsTArray
<nsIFrame
*>& aModifiedFrames
) {
1251 if (mList
.IsEmpty()) {
1252 // Partial builds without a previous display list do not make sense.
1253 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::EmptyList
;
1257 if (aModifiedFrames
.Length() >
1258 StaticPrefs::layout_display_list_rebuild_frame_limit()) {
1259 // Computing a dirty rect with too many modified frames can be slow.
1260 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::RebuildLimit
;
1264 // We don't support retaining with overlay scrollbars, since they require
1265 // us to look at the display list and pick the highest z-index, which
1266 // we can't do during partial building.
1267 if (mBuilder
.DisablePartialUpdates()) {
1268 mBuilder
.SetDisablePartialUpdates(false);
1269 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::Disabled
;
1273 for (nsIFrame
* f
: aModifiedFrames
) {
1276 const LayoutFrameType type
= f
->Type();
1278 // If we have any modified frames of the following types, it is likely that
1279 // doing a partial rebuild of the display list will be slower than doing a
1281 // This is because these frames either intersect or may intersect with most
1282 // of the page content. This is either due to display port size or different
1284 if (type
== LayoutFrameType::Viewport
||
1285 type
== LayoutFrameType::PageContent
||
1286 type
== LayoutFrameType::Canvas
|| type
== LayoutFrameType::Scrollbar
) {
1287 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::FrameType
;
1291 // Detect root scroll frame and do a full rebuild for them too for the same
1292 // reasons as above, but also because top layer items should to be marked
1293 // modified if the root scroll frame is modified. Putting this check here
1294 // means we don't need to check everytime a frame is marked modified though.
1295 if (type
== LayoutFrameType::Scroll
&& f
->GetParent() &&
1296 !f
->GetParent()->GetParent()) {
1297 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::FrameType
;
1305 void RetainedDisplayListBuilder::InvalidateCaretFramesIfNeeded() {
1306 if (mPreviousCaret
== mBuilder
.GetCaretFrame()) {
1307 // The current caret frame is the same as the previous one.
1311 if (mPreviousCaret
) {
1312 mPreviousCaret
->MarkNeedsDisplayItemRebuild();
1315 if (mBuilder
.GetCaretFrame()) {
1316 mBuilder
.GetCaretFrame()->MarkNeedsDisplayItemRebuild();
1319 mPreviousCaret
= mBuilder
.GetCaretFrame();
1322 class AutoClearFramePropsArray
{
1324 explicit AutoClearFramePropsArray(size_t aCapacity
) : mFrames(aCapacity
) {}
1325 AutoClearFramePropsArray() = default;
1326 ~AutoClearFramePropsArray() {
1327 size_t len
= mFrames
.Length();
1328 nsIFrame
** elements
= mFrames
.Elements();
1329 for (size_t i
= 0; i
< len
; ++i
) {
1330 nsIFrame
* f
= elements
[i
];
1331 DL_LOGV("RDL - Clearing modified flags for frame %p", f
);
1332 if (f
->HasOverrideDirtyRegion()) {
1333 f
->SetHasOverrideDirtyRegion(false);
1334 f
->RemoveProperty(nsDisplayListBuilder::DisplayListBuildingRect());
1336 nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
1338 f
->SetFrameIsModified(false);
1339 f
->SetHasModifiedDescendants(false);
1343 nsTArray
<nsIFrame
*>& Frames() { return mFrames
; }
1344 bool IsEmpty() const { return mFrames
.IsEmpty(); }
1347 nsTArray
<nsIFrame
*> mFrames
;
1350 void RetainedDisplayListBuilder::ClearFramesWithProps() {
1351 AutoClearFramePropsArray modifiedFrames
;
1352 AutoClearFramePropsArray framesWithProps
;
1353 GetModifiedAndFramesWithProps(&modifiedFrames
.Frames(),
1354 &framesWithProps
.Frames());
1357 void RetainedDisplayListBuilder::ClearRetainedData() {
1358 DL_LOGI("(%p) RDL - Clearing retained display list builder data", this);
1359 List()->DeleteAll(Builder());
1360 ClearFramesWithProps();
1361 ClearReuseableDisplayItems();
1364 namespace RDLUtils
{
1366 MOZ_NEVER_INLINE_DEBUG
void AssertFrameSubtreeUnmodified(
1367 const nsIFrame
* aFrame
) {
1368 MOZ_ASSERT(!aFrame
->IsFrameModified());
1369 MOZ_ASSERT(!aFrame
->HasModifiedDescendants());
1371 for (const auto& childList
: aFrame
->ChildLists()) {
1372 for (nsIFrame
* child
: childList
.mList
) {
1373 AssertFrameSubtreeUnmodified(child
);
1378 MOZ_NEVER_INLINE_DEBUG
void AssertDisplayListUnmodified(nsDisplayList
* aList
) {
1379 for (nsDisplayItem
* item
: *aList
) {
1380 AssertDisplayItemUnmodified(item
);
1384 MOZ_NEVER_INLINE_DEBUG
void AssertDisplayItemUnmodified(nsDisplayItem
* aItem
) {
1385 MOZ_ASSERT(!aItem
->HasDeletedFrame());
1386 MOZ_ASSERT(!AnyContentAncestorModified(aItem
->FrameForInvalidation()));
1388 if (aItem
->GetChildren()) {
1389 AssertDisplayListUnmodified(aItem
->GetChildren());
1393 } // namespace RDLUtils
1397 void MarkAncestorFrames(nsIFrame
* aFrame
,
1398 nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1399 nsIFrame
* frame
= nsLayoutUtils::GetDisplayListParent(aFrame
);
1400 while (frame
&& !frame
->HasModifiedDescendants()) {
1401 aOutFramesWithProps
.AppendElement(frame
);
1402 frame
->SetHasModifiedDescendants(true);
1403 frame
= nsLayoutUtils::GetDisplayListParent(frame
);
1408 * Iterates over the modified frames array and updates the frame tree flags
1409 * so that container frames know whether they have modified descendant frames.
1410 * Frames that were marked modified are added to |aOutFramesWithProps|, so that
1411 * the modified status can be cleared after the display list build.
1413 void MarkAllAncestorFrames(const nsTArray
<nsIFrame
*>& aModifiedFrames
,
1414 nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1415 nsAutoString frameName
;
1416 DL_LOGI("RDL - Modified frames: %zu", aModifiedFrames
.Length());
1417 for (nsIFrame
* frame
: aModifiedFrames
) {
1419 frame
->GetFrameName(frameName
);
1421 DL_LOGV("RDL - Processing modified frame: %p (%s)", frame
,
1422 NS_ConvertUTF16toUTF8(frameName
).get());
1424 MarkAncestorFrames(frame
, aOutFramesWithProps
);
1429 * Marks the given display item |aItem| as reuseable container, and updates the
1430 * bounds in case some child items were destroyed.
1432 MOZ_NEVER_INLINE_DEBUG
void ReuseStackingContextItem(
1433 nsDisplayListBuilder
* aBuilder
, nsDisplayItem
* aItem
) {
1434 aItem
->SetPreProcessed();
1436 if (aItem
->HasChildren()) {
1437 aItem
->UpdateBounds(aBuilder
);
1440 aBuilder
->AddReusableDisplayItem(aItem
);
1441 DL_LOGD("Reusing display item %p", aItem
);
1444 bool IsSupportedFrameType(const nsIFrame
* aFrame
) {
1445 // The way table backgrounds are handled makes these frames incompatible with
1446 // this retained display list approach.
1447 if (aFrame
->IsTableColFrame()) {
1451 if (aFrame
->IsTableColGroupFrame()) {
1455 if (aFrame
->IsTableRowFrame()) {
1459 if (aFrame
->IsTableRowGroupFrame()) {
1463 if (aFrame
->IsTableCellFrame()) {
1467 // Everything else should work.
1471 bool IsReuseableStackingContextItem(nsDisplayItem
* aItem
) {
1472 if (!IsSupportedFrameType(aItem
->Frame())) {
1476 if (!aItem
->IsReusable()) {
1480 const nsIFrame
* frame
= aItem
->FrameForInvalidation();
1481 return !frame
->HasModifiedDescendants() && !frame
->GetPrevContinuation() &&
1482 !frame
->GetNextContinuation();
1486 * Recursively visits every display item of the display list and destroys all
1487 * display items that depend on deleted or modified frames.
1488 * The stacking context display items for unmodified frame subtrees are kept
1489 * linked and collected in given |aOutItems| array.
1491 void CollectStackingContextItems(nsDisplayListBuilder
* aBuilder
,
1492 nsDisplayList
* aList
, nsIFrame
* aOuterFrame
,
1493 int aDepth
= 0, bool aParentReused
= false) {
1494 for (nsDisplayItem
* item
: aList
->TakeItems()) {
1495 if (DL_LOG_TEST(LogLevel::Debug
)) {
1497 "%*s Preprocessing item %p (%s) (frame: %p) "
1498 "(children: %zu) (depth: %d) (parentReused: %d)",
1499 aDepth
, "", item
, item
->Name(),
1500 item
->HasDeletedFrame() ? nullptr : item
->Frame(),
1501 item
->GetChildren() ? item
->GetChildren()->Length() : 0, aDepth
,
1505 if (!item
->CanBeReused() || item
->HasDeletedFrame() ||
1506 AnyContentAncestorModified(item
->FrameForInvalidation(), aOuterFrame
)) {
1507 DL_LOGD("%*s Deleted modified or temporary item %p", aDepth
, "", item
);
1508 item
->Destroy(aBuilder
);
1512 MOZ_ASSERT(!AnyContentAncestorModified(item
->FrameForInvalidation()));
1513 MOZ_ASSERT(!item
->IsPreProcessed());
1514 item
->InvalidateCachedChildInfo(aBuilder
);
1515 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
1516 item
->SetMergedPreProcessed(false, true);
1518 item
->SetReused(true);
1520 const bool isStackingContextItem
= IsReuseableStackingContextItem(item
);
1522 if (item
->GetChildren()) {
1523 CollectStackingContextItems(aBuilder
, item
->GetChildren(), item
->Frame(),
1525 aParentReused
|| isStackingContextItem
);
1528 if (aParentReused
) {
1529 // Keep the contents of the current container item linked.
1531 RDLUtils::AssertDisplayItemUnmodified(item
);
1533 aList
->AppendToTop(item
);
1534 } else if (isStackingContextItem
) {
1535 // |item| is a stacking context item that can be reused.
1536 ReuseStackingContextItem(aBuilder
, item
);
1538 // |item| is inside a container item that will be destroyed later.
1539 DL_LOGD("%*s Deleted unused item %p", aDepth
, "", item
);
1540 item
->Destroy(aBuilder
);
1544 if (item
->GetType() == DisplayItemType::TYPE_SUBDOCUMENT
) {
1545 IncrementPresShellPaintCount(aBuilder
, item
);
1552 bool RetainedDisplayListBuilder::TrySimpleUpdate(
1553 const nsTArray
<nsIFrame
*>& aModifiedFrames
,
1554 nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1555 if (!mBuilder
.IsReusingStackingContextItems()) {
1559 RDL::MarkAllAncestorFrames(aModifiedFrames
, aOutFramesWithProps
);
1560 RDL::CollectStackingContextItems(&mBuilder
, &mList
, RootReferenceFrame());
1565 PartialUpdateResult
RetainedDisplayListBuilder::AttemptPartialUpdate(
1566 nscolor aBackstop
) {
1567 DL_LOGI("(%p) RDL - AttemptPartialUpdate, root frame: %p", this,
1568 RootReferenceFrame());
1570 mBuilder
.RemoveModifiedWindowRegions();
1572 if (mBuilder
.ShouldSyncDecodeImages()) {
1573 DL_LOGI("RDL - Sync decoding images");
1574 MarkFramesWithItemsAndImagesModified(&mList
);
1577 InvalidateCaretFramesIfNeeded();
1579 // We set the override dirty regions during ComputeRebuildRegion or in
1580 // DisplayPortUtils::InvalidateForDisplayPortChange. The display port change
1581 // also marks the frame modified, so those regions are cleared here as well.
1582 AutoClearFramePropsArray
modifiedFrames(64);
1583 AutoClearFramePropsArray
framesWithProps(64);
1584 GetModifiedAndFramesWithProps(&modifiedFrames
.Frames(),
1585 &framesWithProps
.Frames());
1587 if (!ShouldBuildPartial(modifiedFrames
.Frames())) {
1588 // Do not allow partial builds if the |ShouldBuildPartial()| heuristic
1590 mBuilder
.SetPartialBuildFailed(true);
1591 return PartialUpdateResult::Failed
;
1594 nsRect modifiedDirty
;
1595 nsDisplayList
modifiedDL(&mBuilder
);
1596 nsIFrame
* modifiedAGR
= nullptr;
1597 PartialUpdateResult result
= PartialUpdateResult::NoChange
;
1598 const bool simpleUpdate
=
1599 TrySimpleUpdate(modifiedFrames
.Frames(), framesWithProps
.Frames());
1601 mBuilder
.EnterPresShell(RootReferenceFrame());
1603 if (!simpleUpdate
) {
1604 if (!ComputeRebuildRegion(modifiedFrames
.Frames(), &modifiedDirty
,
1605 &modifiedAGR
, framesWithProps
.Frames()) ||
1606 !PreProcessDisplayList(&mList
, modifiedAGR
, result
,
1607 RootReferenceFrame(), nullptr)) {
1608 DL_LOGI("RDL - Partial update aborted");
1609 mBuilder
.SetPartialBuildFailed(true);
1610 mBuilder
.LeavePresShell(RootReferenceFrame(), nullptr);
1611 mList
.DeleteAll(&mBuilder
);
1612 return PartialUpdateResult::Failed
;
1615 modifiedDirty
= mBuilder
.GetVisibleRect();
1618 // This is normally handled by EnterPresShell, but we skipped it so that we
1619 // didn't call MarkFrameForDisplayIfVisible before ComputeRebuildRegion.
1620 nsIScrollableFrame
* sf
=
1621 RootReferenceFrame()->PresShell()->GetRootScrollFrameAsScrollable();
1623 nsCanvasFrame
* canvasFrame
= do_QueryFrame(sf
->GetScrolledFrame());
1625 mBuilder
.MarkFrameForDisplayIfVisible(canvasFrame
, RootReferenceFrame());
1629 nsRect rootOverflow
= RootOverflowRect();
1630 modifiedDirty
.IntersectRect(modifiedDirty
, rootOverflow
);
1632 mBuilder
.SetDirtyRect(modifiedDirty
);
1633 mBuilder
.SetPartialUpdate(true);
1634 mBuilder
.SetPartialBuildFailed(false);
1636 DL_LOGI("RDL - Starting display list build");
1637 RootReferenceFrame()->BuildDisplayListForStackingContext(&mBuilder
,
1639 DL_LOGI("RDL - Finished display list build");
1641 if (!modifiedDL
.IsEmpty()) {
1642 nsLayoutUtils::AddExtraBackgroundItems(
1643 &mBuilder
, &modifiedDL
, RootReferenceFrame(),
1644 nsRect(nsPoint(0, 0), rootOverflow
.Size()), rootOverflow
, aBackstop
);
1646 mBuilder
.SetPartialUpdate(false);
1648 if (mBuilder
.PartialBuildFailed()) {
1649 DL_LOGI("RDL - Partial update failed!");
1650 mBuilder
.LeavePresShell(RootReferenceFrame(), nullptr);
1651 mBuilder
.ClearReuseableDisplayItems();
1652 mList
.DeleteAll(&mBuilder
);
1653 modifiedDL
.DeleteAll(&mBuilder
);
1654 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::Content
;
1655 return PartialUpdateResult::Failed
;
1658 // printf_stderr("Painting --- Modified list (dirty %d,%d,%d,%d):\n",
1659 // modifiedDirty.x, modifiedDirty.y, modifiedDirty.width,
1660 // modifiedDirty.height);
1661 // nsIFrame::PrintDisplayList(&mBuilder, modifiedDL);
1663 // |modifiedDL| can sometimes be empty here. We still perform the
1664 // display list merging to prune unused items (for example, items that
1665 // are not visible anymore) from the old list.
1666 // TODO: Optimization opportunity. In this case, MergeDisplayLists()
1667 // unnecessarily creates a hashtable of the old items.
1668 // TODO: Ideally we could skip this if result is NoChange, but currently when
1669 // we call RestoreState on nsDisplayWrapList it resets the clip to the base
1670 // clip, and we need the UpdateBounds call (within MergeDisplayLists) to
1671 // move it to the correct inner clip.
1672 if (!simpleUpdate
) {
1673 Maybe
<const ActiveScrolledRoot
*> dummy
;
1674 if (MergeDisplayLists(&modifiedDL
, &mList
, &mList
, dummy
)) {
1675 result
= PartialUpdateResult::Updated
;
1678 MOZ_ASSERT(mList
.IsEmpty());
1679 mList
= std::move(modifiedDL
);
1680 mBuilder
.ClearReuseableDisplayItems();
1681 result
= PartialUpdateResult::Updated
;
1685 if (DL_LOG_TEST(LogLevel::Verbose
)) {
1686 printf_stderr("Painting --- Display list:\n");
1687 nsIFrame::PrintDisplayList(&mBuilder
, mList
);
1691 mBuilder
.LeavePresShell(RootReferenceFrame(), List());
1695 nsRect
RetainedDisplayListBuilder::RootOverflowRect() const {
1696 const nsIFrame
* rootReferenceFrame
= RootReferenceFrame();
1697 nsRect rootOverflowRect
= rootReferenceFrame
->InkOverflowRectRelativeToSelf();
1698 const nsPresContext
* presContext
= rootReferenceFrame
->PresContext();
1699 if (!rootReferenceFrame
->GetParent() &&
1700 presContext
->IsRootContentDocumentCrossProcess() &&
1701 presContext
->HasDynamicToolbar()) {
1702 rootOverflowRect
.SizeTo(nsLayoutUtils::ExpandHeightForDynamicToolbar(
1703 presContext
, rootOverflowRect
.Size()));
1706 return rootOverflowRect
;
1709 } // namespace mozilla