[SPv2] Implement effect compositing for indirect reasons

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

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "platform/graphics/compositing/PaintArtifactCompositor.h"
 
 #include "cc/layers/content_layer_client.h"
 #include "cc/layers/layer.h"
 #include "cc/layers/picture_layer.h"
 #include "cc/playback/compositing_display_item.h"
@@ skipping 543 matching lines @@
           ccInvalidationRect,
           rasterTracking ? &rasterTracking->trackedRasterInvalidations[index]
                          : nullptr);
     }
   }
 
   newContentLayerClients.push_back(std::move(contentLayerClient));
   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;
-
-  if (paintArtifact.getDisplayItemList()[pendingLayerFirstChunk.beginIndex]
-          .isForeignLayer())
-    return false;
-
-  if (newChunk.properties.backfaceHidden !=
-      pendingLayerFirstChunk.properties.backfaceHidden)
-    return false;
-
-  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())
-      return false;
-  }
-  return false;
-}
-
-bool PaintArtifactCompositor::mightOverlap(
-    const PaintChunk& paintChunk,
-    const PendingLayer& candidatePendingLayer,
+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);
+}
+
+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;
+}
+
+void PaintArtifactCompositor::PendingLayer::upcast(
+    const PropertyTreeState& newState,
+    GeometryMapper& geometryMapper) {
+  bounds = geometryMapper
+               .localToAncestorVisualRect(bounds, propertyTreeState, newState)
+               .rect();
+  propertyTreeState = newState;
+  // TODO(trchen): Upgrade GeometryMapper.
+  // knownToBeOpaque = knownToBeOpaque && enclosingRect(mappedRegion) ==
+  // enclosedRect(mappedRegion);
+  // localToAncestorVisualRect returns the enclosingRect of the mapped region.
+  // A variant that returns the enclosedRect is needed.
+  knownToBeOpaque = false;
+}
+
+#if 0
+static unsigned nodeDepth(const TransformPaintPropertyNode* node) {
+  unsigned depth = 0;
+  while (node) {
+    depth++;
+    node = node->parent();
+  }
+  return depth;
+}
+
+// Return true if there are no direct compositing reason on the path between two transform nodes.
+static bool transformsAreCompatible(const TransformPaintPropertyNode* nodeA, const TransformPaintPropertyNode* nodeB) {
+  // Measure both depths.
+  unsigned depthA = nodeDepth(nodeA);
+  unsigned depthB = nodeDepth(nodeB);
+
+  // Make it so depthA >= depthB.
+  if (depthA < depthB) {
+    std::swap(nodeA, nodeB);
+    std::swap(depthA, depthB);
+  }
+
+  // Make it so depthA == depthB.
+  while (depthA > depthB) {
+    if (nodeA->hasDirectCompositingReasons())
+      return false;
+    nodeA = nodeA->parent();
+    depthA--;
+  }
+
+  // Walk up until we find the ancestor.
+  while (nodeA != nodeB) {
+    if (nodeA->hasDirectCompositingReasons() || nodeB->hasDirectCompositingReasons())
+      return false;
+    nodeA = nodeA->parent();
+    nodeB = nodeB->parent();
+  }
+  return true;
+}
+#else
+static bool transformsAreCompatible(const TransformPaintPropertyNode* nodeA,
+                                    const TransformPaintPropertyNode* nodeB) {
+  for (; nodeB != nodeA; nodeB = nodeB->parent()) {
+    if (!nodeB || nodeB->hasDirectCompositingReasons())
+      return false;
+  }
+  return true;
+}
+#endif
+
+static bool canUpcastTo(const PropertyTreeState& guest,
+                        const PropertyTreeState& home) {
+  DCHECK_EQ(home.effect(), guest.effect());
+
+  for (const ClipPaintPropertyNode* currentClip = guest.clip();
+       currentClip != home.clip(); currentClip = currentClip->parent()) {
+    if (currentClip->hasDirectCompositingReasons())
+      return false;
+    if (!transformsAreCompatible(home.transform(),
+                                 currentClip->localTransformSpace()))
+      return false;
+  }
+
+  return transformsAreCompatible(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(
+    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);
-}
-
-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;
+  return screenVisualRectA.intersects(screenVisualRectB);
+}
+
+void PaintArtifactCompositor::layerizeGroup(
+    const PaintArtifact& paintArtifact,
+    Vector<PendingLayer>& pendingLayers,
+    GeometryMapper& geometryMapper,
+    const EffectPaintPropertyNode& currentGroup,
+    Vector<PaintChunk>::const_iterator& chunkIt) {
+  size_t firstLayerInCurrentGroup = pendingLayers.size();
+  while (chunkIt != paintArtifact.paintChunks().end()) {
+    // Look at the effect node of the next chunk. There are 3 possible cases:

[pdr., 2017/02/23 06:05:18]

Do you have an intuition about the frequency of each of these cases?

[trchen, 2017/02/23 22:19:45]

Case A and B always happen in pair, and should be as frequent as the ratio
between effect nodes / total paint chunks. For most pages case C should be the
majority.

Now you mentioned it, I think I should lift case C to the top, according to the
style guide (shorter branch goes first).

+    // A. The next chunk does not belong to the current group.
+    // B. The next chunk belongs to some subgroup of the current group.
+    // C. The next chunk belongs to the current group but no subgroup.
+    const EffectPaintPropertyNode* chunkEffect =
+        chunkIt->properties.propertyTreeState.effect();
+    if (chunkEffect != &currentGroup) {
+      const EffectPaintPropertyNode* subgroup =
+          strictAncestorOf(&currentGroup, chunkEffect);
+      // Case A: This means we need to close the current group without
+      //         processing the next chunk.
+      if (!subgroup)
+        break;
+      // Case B: 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.
+      // If the subgroup generated 2 or more layers then the grouping must be
+      // composited as well.
+      if (pendingLayers.size() != firstLayerInSubgroup + 1)
+        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;
+      // 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 (subgroupLayer.isForeign)
+        continue;
+      if (subgroup->hasDirectCompositingReasons() ||
+          !canUpcastTo(subgroupLayer.propertyTreeState,

[pdr., 2017/02/23 06:05:18]

Can you add a note about the performance of this? I think you're taking the
right approach by getting the code working first and optimizing later (maybe
later patches), just want to note it in a comment so we don't forget.

[trchen, 2017/02/23 22:19:45]

Acknowledged.

+                       PropertyTreeState(subgroup->localTransformSpace(),
+                                         subgroup->outputClip(), subgroup)))
+        continue;
+      subgroupLayer.upcast(
+          PropertyTreeState(subgroup->localTransformSpace(),
+                            subgroup->outputClip(), &currentGroup),
+          geometryMapper);
+    } else {
+      // Case C: 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;
+    }
+    // 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.isForeign &&
+          newLayer.backfaceHidden == candidateLayer.backfaceHidden &&
+          candidateLayer.propertyTreeState.effect() == &currentGroup &&
+          canUpcastTo(newLayer.propertyTreeState,
+                      candidateLayer.propertyTreeState)) {
+        candidateLayer.merge(newLayer, geometryMapper);
+        pendingLayers.pop_back();
+        break;
+      }
+      if (mightOverlap(newLayer.propertyTreeState, newLayer.bounds,
+                       candidateLayer.propertyTreeState, candidateLayer.bounds,
+                       geometryMapper))
+        break;
+    }
   }
 }
 
 void PaintArtifactCompositor::collectPendingLayers(
     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;
-        break;
-      }
-      if (mightOverlap(paintChunk, *candidatePendingLayer, geometryMapper)) {
-        break;
-      }
-    }
-    if (createNew)
-      pendingLayers.push_back(PendingLayer(paintChunk));
-  }
+  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,
     bool storeDebugInfo,
     GeometryMapper& geometryMapper) {
 #ifndef NDEBUG
   storeDebugInfo = true;
 #endif
@@ skipping 65 matching lines @@
 #ifndef NDEBUG
 void PaintArtifactCompositor::showDebugData() {
   LOG(ERROR) << layersAsJSON(LayerTreeIncludesDebugInfo)
                     ->toPrettyJSONString()
                     .utf8()
                     .data();
 }
 #endif
 
 }  // namespace blink