Replace the current contiguity check for composited scrolling

Source/WebCore/rendering/RenderLayer.cpp

Index: Source/WebCore/rendering/RenderLayer.cpp
diff --git a/Source/WebCore/rendering/RenderLayer.cpp b/Source/WebCore/rendering/RenderLayer.cpp
index a4e858918d1c996e8b51d61a3d0b441c40d97458..4109c54b58f88f44ee6c64c212edafe4168964de 100644
--- a/Source/WebCore/rendering/RenderLayer.cpp
+++ b/Source/WebCore/rendering/RenderLayer.cpp
@@ -154,7 +154,7 @@ RenderLayer::RenderLayer(RenderLayerModelObject* renderer)
     , m_hasOutOfFlowPositionedDescendant(false)
     , m_hasOutOfFlowPositionedDescendantDirty(true)
     , m_needsCompositedScrolling(false)
-    , m_descendantsAreContiguousInStackingOrder(false)
+    , m_canBePromotedToStackingContainer(false)
     , m_isRootLayer(renderer->isRenderView())
     , m_usedTransparency(false)
     , m_paintingInsideReflection(false)
@@ -522,159 +522,6 @@ 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
-//
-// So for node A in the example above we would have:
-//   maxStackIndex = 1
-//   minStackIndex = -1
-//   numSCDecendants = 2
-//
-// and so,
-//       maxStackIndex - minStackIndex == numSCDescendants
-//  ===>                      1 - (-1) == 2
-//  ===>                             2 == 2
-//
-//  Since this is true, A can safely become a stacking container.
-//  Now, for node C we have:
-//
-//   maxStackIndex = 4
-//   minStackIndex = 0 <-- because C has stacking index 0.
-//   numSCDecendants = 2
-//
-// and so,
-//       maxStackIndex - minStackIndex == numSCDescendants
-//  ===>                         4 - 0 == 2
-//  ===>                             4 == 2
-//
-// 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:
-//
-//   maxStackIndex = 3
-//   minStackIndex = 0 <-- because C has stacking index 0.
-//   numSCDecendants = 3
-//
-// and so,
-//       maxStackIndex - minStackIndex == numSCDescendants
-//  ===>                         3 - 0 == 3
-//  ===>                             3 == 3
-//
-//  And we would conclude that C could be promoted.
-void RenderLayer::updateDescendantsAreContiguousInStackingOrder()
-{
-    if (!isStackingContext() || !acceleratedCompositingForOverflowScrollEnabled())
-        return;
-
-    ASSERT(!m_normalFlowListDirty);
-    ASSERT(!m_zOrderListsDirty);
-
-    OwnPtr<Vector<RenderLayer*> > posZOrderList;
-    OwnPtr<Vector<RenderLayer*> > negZOrderList;
-    rebuildZOrderLists(StopAtStackingContexts, posZOrderList, negZOrderList);
-
-    // Create a reverse lookup.
-    HashMap<const RenderLayer*, int> lookup;
-
-    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--);
-        }
-    }
-
-    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++);
-        }
-    }
-
-    int minIndex = 0;
-    int maxIndex = 0;
-    int count = 0;
-    bool firstIteration = true;
-    updateDescendantsAreContiguousInStackingOrderRecursive(lookup, minIndex, maxIndex, count, firstIteration);
-}
-
-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;
-    }
-
-    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);
-        }
-    }
-
-    if (!isStackingContext()) {
-        bool newValue = maxIndex - minIndex == count;
-        bool didUpdate = newValue != m_descendantsAreContiguousInStackingOrder;
-        m_descendantsAreContiguousInStackingOrder = newValue;
-        if (didUpdate)
-            updateNeedsCompositedScrolling();
-    }
-}
-
 static inline bool isPositionedContainer(const RenderLayer* layer)
 {
     // FIXME: This is not in sync with containingBlock.
@@ -819,6 +666,177 @@ void RenderLayer::getPaintOrderLists(RenderLayer* ancestorStackingContext,
     }
 }
 
