cc: Added tile bundles

cc/resources/picture_layer_tiling.cc

 // Copyright 2012 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 "cc/resources/picture_layer_tiling.h"
 
 #include <algorithm>
 #include <cmath>
 #include <limits>
 
 #include "base/debug/trace_event.h"
 #include "cc/base/math_util.h"
 #include "ui/gfx/point_conversions.h"
 #include "ui/gfx/rect_conversions.h"
 #include "ui/gfx/safe_integer_conversions.h"
 #include "ui/gfx/size_conversions.h"
 
 namespace cc {
 
+namespace {
+
+const int kTileBundleWidth = 2;
+const int kTileBundleHeight = 2;
+
+std::pair<int, int> ComputeTileBundleIndex(int i, int j) {
+  return std::make_pair(i / kTileBundleWidth, j / kTileBundleHeight);
+}
+
+}
+
 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
     float contents_scale,
     gfx::Size layer_bounds,
     PictureLayerTilingClient* client) {
   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
                                                 layer_bounds,
                                                 client));
 }
 
 PictureLayerTiling::PictureLayerTiling(float contents_scale,
                                        gfx::Size layer_bounds,
                                        PictureLayerTilingClient* client)
     : contents_scale_(contents_scale),
       layer_bounds_(layer_bounds),
       resolution_(NON_IDEAL_RESOLUTION),
       client_(client),
       tiling_data_(gfx::Size(), gfx::Size(), true),
