Replace the current contiguity check for composited scrolling

Source/core/rendering/RenderLayer.cpp

Index: Source/core/rendering/RenderLayer.cpp
diff --git a/Source/core/rendering/RenderLayer.cpp b/Source/core/rendering/RenderLayer.cpp
index 362dc9168ae15cb6493461b4e29d4a986760e664..6d147eb20354ec44726495482ff4a1bbbf678019 100644
--- a/Source/core/rendering/RenderLayer.cpp
+++ b/Source/core/rendering/RenderLayer.cpp
@@ -75,6 +75,7 @@
 #include "core/platform/ScrollAnimator.h"
 #include "core/platform/Scrollbar.h"
 #include "core/platform/ScrollbarTheme.h"
+#include "core/platform/chromium/TraceEvent.h"
 #include "core/platform/graphics/FloatPoint3D.h"
 #include "core/platform/graphics/FloatRect.h"
 #include "core/platform/graphics/Gradient.h"
@@ -147,8 +148,8 @@ RenderLayer::RenderLayer(RenderLayerModelObject* renderer)
     , m_hasUnclippedDescendant(false)
     , m_forceNeedsCompositedScrolling(DoNotForceCompositedScrolling)
     , m_needsCompositedScrolling(false)
-    , m_descendantsAreContiguousInStackingOrder(false)
-    , m_descendantsAreContiguousInStackingOrderDirty(true)
+    , m_canBePromotedToStackingContainer(false)
+    , m_canBePromotedToStackingContainerDirty(true)
     , m_isRootLayer(renderer->isRenderView())
     , m_usedTransparency(false)
     , m_paintingInsideReflection(false)
@@ -516,153 +517,185 @@ bool RenderLayer::acceleratedCompositingForOverflowScrollEnabled() const
         && renderer()->frame()->page()->settings()->acceleratedCompositingForOverflowScrollEnabled();
 }
 
-// If we are a stacking container, then this function will determine if our
-// descendants for a contiguous block in stacking order. This is required in
-// order for an element to be safely promoted to a stacking container. It is safe
-// to become a stacking container if this change would not alter the stacking
-// order of layers on the page. That can only happen if a non-descendant appear
-// between us and our descendants in stacking order. Here's an example:
-//
-//                                 this
-//                                /  |  \.
-//                               A   B   C
-//                              /\   |   /\.
-//                             0 -8  D  2  7
-//                                   |
-//                                   5
-//
-// I've labeled our normal flow descendants A, B, C, and D, our stacking
-// container descendants with their z indices, and us with 'this' (we're a
-// stacking container and our zIndex doesn't matter here). These nodes appear in
-// three lists: posZOrder, negZOrder, and normal flow (keep in mind that normal
-// flow layers don't overlap). So if we arrange these lists in order we get our
-// stacking order:
-//
-//                     [-8], [A-D], [0, 2, 5, 7]--> pos z-order.
-//                       |     |
-//        Neg z-order. <-+     +--> Normal flow descendants.
-//
-// We can then assign new, 'stacking' order indices to these elements as follows:
-//
-//                     [-8], [A-D], [0, 2, 5, 7]
-// 'Stacking' indices:  -1     0     1  2  3  4
-//
-// Note that the normal flow descendants can share an index because they don't
-// stack/overlap. Now our problem becomes very simple: a layer can safely become
-// a stacking container if the stacking-order indices of it and its descendants
-// appear in a contiguous block in the list of stacking indices. This problem
-// can be solved very efficiently by calculating the min/max stacking indices in
-// the subtree, and the number stacking container descendants. Once we have this
-// information, we know that the subtree's indices form a contiguous block if:
-//
-//           maxStackIndex - minStackIndex == numSCDescendants
+enum StackingOrderDirection { FromBackground, FromForeground };
+
+// We'd like to be able to iterate through a single paint order list, but for
+// efficiency's sake, we hang onto two lists instead (namely, the pos and neg
+// z-order lists produced by CollectLayers). This function allows us to index
+// into these two lists as if they were one. It also allows us to index into
+// this virtual list either from the start or from the end (i.e., in either
+// stacking order direction).

[esprehn, 2013/05/07 00:49:16]

This comment is not needed.

[hartmanng, 2013/05/13 17:44:18]

Done.

+static const RenderLayer* getStackingOrderElementAt(const Vector<RenderLayer*>* posZOrderList, const Vector<RenderLayer*>* negZOrderList, const StackingOrderDirection direction, const size_t index)

[esprehn, 2013/05/07 00:49:16]

