cc/tiles/picture_layer_tiling_set.cc

   1 // Copyright 2012 The Chromium Authors
   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/tiles/picture_layer_tiling_set.h"
   6
   7 #include <stddef.h>
   8
   9 #include <algorithm>
  10 #include <limits>
  11 #include <memory>
  12 #include <set>
  13 #include <utility>
  14 #include <vector>
  15
  16 #include "base/containers/contains.h"
  17 #include "base/containers/cxx20_erase.h"
  18 #include "base/memory/ptr_util.h"
  19 #include "base/ranges/algorithm.h"
  20 #include "base/trace_event/trace_event.h"
  21 #include "cc/raster/raster_source.h"
  22 #include "ui/gfx/geometry/rect_conversions.h"
  23
  24 namespace cc {
  25
  26 namespace {
  27
  28 class LargestToSmallestScaleFunctor {
  29  public:
  30   bool operator()(const std::unique_ptr<PictureLayerTiling>& left,
  31                   const std::unique_ptr<PictureLayerTiling>& right) {
  32     return left->contents_scale_key() > right->contents_scale_key();
  33   }
  34 };
  35
  36 inline float LargerRatio(float float1, float float2) {
  37   DCHECK_GT(float1, 0.f);
  38   DCHECK_GT(float2, 0.f);
  39   return float1 > float2 ? float1 / float2 : float2 / float1;
  40 }
  41
  42 const float kSoonBorderDistanceViewportPercentage = 0.15f;
  43 const float kMaxSoonBorderDistanceInScreenPixels = 312.f;
  44
  45 }  // namespace
  46
  47 // static
  48 std::unique_ptr<PictureLayerTilingSet> PictureLayerTilingSet::Create(
  49     WhichTree tree,
  50     PictureLayerTilingClient* client,
  51     int tiling_interest_area_padding,
  52     float skewport_target_time_in_seconds,
  53     int skewport_extrapolation_limit_in_screen_pixels,
  54     float max_preraster_distance) {
  55   return base::WrapUnique(new PictureLayerTilingSet(
  56       tree, client, tiling_interest_area_padding,
  57       skewport_target_time_in_seconds,
  58       skewport_extrapolation_limit_in_screen_pixels, max_preraster_distance));
  59 }
  60
  61 PictureLayerTilingSet::PictureLayerTilingSet(
  62     WhichTree tree,
  63     PictureLayerTilingClient* client,
  64     int tiling_interest_area_padding,
  65     float skewport_target_time_in_seconds,
  66     int skewport_extrapolation_limit_in_screen_pixels,
  67     float max_preraster_distance)
  68     : tiling_interest_area_padding_(tiling_interest_area_padding),
  69       skewport_target_time_in_seconds_(skewport_target_time_in_seconds),
  70       skewport_extrapolation_limit_in_screen_pixels_(
  71           skewport_extrapolation_limit_in_screen_pixels),
  72       tree_(tree),
  73       client_(client),
  74       max_preraster_distance_(max_preraster_distance) {}
  75
  76 PictureLayerTilingSet::~PictureLayerTilingSet() = default;
  77
  78 void PictureLayerTilingSet::CopyTilingsAndPropertiesFromPendingTwin(
  79     const PictureLayerTilingSet* pending_twin_set,
  80     scoped_refptr<RasterSource> raster_source,
  81     const Region& layer_invalidation) {
  82   if (pending_twin_set->tilings_.empty()) {
  83     // If the twin (pending) tiling set is empty, it was not updated for the
  84     // current frame. So we drop tilings from our set as well, instead of
  85     // leaving behind unshared tilings that are all non-ideal.
  86     RemoveAllTilings();
  87     return;
  88   }
  89
  90   bool tiling_sort_required = false;
  91   for (const auto& pending_twin_tiling : pending_twin_set->tilings_) {
  92     gfx::AxisTransform2d raster_transform =
  93         pending_twin_tiling->raster_transform();
  94     bool can_use_lcd_text = pending_twin_tiling->can_use_lcd_text();
  95     PictureLayerTiling* this_tiling =
  96         FindTilingWithScaleKey(pending_twin_tiling->contents_scale_key());
  97     if (this_tiling && (this_tiling->raster_transform() != raster_transform ||
  98                         this_tiling->can_use_lcd_text() != can_use_lcd_text)) {
  99       Remove(this_tiling);
 100       this_tiling = nullptr;
 101     }
 102     if (!this_tiling) {
 103       std::unique_ptr<PictureLayerTiling> new_tiling(
 104           new PictureLayerTiling(tree_, raster_transform, raster_source_,
 105                                  client_, kMaxSoonBorderDistanceInScreenPixels,
 106                                  max_preraster_distance_, can_use_lcd_text));
 107       tilings_.push_back(std::move(new_tiling));
 108       this_tiling = tilings_.back().get();
 109       tiling_sort_required = true;
 110       state_since_last_tile_priority_update_.added_tilings = true;
 111     }
 112     this_tiling->TakeTilesAndPropertiesFrom(pending_twin_tiling.get(),
 113                                             layer_invalidation);
 114   }
 115
 116   if (tiling_sort_required) {
 117     std::sort(tilings_.begin(), tilings_.end(),
 118               LargestToSmallestScaleFunctor());
 119   }
 120 }
 121
 122 void PictureLayerTilingSet::UpdateTilingsToCurrentRasterSourceForActivation(
 123     scoped_refptr<RasterSource> raster_source,
 124     const PictureLayerTilingSet* pending_twin_set,
 125     const Region& layer_invalidation,
 126     float minimum_contents_scale,
 127     float maximum_contents_scale) {
 128   RemoveTilingsBelowScaleKey(minimum_contents_scale);
 129   RemoveTilingsAboveScaleKey(maximum_contents_scale);
 130
 131   raster_source_ = raster_source;
 132
 133   // Copy over tilings that are shared with the |pending_twin_set| tiling set.
 134   // Also, copy all of the properties from twin tilings.
 135   CopyTilingsAndPropertiesFromPendingTwin(pending_twin_set, raster_source,
 136                                           layer_invalidation);
 137
 138   // If the tiling is not shared (FindTilingWithScale returns nullptr), then
 139   // invalidate tiles and update them to the new raster source.
 140   for (const auto& tiling : tilings_) {
 141     if (pending_twin_set->FindTilingWithScaleKey(tiling->contents_scale_key()))
 142       continue;
 143
 144     tiling->SetRasterSourceAndResize(raster_source);
 145     tiling->Invalidate(layer_invalidation);
 146     state_since_last_tile_priority_update_.invalidated = true;
 147     // This is needed for cases where the live tiles rect didn't change but
 148     // recordings exist in the raster source that did not exist on the last
 149     // raster source.
 150     tiling->CreateMissingTilesInLiveTilesRect();
 151
 152     // |this| is active set and |tiling| is not in the pending set, which means
 153     // it is now NON_IDEAL_RESOLUTION. The exception is for LOW_RESOLUTION
 154     // tilings, which are computed and created entirely on the active tree.
 155     // Since the pending tree does not have them, we should just leave them as
 156     // low resolution to not lose them.
 157     if (tiling->resolution() != LOW_RESOLUTION)
 158       tiling->set_resolution(NON_IDEAL_RESOLUTION);
 159   }
 160
 161   VerifyTilings(pending_twin_set);
 162 }
 163
 164 void PictureLayerTilingSet::UpdateTilingsToCurrentRasterSourceForCommit(
 165     scoped_refptr<RasterSource> raster_source,
 166     const Region& layer_invalidation,
 167     float minimum_contents_scale,
 168     float maximum_contents_scale) {
 169   RemoveTilingsBelowScaleKey(minimum_contents_scale);
 170   RemoveTilingsAboveScaleKey(maximum_contents_scale);
 171
 172   raster_source_ = raster_source;
 173
 174   // Invalidate tiles and update them to the new raster source.
 175   for (const std::unique_ptr<PictureLayerTiling>& tiling : tilings_) {
 176     DCHECK(tree_ != PENDING_TREE || !tiling->has_tiles());
 177     tiling->SetRasterSourceAndResize(raster_source);
 178
 179     // Force |UpdateTilePriorities| on commit for cases where the compositor is
 180     // heavily pipelined resulting in back to back draw and commit. This
 181     // prevents the early out from |UpdateTilePriorities| because frame time
 182     // didn't change. That in turn causes an early out from PrepareTiles which
 183     // can cause checkerboarding.
 184     state_since_last_tile_priority_update_.invalidated = true;
 185
 186     // We can commit on either active or pending trees, but only active one can
 187     // have tiles at this point.
 188     if (tree_ == ACTIVE_TREE)
 189       tiling->Invalidate(layer_invalidation);
 190
 191     // This is needed for cases where the live tiles rect didn't change but
 192     // recordings exist in the raster source that did not exist on the last
 193     // raster source.
 194     tiling->CreateMissingTilesInLiveTilesRect();
 195   }
 196   VerifyTilings(nullptr /* pending_twin_set */);
 197 }
 198
 199 void PictureLayerTilingSet::Invalidate(const Region& layer_invalidation) {
 200   for (const auto& tiling : tilings_) {
 201     tiling->Invalidate(layer_invalidation);
 202     tiling->CreateMissingTilesInLiveTilesRect();
 203   }
 204   state_since_last_tile_priority_update_.invalidated = true;
 205 }
 206
 207 void PictureLayerTilingSet::VerifyTilings(
 208     const PictureLayerTilingSet* pending_twin_set) const {
 209 #if DCHECK_IS_ON()
 210   for (const auto& tiling : tilings_) {
 211     DCHECK(tiling->tile_size() ==
 212            client_->CalculateTileSize(tiling->tiling_size()))
 213         << "tile_size: " << tiling->tile_size().ToString()
 214         << " tiling_size: " << tiling->tiling_size().ToString()
 215         << " CalculateTileSize: "
 216         << client_->CalculateTileSize(tiling->tiling_size()).ToString();
 217   }
 218
 219   if (!tilings_.empty()) {
 220     DCHECK_LE(NumHighResTilings(), 1);
 221     // When commiting from the main thread the high res tiling may get dropped,
 222     // but when cloning to the active tree, there should always be one.
 223     if (pending_twin_set) {
 224       DCHECK_EQ(1, NumHighResTilings())
 225           << " num tilings on active: " << tilings_.size()
 226           << " num tilings on pending: " << pending_twin_set->tilings_.size()
 227           << " num high res on pending: "
 228           << pending_twin_set->NumHighResTilings()
 229           << " are on active tree: " << (tree_ == ACTIVE_TREE);
 230     }
 231   }
 232 #endif
 233 }
 234
 235 void PictureLayerTilingSet::CleanUpTilings(
 236     float min_acceptable_high_res_scale_key,
 237     float max_acceptable_high_res_scale_key,
 238     const std::vector<PictureLayerTiling*>& needed_tilings,
 239     PictureLayerTilingSet* twin_set) {
 240   std::vector<PictureLayerTiling*> to_remove;
 241   for (const auto& tiling : tilings_) {
 242     // Keep all tilings within the min/max scales.
 243     if (tiling->contents_scale_key() >= min_acceptable_high_res_scale_key &&
 244         tiling->contents_scale_key() <= max_acceptable_high_res_scale_key) {
 245       continue;
 246     }
 247
 248     // Keep low resolution tilings.
 249     if (tiling->resolution() == LOW_RESOLUTION)
 250       continue;
 251
 252     // Don't remove tilings that are required.
 253     if (base::Contains(needed_tilings, tiling.get())) {
 254       continue;
 255     }
 256
 257     to_remove.push_back(tiling.get());
 258   }
 259
 260   for (auto* tiling : to_remove) {
 261     DCHECK_NE(HIGH_RESOLUTION, tiling->resolution());
 262     Remove(tiling);
 263   }
 264 }
 265
 266 void PictureLayerTilingSet::RemoveNonIdealTilings() {
 267   base::EraseIf(tilings_, [](const std::unique_ptr<PictureLayerTiling>& t) {
 268     return t->resolution() == NON_IDEAL_RESOLUTION;
 269   });
 270 }
 271
 272 void PictureLayerTilingSet::MarkAllTilingsNonIdeal() {
 273   for (const auto& tiling : tilings_)
 274     tiling->set_resolution(NON_IDEAL_RESOLUTION);
 275 }
 276
 277 PictureLayerTiling* PictureLayerTilingSet::AddTiling(
 278     const gfx::AxisTransform2d& raster_transform,
 279     scoped_refptr<RasterSource> raster_source,
 280     bool can_use_lcd_text) {
 281   if (!raster_source_)
 282     raster_source_ = raster_source;
 283
 284 #if DCHECK_IS_ON()
 285   for (const auto& tiling : tilings_) {
 286     const gfx::Vector2dF& scale = raster_transform.scale();
 287     DCHECK_NE(tiling->contents_scale_key(), std::max(scale.x(), scale.y()));
 288     DCHECK_EQ(tiling->raster_source(), raster_source.get());
 289   }
 290 #endif  // DCHECK_IS_ON()
 291
 292   tilings_.push_back(std::make_unique<PictureLayerTiling>(
 293       tree_, raster_transform, raster_source, client_,
 294       kMaxSoonBorderDistanceInScreenPixels, max_preraster_distance_,
 295       can_use_lcd_text));
 296   PictureLayerTiling* appended = tilings_.back().get();
 297   state_since_last_tile_priority_update_.added_tilings = true;
 298
 299   std::sort(tilings_.begin(), tilings_.end(), LargestToSmallestScaleFunctor());
 300   return appended;
 301 }
 302
 303 int PictureLayerTilingSet::NumHighResTilings() const {
 304   return std::count_if(tilings_.begin(), tilings_.end(),
 305                        [](const std::unique_ptr<PictureLayerTiling>& tiling) {
 306                          return tiling->resolution() == HIGH_RESOLUTION;
 307                        });
 308 }
 309
 310 PictureLayerTiling* PictureLayerTilingSet::FindTilingWithScaleKey(
 311     float scale_key) const {
 312   for (const auto& tiling : tilings_) {
 313     if (tiling->contents_scale_key() == scale_key)
 314       return tiling.get();
 315   }
 316   return nullptr;
 317 }
 318
 319 PictureLayerTiling* PictureLayerTilingSet::FindTilingWithResolution(
 320     TileResolution resolution) const {
 321   auto iter =
 322       base::ranges::find(tilings_, resolution, &PictureLayerTiling::resolution);
 323   if (iter == tilings_.end())
 324     return nullptr;
 325   return iter->get();
 326 }
 327
 328 PictureLayerTiling* PictureLayerTilingSet::FindTilingWithNearestScaleKey(
 329     float start_scale,
 330     float snap_to_existing_tiling_ratio) const {
 331   PictureLayerTiling* nearest_tiling = nullptr;
 332   float nearest_ratio = snap_to_existing_tiling_ratio;
 333   for (const auto& tiling : tilings_) {
 334     float tiling_contents_scale = tiling->contents_scale_key();
 335     float ratio = LargerRatio(tiling_contents_scale, start_scale);
 336     if (ratio <= nearest_ratio) {
 337       nearest_tiling = tiling.get();
 338       nearest_ratio = ratio;
 339     }
 340   }
 341   return nearest_tiling;
 342 }
 343
 344 void PictureLayerTilingSet::RemoveTilingsBelowScaleKey(
 345     float minimum_scale_key) {
 346   base::EraseIf(
 347       tilings_,
 348       [minimum_scale_key](const std::unique_ptr<PictureLayerTiling>& tiling) {
 349         return tiling->contents_scale_key() < minimum_scale_key;
 350       });
 351 }
 352
 353 void PictureLayerTilingSet::RemoveTilingsAboveScaleKey(
 354     float maximum_scale_key) {
 355   base::EraseIf(
 356       tilings_,
 357       [maximum_scale_key](const std::unique_ptr<PictureLayerTiling>& tiling) {
 358         return tiling->contents_scale_key() > maximum_scale_key;
 359       });
 360 }
 361
 362 void PictureLayerTilingSet::ReleaseAllResources() {
 363   RemoveAllTilings();
 364   raster_source_ = nullptr;
 365 }
 366
 367 void PictureLayerTilingSet::RemoveAllTilings() {
 368   tilings_.clear();
 369 }
 370
 371 void PictureLayerTilingSet::Remove(PictureLayerTiling* tiling) {
 372   auto iter = base::ranges::find(tilings_, tiling,
 373                                  &std::unique_ptr<PictureLayerTiling>::get);
 374   if (iter == tilings_.end())
 375     return;
 376   tilings_.erase(iter);
 377 }
 378
 379 void PictureLayerTilingSet::RemoveAllTiles() {
 380   for (const auto& tiling : tilings_)
 381     tiling->Reset();
 382 }
 383
 384 float PictureLayerTilingSet::GetMaximumContentsScale() const {
 385   if (tilings_.empty())
 386     return 0.f;
 387   // The first tiling has the largest contents scale.
 388   return tilings_[0]->contents_scale_key();
 389 }
 390
 391 bool PictureLayerTilingSet::TilingsNeedUpdate(
 392     const gfx::Rect& visible_rect_in_layer_space,
 393     double current_frame_time_in_seconds) {
 394   // If we don't have any tilings, we don't need an update.
 395   if (num_tilings() == 0)
 396     return false;
 397
 398   // If we never updated the tiling set, then our history is empty. We should
 399   // update tilings.
 400   if (visible_rect_history_.empty())
 401     return true;
 402
 403   // If we've added new tilings since the last update, then we have to update at
 404   // least that one tiling.
 405   if (state_since_last_tile_priority_update_.added_tilings)
 406     return true;
 407
 408   // Finally, if some state changed (either frame time or visible rect), then we
 409   // need to inform the tilings of the change.
 410   const auto& last_frame = visible_rect_history_.front();
 411   if (current_frame_time_in_seconds != last_frame.frame_time_in_seconds)
 412     return true;
 413
 414   if (visible_rect_in_layer_space != last_frame.visible_rect_in_layer_space)
 415     return true;
 416   return false;
 417 }
 418
 419 gfx::Rect PictureLayerTilingSet::ComputeSkewport(
 420     const gfx::Rect& visible_rect_in_layer_space,
 421     double current_frame_time_in_seconds,
 422     float ideal_contents_scale) {
 423   gfx::Rect skewport = visible_rect_in_layer_space;
 424   if (skewport.IsEmpty() || visible_rect_history_.empty())
 425     return skewport;
 426
 427   // Use the oldest recorded history to get a stable skewport.
 428   const auto& historical_frame = visible_rect_history_.back();
 429   double time_delta =
 430       current_frame_time_in_seconds - historical_frame.frame_time_in_seconds;
 431   if (time_delta == 0.)
 432     return skewport;
 433
 434   double extrapolation_multiplier =
 435       skewport_target_time_in_seconds_ / time_delta;
 436   int old_x = historical_frame.visible_rect_in_layer_space.x();
 437   int old_y = historical_frame.visible_rect_in_layer_space.y();
 438   int old_right = historical_frame.visible_rect_in_layer_space.right();
 439   int old_bottom = historical_frame.visible_rect_in_layer_space.bottom();
 440
 441   int new_x = visible_rect_in_layer_space.x();
 442   int new_y = visible_rect_in_layer_space.y();
 443   int new_right = visible_rect_in_layer_space.right();
 444   int new_bottom = visible_rect_in_layer_space.bottom();
 445
 446   int inset_x = (new_x - old_x) * extrapolation_multiplier;
 447   int inset_y = (new_y - old_y) * extrapolation_multiplier;
 448   int inset_right = (old_right - new_right) * extrapolation_multiplier;
 449   int inset_bottom = (old_bottom - new_bottom) * extrapolation_multiplier;
 450
 451   int skewport_extrapolation_limit_in_layer_pixels =
 452       skewport_extrapolation_limit_in_screen_pixels_ / ideal_contents_scale;
 453   gfx::Rect max_skewport = skewport;
 454   max_skewport.Inset(-skewport_extrapolation_limit_in_layer_pixels);
 455
 456   skewport.Inset(
 457       gfx::Insets::TLBR(inset_y, inset_x, inset_bottom, inset_right));
 458   skewport.Union(visible_rect_in_layer_space);
 459   skewport.Intersect(max_skewport);
 460
 461   // Due to limits in int's representation, it is possible that the two
 462   // operations above (union and intersect) result in an empty skewport. To
 463   // avoid any unpleasant situations like that, union the visible rect again to
 464   // ensure that skewport.Contains(visible_rect_in_layer_space) is always
 465   // true.
 466   skewport.Union(visible_rect_in_layer_space);
 467   skewport.Intersect(eventually_rect_in_layer_space_);
 468   return skewport;
 469 }
 470
 471 gfx::Rect PictureLayerTilingSet::ComputeSoonBorderRect(
 472     const gfx::Rect& visible_rect,
 473     float ideal_contents_scale) {
 474   int max_dimension = std::max(visible_rect.width(), visible_rect.height());
 475   int distance =
 476       std::min<int>(kMaxSoonBorderDistanceInScreenPixels * ideal_contents_scale,
 477                     max_dimension * kSoonBorderDistanceViewportPercentage);
 478
 479   gfx::Rect soon_border_rect = visible_rect;
 480   soon_border_rect.Inset(-distance);
 481   soon_border_rect.Intersect(eventually_rect_in_layer_space_);
 482   return soon_border_rect;
 483 }
 484
 485 void PictureLayerTilingSet::UpdatePriorityRects(
 486     const gfx::Rect& visible_rect_in_layer_space,
 487     double current_frame_time_in_seconds,
 488     float ideal_contents_scale) {
 489   visible_rect_in_layer_space_ = gfx::Rect();
 490   eventually_rect_in_layer_space_ = gfx::Rect();
 491
 492   // We keep things as floats in here.
 493   if (!visible_rect_in_layer_space.IsEmpty()) {
 494     gfx::RectF eventually_rectf(visible_rect_in_layer_space);
 495     eventually_rectf.Inset(-tiling_interest_area_padding_ /
 496                            ideal_contents_scale);
 497     if (eventually_rectf.Intersects(
 498             gfx::RectF(gfx::SizeF(raster_source_->GetSize())))) {
 499       visible_rect_in_layer_space_ = visible_rect_in_layer_space;
 500       eventually_rect_in_layer_space_ = gfx::ToEnclosingRect(eventually_rectf);
 501     }
 502   }
 503
 504   skewport_in_layer_space_ =
 505       ComputeSkewport(visible_rect_in_layer_space_,
 506                       current_frame_time_in_seconds, ideal_contents_scale);
 507   DCHECK(skewport_in_layer_space_.Contains(visible_rect_in_layer_space_));
 508   DCHECK(eventually_rect_in_layer_space_.Contains(skewport_in_layer_space_));
 509
 510   soon_border_rect_in_layer_space_ =
 511       ComputeSoonBorderRect(visible_rect_in_layer_space_, ideal_contents_scale);
 512   DCHECK(
 513       soon_border_rect_in_layer_space_.Contains(visible_rect_in_layer_space_));
 514   DCHECK(eventually_rect_in_layer_space_.Contains(
 515       soon_border_rect_in_layer_space_));
 516
 517   // Finally, update our visible rect history. Note that we use the original
 518   // visible rect here, since we want as accurate of a history as possible for
 519   // stable skewports.
 520   if (visible_rect_history_.size() == 2)
 521     visible_rect_history_.pop_back();
 522   visible_rect_history_.push_front(FrameVisibleRect(
 523       visible_rect_in_layer_space_, current_frame_time_in_seconds));
 524 }
 525
 526 bool PictureLayerTilingSet::UpdateTilePriorities(
 527     const gfx::Rect& visible_rect_in_layer_space,
 528     float ideal_contents_scale,
 529     double current_frame_time_in_seconds,
 530     const Occlusion& occlusion_in_layer_space,
 531     bool can_require_tiles_for_activation) {
 532   StateSinceLastTilePriorityUpdate::AutoClear auto_clear_state(
 533       &state_since_last_tile_priority_update_);
 534
 535   if (!TilingsNeedUpdate(visible_rect_in_layer_space,
 536                          current_frame_time_in_seconds)) {
 537     return state_since_last_tile_priority_update_.invalidated;
 538   }
 539
 540   UpdatePriorityRects(visible_rect_in_layer_space,
 541                       current_frame_time_in_seconds, ideal_contents_scale);
 542
 543   for (const auto& tiling : tilings_) {
 544     tiling->set_can_require_tiles_for_activation(
 545         can_require_tiles_for_activation);
 546     tiling->ComputeTilePriorityRects(
 547         visible_rect_in_layer_space_, skewport_in_layer_space_,
 548         soon_border_rect_in_layer_space_, eventually_rect_in_layer_space_,
 549         ideal_contents_scale, occlusion_in_layer_space);
 550   }
 551   return true;
 552 }
 553
 554 void PictureLayerTilingSet::GetAllPrioritizedTilesForTracing(
 555     std::vector<PrioritizedTile>* prioritized_tiles) const {
 556   for (const auto& tiling : tilings_)
 557     tiling->GetAllPrioritizedTilesForTracing(prioritized_tiles);
 558 }
 559
 560 PictureLayerTilingSet::CoverageIterator::CoverageIterator(
 561     const PictureLayerTilingSet* set,
 562     float coverage_scale,
 563     const gfx::Rect& coverage_rect,
 564     float ideal_contents_scale)
 565     : set_(set),
 566       coverage_scale_(coverage_scale),
 567       current_tiling_(std::numeric_limits<size_t>::max()) {
 568   missing_region_.Union(coverage_rect);
 569
 570   // Determine the smallest content_scale tiling which a scale higher than the
 571   // ideal (or the first tiling if all tilings have a scale less than ideal).
 572   size_t tilings_size = set_->tilings_.size();
 573   for (ideal_tiling_ = 0; ideal_tiling_ < tilings_size; ++ideal_tiling_) {
 574     PictureLayerTiling* tiling = set_->tilings_[ideal_tiling_].get();
 575     if (tiling->contents_scale_key() < ideal_contents_scale) {
 576       if (ideal_tiling_ > 0)
 577         ideal_tiling_--;
 578       break;
 579     }
 580   }
 581
 582   // If all tilings have a scale larger than the ideal, then use the smallest
 583   // scale (which is the last one).
 584   if (ideal_tiling_ == tilings_size && ideal_tiling_ > 0)
 585     ideal_tiling_--;
 586
 587   ++(*this);
 588 }
 589
 590 PictureLayerTilingSet::CoverageIterator::~CoverageIterator() = default;
 591
 592 gfx::Rect PictureLayerTilingSet::CoverageIterator::geometry_rect() const {
 593   // If we don't have any more tilings to process, then return the region
 594   // iterator rect that we need to fill, so that the caller can checkerboard it.
 595   if (!tiling_iter_) {
 596     if (region_iter_ == current_region_.end())
 597       return gfx::Rect();
 598     return *region_iter_;
 599   }
 600   return tiling_iter_.geometry_rect();
 601 }
 602
 603 gfx::RectF PictureLayerTilingSet::CoverageIterator::texture_rect() const {
 604   // Texture rects are only valid if we have a tiling.
 605   if (!tiling_iter_)
 606     return gfx::RectF();
 607   return tiling_iter_.texture_rect();
 608 }
 609
 610 Tile* PictureLayerTilingSet::CoverageIterator::operator->() const {
 611   if (!tiling_iter_)
 612     return nullptr;
 613   return *tiling_iter_;
 614 }
 615
 616 Tile* PictureLayerTilingSet::CoverageIterator::operator*() const {
 617   if (!tiling_iter_)
 618     return nullptr;
 619   return *tiling_iter_;
 620 }
 621
 622 TileResolution PictureLayerTilingSet::CoverageIterator::resolution() const {
 623   const PictureLayerTiling* tiling = CurrentTiling();
 624   DCHECK(tiling);
 625   return tiling->resolution();
 626 }
 627
 628 PictureLayerTiling* PictureLayerTilingSet::CoverageIterator::CurrentTiling()
 629     const {
 630   if (current_tiling_ == std::numeric_limits<size_t>::max())
 631     return nullptr;
 632   if (current_tiling_ >= set_->tilings_.size())
 633     return nullptr;
 634   return set_->tilings_[current_tiling_].get();
 635 }
 636
 637 size_t PictureLayerTilingSet::CoverageIterator::NextTiling() const {
 638   // Order returned by this method is:
 639   // 1. Ideal tiling index
 640   // 2. Tiling index < Ideal in decreasing order (higher res than ideal)
 641   // 3. Tiling index > Ideal in increasing order (lower res than ideal)
 642   // 4. Tiling index > tilings.size() (invalid index)
 643   if (current_tiling_ == std::numeric_limits<size_t>::max())
 644     return ideal_tiling_;
 645   else if (current_tiling_ > ideal_tiling_)
 646     return current_tiling_ + 1;
 647   else if (current_tiling_)
 648     return current_tiling_ - 1;
 649   else
 650     return ideal_tiling_ + 1;
 651 }
 652
 653 PictureLayerTilingSet::CoverageIterator&
 654 PictureLayerTilingSet::CoverageIterator::operator++() {
 655   bool first_time = current_tiling_ == std::numeric_limits<size_t>::max();
 656
 657   if (!*this && !first_time)
 658     return *this;
 659
 660   if (tiling_iter_)
 661     ++tiling_iter_;
 662
 663   // Loop until we find a valid place to stop.
 664   while (true) {
 665     // While we don't have a ready to draw tile, accumulate the geometry rects
 666     // back into the missing region, which will be iterated after this tiling is
 667     // processed.
 668     while (tiling_iter_ &&
 669            (!*tiling_iter_ || !tiling_iter_->draw_info().IsReadyToDraw())) {
 670       missing_region_.Union(tiling_iter_.geometry_rect());
 671       ++tiling_iter_;
 672     }
 673     // We found a ready tile, yield it!
 674     if (tiling_iter_)
 675       return *this;
 676
 677     // If the set of current rects for this tiling is done, go to the next
 678     // tiling and set up to iterate through all of the remaining holes.
 679     // This will also happen the first time through the loop.
 680     if (region_iter_ == current_region_.end()) {
 681       current_tiling_ = NextTiling();
 682       current_region_.Swap(&missing_region_);
 683       missing_region_.Clear();
 684       region_iter_ = current_region_.begin();
 685
 686       // All done and all filled.
 687       if (region_iter_ == current_region_.end()) {
 688         current_tiling_ = set_->tilings_.size();
 689         return *this;
 690       }
 691
 692       // No more valid tiles, return this checkerboard rect.
 693       if (current_tiling_ >= set_->tilings_.size())
 694         return *this;
 695     }
 696
 697     // Pop a rect off.  If there are no more tilings, then these will be
 698     // treated as geometry with null tiles that the caller can checkerboard.
 699     gfx::Rect last_rect = *region_iter_;
 700     ++region_iter_;
 701
 702     // Done, found next checkerboard rect to return.
 703     if (current_tiling_ >= set_->tilings_.size())
 704       return *this;
 705
 706     // Construct a new iterator for the next tiling, but we need to loop
 707     // again until we get to a valid one.
 708     tiling_iter_ = PictureLayerTiling::CoverageIterator(
 709         set_->tilings_[current_tiling_].get(), coverage_scale_, last_rect);
 710   }
 711 }
 712
 713 PictureLayerTilingSet::CoverageIterator::operator bool() const {
 714   return current_tiling_ < set_->tilings_.size() ||
 715          region_iter_ != current_region_.end();
 716 }
 717
 718 void PictureLayerTilingSet::AsValueInto(
 719     base::trace_event::TracedValue* state) const {
 720   for (const auto& tiling : tilings_) {
 721     state->BeginDictionary();
 722     tiling->AsValueInto(state);
 723     state->EndDictionary();
 724   }
 725 }
 726
 727 size_t PictureLayerTilingSet::GPUMemoryUsageInBytes() const {
 728   size_t amount = 0;
 729   for (const auto& tiling : tilings_)
 730     amount += tiling->GPUMemoryUsageInBytes();
 731   return amount;
 732 }
 733
 734 PictureLayerTilingSet::TilingRange PictureLayerTilingSet::GetTilingRange(
 735     TilingRangeType type) const {
 736   // Doesn't seem to be the case right now but if it ever becomes a performance
 737   // problem to compute these ranges each time this function is called, we can
 738   // compute them only when the tiling set has changed instead.
 739   size_t tilings_size = tilings_.size();
 740   TilingRange high_res_range(0, 0);
 741   TilingRange low_res_range(tilings_size, tilings_size);
 742   for (size_t i = 0; i < tilings_size; ++i) {
 743     const PictureLayerTiling* tiling = tilings_[i].get();
 744     if (tiling->resolution() == HIGH_RESOLUTION)
 745       high_res_range = TilingRange(i, i + 1);
 746     if (tiling->resolution() == LOW_RESOLUTION)
 747       low_res_range = TilingRange(i, i + 1);
 748   }
 749
 750   TilingRange range(0, 0);
 751   switch (type) {
 752     case HIGHER_THAN_HIGH_RES:
 753       range = TilingRange(0, high_res_range.start);
 754       break;
 755     case HIGH_RES:
 756       range = high_res_range;
 757       break;
 758     case BETWEEN_HIGH_AND_LOW_RES:
 759       // TODO(vmpstr): This code assumes that high res tiling will come before
 760       // low res tiling, however there are cases where this assumption is
 761       // violated. As a result, it's better to be safe in these situations,
 762       // since otherwise we can end up accessing a tiling that doesn't exist.
 763       // See crbug.com/429397 for high res tiling appearing after low res
 764       // tiling discussion/fixes.
 765       if (high_res_range.start <= low_res_range.start)
 766         range = TilingRange(high_res_range.end, low_res_range.start);
 767       else
 768         range = TilingRange(low_res_range.end, high_res_range.start);
 769       break;
 770     case LOW_RES:
 771       range = low_res_range;
 772       break;
 773     case LOWER_THAN_LOW_RES:
 774       range = TilingRange(low_res_range.end, tilings_size);
 775       break;
 776   }
 777
 778   DCHECK_LE(range.start, range.end);
 779   return range;
 780 }
 781
 782 }  // namespace cc