+      bundle_tiling_data_(gfx::Size(), gfx::Size(), true),
       last_impl_frame_time_in_seconds_(0.0) {
   gfx::Size content_bounds =
       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
 
   DCHECK(!gfx::ToFlooredSize(
       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
       "Tiling created with scale too small as contents become empty." <<
       " Layer bounds: " << layer_bounds.ToString() <<
       " Contents scale: " << contents_scale;
 
   tiling_data_.SetTotalSize(content_bounds);
   tiling_data_.SetMaxTextureSize(tile_size);
+  bundle_tiling_data_.SetTotalSize(content_bounds);
+  bundle_tiling_data_.SetMaxTextureSize(
+      gfx::Size(tile_size.width() * kTileBundleWidth,
+                tile_size.height() * kTileBundleHeight));
 }
 
 PictureLayerTiling::~PictureLayerTiling() {
 }
 
 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
   client_ = client;
 }
 
 gfx::Rect PictureLayerTiling::ContentRect() const {
   return gfx::Rect(tiling_data_.total_size());
 }
 
 gfx::SizeF PictureLayerTiling::ContentSizeF() const {
   return gfx::ScaleSize(layer_bounds_, contents_scale_);
 }
 
-Tile* PictureLayerTiling::TileAt(int i, int j) const {
-  TileMap::const_iterator iter = tiles_.find(TileMapKey(i, j));
-  if (iter == tiles_.end())
-    return NULL;
-  return iter->second.get();
+TileBundle* PictureLayerTiling::CreateBundleForTileAt(
+    int i,
+    int j,
+    const PictureLayerTiling* twin_tiling) {
+  TileBundleMapKey key = ComputeTileBundleIndex(i, j);
+  DCHECK(tile_bundles_.find(key) == tile_bundles_.end());
+
+  scoped_refptr<TileBundle> candidate_bundle = NULL;
+
+  // Always try to get the twin bundle first. TileBundles are always shared
+  // between trees.
+  if (twin_tiling &&
+      tiling_data_.max_texture_size() ==
+      twin_tiling->tiling_data_.max_texture_size()) {
+    candidate_bundle = twin_tiling->TileBundleAt(key.first, key.second);
+  }
+
+  // If we couldn't get a tile bundle, create a new one.
+  if (!candidate_bundle) {
+    candidate_bundle =
+        client_->CreateTileBundle(kTileBundleWidth,
+                                  kTileBundleHeight,
+                                  key.first * kTileBundleWidth,
+                                  key.second * kTileBundleHeight);
+  }
+  tile_bundles_[key] = candidate_bundle;
+  return candidate_bundle.get();
 }
 
-void PictureLayerTiling::CreateTile(int i,
+TileBundle* PictureLayerTiling::TileBundleContainingTileAt(int i, int j) const {
+  TileBundleMapKey key = ComputeTileBundleIndex(i, j);
+  return TileBundleAt(key.first, key.second);
+}
+
+TileBundle* PictureLayerTiling::TileBundleAt(int i, int j) const {
+  TileBundleMapKey key(i, j);
+  TileBundleMap::const_iterator it = tile_bundles_.find(key);
+  if (it == tile_bundles_.end())
+    return NULL;
+  return it->second.get();
+}
+
+Tile* PictureLayerTiling::TileAt(WhichTree tree, int i, int j) const {
+  TileBundle* bundle = TileBundleContainingTileAt(i, j);
+  if (!bundle)
+    return NULL;
+  return bundle->TileAt(tree, i, j);
+}
+
+void PictureLayerTiling::CreateTile(WhichTree tree,
+                                    int i,
                                     int j,
                                     const PictureLayerTiling* twin_tiling) {
-  TileMapKey key(i, j);
-  DCHECK(tiles_.find(key) == tiles_.end());
+  TileBundle* bundle = TileBundleContainingTileAt(i, j);
+  if (!bundle)
+    bundle = CreateBundleForTileAt(i, j, twin_tiling);
 
   gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
   gfx::Rect tile_rect = paint_rect;
   tile_rect.set_size(tiling_data_.max_texture_size());
 
   // Check our twin for a valid tile.
-  if (twin_tiling &&
-      tiling_data_.max_texture_size() ==
-      twin_tiling->tiling_data_.max_texture_size()) {
-    if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
-      gfx::Rect rect =
-          gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
-      if (!client_->GetInvalidation()->Intersects(rect)) {
-        tiles_[key] = candidate_tile;
-        return;
-      }
+  WhichTree twin_tree = (tree == ACTIVE_TREE) ? PENDING_TREE : ACTIVE_TREE;
+  if (Tile* candidate_tile = bundle->TileAt(twin_tree, i, j)) {
+    gfx::Rect rect =
+        gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
+    if (!client_->GetInvalidation()->Intersects(rect)) {
+      bundle->AddTileAt(tree, i, j, candidate_tile);
+      return;
     }
   }
 
   // Create a new tile because our twin didn't have a valid one.
   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
   if (tile.get())
-    tiles_[key] = tile;
+    bundle->AddTileAt(tree, i, j, tile);
+}
+
+bool PictureLayerTiling::RemoveTile(WhichTree tree, int i, int j) {
+  TileBundleMapKey key = ComputeTileBundleIndex(i, j);
+  TileBundleMap::iterator it = tile_bundles_.find(key);
+  if (it == tile_bundles_.end())
+    return false;
+
+  return it->second->RemoveTileAt(tree, i, j);
+}
+
+void PictureLayerTiling::RemoveBundleIfEmptyContainingTileAt(int i, int j) {
+  TileBundleMapKey key = ComputeTileBundleIndex(i, j);
+  TileBundleMap::iterator it = tile_bundles_.find(key);
+  if (it == tile_bundles_.end())
+    return;
+
+  if (it->second->IsEmpty())
+    tile_bundles_.erase(it);
 }
 
 Region PictureLayerTiling::OpaqueRegionInContentRect(
     gfx::Rect content_rect) const {
   Region opaque_region;
   // TODO(enne): implement me
   return opaque_region;
 }
 
 void PictureLayerTiling::SetCanUseLCDText(bool can_use_lcd_text) {
-  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it)
-    it->second->set_can_use_lcd_text(can_use_lcd_text);
+  // TODO(vmpstr): This can be done per bundle with results used
+  // in tile manager.
+  for (TileBundleMap::iterator it = tile_bundles_.begin();
+       it != tile_bundles_.end();
+       ++it) {
+    for (TileBundle::Iterator tile_it(it->second); tile_it; ++tile_it)
+      tile_it->set_can_use_lcd_text(can_use_lcd_text);
+  }
 }
 
 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
+  DCHECK(client_->IsPending());
+
   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
   for (TilingData::Iterator iter(&tiling_data_, live_tiles_rect_); iter;
        ++iter) {
-    TileMapKey key = iter.index();
-    TileMap::iterator find = tiles_.find(key);
-    if (find != tiles_.end())
+    int tile_x = iter.index_x();
+    int tile_y = iter.index_y();
+    Tile* tile = TileAt(PENDING_TREE, tile_x, tile_y);
+    if (tile)
       continue;
-    CreateTile(key.first, key.second, twin_tiling);
+    CreateTile(PENDING_TREE, tile_x, tile_y, twin_tiling);
   }
 }
 
 void PictureLayerTiling::SetLayerBounds(gfx::Size layer_bounds) {
   if (layer_bounds_ == layer_bounds)
     return;
 
+  DCHECK(client_->IsPending());
   DCHECK(!layer_bounds.IsEmpty());
 
   gfx::Size old_layer_bounds = layer_bounds_;
   layer_bounds_ = layer_bounds;
   gfx::Size old_content_bounds = tiling_data_.total_size();
   gfx::Size content_bounds =
       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
 
   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
   if (tile_size != tiling_data_.max_texture_size()) {
     tiling_data_.SetTotalSize(content_bounds);
     tiling_data_.SetMaxTextureSize(tile_size);
+    bundle_tiling_data_.SetTotalSize(content_bounds);
+    bundle_tiling_data_.SetMaxTextureSize(
+        gfx::Size(tile_size.width() * kTileBundleWidth,
+                  tile_size.height() * kTileBundleHeight));
     Reset();
     return;
   }
 
   // Any tiles outside our new bounds are invalid and should be dropped.
   gfx::Rect bounded_live_tiles_rect(live_tiles_rect_);
   bounded_live_tiles_rect.Intersect(gfx::Rect(content_bounds));
-  SetLiveTilesRect(bounded_live_tiles_rect);
+  SetLiveTilesRect(PENDING_TREE, bounded_live_tiles_rect);
   tiling_data_.SetTotalSize(content_bounds);
+  bundle_tiling_data_.SetTotalSize(content_bounds);
 
   // Create tiles for newly exposed areas.
   Region layer_region((gfx::Rect(layer_bounds_)));
   layer_region.Subtract(gfx::Rect(old_layer_bounds));
   Invalidate(layer_region);
 }
 
 void PictureLayerTiling::Invalidate(const Region& layer_region) {
-  std::vector<TileMapKey> new_tile_keys;
+  DCHECK(client_->IsPending());
+
+  std::vector<std::pair<int, int> > new_tile_keys;
   for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
     gfx::Rect layer_rect = iter.rect();
     gfx::Rect content_rect =
         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
     content_rect.Intersect(live_tiles_rect_);
     if (content_rect.IsEmpty())
       continue;
     for (TilingData::Iterator iter(&tiling_data_, content_rect); iter; ++iter) {
-      TileMapKey key(iter.index());
-      TileMap::iterator find = tiles_.find(key);
-      if (find == tiles_.end())
-        continue;
-      tiles_.erase(find);
-      new_tile_keys.push_back(key);
+      int tile_x = iter.index_x();
+      int tile_y = iter.index_y();
+
+      // If there is no bundle for the given tile, we can skip.
+      bool deleted = RemoveTile(PENDING_TREE, tile_x, tile_y);
+      if (deleted)
+        new_tile_keys.push_back(std::make_pair(tile_x, tile_y));
     }
   }
 
   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
-  for (size_t i = 0; i < new_tile_keys.size(); ++i)
-    CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
+  for (size_t i = 0; i < new_tile_keys.size(); ++i) {
+    CreateTile(PENDING_TREE,
+               new_tile_keys[i].first,
+               new_tile_keys[i].second,
+               twin_tiling);
+  }
 }
 
 PictureLayerTiling::CoverageIterator::CoverageIterator()
     : tiling_(NULL),
       current_tile_(NULL),
       tile_i_(0),
       tile_j_(0),
       left_(0),
       top_(0),
       right_(-1),
       bottom_(-1) {
 }
 
 PictureLayerTiling::CoverageIterator::CoverageIterator(
     const PictureLayerTiling* tiling,
     float dest_scale,
     gfx::Rect dest_rect)
     : tiling_(tiling),
       dest_rect_(dest_rect),
       dest_to_content_scale_(0),
       current_tile_(NULL),
       tile_i_(0),
       tile_j_(0),
       left_(0),
       top_(0),
       right_(-1),
-      bottom_(-1) {
+      bottom_(-1),
+      tree_(tiling->client_->IsActive() ? ACTIVE_TREE : PENDING_TREE) {
   DCHECK(tiling_);
   if (dest_rect_.IsEmpty())
     return;
 
   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
   // This is the maximum size that the dest rect can be, given the content size.
   gfx::Size dest_content_size = gfx::ToCeiledSize(gfx::ScaleSize(
       tiling_->ContentRect().size(),
       1 / dest_to_content_scale_,
       1 / dest_to_content_scale_));
@@ skipping 34 matching lines @@
   if (tile_i_ > right_) {
     tile_i_ = left_;
     tile_j_++;
     new_row = true;
     if (tile_j_ > bottom_) {
       current_tile_ = NULL;
       return *this;
     }
   }
 
-  current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
+  current_tile_ = tiling_->TileAt(tree_, tile_i_, tile_j_);
 
   // Calculate the current geometry rect.  Due to floating point rounding
   // and ToEnclosingRect, tiles might overlap in destination space on the
   // edges.
   gfx::Rect last_geometry_rect = current_geometry_rect_;
 
   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 
   current_geometry_rect_ =
       gfx::ScaleToEnclosingRect(content_rect,
@@ skipping 35 matching lines @@
   return current_geometry_rect_;
 }
 
 gfx::Rect
 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
   gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
   rect.set_size(tiling_->tiling_data_.max_texture_size());
   return rect;
 }
 
+TilePriority PictureLayerTiling::CoverageIterator::priority() {
+  TileBundle* bundle = tiling_->TileBundleContainingTileAt(tile_i_, tile_j_);
+  if (bundle)
+    return bundle->GetPriority(tree_);
+  return TilePriority();
+}
+
+void PictureLayerTiling::CoverageIterator::SetPriorityForTesting(
+    const TilePriority& priority) {
+  TileBundle* bundle = tiling_->TileBundleContainingTileAt(tile_i_, tile_j_);
+  bundle->SetPriority(tree_, priority);
+}
+
 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
   gfx::PointF tex_origin =
       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 
   // Convert from dest space => content space => texture space.
   gfx::RectF texture_rect(current_geometry_rect_);
   texture_rect.Scale(dest_to_content_scale_,
                      dest_to_content_scale_);
   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
   texture_rect.Intersect(tiling_->ContentRect());
 
   return texture_rect;
 }
 
 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
   return tiling_->tiling_data_.max_texture_size();
 }
 
 void PictureLayerTiling::Reset() {
   live_tiles_rect_ = gfx::Rect();
-  tiles_.clear();
+  tile_bundles_.clear();
 }
 
 void PictureLayerTiling::UpdateTilePriorities(
     WhichTree tree,
     gfx::Size device_viewport,
     gfx::Rect viewport_in_layer_space,
     gfx::Rect visible_layer_rect,
     gfx::Size last_layer_bounds,
     gfx::Size current_layer_bounds,
     float last_layer_contents_scale,
@@ skipping 25 matching lines @@
                             ? viewport_in_content_space
                             : visible_content_rect;
   gfx::Rect interest_rect = ExpandRectEquallyToAreaBoundedBy(
       starting_rect,
       interest_rect_area,
       ContentRect(),
       &expansion_cache_);
   DCHECK(interest_rect.IsEmpty() ||
          ContentRect().Contains(interest_rect));
 
-  SetLiveTilesRect(interest_rect);
+  SetLiveTilesRect(tree, interest_rect);
 
   double time_delta = 0;
   if (last_impl_frame_time_in_seconds_ != 0.0 &&
       last_layer_bounds == current_layer_bounds) {
     time_delta =
         current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
   }
 
   gfx::Rect view_rect(device_viewport);
   float current_scale = current_layer_contents_scale / contents_scale_;
   float last_scale = last_layer_contents_scale / contents_scale_;
 
   // Fast path tile priority calculation when both transforms are translations.
   if (last_screen_transform.IsApproximatelyIdentityOrTranslation(
           std::numeric_limits<float>::epsilon()) &&
       current_screen_transform.IsApproximatelyIdentityOrTranslation(
           std::numeric_limits<float>::epsilon())) {
     gfx::Vector2dF current_offset(
         current_screen_transform.matrix().get(0, 3),
         current_screen_transform.matrix().get(1, 3));
     gfx::Vector2dF last_offset(
         last_screen_transform.matrix().get(0, 3),
         last_screen_transform.matrix().get(1, 3));
 
-    for (TilingData::Iterator iter(&tiling_data_, interest_rect);
+    for (TilingData::Iterator iter(&bundle_tiling_data_, interest_rect);
          iter; ++iter) {
-      TileMap::iterator find = tiles_.find(iter.index());
-      if (find == tiles_.end())
+      int bundle_x = iter.index_x();
+      int bundle_y = iter.index_y();
+      TileBundle* bundle = TileBundleAt(bundle_x, bundle_y);
+      if (!bundle)
         continue;
-      Tile* tile = find->second.get();
 
-      gfx::Rect tile_bounds =
-          tiling_data_.TileBounds(iter.index_x(), iter.index_y());
-      gfx::RectF current_screen_rect = gfx::ScaleRect(
-          tile_bounds,
-          current_scale,
-          current_scale) + current_offset;
-      gfx::RectF last_screen_rect = gfx::ScaleRect(
-          tile_bounds,
-          last_scale,
-          last_scale) + last_offset;
+      gfx::Rect bundle_bounds =
+          bundle_tiling_data_.TileBounds(bundle_x, bundle_y);
+      gfx::RectF current_screen_rect =
+          gfx::ScaleRect(bundle_bounds, current_scale, current_scale) +
+          current_offset;
+      gfx::RectF last_screen_rect =
+          gfx::ScaleRect(bundle_bounds, last_scale, last_scale) +
+          last_offset;
 
       float distance_to_visible_in_pixels =
           TilePriority::manhattanDistance(current_screen_rect, view_rect);
 
       float time_to_visible_in_seconds =
           TilePriority::TimeForBoundsToIntersect(
               last_screen_rect, current_screen_rect, time_delta, view_rect);
       TilePriority priority(
           resolution_,
           time_to_visible_in_seconds,
           distance_to_visible_in_pixels);
-      tile->SetPriority(tree, priority);
+
+      bundle->SetPriority(tree, priority);
     }
   } else if (!last_screen_transform.HasPerspective() &&
              !current_screen_transform.HasPerspective()) {
     // Secondary fast path that can be applied for any affine transforms.
 
     // Initialize the necessary geometry in screen space, so that we can
     // iterate over tiles in screen space without needing a costly transform
     // mapping for each tile.
 
     // Apply screen space transform to the local origin point (0, 0); only the
     // translation component is needed and can be initialized directly.
     gfx::Point current_screen_space_origin(
         current_screen_transform.matrix().get(0, 3),
         current_screen_transform.matrix().get(1, 3));
 
     gfx::Point last_screen_space_origin(
         last_screen_transform.matrix().get(0, 3),
         last_screen_transform.matrix().get(1, 3));
 
-    float current_tile_width = tiling_data_.TileSizeX(0) * current_scale;
-    float last_tile_width = tiling_data_.TileSizeX(0) * last_scale;
-    float current_tile_height = tiling_data_.TileSizeY(0) * current_scale;
-    float last_tile_height = tiling_data_.TileSizeY(0) * last_scale;
+    float current_bundle_width =
+        bundle_tiling_data_.TileSizeX(0) * current_scale;
+    float last_bundle_width =
+        bundle_tiling_data_.TileSizeX(0) * last_scale;
+    float current_bundle_height =
+        bundle_tiling_data_.TileSizeY(0) * current_scale;
+    float last_bundle_height =
+        bundle_tiling_data_.TileSizeY(0) * last_scale;
 
     // Apply screen space transform to local basis vectors (tile_width, 0) and
     // (0, tile_height); the math simplifies and can be initialized directly.
     gfx::Vector2dF current_horizontal(
-        current_screen_transform.matrix().get(0, 0) * current_tile_width,
-        current_screen_transform.matrix().get(1, 0) * current_tile_width);
+        current_screen_transform.matrix().get(0, 0) * current_bundle_width,
+        current_screen_transform.matrix().get(1, 0) * current_bundle_width);
     gfx::Vector2dF current_vertical(
-        current_screen_transform.matrix().get(0, 1) * current_tile_height,
-        current_screen_transform.matrix().get(1, 1) * current_tile_height);
+        current_screen_transform.matrix().get(0, 1) * current_bundle_height,
+        current_screen_transform.matrix().get(1, 1) * current_bundle_height);
 
     gfx::Vector2dF last_horizontal(
-        last_screen_transform.matrix().get(0, 0) * last_tile_width,
-        last_screen_transform.matrix().get(1, 0) * last_tile_width);
+        last_screen_transform.matrix().get(0, 0) * last_bundle_width,
+        last_screen_transform.matrix().get(1, 0) * last_bundle_width);
     gfx::Vector2dF last_vertical(
-        last_screen_transform.matrix().get(0, 1) * last_tile_height,
-        last_screen_transform.matrix().get(1, 1) * last_tile_height);
+        last_screen_transform.matrix().get(0, 1) * last_bundle_height,
+        last_screen_transform.matrix().get(1, 1) * last_bundle_height);
 