I'd prefer you remove this method. It just makes the code harder to follow.

[hartmanng, 2013/05/13 17:44:18]

Done.

+{
+    const size_t negZOrderListSize = negZOrderList ? negZOrderList->size() : 0;
+
+    if (direction == FromBackground) {
+        if (index < negZOrderListSize)
+            return negZOrderList->at(index);
+
+        return posZOrderList->at(index - negZOrderListSize);
+    }
+
+    const size_t posZOrderListSize = posZOrderList ? posZOrderList->size() : 0;
+
+    if (index < posZOrderListSize)
+        return posZOrderList->at(posZOrderListSize - index - 1);
+
+    return negZOrderList->at(negZOrderListSize - (index - posZOrderListSize) - 1);
+}
+
+// After promotion, the paint order consists of
+// a) the non-descendants which precede the promoted layer,
+// b) the promoted layer, and
+// c) the non-descendants which succeed the promoted layer.
 //
-// So for node A in the example above we would have:
-//   maxStackIndex = 1
-//   minStackIndex = -1
-//   numSCDecendants = 2
+// If the current layer's descendants form a contiguous block in paint order
+// before promotion, the paint order will consist of
+// a) the non-descendants which precede the current layer and its descendants,
+// b) the current layer and its descendants
+// c) The non-descendants which succeed the current layer and its descendants.
 //
-// and so,
-//       maxStackIndex - minStackIndex == numSCDescendants
-//  ===>                      1 - (-1) == 2
-//  ===>                             2 == 2
+// Sub-lists (a) and (c) should be identical in both paint order lists if
+// and only if the descendants form a contiguous block. In fact, this is the
+// only check we need to perform since the order of the descendants with
+// respect to each other cannot be affected by promotion (i.e., we don't
+// need to worry about sub-list (b)).
 //
-//  Since this is true, A can safely become a stacking container.
-//  Now, for node C we have:
+// Some examples:
+// C = currentLayer
+// - = negative z-order child of currentLayer
+// + = positive z-order child of currentLayer
+// P = positioned ancestor of currentLayer
+// x = any other RenderLayer in the list
 //
-//   maxStackIndex = 4
-//   minStackIndex = 0 <-- because C has stacking index 0.
-//   numSCDecendants = 2
+//        original                    |   zOrderListBeforePromote    |  zOrderListAfterPromote
+//        zOrderListBeforePromote     |  after inserting C as above  |
+//     ---------------------------------------------------------------------------------------
+// (1)     x---+++x                   |  x---C+++x                   |     xCx
+// (2)     x---+P++x                  |  x---+PC++x                  |     xPCx
+// (3)     x-x--+++x                  |  x-x--C+++x                  |     xxCx
+// (4)     xxP++x                     |  xxPC++x                     |     xxPCx
 //
-// and so,
-//       maxStackIndex - minStackIndex == numSCDescendants
-//  ===>                         4 - 0 == 2
-//  ===>                             4 == 2
+// In example (1), we compare sub-list (a) by marching from the left of both
+// lists (zOrderListBeforePromote after inserting C and
+// zOrderListAfterPromote). The first mismatch is at index 1 when we hit '-'
+// and 'C'. That means we have neg z-order descendants. This is a problem if
+// we have a background. Before promotion, this bg would get painted with
+// the current layer (i.e., after the neg z-order descendants), but after
+// promotion the bg would get painted before them. This is a stacking order
+// violation and we can't promote. However, if we don't have a background,
+// we would continue on to the second pass. When comparing from the right,
+// we mismatch on '+' and 'C'. Since we hit 'C' on zOrderListAfterPromote,
+// we know that the children are contiguous, and we will promote.
 //
-// Since this is false, C cannot be safely promoted to a stacking container. This
-// happened because of the elements with z-index 5 and 0. Now if 5 had been a
-// child of C rather than D, and A had no child with Z index 0, we would have had:
+// In example (2), when marching from the left, we'll hit a mismatch again
+// on the second element we look at. This time, since this element is a 'P'
+// in zOrderListAfterPromote, this indicates that there is an extra layer
+// (the 'P') mixed in with the children. This could cause a change in paint
+// order if we promote, so we decide not to and break out of the loop. Note
+// that if the current layer has a background, this would provide a second
+// reason not to opt in, since again we have negative z-order children who
+// would change paint order with respect to our background if we promoted.
 //