+// 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.
+//
+// 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.
+//
+// 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)).
+//
+// Some examples:
+// C = currentLayer
+// - = negative z-order child of currentLayer
+// + = positive z-order child of currentLayer
+// A = positioned ancestor of currentLayer
+// x = any other RenderLayer in the list
+//
+//        original                    |   zOrderListBeforePromote    |  zOrderListAfterPromote
+//        zOrderListBeforePromote     |  after inserting C as above  |
+//     ---------------------------------------------------------------------------------------
+// (1)     x---+++x                   |  x---C+++x                   |     xCx
+// (2)     x---+A++x                  |  x---+AC++x                  |     xACx
+// (3)     x-x--+++x                  |  x-x--C+++x                  |     xxCx
+// (4)     xxA++x                     |  xxAC++x                     |     xxACx
+//
+// 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.
+//
+// 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 an 'A'
+// in zOrderListAfterPromote, this indicates that there is an extra layer
+// (the 'A') 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.
+//
+// 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.
+//
+// Finally in example (4), we would match 'xxAC' 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.
+static bool compareLayerListsBeforeAndAfterPromote(const RenderLayer* currentLayer,
+    const Vector<RenderLayer*>* posZOrderListBeforePromote,
+    const Vector<RenderLayer*>* negZOrderListBeforePromote,
+    const Vector<RenderLayer*>* posZOrderListAfterPromote,
+    const Vector<RenderLayer*>* negZOrderListAfterPromote,
+    const size_t sizeBeforePromote,
+    const size_t sizeAfterPromote,
+    const StackingOrderDirection direction)
+{
+    for (size_t index = 0; index < sizeBeforePromote && index < sizeAfterPromote; index++) {
+        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.
+        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.
+//
+// For more details on how the lists will be compared, see the comment and
+// examples for compareLayerListsBeforeAndAfterPromote().
+void RenderLayer::updateCanBeStackingContainer(RenderLayer* ancestorStackingContext)
+{
+    ASSERT(!isStackingContext());
+
+    // FIXME: We can early-out of this function more
+    // often if we maintain a dirty bit for the
+    // m_canBePromotedToStackingContainer property
+    // (https://bugs.webkit.org/show_bug.cgi?id=109966)

[Ian Vollick, 2013/04/16 19:24:33]

That patch is a prereq for this, so we don't need this comment.

[hartmanng, 2013/04/17 20:21:53]

Done.

+
+    OwnPtr<Vector<RenderLayer*> > posZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > posZOrderListAfterPromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListAfterPromote;
+
+    getPaintOrderLists(ancestorStackingContext,
+        posZOrderListBeforePromote, negZOrderListBeforePromote,
+        posZOrderListAfterPromote, negZOrderListAfterPromote);
+
+    size_t posZOrderListSizeBeforePromote = posZOrderListBeforePromote ? posZOrderListBeforePromote->size() : 0;
+    size_t negZOrderListSizeBeforePromote = negZOrderListBeforePromote ? negZOrderListBeforePromote->size() : 0;
+    size_t posZOrderListSizeAfterPromote = posZOrderListAfterPromote ? posZOrderListAfterPromote->size() : 0;
+    size_t negZOrderListSizeAfterPromote = negZOrderListAfterPromote ? negZOrderListAfterPromote->size() : 0;
+
+    size_t sizeBeforePromote = posZOrderListSizeBeforePromote + negZOrderListSizeBeforePromote;
+    size_t sizeAfterPromote = posZOrderListSizeAfterPromote + negZOrderListSizeAfterPromote;
+
+    bool canPromote = compareLayerListsBeforeAndAfterPromote(this, posZOrderListBeforePromote.get(), negZOrderListBeforePromote.get(),
+        posZOrderListAfterPromote.get(), negZOrderListAfterPromote.get(),
+        sizeBeforePromote, sizeAfterPromote, FromBackground)
+        && compareLayerListsBeforeAndAfterPromote(this, posZOrderListBeforePromote.get(), negZOrderListBeforePromote.get(),
+            posZOrderListAfterPromote.get(), negZOrderListAfterPromote.get(),
+            sizeBeforePromote, sizeAfterPromote, FromForeground);
+
+#if USE(ACCELERATED_COMPOSITING)

[Ian Vollick, 2013/04/16 19:24:33]

These guards can go now.

[hartmanng, 2013/04/17 20:21:53]

Done.

+    bool didUpdate = (canPromote != m_canBePromotedToStackingContainer);
+#endif
+
+    m_canBePromotedToStackingContainer = canPromote;
+
+#if USE(ACCELERATED_COMPOSITING)
+    if (didUpdate)
+        updateNeedsCompositedScrolling();
+#endif
+}
+
+void RenderLayer::updateCanBeStackingContainerRecursively(RenderLayer* ancestorStackingContext)
+{
+    if (this != ancestorStackingContext) {
+        if (isStackingContext())
+            return;
+
+        updateCanBeStackingContainer(ancestorStackingContext);
+    }
+
+    if (m_hasVisibleDescendant) {
+        for (RenderLayer* child = firstChild(); child; child = child->nextSibling()) {
+            // Ignore reflections.
+            if (!m_reflection || reflectionLayer() != child)
+                child->updateCanBeStackingContainerRecursively(ancestorStackingContext);
+        }
+    }
+}
+
 String RenderLayer::paintOrderListsAsText()
 {
     OwnPtr<Vector<RenderLayer*> > posZOrderListBeforePromote;
@@ -1217,7 +1235,7 @@ bool RenderLayer::canBeStackingContainer() const
     if (isStackingContext() || !stackingContainer())
         return true;
 
-    return m_descendantsAreContiguousInStackingOrder;
+    return m_canBePromotedToStackingContainer;
 }
 
 void RenderLayer::setHasVisibleContent()
@@ -5896,7 +5914,7 @@ void RenderLayer::collectLayers(bool includeHiddenLayers, CollectLayersBehavior
 
 void RenderLayer::updateLayerListsIfNeeded()
 {
-    bool shouldUpdateDescendantsAreContiguousInStackingOrder = isStackingContext() && (m_zOrderListsDirty || m_normalFlowListDirty);
+    bool shouldUpdateCanBeStackingContainer = acceleratedCompositingForOverflowScrollEnabled() && isStackingContext() && (m_zOrderListsDirty || m_normalFlowListDirty);
     updateZOrderLists();
     updateNormalFlowList();
 
@@ -5905,8 +5923,11 @@ void RenderLayer::updateLayerListsIfNeeded()
         reflectionLayer->updateNormalFlowList();
     }
 
-    if (shouldUpdateDescendantsAreContiguousInStackingOrder) {
-        updateDescendantsAreContiguousInStackingOrder();
+    if (shouldUpdateCanBeStackingContainer) {
+        // call UpdateCanBeStackingContainer for all descendants,
+        // passing self in as ancestor stacking context.
+        updateCanBeStackingContainerRecursively(this);
+
         // The above function can cause us to update m_needsCompositedScrolling
         // and dirty our layer lists. Refresh them if necessary.
         updateZOrderLists();