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

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"
 #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"
 #include "cc/trees/layer_tree_host.h"
 #include "cc/trees/property_tree.h"
 #include "cc/trees/scroll_node.h"
 #include "cc/trees/transform_node.h"
 #include "platform/RuntimeEnabledFeatures.h"
 #include "platform/graphics/paint/ClipPaintPropertyNode.h"
 #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"
 #include "public/platform/Platform.h"
 #include "public/platform/WebCompositorSupport.h"
 #include "public/platform/WebLayer.h"
 #include "ui/gfx/geometry/point.h"
 #include "ui/gfx/geometry/point_f.h"
 #include "ui/gfx/geometry/rect.h"
 #include "ui/gfx/geometry/rect_f.h"
@@ skipping 193 matching lines @@
     // gfx::Rect bounds = gfx::SkIRectToRect(picture->cullRect().roundOut());
     // or use the visual rect directly. However, clip content layers attempt
     // to raster in a different space than that of the visual rects. We'll be
     // reworking visual rects further for SPv2, so for now we just pass a
     // visual rect large enough to make sure items raster.
     list->CreateAndAppendDrawingItem<cc::DrawingDisplayItem>(
         largeRect, sk_ref_sp(picture));
   }
 }
 
-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,
     gfx::Vector2dF& layerOffset) {
   if (paintChunk.size() != 1)
     return nullptr;
 
   const auto& displayItem =
       paintArtifact.getDisplayItemList()[paintChunk.beginIndex];
   if (!displayItem.isForeignLayer())
     return nullptr;
 
   const auto& foreignLayerDisplayItem =
       static_cast<const ForeignLayerDisplayItem&>(displayItem);
   layerOffset = gfx::Vector2dF(foreignLayerDisplayItem.location().x(),
                                foreignLayerDisplayItem.location().y());
   scoped_refptr<cc::Layer> layer = foreignLayerDisplayItem.layer();
   layer->SetBounds(foreignLayerDisplayItem.bounds());
   layer->SetIsDrawable(true);
   return layer;
 }
 
 constexpr int kInvalidNodeId = -1;
 // cc's property trees use 0 for the root node (always non-null).
 constexpr int kRealRootNodeId = 0;
 // cc allocates special nodes for root effects such as the device scale.
 constexpr int kSecondaryRootNodeId = 1;
 constexpr int kPropertyTreeSequenceNumber = 1;
 