-//   maxStackIndex = 3
-//   minStackIndex = 0 <-- because C has stacking index 0.
-//   numSCDecendants = 3
+// In example (3), the discontiguity of the negative z-order children causes
+// us to fail early in our "FromBackground" pass when we try to compare '-'
+// from zOrderListBeforePromote with 'x' in zOrderListAfterPromote.
 //
-// and so,
-//       maxStackIndex - minStackIndex == numSCDescendants
-//  ===>                         3 - 0 == 3
-//  ===>                             3 == 3
+// Finally in example (4), we would match 'xxPC' from the left, then stop
+// since we hit 'C'. Then we would match 'x' from the right, and mismatch
+// on '+' and 'C'. Since we're at 'C' on the zOrderListAfterPromote, we
+// conclude that all the children are contiguous. Since there are no
+// negative z-order children, a background layer is irrelevant in this case.
+// We will opt in, keeping paint order constant.

[esprehn, 2013/05/07 00:49:16]

I'd prefer if you created a much shorter and simpler comment that just explains
the purpose of this method which is decided if making an element that wasn't a
stacking context into one would change the paint order and that you need it to
check for promoting to stacking contexts for scrolling. 

You don't need all these examples in the code. I'd rather a Google doc you send
to blink-dev that describes this whole system.

This comment is crazy long to put inside RenderLayer.cpp. Aim for one short
paragraph.

[hartmanng, 2013/05/13 17:44:18]

Done.

+static bool compareLayerListsBeforeAndAfterPromote(const RenderLayer* currentLayer,
+    const Vector<RenderLayer*>* posZOrderListBeforePromote,
+    const Vector<RenderLayer*>* negZOrderListBeforePromote,
+    const Vector<RenderLayer*>* posZOrderListAfterPromote,
+    const Vector<RenderLayer*>* negZOrderListAfterPromote,
+    const StackingOrderDirection direction)
+{
+    const size_t sizeBeforePromote = (posZOrderListBeforePromote ? posZOrderListBeforePromote->size() : 0) + (negZOrderListBeforePromote ? negZOrderListBeforePromote->size() : 0);
+    const size_t sizeAfterPromote = (posZOrderListAfterPromote ? posZOrderListAfterPromote->size() : 0) + (negZOrderListAfterPromote ? negZOrderListAfterPromote->size() : 0);
+    for (size_t index = 0; index < sizeBeforePromote && index < sizeAfterPromote; index++) {

[esprehn, 2013/05/07 00:49:16]

Use two separate loops please. Get rid of that combined get*() method. You can
achieve the same thing by just reversing the loop start and end and such.

[hartmanng, 2013/05/13 17:44:18]

Done.

+        const RenderLayer* layerBeforePromote = getStackingOrderElementAt(posZOrderListBeforePromote, negZOrderListBeforePromote, direction, index);
+        const RenderLayer* layerAfterPromote = getStackingOrderElementAt(posZOrderListAfterPromote, negZOrderListAfterPromote, direction, index);
+
+        if (layerBeforePromote != layerAfterPromote) {
+            // If we find a mismatch, the only situation where we haven't
+            // necessarily changed paint order yet is if layerAfterPromote
+            // is currentLayer.
+            if (layerAfterPromote != currentLayer)
+                return false;
+
+            // Also, if the current layer has a background, then any
+            // negative z-order children will get between the background
+            // and the rest of the layer.
+            if (direction == FromBackground && currentLayer->renderer()->hasBackground())
+                return false;
+        }
+
+        // To compare the sub-lists (a) and (c) from the comment above, we only
+        // need to march until we hit the currentLayer in the
+        // zOrderListAfterPromote from each direction.

[esprehn, 2013/05/07 00:49:16]

Remove this comment. Comments that reference other comments are bad news.

[hartmanng, 2013/05/13 17:44:18]

Done.

+        if (layerAfterPromote == currentLayer)
+            break;
+    }
+
+    return true;
+}
+
+// Determine whether the current layer can be promoted to a stacking container,
+// given its closest stacking context ancestor. We do this by computing what
+// positive and negative z-order lists would look like before and after
+// promotion, and ensuring that proper stacking order is preserved between the
+// two sets of lists.
 //
-//  And we would conclude that C could be promoted.
-void RenderLayer::updateDescendantsAreContiguousInStackingOrder()
+// For more details on how the lists will be compared, see the comment and
+// examples for compareLayerListsBeforeAndAfterPromote().

[esprehn, 2013/05/07 00:49:16]

Same deal, don't reference across doc comments like this. Just remove the second
line.

[hartmanng, 2013/05/13 17:44:18]

Done.

