Bug 1159042 - p4. Make mDirtyRoots manage roots in preferred depth order - r=dbaron
☠☠ backed out by d5a15c64bd40 ☠ ☠
authorGerald Squelart <gsquelart@mozilla.com>
Mon, 26 Nov 2018 23:24:34 +0000
changeset 507376 080b9ceee8eca10edabc249172d7f113c3642873
parent 507375 6a5191742ca1666d8ca6412993195a9096604128
child 507377 db0e173a6ed2ed65c22a2e60bc3f358e3d19d82c
push id1905
push userffxbld-merge
push dateMon, 21 Jan 2019 12:33:13 +0000
treeherdermozilla-release@c2fca1944d8c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdbaron
bugs1159042
milestone65.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1159042 - p4. Make mDirtyRoots manage roots in preferred depth order - r=dbaron When popping a dirty root, take the shallowest one first (so we reflow from outer frames first, to avoid potential duplicate reflow of inner frames). Prevent duplicate roots (to be reworked in a future bug). Differential Revision: https://phabricator.services.mozilla.com/D9490
layout/base/PresShell.cpp
layout/base/nsIPresShell.h
--- a/layout/base/PresShell.cpp
+++ b/layout/base/PresShell.cpp
@@ -586,37 +586,50 @@ public:
 
 private:
   RefPtr<PresShell> mShell;
   AutoWeakFrame mWeakFrame;
   nsIContent** mTargetContent;
 };
 
 void
-nsIPresShell::DirtyRootsList::AppendElement(nsIFrame* aFrame)
-{
-  mList.AppendElement(aFrame);
-}
-
-void
-nsIPresShell::DirtyRootsList::RemoveElement(nsIFrame* aFrame)
+nsIPresShell::DirtyRootsList::Add(nsIFrame* aFrame)
+{
+  // Is this root already scheduled for reflow?
+  // FIXME: This could possibly be changed to a uniqueness assertion, with some
+  // work in ResizeReflowIgnoreOverride (and maybe others?)
+  if (mList.Contains(aFrame)) {
+    // We don't expect frame to change depths.
+    MOZ_ASSERT(aFrame->GetDepthInFrameTree() ==
+               mList[mList.IndexOf(aFrame)].mDepth);
+    return;
+  }
+
+  mList.InsertElementSorted(
+    FrameAndDepth{ aFrame, aFrame->GetDepthInFrameTree() },
+    FrameAndDepth::CompareByReverseDepth{});
+}
+
+void
+nsIPresShell::DirtyRootsList::Remove(nsIFrame* aFrame)
 {
   mList.RemoveElement(aFrame);
 }
 
