Add an intermediate function to generate 2 paint-order lists.

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 a599026be97ab4edd54b8d41a7b9007f919dabb6..9d2e15dc80263bb18e55571254d863d34443b1c3 100644
--- a/Source/core/rendering/RenderLayer.cpp
+++ b/Source/core/rendering/RenderLayer.cpp
@@ -78,6 +78,7 @@
 #include "OverflowEvent.h"
 #include "OverlapTestRequestClient.h"
 #include "Page.h"
+#include "PaintOrderLists.h"
 #include "PlatformMouseEvent.h"
 #include "RenderArena.h"
 #include "RenderFlowThread.h"
@@ -101,6 +102,7 @@
 #include "Settings.h"
 #include "ShadowRoot.h"
 #include "SourceGraphic.h"
+#include "StaticHashSetNodeList.h"
 #include "StylePropertySet.h"
 #include "StyleResolver.h"
 #include "TextStream.h"
@@ -669,6 +671,237 @@ void RenderLayer::updateDescendantsAreContiguousInStackingOrderRecursive(const H
     }
 }
 
+static inline bool isPositionedContainer(const RenderLayer* layer)
+{
+    // FIXME: This is not in sync with containingBlock.
+    // RenderObject::canContainFixedPositionedObject() should probably be used
+    // instead.
+    RenderLayerModelObject* layerRenderer = layer->renderer();
+    return layer->isRootLayer() || layerRenderer->isPositioned() || layer->hasTransform();
+}
+
+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).
+static const RenderLayer* getStackingOrderElementAt(const Vector<RenderLayer*>* posZOrderList, const Vector<RenderLayer*>* negZOrderList, const StackingOrderDirection direction, const size_t index)
+{
+    size_t negZOrderListSize = negZOrderList ? negZOrderList->size() : 0;
+
+    if (direction == FromBackground) {
+        if (index < negZOrderListSize)
+            return negZOrderList->at(index);
+
+        return posZOrderList->at(index - negZOrderListSize);
+    }
+
+    size_t posZOrderListSize = posZOrderList ? posZOrderList->size() : 0;
+
+    if (index < posZOrderListSize)
+        return posZOrderList->at(posZOrderListSize - index - 1);
+
+    return negZOrderList->at(negZOrderListSize - (index - posZOrderListSize) - 1);
+}
+
+// Compute what positive and negative z-order lists would look like before and
+// after promotion, so we can later ensure that proper stacking order is
+// preserved between the two sets of lists.
+//
+// A few 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
+//
+// (a) xxxxx-----++a+++x
+// (b) xxx-----c++++++xx
+//
+//
+// Normally the current layer would be painted in the normal flow list if it
+// doesn't already appear in the positive z-order list. However, in the case
+// that the layer has a positioned ancestor, it will paint directly after the
+// positioned ancestor. In example (a), the current layer would be painted in
+// the middle of its own positive z-order children, so promoting would cause a
+// change in paint order (since a promoted layer will paint all of its positive
+// z-order children strictly after it paints itself).
+//
+// In example (b), it is ok to promote the current layer only if it does not
+// have a background. If it has a background, the background gets painted before
+// the layer's negative z-order children, so again, a promotion would cause a
+// change in paint order (causing the background to get painted after the
+// negative z-order children instead of before).
+void RenderLayer::collectBeforeAfterPromotionZOrderLists(
+    RenderLayer* ancestorStackingContext,
+    OwnPtr<Vector<RenderLayer*> >& posZOrderListBeforePromote,
+    OwnPtr<Vector<RenderLayer*> >& negZOrderListBeforePromote,
+    OwnPtr<Vector<RenderLayer*> >& posZOrderListAfterPromote,
+    OwnPtr<Vector<RenderLayer*> >& negZOrderListAfterPromote)
+{
+    // We can't use TemporaryChange<> here since m_needsCompositedScrolling and
+    // m_isNormalFlowOnly are both bitfields, so we have to do it the
+    // old-fashioned way.
+    bool oldNeedsCompositedScrolling = m_needsCompositedScrolling;
+    bool oldIsNormalFlowOnly = m_isNormalFlowOnly;
+
+    // Set the flag on the current layer, then rebuild ancestor stacking
+    // context's lists. This way, we can see the exact effects that promoting
+    // this layer would cause.
+    m_needsCompositedScrolling = false;
+    m_isNormalFlowOnly = shouldBeNormalFlowOnly();
+    ancestorStackingContext->rebuildZOrderLists(StopAtStackingContexts, posZOrderListBeforePromote, negZOrderListBeforePromote, 0);
+
+    m_isNormalFlowOnly = false;
+    m_needsCompositedScrolling = true;
+    ancestorStackingContext->rebuildZOrderLists(StopAtStackingContexts, posZOrderListAfterPromote, negZOrderListAfterPromote, this);

[shawnsingh, 2013/04/18 02:22:14]

I feel uncomfortable about using this function to perform speculative
computations that theoretically should not affect the layer tree state.  This
function calls updateDescendantDependentFlags(), which actually does update a
few stateful pieces of information -- and then it marks those values as "clean".
 So even before this patch, the code is precariously balanced on trusting that
we have correctly (or conservatively) dirtied those flags when needed.  So, to
suddenly call it twice in a place where we don't even intend to change the layer
tree seems prone to errors down the road...

So my question is: do we have any guarantees we will have that we won't
accidentally change the state of the layers and keep it changed by mistake?

[hartmanng, 2013/04/18 17:14:00]

I get your concern, but I think we're pretty safe here.
updateDescendantDependentFlags() does update some state, but it only cleans
what's already dirty. If something gets changed after we finish in this
function, the bits should get set to dirty again, and the next time we clean
we'll be at the same state we would've been anyway.

I'm not a fan of relying on dirty bits too much either, but we _should_ be able
to rely on them - otherwise they're really not doing their job.

FWIW, Ian has a patch (https://codereview.chromium.org/13859006/) which cleans
up a lot of the dirty/clean bit code and should give us a bit more confidence
that these bits are being maintained properly.
Basically, the way I see it, since the only state we change is to clean
already-dirty values, we kind of _want_ to keep it changed, don't we? I don't
see a reason we would want to intentionally keep things dirty longer, the idea
is that everything should be clean by the time we need to use it regardless.

+
+    m_needsCompositedScrolling = oldNeedsCompositedScrolling;
+    m_isNormalFlowOnly = oldIsNormalFlowOnly;
+
+
+    size_t posZOrderListSizeBeforePromote = posZOrderListBeforePromote ? posZOrderListBeforePromote->size() : 0;
+
+    const RenderLayer* positionedAncestor = parent();
+    while (positionedAncestor && !isPositionedContainer(positionedAncestor) && !positionedAncestor->isStackingContext())
+        positionedAncestor = positionedAncestor->parent();
+    if (positionedAncestor && (!isPositionedContainer(positionedAncestor) || positionedAncestor->isStackingContext()))
+        positionedAncestor = 0;
+
+    bool currentLayerIsInPosZOrderListBeforePromote = false;
+
+    for (size_t index = 0; index < posZOrderListSizeBeforePromote; index++) {
+        if (posZOrderListBeforePromote->at(index) == this) {
+            currentLayerIsInPosZOrderListBeforePromote = true;
+            break;
+        }
+    }
+
+    // Insert this into the posZOrderistBeforePromote directly after the
+    // positioned ancestor, if there is one. Otherwise, add it to the very
+    // beginning.
+    //
+    // The current layer will appear in the z-order lists after promotion, so
+    // for a meaningful comparison, we must insert it in the z-order lists
+    // before promotion if it does not appear there already.
+    if (!currentLayerIsInPosZOrderListBeforePromote) {
+        if (!positionedAncestor) {
+            if (!posZOrderListBeforePromote)
+                posZOrderListBeforePromote = adoptPtr(new Vector<RenderLayer*>());
+
+            posZOrderListBeforePromote->prepend(this);
+            posZOrderListSizeBeforePromote++;
+        } else {
+            for (size_t index = 0; index < posZOrderListSizeBeforePromote; index++) {
+                if (posZOrderListBeforePromote->at(index) == positionedAncestor) {
+                    posZOrderListBeforePromote->insert(index + 1, this);
+                    posZOrderListSizeBeforePromote++;
+                    break;
+                }
+            }
+        }
+    }
+}
+
+String RenderLayer::paintOrderListsAsText()
+{
+    OwnPtr<Vector<RenderLayer*> > posZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > posZOrderListAfterPromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListAfterPromote;
+
+    RenderLayer* ancestorStackingContext = this;
+
+    while (ancestorStackingContext) {
+        if (ancestorStackingContext != this && ancestorStackingContext->isStackingContext())
+            break;
+        ancestorStackingContext = ancestorStackingContext->parent();
+    }
+
+    if (!ancestorStackingContext)
+        return String();
+
+    collectBeforeAfterPromotionZOrderLists(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;
+
+    TextStream ts;
+
+    ts << "Layer: " << this << " \"" << name() << "\", z-index: " << renderer()->style()->zIndex() << "\n";
+
+    ts << "  stacking context's paint order list BEFORE promote:\n";
+    for (size_t index = 0; index < sizeBeforePromote; index++) {
+        const RenderLayer* layerBeforePromote = getStackingOrderElementAt(posZOrderListBeforePromote.get(), negZOrderListBeforePromote.get(), FromBackground, index);
+        ts << "    " << layerBeforePromote << " \"" << layerBeforePromote->name() << "\", z-index: " << layerBeforePromote->renderer()->style()->zIndex() << "\n";
+    }
+
+    ts << "  stacking context's paint order list AFTER promote:\n";
+    for (size_t index = 0; index < sizeAfterPromote; index++) {
+        const RenderLayer* layerAfterPromote = getStackingOrderElementAt(posZOrderListAfterPromote.get(), negZOrderListAfterPromote.get(), FromBackground, index);
+        ts << "    " << layerAfterPromote << " \"" << layerAfterPromote->name() << "\", z-index: " << layerAfterPromote->renderer()->style()->zIndex() << "\n";
+    }
+
+    return ts.release();
+}
+
+PassRefPtr<PaintOrderLists> RenderLayer::paintOrderLists()
+{
+    OwnPtr<Vector<RenderLayer*> > posZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListBeforePromote;
+    OwnPtr<Vector<RenderLayer*> > posZOrderListAfterPromote;
+    OwnPtr<Vector<RenderLayer*> > negZOrderListAfterPromote;
+
+    RenderLayer* ancestorStackingContext = this;
+
+    while (ancestorStackingContext) {
+        if (ancestorStackingContext != this && ancestorStackingContext->isStackingContext())
+            break;
+        ancestorStackingContext = ancestorStackingContext->parent();
+    }
+
+    if (!ancestorStackingContext)
+        return 0;
+
+    collectBeforeAfterPromotionZOrderLists(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;
+
+    ListHashSet<RefPtr<Node> > listBeforePromote;
+    for (size_t index = 0; index < sizeBeforePromote; index++) {
+        const RenderLayer* layerBeforePromote = getStackingOrderElementAt(posZOrderListBeforePromote.get(), negZOrderListBeforePromote.get(), FromBackground, index);
+        listBeforePromote.add(layerBeforePromote->renderer()->node());
+    }
+
+    ListHashSet<RefPtr<Node> > listAfterPromote;
+    for (size_t index = 0; index < sizeAfterPromote; index++) {
+        const RenderLayer* layerAfterPromote = getStackingOrderElementAt(posZOrderListAfterPromote.get(), negZOrderListAfterPromote.get(), FromBackground, index);
+        listAfterPromote.add(layerAfterPromote->renderer()->node());
+    }
+
+    PassRefPtr<PaintOrderLists> paintOrderLists = adoptRef(new PaintOrderLists(StaticHashSetNodeList::adopt(listBeforePromote), StaticHashSetNodeList::adopt(listAfterPromote)));
+    return paintOrderLists;
+}
+
+
 void RenderLayer::computeRepaintRects(const RenderLayerModelObject* repaintContainer, const RenderGeometryMap* geometryMap)
 {
     ASSERT(!m_visibleContentStatusDirty);
@@ -1303,12 +1536,6 @@ RenderLayer* RenderLayer::stackingContext() const
     return layer;
 }
 
-static inline bool isPositionedContainer(RenderLayer* layer)
-{
-    RenderLayerModelObject* layerRenderer = layer->renderer();
-    return layer->isRootLayer() || layerRenderer->isPositioned() || layer->hasTransform();
-}
-
 static inline bool isFixedPositionedContainer(RenderLayer* layer)
 {
     return layer->isRootLayer() || layer->hasTransform();
@@ -5590,12 +5817,12 @@ void RenderLayer::rebuildZOrderLists()
     m_zOrderListsDirty = false;
 }
 
-void RenderLayer::rebuildZOrderLists(CollectLayersBehavior behavior, OwnPtr<Vector<RenderLayer*> >& posZOrderList, OwnPtr<Vector<RenderLayer*> >& negZOrderList)
+void RenderLayer::rebuildZOrderLists(CollectLayersBehavior behavior, OwnPtr<Vector<RenderLayer*> >& posZOrderList, OwnPtr<Vector<RenderLayer*> >& negZOrderList, const RenderLayer* layerToForceAsStackingContext)

[shawnsingh, 2013/04/18 02:22:14]

To be strict with the distinction between stacking context and stacking
container, shouldn't this variable name be "layerToForceAsStackingContainer" ? 
Or am I missing something?

[hartmanng, 2013/04/18 17:14:00]

Yeah, you're right, good catch.

 {
     bool includeHiddenLayers = compositor()->inCompositingMode();
     for (RenderLayer* child = firstChild(); child; child = child->nextSibling())
         if (!m_reflection || reflectionLayer() != child)
-            child->collectLayers(includeHiddenLayers, behavior, posZOrderList, negZOrderList);
+            child->collectLayers(includeHiddenLayers, behavior, posZOrderList, negZOrderList, layerToForceAsStackingContext);
 
     // Sort the two lists.
     if (posZOrderList)
@@ -5640,7 +5867,7 @@ void RenderLayer::updateNormalFlowList()
     m_normalFlowListDirty = false;
 }
 
-void RenderLayer::collectLayers(bool includeHiddenLayers, CollectLayersBehavior behavior, OwnPtr<Vector<RenderLayer*> >& posBuffer, OwnPtr<Vector<RenderLayer*> >& negBuffer)
+void RenderLayer::collectLayers(bool includeHiddenLayers, CollectLayersBehavior behavior, OwnPtr<Vector<RenderLayer*> >& posBuffer, OwnPtr<Vector<RenderLayer*> >& negBuffer, const RenderLayer* layerToForceAsStackingContext)

[shawnsingh, 2013/04/18 02:22:14]

same question about variable name as above.

[hartmanng, 2013/04/18 17:14:00]

Done.

 {
 #if ENABLE(DIALOG_ELEMENT)
     if (isInTopLayer())
@@ -5649,7 +5876,7 @@ void RenderLayer::collectLayers(bool includeHiddenLayers, CollectLayersBehavior
 
     updateDescendantDependentFlags();
 
-    bool isStacking = behavior == StopAtStackingContexts ? isStackingContext() : isStackingContainer();
+    bool isStacking = (this == layerToForceAsStackingContext) || (behavior == StopAtStackingContexts ? isStackingContext() : isStackingContainer());

[shawnsingh, 2013/04/18 02:22:14]

Not your patch, but the existing conditions on this line of code make me
uncomfortable.  If we ever extend the CollectLayersBehavior enum further,
there's a chance this may become wrong.  I feel there's a more robust way to
handle this that is reasonably compact and comfortable to read...

[hartmanng, 2013/04/18 17:14:00]

Changed to a switch statement, does this look better?

     // Overflow layers are just painted by their enclosing layers, so they don't get put in zorder lists.
     bool includeHiddenLayer = includeHiddenLayers || (m_hasVisibleContent || (m_hasVisibleDescendant && isStacking));
     if (includeHiddenLayer && !isNormalFlowOnly() && !isOutOfFlowRenderFlowThread()) {
@@ -5670,7 +5897,7 @@ void RenderLayer::collectLayers(bool includeHiddenLayers, CollectLayersBehavior
         for (RenderLayer* child = firstChild(); child; child = child->nextSibling()) {
             // Ignore reflections.
             if (!m_reflection || reflectionLayer() != child)
-                child->collectLayers(includeHiddenLayers, behavior, posBuffer, negBuffer);
+                child->collectLayers(includeHiddenLayers, behavior, posBuffer, negBuffer, layerToForceAsStackingContext);
         }
     }
 }