+void RenderLayer::updateCanBeStackingContainer()
 {
-    if (!m_descendantsAreContiguousInStackingOrderDirty || !isStackingContext() || !acceleratedCompositingForOverflowScrollEnabled())
+    TRACE_EVENT0("blink_rendering", "RenderLayer::updateCanBeStackingContainer");
+
+    if (isStackingContext() || !m_canBePromotedToStackingContainerDirty || !acceleratedCompositingForOverflowScrollEnabled())
         return;
 
-    OwnPtr<Vector<RenderLayer*> > posZOrderList;
-    OwnPtr<Vector<RenderLayer*> > negZOrderList;
-    rebuildZOrderLists(StopAtStackingContexts, posZOrderList, negZOrderList);
+    FrameView* frameView = renderer()->view()->frameView();
+    if (!frameView || !frameView->containsScrollableArea(this))
+        return;
 
-    // Create a reverse lookup.
-    HashMap<const RenderLayer*, int> lookup;
+    RenderLayer* ancestorStackingContext = this->ancestorStackingContext();
+    if (!ancestorStackingContext)
+        return;
 
-    if (negZOrderList) {
-        int stackingOrderIndex = -1;
-        size_t listSize = negZOrderList->size();
-        for (size_t i = 0; i < listSize; ++i) {
-            RenderLayer* currentLayer = negZOrderList->at(listSize - i - 1);
-            if (!currentLayer->isStackingContext())
-                continue;
-            lookup.set(currentLayer, stackingOrderIndex--);
-        }
-    }
+    OwnPtr<Vector<RenderLayer*> > posZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > posZOrderListAfterPromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListAfterPromote;
 
-    if (posZOrderList) {
-        size_t listSize = posZOrderList->size();
-        int stackingOrderIndex = 1;
-        for (size_t i = 0; i < listSize; ++i) {
-            RenderLayer* currentLayer = posZOrderList->at(i);
-            if (!currentLayer->isStackingContext())
-                continue;
-            lookup.set(currentLayer, stackingOrderIndex++);
-        }
-    }
+    collectBeforePromotionZOrderList(ancestorStackingContext, posZOrderListBeforePromote, negZOrderListBeforePromote);
+    collectAfterPromotionZOrderList(ancestorStackingContext, posZOrderListAfterPromote, negZOrderListAfterPromote);
 
-    int minIndex = 0;
-    int maxIndex = 0;
-    int count = 0;
-    bool firstIteration = true;
-    updateDescendantsAreContiguousInStackingOrderRecursive(lookup, minIndex, maxIndex, count, firstIteration);
+    size_t sizeBeforePromote = 0;
+    if (posZOrderListBeforePromote)
+        sizeBeforePromote += posZOrderListBeforePromote->size();
+    if (negZOrderListBeforePromote)
+        sizeBeforePromote += negZOrderListBeforePromote->size();

[esprehn, 2013/05/07 00:49:16]

This size variable is unused. These two if blocks (and the one below) are dead
code.

[hartmanng, 2013/05/13 17:44:18]

Done.

 
-    m_descendantsAreContiguousInStackingOrderDirty = false;
-}
+    size_t sizeAfterPromote = 0;
+    if (posZOrderListAfterPromote)
+        sizeAfterPromote += posZOrderListAfterPromote->size();
+    if (negZOrderListAfterPromote)
+        sizeAfterPromote += negZOrderListAfterPromote->size();

[esprehn, 2013/05/07 00:49:16]

This size variable is unused. Please remove the code.

[hartmanng, 2013/05/13 17:44:18]

