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