[SPv2] Implement effect compositing for indirect reasons

third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp

Index: third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
diff --git a/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp b/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
index 0e38a13cb0112b9985629e5e04c18b35d62462a5..76323b1cfa667b269da4bacebb950c105ce75817 100644
--- a/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
+++ b/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
@@ -571,116 +571,242 @@ PaintArtifactCompositor::compositedLayerForPendingLayer(
   return ccPictureLayer;
 }
 
-bool PaintArtifactCompositor::canMergeInto(
-    const PaintArtifact& paintArtifact,
-    const PaintChunk& newChunk,
-    const PendingLayer& candidatePendingLayer) {
-  const PaintChunk& pendingLayerFirstChunk =
-      *candidatePendingLayer.paintChunks[0];
-  if (paintArtifact.getDisplayItemList()[newChunk.beginIndex].isForeignLayer())
-    return false;
+PaintArtifactCompositor::PendingLayer::PendingLayer(
+    const PaintChunk& firstPaintChunk,
+    bool chunkIsForeign,
+    GeometryMapper& geometryMapper)
+    : bounds(firstPaintChunk.bounds),
+      knownToBeOpaque(firstPaintChunk.knownToBeOpaque),
+      backfaceHidden(firstPaintChunk.properties.backfaceHidden),
+      propertyTreeState(firstPaintChunk.properties.propertyTreeState),
+      isForeign(chunkIsForeign) {
+  paintChunks.push_back(&firstPaintChunk);
+}
 
-  if (paintArtifact.getDisplayItemList()[pendingLayerFirstChunk.beginIndex]
-          .isForeignLayer())
-    return false;
+void PaintArtifactCompositor::PendingLayer::merge(
+    const PendingLayer& guest,
+    GeometryMapper& geometryMapper) {
+  DCHECK(!isForeign && !guest.isForeign);
+  DCHECK_EQ(backfaceHidden, guest.backfaceHidden);
+
+  paintChunks.appendVector(guest.paintChunks);
+  FloatRect oldBounds = bounds;
+  bounds.unite(geometryMapper
+                   .localToAncestorVisualRect(
+                       guest.bounds, guest.propertyTreeState, propertyTreeState)
+                   .rect());
+  if (bounds != oldBounds)
+    knownToBeOpaque = false;
+}
 
-  if (newChunk.properties.backfaceHidden !=
-      pendingLayerFirstChunk.properties.backfaceHidden)
+static bool canUpcastTo(const PropertyTreeState& guest,
+                        const PropertyTreeState& home);
+bool PaintArtifactCompositor::PendingLayer::canMerge(
+    const PendingLayer& guest) const {
+  if (isForeign || guest.isForeign)
+    return false;
+  if (backfaceHidden != guest.backfaceHidden)
     return false;
+  if (propertyTreeState.effect() != guest.propertyTreeState.effect())
+    return false;
+  return canUpcastTo(guest.propertyTreeState, propertyTreeState);
+}
 
-  DCHECK_GE(candidatePendingLayer.paintChunks.size(), 1u);
-  PropertyTreeStateIterator iterator(newChunk.properties.propertyTreeState);
-  for (const PropertyTreeState* currentState =
-           &newChunk.properties.propertyTreeState;
-       currentState; currentState = iterator.next()) {
-    if (*currentState == candidatePendingLayer.propertyTreeState)
-      return true;
-    if (currentState->hasDirectCompositingReasons())
+void PaintArtifactCompositor::PendingLayer::upcast(
+    const PropertyTreeState& newState,
+    GeometryMapper& geometryMapper) {
+  bounds = geometryMapper
+               .localToAncestorVisualRect(bounds, propertyTreeState, newState)
+               .rect();
+  propertyTreeState = newState;
+  // TODO(trchen): Upgrade GeometryMapper.
+  // A local visual rect mapped to an ancestor space may become a polygon
+  // (e.g. consider transformed clip), also effects may affect the opaque
+  // region. To determine whether the layer is still opaque, we need to
+  // query conservative opaque rect after mapping to an ancestor space,
+  // which is not supported by GeometryMapper yet.
+  knownToBeOpaque = false;
+}
+
+static bool isNonCompositingAncestorOf(
+    const TransformPaintPropertyNode* ancestor,
+    const TransformPaintPropertyNode* node) {
+  for (; node != ancestor; node = node->parent()) {
+    if (!node || node->hasDirectCompositingReasons())
       return false;
   }
-  return false;
+  return true;
 }
 
-bool PaintArtifactCompositor::mightOverlap(
-    const PaintChunk& paintChunk,
-    const PendingLayer& candidatePendingLayer,
-    GeometryMapper& geometryMapper) {
+static bool canUpcastTo(const PropertyTreeState& guest,

[chrishtr, 2017/03/09 01:27:00]

Document this method.

[trchen, 2017/03/15 22:46:52]

Done.

+                        const PropertyTreeState& home) {
+  DCHECK_EQ(home.effect(), guest.effect());
+
+  for (const ClipPaintPropertyNode* currentClip = guest.clip();
+       currentClip != home.clip(); currentClip = currentClip->parent()) {
+    if (!currentClip || currentClip->hasDirectCompositingReasons())
+      return false;
+    if (!isNonCompositingAncestorOf(home.transform(),
+                                    currentClip->localTransformSpace()))
+      return false;
+  }
+
+  return isNonCompositingAncestorOf(home.transform(), guest.transform());
+}
+
+// Returns nullptr if 'ancestor' is not a strict ancestor of 'node'.
+// Otherwise, return the child of 'ancestor' that is an ancestor of 'node' or
+// 'node' itself.
+static const EffectPaintPropertyNode* strictAncestorOf(

[chrishtr, 2017/03/09 01:27:00]

strictChildOfAlongPath ?

[trchen, 2017/03/15 22:46:52]

Done.

+    const EffectPaintPropertyNode* ancestor,
+    const EffectPaintPropertyNode* node) {
+  for (; node; node = node->parent()) {
+    if (node->parent() == ancestor)
+      return node;
+  }
+  return nullptr;
+}
+
+static bool mightOverlap(const PropertyTreeState& stateA,
+                         const FloatRect& boundsA,
+                         const PropertyTreeState& stateB,
+                         const FloatRect& boundsB,
+                         GeometryMapper& geometryMapper) {
   PropertyTreeState rootPropertyTreeState(TransformPaintPropertyNode::root(),
                                           ClipPaintPropertyNode::root(),
                                           EffectPaintPropertyNode::root());
 
-  FloatRect paintChunkScreenVisualRect =
+  FloatRect screenVisualRectA =
       geometryMapper
-          .localToAncestorVisualRect(paintChunk.bounds,
-                                     paintChunk.properties.propertyTreeState,
-                                     rootPropertyTreeState)
+          .localToAncestorVisualRect(boundsA, stateA, rootPropertyTreeState)
           .rect();
 
-  FloatRect pendingLayerScreenVisualRect =
+  FloatRect screenVisualRectB =
       geometryMapper
-          .localToAncestorVisualRect(candidatePendingLayer.bounds,
-                                     candidatePendingLayer.propertyTreeState,
-                                     rootPropertyTreeState)
+          .localToAncestorVisualRect(boundsB, stateB, rootPropertyTreeState)
           .rect();
 
-  return paintChunkScreenVisualRect.intersects(pendingLayerScreenVisualRect);
+  return screenVisualRectA.intersects(screenVisualRectB);
 }
 
-PaintArtifactCompositor::PendingLayer::PendingLayer(
-    const PaintChunk& firstPaintChunk)
-    : bounds(firstPaintChunk.bounds),
-      knownToBeOpaque(firstPaintChunk.knownToBeOpaque),
-      backfaceHidden(firstPaintChunk.properties.backfaceHidden),
-      propertyTreeState(firstPaintChunk.properties.propertyTreeState) {
-  paintChunks.push_back(&firstPaintChunk);
-}
-
-void PaintArtifactCompositor::PendingLayer::add(
-    const PaintChunk& paintChunk,
-    GeometryMapper* geometryMapper) {
-  DCHECK(paintChunk.properties.backfaceHidden == backfaceHidden);
-  paintChunks.push_back(&paintChunk);
-  FloatRect mappedBounds = paintChunk.bounds;
-  if (geometryMapper) {
-    mappedBounds = geometryMapper->localToAncestorRect(
-        mappedBounds, paintChunk.properties.propertyTreeState.transform(),
-        propertyTreeState.transform());
-  }
-  bounds.unite(mappedBounds);
-  if (bounds.size() != paintChunks[0]->bounds.size()) {
-    if (bounds.size() != paintChunk.bounds.size())
-      knownToBeOpaque = false;
-    else
-      knownToBeOpaque = paintChunk.knownToBeOpaque;
-  }
-}
-
-void PaintArtifactCompositor::collectPendingLayers(
+void PaintArtifactCompositor::layerizeGroup(
     const PaintArtifact& paintArtifact,
     Vector<PendingLayer>& pendingLayers,
-    GeometryMapper& geometryMapper) {
-  // n = # of paint chunks. Memoizing canMergeInto() can get it to O(n^2), and
-  // other heuristics can make worst-case behavior better.
-  for (const PaintChunk& paintChunk : paintArtifact.paintChunks()) {
-    bool createNew = true;
-    for (Vector<PendingLayer>::reverse_iterator candidatePendingLayer =
-             pendingLayers.rbegin();
-         candidatePendingLayer != pendingLayers.rend();
-         ++candidatePendingLayer) {
-      if (canMergeInto(paintArtifact, paintChunk, *candidatePendingLayer)) {
-        candidatePendingLayer->add(paintChunk, &geometryMapper);
-        createNew = false;
+    GeometryMapper& geometryMapper,
+    const EffectPaintPropertyNode& currentGroup,
+    Vector<PaintChunk>::const_iterator& chunkIt) {
+  size_t firstLayerInCurrentGroup = pendingLayers.size();
+  // The worst case time complexity of the algorithm is O(pqd), where
+  // p = the number of paint chunks.
+  // q = average number of trials to find a squash layer or rejected
+  //     for overlapping.
+  // d = (sum of) the depth of property trees.
+  // The analysis as follows:
+  // Every paint chunk will be visited by the main loop below for exactly once,
+  // except for chunks that enter or exit groups (case B & C below).
+  // For normal chunk visit (case A), the only cost is determining squash,
+  // which costs O(qd), where d came from "canUpcastTo" and geometry mapping.
+  // Subtotal: O(pqd)
+  // For group entering and exiting, it could cost O(d) for each group, for
+  // searching the shallowest subgroup (strictAncestorOf), thus O(d^2) in total.
+  // Also when exiting group, the group may be decomposited and squashed to a
+  // previous layer. Again finding the host costs O(qd). Merging would cost O(p)
+  // due to copying the chunk list. Subtotal: O((qd + p)d) = O(qd^2 + pd)
+  // Assuming p > d, the total complexity would be O(pqd + qd^2 + pd) = O(pqd)
+  while (chunkIt != paintArtifact.paintChunks().end()) {
+    // Look at the effect node of the next chunk. There are 3 possible cases:
+    // A. The next chunk belongs to the current group but no subgroup.
+    // B. The next chunk does not belong to the current group.
+    // C. The next chunk belongs to some subgroup of the current group.
+    const EffectPaintPropertyNode* chunkEffect =
+        chunkIt->properties.propertyTreeState.effect();
+    if (chunkEffect == &currentGroup) {
+      // Case A: The next chunk belongs to the current group but no subgroup.
+      bool isForeign = paintArtifact.getDisplayItemList()[chunkIt->beginIndex]
+                           .isForeignLayer();
+      pendingLayers.push_back(
+          PendingLayer(*chunkIt++, isForeign, geometryMapper));
+      if (isForeign)
+        continue;
+    } else {
+      const EffectPaintPropertyNode* subgroup =
+          strictAncestorOf(&currentGroup, chunkEffect);
+      // Case B: This means we need to close the current group without
+      //         processing the next chunk.
+      if (!subgroup)
         break;
-      }
-      if (mightOverlap(paintChunk, *candidatePendingLayer, geometryMapper)) {
+      // Case C: The following chunks belong to a subgroup. Process them by
+      //         a recursion call.
+      size_t firstLayerInSubgroup = pendingLayers.size();
+      layerizeGroup(paintArtifact, pendingLayers, geometryMapper, *subgroup,
+                    chunkIt);
+      // Now the chunk iterator stepped over the subgroup we just saw.

[chrishtr, 2017/03/09 01:27:00]

What about a 3d composited child?

[trchen, 2017/03/15 22:46:52]

Hmmm that's a good point. 3D transformed children themselves are fine, but
nested 3D context may cause a problem. For example:

<div style="transform-style:preserve-3d;">
  <div style="transform:*;">A</div>
  <div style="transform:*;">
    <div style="transform-style:preserve-3d;">
      <div style="transform:*;">B</div>
      <div style="transform:*;">C</div>
      <div style="transform:*;">D</div>
    </div>
  </div>
  <div style="transform:*;">E</div>
</div>>

The semantics of above is that B,C,D are 3D-sorted, and A,BCD,E are 3D-sorted,
where BCD is the flattened result of the former. BCD needs to have a render
surface[1] to represent it. There is a TODO in PropertyTreeBuilder to generate
effect node when such case is detected, but not implemented yet.

[1] Which I think is unnecessary. An effect node without render surface should
be good enough. All we need is some improvement in
DirectRenderer::DrawRenderPass().

+      // If the subgroup generated 2 or more layers then the subgroup must be
+      // composited to satisfy grouping requirement.
+      // i.e. Grouping effects generally must be applied atomically,
+      // for example,  Opacity(A+B) != Opacity(A) + Opacity(B), thus an effect
+      // either applied 100% within a layer, or not at all applied within layer
+      // (i.e. applied by compositor render surface instead).
+      if (pendingLayers.size() != firstLayerInSubgroup + 1)

[chrishtr, 2017/03/09 01:27:00]

Please factor these conditions into a helper method.

[trchen, 2017/03/15 22:46:52]

Done.

+        continue;
+      // Attempt to "decomposite" subgroup. Only decomposite one level deep
+      // because the recusion should have decomposited the sub-subgroups.
+      // If we see a deep subgroup here, that implies some intermediate
+      // subgroup must be composited.
+      PendingLayer& subgroupLayer = pendingLayers[firstLayerInSubgroup];
+      if (subgroupLayer.propertyTreeState.effect() != subgroup)
+        continue;
+      if (subgroupLayer.isForeign)
+        continue;
+      // TODO(trchen): Exotic blending layer may be decomposited only if it
+      // could be merged into the first layer of the current group.
+      if (subgroup->blendMode() != SkBlendMode::kSrcOver)
+        continue;
+      if (subgroup->hasDirectCompositingReasons() ||
+          !canUpcastTo(subgroupLayer.propertyTreeState,
+                       PropertyTreeState(subgroup->localTransformSpace(),
+                                         subgroup->outputClip(), subgroup)))
+        continue;
+      subgroupLayer.upcast(
+          PropertyTreeState(subgroup->localTransformSpace(),
+                            subgroup->outputClip(), &currentGroup),
+          geometryMapper);
+    }
+    // At this point pendingLayers.back() is the either a layer from a
+    // "decomposited" subgroup or a layer created from a chunk we just
+    // processed. Now determine whether it could be merged into a previous
+    // layer.
+    const PendingLayer& newLayer = pendingLayers.back();
+    DCHECK(!newLayer.isForeign);
+    DCHECK_EQ(&currentGroup, newLayer.propertyTreeState.effect());
+    // This iterates pendingLayers[firstLayerInCurrentGroup:-1] in reverse.
+    for (size_t candidateIndex = pendingLayers.size() - 1;
+         candidateIndex-- > firstLayerInCurrentGroup;) {
+      PendingLayer& candidateLayer = pendingLayers[candidateIndex];
+      if (candidateLayer.canMerge(newLayer)) {
+        candidateLayer.merge(newLayer, geometryMapper);
+        pendingLayers.pop_back();
         break;
       }
+      if (mightOverlap(newLayer.propertyTreeState, newLayer.bounds,
+                       candidateLayer.propertyTreeState, candidateLayer.bounds,
+                       geometryMapper))
+        break;
     }
-    if (createNew)
-      pendingLayers.push_back(PendingLayer(paintChunk));
   }
 }
 
+void PaintArtifactCompositor::collectPendingLayers(
+    const PaintArtifact& paintArtifact,
+    Vector<PendingLayer>& pendingLayers,
+    GeometryMapper& geometryMapper) {
+  Vector<PaintChunk>::const_iterator cursor =
+      paintArtifact.paintChunks().begin();
+  layerizeGroup(paintArtifact, pendingLayers, geometryMapper,
+                *EffectPaintPropertyNode::root(), cursor);
+  DCHECK_EQ(paintArtifact.paintChunks().end(), cursor);
+}
+
 void PaintArtifactCompositor::update(
     const PaintArtifact& paintArtifact,
     RasterInvalidationTrackingMap<const PaintChunk>* rasterChunkInvalidations,