-    for (TilingData::Iterator iter(&tiling_data_, interest_rect);
+    for (TilingData::Iterator iter(&bundle_tiling_data_, interest_rect);
          iter; ++iter) {
-      TileMap::iterator find = tiles_.find(iter.index());
-      if (find == tiles_.end())
+      int bundle_x = iter.index_x();
+      int bundle_y = iter.index_y();
+      TileBundle* bundle = TileBundleAt(bundle_x, bundle_y);
+      if (!bundle)
         continue;
 
-      Tile* tile = find->second.get();
-
-      int i = iter.index_x();
-      int j = iter.index_y();
-      gfx::PointF current_tile_origin = current_screen_space_origin +
-              ScaleVector2d(current_horizontal, i) +
-              ScaleVector2d(current_vertical, j);
-      gfx::PointF last_tile_origin = last_screen_space_origin +
-              ScaleVector2d(last_horizontal, i) +
-              ScaleVector2d(last_vertical, j);
+      gfx::PointF current_bundle_origin = current_screen_space_origin +
+              ScaleVector2d(current_horizontal, bundle_x) +
+              ScaleVector2d(current_vertical, bundle_y);
+      gfx::PointF last_bundle_origin = last_screen_space_origin +
+              ScaleVector2d(last_horizontal, bundle_x) +
+              ScaleVector2d(last_vertical, bundle_y);
 
       gfx::RectF current_screen_rect = gfx::QuadF(
-          current_tile_origin,
-          current_tile_origin + current_horizontal,
-          current_tile_origin + current_horizontal + current_vertical,
-          current_tile_origin + current_vertical).BoundingBox();
+          current_bundle_origin,
+          current_bundle_origin + current_horizontal,
+          current_bundle_origin + current_horizontal + current_vertical,
+          current_bundle_origin + current_vertical).BoundingBox();
 
       gfx::RectF last_screen_rect = gfx::QuadF(
-          last_tile_origin,
-          last_tile_origin + last_horizontal,
-          last_tile_origin + last_horizontal + last_vertical,
-          last_tile_origin + last_vertical).BoundingBox();
+          last_bundle_origin,
+          last_bundle_origin + last_horizontal,
+          last_bundle_origin + last_horizontal + last_vertical,
+          last_bundle_origin + last_vertical).BoundingBox();
 
       float distance_to_visible_in_pixels =
           TilePriority::manhattanDistance(current_screen_rect, view_rect);
 
       float time_to_visible_in_seconds =
           TilePriority::TimeForBoundsToIntersect(
               last_screen_rect, current_screen_rect, time_delta, view_rect);
       TilePriority priority(
           resolution_,
           time_to_visible_in_seconds,
           distance_to_visible_in_pixels);
