Implement merging non-composited paint property nodes in the PACompositor.

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 8d806185ea613b1080d1b2ed67c115f353f71468..32696f4947223c42116b2074e1bd0a4cce95dad1 100644
--- a/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
+++ b/third_party/WebKit/Source/platform/graphics/compositing/PaintArtifactCompositor.cpp
@@ -7,9 +7,12 @@
 #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"
 #include "cc/playback/display_item_list.h"
 #include "cc/playback/display_item_list_settings.h"
 #include "cc/playback/drawing_display_item.h"
+#include "cc/playback/filter_display_item.h"
+#include "cc/playback/float_clip_display_item.h"
 #include "cc/playback/transform_display_item.h"
 #include "cc/trees/clip_node.h"
 #include "cc/trees/effect_node.h"
@@ -22,7 +25,9 @@
 #include "platform/graphics/paint/DisplayItem.h"
 #include "platform/graphics/paint/DrawingDisplayItem.h"
 #include "platform/graphics/paint/ForeignLayerDisplayItem.h"
+#include "platform/graphics/paint/GeometryMapper.h"
 #include "platform/graphics/paint/PaintArtifact.h"
+#include "platform/graphics/paint/PropertyTreeState.h"
 #include "platform/graphics/paint/RasterInvalidationTracking.h"
 #include "platform/graphics/paint/ScrollPaintPropertyNode.h"
 #include "platform/graphics/paint/TransformPaintPropertyNode.h"
@@ -222,31 +227,6 @@ static void appendDisplayItemToCcDisplayItemList(const DisplayItem& displayItem,
   }
 }
 
-static scoped_refptr<cc::DisplayItemList> recordPaintChunk(
-    const PaintArtifact& artifact,
-    const PaintChunk& chunk,
-    const gfx::Rect& combinedBounds) {
-  cc::DisplayItemListSettings settings;
-  scoped_refptr<cc::DisplayItemList> list =
-      cc::DisplayItemList::Create(settings);
-
-  gfx::Transform translation;
-  translation.Translate(-combinedBounds.x(), -combinedBounds.y());
-  // Passing combinedBounds as the visual rect for the begin/end transform item
-  // would normally be the sensible thing to do, but see comment above re:
-  // visual rects for drawing items and further rework in flight.
-  list->CreateAndAppendPairedBeginItem<cc::TransformDisplayItem>(translation);
-
-  const DisplayItemList& displayItems = artifact.getDisplayItemList();
-  for (const auto& displayItem : displayItems.itemsInPaintChunk(chunk))
-    appendDisplayItemToCcDisplayItemList(displayItem, list.get());
-
-  list->CreateAndAppendPairedEndItem<cc::EndTransformDisplayItem>();
-
-  list->Finalize();
-  return list;
-}
-
 scoped_refptr<cc::Layer> foreignLayerForPaintChunk(
     const PaintArtifact& paintArtifact,
     const PaintChunk& paintChunk,
@@ -276,8 +256,116 @@ constexpr int kRealRootNodeId = 0;
 constexpr int kSecondaryRootNodeId = 1;
 constexpr int kPropertyTreeSequenceNumber = 1;
 
+static void recordPairedBeginDisplayItems(

[pdr., 2016/12/20 22:50:58]

Can you add a todo(chrishtr) comment about the grouping special sauce here? The
algorithm that groups chunks with the same property tree state.

[chrishtr, 2016/12/20 23:48:31]

Done. Added in recordPendingLayer.

+    const Vector<PropertyTreeState>& pairedStates,
+    cc::DisplayItemList* ccList) {
+  for (Vector<PropertyTreeState>::const_reverse_iterator pairedState =
+           pairedStates.rbegin();
+       pairedState != pairedStates.rend(); ++pairedState) {
+    switch (pairedState->innermostNode()) {
+      case PropertyTreeState::Transform: {
+        gfx::Transform transform(gfx::Transform::kSkipInitialization);
+        transform.matrix() = TransformationMatrix::toSkMatrix44(
+            pairedState->transform()->matrix());
+        ccList->CreateAndAppendPairedBeginItem<cc::TransformDisplayItem>(
+            transform);
+        break;
+      }
+      case PropertyTreeState::Clip: {
+        const FloatRect& rect(pairedState->clip()->clipRect().rect());
+        ccList->CreateAndAppendPairedBeginItem<cc::FloatClipDisplayItem>(
+            gfx::RectF(rect));
+        break;
+      }
+      case PropertyTreeState::Effect: {
+        // TODO(chrishtr): skip effect and/or compositing display items if
+        // not necessary.
+        ccList->CreateAndAppendPairedBeginItem<cc::FilterDisplayItem>(
+            pairedState->effect()->filter().asCcFilterOperations(),
+            pairedState->effect()->outputClip()->clipRect().rect(),
+            // TODO(chrishtr): specify origin of the filter.
+            gfx::PointF());
+        const bool kLcdTextRequiresOpaqueLayer = true;
+        ccList->CreateAndAppendPairedBeginItem<cc::CompositingDisplayItem>(
+            static_cast<uint8_t>(
+                gfx::ToFlooredInt(255 * pairedState->effect()->opacity())),
+            pairedState->effect()->blendMode(),
+            // TODO(chrishtr): compute bounds as necessary.
+            nullptr, nullptr, kLcdTextRequiresOpaqueLayer);
+        break;
+      }
+      case PropertyTreeState::None:
+        break;
+    }
+  }
+}
+
+static void recordPairedEndDisplayItems(
+    const Vector<PropertyTreeState>& pairedStates,
+    cc::DisplayItemList* ccList) {
+  for (Vector<PropertyTreeState>::const_iterator pairedState =
+           pairedStates.begin();
+       pairedState != pairedStates.end(); ++pairedState) {
+    switch (pairedState->innermostNode()) {
+      case PropertyTreeState::Transform:
+        ccList->CreateAndAppendPairedEndItem<cc::EndTransformDisplayItem>();
+        break;
+      case PropertyTreeState::Clip:
+        ccList->CreateAndAppendPairedEndItem<cc::EndFloatClipDisplayItem>();
+        break;
+      case PropertyTreeState::Effect:
+        ccList->CreateAndAppendPairedEndItem<cc::EndCompositingDisplayItem>();
+        ccList->CreateAndAppendPairedEndItem<cc::EndFilterDisplayItem>();
+

[wkorman, 2016/12/20 00:28:56]

extra line

[chrishtr, 2016/12/20 23:36:32]

Fixed.

+        break;
+      case PropertyTreeState::None:
+        break;
+    }
+  }
+}
+
 }  // namespace
 
