Generate scroll/clip display item hierarchy for SPv2

Source/core/paint/DeprecatedPaintLayerPainter.cpp

Index: Source/core/paint/DeprecatedPaintLayerPainter.cpp
diff --git a/Source/core/paint/DeprecatedPaintLayerPainter.cpp b/Source/core/paint/DeprecatedPaintLayerPainter.cpp
index b3e1e59e9bcc5775b3d71277d7e553ac160d19c4..2202aecab95d1c6ad84411cdcb2394a1dc0eb684 100644
--- a/Source/core/paint/DeprecatedPaintLayerPainter.cpp
+++ b/Source/core/paint/DeprecatedPaintLayerPainter.cpp
@@ -15,6 +15,7 @@
 #include "core/paint/DeprecatedPaintLayer.h"
 #include "core/paint/FilterPainter.h"
 #include "core/paint/LayerClipRecorder.h"
+#include "core/paint/LayerDescendantClipRecorder.h"
 #include "core/paint/LayerFixedPositionRecorder.h"
 #include "core/paint/PaintInfo.h"
 #include "core/paint/SVGClipPainter.h"
@@ -230,7 +231,10 @@ DeprecatedPaintLayerPainter::PaintResult DeprecatedPaintLayerPainter::paintLayer
     m_paintLayer.stackingNode()->updateLayerListsIfNeeded();
 
     LayoutPoint offsetFromRoot;
-    m_paintLayer.convertToLayerCoords(paintingInfo.rootLayer, offsetFromRoot);
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
+        m_paintLayer.convertToLayerCoords(paintingInfo.rootLayer, offsetFromRoot, DeprecatedPaintLayer::ExcludeScroll);
+    else
+        m_paintLayer.convertToLayerCoords(paintingInfo.rootLayer, offsetFromRoot);
 
     if (m_paintLayer.compositingState() == PaintsIntoOwnBacking)
         offsetFromRoot.move(m_paintLayer.subpixelAccumulation());
@@ -272,10 +276,19 @@ DeprecatedPaintLayerPainter::PaintResult DeprecatedPaintLayerPainter::paintLayer
         // Collect the fragments. This will compute the clip rectangles and paint offsets for each layer fragment.
         ClipRectsCacheSlot cacheSlot = (paintFlags & PaintLayerUncachedClipRects) ? UncachedClipRects : PaintingClipRects;
         ShouldRespectOverflowClip respectOverflowClip = shouldRespectOverflowClip(paintFlags, m_paintLayer.layoutObject());
-        if (fragmentPolicy == ForceSingleFragment)
+        if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
+            // TODO(trchen): Need to handle layer fragmentation.

[chrishtr, 2015/09/17 18:07:53]

How hard will this be? We need a clear plan for it before committing this patch.

+            DeprecatedPaintLayerFragment fragment;
+            fragment.layerBounds = LayoutRect(offsetFromRoot, LayoutSize(m_paintLayer.size()));
+            fragment.backgroundRect = LayoutRect::infiniteRect();
+            fragment.foregroundRect = LayoutRect::infiniteRect();
+            fragment.outlineRect = LayoutRect::infiniteRect();
+            layerFragments.append(fragment);
+        } else if (fragmentPolicy == ForceSingleFragment) {
             m_paintLayer.appendSingleFragmentIgnoringPagination(layerFragments, localPaintingInfo.rootLayer, localPaintingInfo.paintDirtyRect, cacheSlot, IgnoreOverlayScrollbarSize, respectOverflowClip, &offsetFromRoot, localPaintingInfo.subPixelAccumulation);
-        else
+        } else {
             m_paintLayer.collectFragments(layerFragments, localPaintingInfo.rootLayer, localPaintingInfo.paintDirtyRect, cacheSlot, IgnoreOverlayScrollbarSize, respectOverflowClip, &offsetFromRoot, localPaintingInfo.subPixelAccumulation);
+        }
         if (shouldPaintContent) {
             // TODO(wangxianzhu): This is for old slow scrolling. Implement similar optimization for slimming paint v2.
             shouldPaintContent = atLeastOneFragmentIntersectsDamageRect(layerFragments, localPaintingInfo, paintFlags, offsetFromRoot);
@@ -350,6 +363,9 @@ DeprecatedPaintLayerPainter::PaintResult DeprecatedPaintLayerPainter::paintLayer
 
 bool DeprecatedPaintLayerPainter::needsToClip(const DeprecatedPaintLayerPaintingInfo& localPaintingInfo, const ClipRect& clipRect)
 {
+    // With SPv2 a layer clips its descendants so a layer never clips itself.
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
+        return false;
     return clipRect.rect() != localPaintingInfo.paintDirtyRect || clipRect.hasRadius();
 }
 
@@ -473,6 +489,9 @@ DeprecatedPaintLayerPainter::PaintResult DeprecatedPaintLayerPainter::paintChild
     LayerListMutationDetector mutationChecker(m_paintLayer.stackingNode());
 #endif
 
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
+        return paintChildrenWithFullScrollClipChain(childrenToVisit, context, paintingInfo, paintFlags);
+
     IntSize scrollOffsetAccumulation = paintingInfo.scrollOffsetAccumulation;
     if (m_paintLayer.layoutObject()->hasOverflowClip())
         scrollOffsetAccumulation += m_paintLayer.layoutBox()->scrolledContentOffset();
@@ -499,6 +518,90 @@ DeprecatedPaintLayerPainter::PaintResult DeprecatedPaintLayerPainter::paintChild
     return result;
 }
 
