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 "ui/gfx/point_conversions.h"
14#include "ui/gfx/rect_conversions.h"
15#include "ui/gfx/safe_integer_conversions.h"
16#include "ui/gfx/size_conversions.h"
17
18namespace cc {
19
20scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
21    float contents_scale,
22    gfx::Size layer_bounds,
23    PictureLayerTilingClient* client) {
24  return make_scoped_ptr(new PictureLayerTiling(contents_scale,
25                                                layer_bounds,
26                                                client));
27}
28
29PictureLayerTiling::PictureLayerTiling(float contents_scale,
30                                       gfx::Size layer_bounds,
31                                       PictureLayerTilingClient* client)
32    : contents_scale_(contents_scale),
33      layer_bounds_(layer_bounds),
34      resolution_(NON_IDEAL_RESOLUTION),
35      client_(client),
36      tiling_data_(gfx::Size(), gfx::Size(), true),
37      last_impl_frame_time_in_seconds_(0.0) {
38  gfx::Size content_bounds =
39      gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
40  gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
41
42  DCHECK(!gfx::ToFlooredSize(
43      gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
44      "Tiling created with scale too small as contents become empty." <<
45      " Layer bounds: " << layer_bounds.ToString() <<
46      " Contents scale: " << contents_scale;
47
48  tiling_data_.SetTotalSize(content_bounds);
49  tiling_data_.SetMaxTextureSize(tile_size);
50}
51
52PictureLayerTiling::~PictureLayerTiling() {
53}
54
55void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
56  client_ = client;
57}
58
59gfx::Rect PictureLayerTiling::ContentRect() const {
60  return gfx::Rect(tiling_data_.total_size());
61}
62
63gfx::SizeF PictureLayerTiling::ContentSizeF() const {
64  return gfx::ScaleSize(layer_bounds_, contents_scale_);
65}
66
67Tile* PictureLayerTiling::TileAt(int i, int j) const {
68  TileMap::const_iterator iter = tiles_.find(TileMapKey(i, j));
69  if (iter == tiles_.end())
70    return NULL;
71  return iter->second.get();
72}
73
74void PictureLayerTiling::CreateTile(int i,
75                                    int j,
76                                    const PictureLayerTiling* twin_tiling) {
77  TileMapKey key(i, j);
78  DCHECK(tiles_.find(key) == tiles_.end());
79
80  gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
81  gfx::Rect tile_rect = paint_rect;
82  tile_rect.set_size(tiling_data_.max_texture_size());
83
84  // Check our twin for a valid tile.
85  if (twin_tiling &&
86      tiling_data_.max_texture_size() ==
87      twin_tiling->tiling_data_.max_texture_size()) {
88    if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
89      gfx::Rect rect =
90          gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
91      if (!client_->GetInvalidation()->Intersects(rect)) {
92        tiles_[key] = candidate_tile;
93        return;
94      }
95    }
96  }
97
98  // Create a new tile because our twin didn't have a valid one.
99  scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
100  if (tile.get())
101    tiles_[key] = tile;
102}
103
104Region PictureLayerTiling::OpaqueRegionInContentRect(
105    gfx::Rect content_rect) const {
106  Region opaque_region;
107  // TODO(enne): implement me
108  return opaque_region;
109}
110
111void PictureLayerTiling::SetCanUseLCDText(bool can_use_lcd_text) {
112  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it)
113    it->second->set_can_use_lcd_text(can_use_lcd_text);
114}
115
116void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
117  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
118  bool include_borders = true;
119  for (TilingData::Iterator iter(
120           &tiling_data_, live_tiles_rect_, include_borders);
121       iter;
122       ++iter) {
123    TileMapKey key = iter.index();
124    TileMap::iterator find = tiles_.find(key);
125    if (find != tiles_.end())
126      continue;
127    CreateTile(key.first, key.second, twin_tiling);
128  }
129}
130
131void PictureLayerTiling::SetLayerBounds(gfx::Size layer_bounds) {
132  if (layer_bounds_ == layer_bounds)
133    return;
134
135  DCHECK(!layer_bounds.IsEmpty());
136
137  gfx::Size old_layer_bounds = layer_bounds_;
138  layer_bounds_ = layer_bounds;
139  gfx::Size old_content_bounds = tiling_data_.total_size();
140  gfx::Size content_bounds =
141      gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
142
143  gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
144  if (tile_size != tiling_data_.max_texture_size()) {
145    tiling_data_.SetTotalSize(content_bounds);
146    tiling_data_.SetMaxTextureSize(tile_size);
147    Reset();
148    return;
149  }
150
151  // Any tiles outside our new bounds are invalid and should be dropped.
152  gfx::Rect bounded_live_tiles_rect(live_tiles_rect_);
153  bounded_live_tiles_rect.Intersect(gfx::Rect(content_bounds));
154  SetLiveTilesRect(bounded_live_tiles_rect);
155  tiling_data_.SetTotalSize(content_bounds);
156
157  // Create tiles for newly exposed areas.
158  Region layer_region((gfx::Rect(layer_bounds_)));
159  layer_region.Subtract(gfx::Rect(old_layer_bounds));
160  Invalidate(layer_region);
161}
162
163void PictureLayerTiling::Invalidate(const Region& layer_region) {
164  std::vector<TileMapKey> new_tile_keys;
165  for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
166    gfx::Rect layer_rect = iter.rect();
167    gfx::Rect content_rect =
168        gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
169    content_rect.Intersect(live_tiles_rect_);
170    if (content_rect.IsEmpty())
171      continue;
172    bool include_borders = true;
173    for (TilingData::Iterator iter(
174             &tiling_data_, content_rect, include_borders);
175         iter;
176         ++iter) {
177      TileMapKey key(iter.index());
178      TileMap::iterator find = tiles_.find(key);
179      if (find == tiles_.end())
180        continue;
181      tiles_.erase(find);
182      new_tile_keys.push_back(key);
183    }
184  }
185
186  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
187  for (size_t i = 0; i < new_tile_keys.size(); ++i)
188    CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
189}
190
191PictureLayerTiling::CoverageIterator::CoverageIterator()
192    : tiling_(NULL),
193      current_tile_(NULL),
194      tile_i_(0),
195      tile_j_(0),
196      left_(0),
197      top_(0),
198      right_(-1),
199      bottom_(-1) {
200}
201
202PictureLayerTiling::CoverageIterator::CoverageIterator(
203    const PictureLayerTiling* tiling,
204    float dest_scale,
205    gfx::Rect dest_rect)
206    : tiling_(tiling),
207      dest_rect_(dest_rect),
208      dest_to_content_scale_(0),
209      current_tile_(NULL),
210      tile_i_(0),
211      tile_j_(0),
212      left_(0),
213      top_(0),
214      right_(-1),
215      bottom_(-1) {
216  DCHECK(tiling_);
217  if (dest_rect_.IsEmpty())
218    return;
219
220  dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
221  // This is the maximum size that the dest rect can be, given the content size.
222  gfx::Size dest_content_size = gfx::ToCeiledSize(gfx::ScaleSize(
223      tiling_->ContentRect().size(),
224      1 / dest_to_content_scale_,
225      1 / dest_to_content_scale_));
226
227  gfx::Rect content_rect =
228      gfx::ScaleToEnclosingRect(dest_rect_,
229                                dest_to_content_scale_,
230                                dest_to_content_scale_);
231  // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
232  // check for non-intersection first.
233  content_rect.Intersect(gfx::Rect(tiling_->tiling_data_.total_size()));
234  if (content_rect.IsEmpty())
235    return;
236
237  left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
238  top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
239  right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
240      content_rect.right() - 1);
241  bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
242      content_rect.bottom() - 1);
243
244  tile_i_ = left_ - 1;
245  tile_j_ = top_;
246  ++(*this);
247}
248
249PictureLayerTiling::CoverageIterator::~CoverageIterator() {
250}
251
252PictureLayerTiling::CoverageIterator&
253PictureLayerTiling::CoverageIterator::operator++() {
254  if (tile_j_ > bottom_)
255    return *this;
256
257  bool first_time = tile_i_ < left_;
258  bool new_row = false;
259  tile_i_++;
260  if (tile_i_ > right_) {
261    tile_i_ = left_;
262    tile_j_++;
263    new_row = true;
264    if (tile_j_ > bottom_) {
265      current_tile_ = NULL;
266      return *this;
267    }
268  }
269
270  current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
271
272  // Calculate the current geometry rect.  Due to floating point rounding
273  // and ToEnclosingRect, tiles might overlap in destination space on the
274  // edges.
275  gfx::Rect last_geometry_rect = current_geometry_rect_;
276
277  gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
278
279  current_geometry_rect_ =
280      gfx::ScaleToEnclosingRect(content_rect,
281                                1 / dest_to_content_scale_,
282                                1 / dest_to_content_scale_);
283
284  current_geometry_rect_.Intersect(dest_rect_);
285
286  if (first_time)
287    return *this;
288
289  // Iteration happens left->right, top->bottom.  Running off the bottom-right
290  // edge is handled by the intersection above with dest_rect_.  Here we make
291  // sure that the new current geometry rect doesn't overlap with the last.
292  int min_left;
293  int min_top;
294  if (new_row) {
295    min_left = dest_rect_.x();
296    min_top = last_geometry_rect.bottom();
297  } else {
298    min_left = last_geometry_rect.right();
299    min_top = last_geometry_rect.y();
300  }
301
302  int inset_left = std::max(0, min_left - current_geometry_rect_.x());
303  int inset_top = std::max(0, min_top - current_geometry_rect_.y());
304  current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
305
306  if (!new_row) {
307    DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
308    DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
309    DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
310  }
311
312  return *this;
313}
314
315gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
316  return current_geometry_rect_;
317}
318
319gfx::Rect
320PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
321  gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
322  rect.set_size(tiling_->tiling_data_.max_texture_size());
323  return rect;
324}
325
326gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
327  gfx::PointF tex_origin =
328      tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
329
330  // Convert from dest space => content space => texture space.
331  gfx::RectF texture_rect(current_geometry_rect_);
332  texture_rect.Scale(dest_to_content_scale_,
333                     dest_to_content_scale_);
334  texture_rect.Offset(-tex_origin.OffsetFromOrigin());
335  texture_rect.Intersect(tiling_->ContentRect());
336
337  return texture_rect;
338}
339
340gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
341  return tiling_->tiling_data_.max_texture_size();
342}
343
344void PictureLayerTiling::Reset() {
345  live_tiles_rect_ = gfx::Rect();
346  tiles_.clear();
347}
348
349void PictureLayerTiling::UpdateTilePriorities(
350    WhichTree tree,
351    gfx::Size device_viewport,
352    gfx::Rect viewport_in_layer_space,
353    gfx::Rect visible_layer_rect,
354    gfx::Size last_layer_bounds,
355    gfx::Size current_layer_bounds,
356    float last_layer_contents_scale,
357    float current_layer_contents_scale,
358    const gfx::Transform& last_screen_transform,
359    const gfx::Transform& current_screen_transform,
360    double current_frame_time_in_seconds,
361    size_t max_tiles_for_interest_area) {
362  if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
363    // This should never be zero for the purposes of has_ever_been_updated().
364    DCHECK_NE(current_frame_time_in_seconds, 0.0);
365    return;
366  }
367  if (ContentRect().IsEmpty()) {
368    last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
369    return;
370  }
371
372  gfx::Rect viewport_in_content_space =
373      gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
374  gfx::Rect visible_content_rect =
375      gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
376
377  gfx::Size tile_size = tiling_data_.max_texture_size();
378  int64 interest_rect_area =
379      max_tiles_for_interest_area * tile_size.width() * tile_size.height();
380
381  gfx::Rect starting_rect = visible_content_rect.IsEmpty()
382                            ? viewport_in_content_space
383                            : visible_content_rect;
384  gfx::Rect interest_rect = ExpandRectEquallyToAreaBoundedBy(
385      starting_rect,
386      interest_rect_area,
387      ContentRect(),
388      &expansion_cache_);
389  DCHECK(interest_rect.IsEmpty() ||
390         ContentRect().Contains(interest_rect));
391
392  SetLiveTilesRect(interest_rect);
393
394  double time_delta = 0;
395  if (last_impl_frame_time_in_seconds_ != 0.0 &&
396      last_layer_bounds == current_layer_bounds) {
397    time_delta =
398        current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
399  }
400
401  gfx::RectF view_rect(device_viewport);
402  float current_scale = current_layer_contents_scale / contents_scale_;
403  float last_scale = last_layer_contents_scale / contents_scale_;
404
405  // Fast path tile priority calculation when both transforms are translations.
406  if (last_screen_transform.IsApproximatelyIdentityOrTranslation(
407          std::numeric_limits<float>::epsilon()) &&
408      current_screen_transform.IsApproximatelyIdentityOrTranslation(
409          std::numeric_limits<float>::epsilon())) {
410    gfx::Vector2dF current_offset(
411        current_screen_transform.matrix().get(0, 3),
412        current_screen_transform.matrix().get(1, 3));
413    gfx::Vector2dF last_offset(
414        last_screen_transform.matrix().get(0, 3),
415        last_screen_transform.matrix().get(1, 3));
416
417    bool include_borders = true;
418    for (TilingData::Iterator iter(&tiling_data_, interest_rect, include_borders);
419         iter; ++iter) {
420      TileMap::iterator find = tiles_.find(iter.index());
421      if (find == tiles_.end())
422        continue;
423      Tile* tile = find->second.get();
424
425      gfx::Rect tile_bounds =
426          tiling_data_.TileBounds(iter.index_x(), iter.index_y());
427      gfx::RectF current_screen_rect = gfx::ScaleRect(
428          tile_bounds,
429          current_scale,
430          current_scale) + current_offset;
431      gfx::RectF last_screen_rect = gfx::ScaleRect(
432          tile_bounds,
433          last_scale,
434          last_scale) + last_offset;
435
436      float distance_to_visible_in_pixels =
437          current_screen_rect.ManhattanInternalDistance(view_rect);
438
439      float time_to_visible_in_seconds =
440          TilePriority::TimeForBoundsToIntersect(
441              last_screen_rect, current_screen_rect, time_delta, view_rect);
442      TilePriority priority(
443          resolution_,
444          time_to_visible_in_seconds,
445          distance_to_visible_in_pixels);
446      tile->SetPriority(tree, priority);
447    }
448  } else if (!last_screen_transform.HasPerspective() &&
449             !current_screen_transform.HasPerspective()) {
450    // Secondary fast path that can be applied for any affine transforms.
451
452    // Initialize the necessary geometry in screen space, so that we can
453    // iterate over tiles in screen space without needing a costly transform
454    // mapping for each tile.
455
456    // Apply screen space transform to the local origin point (0, 0); only the
457    // translation component is needed and can be initialized directly.
458    gfx::Point current_screen_space_origin(
459        current_screen_transform.matrix().get(0, 3),
460        current_screen_transform.matrix().get(1, 3));
461
462    gfx::Point last_screen_space_origin(
463        last_screen_transform.matrix().get(0, 3),
464        last_screen_transform.matrix().get(1, 3));
465
466    float current_tile_width = tiling_data_.TileSizeX(0) * current_scale;
467    float last_tile_width = tiling_data_.TileSizeX(0) * last_scale;
468    float current_tile_height = tiling_data_.TileSizeY(0) * current_scale;
469    float last_tile_height = tiling_data_.TileSizeY(0) * last_scale;
470
471    // Apply screen space transform to local basis vectors (tile_width, 0) and
472    // (0, tile_height); the math simplifies and can be initialized directly.
473    gfx::Vector2dF current_horizontal(
474        current_screen_transform.matrix().get(0, 0) * current_tile_width,
475        current_screen_transform.matrix().get(1, 0) * current_tile_width);
476    gfx::Vector2dF current_vertical(
477        current_screen_transform.matrix().get(0, 1) * current_tile_height,
478        current_screen_transform.matrix().get(1, 1) * current_tile_height);
479
480    gfx::Vector2dF last_horizontal(
481        last_screen_transform.matrix().get(0, 0) * last_tile_width,
482        last_screen_transform.matrix().get(1, 0) * last_tile_width);
483    gfx::Vector2dF last_vertical(
484        last_screen_transform.matrix().get(0, 1) * last_tile_height,
485        last_screen_transform.matrix().get(1, 1) * last_tile_height);
486
487    bool include_borders = true;
488    for (TilingData::Iterator iter(&tiling_data_, interest_rect, include_borders);
489         iter; ++iter) {
490      TileMap::iterator find = tiles_.find(iter.index());
491      if (find == tiles_.end())
492        continue;
493
494      Tile* tile = find->second.get();
495
496      int i = iter.index_x();
497      int j = iter.index_y();
498      gfx::PointF current_tile_origin = current_screen_space_origin +
499              ScaleVector2d(current_horizontal, i) +
500              ScaleVector2d(current_vertical, j);
501      gfx::PointF last_tile_origin = last_screen_space_origin +
502              ScaleVector2d(last_horizontal, i) +
503              ScaleVector2d(last_vertical, j);
504
505      gfx::RectF current_screen_rect = gfx::QuadF(
506          current_tile_origin,
507          current_tile_origin + current_horizontal,
508          current_tile_origin + current_horizontal + current_vertical,
509          current_tile_origin + current_vertical).BoundingBox();
510
511      gfx::RectF last_screen_rect = gfx::QuadF(
512          last_tile_origin,
513          last_tile_origin + last_horizontal,
514          last_tile_origin + last_horizontal + last_vertical,
515          last_tile_origin + last_vertical).BoundingBox();
516
517      float distance_to_visible_in_pixels =
518          current_screen_rect.ManhattanInternalDistance(view_rect);
519
520      float time_to_visible_in_seconds =
521          TilePriority::TimeForBoundsToIntersect(
522              last_screen_rect, current_screen_rect, time_delta, view_rect);
523      TilePriority priority(
524          resolution_,
525          time_to_visible_in_seconds,
526          distance_to_visible_in_pixels);
527      tile->SetPriority(tree, priority);
528    }
529  } else {
530    bool include_borders = true;
531    for (TilingData::Iterator iter(&tiling_data_, interest_rect, include_borders);
532         iter; ++iter) {
533      TileMap::iterator find = tiles_.find(iter.index());
534      if (find == tiles_.end())
535        continue;
536      Tile* tile = find->second.get();
537
538      gfx::Rect tile_bounds =
539          tiling_data_.TileBounds(iter.index_x(), iter.index_y());
540      gfx::RectF current_layer_content_rect = gfx::ScaleRect(
541          tile_bounds,
542          current_scale,
543          current_scale);
544      gfx::RectF current_screen_rect = MathUtil::MapClippedRect(
545          current_screen_transform, current_layer_content_rect);
546      gfx::RectF last_layer_content_rect = gfx::ScaleRect(
547          tile_bounds,
548          last_scale,
549          last_scale);
550      gfx::RectF last_screen_rect  = MathUtil::MapClippedRect(
551          last_screen_transform, last_layer_content_rect);
552
553      float distance_to_visible_in_pixels =
554          current_screen_rect.ManhattanInternalDistance(view_rect);
555
556      float time_to_visible_in_seconds =
557          TilePriority::TimeForBoundsToIntersect(
558              last_screen_rect, current_screen_rect, time_delta, view_rect);
559
560      TilePriority priority(
561          resolution_,
562          time_to_visible_in_seconds,
563          distance_to_visible_in_pixels);
564      tile->SetPriority(tree, priority);
565    }
566  }
567
568  last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
569}
570
571void PictureLayerTiling::SetLiveTilesRect(
572    gfx::Rect new_live_tiles_rect) {
573  DCHECK(new_live_tiles_rect.IsEmpty() ||
574         ContentRect().Contains(new_live_tiles_rect));
575  if (live_tiles_rect_ == new_live_tiles_rect)
576    return;
577
578  // Iterate to delete all tiles outside of our new live_tiles rect.
579  for (TilingData::DifferenceIterator iter(&tiling_data_,
580                                           live_tiles_rect_,
581                                           new_live_tiles_rect);
582       iter;
583       ++iter) {
584    TileMapKey key(iter.index());
585    TileMap::iterator found = tiles_.find(key);
586    // If the tile was outside of the recorded region, it won't exist even
587    // though it was in the live rect.
588    if (found != tiles_.end())
589      tiles_.erase(found);
590  }
591
592  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
593
594  // Iterate to allocate new tiles for all regions with newly exposed area.
595  for (TilingData::DifferenceIterator iter(&tiling_data_,
596                                           new_live_tiles_rect,
597                                           live_tiles_rect_);
598       iter;
599       ++iter) {
600    TileMapKey key(iter.index());
601    CreateTile(key.first, key.second, twin_tiling);
602  }
603
604  live_tiles_rect_ = new_live_tiles_rect;
605}
606
607void PictureLayerTiling::DidBecomeRecycled() {
608  // DidBecomeActive below will set the active priority for tiles that are
609  // still in the tree. Calling this first on an active tiling that is becoming
610  // recycled takes care of tiles that are no longer in the active tree (eg.
611  // due to a pending invalidation).
612  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
613    it->second->SetPriority(ACTIVE_TREE, TilePriority());
614  }
615}
616
617void PictureLayerTiling::DidBecomeActive() {
618  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
619    it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
620    it->second->SetPriority(PENDING_TREE, TilePriority());
621
622    // Tile holds a ref onto a picture pile. If the tile never gets invalidated
623    // and recreated, then that picture pile ref could exist indefinitely.  To
624    // prevent this, ask the client to update the pile to its own ref.  This
625    // will cause PicturePileImpls and their clones to get deleted once the
626    // corresponding PictureLayerImpl and any in flight raster jobs go out of
627    // scope.
628    client_->UpdatePile(it->second.get());
629  }
630}
631
632void PictureLayerTiling::UpdateTilesToCurrentPile() {
633  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
634    client_->UpdatePile(it->second.get());
635  }
636}
637
638scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
639  scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
640  state->SetInteger("num_tiles", tiles_.size());
641  state->SetDouble("content_scale", contents_scale_);
642  state->Set("content_bounds",
643             MathUtil::AsValue(ContentRect().size()).release());
644  return state.PassAs<base::Value>();
645}
646
647size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
648  size_t amount = 0;
649  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
650    const Tile* tile = it->second.get();
651    amount += tile->GPUMemoryUsageInBytes();
652  }
653  return amount;
654}
655
656PictureLayerTiling::RectExpansionCache::RectExpansionCache()
657  : previous_target(0) {
658}
659
660namespace {
661
662// This struct represents an event at which the expending rect intersects
663// one of its boundaries.  4 intersection events will occur during expansion.
664struct EdgeEvent {
665  enum { BOTTOM, TOP, LEFT, RIGHT } edge;
666  int* num_edges;
667  int distance;
668};
669
670// Compute the delta to expand from edges to cover target_area.
671int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
672                          int width, int height,
673                          int64 target_area) {
674  // Compute coefficients for the quadratic equation:
675  //   a*x^2 + b*x + c = 0
676  int a = num_y_edges * num_x_edges;
677  int b = num_y_edges * width + num_x_edges * height;
678  int64 c = static_cast<int64>(width) * height - target_area;
679
680  // Compute the delta for our edges using the quadratic equation.
681  return a == 0 ? -c / b :
682     (-b + static_cast<int>(
683         std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
684}
685
686}  // namespace
687
688gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
689    gfx::Rect starting_rect,
690    int64 target_area,
691    gfx::Rect bounding_rect,
692    RectExpansionCache* cache) {
693  if (starting_rect.IsEmpty())
694    return starting_rect;
695
696  if (cache &&
697      cache->previous_start == starting_rect &&
698      cache->previous_bounds == bounding_rect &&
699      cache->previous_target == target_area)
700    return cache->previous_result;
701
702  if (cache) {
703    cache->previous_start = starting_rect;
704    cache->previous_bounds = bounding_rect;
705    cache->previous_target = target_area;
706  }
707
708  DCHECK(!bounding_rect.IsEmpty());
709  DCHECK_GT(target_area, 0);
710
711  // Expand the starting rect to cover target_area, if it is smaller than it.
712  int delta = ComputeExpansionDelta(
713      2, 2, starting_rect.width(), starting_rect.height(), target_area);
714  gfx::Rect expanded_starting_rect = starting_rect;
715  if (delta > 0)
716    expanded_starting_rect.Inset(-delta, -delta);
717
718  gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
719  if (rect.IsEmpty()) {
720    // The starting_rect and bounding_rect are far away.
721    if (cache)
722      cache->previous_result = rect;
723    return rect;
724  }
725  if (delta >= 0 && rect == expanded_starting_rect) {
726    // The starting rect already covers the entire bounding_rect and isn't too
727    // large for the target_area.
728    if (cache)
729      cache->previous_result = rect;
730    return rect;
731  }
732
733  // Continue to expand/shrink rect to let it cover target_area.
734
735  // These values will be updated by the loop and uses as the output.
736  int origin_x = rect.x();
737  int origin_y = rect.y();
738  int width = rect.width();
739  int height = rect.height();
740
741  // In the beginning we will consider 2 edges in each dimension.
742  int num_y_edges = 2;
743  int num_x_edges = 2;
744
745  // Create an event list.
746  EdgeEvent events[] = {
747    { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
748    { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
749    { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
750    { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
751  };
752
753  // Sort the events by distance (closest first).
754  if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
755  if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
756  if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
757  if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
758  if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
759
760  for (int event_index = 0; event_index < 4; event_index++) {
761    const EdgeEvent& event = events[event_index];
762
763    int delta = ComputeExpansionDelta(
764        num_x_edges, num_y_edges, width, height, target_area);
765
766    // Clamp delta to our event distance.
767    if (delta > event.distance)
768      delta = event.distance;
769
770    // Adjust the edge count for this kind of edge.
771    --*event.num_edges;
772
773    // Apply the delta to the edges and edge events.
774    for (int i = event_index; i < 4; i++) {
775      switch (events[i].edge) {
776        case EdgeEvent::BOTTOM:
777            origin_y -= delta;
778            height += delta;
779            break;
780        case EdgeEvent::TOP:
781            height += delta;
782            break;
783        case EdgeEvent::LEFT:
784            origin_x -= delta;
785            width += delta;
786            break;
787        case EdgeEvent::RIGHT:
788            width += delta;
789            break;
790      }
791      events[i].distance -= delta;
792    }
793
794    // If our delta is less then our event distance, we're done.
795    if (delta < event.distance)
796      break;
797  }
798
799  gfx::Rect result(origin_x, origin_y, width, height);
800  if (cache)
801    cache->previous_result = result;
802  return result;
803}
804
805}  // namespace cc
806