+scoped_refptr<cc::DisplayItemList> PaintArtifactCompositor::recordPendingLayer(
+    const PaintArtifact& artifact,
+    const PendingLayer& pendingLayer,
+    const gfx::Rect& combinedBounds) {
+  cc::DisplayItemListSettings settings;
+  scoped_refptr<cc::DisplayItemList> ccList =
+      cc::DisplayItemList::Create(settings);
+
+  gfx::Transform translation;

[pdr., 2016/12/20 06:46:30]

I don't understand the paired begin/end display items concept in this function.
Is it supporting non-composited effects? Which tests cover this?

[pdr., 2016/12/20 22:50:58]

After discussion, I now get this. It's just the code that turns non-composited
property tree nodes into display items. It uses a push and pop algorithm with
the property tree state iteration pattern to ensure the nesting is correct.

I think we're still missing tests though.

[chrishtr, 2016/12/20 23:36:32]

Explained in person.

The tests MergeSimpleChunks, MergeClip, MergeTransform and MergeNested
explicitly
exercise this code and test that it's done correctly.

There are also tests of PropertyTreeStateIterator and the
PropertyTreeState::innermostNode() method, which is another critical
piece of the algorithm.

[chrishtr, 2016/12/20 23:48:31]

Agreed offline no extra test needed.

+  translation.Translate(-combinedBounds.x(), -combinedBounds.y());
+  // Passing combinedBounds as the visual rect for the begin/end transform item
+  // would normally be the sensible thing to do, but see comment above re:
+  // visual rects for drawing items and further rework in flight.
+  ccList->CreateAndAppendPairedBeginItem<cc::TransformDisplayItem>(translation);
+
+  const DisplayItemList& displayItems = artifact.getDisplayItemList();
+  for (const auto& paintChunk : pendingLayer.paintChunks) {
+    const PropertyTreeState* state = &paintChunk->properties.propertyTreeState;
+    PropertyTreeStateIterator iterator(*state);
+    Vector<PropertyTreeState> pairedStates;
+    for (; state && *state != pendingLayer.propertyTreeState;
+         state = iterator.next()) {
+      if (state->innermostNode() != PropertyTreeState::None)
+        pairedStates.push_back(*state);
+    }
+
+    recordPairedBeginDisplayItems(pairedStates, ccList.get());
+
+    for (const auto& displayItem : displayItems.itemsInPaintChunk(*paintChunk))
+      appendDisplayItemToCcDisplayItemList(displayItem, ccList.get());
+
+    recordPairedEndDisplayItems(pairedStates, ccList.get());
+  }
+
+  ccList->CreateAndAppendPairedEndItem<cc::EndTransformDisplayItem>();
+
+  ccList->Finalize();
+  return ccList;
+}
+
 std::unique_ptr<PaintArtifactCompositor::ContentLayerClientImpl>
 PaintArtifactCompositor::clientForPaintChunk(
     const PaintChunk& paintChunk,
@@ -296,50 +384,70 @@ PaintArtifactCompositor::clientForPaintChunk(
           : paintArtifact.getDisplayItemList()[paintChunk.beginIndex].getId()));
 }
 
