Bug 1159042 - p4. Make mDirtyRoots manage roots in preferred depth order - r=dbaron
authorGerald Squelart <gsquelart@mozilla.com>
Tue, 11 Dec 2018 20:32:56 +0000
changeset 450144 6c1abb10067feb7e8161ee8f0a93a5ef8dc75ff2
parent 450143 e5b84b579c5403898d390188c877d52831c0cce1
child 450145 60524976c8f66f4ebfc93b7fb17fd850f2c6f352
push id35190
push userccoroiu@mozilla.com
push dateWed, 12 Dec 2018 05:10:47 +0000
treeherdermozilla-central@5bcbe5232a26 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdbaron
bugs1159042
milestone66.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
@@ -562,41 +562,73 @@ class MOZ_STACK_CLASS AutoPointerEventTa
   }
 
  private:
   RefPtr<PresShell> mShell;
   AutoWeakFrame mWeakFrame;
   nsIContent** mTargetContent;
 };
 
-void nsIPresShell::DirtyRootsList::AppendElement(nsIFrame* aFrame) {
-  mList.AppendElement(aFrame);
-}
-
-void nsIPresShell::DirtyRootsList::RemoveElement(nsIFrame* aFrame) {
+void 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(); }
 
 bool nsIPresShell::DirtyRootsList::Contains(nsIFrame* aFrame) const {
   return mList.Contains(aFrame);
 }
 
 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;
 
@@ -1931,17 +1963,17 @@ nsresult PresShell::ResizeReflowIgnoreOv
       {
         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) {
@@ -2061,17 +2093,17 @@ void PresShell::NotifyDestroyingFrame(ns
 
   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;
     }
@@ -2639,17 +2671,17 @@ void PresShell::FrameNeedsReflow(nsIFram
     // 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
 
@@ -4292,32 +4324,17 @@ void PresShell::ContentRemoved(nsIConten
 }
 
 void 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) {
     // Nothing to do here
     return;
@@ -8570,17 +8587,17 @@ bool PresShell::DoReflow(nsIFrame* targe
 
         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();
@@ -8662,19 +8679,17 @@ bool PresShell::ProcessReflowCommands(bo
       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
@@ -1738,32 +1738,54 @@ class nsIPresShell : public nsStubDocume
   // list.
   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