src/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 #include <set>
  11
  12 #include "base/debug/trace_event.h"
  13 #include "base/debug/trace_event_argument.h"
  14 #include "base/logging.h"
  15 #include "cc/base/math_util.h"
  16 #include "cc/resources/tile.h"
  17 #include "cc/resources/tile_priority.h"
  18 #include "ui/gfx/geometry/point_conversions.h"
  19 #include "ui/gfx/geometry/rect_conversions.h"
  20 #include "ui/gfx/geometry/safe_integer_conversions.h"
  21 #include "ui/gfx/geometry/size_conversions.h"
  22
  23 namespace cc {
  24 namespace {
  25
  26 const float kSoonBorderDistanceInScreenPixels = 312.f;
  27
  28 class TileEvictionOrder {
  29  public:
  30   explicit TileEvictionOrder(TreePriority tree_priority)
  31       : tree_priority_(tree_priority) {}
  32   ~TileEvictionOrder() {}
  33
  34   bool operator()(const Tile* a, const Tile* b) {
  35     const TilePriority& a_priority =
  36         a->priority_for_tree_priority(tree_priority_);
  37     const TilePriority& b_priority =
  38         b->priority_for_tree_priority(tree_priority_);
  39
  40     DCHECK(a_priority.priority_bin == b_priority.priority_bin);
  41     DCHECK(a->required_for_activation() == b->required_for_activation());
  42
  43     // Or if a is occluded and b is unoccluded.
  44     bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
  45     bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
  46     if (a_is_occluded != b_is_occluded)
  47       return a_is_occluded;
  48
  49     // Or if a is farther away from visible.
  50     return a_priority.distance_to_visible > b_priority.distance_to_visible;
  51   }
  52
  53  private:
  54   TreePriority tree_priority_;
  55 };
  56
  57 }  // namespace
  58
  59 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
  60     float contents_scale,
  61     const gfx::Size& layer_bounds,
  62     PictureLayerTilingClient* client) {
  63   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
  64                                                 layer_bounds,
  65                                                 client));
  66 }
  67
  68 PictureLayerTiling::PictureLayerTiling(float contents_scale,
  69                                        const gfx::Size& layer_bounds,
  70                                        PictureLayerTilingClient* client)
  71     : contents_scale_(contents_scale),
  72       layer_bounds_(layer_bounds),
  73       resolution_(NON_IDEAL_RESOLUTION),
  74       client_(client),
  75       tiling_data_(gfx::Size(), gfx::Size(), kBorderTexels),
  76       last_impl_frame_time_in_seconds_(0.0),
  77       content_to_screen_scale_(0.f),
  78       can_require_tiles_for_activation_(false),
  79       has_visible_rect_tiles_(false),
  80       has_skewport_rect_tiles_(false),
  81       has_soon_border_rect_tiles_(false),
  82       has_eventually_rect_tiles_(false),
  83       eviction_tiles_cache_valid_(false),
  84       eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
  85   gfx::Size content_bounds =
  86       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
  87   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
  88   if (tile_size.IsEmpty()) {
  89     layer_bounds_ = gfx::Size();
  90     content_bounds = gfx::Size();
  91   }
  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     it->second->set_shared(false);
 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       const Region* invalidation = client_->GetPendingInvalidation();
 130       if (!invalidation || !invalidation->Intersects(rect)) {
 131         DCHECK(!candidate_tile->is_shared());
 132         DCHECK_EQ(i, candidate_tile->tiling_i_index());
 133         DCHECK_EQ(j, candidate_tile->tiling_j_index());
 134         candidate_tile->set_shared(true);
 135         tiles_[key] = candidate_tile;
 136         return candidate_tile;
 137       }
 138     }
 139   }
 140
 141   // Create a new tile because our twin didn't have a valid one.
 142   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
 143   if (tile.get()) {
 144     DCHECK(!tile->is_shared());
 145     tile->set_tiling_index(i, j);
 146     tiles_[key] = tile;
 147   }
 148   eviction_tiles_cache_valid_ = false;
 149   return tile.get();
 150 }
 151
 152 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
 153   const PictureLayerTiling* twin_tiling =
 154       client_->GetPendingOrActiveTwinTiling(this);
 155   bool include_borders = false;
 156   for (TilingData::Iterator iter(
 157            &tiling_data_, live_tiles_rect_, include_borders);
 158        iter;
 159        ++iter) {
 160     TileMapKey key = iter.index();
 161     TileMap::iterator find = tiles_.find(key);
 162     if (find != tiles_.end())
 163       continue;
 164     CreateTile(key.first, key.second, twin_tiling);
 165   }
 166
 167   VerifyLiveTilesRect();
 168 }
 169
 170 void PictureLayerTiling::UpdateTilesToCurrentPile(
 171     const Region& layer_invalidation,
 172     const gfx::Size& new_layer_bounds) {
 173   DCHECK(!new_layer_bounds.IsEmpty());
 174
 175   gfx::Size tile_size = tiling_data_.max_texture_size();
 176
 177   if (new_layer_bounds != layer_bounds_) {
 178     gfx::Size content_bounds =
 179         gfx::ToCeiledSize(gfx::ScaleSize(new_layer_bounds, contents_scale_));
 180
 181     tile_size = client_->CalculateTileSize(content_bounds);
 182     if (tile_size.IsEmpty()) {
 183       layer_bounds_ = gfx::Size();
 184       content_bounds = gfx::Size();
 185     } else {
 186       layer_bounds_ = new_layer_bounds;
 187     }
 188
 189     // The SetLiveTilesRect() method would drop tiles outside the new bounds,
 190     // but may do so incorrectly if resizing the tiling causes the number of
 191     // tiles in the tiling_data_ to change.
 192     gfx::Rect content_rect(content_bounds);
 193     int before_left = tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.x());
 194     int before_top = tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.y());
 195     int before_right =
 196         tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 197     int before_bottom =
 198         tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 199
 200     // The live_tiles_rect_ is clamped to stay within the tiling size as we
 201     // change it.
 202     live_tiles_rect_.Intersect(content_rect);
 203     tiling_data_.SetTilingSize(content_bounds);
 204
 205     int after_right = -1;
 206     int after_bottom = -1;
 207     if (!live_tiles_rect_.IsEmpty()) {
 208       after_right =
 209           tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 210       after_bottom =
 211           tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 212     }
 213
 214     // There is no recycled twin since this is run on the pending tiling.
 215     PictureLayerTiling* recycled_twin = NULL;
 216     DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this));
 217     DCHECK_EQ(PENDING_TREE, client_->GetTree());
 218
 219     // Drop tiles outside the new layer bounds if the layer shrank.
 220     for (int i = after_right + 1; i <= before_right; ++i) {
 221       for (int j = before_top; j <= before_bottom; ++j)
 222         RemoveTileAt(i, j, recycled_twin);
 223     }
 224     for (int i = before_left; i <= after_right; ++i) {
 225       for (int j = after_bottom + 1; j <= before_bottom; ++j)
 226         RemoveTileAt(i, j, recycled_twin);
 227     }
 228
 229     // If the layer grew, the live_tiles_rect_ is not changed, but a new row
 230     // and/or column of tiles may now exist inside the same live_tiles_rect_.
 231     const PictureLayerTiling* twin_tiling =
 232         client_->GetPendingOrActiveTwinTiling(this);
 233     if (after_right > before_right) {
 234       DCHECK_EQ(after_right, before_right + 1);
 235       for (int j = before_top; j <= after_bottom; ++j)
 236         CreateTile(after_right, j, twin_tiling);
 237     }
 238     if (after_bottom > before_bottom) {
 239       DCHECK_EQ(after_bottom, before_bottom + 1);
 240       for (int i = before_left; i <= before_right; ++i)
 241         CreateTile(i, after_bottom, twin_tiling);
 242     }
 243   }
 244
 245   if (tile_size != tiling_data_.max_texture_size()) {
 246     tiling_data_.SetMaxTextureSize(tile_size);
 247     // When the tile size changes, the TilingData positions no longer work
 248     // as valid keys to the TileMap, so just drop all tiles.
 249     Reset();
 250   } else {
 251     Invalidate(layer_invalidation);
 252   }
 253
 254   RasterSource* raster_source = client_->GetRasterSource();
 255   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 256     it->second->set_raster_source(raster_source);
 257   VerifyLiveTilesRect();
 258 }
 259
 260 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) {
 261   bool recreate_invalidated_tiles = false;
 262   DoInvalidate(layer_region, recreate_invalidated_tiles);
 263 }
 264
 265 void PictureLayerTiling::Invalidate(const Region& layer_region) {
 266   bool recreate_invalidated_tiles = true;
 267   DoInvalidate(layer_region, recreate_invalidated_tiles);
 268 }
 269
 270 void PictureLayerTiling::DoInvalidate(const Region& layer_region,
 271                                       bool recreate_invalidated_tiles) {
 272   std::vector<TileMapKey> new_tile_keys;
 273   gfx::Rect expanded_live_tiles_rect =
 274       tiling_data_.ExpandRectIgnoringBordersToTileBounds(live_tiles_rect_);
 275   for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
 276     gfx::Rect layer_rect = iter.rect();
 277     gfx::Rect content_rect =
 278         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
 279     // Consider tiles inside the live tiles rect even if only their border
 280     // pixels intersect the invalidation. But don't consider tiles outside
 281     // the live tiles rect with the same conditions, as they won't exist.
 282     int border_pixels = tiling_data_.border_texels();
 283     content_rect.Inset(-border_pixels, -border_pixels);
 284     // Avoid needless work by not bothering to invalidate where there aren't
 285     // tiles.
 286     content_rect.Intersect(expanded_live_tiles_rect);
 287     if (content_rect.IsEmpty())
 288       continue;
 289     // Since the content_rect includes border pixels already, don't include
 290     // borders when iterating to avoid double counting them.
 291     bool include_borders = false;
 292     for (TilingData::Iterator iter(
 293              &tiling_data_, content_rect, include_borders);
 294          iter;
 295          ++iter) {
 296       // There is no recycled twin since this is run on the pending tiling.
 297       PictureLayerTiling* recycled_twin = NULL;
 298       DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this));
 299       DCHECK_EQ(PENDING_TREE, client_->GetTree());
 300       if (RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin))
 301         new_tile_keys.push_back(iter.index());
 302     }
 303   }
 304
 305   if (recreate_invalidated_tiles && !new_tile_keys.empty()) {
 306     for (size_t i = 0; i < new_tile_keys.size(); ++i) {
 307       // Don't try to share a tile with the twin layer, it's been invalidated so
 308       // we have to make our own tile here.
 309       const PictureLayerTiling* twin_tiling = NULL;
 310       CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
 311     }
 312   }
 313 }
 314
 315 PictureLayerTiling::CoverageIterator::CoverageIterator()
 316     : tiling_(NULL),
 317       current_tile_(NULL),
 318       tile_i_(0),
 319       tile_j_(0),
 320       left_(0),
 321       top_(0),
 322       right_(-1),
 323       bottom_(-1) {
 324 }
 325
 326 PictureLayerTiling::CoverageIterator::CoverageIterator(
 327     const PictureLayerTiling* tiling,
 328     float dest_scale,
 329     const gfx::Rect& dest_rect)
 330     : tiling_(tiling),
 331       dest_rect_(dest_rect),
 332       dest_to_content_scale_(0),
 333       current_tile_(NULL),
 334       tile_i_(0),
 335       tile_j_(0),
 336       left_(0),
 337       top_(0),
 338       right_(-1),
 339       bottom_(-1) {
 340   DCHECK(tiling_);
 341   if (dest_rect_.IsEmpty())
 342     return;
 343
 344   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 345
 346   gfx::Rect content_rect =
 347       gfx::ScaleToEnclosingRect(dest_rect_,
 348                                 dest_to_content_scale_,
 349                                 dest_to_content_scale_);
 350   // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
 351   // check for non-intersection first.
 352   content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 353   if (content_rect.IsEmpty())
 354     return;
 355
 356   left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
 357   top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
 358   right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
 359       content_rect.right() - 1);
 360   bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
 361       content_rect.bottom() - 1);
 362
 363   tile_i_ = left_ - 1;
 364   tile_j_ = top_;
 365   ++(*this);
 366 }
 367
 368 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 369 }
 370
 371 PictureLayerTiling::CoverageIterator&
 372 PictureLayerTiling::CoverageIterator::operator++() {
 373   if (tile_j_ > bottom_)
 374     return *this;
 375
 376   bool first_time = tile_i_ < left_;
 377   bool new_row = false;
 378   tile_i_++;
 379   if (tile_i_ > right_) {
 380     tile_i_ = left_;
 381     tile_j_++;
 382     new_row = true;
 383     if (tile_j_ > bottom_) {
 384       current_tile_ = NULL;
 385       return *this;
 386     }
 387   }
 388
 389   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 390
 391   // Calculate the current geometry rect.  Due to floating point rounding
 392   // and ToEnclosingRect, tiles might overlap in destination space on the
 393   // edges.
 394   gfx::Rect last_geometry_rect = current_geometry_rect_;
 395
 396   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 397
 398   current_geometry_rect_ =
 399       gfx::ScaleToEnclosingRect(content_rect,
 400                                 1 / dest_to_content_scale_,
 401                                 1 / dest_to_content_scale_);
 402
 403   current_geometry_rect_.Intersect(dest_rect_);
 404
 405   if (first_time)
 406     return *this;
 407
 408   // Iteration happens left->right, top->bottom.  Running off the bottom-right
 409   // edge is handled by the intersection above with dest_rect_.  Here we make
 410   // sure that the new current geometry rect doesn't overlap with the last.
 411   int min_left;
 412   int min_top;
 413   if (new_row) {
 414     min_left = dest_rect_.x();
 415     min_top = last_geometry_rect.bottom();
 416   } else {
 417     min_left = last_geometry_rect.right();
 418     min_top = last_geometry_rect.y();
 419   }
 420
 421   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 422   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 423   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 424
 425   if (!new_row) {
 426     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 427     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 428     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 429   }
 430
 431   return *this;
 432 }
 433
 434 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 435   return current_geometry_rect_;
 436 }
 437
 438 gfx::Rect
 439 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
 440   gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
 441   rect.set_size(tiling_->tiling_data_.max_texture_size());
 442   return rect;
 443 }
 444
 445 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 446   gfx::PointF tex_origin =
 447       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 448
 449   // Convert from dest space => content space => texture space.
 450   gfx::RectF texture_rect(current_geometry_rect_);
 451   texture_rect.Scale(dest_to_content_scale_,
 452                      dest_to_content_scale_);
 453   texture_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 454   if (texture_rect.IsEmpty())
 455     return texture_rect;
 456   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 457
 458   return texture_rect;
 459 }
 460
 461 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
 462   return tiling_->tiling_data_.max_texture_size();
 463 }
 464
 465 bool PictureLayerTiling::RemoveTileAt(int i,
 466                                       int j,
 467                                       PictureLayerTiling* recycled_twin) {
 468   TileMap::iterator found = tiles_.find(TileMapKey(i, j));
 469   if (found == tiles_.end())
 470     return false;
 471   found->second->set_shared(false);
 472   tiles_.erase(found);
 473   eviction_tiles_cache_valid_ = false;
 474   if (recycled_twin) {
 475     // Recycled twin does not also have a recycled twin, so pass NULL.
 476     recycled_twin->RemoveTileAt(i, j, NULL);
 477   }
 478   return true;
 479 }
 480
 481 void PictureLayerTiling::Reset() {
 482   live_tiles_rect_ = gfx::Rect();
 483   PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
 484   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 485     it->second->set_shared(false);
 486     if (recycled_twin)
 487       recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL);
 488   }
 489   tiles_.clear();
 490   eviction_tiles_cache_valid_ = false;
 491 }
 492
 493 gfx::Rect PictureLayerTiling::ComputeSkewport(
 494     double current_frame_time_in_seconds,
 495     const gfx::Rect& visible_rect_in_content_space) const {
 496   gfx::Rect skewport = visible_rect_in_content_space;
 497   if (last_impl_frame_time_in_seconds_ == 0.0)
 498     return skewport;
 499
 500   double time_delta =
 501       current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
 502   if (time_delta == 0.0)
 503     return skewport;
 504
 505   float skewport_target_time_in_seconds =
 506       client_->GetSkewportTargetTimeInSeconds();
 507   double extrapolation_multiplier =
 508       skewport_target_time_in_seconds / time_delta;
 509
 510   int old_x = last_visible_rect_in_content_space_.x();
 511   int old_y = last_visible_rect_in_content_space_.y();
 512   int old_right = last_visible_rect_in_content_space_.right();
 513   int old_bottom = last_visible_rect_in_content_space_.bottom();
 514
 515   int new_x = visible_rect_in_content_space.x();
 516   int new_y = visible_rect_in_content_space.y();
 517   int new_right = visible_rect_in_content_space.right();
 518   int new_bottom = visible_rect_in_content_space.bottom();
 519
 520   int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels();
 521
 522   // Compute the maximum skewport based on |skewport_limit|.
 523   gfx::Rect max_skewport = skewport;
 524   max_skewport.Inset(
 525       -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit);
 526
 527   // Inset the skewport by the needed adjustment.
 528   skewport.Inset(extrapolation_multiplier * (new_x - old_x),
 529                  extrapolation_multiplier * (new_y - old_y),
 530                  extrapolation_multiplier * (old_right - new_right),
 531                  extrapolation_multiplier * (old_bottom - new_bottom));
 532
 533   // Clip the skewport to |max_skewport|.
 534   skewport.Intersect(max_skewport);
 535
 536   // Finally, ensure that visible rect is contained in the skewport.
 537   skewport.Union(visible_rect_in_content_space);
 538   return skewport;
 539 }
 540
 541 void PictureLayerTiling::ComputeTilePriorityRects(
 542     WhichTree tree,
 543     const gfx::Rect& viewport_in_layer_space,
 544     float ideal_contents_scale,
 545     double current_frame_time_in_seconds,
 546     const Occlusion& occlusion_in_layer_space) {
 547   if (!NeedsUpdateForFrameAtTimeAndViewport(current_frame_time_in_seconds,
 548                                             viewport_in_layer_space)) {
 549     // This should never be zero for the purposes of has_ever_been_updated().
 550     DCHECK_NE(current_frame_time_in_seconds, 0.0);
 551     return;
 552   }
 553
 554   gfx::Rect visible_rect_in_content_space =
 555       gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
 556
 557   if (tiling_size().IsEmpty()) {
 558     last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 559     last_viewport_in_layer_space_ = viewport_in_layer_space;
 560     last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 561     return;
 562   }
 563
 564   // Calculate the skewport.
 565   gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
 566                                        visible_rect_in_content_space);
 567   DCHECK(skewport.Contains(visible_rect_in_content_space));
 568
 569   // Calculate the eventually/live tiles rect.
 570   size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea();
 571
 572   gfx::Size tile_size = tiling_data_.max_texture_size();
 573   int64 eventually_rect_area =
 574       max_tiles_for_interest_area * tile_size.width() * tile_size.height();
 575
 576   gfx::Rect eventually_rect =
 577       ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space,
 578                                        eventually_rect_area,
 579                                        gfx::Rect(tiling_size()),
 580                                        &expansion_cache_);
 581
 582   DCHECK(eventually_rect.IsEmpty() ||
 583          gfx::Rect(tiling_size()).Contains(eventually_rect))
 584       << "tiling_size: " << tiling_size().ToString()
 585       << " eventually_rect: " << eventually_rect.ToString();
 586
 587   // Calculate the soon border rect.
 588   content_to_screen_scale_ = ideal_contents_scale / contents_scale_;
 589   gfx::Rect soon_border_rect = visible_rect_in_content_space;
 590   float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale_;
 591   soon_border_rect.Inset(-border, -border, -border, -border);
 592
 593   // Update the tiling state.
 594   SetLiveTilesRect(eventually_rect);
 595
 596   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 597   last_viewport_in_layer_space_ = viewport_in_layer_space;
 598   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 599
 600   eviction_tiles_cache_valid_ = false;
 601
 602   current_visible_rect_ = visible_rect_in_content_space;
 603   current_skewport_rect_ = skewport;
 604   current_soon_border_rect_ = soon_border_rect;
 605   current_eventually_rect_ = eventually_rect;
 606   current_occlusion_in_layer_space_ = occlusion_in_layer_space;
 607
 608   // Update has_*_tiles state.
 609   gfx::Rect tiling_rect(tiling_size());
 610
 611   has_visible_rect_tiles_ = tiling_rect.Intersects(current_visible_rect_);
 612   has_skewport_rect_tiles_ = tiling_rect.Intersects(current_skewport_rect_);
 613   has_soon_border_rect_tiles_ =
 614       tiling_rect.Intersects(current_soon_border_rect_);
 615   has_eventually_rect_tiles_ = tiling_rect.Intersects(current_eventually_rect_);
 616 }
 617
 618 void PictureLayerTiling::SetLiveTilesRect(
 619     const gfx::Rect& new_live_tiles_rect) {
 620   DCHECK(new_live_tiles_rect.IsEmpty() ||
 621          gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
 622       << "tiling_size: " << tiling_size().ToString()
 623       << " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
 624   if (live_tiles_rect_ == new_live_tiles_rect)
 625     return;
 626
 627   // Iterate to delete all tiles outside of our new live_tiles rect.
 628   PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
 629   for (TilingData::DifferenceIterator iter(&tiling_data_,
 630                                            live_tiles_rect_,
 631                                            new_live_tiles_rect);
 632        iter;
 633        ++iter) {
 634     RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin);
 635   }
 636
 637   const PictureLayerTiling* twin_tiling =
 638       client_->GetPendingOrActiveTwinTiling(this);
 639
 640   // Iterate to allocate new tiles for all regions with newly exposed area.
 641   for (TilingData::DifferenceIterator iter(&tiling_data_,
 642                                            new_live_tiles_rect,
 643                                            live_tiles_rect_);
 644        iter;
 645        ++iter) {
 646     TileMapKey key(iter.index());
 647     CreateTile(key.first, key.second, twin_tiling);
 648   }
 649
 650   live_tiles_rect_ = new_live_tiles_rect;
 651   VerifyLiveTilesRect();
 652 }
 653
 654 void PictureLayerTiling::VerifyLiveTilesRect() {
 655 #if DCHECK_IS_ON
 656   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 657     if (!it->second.get())
 658       continue;
 659     DCHECK(it->first.first < tiling_data_.num_tiles_x())
 660         << this << " " << it->first.first << "," << it->first.second
 661         << " num_tiles_x " << tiling_data_.num_tiles_x() << " live_tiles_rect "
 662         << live_tiles_rect_.ToString();
 663     DCHECK(it->first.second < tiling_data_.num_tiles_y())
 664         << this << " " << it->first.first << "," << it->first.second
 665         << " num_tiles_y " << tiling_data_.num_tiles_y() << " live_tiles_rect "
 666         << live_tiles_rect_.ToString();
 667     DCHECK(tiling_data_.TileBounds(it->first.first, it->first.second)
 668                .Intersects(live_tiles_rect_))
 669         << this << " " << it->first.first << "," << it->first.second
 670         << " tile bounds "
 671         << tiling_data_.TileBounds(it->first.first, it->first.second).ToString()
 672         << " live_tiles_rect " << live_tiles_rect_.ToString();
 673   }
 674 #endif
 675 }
 676
 677 bool PictureLayerTiling::IsTileOccluded(const Tile* tile) const {
 678   DCHECK(tile);
 679
 680   if (!current_occlusion_in_layer_space_.HasOcclusion())
 681     return false;
 682
 683   gfx::Rect tile_query_rect =
 684       gfx::IntersectRects(tile->content_rect(), current_visible_rect_);
 685
 686   // Explicitly check if the tile is outside the viewport. If so, we need to
 687   // return false, since occlusion for this tile is unknown.
 688   // TODO(vmpstr): Since the current visible rect is really a viewport in
 689   // layer space, we should probably clip tile query rect to tiling bounds
 690   // or live tiles rect.
 691   if (tile_query_rect.IsEmpty())
 692     return false;
 693
 694   if (contents_scale_ != 1.f) {
 695     tile_query_rect =
 696         gfx::ScaleToEnclosingRect(tile_query_rect, 1.0f / contents_scale_);
 697   }
 698
 699   return current_occlusion_in_layer_space_.IsOccluded(tile_query_rect);
 700 }
 701
 702 bool PictureLayerTiling::IsTileRequiredForActivation(const Tile* tile) const {
 703   DCHECK_EQ(PENDING_TREE, client_->GetTree());
 704
 705   // Note that although this function will determine whether tile is required
 706   // for activation assuming that it is in visible (ie in the viewport). That is
 707   // to say, even if the tile is outside of the viewport, it will be treated as
 708   // if it was inside (there are no explicit checks for this). Hence, this
 709   // function is only called for visible tiles to ensure we don't block
 710   // activation on tiles outside of the viewport.
 711
 712   // If we are not allowed to mark tiles as required for activation, then don't
 713   // do it.
 714   if (!can_require_tiles_for_activation_)
 715     return false;
 716
 717   if (resolution_ != HIGH_RESOLUTION)
 718     return false;
 719
 720   if (IsTileOccluded(tile))
 721     return false;
 722
 723   if (client_->RequiresHighResToDraw())
 724     return true;
 725
 726   const PictureLayerTiling* twin_tiling =
 727       client_->GetPendingOrActiveTwinTiling(this);
 728   if (!twin_tiling)
 729     return true;
 730
 731   if (twin_tiling->layer_bounds() != layer_bounds())
 732     return true;
 733
 734   if (twin_tiling->current_visible_rect_ != current_visible_rect_)
 735     return true;
 736
 737   Tile* twin_tile =
 738       twin_tiling->TileAt(tile->tiling_i_index(), tile->tiling_j_index());
 739   // If twin tile is missing, it might not have a recording, so we don't need
 740   // this tile to be required for activation.
 741   if (!twin_tile)
 742     return false;
 743
 744   return true;
 745 }
 746
 747 void PictureLayerTiling::UpdateTileAndTwinPriority(Tile* tile) const {
 748   UpdateTilePriority(tile);
 749
 750   const PictureLayerTiling* twin_tiling =
 751       client_->GetPendingOrActiveTwinTiling(this);
 752   if (!tile->is_shared() || !twin_tiling) {
 753     WhichTree tree = client_->GetTree();
 754     WhichTree twin_tree = tree == ACTIVE_TREE ? PENDING_TREE : ACTIVE_TREE;
 755     tile->SetPriority(twin_tree, TilePriority());
 756     tile->set_is_occluded(twin_tree, false);
 757     if (twin_tree == PENDING_TREE)
 758       tile->set_required_for_activation(false);
 759     return;
 760   }
 761
 762   twin_tiling->UpdateTilePriority(tile);
 763 }
 764
 765 void PictureLayerTiling::UpdateTilePriority(Tile* tile) const {
 766   // TODO(vmpstr): This code should return the priority instead of setting it on
 767   // the tile. This should be a part of the change to move tile priority from
 768   // tiles into iterators.
 769   WhichTree tree = client_->GetTree();
 770
 771   DCHECK_EQ(TileAt(tile->tiling_i_index(), tile->tiling_j_index()), tile);
 772   gfx::Rect tile_bounds =
 773       tiling_data_.TileBounds(tile->tiling_i_index(), tile->tiling_j_index());
 774
 775   if (current_visible_rect_.Intersects(tile_bounds)) {
 776     tile->SetPriority(tree, TilePriority(resolution_, TilePriority::NOW, 0));
 777     if (tree == PENDING_TREE)
 778       tile->set_required_for_activation(IsTileRequiredForActivation(tile));
 779     tile->set_is_occluded(tree, IsTileOccluded(tile));
 780     return;
 781   }
 782
 783   if (tree == PENDING_TREE)
 784     tile->set_required_for_activation(false);
 785   tile->set_is_occluded(tree, false);
 786
 787   DCHECK_GT(content_to_screen_scale_, 0.f);
 788   float distance_to_visible =
 789       current_visible_rect_.ManhattanInternalDistance(tile_bounds) *
 790       content_to_screen_scale_;
 791
 792   if (current_soon_border_rect_.Intersects(tile_bounds) ||
 793       current_skewport_rect_.Intersects(tile_bounds)) {
 794     tile->SetPriority(
 795         tree,
 796         TilePriority(resolution_, TilePriority::SOON, distance_to_visible));
 797     return;
 798   }
 799
 800   tile->SetPriority(
 801       tree,
 802       TilePriority(resolution_, TilePriority::EVENTUALLY, distance_to_visible));
 803 }
 804
 805 void PictureLayerTiling::GetAllTilesForTracing(
 806     std::set<const Tile*>* tiles) const {
 807   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 808     tiles->insert(it->second.get());
 809 }
 810
 811 void PictureLayerTiling::AsValueInto(base::debug::TracedValue* state) const {
 812   state->SetInteger("num_tiles", tiles_.size());
 813   state->SetDouble("content_scale", contents_scale_);
 814   state->BeginDictionary("tiling_size");
 815   MathUtil::AddToTracedValue(tiling_size(), state);
 816   state->EndDictionary();
 817 }
 818
 819 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 820   size_t amount = 0;
 821   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 822     const Tile* tile = it->second.get();
 823     amount += tile->GPUMemoryUsageInBytes();
 824   }
 825   return amount;
 826 }
 827
 828 PictureLayerTiling::RectExpansionCache::RectExpansionCache()
 829   : previous_target(0) {
 830 }
 831
 832 namespace {
 833
 834 // This struct represents an event at which the expending rect intersects
 835 // one of its boundaries.  4 intersection events will occur during expansion.
 836 struct EdgeEvent {
 837   enum { BOTTOM, TOP, LEFT, RIGHT } edge;
 838   int* num_edges;
 839   int distance;
 840 };
 841
 842 // Compute the delta to expand from edges to cover target_area.
 843 int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
 844                           int width, int height,
 845                           int64 target_area) {
 846   // Compute coefficients for the quadratic equation:
 847   //   a*x^2 + b*x + c = 0
 848   int a = num_y_edges * num_x_edges;
 849   int b = num_y_edges * width + num_x_edges * height;
 850   int64 c = static_cast<int64>(width) * height - target_area;
 851
 852   // Compute the delta for our edges using the quadratic equation.
 853   int delta =
 854       (a == 0) ? -c / b : (-b + static_cast<int>(std::sqrt(
 855                                     static_cast<int64>(b) * b - 4.0 * a * c))) /
 856                               (2 * a);
 857   return std::max(0, delta);
 858 }
 859
 860 }  // namespace
 861
 862 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
 863     const gfx::Rect& starting_rect,
 864     int64 target_area,
 865     const gfx::Rect& bounding_rect,
 866     RectExpansionCache* cache) {
 867   if (starting_rect.IsEmpty())
 868     return starting_rect;
 869
 870   if (cache &&
 871       cache->previous_start == starting_rect &&
 872       cache->previous_bounds == bounding_rect &&
 873       cache->previous_target == target_area)
 874     return cache->previous_result;
 875
 876   if (cache) {
 877     cache->previous_start = starting_rect;
 878     cache->previous_bounds = bounding_rect;
 879     cache->previous_target = target_area;
 880   }
 881
 882   DCHECK(!bounding_rect.IsEmpty());
 883   DCHECK_GT(target_area, 0);
 884
 885   // Expand the starting rect to cover target_area, if it is smaller than it.
 886   int delta = ComputeExpansionDelta(
 887       2, 2, starting_rect.width(), starting_rect.height(), target_area);
 888   gfx::Rect expanded_starting_rect = starting_rect;
 889   if (delta > 0)
 890     expanded_starting_rect.Inset(-delta, -delta);
 891
 892   gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
 893   if (rect.IsEmpty()) {
 894     // The starting_rect and bounding_rect are far away.
 895     if (cache)
 896       cache->previous_result = rect;
 897     return rect;
 898   }
 899   if (delta >= 0 && rect == expanded_starting_rect) {
 900     // The starting rect already covers the entire bounding_rect and isn't too
 901     // large for the target_area.
 902     if (cache)
 903       cache->previous_result = rect;
 904     return rect;
 905   }
 906
 907   // Continue to expand/shrink rect to let it cover target_area.
 908
 909   // These values will be updated by the loop and uses as the output.
 910   int origin_x = rect.x();
 911   int origin_y = rect.y();
 912   int width = rect.width();
 913   int height = rect.height();
 914
 915   // In the beginning we will consider 2 edges in each dimension.
 916   int num_y_edges = 2;
 917   int num_x_edges = 2;
 918
 919   // Create an event list.
 920   EdgeEvent events[] = {
 921     { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
 922     { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
 923     { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
 924     { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
 925   };
 926
 927   // Sort the events by distance (closest first).
 928   if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
 929   if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
 930   if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
 931   if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
 932   if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
 933
 934   for (int event_index = 0; event_index < 4; event_index++) {
 935     const EdgeEvent& event = events[event_index];
 936
 937     int delta = ComputeExpansionDelta(
 938         num_x_edges, num_y_edges, width, height, target_area);
 939
 940     // Clamp delta to our event distance.
 941     if (delta > event.distance)
 942       delta = event.distance;
 943
 944     // Adjust the edge count for this kind of edge.
 945     --*event.num_edges;
 946
 947     // Apply the delta to the edges and edge events.
 948     for (int i = event_index; i < 4; i++) {
 949       switch (events[i].edge) {
 950         case EdgeEvent::BOTTOM:
 951             origin_y -= delta;
 952             height += delta;
 953             break;
 954         case EdgeEvent::TOP:
 955             height += delta;
 956             break;
 957         case EdgeEvent::LEFT:
 958             origin_x -= delta;
 959             width += delta;
 960             break;
 961         case EdgeEvent::RIGHT:
 962             width += delta;
 963             break;
 964       }
 965       events[i].distance -= delta;
 966     }
 967
 968     // If our delta is less then our event distance, we're done.
 969     if (delta < event.distance)
 970       break;
 971   }
 972
 973   gfx::Rect result(origin_x, origin_y, width, height);
 974   if (cache)
 975     cache->previous_result = result;
 976   return result;
 977 }
 978
 979 void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
 980     TreePriority tree_priority) {
 981   if (eviction_tiles_cache_valid_ &&
 982       eviction_cache_tree_priority_ == tree_priority)
 983     return;
 984
 985   eviction_tiles_now_.clear();
 986   eviction_tiles_now_and_required_for_activation_.clear();
 987   eviction_tiles_soon_.clear();
 988   eviction_tiles_soon_and_required_for_activation_.clear();
 989   eviction_tiles_eventually_.clear();
 990   eviction_tiles_eventually_and_required_for_activation_.clear();
 991
 992   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 993     Tile* tile = it->second.get();
 994     UpdateTileAndTwinPriority(tile);
 995     const TilePriority& priority =
 996         tile->priority_for_tree_priority(tree_priority);
 997     switch (priority.priority_bin) {
 998       case TilePriority::EVENTUALLY:
 999         if (tile->required_for_activation())
1000           eviction_tiles_eventually_and_required_for_activation_.push_back(
1001               tile);
1002         else
1003           eviction_tiles_eventually_.push_back(tile);
1004         break;
1005       case TilePriority::SOON:
1006         if (tile->required_for_activation())
1007           eviction_tiles_soon_and_required_for_activation_.push_back(tile);
1008         else
1009           eviction_tiles_soon_.push_back(tile);
1010         break;
1011       case TilePriority::NOW:
1012         if (tile->required_for_activation())
1013           eviction_tiles_now_and_required_for_activation_.push_back(tile);
1014         else
1015           eviction_tiles_now_.push_back(tile);
1016         break;
1017     }
1018   }
1019
1020   // TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that
1021   // can be updated for each of the queues.
1022   TileEvictionOrder sort_order(tree_priority);
1023   std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order);
1024   std::sort(eviction_tiles_now_and_required_for_activation_.begin(),
1025             eviction_tiles_now_and_required_for_activation_.end(),
1026             sort_order);
1027   std::sort(
1028       eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order);
1029   std::sort(eviction_tiles_soon_and_required_for_activation_.begin(),
1030             eviction_tiles_soon_and_required_for_activation_.end(),
1031             sort_order);
1032   std::sort(eviction_tiles_eventually_.begin(),
1033             eviction_tiles_eventually_.end(),
1034             sort_order);
1035   std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(),
1036             eviction_tiles_eventually_and_required_for_activation_.end(),
1037             sort_order);
1038
1039   eviction_tiles_cache_valid_ = true;
1040   eviction_cache_tree_priority_ = tree_priority;
1041 }
1042
1043 const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles(
1044     TreePriority tree_priority,
1045     EvictionCategory category) {
1046   UpdateEvictionCacheIfNeeded(tree_priority);
1047   switch (category) {
1048     case EVENTUALLY:
1049       return &eviction_tiles_eventually_;
1050     case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
1051       return &eviction_tiles_eventually_and_required_for_activation_;
1052     case SOON:
1053       return &eviction_tiles_soon_;
1054     case SOON_AND_REQUIRED_FOR_ACTIVATION:
1055       return &eviction_tiles_soon_and_required_for_activation_;
1056     case NOW:
1057       return &eviction_tiles_now_;
1058     case NOW_AND_REQUIRED_FOR_ACTIVATION:
1059       return &eviction_tiles_now_and_required_for_activation_;
1060   }
1061   NOTREACHED();
1062   return &eviction_tiles_eventually_;
1063 }
1064
1065 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
1066     : tiling_(NULL), current_tile_(NULL) {}
1067
1068 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
1069     PictureLayerTiling* tiling)
1070     : tiling_(tiling), phase_(VISIBLE_RECT), current_tile_(NULL) {
1071   if (!tiling_->has_visible_rect_tiles_) {
1072     AdvancePhase();
1073     return;
1074   }
1075
1076   visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
1077                                            tiling_->current_visible_rect_,
1078                                            false /* include_borders */);
1079   if (!visible_iterator_) {
1080     AdvancePhase();
1081     return;
1082   }
1083
1084   current_tile_ =
1085       tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y());
1086   if (!current_tile_ || !TileNeedsRaster(current_tile_)) {
1087     ++(*this);
1088     return;
1089   }
1090   tiling_->UpdateTileAndTwinPriority(current_tile_);
1091 }
1092
1093 PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
1094
1095 void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() {
1096   DCHECK_LT(phase_, EVENTUALLY_RECT);
1097
1098   do {
1099     phase_ = static_cast<Phase>(phase_ + 1);
1100     switch (phase_) {
1101       case VISIBLE_RECT:
1102         NOTREACHED();
1103         return;
1104       case SKEWPORT_RECT:
1105         if (!tiling_->has_skewport_rect_tiles_)
1106           continue;
1107
1108         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
1109             &tiling_->tiling_data_,
1110             tiling_->current_skewport_rect_,
1111             tiling_->current_visible_rect_,
1112             tiling_->current_visible_rect_);
1113         break;
1114       case SOON_BORDER_RECT:
1115         if (!tiling_->has_soon_border_rect_tiles_)
1116           continue;
1117
1118         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
1119             &tiling_->tiling_data_,
1120             tiling_->current_soon_border_rect_,
1121             tiling_->current_skewport_rect_,
1122             tiling_->current_visible_rect_);
1123         break;
1124       case EVENTUALLY_RECT:
1125         if (!tiling_->has_eventually_rect_tiles_) {
1126           current_tile_ = NULL;
1127           return;
1128         }
1129
1130         spiral_iterator_ = TilingData::SpiralDifferenceIterator(
1131             &tiling_->tiling_data_,
1132             tiling_->current_eventually_rect_,
1133             tiling_->current_skewport_rect_,
1134             tiling_->current_soon_border_rect_);
1135         break;
1136     }
1137
1138     while (spiral_iterator_) {
1139       current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(),
1140                                       spiral_iterator_.index_y());
1141       if (current_tile_ && TileNeedsRaster(current_tile_))
1142         break;
1143       ++spiral_iterator_;
1144     }
1145
1146     if (!spiral_iterator_ && phase_ == EVENTUALLY_RECT) {
1147       current_tile_ = NULL;
1148       break;
1149     }
1150   } while (!spiral_iterator_);
1151
1152   if (current_tile_)
1153     tiling_->UpdateTileAndTwinPriority(current_tile_);
1154 }
1155
1156 PictureLayerTiling::TilingRasterTileIterator&
1157 PictureLayerTiling::TilingRasterTileIterator::
1158 operator++() {
1159   current_tile_ = NULL;
1160   while (!current_tile_ || !TileNeedsRaster(current_tile_)) {
1161     std::pair<int, int> next_index;
1162     switch (phase_) {
1163       case VISIBLE_RECT:
1164         ++visible_iterator_;
1165         if (!visible_iterator_) {
1166           AdvancePhase();
1167           return *this;
1168         }
1169         next_index = visible_iterator_.index();
1170         break;
1171       case SKEWPORT_RECT:
1172       case SOON_BORDER_RECT:
1173         ++spiral_iterator_;
1174         if (!spiral_iterator_) {
1175           AdvancePhase();
1176           return *this;
1177         }
1178         next_index = spiral_iterator_.index();
1179         break;
1180       case EVENTUALLY_RECT:
1181         ++spiral_iterator_;
1182         if (!spiral_iterator_) {
1183           current_tile_ = NULL;
1184           return *this;
1185         }
1186         next_index = spiral_iterator_.index();
1187         break;
1188     }
1189     current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
1190   }
1191
1192   if (current_tile_)
1193     tiling_->UpdateTileAndTwinPriority(current_tile_);
1194   return *this;
1195 }
1196
1197 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
1198     : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
1199 }
1200
1201 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
1202     PictureLayerTiling* tiling,
1203     TreePriority tree_priority,
1204     EvictionCategory category)
1205     : eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)),
1206       // Note: initializing to "0 - 1" works as overflow is well defined for
1207       // unsigned integers.
1208       current_eviction_tiles_index_(static_cast<size_t>(0) - 1) {
1209   DCHECK(eviction_tiles_);
1210   ++(*this);
1211 }
1212
1213 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
1214 }
1215
1216 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
1217   return eviction_tiles_ &&
1218          current_eviction_tiles_index_ != eviction_tiles_->size();
1219 }
1220
1221 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
1222   DCHECK(*this);
1223   return (*eviction_tiles_)[current_eviction_tiles_index_];
1224 }
1225
1226 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
1227   DCHECK(*this);
1228   return (*eviction_tiles_)[current_eviction_tiles_index_];
1229 }
1230
1231 PictureLayerTiling::TilingEvictionTileIterator&
1232 PictureLayerTiling::TilingEvictionTileIterator::
1233 operator++() {
1234   DCHECK(*this);
1235   do {
1236     ++current_eviction_tiles_index_;
1237   } while (current_eviction_tiles_index_ != eviction_tiles_->size() &&
1238            !(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources());
1239
1240   return *this;
1241 }
1242
1243 }  // namespace cc