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