cc/resources/picture_layer_tiling.cc

   1 // Copyright 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "cc/resources/picture_layer_tiling.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9 #include <limits>
  10
  11 #include "base/debug/trace_event.h"
  12 #include "base/debug/trace_event_argument.h"
  13 #include "cc/base/math_util.h"
  14 #include "cc/resources/tile.h"
  15 #include "cc/resources/tile_priority.h"
  16 #include "cc/trees/occlusion_tracker.h"
  17 #include "ui/gfx/point_conversions.h"
  18 #include "ui/gfx/rect_conversions.h"
  19 #include "ui/gfx/safe_integer_conversions.h"
  20 #include "ui/gfx/size_conversions.h"
  21
  22 namespace cc {
  23 namespace {
  24
  25 const float kSoonBorderDistanceInScreenPixels = 312.f;
  26
  27 class TileEvictionOrder {
  28  public:
  29   explicit TileEvictionOrder(TreePriority tree_priority)
  30       : tree_priority_(tree_priority) {}
  31   ~TileEvictionOrder() {}
  32
  33   bool operator()(const Tile* a, const Tile* b) {
  34     const TilePriority& a_priority =
  35         a->priority_for_tree_priority(tree_priority_);
  36     const TilePriority& b_priority =
  37         b->priority_for_tree_priority(tree_priority_);
  38
  39     DCHECK(a_priority.priority_bin == b_priority.priority_bin);
  40     DCHECK(a->required_for_activation() == b->required_for_activation());
  41
  42     // Or if a is occluded and b is unoccluded.
  43     bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
  44     bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
  45     if (a_is_occluded != b_is_occluded)
  46       return a_is_occluded;
  47
  48     // Or if a is farther away from visible.
  49     return a_priority.distance_to_visible > b_priority.distance_to_visible;
  50   }
  51
  52  private:
  53   TreePriority tree_priority_;
  54 };
  55
  56 void ReleaseTile(Tile* tile, WhichTree tree) {
  57   // Reset priority as tile is ref-counted and might still be used
  58   // even though we no longer hold a reference to it here anymore.
  59   tile->SetPriority(tree, TilePriority());
  60   tile->set_shared(false);
  61 }
  62
  63 }  // namespace
  64
  65 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
  66     float contents_scale,
  67     const gfx::Size& layer_bounds,
  68     PictureLayerTilingClient* client) {
  69   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
  70                                                 layer_bounds,
  71                                                 client));
  72 }
  73
  74 PictureLayerTiling::PictureLayerTiling(float contents_scale,
  75                                        const gfx::Size& layer_bounds,
  76                                        PictureLayerTilingClient* client)
  77     : contents_scale_(contents_scale),
  78       layer_bounds_(layer_bounds),
  79       resolution_(NON_IDEAL_RESOLUTION),
  80       client_(client),
  81       tiling_data_(gfx::Size(), gfx::Size(), true),
  82       last_impl_frame_time_in_seconds_(0.0),
  83       has_visible_rect_tiles_(false),
  84       has_skewport_rect_tiles_(false),
  85       has_soon_border_rect_tiles_(false),
  86       has_eventually_rect_tiles_(false),
  87       eviction_tiles_cache_valid_(false),
  88       eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
  89   gfx::Size content_bounds =
  90       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
  91   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
  92
  93   DCHECK(!gfx::ToFlooredSize(
  94       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
  95       "Tiling created with scale too small as contents become empty." <<
  96       " Layer bounds: " << layer_bounds.ToString() <<
  97       " Contents scale: " << contents_scale;
  98
  99   tiling_data_.SetTilingSize(content_bounds);
 100   tiling_data_.SetMaxTextureSize(tile_size);
 101 }
 102
 103 PictureLayerTiling::~PictureLayerTiling() {
 104   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 105     ReleaseTile(it->second.get(), client_->GetTree());
 106 }
 107
 108 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
 109   client_ = client;
 110 }
 111
 112 Tile* PictureLayerTiling::CreateTile(int i,
 113                                      int j,
 114                                      const PictureLayerTiling* twin_tiling) {
 115   TileMapKey key(i, j);
 116   DCHECK(tiles_.find(key) == tiles_.end());
 117
 118   gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
 119   gfx::Rect tile_rect = paint_rect;
 120   tile_rect.set_size(tiling_data_.max_texture_size());
 121
 122   // Check our twin for a valid tile.
 123   if (twin_tiling &&
 124       tiling_data_.max_texture_size() ==
 125       twin_tiling->tiling_data_.max_texture_size()) {
 126     if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
 127       gfx::Rect rect =
 128           gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
 129       if (!client_->GetInvalidation()->Intersects(rect)) {
 130         DCHECK(!candidate_tile->is_shared());
 131         candidate_tile->set_shared(true);
 132         tiles_[key] = candidate_tile;
 133         return candidate_tile;
 134       }
 135     }
 136   }
 137
 138   // Create a new tile because our twin didn't have a valid one.
 139   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
 140   if (tile.get()) {
 141     DCHECK(!tile->is_shared());
 142     tiles_[key] = tile;
 143   }
 144   return tile.get();
 145 }
 146
 147 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
 148   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 149   bool include_borders = true;
 150   for (TilingData::Iterator iter(
 151            &tiling_data_, live_tiles_rect_, include_borders);
 152        iter;
 153        ++iter) {
 154     TileMapKey key = iter.index();
 155     TileMap::iterator find = tiles_.find(key);
 156     if (find != tiles_.end())
 157       continue;
 158     CreateTile(key.first, key.second, twin_tiling);
 159   }
 160 }
 161
 162 void PictureLayerTiling::UpdateTilesToCurrentPile(
 163     const Region& layer_invalidation,
 164     const gfx::Size& new_layer_bounds) {
 165   DCHECK(!new_layer_bounds.IsEmpty());
 166
 167   gfx::Size old_layer_bounds = layer_bounds_;
 168   layer_bounds_ = new_layer_bounds;
 169
 170   gfx::Size content_bounds =
 171       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
 172   gfx::Size tile_size = tiling_data_.max_texture_size();
 173
 174   if (layer_bounds_ != old_layer_bounds) {
 175     // Drop tiles outside the new layer bounds if the layer shrank.
 176     SetLiveTilesRect(
 177         gfx::IntersectRects(live_tiles_rect_, gfx::Rect(content_bounds)));
 178     tiling_data_.SetTilingSize(content_bounds);
 179     tile_size = client_->CalculateTileSize(content_bounds);
 180   }
 181
 182   if (tile_size != tiling_data_.max_texture_size()) {
 183     tiling_data_.SetMaxTextureSize(tile_size);
 184     // When the tile size changes, the TilingData positions no longer work
 185     // as valid keys to the TileMap, so just drop all tiles.
 186     Reset();
 187   } else {
 188     Invalidate(layer_invalidation);
 189   }
 190
 191   PicturePileImpl* pile = client_->GetPile();
 192   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 193     it->second->set_picture_pile(pile);
 194 }
 195
 196 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) {
 197   bool recreate_invalidated_tiles = false;
 198   DoInvalidate(layer_region, recreate_invalidated_tiles);
 199 }
 200
 201 void PictureLayerTiling::Invalidate(const Region& layer_region) {
 202   bool recreate_invalidated_tiles = true;
 203   DoInvalidate(layer_region, recreate_invalidated_tiles);
 204 }
 205
 206 void PictureLayerTiling::DoInvalidate(const Region& layer_region,
 207                                       bool recreate_invalidated_tiles) {
 208   std::vector<TileMapKey> new_tile_keys;
 209   gfx::Rect expanded_live_tiles_rect =
 210       tiling_data_.ExpandRectIgnoringBordersToTileBoundsWithBorders(
 211           live_tiles_rect_);
 212   for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
 213     gfx::Rect layer_rect = iter.rect();
 214     gfx::Rect content_rect =
 215         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
 216     // Avoid needless work by not bothering to invalidate where there aren't
 217     // tiles.
 218     content_rect.Intersect(expanded_live_tiles_rect);
 219     if (content_rect.IsEmpty())
 220       continue;
 221     bool include_borders = true;
 222     for (TilingData::Iterator iter(
 223              &tiling_data_, content_rect, include_borders);
 224          iter;
 225          ++iter) {
 226       TileMapKey key(iter.index());
 227       TileMap::iterator find = tiles_.find(key);
 228       if (find == tiles_.end())
 229         continue;
 230
 231       ReleaseTile(find->second.get(), client_->GetTree());
 232
 233       tiles_.erase(find);
 234       new_tile_keys.push_back(key);
 235     }
 236   }
 237
 238   if (recreate_invalidated_tiles && !new_tile_keys.empty()) {
 239     for (size_t i = 0; i < new_tile_keys.size(); ++i) {
 240       // Don't try to share a tile with the twin layer, it's been invalidated so
 241       // we have to make our own tile here.
 242       const PictureLayerTiling* twin_tiling = NULL;
 243       CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
 244     }
 245   }
 246 }
 247
 248 PictureLayerTiling::CoverageIterator::CoverageIterator()
 249     : tiling_(NULL),
 250       current_tile_(NULL),
 251       tile_i_(0),
 252       tile_j_(0),
 253       left_(0),
 254       top_(0),
 255       right_(-1),
 256       bottom_(-1) {
 257 }
 258
 259 PictureLayerTiling::CoverageIterator::CoverageIterator(
 260     const PictureLayerTiling* tiling,
 261     float dest_scale,
 262     const gfx::Rect& dest_rect)
 263     : tiling_(tiling),
 264       dest_rect_(dest_rect),
 265       dest_to_content_scale_(0),
 266       current_tile_(NULL),
 267       tile_i_(0),
 268       tile_j_(0),
 269       left_(0),
 270       top_(0),
 271       right_(-1),
 272       bottom_(-1) {
 273   DCHECK(tiling_);
 274   if (dest_rect_.IsEmpty())
 275     return;
 276
 277   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 278
 279   gfx::Rect content_rect =
 280       gfx::ScaleToEnclosingRect(dest_rect_,
 281                                 dest_to_content_scale_,
 282                                 dest_to_content_scale_);
 283   // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
 284   // check for non-intersection first.
 285   content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 286   if (content_rect.IsEmpty())
 287     return;
 288
 289   left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
 290   top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
 291   right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
 292       content_rect.right() - 1);
 293   bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
 294       content_rect.bottom() - 1);
 295
 296   tile_i_ = left_ - 1;
 297   tile_j_ = top_;
 298   ++(*this);
 299 }
 300
 301 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 302 }
 303
 304 PictureLayerTiling::CoverageIterator&
 305 PictureLayerTiling::CoverageIterator::operator++() {
 306   if (tile_j_ > bottom_)
 307     return *this;
 308
 309   bool first_time = tile_i_ < left_;
 310   bool new_row = false;
 311   tile_i_++;
 312   if (tile_i_ > right_) {
 313     tile_i_ = left_;
 314     tile_j_++;
 315     new_row = true;
 316     if (tile_j_ > bottom_) {
 317       current_tile_ = NULL;
 318       return *this;
 319     }
 320   }
 321
 322   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 323
 324   // Calculate the current geometry rect.  Due to floating point rounding
 325   // and ToEnclosingRect, tiles might overlap in destination space on the
 326   // edges.
 327   gfx::Rect last_geometry_rect = current_geometry_rect_;
 328
 329   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 330
 331   current_geometry_rect_ =
 332       gfx::ScaleToEnclosingRect(content_rect,
 333                                 1 / dest_to_content_scale_,
 334                                 1 / dest_to_content_scale_);
 335
 336   current_geometry_rect_.Intersect(dest_rect_);
 337
 338   if (first_time)
 339     return *this;
 340
 341   // Iteration happens left->right, top->bottom.  Running off the bottom-right
 342   // edge is handled by the intersection above with dest_rect_.  Here we make
 343   // sure that the new current geometry rect doesn't overlap with the last.
 344   int min_left;
 345   int min_top;
 346   if (new_row) {
 347     min_left = dest_rect_.x();
 348     min_top = last_geometry_rect.bottom();
 349   } else {
 350     min_left = last_geometry_rect.right();
 351     min_top = last_geometry_rect.y();
 352   }
 353
 354   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 355   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 356   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 357
 358   if (!new_row) {
 359     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 360     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 361     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 362   }
 363
 364   return *this;
 365 }
 366
 367 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 368   return current_geometry_rect_;
 369 }
 370
 371 gfx::Rect
 372 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
 373   gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
 374   rect.set_size(tiling_->tiling_data_.max_texture_size());
 375   return rect;
 376 }
 377
 378 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 379   gfx::PointF tex_origin =
 380       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 381
 382   // Convert from dest space => content space => texture space.
 383   gfx::RectF texture_rect(current_geometry_rect_);
 384   texture_rect.Scale(dest_to_content_scale_,
 385                      dest_to_content_scale_);
 386   texture_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 387   if (texture_rect.IsEmpty())
 388     return texture_rect;
 389   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 390
 391   return texture_rect;
 392 }
 393
 394 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
 395   return tiling_->tiling_data_.max_texture_size();
 396 }
 397
 398 void PictureLayerTiling::Reset() {
 399   live_tiles_rect_ = gfx::Rect();
 400   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 401     ReleaseTile(it->second.get(), client_->GetTree());
 402   tiles_.clear();
 403 }
 404
 405 gfx::Rect PictureLayerTiling::ComputeSkewport(
 406     double current_frame_time_in_seconds,
 407     const gfx::Rect& visible_rect_in_content_space) const {
 408   gfx::Rect skewport = visible_rect_in_content_space;
 409   if (last_impl_frame_time_in_seconds_ == 0.0)
 410     return skewport;
 411
 412   double time_delta =
 413       current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
 414   if (time_delta == 0.0)
 415     return skewport;
 416
 417   float skewport_target_time_in_seconds =
 418       client_->GetSkewportTargetTimeInSeconds();
 419   double extrapolation_multiplier =
 420       skewport_target_time_in_seconds / time_delta;
 421
 422   int old_x = last_visible_rect_in_content_space_.x();
 423   int old_y = last_visible_rect_in_content_space_.y();
 424   int old_right = last_visible_rect_in_content_space_.right();
 425   int old_bottom = last_visible_rect_in_content_space_.bottom();
 426
 427   int new_x = visible_rect_in_content_space.x();
 428   int new_y = visible_rect_in_content_space.y();
 429   int new_right = visible_rect_in_content_space.right();
 430   int new_bottom = visible_rect_in_content_space.bottom();
 431
 432   int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels();
 433
 434   // Compute the maximum skewport based on |skewport_limit|.
 435   gfx::Rect max_skewport = skewport;
 436   max_skewport.Inset(
 437       -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit);
 438
 439   // Inset the skewport by the needed adjustment.
 440   skewport.Inset(extrapolation_multiplier * (new_x - old_x),
 441                  extrapolation_multiplier * (new_y - old_y),
 442                  extrapolation_multiplier * (old_right - new_right),
 443                  extrapolation_multiplier * (old_bottom - new_bottom));
 444
 445   // Clip the skewport to |max_skewport|.
 446   skewport.Intersect(max_skewport);
 447
 448   // Finally, ensure that visible rect is contained in the skewport.
 449   skewport.Union(visible_rect_in_content_space);
 450   return skewport;
 451 }
 452
 453 void PictureLayerTiling::UpdateTilePriorities(
 454     WhichTree tree,
 455     const gfx::Rect& visible_layer_rect,
 456     float ideal_contents_scale,
 457     double current_frame_time_in_seconds,
 458     const OcclusionTracker<LayerImpl>* occlusion_tracker,
 459     const LayerImpl* render_target,
 460     const gfx::Transform& draw_transform) {
 461   if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
 462     // This should never be zero for the purposes of has_ever_been_updated().
 463     DCHECK_NE(current_frame_time_in_seconds, 0.0);
 464     return;
 465   }
 466
 467   gfx::Rect visible_rect_in_content_space =
 468       gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
 469
 470   if (tiling_size().IsEmpty()) {
 471     last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 472     last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 473     return;
 474   }
 475
 476   size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea();
 477
 478   gfx::Size tile_size = tiling_data_.max_texture_size();
 479   int64 eventually_rect_area =
 480       max_tiles_for_interest_area * tile_size.width() * tile_size.height();
 481
 482   gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
 483                                        visible_rect_in_content_space);
 484   DCHECK(skewport.Contains(visible_rect_in_content_space));
 485
 486   gfx::Rect eventually_rect =
 487       ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space,
 488                                        eventually_rect_area,
 489                                        gfx::Rect(tiling_size()),
 490                                        &expansion_cache_);
 491
 492   DCHECK(eventually_rect.IsEmpty() ||
 493          gfx::Rect(tiling_size()).Contains(eventually_rect))
 494       << "tiling_size: " << tiling_size().ToString()
 495       << " eventually_rect: " << eventually_rect.ToString();
 496
 497   SetLiveTilesRect(eventually_rect);
 498
 499   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 500   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 501
 502   eviction_tiles_cache_valid_ = false;
 503
 504   TilePriority now_priority(resolution_, TilePriority::NOW, 0);
 505   float content_to_screen_scale = ideal_contents_scale / contents_scale_;
 506
 507   // Assign now priority to all visible tiles.
 508   bool include_borders = true;
 509   has_visible_rect_tiles_ = false;
 510   for (TilingData::Iterator iter(
 511            &tiling_data_, visible_rect_in_content_space, include_borders);
 512        iter;
 513        ++iter) {
 514     TileMap::iterator find = tiles_.find(iter.index());
 515     if (find == tiles_.end())
 516       continue;
 517     has_visible_rect_tiles_ = true;
 518     Tile* tile = find->second.get();
 519
 520     tile->SetPriority(tree, now_priority);
 521
 522     // Set whether tile is occluded or not.
 523     bool is_occluded = false;
 524     if (occlusion_tracker) {
 525       gfx::Rect tile_query_rect = ScaleToEnclosingRect(
 526           IntersectRects(tile->content_rect(), visible_rect_in_content_space),
 527           1.0f / contents_scale_);
 528       // TODO(vmpstr): Remove render_target and draw_transform from the
 529       // parameters so they can be hidden from the tiling.
 530       is_occluded = occlusion_tracker->Occluded(
 531           render_target, tile_query_rect, draw_transform);
 532     }
 533     tile->set_is_occluded(tree, is_occluded);
 534   }
 535
 536   // Assign soon priority to skewport tiles.
 537   has_skewport_rect_tiles_ = false;
 538   for (TilingData::DifferenceIterator iter(
 539            &tiling_data_, skewport, visible_rect_in_content_space);
 540        iter;
 541        ++iter) {
 542     TileMap::iterator find = tiles_.find(iter.index());
 543     if (find == tiles_.end())
 544       continue;
 545     has_skewport_rect_tiles_ = true;
 546     Tile* tile = find->second.get();
 547
 548     gfx::Rect tile_bounds =
 549         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 550
 551     float distance_to_visible =
 552         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
 553         content_to_screen_scale;
 554
 555     TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible);
 556     tile->SetPriority(tree, priority);
 557   }
 558
 559   // Assign eventually priority to interest rect tiles.
 560   has_eventually_rect_tiles_ = false;
 561   for (TilingData::DifferenceIterator iter(
 562            &tiling_data_, eventually_rect, skewport);
 563        iter;
 564        ++iter) {
 565     TileMap::iterator find = tiles_.find(iter.index());
 566     if (find == tiles_.end())
 567       continue;
 568     has_eventually_rect_tiles_ = true;
 569     Tile* tile = find->second.get();
 570
 571     gfx::Rect tile_bounds =
 572         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 573
 574     float distance_to_visible =
 575         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
 576         content_to_screen_scale;
 577     TilePriority priority(
 578         resolution_, TilePriority::EVENTUALLY, distance_to_visible);
 579     tile->SetPriority(tree, priority);
 580   }
 581
 582   // Upgrade the priority on border tiles to be SOON.
 583   gfx::Rect soon_border_rect = visible_rect_in_content_space;
 584   float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale;
 585   soon_border_rect.Inset(-border, -border, -border, -border);
 586   has_soon_border_rect_tiles_ = false;
 587   for (TilingData::DifferenceIterator iter(
 588            &tiling_data_, soon_border_rect, skewport);
 589        iter;
 590        ++iter) {
 591     TileMap::iterator find = tiles_.find(iter.index());
 592     if (find == tiles_.end())
 593       continue;
 594     has_soon_border_rect_tiles_ = true;
 595     Tile* tile = find->second.get();
 596
 597     TilePriority priority(resolution_,
 598                           TilePriority::SOON,
 599                           tile->priority(tree).distance_to_visible);
 600     tile->SetPriority(tree, priority);
 601   }
 602
 603   // Update iteration rects.
 604   current_visible_rect_ = visible_rect_in_content_space;
 605   current_skewport_rect_ = skewport;
 606   current_soon_border_rect_ = soon_border_rect;
 607   current_eventually_rect_ = eventually_rect;
 608 }
 609
 610 void PictureLayerTiling::SetLiveTilesRect(
 611     const gfx::Rect& new_live_tiles_rect) {
 612   DCHECK(new_live_tiles_rect.IsEmpty() ||
 613          gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
 614       << "tiling_size: " << tiling_size().ToString()
 615       << " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
 616   if (live_tiles_rect_ == new_live_tiles_rect)
 617     return;
 618
 619   // Iterate to delete all tiles outside of our new live_tiles rect.
 620   for (TilingData::DifferenceIterator iter(&tiling_data_,
 621                                            live_tiles_rect_,
 622                                            new_live_tiles_rect);
 623        iter;
 624        ++iter) {
 625     TileMapKey key(iter.index());
 626     TileMap::iterator found = tiles_.find(key);
 627     // If the tile was outside of the recorded region, it won't exist even
 628     // though it was in the live rect.
 629     if (found != tiles_.end()) {
 630       ReleaseTile(found->second.get(), client_->GetTree());
 631       tiles_.erase(found);
 632     }
 633   }
 634
 635   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 636
 637   // Iterate to allocate new tiles for all regions with newly exposed area.
 638   for (TilingData::DifferenceIterator iter(&tiling_data_,
 639                                            new_live_tiles_rect,
 640                                            live_tiles_rect_);
 641        iter;
 642        ++iter) {
 643     TileMapKey key(iter.index());
 644     CreateTile(key.first, key.second, twin_tiling);
 645   }
 646
 647   live_tiles_rect_ = new_live_tiles_rect;
 648 }
 649
 650 void PictureLayerTiling::DidBecomeRecycled() {
 651   // DidBecomeActive below will set the active priority for tiles that are
 652   // still in the tree. Calling this first on an active tiling that is becoming
 653   // recycled takes care of tiles that are no longer in the active tree (eg.
 654   // due to a pending invalidation).
 655   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 656     it->second->SetPriority(ACTIVE_TREE, TilePriority());
 657   }
 658 }
 659
 660 void PictureLayerTiling::DidBecomeActive() {
 661   PicturePileImpl* active_pile = client_->GetPile();
 662   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 663     it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
 664     it->second->SetPriority(PENDING_TREE, TilePriority());
 665
 666     // Tile holds a ref onto a picture pile. If the tile never gets invalidated
 667     // and recreated, then that picture pile ref could exist indefinitely.  To
 668     // prevent this, ask the client to update the pile to its own ref.  This
 669     // will cause PicturePileImpls to get deleted once the corresponding
 670     // PictureLayerImpl and any in flight raster jobs go out of scope.
 671     it->second->set_picture_pile(active_pile);
 672   }
 673 }
 674
 675 void PictureLayerTiling::AsValueInto(base::debug::TracedValue* state) const {
 676   state->SetInteger("num_tiles", tiles_.size());
 677   state->SetDouble("content_scale", contents_scale_);
 678   state->BeginDictionary("tiling_size");
 679   MathUtil::AddToTracedValue(tiling_size(), state);
 680   state->EndDictionary();
 681 }
 682
 683 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 684   size_t amount = 0;
 685   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 686     const Tile* tile = it->second.get();
 687     amount += tile->GPUMemoryUsageInBytes();
 688   }
 689   return amount;
 690 }
 691
 692 PictureLayerTiling::RectExpansionCache::RectExpansionCache()
 693   : previous_target(0) {
 694 }
 695
 696 namespace {
 697
 698 // This struct represents an event at which the expending rect intersects
 699 // one of its boundaries.  4 intersection events will occur during expansion.
 700 struct EdgeEvent {
 701   enum { BOTTOM, TOP, LEFT, RIGHT } edge;
 702   int* num_edges;
 703   int distance;
 704 };
 705
 706 // Compute the delta to expand from edges to cover target_area.
 707 int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
 708                           int width, int height,
 709                           int64 target_area) {
 710   // Compute coefficients for the quadratic equation:
 711   //   a*x^2 + b*x + c = 0
 712   int a = num_y_edges * num_x_edges;
 713   int b = num_y_edges * width + num_x_edges * height;
 714   int64 c = static_cast<int64>(width) * height - target_area;
 715
 716   // Compute the delta for our edges using the quadratic equation.
 717   return a == 0 ? -c / b :
 718      (-b + static_cast<int>(
 719          std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
 720 }
 721
 722 }  // namespace
 723
 724 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
 725     const gfx::Rect& starting_rect,
 726     int64 target_area,
 727     const gfx::Rect& bounding_rect,
 728     RectExpansionCache* cache) {
 729   if (starting_rect.IsEmpty())
 730     return starting_rect;
 731
 732   if (cache &&
 733       cache->previous_start == starting_rect &&
 734       cache->previous_bounds == bounding_rect &&
 735       cache->previous_target == target_area)
 736     return cache->previous_result;
 737
 738   if (cache) {
 739     cache->previous_start = starting_rect;
 740     cache->previous_bounds = bounding_rect;
 741     cache->previous_target = target_area;
 742   }
 743
 744   DCHECK(!bounding_rect.IsEmpty());
 745   DCHECK_GT(target_area, 0);
 746
 747   // Expand the starting rect to cover target_area, if it is smaller than it.
 748   int delta = ComputeExpansionDelta(
 749       2, 2, starting_rect.width(), starting_rect.height(), target_area);
 750   gfx::Rect expanded_starting_rect = starting_rect;
 751   if (delta > 0)
 752     expanded_starting_rect.Inset(-delta, -delta);
 753
 754   gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
 755   if (rect.IsEmpty()) {
 756     // The starting_rect and bounding_rect are far away.
 757     if (cache)
 758       cache->previous_result = rect;
 759     return rect;
 760   }
 761   if (delta >= 0 && rect == expanded_starting_rect) {
 762     // The starting rect already covers the entire bounding_rect and isn't too
 763     // large for the target_area.
 764     if (cache)
 765       cache->previous_result = rect;
 766     return rect;
 767   }
 768
 769   // Continue to expand/shrink rect to let it cover target_area.
 770
 771   // These values will be updated by the loop and uses as the output.
 772   int origin_x = rect.x();
 773   int origin_y = rect.y();
 774   int width = rect.width();
 775   int height = rect.height();
 776
 777   // In the beginning we will consider 2 edges in each dimension.
 778   int num_y_edges = 2;
 779   int num_x_edges = 2;
 780
 781   // Create an event list.
 782   EdgeEvent events[] = {
 783     { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
 784     { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
 785     { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
 786     { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
 787   };
 788
 789   // Sort the events by distance (closest first).
 790   if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
 791   if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
 792   if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
 793   if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
 794   if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
 795
 796   for (int event_index = 0; event_index < 4; event_index++) {
 797     const EdgeEvent& event = events[event_index];
 798
 799     int delta = ComputeExpansionDelta(
 800         num_x_edges, num_y_edges, width, height, target_area);
 801
 802     // Clamp delta to our event distance.
 803     if (delta > event.distance)
 804       delta = event.distance;
 805
 806     // Adjust the edge count for this kind of edge.
 807     --*event.num_edges;
 808
 809     // Apply the delta to the edges and edge events.
 810     for (int i = event_index; i < 4; i++) {
 811       switch (events[i].edge) {
 812         case EdgeEvent::BOTTOM:
 813             origin_y -= delta;
 814             height += delta;
 815             break;
 816         case EdgeEvent::TOP:
 817             height += delta;
 818             break;
 819         case EdgeEvent::LEFT:
 820             origin_x -= delta;
 821             width += delta;
 822             break;
 823         case EdgeEvent::RIGHT:
 824             width += delta;
 825             break;
 826       }
 827       events[i].distance -= delta;
 828     }
 829
 830     // If our delta is less then our event distance, we're done.
 831     if (delta < event.distance)
 832       break;
 833   }
 834
 835   gfx::Rect result(origin_x, origin_y, width, height);
 836   if (cache)
 837     cache->previous_result = result;
 838   return result;
 839 }
 840
 841 void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
 842     TreePriority tree_priority) {
 843   if (eviction_tiles_cache_valid_ &&
 844       eviction_cache_tree_priority_ == tree_priority)
 845     return;
 846
 847   eviction_tiles_now_.clear();
 848   eviction_tiles_now_and_required_for_activation_.clear();
 849   eviction_tiles_soon_.clear();
 850   eviction_tiles_soon_and_required_for_activation_.clear();
 851   eviction_tiles_eventually_.clear();
 852   eviction_tiles_eventually_and_required_for_activation_.clear();
 853
 854   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 855     // TODO(vmpstr): This should update the priority if UpdateTilePriorities
 856     // changes not to do this.
 857     Tile* tile = it->second.get();
 858     const TilePriority& priority =
 859         tile->priority_for_tree_priority(tree_priority);
 860     switch (priority.priority_bin) {
 861       case TilePriority::EVENTUALLY:
 862         if (tile->required_for_activation())
 863           eviction_tiles_eventually_and_required_for_activation_.push_back(
 864               tile);
 865         else
 866           eviction_tiles_eventually_.push_back(tile);
 867         break;
 868       case TilePriority::SOON:
 869         if (tile->required_for_activation())
 870           eviction_tiles_soon_and_required_for_activation_.push_back(tile);
 871         else
 872           eviction_tiles_soon_.push_back(tile);
 873         break;
 874       case TilePriority::NOW:
 875         if (tile->required_for_activation())
 876           eviction_tiles_now_and_required_for_activation_.push_back(tile);
 877         else
 878           eviction_tiles_now_.push_back(tile);
 879         break;
 880     }
 881   }
 882
 883   // TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that
 884   // can be updated for each of the queues.
 885   TileEvictionOrder sort_order(tree_priority);
 886   std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order);
 887   std::sort(eviction_tiles_now_and_required_for_activation_.begin(),
 888             eviction_tiles_now_and_required_for_activation_.end(),
 889             sort_order);
 890   std::sort(
 891       eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order);
 892   std::sort(eviction_tiles_soon_and_required_for_activation_.begin(),
 893             eviction_tiles_soon_and_required_for_activation_.end(),
 894             sort_order);
 895   std::sort(eviction_tiles_eventually_.begin(),
 896             eviction_tiles_eventually_.end(),
 897             sort_order);
 898   std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(),
 899             eviction_tiles_eventually_and_required_for_activation_.end(),
 900             sort_order);
 901
 902   eviction_tiles_cache_valid_ = true;
 903   eviction_cache_tree_priority_ = tree_priority;
 904 }
 905
 906 const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles(
 907     TreePriority tree_priority,
 908     EvictionCategory category) {
 909   UpdateEvictionCacheIfNeeded(tree_priority);
 910   switch (category) {
 911     case EVENTUALLY:
 912       return &eviction_tiles_eventually_;
 913     case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
 914       return &eviction_tiles_eventually_and_required_for_activation_;
 915     case SOON:
 916       return &eviction_tiles_soon_;
 917     case SOON_AND_REQUIRED_FOR_ACTIVATION:
 918       return &eviction_tiles_soon_and_required_for_activation_;
 919     case NOW:
 920       return &eviction_tiles_now_;
 921     case NOW_AND_REQUIRED_FOR_ACTIVATION:
 922       return &eviction_tiles_now_and_required_for_activation_;
 923   }
 924   NOTREACHED();
 925   return &eviction_tiles_eventually_;
 926 }
 927
 928 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
 929     : tiling_(NULL), current_tile_(NULL) {}
 930
 931 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
 932     PictureLayerTiling* tiling,
 933     WhichTree tree)
 934     : tiling_(tiling), phase_(VISIBLE_RECT), tree_(tree), current_tile_(NULL) {
 935   if (!tiling_->has_visible_rect_tiles_) {
 936     AdvancePhase();
 937     return;
 938   }
 939
 940   visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
 941                                            tiling_->current_visible_rect_,
 942                                            true /* include_borders */);
 943   if (!visible_iterator_) {
 944     AdvancePhase();
 945     return;
 946   }
 947
 948   current_tile_ =
 949       tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y());
 950   if (!current_tile_ || !TileNeedsRaster(current_tile_))
 951     ++(*this);
 952 }
 953
 954 PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
 955
 956 void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() {
 957   DCHECK_LT(phase_, EVENTUALLY_RECT);
 958
 959   do {
 960     phase_ = static_cast<Phase>(phase_ + 1);
 961     switch (phase_) {
 962       case VISIBLE_RECT:
 963         NOTREACHED();
 964         return;
 965       case SKEWPORT_RECT:
 966         if (!tiling_->has_skewport_rect_tiles_)
 967           continue;
 968
 969         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
 970             &tiling_->tiling_data_,
 971             tiling_->current_skewport_rect_,
 972             tiling_->current_visible_rect_,
 973             tiling_->current_visible_rect_);
 974         break;
 975       case SOON_BORDER_RECT:
 976         if (!tiling_->has_soon_border_rect_tiles_)
 977           continue;
 978
 979         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
 980             &tiling_->tiling_data_,
 981             tiling_->current_soon_border_rect_,
 982             tiling_->current_skewport_rect_,
 983             tiling_->current_visible_rect_);
 984         break;
 985       case EVENTUALLY_RECT:
 986         if (!tiling_->has_eventually_rect_tiles_) {
 987           current_tile_ = NULL;
 988           return;
 989         }
 990
 991         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
 992             &tiling_->tiling_data_,
 993             tiling_->current_eventually_rect_,
 994             tiling_->current_skewport_rect_,
 995             tiling_->current_soon_border_rect_);
 996         break;
 997     }
 998
 999     while (spiral_iterator_) {
1000       current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(),
1001                                       spiral_iterator_.index_y());
1002       if (current_tile_ && TileNeedsRaster(current_tile_))
1003         break;
1004       ++spiral_iterator_;
1005     }
1006
1007     if (!spiral_iterator_ && phase_ == EVENTUALLY_RECT) {
1008       current_tile_ = NULL;
1009       break;
1010     }
1011   } while (!spiral_iterator_);
1012 }
1013
1014 PictureLayerTiling::TilingRasterTileIterator&
1015 PictureLayerTiling::TilingRasterTileIterator::
1016 operator++() {
1017   current_tile_ = NULL;
1018   while (!current_tile_ || !TileNeedsRaster(current_tile_)) {
1019     std::pair<int, int> next_index;
1020     switch (phase_) {
1021       case VISIBLE_RECT:
1022         ++visible_iterator_;
1023         if (!visible_iterator_) {
1024           AdvancePhase();
1025           return *this;
1026         }
1027         next_index = visible_iterator_.index();
1028         break;
1029       case SKEWPORT_RECT:
1030       case SOON_BORDER_RECT:
1031         ++spiral_iterator_;
1032         if (!spiral_iterator_) {
1033           AdvancePhase();
1034           return *this;
1035         }
1036         next_index = spiral_iterator_.index();
1037         break;
1038       case EVENTUALLY_RECT:
1039         ++spiral_iterator_;
1040         if (!spiral_iterator_) {
1041           current_tile_ = NULL;
1042           return *this;
1043         }
1044         next_index = spiral_iterator_.index();
1045         break;
1046     }
1047     current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
1048   }
1049   return *this;
1050 }
1051
1052 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
1053     : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
1054 }
1055
1056 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
1057     PictureLayerTiling* tiling,
1058     TreePriority tree_priority,
1059     EvictionCategory category)
1060     : eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)),
1061       // Note: initializing to "0 - 1" works as overflow is well defined for
1062       // unsigned integers.
1063       current_eviction_tiles_index_(static_cast<size_t>(0) - 1) {
1064   DCHECK(eviction_tiles_);
1065   ++(*this);
1066 }
1067
1068 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
1069 }
1070
1071 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
1072   return eviction_tiles_ &&
1073          current_eviction_tiles_index_ != eviction_tiles_->size();
1074 }
1075
1076 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
1077   DCHECK(*this);
1078   return (*eviction_tiles_)[current_eviction_tiles_index_];
1079 }
1080
1081 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
1082   DCHECK(*this);
1083   return (*eviction_tiles_)[current_eviction_tiles_index_];
1084 }
1085
1086 PictureLayerTiling::TilingEvictionTileIterator&
1087 PictureLayerTiling::TilingEvictionTileIterator::
1088 operator++() {
1089   DCHECK(*this);
1090   do {
1091     ++current_eviction_tiles_index_;
1092   } while (current_eviction_tiles_index_ != eviction_tiles_->size() &&
1093            !(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources());
1094
1095   return *this;
1096 }
1097
1098 }  // namespace cc