Raster display item lists via a visual rect RTree.

cc/playback/display_item_list.cc

Index: cc/playback/display_item_list.cc
diff --git a/cc/playback/display_item_list.cc b/cc/playback/display_item_list.cc
index a1a9cdbfc569a99c65c9243bb4cd41cc05fa0525..32c7be61d02ef64892d4678d8acd7ab6503c902b 100644
--- a/cc/playback/display_item_list.cc
+++ b/cc/playback/display_item_list.cc
@@ -23,6 +23,7 @@
 #include "third_party/skia/include/core/SkPictureRecorder.h"
 #include "third_party/skia/include/utils/SkPictureUtils.h"
 #include "ui/gfx/geometry/rect.h"
+#include "ui/gfx/geometry/rect_conversions.h"
 #include "ui/gfx/skia_util.h"
 
 namespace cc {
@@ -45,19 +46,15 @@ const int kDefaultNumDisplayItemsToReserve = 100;
 }  // namespace
 
 scoped_refptr<DisplayItemList> DisplayItemList::Create(
-    const gfx::Rect& layer_rect,
     const DisplayItemListSettings& settings) {
-  return make_scoped_refptr(new DisplayItemList(
-      layer_rect, settings,
-      !settings.use_cached_picture || DisplayItemsTracingEnabled()));
+  return make_scoped_refptr(new DisplayItemList(settings));
 }
 
 scoped_refptr<DisplayItemList> DisplayItemList::CreateFromProto(
     const proto::DisplayItemList& proto) {
   gfx::Rect layer_rect = ProtoToRect(proto.layer_rect());
   scoped_refptr<DisplayItemList> list =
-      DisplayItemList::Create(ProtoToRect(proto.layer_rect()),
-                              DisplayItemListSettings(proto.settings()));
+      DisplayItemList::Create(DisplayItemListSettings(proto.settings()));
 
   for (int i = 0; i < proto.items_size(); i++) {
     const proto::DisplayItem& item_proto = proto.items(i);
@@ -70,29 +67,16 @@ scoped_refptr<DisplayItemList> DisplayItemList::CreateFromProto(
   return list;
 }
 
-DisplayItemList::DisplayItemList(gfx::Rect layer_rect,
-                                 const DisplayItemListSettings& settings,
-                                 bool retain_individual_display_items)
+DisplayItemList::DisplayItemList(const DisplayItemListSettings& settings)
     : items_(LargestDisplayItemSize(),
              LargestDisplayItemSize() * kDefaultNumDisplayItemsToReserve),
       settings_(settings),
-      retain_individual_display_items_(retain_individual_display_items),
-      layer_rect_(layer_rect),
-      is_suitable_for_gpu_rasterization_(true),
+      all_items_are_suitable_for_gpu_rasterization_(true),
       approximate_op_count_(0),
-      picture_memory_usage_(0),
       external_memory_usage_(0) {
 #if DCHECK_IS_ON()
-  needs_process_ = false;
+  needs_finalize_ = false;
 #endif
-  if (settings_.use_cached_picture) {
-    SkRTreeFactory factory;
-    recorder_.reset(new SkPictureRecorder());
-    canvas_ = skia::SharePtr(recorder_->beginRecording(
-        layer_rect_.width(), layer_rect_.height(), &factory));
-    canvas_->translate(-layer_rect_.x(), -layer_rect_.y());
-    canvas_->clipRect(gfx::RectToSkRect(layer_rect_));
-  }
 }
 
 DisplayItemList::~DisplayItemList() {
@@ -101,10 +85,10 @@ DisplayItemList::~DisplayItemList() {
 void DisplayItemList::ToProtobuf(proto::DisplayItemList* proto) {
   // The flattened SkPicture approach is going away, and the proto
   // doesn't currently support serializing that flattened picture.
-  DCHECK(retain_individual_display_items_);
+  // DCHECK(retain_individual_display_items_);
 
-  RectToProto(layer_rect_, proto->mutable_layer_rect());
-  settings_.ToProtobuf(proto->mutable_settings());
+  // RectToProto(layer_rect_, proto->mutable_layer_rect());
+  // settings_.ToProtobuf(proto->mutable_settings());
 
   DCHECK_EQ(0, proto->items_size());
   for (const auto& item : items_)
@@ -113,154 +97,85 @@ void DisplayItemList::ToProtobuf(proto::DisplayItemList* proto) {
 
 void DisplayItemList::Raster(SkCanvas* canvas,
                              SkPicture::AbortCallback* callback,
-                             const gfx::Rect& canvas_target_playback_rect,
+                             const gfx::Rect& canvas_playback_rect,
                              float contents_scale) const {
-  DCHECK(ProcessAppendedItemsCalled());
-  if (!settings_.use_cached_picture) {
-    canvas->save();
-    canvas->scale(contents_scale, contents_scale);
-    for (const auto& item : items_)
-      item.Raster(canvas, canvas_target_playback_rect, callback);
-    canvas->restore();
-  } else {
-    DCHECK(picture_);
-
-    canvas->save();
-    canvas->scale(contents_scale, contents_scale);
-    canvas->translate(layer_rect_.x(), layer_rect_.y());
-    if (callback) {
-      // If we have a callback, we need to call |draw()|, |drawPicture()|
-      // doesn't take a callback.  This is used by |AnalysisCanvas| to early
-      // out.
-      picture_->playback(canvas, callback);
-    } else {
-      // Prefer to call |drawPicture()| on the canvas since it could place the
-      // entire picture on the canvas instead of parsing the skia operations.
-      canvas->drawPicture(picture_.get());
-    }
-    canvas->restore();
-  }
+  DCHECK(FinalizeCalled());
+  canvas->save();
+  canvas->scale(contents_scale, contents_scale);
+
+  gfx::Rect query_rect = GetQueryRect(canvas_playback_rect, contents_scale);
+  std::vector<size_t> indices;
+  rtree_.Search(query_rect, &indices);
+  for (size_t index : indices)
+    items_[index].Raster(canvas, callback);
+  canvas->restore();
 }
 
-void DisplayItemList::ProcessAppendedItemsOnTheFly() {
-  if (retain_individual_display_items_)
-    return;
-  if (items_.size() >= kDefaultNumDisplayItemsToReserve) {
-    ProcessAppendedItems();
-    // This function exists to keep the |items_| from growing indefinitely if
-    // we're not going to store them anyway. So the items better be deleted
-    // after |items_| grows too large and we process it.
-    DCHECK(items_.empty());
-  }
+gfx::Rect DisplayItemList::GetQueryRect(const gfx::Rect& rect, float scale) const {
+  // If the playback rect is empty, assume that we need to play back everything.
+  // TODO(wkorman): Double-check scaling the rectangle.
+  return rect.IsEmpty() ? rtree_.GetBounds()
+      : ScaleToEnclosingRect(rect, 1.f / scale);
 }
 
-void DisplayItemList::ProcessAppendedItems() {
+void DisplayItemList::Finalize() {
 #if DCHECK_IS_ON()
-  needs_process_ = false;
+  needs_finalize_ = false;
 #endif
-  for (const DisplayItem& item : items_) {
-    if (settings_.use_cached_picture) {
-      // When using a cached picture we will calculate gpu suitability on the
-      // entire cached picture instead of the items. This is more permissive
-      // since none of the items might individually trigger a veto even though
-      // they collectively have enough "bad" operations that a corresponding
-      // Picture would get vetoed. See crbug.com/513016.
-      DCHECK(canvas_);
-      approximate_op_count_ += item.approximate_op_count();
-      item.Raster(canvas_.get(), gfx::Rect(), nullptr);
-    } else {
-      is_suitable_for_gpu_rasterization_ &=
-          item.is_suitable_for_gpu_rasterization();
-      approximate_op_count_ += item.approximate_op_count();
-    }
-
-    if (retain_individual_display_items_) {
-      // Warning: this double-counts SkPicture data if use_cached_picture is
-      // also true.
-      external_memory_usage_ += item.external_memory_usage();
-    }
+  // LOG(ERROR) << AsValue(true)->ToString().c_str() << "\n";
+
+  int i = 0;
+  for (const auto& item : items_) {
+    all_items_are_suitable_for_gpu_rasterization_ &=
+        item.is_suitable_for_gpu_rasterization();
+    approximate_op_count_ += item.approximate_op_count();
+    external_memory_usage_ += item.external_memory_usage();
+    // LOG(ERROR) << base::StringPrintf("item visual rect: (%0.2f, %0.2f, %0.2f,
+    // %0.2f)",
+    //                                  visual_rects_[i].x(),
+    //                                  visual_rects_[i].y(),
+    //                                  visual_rects_[i].width(),
+    //                                  visual_rects_[i].height());
+    i++;
   }
 
-  if (!retain_individual_display_items_)
-    items_.Clear();
-}
-
-void DisplayItemList::RasterIntoCanvas(const DisplayItem& item) {
-  DCHECK(canvas_);
-  DCHECK(!retain_individual_display_items_);
-  approximate_op_count_ += item.approximate_op_count();
-
-  item.Raster(canvas_.get(), gfx::Rect(), nullptr);
-}
-
-bool DisplayItemList::RetainsIndividualDisplayItems() const {
-  return retain_individual_display_items_;
-}
+  // LOG(ERROR) << "item count: " << i;
 
-void DisplayItemList::RemoveLast() {
-  // We cannot remove the last item if it has been squashed into a picture.
-  // The last item should not have been handled by ProcessAppendedItems, so we
-  // don't need to remove it from approximate_op_count_, etc.
-  DCHECK(retain_individual_display_items_);
-  DCHECK(!settings_.use_cached_picture);
-  items_.RemoveLast();
-}
-
-void DisplayItemList::Finalize() {
   // TODO(wkorman): Uncomment the assert below once we've investigated
   // and resolved issues. http://crbug.com/557905
-  // DCHECK_EQ(items_.size(), visual_rects_.size());
+  DCHECK_EQ(items_.size(), visual_rects_.size());
 
-  // TODO(vmpstr): Build and make use of an RTree from the visual
-  // rects. For now we just clear them out since we won't ever need
-  // them to stick around post-Finalize. http://crbug.com/527245
-  visual_rects_.clear();
+  // TODO(wkorman): These are RectF rather than Rect in
+  // http://crrev.com/1459003003 does it matter?
+  rtree_.Build(visual_rects_);
 
-  ProcessAppendedItems();
-
-  if (settings_.use_cached_picture) {
-    // Convert to an SkPicture for faster rasterization.
-    DCHECK(settings_.use_cached_picture);
-    DCHECK(!picture_);
-    picture_ = skia::AdoptRef(recorder_->endRecordingAsPicture());
-    DCHECK(picture_);
-    picture_memory_usage_ =
-        SkPictureUtils::ApproximateBytesUsed(picture_.get());
-    recorder_.reset();
-    canvas_.clear();
-    is_suitable_for_gpu_rasterization_ =
-        picture_->suitableForGpuRasterization(nullptr);
-  }
+  visual_rects_.clear();
 }
 
 bool DisplayItemList::IsSuitableForGpuRasterization() const {
-  DCHECK(ProcessAppendedItemsCalled());
-  return is_suitable_for_gpu_rasterization_;
+  DCHECK(FinalizeCalled());
+  // This is more permissive than Picture's implementation, since none of the
+  // items might individually trigger a veto even though they collectively have
+  // enough "bad" operations that a corresponding Picture would get vetoed. See
+  // crbug.com/513016.
+  return all_items_are_suitable_for_gpu_rasterization_;
 }
 
 int DisplayItemList::ApproximateOpCount() const {
-  DCHECK(ProcessAppendedItemsCalled());
+  DCHECK(FinalizeCalled());
   return approximate_op_count_;
 }
 
 size_t DisplayItemList::ApproximateMemoryUsage() const {
-  DCHECK(ProcessAppendedItemsCalled());
-  // We double-count in this case. Produce zero to avoid being misleading.
-  if (settings_.use_cached_picture && retain_individual_display_items_)
-    return 0;
-
-  DCHECK(!settings_.use_cached_picture || picture_);
-
+  DCHECK(FinalizeCalled());
   size_t memory_usage = sizeof(*this);
 
   // Memory outside this class due to |items_|.
   memory_usage += items_.GetCapacityInBytes() + external_memory_usage_;
 
-  // Memory outside this class due to |picture|.
-  memory_usage += picture_memory_usage_;
-
   // TODO(jbroman): Does anything else owned by this class substantially
   // contribute to memory usage?
+  // TODO(vmpstr): Probably DiscardableImageMap is worth counting here.
 
   return memory_usage;
 }
@@ -271,7 +186,7 @@ bool DisplayItemList::ShouldBeAnalyzedForSolidColor() const {
 
 scoped_refptr<base::trace_event::ConvertableToTraceFormat>
 DisplayItemList::AsValue(bool include_items) const {
-  DCHECK(ProcessAppendedItemsCalled());
+  DCHECK(FinalizeCalled());
   scoped_refptr<base::trace_event::TracedValue> state =
       new base::trace_event::TracedValue();
 
@@ -279,7 +194,7 @@ DisplayItemList::AsValue(bool include_items) const {
   if (include_items) {
     state->BeginArray("items");
     size_t item_index = 0;
-    for (const DisplayItem& item : items_) {
+    for (const auto& item : items_) {
       item.AsValueInto(visual_rects_.size() >= item_index
                            ? visual_rects_[item_index]
                            : gfx::Rect(),
@@ -288,16 +203,15 @@ DisplayItemList::AsValue(bool include_items) const {
     }
     state->EndArray();  // "items".
   }
-  state->SetValue("layer_rect", MathUtil::AsValue(layer_rect_));
   state->EndDictionary();  // "params".
 
-  if (!layer_rect_.IsEmpty()) {
+  if (!items_.empty()) {
     SkPictureRecorder recorder;
-    SkCanvas* canvas =
-        recorder.beginRecording(layer_rect_.width(), layer_rect_.height());
-    canvas->translate(-layer_rect_.x(), -layer_rect_.y());
-    canvas->clipRect(gfx::RectToSkRect(layer_rect_));
-    Raster(canvas, NULL, gfx::Rect(), 1.f);
+    gfx::Rect bounds = rtree_.GetBounds();
+    SkCanvas* canvas = recorder.beginRecording(bounds.width(), bounds.height());
+    canvas->translate(-bounds.x(), -bounds.y());
+    canvas->clipRect(gfx::RectToSkRect(bounds));
+    Raster(canvas, nullptr, gfx::Rect(), 1.f);
     skia::RefPtr<SkPicture> picture =
         skia::AdoptRef(recorder.endRecordingAsPicture());
 
@@ -310,7 +224,7 @@ DisplayItemList::AsValue(bool include_items) const {
 }
 
 void DisplayItemList::EmitTraceSnapshot() const {
-  DCHECK(ProcessAppendedItemsCalled());
+  DCHECK(FinalizeCalled());
   TRACE_EVENT_OBJECT_SNAPSHOT_WITH_ID(
       TRACE_DISABLED_BY_DEFAULT("cc.debug.display_items") ","
       TRACE_DISABLED_BY_DEFAULT("cc.debug.picture") ","
@@ -321,20 +235,13 @@ void DisplayItemList::EmitTraceSnapshot() const {
 }
 
 void DisplayItemList::GenerateDiscardableImagesMetadata() {
-  DCHECK(ProcessAppendedItemsCalled());
-  // This should be only called once, and only after CreateAndCacheSkPicture.
+  DCHECK(FinalizeCalled());
   DCHECK(image_map_.empty());
-  DCHECK(!settings_.use_cached_picture || picture_);
-  if (settings_.use_cached_picture && !picture_->willPlayBackBitmaps())
-    return;
 
-  // The cached picture is translated by -layer_rect_.origin during record,
-  // so we need to offset that back in order to get right positioning for
-  // images.
+  gfx::Rect bounds = rtree_.GetBounds();
   DiscardableImageMap::ScopedMetadataGenerator generator(
-      &image_map_, gfx::Size(layer_rect_.right(), layer_rect_.bottom()));
-  Raster(generator.canvas(), nullptr,
-         gfx::Rect(layer_rect_.right(), layer_rect_.bottom()), 1.f);
+      &image_map_, gfx::Size(bounds.right(), bounds.bottom()));
+  Raster(generator.canvas(), nullptr, gfx::Rect(), 1.f);
 }
 
 void DisplayItemList::GetDiscardableImagesInRect(