-      tile->SetPriority(tree, priority);
+
+      bundle->SetPriority(tree, priority);
     }
   } else {
-    for (TilingData::Iterator iter(&tiling_data_, interest_rect);
+    for (TilingData::Iterator iter(&bundle_tiling_data_, interest_rect);
          iter; ++iter) {
-      TileMap::iterator find = tiles_.find(iter.index());
-      if (find == tiles_.end())
+      int bundle_x = iter.index_x();
+      int bundle_y = iter.index_y();
+      TileBundle* bundle = TileBundleAt(bundle_x, bundle_y);
+      if (!bundle)
         continue;
-      Tile* tile = find->second.get();
 
-      gfx::Rect tile_bounds =
-          tiling_data_.TileBounds(iter.index_x(), iter.index_y());
+      gfx::Rect bundle_bounds =
+          bundle_tiling_data_.TileBounds(bundle_x, bundle_y);
       gfx::RectF current_layer_content_rect = gfx::ScaleRect(
-          tile_bounds,
+          bundle_bounds,
           current_scale,
           current_scale);
       gfx::RectF current_screen_rect = MathUtil::MapClippedRect(
           current_screen_transform, current_layer_content_rect);
       gfx::RectF last_layer_content_rect = gfx::ScaleRect(
-          tile_bounds,
+          bundle_bounds,
           last_scale,
           last_scale);
       gfx::RectF last_screen_rect  = MathUtil::MapClippedRect(
           last_screen_transform, last_layer_content_rect);
 
       float distance_to_visible_in_pixels =
           TilePriority::manhattanDistance(current_screen_rect, view_rect);
 
       float time_to_visible_in_seconds =
           TilePriority::TimeForBoundsToIntersect(
               last_screen_rect, current_screen_rect, time_delta, view_rect);
 
       TilePriority priority(
           resolution_,
           time_to_visible_in_seconds,
           distance_to_visible_in_pixels);
-      tile->SetPriority(tree, priority);
+
+      bundle->SetPriority(tree, priority);
     }
   }
 
   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 }
 
 void PictureLayerTiling::SetLiveTilesRect(
-    gfx::Rect new_live_tiles_rect) {
+    WhichTree tree, gfx::Rect new_live_tiles_rect) {
   DCHECK(new_live_tiles_rect.IsEmpty() ||
          ContentRect().Contains(new_live_tiles_rect));
   if (live_tiles_rect_ == new_live_tiles_rect)
     return;
 
   // Iterate to delete all tiles outside of our new live_tiles rect.
   for (TilingData::DifferenceIterator iter(&tiling_data_,
                                            live_tiles_rect_,
                                            new_live_tiles_rect);
        iter;
        ++iter) {
-    TileMapKey key(iter.index());
-    TileMap::iterator found = tiles_.find(key);
+    int tile_x = iter.index_x();
+    int tile_y = iter.index_y();
+
     // If the tile was outside of the recorded region, it won't exist even
     // though it was in the live rect.
-    if (found != tiles_.end())
-      tiles_.erase(found);
+    RemoveTile(tree, tile_x, tile_y);
+    RemoveBundleIfEmptyContainingTileAt(tile_x, tile_y);
   }
 
   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 
   // Iterate to allocate new tiles for all regions with newly exposed area.
   for (TilingData::DifferenceIterator iter(&tiling_data_,
                                            new_live_tiles_rect,
                                            live_tiles_rect_);
        iter;
        ++iter) {
-    TileMapKey key(iter.index());
-    CreateTile(key.first, key.second, twin_tiling);
+    // TODO(vmpstr): Since the old active tree became the recycled tree,

[enne (OOO), 2013/11/25 22:17:11]

For what it's worth, the old pending tree becomes the recycled tree after it
pushes from pending -> active.

Can you help me understand what the problem is more here? I feel like the
invalidation region and creating new tiles already handles this, or that there
isn't a fundamental difference between tiles and bundles wrt
recycle/active/pending tree sharing.

[vmpstr, 2013/11/27 00:03:15]

I've changed this... This wasn't the correct fix for the problem I was seeing.

The problem is the following:

We can call UpdateTilePriorities on the active tree, which can create a new tile
bundle (that is not on the twin) that is now in the new live tiles rect. This
populates the tiles in the tile bundle active_tree bucket.

The active tiling then later on becomes the pending tiling and the pending one
becomes the active.

However, the only way we swap active and pending tiles in a bundle is via did
become active (which is called, obviously, on the pending tree). The result is
that this newly created bundle is inaccessible via the pending tree and the
tiles are never swapped.

Now in the new active tiling (old pending tiling, if this still makes any
sense), we call UpdateTilePriorities again and this time we get the twin tiling
bundle that we created earlier. However, because swap was never called on this
tiling, we now have a tiling that already has active_tree bucket tiles filled
in, and so we dcheck in TileBundle::AddTileAt.


I considered always populating the tiling on both trees (ie, when we create a
new one on this, add it to the twin immediately), but that doesn't work in all
situations since we might not have a twin yet (ie, it's currently recycled). So
the fix I came up with is to keep track on the bundle whether the tiles need to
be swapped and then doing a lightweight check to see if tiles need swapping
every time we grab a bundle. I don't necessarily think it's the best solution,
but I think it works properly. If we add a "did become pending" callback, then
we can do this swap check during that callback.

The order of the callbacks will then be important then:
- DidBecomeRecycled first called on the current active tree (this sets the needs
swapping state)
- DidBecomeActive must be called next on the current pending tree (this swaps
everything that it can visit and resets the needs swapping state)
- DidBecomePending is then called some time later when we create a new pending
tree (this would only swap whatever needs swapping as indicated by the state).

[enne (OOO), 2013/11/27 01:38:05]

Re: DidBecomeRecycled/Active/Pending with swapping state, that sgtm as a
short/medium-term solution.  I do agree with what you said offline that the
longer solution here is to just sharing tilings.  This essentially lets you do
everything in one pass and doesn't have this "no twin when recycled problem".

Even if this is a short term solution, could you at least add one unit test that
runs through a scenario where you have some shared and some unshared tiles
during this activation? Maybe in picture_layer_impl_unittest with different live
tiles rects?

[vmpstr, 2013/11/27 21:09:36]

Of course. I plan to add more than one. :) I just want to get the review in more
or less the shape that it will take, so that I don't spend too much time
changing newly written tests. I hope that's OK.

+    // and since the recycle tiles are recorded in bundle's pending list,
+    // we might run into a situation where we already have a tile in that
+    // region. We should remove it first. We can't use RemoveTile here,
+    // since the bundle might not yet be on this tiling. That is, the
+    // act of adding a tile will grab a bundle from the twin tiling that
+    // has this bad property of already having a tile in that spot.
+    // The todo here is to come up with a better way of recycling.
+    // Maybe having a separate list for that.
+    TileBundleMapKey key =
+        ComputeTileBundleIndex(iter.index_x(), iter.index_y());
+    TileBundleMap::iterator bundle_it = tile_bundles_.find(key);
+    TileBundle* bundle = NULL;
+    if (bundle_it != tile_bundles_.end()) {
+      bundle = bundle_it->second;
+    } else {
+      bundle =
+          CreateBundleForTileAt(iter.index_x(), iter.index_y(), twin_tiling);
+    }
+
+    bundle->RemoveTileAt(tree, iter.index_x(), iter.index_y());
+    CreateTile(tree, iter.index_x(), iter.index_y(), twin_tiling);
   }
 
   live_tiles_rect_ = new_live_tiles_rect;
 }
 
 void PictureLayerTiling::DidBecomeRecycled() {
   // DidBecomeActive below will set the active priority for tiles that are
   // still in the tree. Calling this first on an active tiling that is becoming
   // recycled takes care of tiles that are no longer in the active tree (eg.
   // due to a pending invalidation).
-  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    it->second->SetPriority(ACTIVE_TREE, TilePriority());
+  for (TileBundleMap::const_iterator it = tile_bundles_.begin();
+       it != tile_bundles_.end();
+       ++it) {
+    it->second->DidBecomeRecycled();
   }
 }
 
 void PictureLayerTiling::DidBecomeActive() {
-  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
-    it->second->SetPriority(PENDING_TREE, TilePriority());
-
-    // Tile holds a ref onto a picture pile. If the tile never gets invalidated
-    // and recreated, then that picture pile ref could exist indefinitely.  To
-    // prevent this, ask the client to update the pile to its own ref.  This
-    // will cause PicturePileImpls and their clones to get deleted once the
-    // corresponding PictureLayerImpl and any in flight raster jobs go out of
-    // scope.
-    client_->UpdatePile(it->second.get());
+  for (TileBundleMap::const_iterator it = tile_bundles_.begin();
+       it != tile_bundles_.end();
+       ++it) {
+    it->second->DidBecomeActive();
+    for (TileBundle::Iterator tile_it(it->second.get()); tile_it; ++tile_it) {
+      // Tile holds a ref onto a picture pile. If the tile never gets
+      // invalidated and recreated, then that picture pile ref could exist
+      // indefinitely.  To prevent this, ask the client to update the pile to
+      // its own ref.  This will cause PicturePileImpls and their clones to get
+      // deleted once the corresponding PictureLayerImpl and any in flight
+      // raster jobs go out of scope.
+      if (tile_it.active_tree_only_tile() &&
+          tile_it.active_priority() != TilePriority())
+        client_->UpdatePile(*tile_it);

[enne (OOO), 2013/11/25 22:17:11]

Previously DidBecomeActive and UpdateTileToCurrentPile touched both shared and
unshared tiles.  This work was really only needed for the shared tiles, since
unshared tiles already had the right pile.  If tiles are shared, there is no
invalidation, and therefore the new pile is also correct.

I am not sure these checks are needed, and all tiles should be updated to the
new pile both here and below.

[vmpstr, 2013/11/27 00:03:15]

I changed this to be only updated for shared tiles. The reason I need the check
is that the iterator gets the tiles from both active and pending tilings (which
is a departure from the way it was done before) and we can run into a situation
where the current client's pile can't raster into a tile that is only on the
twin tiling (due to different recording region; ie the tile bundle may exist on
both trees, but the bottom row of tiles in the bundle might only be covered by a
recording from only one of the trees)

[enne (OOO), 2013/11/27 01:38:05]

Hmm.  In the case that the pile can't raster onto those tiles, then that tile
will not exist.  Maybe the iterator just needs a tree parameter so that you
don't iterate over unshared, pending-only tiles?

[vmpstr, 2013/11/27 21:09:36]

Done.

+    }
   }
 }
 
 void PictureLayerTiling::UpdateTilesToCurrentPile() {
-  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    client_->UpdatePile(it->second.get());
+  for (TileBundleMap::const_iterator it = tile_bundles_.begin();
+       it != tile_bundles_.end();
+       ++it) {
+    for (TileBundle::Iterator tile_it(it->second.get()); tile_it; ++tile_it) {
+      if (tile_it.pending_tree_only_tile() &&
+          tile_it.pending_priority() != TilePriority())
+        client_->UpdatePile(*tile_it);
+    }
   }
 }
 
 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
-  state->SetInteger("num_tiles", tiles_.size());
+  state->SetInteger("num_tile_bundles", tile_bundles_.size());
   state->SetDouble("content_scale", contents_scale_);
   state->Set("content_bounds",
              MathUtil::AsValue(ContentRect().size()).release());
   return state.PassAs<base::Value>();
 }
 
 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
   size_t amount = 0;
-  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
-    const Tile* tile = it->second.get();
-    amount += tile->GPUMemoryUsageInBytes();
+  for (TileBundleMap::const_iterator it = tile_bundles_.begin();
+       it != tile_bundles_.end();
+       ++it) {
+    for (TileBundle::Iterator tile_it(it->second.get()); tile_it; ++tile_it)
+      amount += tile_it->GPUMemoryUsageInBytes();
   }
   return amount;
 }
 
 PictureLayerTiling::RectExpansionCache::RectExpansionCache()
   : previous_target(0) {
 }
 
 namespace {
 
@@ skipping 134 matching lines @@
       break;
   }
 
   gfx::Rect result(origin_x, origin_y, width, height);
   if (cache)
     cache->previous_result = result;
   return result;
 }
 
 }  // namespace cc