+struct RectAndClipState {

[pdr., 2016/12/22 19:46:26]

Nit: remove this (not used).

[chrishtr, 2016/12/22 19:53:54]

Removed.

+  RectAndClipState() : RectAndClipState(FloatRect(), nullptr) {}
+  RectAndClipState(const FloatRect& rectArg, const PropertyTreeState* stateArg)
+      : rect(rectArg), propertyTreeState(stateArg) {}
+  FloatRect rect;
+  const PropertyTreeState* propertyTreeState;
+};
+
+enum EndDisplayItemType { EndTransform, EndClip, EndEffect };
+
+// Applies the clips between |localState| and |ancestorState| into a single
+// combined cc::FloatClipDisplayItem on |ccList|.
+static void applyClipsBetweenStates(const PropertyTreeState& localState,
+                       const PropertyTreeState& ancestorState,
+                       cc::DisplayItemList& ccList,
+                       Vector<EndDisplayItemType>& endDisplayItems,
+                       GeometryMapper& geometryMapper) {
+  DCHECK(localState.transform() == ancestorState.transform());
+#ifdef DCHECK_IS_ON
+  const TransformPaintPropertyNode* transformNode =
+      localState.clip()->localTransformSpace();
+  if (transformNode != ancestorState.transform()) {
+      bool success = false;
+      const TransformationMatrix& localToAncestorMatrix =
+          geometryMapper.localToAncestorMatrix(transformNode, ancestorState,
+                                               success);
+      DCHECK(success);
+      // Clips are only in descendant spaces that are transformed by one
+      // or more scrolls.
+      DCHECK(localToAncestorMatrix.isIdentityOrTranslation());
+

[pdr., 2016/12/22 19:46:26]

nit: newline.

[chrishtr, 2016/12/22 19:53:54]

Done.

+  }
+#endif
+
+  static FloatRect infinteFloatRect = FloatRect(LayoutRect::infiniteIntRect());

[pdr., 2016/12/22 19:46:26]

This won't actually be equal to an infinite float rect. What is this code for?

[chrishtr, 2016/12/22 19:53:54]

The early-out is to avoid effects that do nothing. But I can remove that.

Otherwise, I have to supply some input to the clip machinery in
localToVisualRectInAncestorSpace. Note that PaintLayerClipper does the same
thing..

+  FloatRect combinedClip;
+  bool success = false;
+  combinedClip = geometryMapper.localToVisualRectInAncestorSpace(
+      infinteFloatRect, localState, ancestorState, success);
+  DCHECK(success);
+  if (combinedClip == infinteFloatRect)
+    return;
+
+  ccList.CreateAndAppendPairedBeginItem<cc::FloatClipDisplayItem>(
+      gfx::RectF(combinedClip));
+  endDisplayItems.push_back(EndClip);
+}
+
+static void recordPairedBeginDisplayItems(
+    const Vector<PropertyTreeState>& pairedStates,
+    const PropertyTreeState& pendingLayerState,
+    cc::DisplayItemList& ccList,
+    Vector<EndDisplayItemType>& endDisplayItems,
+    GeometryMapper& geometryMapper) {
+  PropertyTreeState mappedClipDestinationSpace = pendingLayerState;
+  PropertyTreeState clipSpace = pendingLayerState;
+  bool hasClip = false;
+
+  for (Vector<PropertyTreeState>::const_reverse_iterator pairedState =

[pdr., 2016/12/22 19:46:26]

Please add a comments here describing this algorithm at a high level, and how
clips are pushed around and effects are transformed with a 2d offset.

[chrishtr, 2016/12/22 19:53:54]

I added a comment in the .h file for the method which calls, this, that refers
readers to the designdoc. Good enough, or add more comments?

+           pairedStates.rbegin();
+       pairedState != pairedStates.rend(); ++pairedState) {
+    switch (pairedState->innermostNode()) {
+      case PropertyTreeState::Transform: {
+        if (hasClip) {
+          applyClipsBetweenStates(clipSpace, mappedClipDestinationSpace, ccList,
+                     endDisplayItems, geometryMapper);
+        }
+        mappedClipDestinationSpace = *pairedState;
+        clipSpace = *pairedState;
+
+        gfx::Transform transform(gfx::Transform::kSkipInitialization);
+        transform.matrix() = TransformationMatrix::toSkMatrix44(
+            pairedState->transform()->matrix());
+
+        ccList.CreateAndAppendPairedBeginItem<cc::TransformDisplayItem>(
+            transform);
+        endDisplayItems.push_back(EndTransform);
+        break;
+      }
+      case PropertyTreeState::Clip: {
+        // Clips are handled in |applyClips| when ending the iterator, or
+        // transitioning between transform spaces. Here we store off the
+        // PropertyTreeState of the first found clip,

[pdr., 2016/12/22 19:46:26]

Nit: reflow this comment.

[chrishtr, 2016/12/22 19:53:54]

Done.

+        // under the transform of pairedState->transform(). All subsequent clips
+        // before applying the
+        // transform will be applied in applyClips.
+        clipSpace = *pairedState;
+        hasClip = true;
+#ifdef DCHECK_IS_ON
+        if (pairedState->clip()->localTransformSpace() !=
+            pairedState->transform()) {
+          const TransformationMatrix& localTransformMatrix =
+              pairedState->effect()->localTransformSpace()->matrix();
+          // Clips are only in descendant spaces that are transformed by scroll.
+          DCHECK(localTransformMatrix.isIdentityOrTranslation());
+        }
+#endif
+        break;
+      }
+      case PropertyTreeState::Effect: {
+        // TODO(chrishtr): skip effect and/or compositing display items if
+        // not necessary.
+
+        FloatRect clipRect =
+            pairedState->effect()->outputClip()->clipRect().rect();
+        // TODO(chrishtr): specify origin of the filter.

[pdr., 2016/12/22 19:46:26]

Non-rhetorical question: what will the origin be equal to?

[chrishtr, 2016/12/22 19:53:54]

Filters can have origins specified by the offsets from the element of the
filter. SPv1 supports it, but it's not yet implemented on effect nodes.

+        FloatPoint filterOrigin;
+        if (pairedState->effect()->localTransformSpace() !=
+            pairedState->transform()) {
+          bool success = false;
+          const TransformPaintPropertyNode* transformNode =
+              pairedState->effect()->localTransformSpace();
+          const TransformationMatrix& localToAncestorMatrix =
+              geometryMapper.localToAncestorMatrix(transformNode, *pairedState,
+                                                   success);
+          DCHECK(success);
+          // Effects are only in descendant spaces that are transformed by one
+          // or more scrolls.
+          DCHECK(localToAncestorMatrix.isIdentityOrTranslation());
+
+          clipRect = localToAncestorMatrix.mapRect(clipRect);
+          filterOrigin = localToAncestorMatrix.mapPoint(filterOrigin);
+        }
+
+        ccList.CreateAndAppendPairedBeginItem<cc::FilterDisplayItem>(
+            pairedState->effect()->filter().asCcFilterOperations(),
+            pairedState->effect()->outputClip()->clipRect().rect(),
+            gfx::PointF(filterOrigin.x(), filterOrigin.y()));
+        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);
+        endDisplayItems.push_back(EndEffect);
+        break;
+      }
+      case PropertyTreeState::None:
+        break;
+    }
+  }
+
+  if (hasClip) {
+    applyClipsBetweenStates(clipSpace, mappedClipDestinationSpace, ccList, endDisplayItems,
+               geometryMapper);
+  }
+}
+
+static void recordPairedEndDisplayItems(
+    const Vector<EndDisplayItemType>& endDisplayItemTypes,
+    cc::DisplayItemList* ccList) {
+  for (Vector<EndDisplayItemType>::const_reverse_iterator endType =
+           endDisplayItemTypes.rbegin();
+       endType != endDisplayItemTypes.rend(); ++endType) {
+    switch (*endType) {
+      case EndTransform:
+        ccList->CreateAndAppendPairedEndItem<cc::EndTransformDisplayItem>();
+        break;
+      case EndClip:
+        ccList->CreateAndAppendPairedEndItem<cc::EndFloatClipDisplayItem>();
+        break;
+      case EndEffect:
+        ccList->CreateAndAppendPairedEndItem<cc::EndCompositingDisplayItem>();
+        ccList->CreateAndAppendPairedEndItem<cc::EndFilterDisplayItem>();
+        break;
+    }
+  }
+}
+
 }  // namespace
 
