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