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());
527 if (aOutItem
->GetType() == DisplayItemType::TYPE_TRANSFORM
) {
528 MOZ_ASSERT(!aNewItem
||
529 aNewItem
->GetType() == DisplayItemType::TYPE_TRANSFORM
);
530 MOZ_ASSERT(aOldItem
->GetType() == DisplayItemType::TYPE_TRANSFORM
);
531 static_cast<nsDisplayTransform
*>(aOutItem
)->SetContainsASRs(
532 static_cast<nsDisplayTransform
*>(aOldItem
)->GetContainsASRs() ||
534 ? static_cast<nsDisplayTransform
*>(aNewItem
)->GetContainsASRs()
539 bool ShouldUseNewItem(nsDisplayItem
* aNewItem
) {
540 // Generally we want to use the old item when the frame isn't marked as
541 // modified so that any cached information on the item (or referencing the
542 // item) gets retained. Quite a few FrameLayerBuilder performance
543 // improvements benefit by this. Sometimes, however, we can end up where the
544 // new item paints something different from the old item, even though we
545 // haven't modified the frame, and it's hard to fix. In these cases we just
546 // always use the new item to be safe.
547 DisplayItemType type
= aNewItem
->GetType();
548 if (type
== DisplayItemType::TYPE_CANVAS_BACKGROUND_COLOR
||
549 type
== DisplayItemType::TYPE_SOLID_COLOR
) {
550 // The canvas background color item can paint the color from another
551 // frame, and even though we schedule a paint, we don't mark the canvas
556 if (type
== DisplayItemType::TYPE_TABLE_BORDER_COLLAPSE
) {
557 // We intentionally don't mark the root table frame as modified when a
558 // subframe changes, even though the border collapse item for the root
559 // frame is what paints the changed border. Marking the root frame as
560 // modified would rebuild display items for the whole table area, and we
565 if (type
== DisplayItemType::TYPE_TEXT_OVERFLOW
) {
566 // Text overflow marker items are created with the wrapping block as their
567 // frame, and have an index value to note which line they are created for.
568 // Their rendering can change if the items on that line change, which may
569 // not mark the block as modified. We rebuild them if we build any item on
570 // the line, so we should always get new items if they might have changed
571 // rendering, and it's easier to just use the new items rather than
572 // computing if we actually need them.
576 if (type
== DisplayItemType::TYPE_SUBDOCUMENT
||
577 type
== DisplayItemType::TYPE_STICKY_POSITION
) {
578 // nsDisplaySubDocument::mShouldFlatten can change without an invalidation
579 // (and is the reason we unconditionally build the subdocument item), so
580 // always use the new one to make sure we get the right value.
581 // Same for |nsDisplayStickyPosition::mShouldFlatten|.
585 if (type
== DisplayItemType::TYPE_CARET
) {
586 // The caret can change position while still being owned by the same frame
587 // and we don't invalidate in that case. Use the new version since the
588 // changed bounds are needed for DLBI.
592 if (type
== DisplayItemType::TYPE_MASK
||
593 type
== DisplayItemType::TYPE_FILTER
||
594 type
== DisplayItemType::TYPE_SVG_WRAPPER
) {
595 // SVG items have some invalidation issues, see bugs 1494110 and 1494663.
599 if (type
== DisplayItemType::TYPE_TRANSFORM
) {
600 // Prerendering of transforms can change without frame invalidation.
607 RetainedDisplayList
Finalize() {
608 for (size_t i
= 0; i
< mOldDAG
.Length(); i
++) {
609 if (mOldItems
[i
].IsUsed()) {
613 AutoTArray
<MergedListIndex
, 2> directPredecessors
=
614 ResolveNodeIndexesOldToMerged(
615 mOldDAG
.GetDirectPredecessors(OldListIndex(i
)));
616 ProcessOldNode(OldListIndex(i
), std::move(directPredecessors
));
619 RetainedDisplayList
result(mBuilder
->Builder());
620 result
.AppendToTop(&mMergedItems
);
621 result
.mDAG
= std::move(mMergedDAG
);
622 MOZ_RELEASE_ASSERT(result
.mDAG
.Length() == result
.Length());
626 bool HasMatchingItemInOldList(nsDisplayItem
* aItem
, OldListIndex
* aOutIndex
) {
627 // Look for an item that matches aItem's frame and per-frame-key, but isn't
629 uint32_t outerKey
= mOuterItem
? mOuterItem
->GetPerFrameKey() : 0;
630 nsIFrame
* frame
= aItem
->Frame();
631 for (nsDisplayItem
* i
: frame
->DisplayItems()) {
632 if (i
!= aItem
&& i
->Frame() == frame
&&
633 i
->GetPerFrameKey() == aItem
->GetPerFrameKey()) {
634 if (i
->GetOldListIndex(mOldList
, outerKey
, aOutIndex
)) {
642 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
643 bool HasModifiedFrame(nsDisplayItem
* aItem
) {
644 nsIFrame
* stopFrame
= mOuterItem
? mOuterItem
->Frame() : nullptr;
645 return AnyContentAncestorModified(aItem
->FrameForInvalidation(), stopFrame
);
649 void UpdateContainerASR(nsDisplayItem
* aItem
) {
650 mContainerASR
= SelectContainerASR(
651 aItem
->GetClipChain(), aItem
->GetActiveScrolledRoot(), mContainerASR
);
654 MergedListIndex
AddNewNode(
655 nsDisplayItem
* aItem
, const Maybe
<OldListIndex
>& aOldIndex
,
656 Span
<const MergedListIndex
> aDirectPredecessors
,
657 const Maybe
<MergedListIndex
>& aExtraDirectPredecessor
) {
658 UpdateContainerASR(aItem
);
659 aItem
->NotifyUsed(mBuilder
->Builder());
661 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
662 for (nsDisplayItem
* i
: aItem
->Frame()->DisplayItems()) {
663 if (i
->Frame() == aItem
->Frame() &&
664 i
->GetPerFrameKey() == aItem
->GetPerFrameKey()) {
665 MOZ_DIAGNOSTIC_ASSERT(!i
->IsMergedItem());
669 aItem
->SetMergedPreProcessed(true, false);
672 mMergedItems
.AppendToTop(aItem
);
673 mBuilder
->Metrics()->mTotalItems
++;
675 MergedListIndex newIndex
=
676 mMergedDAG
.AddNode(aDirectPredecessors
, aExtraDirectPredecessor
);
680 void ProcessOldNode(OldListIndex aNode
,
681 nsTArray
<MergedListIndex
>&& aDirectPredecessors
) {
682 nsDisplayItem
* item
= mOldItems
[aNode
.val
].mItem
;
683 if (mOldItems
[aNode
.val
].IsChanged()) {
684 mOldItems
[aNode
.val
].Discard(mBuilder
, std::move(aDirectPredecessors
));
685 mResultIsModified
= true;
687 MergeChildLists(nullptr, item
, item
);
689 if (item
->GetType() == DisplayItemType::TYPE_SUBDOCUMENT
) {
690 mBuilder
->IncrementSubDocPresShellPaintCount(item
);
692 item
->SetReused(true);
693 mBuilder
->Metrics()->mReusedItems
++;
694 mOldItems
[aNode
.val
].AddedToMergedList(
695 AddNewNode(item
, Some(aNode
), aDirectPredecessors
, Nothing()));
699 struct PredecessorStackItem
{
700 PredecessorStackItem(OldListIndex aNode
, Span
<OldListIndex
> aPredecessors
)
702 mDirectPredecessors(aPredecessors
),
703 mCurrentPredecessorIndex(0) {}
706 return mCurrentPredecessorIndex
== mDirectPredecessors
.Length();
709 OldListIndex
GetAndIncrementCurrentPredecessor() {
710 return mDirectPredecessors
[mCurrentPredecessorIndex
++];
714 Span
<OldListIndex
> mDirectPredecessors
;
715 size_t mCurrentPredecessorIndex
;
718 AutoTArray
<MergedListIndex
, 2> ProcessPredecessorsOfOldNode(
719 OldListIndex aNode
) {
720 AutoTArray
<PredecessorStackItem
, 256> mStack
;
721 mStack
.AppendElement(
722 PredecessorStackItem(aNode
, mOldDAG
.GetDirectPredecessors(aNode
)));
725 if (mStack
.LastElement().IsFinished()) {
726 // If we've finished processing all the entries in the current set, then
727 // pop it off the processing stack and process it.
728 PredecessorStackItem item
= mStack
.PopLastElement();
729 AutoTArray
<MergedListIndex
, 2> result
=
730 ResolveNodeIndexesOldToMerged(item
.mDirectPredecessors
);
732 if (mStack
.IsEmpty()) {
736 ProcessOldNode(item
.mNode
, std::move(result
));
738 // Grab the current predecessor, push predecessors of that onto the
739 // processing stack (if it hasn't already been processed), and then
740 // advance to the next entry.
741 OldListIndex currentIndex
=
742 mStack
.LastElement().GetAndIncrementCurrentPredecessor();
743 if (!mOldItems
[currentIndex
.val
].IsUsed()) {
744 mStack
.AppendElement(PredecessorStackItem(
745 currentIndex
, mOldDAG
.GetDirectPredecessors(currentIndex
)));
751 AutoTArray
<MergedListIndex
, 2> ResolveNodeIndexesOldToMerged(
752 Span
<OldListIndex
> aDirectPredecessors
) {
753 AutoTArray
<MergedListIndex
, 2> result
;
754 result
.SetCapacity(aDirectPredecessors
.Length());
755 for (OldListIndex index
: aDirectPredecessors
) {
756 OldItemInfo
& oldItem
= mOldItems
[index
.val
];
757 if (oldItem
.IsDiscarded()) {
758 for (MergedListIndex inner
: oldItem
.mDirectPredecessors
) {
759 if (!result
.Contains(inner
)) {
760 result
.AppendElement(inner
);
764 result
.AppendElement(oldItem
.mIndex
);
770 RetainedDisplayListBuilder
* mBuilder
;
771 RetainedDisplayList
* mOldList
;
772 Maybe
<const ActiveScrolledRoot
*> mContainerASR
;
773 nsTArray
<OldItemInfo
> mOldItems
;
774 DirectedAcyclicGraph
<OldListUnits
> mOldDAG
;
775 // Unfortunately we can't use strong typing for the hashtables
776 // since they internally encode the type with the mOps pointer,
777 // and assert when we try swap the contents
778 nsDisplayList mMergedItems
;
779 DirectedAcyclicGraph
<MergedListUnits
> mMergedDAG
;
780 nsDisplayItem
* mOuterItem
;
781 bool mResultIsModified
;
785 void VerifyNotModified(nsDisplayList
* aList
) {
786 for (nsDisplayItem
* item
: *aList
) {
787 MOZ_ASSERT(!AnyContentAncestorModified(item
->FrameForInvalidation()));
789 if (item
->GetChildren()) {
790 VerifyNotModified(item
->GetChildren());
797 * Takes two display lists and merges them into an output list.
799 * Display lists wthout an explicit DAG are interpreted as linear DAGs (with a
800 * maximum of one direct predecessor and one direct successor per node). We add
801 * the two DAGs together, and then output the topological sorted ordering as the
802 * final display list.
804 * Once we've merged a list, we then retain the DAG (as part of the
805 * RetainedDisplayList object) to use for future merges.
807 bool RetainedDisplayListBuilder::MergeDisplayLists(
808 nsDisplayList
* aNewList
, RetainedDisplayList
* aOldList
,
809 RetainedDisplayList
* aOutList
,
810 mozilla::Maybe
<const mozilla::ActiveScrolledRoot
*>& aOutContainerASR
,
811 nsDisplayItem
* aOuterItem
) {
812 AUTO_PROFILER_LABEL_CATEGORY_PAIR(GRAPHICS_DisplayListMerging
);
814 if (!aOldList
->IsEmpty()) {
815 // If we still have items in the actual list, then it is because
816 // PreProcessDisplayList decided that it was sure it can't be modified. We
817 // can just use it directly, and throw any new items away.
819 aNewList
->DeleteAll(&mBuilder
);
821 VerifyNotModified(aOldList
);
824 if (aOldList
!= aOutList
) {
825 *aOutList
= std::move(*aOldList
);
831 MergeState
merge(this, *aOldList
, aOuterItem
);
833 Maybe
<MergedListIndex
> previousItemIndex
;
834 for (nsDisplayItem
* item
: aNewList
->TakeItems()) {
835 Metrics()->mNewItems
++;
836 previousItemIndex
= merge
.ProcessItemFromNewList(item
, previousItemIndex
);
839 *aOutList
= merge
.Finalize();
840 aOutContainerASR
= merge
.mContainerASR
;
841 return merge
.mResultIsModified
;
844 void RetainedDisplayListBuilder::GetModifiedAndFramesWithProps(
845 nsTArray
<nsIFrame
*>* aOutModifiedFrames
,
846 nsTArray
<nsIFrame
*>* aOutFramesWithProps
) {
847 for (auto it
= Data()->ConstIterator(); !it
.Done(); it
.Next()) {
848 nsIFrame
* frame
= it
.Key();
849 const RetainedDisplayListData::FrameFlags
& flags
= it
.Data();
851 if (flags
.contains(RetainedDisplayListData::FrameFlag::Modified
)) {
852 aOutModifiedFrames
->AppendElement(frame
);
855 if (flags
.contains(RetainedDisplayListData::FrameFlag::HasProps
)) {
856 aOutFramesWithProps
->AppendElement(frame
);
859 if (flags
.contains(RetainedDisplayListData::FrameFlag::HadWillChange
)) {
860 Builder()->RemoveFromWillChangeBudgets(frame
);
867 // ComputeRebuildRegion debugging
868 // #define CRR_DEBUG 1
870 # define CRR_LOG(...) printf_stderr(__VA_ARGS__)
872 # define CRR_LOG(...)
875 static nsDisplayItem
* GetFirstDisplayItemWithChildren(nsIFrame
* aFrame
) {
876 for (nsDisplayItem
* i
: aFrame
->DisplayItems()) {
877 if (i
->HasDeletedFrame() || i
->Frame() != aFrame
) {
878 // The main frame for the display item has been deleted or the display
879 // item belongs to another frame.
883 if (i
->HasChildren()) {
884 return static_cast<nsDisplayItem
*>(i
);
890 static bool IsInPreserve3DContext(const nsIFrame
* aFrame
) {
891 return aFrame
->Extend3DContext() ||
892 aFrame
->Combines3DTransformWithAncestors();
895 // Returns true if |aFrame| can store a display list building rect.
896 // These limitations are necessary to guarantee that
897 // 1) Just enough items are rebuilt to properly update display list
898 // 2) Modified frames will be visited during a partial display list build.
899 static bool CanStoreDisplayListBuildingRect(nsDisplayListBuilder
* aBuilder
,
901 return aFrame
!= aBuilder
->RootReferenceFrame() &&
902 aFrame
->IsStackingContext() && aFrame
->IsFixedPosContainingBlock() &&
903 // Split frames might have placeholders for modified frames in their
904 // unmodified continuation frame.
905 !aFrame
->GetPrevContinuation() && !aFrame
->GetNextContinuation();
908 static bool ProcessFrameInternal(nsIFrame
* aFrame
,
909 nsDisplayListBuilder
* aBuilder
,
910 nsIFrame
** aAGR
, nsRect
& aOverflow
,
911 const nsIFrame
* aStopAtFrame
,
912 nsTArray
<nsIFrame
*>& aOutFramesWithProps
,
913 const bool aStopAtStackingContext
) {
914 nsIFrame
* currentFrame
= aFrame
;
916 while (currentFrame
!= aStopAtFrame
) {
917 CRR_LOG("currentFrame: %p (placeholder=%d), aOverflow: %d %d %d %d\n",
918 currentFrame
, !aStopAtStackingContext
, aOverflow
.x
, aOverflow
.y
,
919 aOverflow
.width
, aOverflow
.height
);
921 // If the current frame is an OOF frame, DisplayListBuildingData needs to be
922 // set on all the ancestor stacking contexts of the placeholder frame, up
923 // to the containing block of the OOF frame. This is done to ensure that the
924 // content that might be behind the OOF frame is built for merging.
925 nsIFrame
* placeholder
= currentFrame
->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW
)
926 ? currentFrame
->GetPlaceholderFrame()
930 nsRect placeholderOverflow
= aOverflow
;
931 auto rv
= nsLayoutUtils::TransformRect(currentFrame
, placeholder
,
932 placeholderOverflow
);
933 if (rv
!= nsLayoutUtils::TRANSFORM_SUCCEEDED
) {
934 placeholderOverflow
= nsRect();
937 CRR_LOG("Processing placeholder %p for OOF frame %p\n", placeholder
,
940 CRR_LOG("OOF frame draw area: %d %d %d %d\n", placeholderOverflow
.x
,
941 placeholderOverflow
.y
, placeholderOverflow
.width
,
942 placeholderOverflow
.height
);
944 // Tracking AGRs for the placeholder processing is not necessary, as the
945 // goal is to only modify the DisplayListBuildingData rect.
946 nsIFrame
* dummyAGR
= nullptr;
948 // Find a common ancestor frame to handle frame continuations.
949 // TODO: It might be possible to write a more specific and efficient
950 // function for this.
951 const nsIFrame
* ancestor
= nsLayoutUtils::FindNearestCommonAncestorFrame(
952 currentFrame
->GetParent(), placeholder
->GetParent());
954 if (!ProcessFrameInternal(placeholder
, aBuilder
, &dummyAGR
,
955 placeholderOverflow
, ancestor
,
956 aOutFramesWithProps
, false)) {
961 // Convert 'aOverflow' into the coordinate space of the nearest stacking
962 // context or display port ancestor and update 'currentFrame' to point to
964 aOverflow
= nsLayoutUtils::TransformFrameRectToAncestor(
965 currentFrame
, aOverflow
, aStopAtFrame
, nullptr, nullptr,
966 /* aStopAtStackingContextAndDisplayPortAndOOFFrame = */ true,
968 if (IsInPreserve3DContext(currentFrame
)) {
972 MOZ_ASSERT(currentFrame
);
974 // Check whether the current frame is a scrollable frame with display port.
976 nsIScrollableFrame
* sf
= do_QueryFrame(currentFrame
);
977 nsIContent
* content
= sf
? currentFrame
->GetContent() : nullptr;
979 if (content
&& DisplayPortUtils::GetDisplayPort(content
, &displayPort
)) {
980 CRR_LOG("Frame belongs to displayport frame %p\n", currentFrame
);
982 // Get overflow relative to the scrollport (from the scrollframe)
983 nsRect r
= aOverflow
- sf
->GetScrollPortRect().TopLeft();
984 r
.IntersectRect(r
, displayPort
);
986 nsRect
* rect
= currentFrame
->GetProperty(
987 nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
990 currentFrame
->SetProperty(
991 nsDisplayListBuilder::DisplayListBuildingDisplayPortRect(), rect
);
992 currentFrame
->SetHasOverrideDirtyRegion(true);
993 aOutFramesWithProps
.AppendElement(currentFrame
);
995 rect
->UnionRect(*rect
, r
);
996 CRR_LOG("Adding area to displayport draw area: %d %d %d %d\n", r
.x
, r
.y
,
999 // TODO: Can we just use MarkFrameForDisplayIfVisible, plus
1000 // MarkFramesForDifferentAGR to ensure that this displayport, plus any
1001 // items that move relative to it get rebuilt, and then not contribute
1002 // to the root dirty area?
1003 aOverflow
= sf
->GetScrollPortRect();
1005 // Don't contribute to the root dirty area at all.
1006 aOverflow
.SetEmpty();
1009 aOverflow
.IntersectRect(aOverflow
,
1010 currentFrame
->InkOverflowRectRelativeToSelf());
1013 if (aOverflow
.IsEmpty()) {
1017 if (CanStoreDisplayListBuildingRect(aBuilder
, currentFrame
)) {
1018 CRR_LOG("Frame belongs to stacking context frame %p\n", currentFrame
);
1019 // If we found an intermediate stacking context with an existing display
1020 // item then we can store the dirty rect there and stop. If we couldn't
1021 // find one then we need to keep bubbling up to the next stacking context.
1022 nsDisplayItem
* wrapperItem
=
1023 GetFirstDisplayItemWithChildren(currentFrame
);
1028 // Store the stacking context relative dirty area such
1029 // that display list building will pick it up when it
1031 nsDisplayListBuilder::DisplayListBuildingData
* data
=
1032 currentFrame
->GetProperty(
1033 nsDisplayListBuilder::DisplayListBuildingRect());
1035 data
= new nsDisplayListBuilder::DisplayListBuildingData();
1036 currentFrame
->SetProperty(
1037 nsDisplayListBuilder::DisplayListBuildingRect(), data
);
1038 currentFrame
->SetHasOverrideDirtyRegion(true);
1039 aOutFramesWithProps
.AppendElement(currentFrame
);
1041 CRR_LOG("Adding area to stacking context draw area: %d %d %d %d\n",
1042 aOverflow
.x
, aOverflow
.y
, aOverflow
.width
, aOverflow
.height
);
1043 data
->mDirtyRect
.UnionRect(data
->mDirtyRect
, aOverflow
);
1045 if (!aStopAtStackingContext
) {
1046 // Continue ascending the frame tree until we reach aStopAtFrame.
1050 // Grab the visible (display list building) rect for children of this
1051 // wrapper item and convert into into coordinate relative to the current
1053 nsRect previousVisible
= wrapperItem
->GetBuildingRectForChildren();
1054 if (wrapperItem
->ReferenceFrameForChildren() != wrapperItem
->Frame()) {
1055 previousVisible
-= wrapperItem
->ToReferenceFrame();
1058 if (!previousVisible
.Contains(aOverflow
)) {
1059 // If the overflow area of the changed frame isn't contained within the
1060 // old item, then we might change the size of the item and need to
1061 // update its sorting accordingly. Keep propagating the overflow area up
1062 // so that we build intersecting items for sorting.
1066 if (!data
->mModifiedAGR
) {
1067 data
->mModifiedAGR
= *aAGR
;
1068 } else if (data
->mModifiedAGR
!= *aAGR
) {
1069 data
->mDirtyRect
= currentFrame
->InkOverflowRectRelativeToSelf();
1071 "Found multiple modified AGRs within this stacking context, "
1075 // Don't contribute to the root dirty area at all.
1076 aOverflow
.SetEmpty();
1085 bool RetainedDisplayListBuilder::ProcessFrame(
1086 nsIFrame
* aFrame
, nsDisplayListBuilder
* aBuilder
, nsIFrame
* aStopAtFrame
,
1087 nsTArray
<nsIFrame
*>& aOutFramesWithProps
, const bool aStopAtStackingContext
,
1088 nsRect
* aOutDirty
, nsIFrame
** aOutModifiedAGR
) {
1089 if (aFrame
->HasOverrideDirtyRegion()) {
1090 aOutFramesWithProps
.AppendElement(aFrame
);
1093 if (aFrame
->HasAnyStateBits(NS_FRAME_IN_POPUP
)) {
1097 // TODO: There is almost certainly a faster way of doing this, probably can be
1098 // combined with the ancestor walk for TransformFrameRectToAncestor.
1099 nsIFrame
* agrFrame
= aBuilder
->FindAnimatedGeometryRootFrameFor(aFrame
);
1101 CRR_LOG("Processing frame %p with agr %p\n", aFrame
, agr
->mFrame
);
1103 // Convert the frame's overflow rect into the coordinate space
1104 // of the nearest stacking context that has an existing display item.
1105 // We store that as a dirty rect on that stacking context so that we build
1106 // all items that intersect the changed frame within the stacking context,
1107 // and then we use MarkFrameForDisplayIfVisible to make sure the stacking
1108 // context itself gets built. We don't need to build items that intersect
1109 // outside of the stacking context, since we know the stacking context item
1110 // exists in the old list, so we can trivially merge without needing other
1112 nsRect overflow
= aFrame
->InkOverflowRectRelativeToSelf();
1114 // If the modified frame is also a caret frame, include the caret area.
1115 // This is needed because some frames (for example text frames without text)
1116 // might have an empty overflow rect.
1117 if (aFrame
== aBuilder
->GetCaretFrame()) {
1118 overflow
.UnionRect(overflow
, aBuilder
->GetCaretRect());
1121 if (!ProcessFrameInternal(aFrame
, aBuilder
, &agrFrame
, overflow
, aStopAtFrame
,
1122 aOutFramesWithProps
, aStopAtStackingContext
)) {
1126 if (!overflow
.IsEmpty()) {
1127 aOutDirty
->UnionRect(*aOutDirty
, overflow
);
1128 CRR_LOG("Adding area to root draw area: %d %d %d %d\n", overflow
.x
,
1129 overflow
.y
, overflow
.width
, overflow
.height
);
1131 // If we get changed frames from multiple AGRS, then just give up as it gets
1132 // really complex to track which items would need to be marked in
1133 // MarkFramesForDifferentAGR.
1134 if (!*aOutModifiedAGR
) {
1135 CRR_LOG("Setting %p as root stacking context AGR\n", agrFrame
);
1136 *aOutModifiedAGR
= agrFrame
;
1137 } else if (agrFrame
&& *aOutModifiedAGR
!= agrFrame
) {
1138 CRR_LOG("Found multiple AGRs in root stacking context, giving up\n");
1145 static void AddFramesForContainingBlock(nsIFrame
* aBlock
,
1146 const nsFrameList
& aFrames
,
1147 nsTArray
<nsIFrame
*>& aExtraFrames
) {
1148 for (nsIFrame
* f
: aFrames
) {
1149 if (!f
->IsFrameModified() && AnyContentAncestorModified(f
, aBlock
)) {
1150 CRR_LOG("Adding invalid OOF %p\n", f
);
1151 aExtraFrames
.AppendElement(f
);
1156 // Placeholder descendants of aFrame don't contribute to aFrame's overflow area.
1157 // Find all the containing blocks that might own placeholders under us, walk
1158 // their OOF frames list, and manually invalidate any frames that are
1159 // descendants of a modified frame (us, or another frame we'll get to soon).
1160 // This is combined with the work required for MarkFrameForDisplayIfVisible,
1161 // so that we can avoid an extra ancestor walk, and we can reuse the flag
1162 // to detect when we've already visited an ancestor (and thus all further
1163 // ancestors must also be visited).
1164 static void FindContainingBlocks(nsIFrame
* aFrame
,
1165 nsTArray
<nsIFrame
*>& aExtraFrames
) {
1166 for (nsIFrame
* f
= aFrame
; f
; f
= nsLayoutUtils::GetDisplayListParent(f
)) {
1167 if (f
->ForceDescendIntoIfVisible()) {
1170 f
->SetForceDescendIntoIfVisible(true);
1171 CRR_LOG("Considering OOFs for %p\n", f
);
1173 AddFramesForContainingBlock(f
, f
->GetChildList(FrameChildListID::Float
),
1175 AddFramesForContainingBlock(f
, f
->GetChildList(f
->GetAbsoluteListID()),
1178 // This condition must match the condition in
1179 // nsLayoutUtils::GetParentOrPlaceholderFor which is used by
1180 // nsLayoutUtils::GetDisplayListParent
1181 if (f
->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW
) && !f
->GetPrevInFlow()) {
1182 nsIFrame
* parent
= f
->GetParent();
1183 if (parent
&& !parent
->ForceDescendIntoIfVisible()) {
1184 // If the GetDisplayListParent call is going to walk to a placeholder,
1185 // in rare cases the placeholder might be contained in a different
1186 // continuation from the oof. So we have to make sure to mark the oofs
1187 // parent. In the common case this doesn't make us do any extra work,
1188 // just changes the order in which we visit the frames since walking
1189 // through placeholders will walk through the parent, and we stop when
1190 // we find a ForceDescendIntoIfVisible bit set.
1191 FindContainingBlocks(parent
, aExtraFrames
);
1198 * Given a list of frames that has been modified, computes the region that we
1199 * need to do display list building for in order to build all modified display
1202 * When a modified frame is within a stacking context (with an existing display
1203 * item), then we only contribute to the build area within the stacking context,
1204 * as well as forcing display list building to descend to the stacking context.
1205 * We don't need to add build area outside of the stacking context (and force
1206 * items above/below the stacking context container item to be built), since
1207 * just matching the position of the stacking context container item is
1208 * sufficient to ensure correct ordering during merging.
1210 * We need to rebuild all items that might intersect with the modified frame,
1211 * both now and during async changes on the compositor. We do this by rebuilding
1212 * the area covered by the changed frame, as well as rebuilding all items that
1213 * have a different (async) AGR to the changed frame. If we have changes to
1214 * multiple AGRs (within a stacking context), then we rebuild that stacking
1217 * @param aModifiedFrames The list of modified frames.
1218 * @param aOutDirty The result region to use for display list building.
1219 * @param aOutModifiedAGR The modified AGR for the root stacking context.
1220 * @param aOutFramesWithProps The list of frames to which we attached partial
1221 * build data so that it can be cleaned up.
1223 * @return true if we succesfully computed a partial rebuild region, false if a
1224 * full build is required.
1226 bool RetainedDisplayListBuilder::ComputeRebuildRegion(
1227 nsTArray
<nsIFrame
*>& aModifiedFrames
, nsRect
* aOutDirty
,
1228 nsIFrame
** aOutModifiedAGR
, nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1229 CRR_LOG("Computing rebuild regions for %zu frames:\n",
1230 aModifiedFrames
.Length());
1231 nsTArray
<nsIFrame
*> extraFrames
;
1232 for (nsIFrame
* f
: aModifiedFrames
) {
1235 mBuilder
.AddFrameMarkedForDisplayIfVisible(f
);
1236 FindContainingBlocks(f
, extraFrames
);
1238 if (!ProcessFrame(f
, &mBuilder
, RootReferenceFrame(), aOutFramesWithProps
,
1239 true, aOutDirty
, aOutModifiedAGR
)) {
1244 // Since we set modified to true on the extraFrames, add them to
1245 // aModifiedFrames so that it will get reverted.
1246 aModifiedFrames
.AppendElements(extraFrames
);
1248 for (nsIFrame
* f
: extraFrames
) {
1249 f
->SetFrameIsModified(true);
1251 if (!ProcessFrame(f
, &mBuilder
, RootReferenceFrame(), aOutFramesWithProps
,
1252 true, aOutDirty
, aOutModifiedAGR
)) {
1260 bool RetainedDisplayListBuilder::ShouldBuildPartial(
1261 nsTArray
<nsIFrame
*>& aModifiedFrames
) {
1262 if (mList
.IsEmpty()) {
1263 // Partial builds without a previous display list do not make sense.
1264 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::EmptyList
;
1268 if (aModifiedFrames
.Length() >
1269 StaticPrefs::layout_display_list_rebuild_frame_limit()) {
1270 // Computing a dirty rect with too many modified frames can be slow.
1271 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::RebuildLimit
;
1275 // We don't support retaining with overlay scrollbars, since they require
1276 // us to look at the display list and pick the highest z-index, which
1277 // we can't do during partial building.
1278 if (mBuilder
.DisablePartialUpdates()) {
1279 mBuilder
.SetDisablePartialUpdates(false);
1280 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::Disabled
;
1284 for (nsIFrame
* f
: aModifiedFrames
) {
1287 const LayoutFrameType type
= f
->Type();
1289 // If we have any modified frames of the following types, it is likely that
1290 // doing a partial rebuild of the display list will be slower than doing a
1292 // This is because these frames either intersect or may intersect with most
1293 // of the page content. This is either due to display port size or different
1295 if (type
== LayoutFrameType::Viewport
||
1296 type
== LayoutFrameType::PageContent
||
1297 type
== LayoutFrameType::Canvas
|| type
== LayoutFrameType::Scrollbar
) {
1298 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::FrameType
;
1302 // Detect root scroll frame and do a full rebuild for them too for the same
1303 // reasons as above, but also because top layer items should to be marked
1304 // modified if the root scroll frame is modified. Putting this check here
1305 // means we don't need to check everytime a frame is marked modified though.
1306 if (type
== LayoutFrameType::Scroll
&& f
->GetParent() &&
1307 !f
->GetParent()->GetParent()) {
1308 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::FrameType
;
1316 class AutoClearFramePropsArray
{
1318 explicit AutoClearFramePropsArray(size_t aCapacity
) : mFrames(aCapacity
) {}
1319 AutoClearFramePropsArray() = default;
1320 ~AutoClearFramePropsArray() {
1321 size_t len
= mFrames
.Length();
1322 nsIFrame
** elements
= mFrames
.Elements();
1323 for (size_t i
= 0; i
< len
; ++i
) {
1324 nsIFrame
* f
= elements
[i
];
1325 DL_LOGV("RDL - Clearing modified flags for frame %p", f
);
1326 if (f
->HasOverrideDirtyRegion()) {
1327 f
->SetHasOverrideDirtyRegion(false);
1328 f
->RemoveProperty(nsDisplayListBuilder::DisplayListBuildingRect());
1330 nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());
1332 f
->SetFrameIsModified(false);
1333 f
->SetHasModifiedDescendants(false);
1337 nsTArray
<nsIFrame
*>& Frames() { return mFrames
; }
1338 bool IsEmpty() const { return mFrames
.IsEmpty(); }
1341 nsTArray
<nsIFrame
*> mFrames
;
1344 void RetainedDisplayListBuilder::ClearFramesWithProps() {
1345 AutoClearFramePropsArray
modifiedFrames(Data()->GetModifiedFrameCount());
1346 AutoClearFramePropsArray framesWithProps
;
1347 GetModifiedAndFramesWithProps(&modifiedFrames
.Frames(),
1348 &framesWithProps
.Frames());
1351 void RetainedDisplayListBuilder::ClearRetainedData() {
1352 DL_LOGI("(%p) RDL - Clearing retained display list builder data", this);
1353 List()->DeleteAll(Builder());
1354 ClearFramesWithProps();
1355 ClearReuseableDisplayItems();
1358 namespace RDLUtils
{
1360 MOZ_NEVER_INLINE_DEBUG
void AssertFrameSubtreeUnmodified(
1361 const nsIFrame
* aFrame
) {
1362 MOZ_ASSERT(!aFrame
->IsFrameModified());
1363 MOZ_ASSERT(!aFrame
->HasModifiedDescendants());
1365 for (const auto& childList
: aFrame
->ChildLists()) {
1366 for (nsIFrame
* child
: childList
.mList
) {
1367 AssertFrameSubtreeUnmodified(child
);
1372 MOZ_NEVER_INLINE_DEBUG
void AssertDisplayListUnmodified(nsDisplayList
* aList
) {
1373 for (nsDisplayItem
* item
: *aList
) {
1374 AssertDisplayItemUnmodified(item
);
1378 MOZ_NEVER_INLINE_DEBUG
void AssertDisplayItemUnmodified(nsDisplayItem
* aItem
) {
1379 MOZ_ASSERT(!aItem
->HasDeletedFrame());
1380 MOZ_ASSERT(!AnyContentAncestorModified(aItem
->FrameForInvalidation()));
1382 if (aItem
->GetChildren()) {
1383 AssertDisplayListUnmodified(aItem
->GetChildren());
1387 } // namespace RDLUtils
1391 void MarkAncestorFrames(nsIFrame
* aFrame
,
1392 nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1393 nsIFrame
* frame
= nsLayoutUtils::GetDisplayListParent(aFrame
);
1394 while (frame
&& !frame
->HasModifiedDescendants()) {
1395 aOutFramesWithProps
.AppendElement(frame
);
1396 frame
->SetHasModifiedDescendants(true);
1397 frame
= nsLayoutUtils::GetDisplayListParent(frame
);
1402 * Iterates over the modified frames array and updates the frame tree flags
1403 * so that container frames know whether they have modified descendant frames.
1404 * Frames that were marked modified are added to |aOutFramesWithProps|, so that
1405 * the modified status can be cleared after the display list build.
1407 void MarkAllAncestorFrames(const nsTArray
<nsIFrame
*>& aModifiedFrames
,
1408 nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1409 nsAutoString frameName
;
1410 DL_LOGI("RDL - Modified frames: %zu", aModifiedFrames
.Length());
1411 for (nsIFrame
* frame
: aModifiedFrames
) {
1413 frame
->GetFrameName(frameName
);
1415 DL_LOGV("RDL - Processing modified frame: %p (%s)", frame
,
1416 NS_ConvertUTF16toUTF8(frameName
).get());
1418 MarkAncestorFrames(frame
, aOutFramesWithProps
);
1423 * Marks the given display item |aItem| as reuseable container, and updates the
1424 * bounds in case some child items were destroyed.
1426 MOZ_NEVER_INLINE_DEBUG
void ReuseStackingContextItem(
1427 nsDisplayListBuilder
* aBuilder
, nsDisplayItem
* aItem
) {
1428 aItem
->SetPreProcessed();
1430 if (aItem
->HasChildren()) {
1431 aItem
->UpdateBounds(aBuilder
);
1434 aBuilder
->AddReusableDisplayItem(aItem
);
1435 DL_LOGD("Reusing display item %p", aItem
);
1438 bool IsSupportedFrameType(const nsIFrame
* aFrame
) {
1439 // The way table backgrounds are handled makes these frames incompatible with
1440 // this retained display list approach.
1441 if (aFrame
->IsTableColFrame()) {
1445 if (aFrame
->IsTableColGroupFrame()) {
1449 if (aFrame
->IsTableRowFrame()) {
1453 if (aFrame
->IsTableRowGroupFrame()) {
1457 if (aFrame
->IsTableCellFrame()) {
1461 // Everything else should work.
1465 bool IsReuseableStackingContextItem(nsDisplayItem
* aItem
) {
1466 if (!IsSupportedFrameType(aItem
->Frame())) {
1470 if (!aItem
->IsReusable()) {
1474 const nsIFrame
* frame
= aItem
->FrameForInvalidation();
1475 return !frame
->HasModifiedDescendants() && !frame
->GetPrevContinuation() &&
1476 !frame
->GetNextContinuation();
1480 * Recursively visits every display item of the display list and destroys all
1481 * display items that depend on deleted or modified frames.
1482 * The stacking context display items for unmodified frame subtrees are kept
1483 * linked and collected in given |aOutItems| array.
1485 void CollectStackingContextItems(nsDisplayListBuilder
* aBuilder
,
1486 nsDisplayList
* aList
, nsIFrame
* aOuterFrame
,
1487 int aDepth
= 0, bool aParentReused
= false) {
1488 for (nsDisplayItem
* item
: aList
->TakeItems()) {
1489 if (DL_LOG_TEST(LogLevel::Debug
)) {
1491 "%*s Preprocessing item %p (%s) (frame: %p) "
1492 "(children: %zu) (depth: %d) (parentReused: %d)",
1493 aDepth
, "", item
, item
->Name(),
1494 item
->HasDeletedFrame() ? nullptr : item
->Frame(),
1495 item
->GetChildren() ? item
->GetChildren()->Length() : 0, aDepth
,
1499 if (!item
->CanBeReused() || item
->HasDeletedFrame() ||
1500 AnyContentAncestorModified(item
->FrameForInvalidation(), aOuterFrame
)) {
1501 DL_LOGD("%*s Deleted modified or temporary item %p", aDepth
, "", item
);
1502 item
->Destroy(aBuilder
);
1506 MOZ_ASSERT(!AnyContentAncestorModified(item
->FrameForInvalidation()));
1507 MOZ_ASSERT(!item
->IsPreProcessed());
1508 item
->InvalidateCachedChildInfo(aBuilder
);
1509 #ifdef MOZ_DIAGNOSTIC_ASSERT_ENABLED
1510 item
->SetMergedPreProcessed(false, true);
1512 item
->SetReused(true);
1514 const bool isStackingContextItem
= IsReuseableStackingContextItem(item
);
1516 if (item
->GetChildren()) {
1517 CollectStackingContextItems(aBuilder
, item
->GetChildren(), item
->Frame(),
1519 aParentReused
|| isStackingContextItem
);
1522 if (aParentReused
) {
1523 // Keep the contents of the current container item linked.
1525 RDLUtils::AssertDisplayItemUnmodified(item
);
1527 aList
->AppendToTop(item
);
1528 } else if (isStackingContextItem
) {
1529 // |item| is a stacking context item that can be reused.
1530 ReuseStackingContextItem(aBuilder
, item
);
1532 // |item| is inside a container item that will be destroyed later.
1533 DL_LOGD("%*s Deleted unused item %p", aDepth
, "", item
);
1534 item
->Destroy(aBuilder
);
1538 if (item
->GetType() == DisplayItemType::TYPE_SUBDOCUMENT
) {
1539 IncrementPresShellPaintCount(aBuilder
, item
);
1546 bool RetainedDisplayListBuilder::TrySimpleUpdate(
1547 const nsTArray
<nsIFrame
*>& aModifiedFrames
,
1548 nsTArray
<nsIFrame
*>& aOutFramesWithProps
) {
1549 if (!mBuilder
.IsReusingStackingContextItems()) {
1553 RDL::MarkAllAncestorFrames(aModifiedFrames
, aOutFramesWithProps
);
1554 RDL::CollectStackingContextItems(&mBuilder
, &mList
, RootReferenceFrame());
1559 PartialUpdateResult
RetainedDisplayListBuilder::AttemptPartialUpdate(
1560 nscolor aBackstop
) {
1561 DL_LOGI("(%p) RDL - AttemptPartialUpdate, root frame: %p", this,
1562 RootReferenceFrame());
1564 mBuilder
.RemoveModifiedWindowRegions();
1566 if (mBuilder
.ShouldSyncDecodeImages()) {
1567 DL_LOGI("RDL - Sync decoding images");
1568 MarkFramesWithItemsAndImagesModified(&mList
);
1571 mBuilder
.InvalidateCaretFramesIfNeeded();
1573 // We set the override dirty regions during ComputeRebuildRegion or in
1574 // DisplayPortUtils::InvalidateForDisplayPortChange. The display port change
1575 // also marks the frame modified, so those regions are cleared here as well.
1576 AutoClearFramePropsArray
modifiedFrames(Data()->GetModifiedFrameCount());
1577 AutoClearFramePropsArray
framesWithProps(64);
1578 GetModifiedAndFramesWithProps(&modifiedFrames
.Frames(),
1579 &framesWithProps
.Frames());
1581 if (!ShouldBuildPartial(modifiedFrames
.Frames())) {
1582 // Do not allow partial builds if the |ShouldBuildPartial()| heuristic
1584 mBuilder
.SetPartialBuildFailed(true);
1585 return PartialUpdateResult::Failed
;
1588 nsRect modifiedDirty
;
1589 nsDisplayList
modifiedDL(&mBuilder
);
1590 nsIFrame
* modifiedAGR
= nullptr;
1591 PartialUpdateResult result
= PartialUpdateResult::NoChange
;
1592 const bool simpleUpdate
=
1593 TrySimpleUpdate(modifiedFrames
.Frames(), framesWithProps
.Frames());
1595 mBuilder
.EnterPresShell(RootReferenceFrame());
1597 if (!simpleUpdate
) {
1598 if (!ComputeRebuildRegion(modifiedFrames
.Frames(), &modifiedDirty
,
1599 &modifiedAGR
, framesWithProps
.Frames()) ||
1600 !PreProcessDisplayList(&mList
, modifiedAGR
, result
,
1601 RootReferenceFrame(), nullptr)) {
1602 DL_LOGI("RDL - Partial update aborted");
1603 mBuilder
.SetPartialBuildFailed(true);
1604 mBuilder
.LeavePresShell(RootReferenceFrame(), nullptr);
1605 mList
.DeleteAll(&mBuilder
);
1606 return PartialUpdateResult::Failed
;
1609 modifiedDirty
= mBuilder
.GetVisibleRect();
1612 // This is normally handled by EnterPresShell, but we skipped it so that we
1613 // didn't call MarkFrameForDisplayIfVisible before ComputeRebuildRegion.
1614 nsIScrollableFrame
* sf
=
1615 RootReferenceFrame()->PresShell()->GetRootScrollFrameAsScrollable();
1617 nsCanvasFrame
* canvasFrame
= do_QueryFrame(sf
->GetScrolledFrame());
1619 mBuilder
.MarkFrameForDisplayIfVisible(canvasFrame
, RootReferenceFrame());
1623 nsRect rootOverflow
= RootOverflowRect();
1624 modifiedDirty
.IntersectRect(modifiedDirty
, rootOverflow
);
1626 mBuilder
.SetDirtyRect(modifiedDirty
);
1627 mBuilder
.SetPartialUpdate(true);
1628 mBuilder
.SetPartialBuildFailed(false);
1630 DL_LOGI("RDL - Starting display list build");
1631 RootReferenceFrame()->BuildDisplayListForStackingContext(&mBuilder
,
1633 DL_LOGI("RDL - Finished display list build");
1635 if (!modifiedDL
.IsEmpty()) {
1636 nsLayoutUtils::AddExtraBackgroundItems(
1637 &mBuilder
, &modifiedDL
, RootReferenceFrame(),
1638 nsRect(nsPoint(0, 0), rootOverflow
.Size()), rootOverflow
, aBackstop
);
1640 mBuilder
.SetPartialUpdate(false);
1642 if (mBuilder
.PartialBuildFailed()) {
1643 DL_LOGI("RDL - Partial update failed!");
1644 mBuilder
.LeavePresShell(RootReferenceFrame(), nullptr);
1645 mBuilder
.ClearReuseableDisplayItems();
1646 mList
.DeleteAll(&mBuilder
);
1647 modifiedDL
.DeleteAll(&mBuilder
);
1648 Metrics()->mPartialUpdateFailReason
= PartialUpdateFailReason::Content
;
1649 return PartialUpdateResult::Failed
;
1652 // printf_stderr("Painting --- Modified list (dirty %d,%d,%d,%d):\n",
1653 // modifiedDirty.x, modifiedDirty.y, modifiedDirty.width,
1654 // modifiedDirty.height);
1655 // nsIFrame::PrintDisplayList(&mBuilder, modifiedDL);
1657 // |modifiedDL| can sometimes be empty here. We still perform the
1658 // display list merging to prune unused items (for example, items that
1659 // are not visible anymore) from the old list.
1660 // TODO: Optimization opportunity. In this case, MergeDisplayLists()
1661 // unnecessarily creates a hashtable of the old items.
1662 // TODO: Ideally we could skip this if result is NoChange, but currently when
1663 // we call RestoreState on nsDisplayWrapList it resets the clip to the base
1664 // clip, and we need the UpdateBounds call (within MergeDisplayLists) to
1665 // move it to the correct inner clip.
1666 if (!simpleUpdate
) {
1667 Maybe
<const ActiveScrolledRoot
*> dummy
;
1668 if (MergeDisplayLists(&modifiedDL
, &mList
, &mList
, dummy
)) {
1669 result
= PartialUpdateResult::Updated
;
1672 MOZ_ASSERT(mList
.IsEmpty());
1673 mList
= std::move(modifiedDL
);
1674 mBuilder
.ClearReuseableDisplayItems();
1675 result
= PartialUpdateResult::Updated
;
1679 if (DL_LOG_TEST(LogLevel::Verbose
)) {
1680 printf_stderr("Painting --- Display list:\n");
1681 nsIFrame::PrintDisplayList(&mBuilder
, mList
);
1685 mBuilder
.LeavePresShell(RootReferenceFrame(), List());
1689 nsRect
RetainedDisplayListBuilder::RootOverflowRect() const {
1690 const nsIFrame
* rootReferenceFrame
= RootReferenceFrame();
1691 nsRect rootOverflowRect
= rootReferenceFrame
->InkOverflowRectRelativeToSelf();
1692 const nsPresContext
* presContext
= rootReferenceFrame
->PresContext();
1693 if (!rootReferenceFrame
->GetParent() &&
1694 presContext
->IsRootContentDocumentCrossProcess() &&
1695 presContext
->HasDynamicToolbar()) {
1696 rootOverflowRect
.SizeTo(nsLayoutUtils::ExpandHeightForDynamicToolbar(
1697 presContext
, rootOverflowRect
.Size()));
1700 return rootOverflowRect
;
1703 } // namespace mozilla