1 files changed, 208 insertions, 0 deletions
diff --git a/layout/base/OverflowChangedTracker.h b/layout/base/OverflowChangedTracker.h
new file mode 100644
index 0000000000..f79962e82f
--- /dev/null
+++ b/layout/base/OverflowChangedTracker.h
@@ -0,0 +1,208 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_OverflowChangedTracker_h
+#define mozilla_OverflowChangedTracker_h
+
+#include "nsIFrame.h"
+#include "nsContainerFrame.h"
+#include "mozilla/SplayTree.h"
+
+namespace mozilla {
+
+/**
+ * Helper class that collects a list of frames that need
+ * UpdateOverflow() called on them, and coalesces them
+ * to avoid walking up the same ancestor tree multiple times.
+ */
+class OverflowChangedTracker {
+ public:
+  enum ChangeKind {
+    /**
+     * The frame was explicitly added as a result of
+     * nsChangeHint_UpdatePostTransformOverflow and hence may have had a style
+     * change that changes its geometry relative to parent, without reflowing.
+     */
+    TRANSFORM_CHANGED,
+    /**
+     * The overflow areas of children have changed
+     * and we need to call UpdateOverflow on the frame.
+     */
+    CHILDREN_CHANGED,
+  };
+
+  OverflowChangedTracker() : mSubtreeRoot(nullptr) {}
+
+  ~OverflowChangedTracker() {
+    NS_ASSERTION(mEntryList.empty(), "Need to flush before destroying!");
+  }
+
+  /**
+   * Add a frame that has had a style change, and needs its
+   * overflow updated.
+   *
+   * If there are pre-transform overflow areas stored for this
+   * frame, then we will call FinishAndStoreOverflow with those
+   * areas instead of UpdateOverflow().
+   *
+   * If the overflow area changes, then UpdateOverflow will also
+   * be called on the parent.
+   */
+  void AddFrame(nsIFrame* aFrame, ChangeKind aChangeKind) {
+    MOZ_ASSERT(
+        aFrame->FrameMaintainsOverflow(),
+        "Why add a frame that doesn't maintain overflow to the tracker?");
+    uint32_t depth = aFrame->GetDepthInFrameTree();
+    Entry* entry = nullptr;
+    if (!mEntryList.empty()) {
+      entry = mEntryList.find(Entry(aFrame, depth));
+    }
+    if (entry == nullptr) {
+      // Add new entry.
+      mEntryList.insert(new Entry(aFrame, depth, aChangeKind));
+    } else {
+      // Update the existing entry if the new value is stronger.
+      entry->mChangeKind = std::max(entry->mChangeKind, aChangeKind);
+    }
+  }
+
+  /**
+   * Remove a frame.
+   */
+  void RemoveFrame(nsIFrame* aFrame) {
+    if (mEntryList.empty()) {
+      return;
+    }
+
+    uint32_t depth = aFrame->GetDepthInFrameTree();
+    if (mEntryList.find(Entry(aFrame, depth))) {
+      delete mEntryList.remove(Entry(aFrame, depth));
+    }
+  }
+
+  /**
+   * Set the subtree root to limit overflow updates. This must be set if and
+   * only if currently reflowing aSubtreeRoot, to ensure overflow changes will
+   * still propagate correctly.
+   */
+  void SetSubtreeRoot(const nsIFrame* aSubtreeRoot) {
+    mSubtreeRoot = aSubtreeRoot;
+  }
+
+  /**
+   * Update the overflow of all added frames, and clear the entry list.
+   *
+   * Start from those deepest in the frame tree and works upwards. This stops
+   * us from processing the same frame twice.
+   */
+  void Flush() {
+    while (!mEntryList.empty()) {
+      Entry* entry = mEntryList.removeMin();
+      nsIFrame* frame = entry->mFrame;
+
+      bool overflowChanged = false;
+      if (entry->mChangeKind == CHILDREN_CHANGED) {
+        // Need to union the overflow areas of the children.
+        // Only update the parent if the overflow changes.
+        overflowChanged = frame->UpdateOverflow();
+      } else {
+        // Take a faster path that doesn't require unioning the overflow areas
+        // of our children.
+
+        NS_ASSERTION(
+            frame->GetProperty(nsIFrame::DebugInitialOverflowPropertyApplied()),
+            "InitialOverflowProperty must be set first.");
+
+        OverflowAreas* overflow =
+            frame->GetProperty(nsIFrame::InitialOverflowProperty());
+        if (overflow) {
+          // FinishAndStoreOverflow will change the overflow areas passed in,
+          // so make a copy.
+          OverflowAreas overflowCopy = *overflow;
+          frame->FinishAndStoreOverflow(overflowCopy, frame->GetSize());
+        } else {
+          nsRect bounds(nsPoint(0, 0), frame->GetSize());
+          OverflowAreas boundsOverflow;
+          boundsOverflow.SetAllTo(bounds);
+          frame->FinishAndStoreOverflow(boundsOverflow, bounds.Size());
+        }
+
+        // We can't tell if the overflow changed, so be conservative
+        overflowChanged = true;
+      }
+
+      // If the frame style changed (e.g. positioning offsets)
+      // then we need to update the parent with the overflow areas of its
+      // children.
+      if (overflowChanged) {
+        nsIFrame* parent = frame->GetParent();
+
+        // It's possible that the parent is already in a nondisplay context,
+        // should not add it to the list if that's true.
+        if (parent && parent != mSubtreeRoot &&
+            parent->FrameMaintainsOverflow()) {
+          Entry* parentEntry =
+              mEntryList.find(Entry(parent, entry->mDepth - 1));
+          if (parentEntry) {
+            parentEntry->mChangeKind =
+                std::max(parentEntry->mChangeKind, CHILDREN_CHANGED);
+          } else {
+            mEntryList.insert(
+                new Entry(parent, entry->mDepth - 1, CHILDREN_CHANGED));
+          }
+        }
+      }
+      delete entry;
+    }
+  }
+
+ private:
+  struct Entry : SplayTreeNode<Entry> {
+    Entry(nsIFrame* aFrame, uint32_t aDepth,
+          ChangeKind aChangeKind = CHILDREN_CHANGED)
+        : mFrame(aFrame), mDepth(aDepth), mChangeKind(aChangeKind) {}
+
+    bool operator==(const Entry& aOther) const {
+      return mFrame == aOther.mFrame;
+    }
+
+    /**
+     * Sort by *reverse* depth in the tree, and break ties with
+     * the frame pointer.
+     */
+    bool operator<(const Entry& aOther) const {
+      if (mDepth == aOther.mDepth) {
+        return mFrame < aOther.mFrame;
+      }
+      return mDepth > aOther.mDepth; /* reverse, want "min" to be deepest */
+    }
+
+    static int compare(const Entry& aOne, const Entry& aTwo) {
+      if (aOne == aTwo) {
+        return 0;
+      } else if (aOne < aTwo) {
+        return -1;
+      } else {
+        return 1;
+      }
+    }
+
+    nsIFrame* mFrame;
+    /* Depth in the frame tree */
+    uint32_t mDepth;
+    ChangeKind mChangeKind;
+  };
+
+  /* A list of frames to process, sorted by their depth in the frame tree */
+  SplayTree<Entry, Entry> mEntryList;
+
+  /* Don't update overflow of this frame or its ancestors. */
+  const nsIFrame* mSubtreeRoot;
+};
+
+}  // namespace mozilla
+
+#endif