+scoped_refptr<cc::DisplayItemList> PaintArtifactCompositor::recordPendingLayer(
+    const PaintArtifact& artifact,
+    const PendingLayer& pendingLayer,
+    const gfx::Rect& combinedBounds,
+    GeometryMapper& geometryMapper) {
+  cc::DisplayItemListSettings settings;
+  scoped_refptr<cc::DisplayItemList> ccList =
+      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.
+  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);
+    }
+
+    // TODO(chrishtr): we can avoid some extra paired display items if
+    // multiple PaintChunks share them. We can also collapse clips between
+    // transforms into single clips in the same way that PaintLayerClipper does.
+    Vector<EndDisplayItemType> endDisplayItems;
+
+    recordPairedBeginDisplayItems(pairedStates, pendingLayer.propertyTreeState,
+                                  *ccList.get(), endDisplayItems,
+                                  geometryMapper);
+
+    for (const auto& displayItem : displayItems.itemsInPaintChunk(*paintChunk))
+      appendDisplayItemToCcDisplayItemList(displayItem, ccList.get());
+
+    recordPairedEndDisplayItems(endDisplayItems, ccList.get());
+  }
+
+  ccList->CreateAndAppendPairedEndItem<cc::EndTransformDisplayItem>();
+
+  ccList->Finalize();
+  return ccList;
+}
+
 std::unique_ptr<PaintArtifactCompositor::ContentLayerClientImpl>
 PaintArtifactCompositor::clientForPaintChunk(
     const PaintChunk& paintChunk,
     const PaintArtifact& paintArtifact) {
   // TODO(chrishtr): for now, just using a linear walk. In the future we can
   // optimize this by using the same techniques used in PaintController for
   // display lists.
   for (auto& client : m_contentLayerClients) {
     if (client && client->matches(paintChunk))
       return std::move(client);
   }
 
   return WTF::wrapUnique(new ContentLayerClientImpl(
       paintChunk.id
           ? *paintChunk.id
           : 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,
-    bool storeDebugInfo) {
-  DCHECK(paintChunk.size());
+    RasterInvalidationTrackingMap<const PaintChunk>* trackingMap,
+    bool storeDebugInfo,
+    GeometryMapper& geometryMapper) {
+  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 combinedBounds = enclosingIntRect(paintChunk.bounds);
-  scoped_refptr<cc::DisplayItemList> displayList =
-      recordPaintChunk(paintArtifact, paintChunk, combinedBounds);
+  gfx::Rect ccCombinedBounds(enclosingIntRect(pendingLayer.bounds));
+
+  scoped_refptr<cc::DisplayItemList> displayList = recordPendingLayer(
+      paintArtifact, pendingLayer, ccCombinedBounds, geometryMapper);
   contentLayerClient->SetDisplayList(std::move(displayList));
-  contentLayerClient->SetPaintableRegion(gfx::Rect(combinedBounds.size()));
+  contentLayerClient->SetPaintableRegion(gfx::Rect(ccCombinedBounds.size()));
 
-  layerOffset = combinedBounds.OffsetFromOrigin();
+  layerOffset = ccCombinedBounds.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());
+  ccPictureLayer->SetContentsOpaque(pendingLayer.knownToBeOpaque);
+  contentLayerClient->clearPaintChunkDebugData();
 
-  contentLayerClient->clearPaintChunkDebugData();
-  if (storeDebugInfo) {
-    contentLayerClient->addPaintChunkDebugData(
-        paintArtifact.getDisplayItemList().subsequenceAsJSON(
-            paintChunk.beginIndex, paintChunk.endIndex,
-            DisplayItemList::SkipNonDrawings |
-                DisplayItemList::ShownOnlyDisplayItemTypes));
-  }
+  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()),
-                                 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);
+    if (storeDebugInfo) {
+      contentLayerClient->addPaintChunkDebugData(
+          paintArtifact.getDisplayItemList().subsequenceAsJSON(
+              paintChunk->beginIndex, paintChunk->endIndex,
+              DisplayItemList::SkipNonDrawings |
+                  DisplayItemList::ShownOnlyDisplayItemTypes));
+    }
+
+    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()));
+      if (ccInvalidationRect.IsEmpty())
+        continue;
+      // 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));
   return ccPictureLayer;
 }
 
 namespace {
 
 class PropertyTreeManager {
   WTF_MAKE_NONCOPYABLE(PropertyTreeManager);
@@ skipping 292 matching lines @@
   scrollTree().set_needs_update(true);
 }
 
 unsigned depth(const EffectPaintPropertyNode* node) {
   unsigned result = 0;
   for (; node; node = node->parent())
     result++;
   return result;
 }
 
+// TODO(chrishtr): templatize this to avoid duplication of
+// GeometryMapper::leastCommonAncestor.
 const EffectPaintPropertyNode* lowestCommonAncestor(
     const EffectPaintPropertyNode* nodeA,
     const EffectPaintPropertyNode* nodeB) {
   // Optimized common case.
   if (nodeA == nodeB)
     return nodeA;
 
   unsigned depthA = depth(nodeA), depthB = depth(nodeB);
   while (depthA > depthB) {
     nodeA = nodeA->parent();
@@ skipping 94 matching lines @@
 
   dummyLayer->set_property_tree_sequence_number(kPropertyTreeSequenceNumber);
   dummyLayer->SetTransformTreeIndex(kSecondaryRootNodeId);
   dummyLayer->SetClipTreeIndex(outputClipId);
   dummyLayer->SetEffectTreeIndex(effectNode.id);
   dummyLayer->SetScrollTreeIndex(kRealRootNodeId);
 }
 
 }  // 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
+  return true;
+}
+
+PaintArtifactCompositor::PendingLayer::PendingLayer(
+    const PaintChunk& firstPaintChunk)
+    : knownToBeOpaque(true),
+      backfaceHidden(firstPaintChunk.properties.backfaceHidden),
+      propertyTreeState(firstPaintChunk.properties.propertyTreeState) {
+  add(firstPaintChunk);
+}
+
+void PaintArtifactCompositor::PendingLayer::add(const PaintChunk& paintChunk) {
+  DCHECK(paintChunk.properties.backfaceHidden == backfaceHidden);
+  paintChunks.append(&paintChunk);
+  bounds.unite(paintChunk.bounds);
+  knownToBeOpaque = knownToBeOpaque && paintChunk.knownToBeOpaque;
+}
+
+void PaintArtifactCompositor::collectPendingLayers(
+    const Vector<PaintChunk>& paintChunks,
+    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 : paintChunks) {
+    bool createNew = true;
+    for (Vector<PendingLayer>::reverse_iterator candidatePendingLayer =
+             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));
+  }
+}
+
 void PaintArtifactCompositor::update(
     const PaintArtifact& paintArtifact,
     RasterInvalidationTrackingMap<const PaintChunk>* rasterChunkInvalidations,
     bool storeDebugInfo) {
   DCHECK(m_rootLayer);
 
   cc::LayerTree* layerTree = m_rootLayer->GetLayerTree();
 
   // The tree will be null after detaching and this update can be ignored.
   // See: WebViewImpl::detachPaintArtifactCompositor().
   if (!layerTree)
     return;
 
   if (m_extraDataForTestingEnabled)
     m_extraDataForTesting = WTF::wrapUnique(new ExtraDataForTesting);
 
   m_rootLayer->RemoveAllChildren();
   m_rootLayer->set_property_tree_sequence_number(kPropertyTreeSequenceNumber);
 
   PropertyTreeManager propertyTreeManager(*layerTree->property_trees(),
                                           m_rootLayer.get());
 
+  Vector<PendingLayer, 0> pendingLayers;
+  GeometryMapper geometryMapper;
+  collectPendingLayers(paintArtifact.paintChunks(), pendingLayers,
+                       geometryMapper);
+
   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,
-        storeDebugInfo);
+    scoped_refptr<cc::Layer> layer = compositedLayerForPendingLayer(
+        paintArtifact, pendingLayer, layerOffset, newContentLayerClients,
+        rasterChunkInvalidations, storeDebugInfo, geometryMapper);
 
     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);
 
     layer->set_offset_to_transform_parent(layerOffset);
 
     m_rootLayer->AddChild(layer);
     layer->set_property_tree_sequence_number(kPropertyTreeSequenceNumber);
     layer->SetTransformTreeIndex(transformId);
     layer->SetClipTreeIndex(clipId);
     layer->SetEffectTreeIndex(effectId);
     layer->SetScrollTreeIndex(scrollId);
 
     // TODO(jbroman): This probably shouldn't be necessary, but it is still
     // queried by RenderSurfaceImpl.
     layer->Set3dSortingContextId(layerTree->property_trees()
                                      ->transform_tree.Node(transformId)
                                      ->sorting_context_id);
 
-    layer->SetShouldCheckBackfaceVisibility(
-        paintChunk.properties.backfaceHidden);
+    layer->SetShouldCheckBackfaceVisibility(pendingLayer.backfaceHidden);
 
     if (m_extraDataForTestingEnabled)
       m_extraDataForTesting->contentLayers.append(layer);
   }
   m_contentLayerClients.clear();
   m_contentLayerClients.swap(newContentLayerClients);
 
   // Mark the property trees as having been rebuilt.
   layerTree->property_trees()->sequence_number = kPropertyTreeSequenceNumber;
   layerTree->property_trees()->needs_rebuild = false;
   layerTree->property_trees()->ResetCachedData();
 }
 
 }  // namespace blink