-scoped_refptr<cc::Layer> PaintArtifactCompositor::layerForPaintChunk(
+scoped_refptr<cc::Layer>
+PaintArtifactCompositor::compositedLayerForPendingLayer(
     const PaintArtifact& paintArtifact,
-    const PaintChunk& paintChunk,
+    const PendingLayer& pendingLayer,
     gfx::Vector2dF& layerOffset,
     Vector<std::unique_ptr<ContentLayerClientImpl>>& newContentLayerClients,
-    RasterInvalidationTracking* tracking) {
-  DCHECK(paintChunk.size());
+    RasterInvalidationTrackingMap<const PaintChunk>* trackingMap) {
+  DCHECK(pendingLayer.paintChunks.size());
+  const PaintChunk& firstPaintChunk = *pendingLayer.paintChunks[0];
+  DCHECK(firstPaintChunk.size());
+#if DCHECK_IS_ON
+  for (const auto& paintChunk : pendingLayer.paintChunks) {
+    DCHECK(paintChunk.properties == firstPaintChunk.properties);
+  }
+#endif
 
   // If the paint chunk is a foreign layer, just return that layer.
-  if (scoped_refptr<cc::Layer> foreignLayer =
-          foreignLayerForPaintChunk(paintArtifact, paintChunk, layerOffset))
+  if (scoped_refptr<cc::Layer> foreignLayer = foreignLayerForPaintChunk(
+          paintArtifact, firstPaintChunk, layerOffset)) {
+    DCHECK(pendingLayer.paintChunks.size() == 1);
     return foreignLayer;
+  }
 
   // The common case: create or reuse a PictureLayer for painted content.
   std::unique_ptr<ContentLayerClientImpl> contentLayerClient =
-      clientForPaintChunk(paintChunk, paintArtifact);
+      clientForPaintChunk(firstPaintChunk, paintArtifact);
+
+  gfx::Rect ccCombinedBounds(enclosingIntRect(pendingLayer.bounds));
 
-  gfx::Rect combinedBounds = enclosingIntRect(paintChunk.bounds);
   scoped_refptr<cc::DisplayItemList> displayList =
-      recordPaintChunk(paintArtifact, paintChunk, combinedBounds);
+      recordPendingLayer(paintArtifact, pendingLayer, ccCombinedBounds);

[wkorman, 2016/12/20 00:28:56]

Possible to have ccCombinedBounds be an empty rect here, if so should we
early-out/skip or otherwise avoid creating a cc::Layer at all?

[chrishtr, 2016/12/20 23:36:31]

It could, but that seems a premature optimization at this point in the
implementation cycle. I prefer to keep this simple for now.

   contentLayerClient->SetDisplayList(std::move(displayList));
-  contentLayerClient->SetPaintableRegion(gfx::Rect(combinedBounds.size()));
+  contentLayerClient->SetPaintableRegion(gfx::Rect(ccCombinedBounds.size()));
+
+  layerOffset = ccCombinedBounds.OffsetFromOrigin();
 
-  layerOffset = combinedBounds.OffsetFromOrigin();
   scoped_refptr<cc::PictureLayer> ccPictureLayer =
       contentLayerClient->ccPictureLayer();
-  ccPictureLayer->SetBounds(combinedBounds.size());
+  ccPictureLayer->SetBounds(ccCombinedBounds.size());
   ccPictureLayer->SetIsDrawable(true);
-  if (paintChunk.knownToBeOpaque)
-    ccPictureLayer->SetContentsOpaque(true);
-  DCHECK(!tracking ||
-         tracking->trackedRasterInvalidations.size() ==
-             paintChunk.rasterInvalidationRects.size());
-  for (unsigned index = 0; index < paintChunk.rasterInvalidationRects.size();
-       ++index) {
-    IntRect rect(enclosingIntRect(paintChunk.rasterInvalidationRects[index]));
-    gfx::Rect ccInvalidationRect(rect.x(), rect.y(), std::max(0, rect.width()),
-                                 std::max(0, rect.height()));
-    // Raster paintChunk.rasterInvalidationRects is in the space of the
-    // containing transform node, so need to subtract off the layer offset.
-    ccInvalidationRect.Offset(-combinedBounds.OffsetFromOrigin());
-    contentLayerClient->setNeedsDisplayRect(
-        ccInvalidationRect,
-        tracking ? &tracking->trackedRasterInvalidations[index] : nullptr);
+  ccPictureLayer->SetContentsOpaque(pendingLayer.knownToBeOpaque);
+
+  for (const auto& paintChunk : pendingLayer.paintChunks) {
+    RasterInvalidationTracking* rasterTracking =
+        trackingMap ? trackingMap->find(paintChunk) : nullptr;
+    DCHECK(!rasterTracking ||
+           rasterTracking->trackedRasterInvalidations.size() ==
+               paintChunk->rasterInvalidationRects.size());
+
+    for (unsigned index = 0; index < paintChunk->rasterInvalidationRects.size();
+         ++index) {
+      IntRect rect(
+          enclosingIntRect(paintChunk->rasterInvalidationRects[index]));
+      gfx::Rect ccInvalidationRect(rect.x(), rect.y(),
+                                   std::max(0, rect.width()),

[wkorman, 2016/12/20 00:28:56]

Edge cases we're guarding against with max() here and in next line could create
an empty rect. If that happens, should we skip some of the below?

[chrishtr, 2016/12/20 23:36:31]

Optimized.

+                                   std::max(0, rect.height()));
+      // Raster paintChunk.rasterInvalidationRects is in the space of the
+      // containing transform node, so need to subtract off the layer offset.
+      ccInvalidationRect.Offset(-ccCombinedBounds.OffsetFromOrigin());
+      contentLayerClient->setNeedsDisplayRect(
+          ccInvalidationRect,
+          rasterTracking ? &rasterTracking->trackedRasterInvalidations[index]
+                         : nullptr);
+    }
   }
 
   newContentLayerClients.append(std::move(contentLayerClient));
@@ -766,6 +874,54 @@ void PropertyTreeManager::buildEffectNodesRecursively(
 
 }  // namespace
 
+bool PaintArtifactCompositor::canMergeInto(
+    const PaintChunk& newChunk,
+    const PendingLayer& candidatePendingLayer) {
+  DCHECK(candidatePendingLayer.paintChunks.size() >= 1);
+  PropertyTreeStateIterator iterator(newChunk.properties.propertyTreeState);
+  for (const PropertyTreeState* currentState =
+           &newChunk.properties.propertyTreeState;
+       currentState; currentState = iterator.next()) {
+    if (currentState->hasDirectCompositingReasons())
+      return false;
+    if (*currentState == candidatePendingLayer.propertyTreeState)
+      return true;
+  }
+  return false;
+}
+
+bool PaintArtifactCompositor::overlaps(
+    const PaintChunk& paintChunk,
+    const PendingLayer& candidatePendingLayer,
+    GeometryMapper& geometryMapper) {
+  // TODO(chrishtr): implement

[wkorman, 2016/12/20 00:28:56]

Mentioned to pdr@ already, we should consider how to split out the logic growing
in PAC into separate classes for maintainability. When we add overlap
implementation could be a good early case. Could do similarly to how we moved
paint logic out of LayoutObject, perhaps, with a stack-alloc'd delegate class,
or just moving static methods to separate class. Could make unit testing easier.
Think about it!

+  return true;
+}
+
+void PaintArtifactCompositor::collectPendingLayers(
+    const Vector<PaintChunk>& paintChunks,
+    Vector<PendingLayer>& pendingLayers) {
+  GeometryMapper geometryMapper;
+  for (const PaintChunk& paintChunk : paintChunks) {

[pdr., 2016/12/20 06:46:30]

What do you think about the performance of this function? I think it will be at
least O(n^2) in the case of n independently transformed layers (sort of the
"famous.co" case).

[pdr., 2016/12/20 22:50:58]

We discussed this offline and other folks were aware of this. Can you please add
a comment here about optimizing this in the future? I agree 100% about moving
forward with this simple approach and optimizing later.

[chrishtr, 2016/12/20 23:36:31]

Added a comment about n^3 etc.

+    bool createNew = true;
+    for (Vector<PendingLayer>::reverse_iterator candidatePendingLayer =

[pdr., 2016/12/20 06:46:30]

Could this candidate layer loop could be skipped if the paint chunk has
immediate direct compositing reasons that prevent it from being merged with
other layers?

+             pendingLayers.rbegin();
+         candidatePendingLayer != pendingLayers.rend();
+         ++candidatePendingLayer) {
+      if (canMergeInto(paintChunk, *candidatePendingLayer)) {
+        candidatePendingLayer->add(paintChunk);
+        createNew = false;
+        break;
+      }
+      if (overlaps(paintChunk, *candidatePendingLayer, geometryMapper)) {
+        break;
+      }
+    }
+    if (createNew)
+      pendingLayers.append(PendingLayer(paintChunk));

[wkorman, 2016/12/20 00:28:56]

Does this move, or copy, the new PendingLayer instance? Move preferred, thought
worth checking.

[chrishtr, 2016/12/20 23:36:31]

Copies. I ran into some complications when attempting the move constructor,
prefer
to do that in another patch.

+  }
+}
+
 void PaintArtifactCompositor::update(
     const PaintArtifact& paintArtifact,
     RasterInvalidationTrackingMap<const PaintChunk>* rasterChunkInvalidations) {
@@ -787,23 +943,25 @@ void PaintArtifactCompositor::update(
   PropertyTreeManager propertyTreeManager(*layerTree->property_trees(),
                                           m_rootLayer.get());
 
+  Vector<PendingLayer> pendingLayers;

[wkorman, 2016/12/20 00:28:56]

Wondered whether there is optimization value to not allocating the initial
vector until/unless we know there will be something added to it.

[chrishtr, 2016/12/20 23:36:31]

Done.

+  collectPendingLayers(paintArtifact.paintChunks(), pendingLayers);
+
   Vector<std::unique_ptr<ContentLayerClientImpl>> newContentLayerClients;
   newContentLayerClients.reserveCapacity(paintArtifact.paintChunks().size());
-  for (const PaintChunk& paintChunk : paintArtifact.paintChunks()) {
+  for (const PendingLayer& pendingLayer : pendingLayers) {
     gfx::Vector2dF layerOffset;
-    scoped_refptr<cc::Layer> layer = layerForPaintChunk(
-        paintArtifact, paintChunk, layerOffset, newContentLayerClients,
-        rasterChunkInvalidations ? rasterChunkInvalidations->find(&paintChunk)
-                                 : nullptr);
+    scoped_refptr<cc::Layer> layer = compositedLayerForPendingLayer(
+        paintArtifact, pendingLayer, layerOffset, newContentLayerClients,
+        rasterChunkInvalidations);
 
     int transformId = propertyTreeManager.compositorIdForTransformNode(
-        paintChunk.properties.propertyTreeState.transform());
+        pendingLayer.propertyTreeState.transform());
     int scrollId = propertyTreeManager.compositorIdForScrollNode(
-        paintChunk.properties.propertyTreeState.scroll());
+        pendingLayer.propertyTreeState.scroll());
     int clipId = propertyTreeManager.compositorIdForClipNode(
-        paintChunk.properties.propertyTreeState.clip());
+        pendingLayer.propertyTreeState.clip());
     int effectId = propertyTreeManager.switchToEffectNode(
-        *paintChunk.properties.propertyTreeState.effect());
+        *pendingLayer.propertyTreeState.effect());
 
     propertyTreeManager.updateScrollOffset(layer->id(), scrollId);
 
@@ -822,8 +980,7 @@ void PaintArtifactCompositor::update(
                                      ->transform_tree.Node(transformId)
                                      ->sorting_context_id);
 
-    layer->SetShouldCheckBackfaceVisibility(
-        paintChunk.properties.backfaceHidden);
+    layer->SetShouldCheckBackfaceVisibility(pendingLayer.backfaceHidden);
 
     if (m_extraDataForTestingEnabled)
       m_extraDataForTesting->contentLayers.append(layer);