[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 <algorithm>
 #include <memory>
 #include <utility>
 #include "cc/layers/content_layer_client.h"
@@ skipping 546 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())
+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(

[chrishtr, 2017/02/28 22:50:35]

This is a change (used to be localToAncestorRect). Is it unittested?

[trchen, 2017/03/01 01:26:11]

Good point. I shall add a test.

[trchen, 2017/03/07 01:41:24]

Done.

+                       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) ==

[chrishtr, 2017/02/28 22:50:33]

Are you trying to detect exact integer bounds here?

[trchen, 2017/03/01 01:26:11]

Sorry my comment was confusing. By enclosedRect I meant a rect that is
guaranteed to be a subset of the transformed region, for the purpose of
determining opaque rect. For rectilinear transforms it is trivial. For
transforms that outputs a quad there is no unique best answer (and I think using
empty rect is fine in this case).

[trchen, 2017/03/07 01:41:24]

Comments clarified.

+  // enclosedRect(mappedRegion);
+  // localToAncestorVisualRect returns the enclosingRect of the mapped region.
+  // A variant that returns the enclosedRect is needed.
+  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;
-}
-
-bool PaintArtifactCompositor::mightOverlap(
-    const PaintChunk& paintChunk,
-    const PendingLayer& candidatePendingLayer,
-    GeometryMapper& geometryMapper) {
+  return true;
+}
+
+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 || currentClip->hasDirectCompositingReasons())
+      return false;
+    if (!isNonCompositingAncestorOf(home.transform(),

[chrishtr, 2017/02/28 22:50:35]

Won't the check on line 633 handle all of these?

[trchen, 2017/03/01 01:26:11]

Unfortunately not. Sometimes clips applied to a chunk can have deeper transform
node than the chunk. One notable example is CSS clip with fixed-pos child:

<div style="overflow:scroll: position:relative;">
  <div style="position:absolute; clip:rect(1px,2px,3px,4px);">
    <div style="position:fixed;">Foo</div>
  </div>
</div>

And worse, we could have transform space inversion:

<div style="overflow:scroll: position:relative;">
  <div style="position:absolute; clip:rect(1px,2px,3px,4px);">
    <div style="position:fixed; overflow:hidden;">Ouch</div>
  </div>
</div>

Another example would be CSS mask (which creates an implicit clip) with scroll
escaping:
<div style="overflow:scroll">
  <div style="mask:url('foo')">
    <div style="position:absolute">foo</div>
  </div>
</div>

+                                    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(
+    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();
+  // 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;
+      // 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.
+      // If the subgroup generated 2 or more layers then the grouping must be
+      // composited as well.

[chrishtr, 2017/02/28 22:50:33]

Explain why.

[trchen, 2017/03/01 01:26:11]

Acknowledged.

[trchen, 2017/03/07 01:41:24]

Done.

+      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;
+      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.isForeign &&

[chrishtr, 2017/02/28 22:50:35]

I think it would be clearer to move these conditions back into a canMergeInto
method
similar to what existed before this CL.

[trchen, 2017/03/01 01:26:11]

How about making it PendingLayer::canMerge(const PendingLayer& guest)?

[trchen, 2017/03/07 01:41:24]

Done.

+          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