+static DeprecatedPaintLayerPainter::PaintResult recursivelyScrollAndPaintChildLayer(Vector<DeprecatedPaintLayer*>& clippingAncestors, DeprecatedPaintLayer& child, GraphicsContext& context, const DeprecatedPaintLayerPaintingInfo& paintingInfo, PaintLayerFlags paintFlags, DeprecatedPaintLayer* paintOffsetBase, LayoutPoint paintOffset)

[chrishtr, 2015/09/17 00:53:46]

This looks like a bottom-up approach: when encountering a new DPL, figure out
its entire clip and scroll chain up to the root of the document, and emit it.

Why not instead do it top-down: when painting children of a DPL, first paint
pieces of the subtree that are clipped/scrolled by it, then the part that is
not. e.g.:

void paintLayer() {
  {
    ClipRecorder recorder;
    paintClippedChildren();
  }
  paintUnclippedChildren();
}

paintClippedChildren() {
  for (child in children) {
    if (isClipped(child, this))
      paintLayer(child);
  }
}

void paintUnclippedChildren() {
  {
    ScrollRecorder recorder;
    paintScrolledButNotClippedChildren();
  }
  paintUnclippedAndUnscrolledChildren();
}

void paintScrolledButNotClippedChildren() {
  for (child in children) {
    // I don't think there are any such children, but anyway.
    if (!clippedBy(child, this) && scrollsWith(child, this))
      child->paintLayer();
}

etc.


Will this algorithm work? (modulo position: fixed, which can maybe be handled
specially)

I believe it's also linear time.

[trchen, 2015/09/17 01:56:04]

Only up to the nearest self-painting ancestor. i.e. (pseudo) stacking context.
Order will be incorrect. We want to traverse non-self-painting descendants in
painting order. The above algorithm traverses in positioning order. For example:
<div style="overflow:scroll">
  <div style="position:relative; z-index:1;">A</div>
  <div style="position:relative; z-index:3;">B</div>
</div>
<div style="overflow:scroll">
  <div style="position:relative; z-index:2;">C</div>
  <div style="position:relative; z-index:4;">D</div>
</div>

The traverse order of your algorithm will be ABCD, but the correct order should
be ACBD.

An alternative approach is to run your algorithm first to generate a bunch of
meta display items without painting actual layer contents. Then use a warp gate
(a.k.a. referral display item) to jump to the correct space when we paint them
in painting order.

I discussed this alternative approach with pdr@ before, but our conclusion is to
favor simplicity unless we see performance problem in real world

+{
+    ASSERT(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
+    if (clippingAncestors.isEmpty())
+        return DeprecatedPaintLayerPainter(child).paintLayer(&context, paintingInfo, paintFlags);
+    DeprecatedPaintLayer* layer = clippingAncestors.last();
+    clippingAncestors.removeLast();
+
+    ASSERT(layer->layoutObject()->hasOverflowClip() && layer->layoutObject()->isBox());
+    layer->convertToLayerCoords(paintOffsetBase, paintOffset, DeprecatedPaintLayer::ExcludeScroll);
+    LayerDescendantClipRecorder clipRecorder(context, *layer->layoutBox(), paintOffset);
+#if ENABLE(ASSERT)
+    // We want to calculate the current layer position relative to the painting root.
+    // The conversion above reduces time complexity but is logically incorrect.
+    // For example if we have layers A, B, C where layer A is the grandparent of layer C,
+    // we want to first convert from space C->B then B->A. What we do above is actually
+    // convert from space B->A first then C->B. It works because we assume the conversions
+    // are all linear translation thus commutative.
+    LayoutPoint expectedPaintOffset = toLayoutPoint(paintingInfo.subPixelAccumulation);
+    layer->convertToLayerCoords(paintingInfo.rootLayer, expectedPaintOffset, DeprecatedPaintLayer::ExcludeScroll);
+    ASSERT(paintOffset == expectedPaintOffset);
+#endif
+
+    IntSize scrollOffset = layer->layoutBox()->scrolledContentOffset();
+    Optional<ScrollRecorder> scrollRecorder;
+    if (layer->scrollsOverflow() || !scrollOffset.isZero())
+        scrollRecorder.emplace(context, *layer->layoutObject(), PaintPhaseBlockBackground, scrollOffset);
+    return recursivelyScrollAndPaintChildLayer(clippingAncestors, child, context, paintingInfo, paintFlags, layer, paintOffset);
+}
+
+static void collectClippingLayersBetween(Vector<DeprecatedPaintLayer*> &clippingAncestors, DeprecatedPaintLayer* layer, DeprecatedPaintLayer* ancestor)

[chrishtr, 2015/09/17 00:53:46]

This function is doing almost (exactly?) the same thing as
DeprecatedPaintLayerClipper.

[trchen, 2015/09/17 01:56:04]

Yep. Albeit we don't try to collapse clip rects right away, but defer it until
layerization or even rasterization.

+{
+    while (layer && layer != ancestor) {
+        EPosition position = layer->layoutObject()->style()->position();
+        ASSERT(position != FixedPosition);
+
+        DeprecatedPaintLayer* container = nullptr;
+        if (position == AbsolutePosition) {
+            bool ranPastThisLayer;
+            container = layer->enclosingPositionedAncestor(ancestor, &ranPastThisLayer);
+            if (ranPastThisLayer)
+                break;
+        } else {
+            container = layer->parent();
+        }
+        if (!container)
+            break;
+
+        if (container->layoutObject()->hasOverflowClip())

[chrishtr, 2015/09/17 18:07:53]

What about css clip and clip-path?

+            clippingAncestors.append(container);
+
+        layer = container;
+    }
+}
+
+// TODO(trchen): Measure performance of this and implement display item de-duping if needed.
+// For the pessimistic case this function will generate O(n^2) of clip/scroll pairs, for example:
+// <div style="overflow:scroll;"> * repeat 100 times
+// <div style="position:relative;"></div> * repeat 100 times
+// We will need to generate 100 clip/scroll pairs for each of the in-flow positioned children.
+DeprecatedPaintLayerPainter::PaintResult DeprecatedPaintLayerPainter::paintChildrenWithFullScrollClipChain(unsigned childrenToVisit, GraphicsContext* context, const DeprecatedPaintLayerPaintingInfo& paintingInfo, PaintLayerFlags paintFlags)

[chrishtr, 2015/09/22 18:32:56]

Let's implement an optimization here: between painting successive child DPLs,
don't pop the clip or scroll chain off the stack. Instead, keep them around to
potentially reuse if the subsequent child has the same clip/scroll chain. This
will optimize a probably common scenario of multiple children with the same
clip/scroll pattern.

Another optimization I think you should add is to just push the clip and scroll
items on the stack before any recursion at all if the current DPL is a stacking
context.

+{
+    PaintResult result = FullyPainted;
+    ASSERT(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
+
+    DeprecatedPaintLayerStackingNodeIterator iterator(*m_paintLayer.stackingNode(), childrenToVisit);
+    while (DeprecatedPaintLayerStackingNode* childNode = iterator.next()) {
+        DeprecatedPaintLayer* child = childNode->layer();
+        EPosition childPosition = child->layoutObject()->style()->position();
+        if (childPosition == FixedPosition) {
+            // TODO(trchen): Fixed position needs to be implemented here.

[chrishtr, 2015/09/17 18:07:53]

We need a plan for how to do it before committing this patch.

[chrishtr, 2015/09/22 18:32:56]

On reflection, I think fixed position shouldn't be super hard, right? Just
compute whether clips and scrolls apply to it. Not requiring it be implemented
here, but checking.

+            if (DeprecatedPaintLayerPainter(*child).paintLayer(context, paintingInfo, paintFlags) == MaybeNotFullyPainted)
+                result = MaybeNotFullyPainted;
+            continue;
+        }
+
+        Vector<DeprecatedPaintLayer*> clippingAncestors;
+        collectClippingLayersBetween(clippingAncestors, child, &m_paintLayer);
+        if (recursivelyScrollAndPaintChildLayer(clippingAncestors, *child, *context, paintingInfo, paintFlags, paintingInfo.rootLayer, toLayoutPoint(paintingInfo.subPixelAccumulation)) == MaybeNotFullyPainted)
+            result = MaybeNotFullyPainted;
+    }
+    return result;
+}
+
 // FIXME: inline this.
 static bool paintForFixedRootBackground(const DeprecatedPaintLayer* layer, PaintLayerFlags paintFlags)
 {
@@ -536,6 +639,13 @@ void DeprecatedPaintLayerPainter::paintFragmentWithPhase(PaintPhase phase, const
 {
     ASSERT(m_paintLayer.isSelfPaintingLayer());
 
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
+        PaintInfo paintInfo(context, enclosingIntRect(paintingInfo.paintDirtyRect), phase, paintingInfo.globalPaintFlags(), paintFlags, paintingRootForLayoutObject, paintingInfo.rootLayer->layoutObject());
+        LayoutPoint paintOffset = toPoint(fragment.layerBounds.location() - m_paintLayer.layoutBoxLocation());
+        m_paintLayer.layoutObject()->paint(paintInfo, paintOffset);
+        return;
+    }
+
     Optional<LayerClipRecorder> clipRecorder;
     if (clipState != HasClipped && paintingInfo.clipToDirtyRect && needsToClip(paintingInfo, clipRect)) {
         DisplayItem::Type clipType = DisplayItem::paintPhaseToClipLayerFragmentType(phase);