Done.

 
-void RenderLayer::updateDescendantsAreContiguousInStackingOrderRecursive(const HashMap<const RenderLayer*, int>& lookup, int& minIndex, int& maxIndex, int& count, bool firstIteration)
-{
-    if (isStackingContext() && !firstIteration) {
-        if (lookup.contains(this)) {
-            minIndex = std::min(minIndex, lookup.get(this));
-            maxIndex = std::max(maxIndex, lookup.get(this));
-            count++;
-        }
-        return;
-    }
+    m_canBePromotedToStackingContainerDirty = false;
 
-    for (RenderLayer* child = firstChild(); child; child = child->nextSibling()) {
-        int childMinIndex = 0;
-        int childMaxIndex = 0;
-        int childCount = 0;
-        child->updateDescendantsAreContiguousInStackingOrderRecursive(lookup, childMinIndex, childMaxIndex, childCount, false);
-        if (childCount) {
-            count += childCount;
-            minIndex = std::min(minIndex, childMinIndex);
-            maxIndex = std::max(maxIndex, childMaxIndex);
-        }
-    }
+    m_canBePromotedToStackingContainer = compareLayerListsBeforeAndAfterPromote(this, posZOrderListBeforePromote.get(), negZOrderListBeforePromote.get(), posZOrderListAfterPromote.get(), negZOrderListAfterPromote.get(), FromBackground);
 
-    if (!isStackingContext()) {
-        m_descendantsAreContiguousInStackingOrder = (maxIndex - minIndex) == count;
-        m_descendantsAreContiguousInStackingOrderDirty = false;
-    }
+    // No need to do the second check.
+    if (!m_canBePromotedToStackingContainer)
+        return;
+
+    m_canBePromotedToStackingContainer = compareLayerListsBeforeAndAfterPromote(this, posZOrderListBeforePromote.get(), negZOrderListBeforePromote.get(), posZOrderListAfterPromote.get(), negZOrderListAfterPromote.get(), FromForeground);
 }
 
 static inline bool isPositionedContainer(const RenderLayer* layer)
@@ -1090,8 +1123,8 @@ bool RenderLayer::canBeStackingContainer() const
     if (isStackingContext() || !ancestorStackingContainer())
         return true;
 
-    ASSERT(!m_descendantsAreContiguousInStackingOrderDirty);
-    return m_descendantsAreContiguousInStackingOrder;
+    ASSERT(!m_canBePromotedToStackingContainerDirty);
+    return m_canBePromotedToStackingContainer;
 }
 
 void RenderLayer::setHasVisibleContent()
@@ -2086,31 +2119,27 @@ bool RenderLayer::needsCompositedScrolling() const
 
 void RenderLayer::updateNeedsCompositedScrolling()
 {
-    if (RenderLayer* ancestor = ancestorStackingContext())
-        ancestor->updateDescendantsAreContiguousInStackingOrder();
+    updateCanBeStackingContainer();
 
     bool needsCompositedScrolling = false;
+    updateDescendantDependentFlags();
 
-    FrameView* frameView = renderer()->view()->frameView();
-    if (frameView && frameView->containsScrollableArea(this)) {
-        updateDescendantDependentFlags();
-
-        bool forceUseCompositedScrolling = acceleratedCompositingForOverflowScrollEnabled()
-            && canBeStackingContainer()
-            && !hasUnclippedDescendant();
+    ASSERT(renderer()->view()->frameView() && renderer()->view()->frameView()->containsScrollableArea(this));
+    bool forceUseCompositedScrolling = acceleratedCompositingForOverflowScrollEnabled()
+        && canBeStackingContainer()
+        && !hasUnclippedDescendant();
 
 #if ENABLE(ACCELERATED_OVERFLOW_SCROLLING)
-        needsCompositedScrolling = forceUseCompositedScrolling || renderer()->style()->useTouchOverflowScrolling();
+    needsCompositedScrolling = forceUseCompositedScrolling || renderer()->style()->useTouchOverflowScrolling();
 #else
-        needsCompositedScrolling = forceUseCompositedScrolling;
+    needsCompositedScrolling = forceUseCompositedScrolling;
 #endif
-        // We gather a boolean value for use with Google UMA histograms to
-        // quantify the actual effects of a set of patches attempting to
-        // relax composited scrolling requirements, thereby increasing the
-        // number of composited overflow divs.
-        if (acceleratedCompositingForOverflowScrollEnabled())
-            HistogramSupport::histogramEnumeration("Renderer.NeedsCompositedScrolling", needsCompositedScrolling, 2);
-    }
+    // We gather a boolean value for use with Google UMA histograms to
+    // quantify the actual effects of a set of patches attempting to
+    // relax composited scrolling requirements, thereby increasing the
+    // number of composited overflow divs.
+    if (acceleratedCompositingForOverflowScrollEnabled())
+        HistogramSupport::histogramEnumeration("Renderer.NeedsCompositedScrolling", needsCompositedScrolling, 2);
 
     setNeedsCompositedScrolling(needsCompositedScrolling);
 }
@@ -5641,7 +5670,7 @@ void RenderLayer::dirtyZOrderLists()
         m_negZOrderList->clear();
     m_zOrderListsDirty = true;
 
-    m_descendantsAreContiguousInStackingOrderDirty = true;
+    m_canBePromotedToStackingContainerDirty = true;
 
     if (!renderer()->documentBeingDestroyed()) {
         compositor()->setNeedsUpdateCompositingRequirementsState();