-void
-nsIPresShell::DirtyRootsList::RemoveElements(nsIFrame* aFrame)
-{
-  mList.RemoveElementsBy([&](nsIFrame* aRoot){ return aRoot == aFrame; });
-}
-
-void
-nsIPresShell::DirtyRootsList::RemoveElementAt(size_t aIndex)
-{
-  return mList.RemoveElementAt(aIndex);
+nsIFrame*
+nsIPresShell::DirtyRootsList::PopShallowestRoot()
+{
+  // List is sorted in order of decreasing depth, so there are no deeper
+  // frames than the last one.
+  const FrameAndDepth& lastFAD = mList.LastElement();
+  nsIFrame* frame = lastFAD.mFrame;
+  // We don't expect frame to change depths.
+  MOZ_ASSERT(frame->GetDepthInFrameTree() == lastFAD.mDepth);
+  mList.RemoveLastElement();
+  return frame;
 }
 
 void
 nsIPresShell::DirtyRootsList::Clear()
 {
   mList.Clear();
 }
 
@@ -627,20 +640,34 @@ nsIPresShell::DirtyRootsList::Contains(n
 }
 
 bool
 nsIPresShell::DirtyRootsList::IsEmpty() const
 {
   return mList.IsEmpty();
 }
 
-size_t
-nsIPresShell::DirtyRootsList::Length() const
-{
-  return mList.Length();
+bool
+nsIPresShell::DirtyRootsList::FrameIsAncestorOfDirtyRoot(nsIFrame* aFrame) const
+{
+  MOZ_ASSERT(aFrame);
+
+  // Look for a path from any dirty roots to aFrame, following GetParent().
+  // This check mirrors what FrameNeedsReflow() would have done if the reflow
+  // root didn't get in the way.
+  for (nsIFrame* dirtyFrame : mList) {
+    do {
+      if (dirtyFrame == aFrame) {
+        return true;
+      }
+      dirtyFrame = dirtyFrame->GetParent();
+    } while (dirtyFrame);
+  }
+
+  return false;
 }
 
 bool PresShell::sDisableNonTestMouseEvents = false;
 
 mozilla::LazyLogModule PresShell::gLog("PresShell");
 
 mozilla::TimeStamp PresShell::sLastInputCreated;
 mozilla::TimeStamp PresShell::sLastInputProcessed;
@@ -2064,17 +2091,17 @@ PresShell::ResizeReflowIgnoreOverride(ns
       {
         nsAutoCauseReflowNotifier crNotifier(this);
         WillDoReflow();
 
         // Kick off a top-down reflow
         AUTO_LAYOUT_PHASE_ENTRY_POINT(GetPresContext(), Reflow);
         nsViewManager::AutoDisableRefresh refreshBlocker(viewManager);
 
-        mDirtyRoots.RemoveElement(rootFrame);
+        mDirtyRoots.Remove(rootFrame);
         DoReflow(rootFrame, true, nullptr);
 
         if (shrinkToFit) {
           const bool reflowAgain = wm.IsVertical() ?
                                 mPresContext->GetVisibleArea().width > aWidth :
                                 mPresContext->GetVisibleArea().height > aHeight;
 
           if (reflowAgain) {
@@ -2200,17 +2227,17 @@ PresShell::NotifyDestroyingFrame(nsIFram
 
   if (!mIgnoreFrameDestruction) {
     if (aFrame->HasImageRequest()) {
       mDocument->StyleImageLoader()->DropRequestsForFrame(aFrame);
     }
 
     mFrameConstructor->NotifyDestroyingFrame(aFrame);
 
-    mDirtyRoots.RemoveElements(aFrame);
+    mDirtyRoots.Remove(aFrame);
 
     // Remove frame properties
     aFrame->DeleteAllProperties();
 
     if (aFrame == mCurrentEventFrame) {
       mCurrentEventContent = aFrame->GetContent();
       mCurrentEventFrame = nullptr;
     }
@@ -2858,17 +2885,17 @@ PresShell::FrameNeedsReflow(nsIFrame *aF
     // Set NS_FRAME_HAS_DIRTY_CHILDREN bits (via nsIFrame::ChildIsDirty)
     // up the tree until we reach either a frame that's already dirty or
     // a reflow root.
     nsIFrame *f = subtreeRoot;
     for (;;) {
       if (FRAME_IS_REFLOW_ROOT(f) || !f->GetParent()) {
         // we've hit a reflow root or the root frame
         if (!wasDirty) {
-          mDirtyRoots.AppendElement(f);
+          mDirtyRoots.Add(f);
           SetNeedLayoutFlush();
         }
 #ifdef DEBUG
         else {
           VerifyHasDirtyRootAncestor(f);
         }
 #endif
 
@@ -4666,32 +4693,17 @@ PresShell::NotifyCounterStylesAreDirty()
 {
   nsAutoCauseReflowNotifier reflowNotifier(this);
   mFrameConstructor->NotifyCounterStylesAreDirty();
 }
 
 bool
 nsIPresShell::FrameIsAncestorOfDirtyRoot(nsIFrame* aFrame) const
 {
-  MOZ_ASSERT(aFrame);
-
-  // Look for a path from any dirty roots to aFrame, following GetParent().
-  // This check mirrors what FrameNeedsReflow() would have done if the reflow
-  // root didn't get in the way.
-  for (nsIFrame* dirtyFrame : mDirtyRoots) {
-    while (dirtyFrame) {
-      if (dirtyFrame == aFrame) {
-        return true;
-      }
-
-      dirtyFrame = dirtyFrame->GetParent();
-    }
-  }
-
-  return false;
+  return mDirtyRoots.FrameIsAncestorOfDirtyRoot(aFrame);
 }
 
 void
 PresShell::ReconstructFrames()
 {
   MOZ_ASSERT(!mFrameConstructor->GetRootFrame() || mDidInitialize,
              "Must not have root frame before initial reflow");
   if (!mDidInitialize || mIsDestroying) {
@@ -9135,17 +9147,17 @@ PresShell::DoReflow(nsIFrame* target, bo
 
         if (f == target) {
           break;
         }
       }
     }
 
     NS_ASSERTION(NS_SUBTREE_DIRTY(target), "Why is the target not dirty?");
-    mDirtyRoots.AppendElement(target);
+    mDirtyRoots.Add(target);
     SetNeedLayoutFlush();
 
     // Clear mFramesToDirty after we've done the NS_SUBTREE_DIRTY(target)
     // assertion so that if it fails it's easier to see what's going on.
 #ifdef NOISY_INTERRUPTIBLE_REFLOW
     printf("mFramesToDirty.Count() == %u\n", mFramesToDirty.Count());
 #endif /* NOISY_INTERRUPTIBLE_REFLOW */
     mFramesToDirty.Clear();
@@ -9232,19 +9244,17 @@ PresShell::ProcessReflowCommands(bool aI
       WillDoReflow();
       AUTO_LAYOUT_PHASE_ENTRY_POINT(GetPresContext(), Reflow);
       nsViewManager::AutoDisableRefresh refreshBlocker(mViewManager);
 
       OverflowChangedTracker overflowTracker;
 
       do {
         // Send an incremental reflow notification to the target frame.
-        int32_t idx = mDirtyRoots.Length() - 1;
-        nsIFrame *target = mDirtyRoots[idx];
-        mDirtyRoots.RemoveElementAt(idx);
+        nsIFrame *target = mDirtyRoots.PopShallowestRoot();
 
         if (!NS_SUBTREE_DIRTY(target)) {
           // It's not dirty anymore, which probably means the notification
           // was posted in the middle of a reflow (perhaps with a reflow
           // root in the middle).  Don't do anything.
           continue;
         }
 
--- a/layout/base/nsIPresShell.h
+++ b/layout/base/nsIPresShell.h
@@ -1782,32 +1782,58 @@ protected:
   AutoWeakFrame*            mAutoWeakFrames;
 
   // A hash table of heap allocated weak frames.
   nsTHashtable<nsPtrHashKey<WeakFrame>> mWeakFrames;
 
   class DirtyRootsList
   {
   public:
-    void AppendElement(nsIFrame* aFrame);
-    void RemoveElement(nsIFrame* aFrame);
-    void RemoveElements(nsIFrame* aFrame);
-    void RemoveElementAt(size_t aIndex);
+    // Add a dirty root.
+    void Add(nsIFrame* aFrame);
+    // Remove this frame if present.
+    void Remove(nsIFrame* aFrame);
+    // Remove and return one of the shallowest dirty roots from the list.
+    // (If two roots are at the same depth, order is indeterminate.)
+    nsIFrame* PopShallowestRoot();
+    // Remove all dirty roots.
     void Clear();
+    // Is this frame one of the dirty roots?
     bool Contains(nsIFrame* aFrame) const;
+    // Are there no dirty roots?
     bool IsEmpty() const;
-    size_t Length() const;
-    auto begin() const { return mList.begin(); }
-    auto begin() { return mList.begin(); }
-    auto end() const { return mList.end(); }
-    auto end() { return mList.end(); }
-    auto& operator[](size_t i) { return mList[i]; }
+    // Is the given frame an ancestor of any dirty root?
+    bool FrameIsAncestorOfDirtyRoot(nsIFrame* aFrame) const;
 
   private:
-    nsTArray<nsIFrame*> mList;
+    struct FrameAndDepth
+    {
+      nsIFrame* mFrame;
+      const uint32_t mDepth;
+
+      // Easy conversion to nsIFrame*, as it's the most likely need.
+      operator nsIFrame*() const { return mFrame; }
+
+      // Used to sort by reverse depths, i.e., deeper < shallower.
+      class CompareByReverseDepth
+      {
+      public:
+        bool Equals(const FrameAndDepth& aA, const FrameAndDepth& aB) const
+        {
+          return aA.mDepth == aB.mDepth;
+        }
+        bool LessThan(const FrameAndDepth& aA, const FrameAndDepth& aB) const
+        {
+          // Reverse depth! So '>' instead of '<'.
+          return aA.mDepth > aB.mDepth;
+        }
+      };
+    };
+    // List of all known dirty roots, sorted by decreasing depths.
+    nsTArray<FrameAndDepth> mList;
   };
 
   // Reflow roots that need to be reflowed.
   DirtyRootsList mDirtyRoots;
 
 #ifdef MOZ_GECKO_PROFILER
   // These two fields capture call stacks of any changes that require a restyle
   // or a reflow. Only the first change per restyle / reflow is recorded (the