cc/resources/tile_manager_unittest.cc

   1 // Copyright 2013 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/eviction_tile_priority_queue.h"
   6 #include "cc/resources/raster_tile_priority_queue.h"
   7 #include "cc/resources/resource_pool.h"
   8 #include "cc/resources/tile.h"
   9 #include "cc/resources/tile_priority.h"
  10 #include "cc/resources/tiling_set_raster_queue_all.h"
  11 #include "cc/test/begin_frame_args_test.h"
  12 #include "cc/test/fake_impl_proxy.h"
  13 #include "cc/test/fake_layer_tree_host_impl.h"
  14 #include "cc/test/fake_output_surface.h"
  15 #include "cc/test/fake_output_surface_client.h"
  16 #include "cc/test/fake_picture_layer_impl.h"
  17 #include "cc/test/fake_picture_layer_tiling_client.h"
  18 #include "cc/test/fake_picture_pile_impl.h"
  19 #include "cc/test/fake_tile_manager.h"
  20 #include "cc/test/impl_side_painting_settings.h"
  21 #include "cc/test/test_shared_bitmap_manager.h"
  22 #include "cc/test/test_task_graph_runner.h"
  23 #include "cc/test/test_tile_priorities.h"
  24 #include "cc/trees/layer_tree_impl.h"
  25 #include "testing/gtest/include/gtest/gtest.h"
  26
  27 namespace cc {
  28 namespace {
  29
  30 class LowResTilingsSettings : public ImplSidePaintingSettings {
  31  public:
  32   LowResTilingsSettings() { create_low_res_tiling = true; }
  33 };
  34
  35 class TileManagerTilePriorityQueueTest : public testing::Test {
  36  public:
  37   TileManagerTilePriorityQueueTest()
  38       : memory_limit_policy_(ALLOW_ANYTHING),
  39         max_tiles_(10000),
  40         ready_to_activate_(false),
  41         id_(7),
  42         proxy_(base::MessageLoopProxy::current()),
  43         host_impl_(LowResTilingsSettings(),
  44                    &proxy_,
  45                    &shared_bitmap_manager_,
  46                    &task_graph_runner_) {}
  47
  48   void SetTreePriority(TreePriority tree_priority) {
  49     GlobalStateThatImpactsTilePriority state;
  50     gfx::Size tile_size(256, 256);
  51
  52     state.soft_memory_limit_in_bytes = 100 * 1000 * 1000;
  53     state.num_resources_limit = max_tiles_;
  54     state.hard_memory_limit_in_bytes = state.soft_memory_limit_in_bytes * 2;
  55     state.memory_limit_policy = memory_limit_policy_;
  56     state.tree_priority = tree_priority;
  57
  58     global_state_ = state;
  59     host_impl_.resource_pool()->SetResourceUsageLimits(
  60         state.soft_memory_limit_in_bytes,
  61         state.soft_memory_limit_in_bytes,
  62         state.num_resources_limit);
  63     host_impl_.tile_manager()->SetGlobalStateForTesting(state);
  64   }
  65
  66   void SetUp() override {
  67     InitializeRenderer();
  68     SetTreePriority(SAME_PRIORITY_FOR_BOTH_TREES);
  69   }
  70
  71   virtual void InitializeRenderer() {
  72     host_impl_.InitializeRenderer(FakeOutputSurface::Create3d());
  73   }
  74
  75   void SetupDefaultTrees(const gfx::Size& layer_bounds) {
  76     gfx::Size tile_size(100, 100);
  77
  78     scoped_refptr<FakePicturePileImpl> pending_pile =
  79         FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
  80     scoped_refptr<FakePicturePileImpl> active_pile =
  81         FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
  82
  83     SetupTrees(pending_pile, active_pile);
  84   }
  85
  86   void ActivateTree() {
  87     host_impl_.ActivateSyncTree();
  88     CHECK(!host_impl_.pending_tree());
  89     pending_layer_ = NULL;
  90     active_layer_ = static_cast<FakePictureLayerImpl*>(
  91         host_impl_.active_tree()->LayerById(id_));
  92   }
  93
  94   void SetupDefaultTreesWithFixedTileSize(const gfx::Size& layer_bounds,
  95                                           const gfx::Size& tile_size) {
  96     SetupDefaultTrees(layer_bounds);
  97     pending_layer_->set_fixed_tile_size(tile_size);
  98     active_layer_->set_fixed_tile_size(tile_size);
  99   }
 100
 101   void SetupTrees(scoped_refptr<PicturePileImpl> pending_pile,
 102                   scoped_refptr<PicturePileImpl> active_pile) {
 103     SetupPendingTree(active_pile);
 104     ActivateTree();
 105     SetupPendingTree(pending_pile);
 106   }
 107
 108   void SetupPendingTree(scoped_refptr<PicturePileImpl> pile) {
 109     host_impl_.CreatePendingTree();
 110     LayerTreeImpl* pending_tree = host_impl_.pending_tree();
 111
 112     // Steal from the recycled tree.
 113     scoped_ptr<LayerImpl> old_pending_root = pending_tree->DetachLayerTree();
 114     DCHECK_IMPLIES(old_pending_root, old_pending_root->id() == id_);
 115
 116     scoped_ptr<FakePictureLayerImpl> pending_layer;
 117     if (old_pending_root) {
 118       pending_layer.reset(
 119           static_cast<FakePictureLayerImpl*>(old_pending_root.release()));
 120       pending_layer->SetRasterSourceOnPending(pile, Region());
 121     } else {
 122       pending_layer =
 123           FakePictureLayerImpl::CreateWithRasterSource(pending_tree, id_, pile);
 124       pending_layer->SetDrawsContent(true);
 125       pending_layer->SetHasRenderSurface(true);
 126     }
 127     // The bounds() just mirror the pile size.
 128     pending_layer->SetBounds(pending_layer->raster_source()->GetSize());
 129     pending_tree->SetRootLayer(pending_layer.Pass());
 130
 131     pending_layer_ = static_cast<FakePictureLayerImpl*>(
 132         host_impl_.pending_tree()->LayerById(id_));
 133
 134     // Add tilings/tiles for the layer.
 135     bool update_lcd_text = false;
 136     host_impl_.pending_tree()->UpdateDrawProperties(update_lcd_text);
 137   }
 138
 139   TileManager* tile_manager() { return host_impl_.tile_manager(); }
 140
 141  protected:
 142   GlobalStateThatImpactsTilePriority global_state_;
 143
 144   TestSharedBitmapManager shared_bitmap_manager_;
 145   TestTaskGraphRunner task_graph_runner_;
 146   TileMemoryLimitPolicy memory_limit_policy_;
 147   int max_tiles_;
 148   bool ready_to_activate_;
 149   int id_;
 150   FakeImplProxy proxy_;
 151   FakeLayerTreeHostImpl host_impl_;
 152   FakePictureLayerImpl* pending_layer_;
 153   FakePictureLayerImpl* active_layer_;
 154 };
 155
 156 TEST_F(TileManagerTilePriorityQueueTest, RasterTilePriorityQueue) {
 157   const gfx::Size layer_bounds(1000, 1000);
 158   host_impl_.SetViewportSize(layer_bounds);
 159   SetupDefaultTrees(layer_bounds);
 160
 161   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
 162       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
 163   EXPECT_FALSE(queue->IsEmpty());
 164
 165   size_t tile_count = 0;
 166   std::set<Tile*> all_tiles;
 167   while (!queue->IsEmpty()) {
 168     EXPECT_TRUE(queue->Top());
 169     all_tiles.insert(queue->Top());
 170     ++tile_count;
 171     queue->Pop();
 172   }
 173
 174   EXPECT_EQ(tile_count, all_tiles.size());
 175   EXPECT_EQ(16u, tile_count);
 176
 177   // Sanity check, all tiles should be visible.
 178   std::set<Tile*> smoothness_tiles;
 179   queue = host_impl_.BuildRasterQueue(SMOOTHNESS_TAKES_PRIORITY,
 180                                       RasterTilePriorityQueue::Type::ALL);
 181   bool had_low_res = false;
 182   while (!queue->IsEmpty()) {
 183     Tile* tile = queue->Top();
 184     EXPECT_TRUE(tile);
 185     EXPECT_EQ(TilePriority::NOW, tile->priority(ACTIVE_TREE).priority_bin);
 186     EXPECT_EQ(TilePriority::NOW, tile->priority(PENDING_TREE).priority_bin);
 187     if (tile->priority(ACTIVE_TREE).resolution == LOW_RESOLUTION)
 188       had_low_res = true;
 189     else
 190       smoothness_tiles.insert(tile);
 191     queue->Pop();
 192   }
 193   EXPECT_EQ(all_tiles, smoothness_tiles);
 194   EXPECT_TRUE(had_low_res);
 195
 196   // Check that everything is required for activation.
 197   queue = host_impl_.BuildRasterQueue(
 198       SMOOTHNESS_TAKES_PRIORITY,
 199       RasterTilePriorityQueue::Type::REQUIRED_FOR_ACTIVATION);
 200   std::set<Tile*> required_for_activation_tiles;
 201   while (!queue->IsEmpty()) {
 202     Tile* tile = queue->Top();
 203     EXPECT_TRUE(tile->required_for_activation());
 204     required_for_activation_tiles.insert(tile);
 205     queue->Pop();
 206   }
 207   EXPECT_EQ(all_tiles, required_for_activation_tiles);
 208
 209   // Check that everything is required for draw.
 210   queue = host_impl_.BuildRasterQueue(
 211       SMOOTHNESS_TAKES_PRIORITY,
 212       RasterTilePriorityQueue::Type::REQUIRED_FOR_DRAW);
 213   std::set<Tile*> required_for_draw_tiles;
 214   while (!queue->IsEmpty()) {
 215     Tile* tile = queue->Top();
 216     EXPECT_TRUE(tile->required_for_draw());
 217     required_for_draw_tiles.insert(tile);
 218     queue->Pop();
 219   }
 220   EXPECT_EQ(all_tiles, required_for_draw_tiles);
 221
 222   Region invalidation(gfx::Rect(0, 0, 500, 500));
 223
 224   // Invalidate the pending tree.
 225   pending_layer_->set_invalidation(invalidation);
 226   pending_layer_->HighResTiling()->Invalidate(invalidation);
 227   pending_layer_->LowResTiling()->Invalidate(invalidation);
 228
 229   active_layer_->ResetAllTilesPriorities();
 230   pending_layer_->ResetAllTilesPriorities();
 231
 232   // Renew all of the tile priorities.
 233   gfx::Rect viewport(50, 50, 100, 100);
 234   pending_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 235                                                             Occlusion());
 236   pending_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 237                                                            Occlusion());
 238   active_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 239                                                            Occlusion());
 240   active_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 241                                                           Occlusion());
 242
 243   // Populate all tiles directly from the tilings.
 244   all_tiles.clear();
 245   std::set<Tile*> high_res_tiles;
 246   std::vector<Tile*> pending_high_res_tiles =
 247       pending_layer_->HighResTiling()->AllTilesForTesting();
 248   for (size_t i = 0; i < pending_high_res_tiles.size(); ++i) {
 249     all_tiles.insert(pending_high_res_tiles[i]);
 250     high_res_tiles.insert(pending_high_res_tiles[i]);
 251   }
 252
 253   std::vector<Tile*> pending_low_res_tiles =
 254       pending_layer_->LowResTiling()->AllTilesForTesting();
 255   for (size_t i = 0; i < pending_low_res_tiles.size(); ++i)
 256     all_tiles.insert(pending_low_res_tiles[i]);
 257
 258   std::vector<Tile*> active_high_res_tiles =
 259       active_layer_->HighResTiling()->AllTilesForTesting();
 260   for (size_t i = 0; i < active_high_res_tiles.size(); ++i) {
 261     all_tiles.insert(active_high_res_tiles[i]);
 262     high_res_tiles.insert(active_high_res_tiles[i]);
 263   }
 264
 265   std::vector<Tile*> active_low_res_tiles =
 266       active_layer_->LowResTiling()->AllTilesForTesting();
 267   for (size_t i = 0; i < active_low_res_tiles.size(); ++i)
 268     all_tiles.insert(active_low_res_tiles[i]);
 269
 270   Tile* last_tile = NULL;
 271   smoothness_tiles.clear();
 272   tile_count = 0;
 273   size_t correct_order_tiles = 0u;
 274   // Here we expect to get increasing ACTIVE_TREE priority_bin.
 275   queue = host_impl_.BuildRasterQueue(SMOOTHNESS_TAKES_PRIORITY,
 276                                       RasterTilePriorityQueue::Type::ALL);
 277   std::set<Tile*> expected_required_for_draw_tiles;
 278   std::set<Tile*> expected_required_for_activation_tiles;
 279   while (!queue->IsEmpty()) {
 280     Tile* tile = queue->Top();
 281     EXPECT_TRUE(tile);
 282
 283     if (!last_tile)
 284       last_tile = tile;
 285
 286     EXPECT_LE(last_tile->priority(ACTIVE_TREE).priority_bin,
 287               tile->priority(ACTIVE_TREE).priority_bin);
 288     bool skip_updating_last_tile = false;
 289     if (last_tile->priority(ACTIVE_TREE).priority_bin ==
 290         tile->priority(ACTIVE_TREE).priority_bin) {
 291       correct_order_tiles +=
 292           last_tile->priority(ACTIVE_TREE).distance_to_visible <=
 293           tile->priority(ACTIVE_TREE).distance_to_visible;
 294     } else if (tile->priority(ACTIVE_TREE).priority_bin ==
 295                    TilePriority::EVENTUALLY &&
 296                tile->priority(PENDING_TREE).priority_bin == TilePriority::NOW) {
 297       // Since we'd return pending tree now tiles before the eventually tiles on
 298       // the active tree, update the value.
 299       ++correct_order_tiles;
 300       skip_updating_last_tile = true;
 301     }
 302
 303     if (tile->priority(ACTIVE_TREE).priority_bin == TilePriority::NOW &&
 304         last_tile->priority(ACTIVE_TREE).resolution !=
 305             tile->priority(ACTIVE_TREE).resolution) {
 306       // Low resolution should come first.
 307       EXPECT_EQ(LOW_RESOLUTION, last_tile->priority(ACTIVE_TREE).resolution);
 308     }
 309
 310     if (!skip_updating_last_tile)
 311       last_tile = tile;
 312     ++tile_count;
 313     smoothness_tiles.insert(tile);
 314     if (tile->required_for_draw())
 315       expected_required_for_draw_tiles.insert(tile);
 316     if (tile->required_for_activation())
 317       expected_required_for_activation_tiles.insert(tile);
 318     queue->Pop();
 319   }
 320
 321   EXPECT_EQ(tile_count, smoothness_tiles.size());
 322   EXPECT_EQ(all_tiles, smoothness_tiles);
 323   // Since we don't guarantee increasing distance due to spiral iterator, we
 324   // should check that we're _mostly_ right.
 325   EXPECT_GT(correct_order_tiles, 3 * tile_count / 4);
 326
 327   // Check that we have consistent required_for_activation tiles.
 328   queue = host_impl_.BuildRasterQueue(
 329       SMOOTHNESS_TAKES_PRIORITY,
 330       RasterTilePriorityQueue::Type::REQUIRED_FOR_ACTIVATION);
 331   required_for_activation_tiles.clear();
 332   while (!queue->IsEmpty()) {
 333     Tile* tile = queue->Top();
 334     EXPECT_TRUE(tile->required_for_activation());
 335     required_for_activation_tiles.insert(tile);
 336     queue->Pop();
 337   }
 338   EXPECT_EQ(expected_required_for_activation_tiles,
 339             required_for_activation_tiles);
 340   EXPECT_NE(all_tiles, required_for_activation_tiles);
 341
 342   // Check that we have consistent required_for_draw tiles.
 343   queue = host_impl_.BuildRasterQueue(
 344       SMOOTHNESS_TAKES_PRIORITY,
 345       RasterTilePriorityQueue::Type::REQUIRED_FOR_DRAW);
 346   required_for_draw_tiles.clear();
 347   while (!queue->IsEmpty()) {
 348     Tile* tile = queue->Top();
 349     EXPECT_TRUE(tile->required_for_draw());
 350     required_for_draw_tiles.insert(tile);
 351     queue->Pop();
 352   }
 353   EXPECT_EQ(expected_required_for_draw_tiles, required_for_draw_tiles);
 354   EXPECT_NE(all_tiles, required_for_draw_tiles);
 355
 356   std::set<Tile*> new_content_tiles;
 357   last_tile = NULL;
 358   size_t increasing_distance_tiles = 0u;
 359   // Here we expect to get increasing PENDING_TREE priority_bin.
 360   queue = host_impl_.BuildRasterQueue(NEW_CONTENT_TAKES_PRIORITY,
 361                                       RasterTilePriorityQueue::Type::ALL);
 362   tile_count = 0;
 363   while (!queue->IsEmpty()) {
 364     Tile* tile = queue->Top();
 365     EXPECT_TRUE(tile);
 366
 367     if (!last_tile)
 368       last_tile = tile;
 369
 370     EXPECT_LE(last_tile->priority(PENDING_TREE).priority_bin,
 371               tile->priority(PENDING_TREE).priority_bin);
 372     if (last_tile->priority(PENDING_TREE).priority_bin ==
 373         tile->priority(PENDING_TREE).priority_bin) {
 374       increasing_distance_tiles +=
 375           last_tile->priority(PENDING_TREE).distance_to_visible <=
 376           tile->priority(PENDING_TREE).distance_to_visible;
 377     }
 378
 379     if (tile->priority(PENDING_TREE).priority_bin == TilePriority::NOW &&
 380         last_tile->priority(PENDING_TREE).resolution !=
 381             tile->priority(PENDING_TREE).resolution) {
 382       // High resolution should come first.
 383       EXPECT_EQ(HIGH_RESOLUTION, last_tile->priority(PENDING_TREE).resolution);
 384     }
 385
 386     last_tile = tile;
 387     new_content_tiles.insert(tile);
 388     ++tile_count;
 389     queue->Pop();
 390   }
 391
 392   EXPECT_EQ(tile_count, new_content_tiles.size());
 393   EXPECT_EQ(high_res_tiles, new_content_tiles);
 394   // Since we don't guarantee increasing distance due to spiral iterator, we
 395   // should check that we're _mostly_ right.
 396   EXPECT_GE(increasing_distance_tiles, 3 * tile_count / 4);
 397
 398   // Check that we have consistent required_for_activation tiles.
 399   queue = host_impl_.BuildRasterQueue(
 400       NEW_CONTENT_TAKES_PRIORITY,
 401       RasterTilePriorityQueue::Type::REQUIRED_FOR_ACTIVATION);
 402   required_for_activation_tiles.clear();
 403   while (!queue->IsEmpty()) {
 404     Tile* tile = queue->Top();
 405     EXPECT_TRUE(tile->required_for_activation());
 406     required_for_activation_tiles.insert(tile);
 407     queue->Pop();
 408   }
 409   EXPECT_EQ(expected_required_for_activation_tiles,
 410             required_for_activation_tiles);
 411   EXPECT_NE(new_content_tiles, required_for_activation_tiles);
 412
 413   // Check that we have consistent required_for_draw tiles.
 414   queue = host_impl_.BuildRasterQueue(
 415       NEW_CONTENT_TAKES_PRIORITY,
 416       RasterTilePriorityQueue::Type::REQUIRED_FOR_DRAW);
 417   required_for_draw_tiles.clear();
 418   while (!queue->IsEmpty()) {
 419     Tile* tile = queue->Top();
 420     EXPECT_TRUE(tile->required_for_draw());
 421     required_for_draw_tiles.insert(tile);
 422     queue->Pop();
 423   }
 424   EXPECT_EQ(expected_required_for_draw_tiles, required_for_draw_tiles);
 425   EXPECT_NE(new_content_tiles, required_for_draw_tiles);
 426 }
 427
 428 TEST_F(TileManagerTilePriorityQueueTest, RasterTilePriorityQueueInvalidation) {
 429   const gfx::Size layer_bounds(1000, 1000);
 430   host_impl_.SetViewportSize(gfx::Size(500, 500));
 431   SetupDefaultTrees(layer_bounds);
 432
 433   // Use a tile's content rect as an invalidation. We should inset it a bit to
 434   // ensure that border math doesn't invalidate neighbouring tiles.
 435   gfx::Rect invalidation =
 436       pending_layer_->HighResTiling()->TileAt(1, 0)->content_rect();
 437   invalidation.Inset(2, 2);
 438
 439   pending_layer_->set_invalidation(invalidation);
 440   pending_layer_->HighResTiling()->Invalidate(invalidation);
 441   pending_layer_->LowResTiling()->Invalidate(invalidation);
 442
 443   // Sanity checks: Tile at 0, 0 should be the same on both trees, tile at 1, 0
 444   // should be different.
 445   EXPECT_TRUE(pending_layer_->HighResTiling()->TileAt(0, 0));
 446   EXPECT_TRUE(active_layer_->HighResTiling()->TileAt(0, 0));
 447   EXPECT_EQ(pending_layer_->HighResTiling()->TileAt(0, 0),
 448             active_layer_->HighResTiling()->TileAt(0, 0));
 449   EXPECT_TRUE(pending_layer_->HighResTiling()->TileAt(1, 0));
 450   EXPECT_TRUE(active_layer_->HighResTiling()->TileAt(1, 0));
 451   EXPECT_NE(pending_layer_->HighResTiling()->TileAt(1, 0),
 452             active_layer_->HighResTiling()->TileAt(1, 0));
 453
 454   std::set<Tile*> expected_now_tiles;
 455   std::set<Tile*> expected_required_for_draw_tiles;
 456   std::set<Tile*> expected_required_for_activation_tiles;
 457   for (int i = 0; i <= 1; ++i) {
 458     for (int j = 0; j <= 1; ++j) {
 459       expected_now_tiles.insert(pending_layer_->HighResTiling()->TileAt(i, j));
 460       expected_now_tiles.insert(active_layer_->HighResTiling()->TileAt(i, j));
 461
 462       expected_required_for_activation_tiles.insert(
 463           pending_layer_->HighResTiling()->TileAt(i, j));
 464       expected_required_for_draw_tiles.insert(
 465           active_layer_->HighResTiling()->TileAt(i, j));
 466     }
 467   }
 468   // Expect 3 shared tiles and 1 unshared tile in total.
 469   EXPECT_EQ(5u, expected_now_tiles.size());
 470   // Expect 4 tiles for each draw and activation, but not all the same.
 471   EXPECT_EQ(4u, expected_required_for_activation_tiles.size());
 472   EXPECT_EQ(4u, expected_required_for_draw_tiles.size());
 473   EXPECT_NE(expected_required_for_draw_tiles,
 474             expected_required_for_activation_tiles);
 475
 476   std::set<Tile*> expected_all_tiles;
 477   for (int i = 0; i <= 3; ++i) {
 478     for (int j = 0; j <= 3; ++j) {
 479       expected_all_tiles.insert(pending_layer_->HighResTiling()->TileAt(i, j));
 480       expected_all_tiles.insert(active_layer_->HighResTiling()->TileAt(i, j));
 481     }
 482   }
 483   // Expect 15 shared tiles and 1 unshared tile.
 484   EXPECT_EQ(17u, expected_all_tiles.size());
 485
 486   // The actual test will now build different queues and verify that the queues
 487   // return the same information as computed manually above.
 488   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
 489       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
 490   std::set<Tile*> actual_now_tiles;
 491   std::set<Tile*> actual_all_tiles;
 492   while (!queue->IsEmpty()) {
 493     Tile* tile = queue->Top();
 494     queue->Pop();
 495     if (tile->combined_priority().priority_bin == TilePriority::NOW)
 496       actual_now_tiles.insert(tile);
 497     actual_all_tiles.insert(tile);
 498   }
 499   EXPECT_EQ(expected_now_tiles, actual_now_tiles);
 500   EXPECT_EQ(expected_all_tiles, actual_all_tiles);
 501
 502   queue = host_impl_.BuildRasterQueue(
 503       SAME_PRIORITY_FOR_BOTH_TREES,
 504       RasterTilePriorityQueue::Type::REQUIRED_FOR_DRAW);
 505   std::set<Tile*> actual_required_for_draw_tiles;
 506   while (!queue->IsEmpty()) {
 507     Tile* tile = queue->Top();
 508     queue->Pop();
 509     actual_required_for_draw_tiles.insert(tile);
 510   }
 511   EXPECT_EQ(expected_required_for_draw_tiles, actual_required_for_draw_tiles);
 512
 513   queue = host_impl_.BuildRasterQueue(
 514       SAME_PRIORITY_FOR_BOTH_TREES,
 515       RasterTilePriorityQueue::Type::REQUIRED_FOR_ACTIVATION);
 516   std::set<Tile*> actual_required_for_activation_tiles;
 517   while (!queue->IsEmpty()) {
 518     Tile* tile = queue->Top();
 519     queue->Pop();
 520     actual_required_for_activation_tiles.insert(tile);
 521   }
 522   EXPECT_EQ(expected_required_for_activation_tiles,
 523             actual_required_for_activation_tiles);
 524 }
 525
 526 TEST_F(TileManagerTilePriorityQueueTest, ActivationComesBeforeEventually) {
 527   base::TimeTicks time_ticks;
 528   time_ticks += base::TimeDelta::FromMilliseconds(1);
 529   host_impl_.SetCurrentBeginFrameArgs(
 530       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 531
 532   gfx::Size layer_bounds(1000, 1000);
 533   SetupDefaultTrees(layer_bounds);
 534
 535   // Create a pending child layer.
 536   gfx::Size tile_size(256, 256);
 537   scoped_refptr<FakePicturePileImpl> pending_pile =
 538       FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
 539   scoped_ptr<FakePictureLayerImpl> pending_child =
 540       FakePictureLayerImpl::CreateWithRasterSource(host_impl_.pending_tree(),
 541                                                    id_ + 1, pending_pile);
 542   FakePictureLayerImpl* pending_child_raw = pending_child.get();
 543   pending_child_raw->SetDrawsContent(true);
 544   pending_layer_->AddChild(pending_child.Pass());
 545
 546   // Set a small viewport, so we have soon and eventually tiles.
 547   host_impl_.SetViewportSize(gfx::Size(200, 200));
 548   time_ticks += base::TimeDelta::FromMilliseconds(1);
 549   host_impl_.SetCurrentBeginFrameArgs(
 550       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 551   bool update_lcd_text = false;
 552   host_impl_.pending_tree()->UpdateDrawProperties(update_lcd_text);
 553
 554   host_impl_.SetRequiresHighResToDraw();
 555   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
 556       SMOOTHNESS_TAKES_PRIORITY, RasterTilePriorityQueue::Type::ALL));
 557   EXPECT_FALSE(queue->IsEmpty());
 558
 559   // Get all the tiles that are NOW or SOON and make sure they are ready to
 560   // draw.
 561   std::vector<Tile*> all_tiles;
 562   while (!queue->IsEmpty()) {
 563     Tile* tile = queue->Top();
 564     if (tile->combined_priority().priority_bin >= TilePriority::EVENTUALLY)
 565       break;
 566
 567     all_tiles.push_back(tile);
 568     queue->Pop();
 569   }
 570
 571   tile_manager()->InitializeTilesWithResourcesForTesting(
 572       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 573
 574   // Ensure we can activate.
 575   EXPECT_TRUE(tile_manager()->IsReadyToActivate());
 576 }
 577
 578 TEST_F(TileManagerTilePriorityQueueTest, EvictionTilePriorityQueue) {
 579   const gfx::Size layer_bounds(1000, 1000);
 580   host_impl_.SetViewportSize(layer_bounds);
 581   SetupDefaultTrees(layer_bounds);
 582
 583   scoped_ptr<EvictionTilePriorityQueue> empty_queue(
 584       host_impl_.BuildEvictionQueue(SAME_PRIORITY_FOR_BOTH_TREES));
 585   EXPECT_TRUE(empty_queue->IsEmpty());
 586   std::set<Tile*> all_tiles;
 587   size_t tile_count = 0;
 588
 589   scoped_ptr<RasterTilePriorityQueue> raster_queue(host_impl_.BuildRasterQueue(
 590       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
 591   while (!raster_queue->IsEmpty()) {
 592     ++tile_count;
 593     EXPECT_TRUE(raster_queue->Top());
 594     all_tiles.insert(raster_queue->Top());
 595     raster_queue->Pop();
 596   }
 597
 598   EXPECT_EQ(tile_count, all_tiles.size());
 599   EXPECT_EQ(16u, tile_count);
 600
 601   tile_manager()->InitializeTilesWithResourcesForTesting(
 602       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 603
 604   scoped_ptr<EvictionTilePriorityQueue> queue(
 605       host_impl_.BuildEvictionQueue(SMOOTHNESS_TAKES_PRIORITY));
 606   EXPECT_FALSE(queue->IsEmpty());
 607
 608   // Sanity check, all tiles should be visible.
 609   std::set<Tile*> smoothness_tiles;
 610   while (!queue->IsEmpty()) {
 611     Tile* tile = queue->Top();
 612     EXPECT_TRUE(tile);
 613     EXPECT_EQ(TilePriority::NOW, tile->priority(ACTIVE_TREE).priority_bin);
 614     EXPECT_EQ(TilePriority::NOW, tile->priority(PENDING_TREE).priority_bin);
 615     EXPECT_TRUE(tile->HasResource());
 616     smoothness_tiles.insert(tile);
 617     queue->Pop();
 618   }
 619   EXPECT_EQ(all_tiles, smoothness_tiles);
 620
 621   tile_manager()->ReleaseTileResourcesForTesting(
 622       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 623
 624   Region invalidation(gfx::Rect(0, 0, 500, 500));
 625
 626   // Invalidate the pending tree.
 627   pending_layer_->set_invalidation(invalidation);
 628   pending_layer_->HighResTiling()->Invalidate(invalidation);
 629   pending_layer_->LowResTiling()->Invalidate(invalidation);
 630
 631   active_layer_->ResetAllTilesPriorities();
 632   pending_layer_->ResetAllTilesPriorities();
 633
 634   // Renew all of the tile priorities.
 635   gfx::Rect viewport(50, 50, 100, 100);
 636   pending_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 637                                                             Occlusion());
 638   pending_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 639                                                            Occlusion());
 640   active_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 641                                                            Occlusion());
 642   active_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 643                                                           Occlusion());
 644
 645   // Populate all tiles directly from the tilings.
 646   all_tiles.clear();
 647   std::vector<Tile*> pending_high_res_tiles =
 648       pending_layer_->HighResTiling()->AllTilesForTesting();
 649   for (size_t i = 0; i < pending_high_res_tiles.size(); ++i)
 650     all_tiles.insert(pending_high_res_tiles[i]);
 651
 652   std::vector<Tile*> pending_low_res_tiles =
 653       pending_layer_->LowResTiling()->AllTilesForTesting();
 654   for (size_t i = 0; i < pending_low_res_tiles.size(); ++i)
 655     all_tiles.insert(pending_low_res_tiles[i]);
 656
 657   std::vector<Tile*> active_high_res_tiles =
 658       active_layer_->HighResTiling()->AllTilesForTesting();
 659   for (size_t i = 0; i < active_high_res_tiles.size(); ++i)
 660     all_tiles.insert(active_high_res_tiles[i]);
 661
 662   std::vector<Tile*> active_low_res_tiles =
 663       active_layer_->LowResTiling()->AllTilesForTesting();
 664   for (size_t i = 0; i < active_low_res_tiles.size(); ++i)
 665     all_tiles.insert(active_low_res_tiles[i]);
 666
 667   tile_manager()->InitializeTilesWithResourcesForTesting(
 668       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 669
 670   Tile* last_tile = NULL;
 671   smoothness_tiles.clear();
 672   tile_count = 0;
 673   // Here we expect to get increasing combined priority_bin.
 674   queue = host_impl_.BuildEvictionQueue(SMOOTHNESS_TAKES_PRIORITY);
 675   int distance_increasing = 0;
 676   int distance_decreasing = 0;
 677   while (!queue->IsEmpty()) {
 678     Tile* tile = queue->Top();
 679     EXPECT_TRUE(tile);
 680     EXPECT_TRUE(tile->HasResource());
 681
 682     if (!last_tile)
 683       last_tile = tile;
 684
 685     const TilePriority& last_priority = last_tile->combined_priority();
 686     const TilePriority& priority = tile->combined_priority();
 687
 688     EXPECT_GE(last_priority.priority_bin, priority.priority_bin);
 689     if (last_priority.priority_bin == priority.priority_bin) {
 690       EXPECT_LE(last_tile->required_for_activation(),
 691                 tile->required_for_activation());
 692       if (last_tile->required_for_activation() ==
 693           tile->required_for_activation()) {
 694         if (last_priority.distance_to_visible >= priority.distance_to_visible)
 695           ++distance_decreasing;
 696         else
 697           ++distance_increasing;
 698       }
 699     }
 700
 701     last_tile = tile;
 702     ++tile_count;
 703     smoothness_tiles.insert(tile);
 704     queue->Pop();
 705   }
 706
 707   // Ensure that the distance is decreasing many more times than increasing.
 708   EXPECT_EQ(3, distance_increasing);
 709   EXPECT_EQ(17, distance_decreasing);
 710   EXPECT_EQ(tile_count, smoothness_tiles.size());
 711   EXPECT_EQ(all_tiles, smoothness_tiles);
 712
 713   std::set<Tile*> new_content_tiles;
 714   last_tile = NULL;
 715   // Again, we expect to get increasing combined priority_bin.
 716   queue = host_impl_.BuildEvictionQueue(NEW_CONTENT_TAKES_PRIORITY);
 717   distance_decreasing = 0;
 718   distance_increasing = 0;
 719   while (!queue->IsEmpty()) {
 720     Tile* tile = queue->Top();
 721     EXPECT_TRUE(tile);
 722
 723     if (!last_tile)
 724       last_tile = tile;
 725
 726     const TilePriority& last_priority = last_tile->combined_priority();
 727     const TilePriority& priority = tile->combined_priority();
 728
 729     EXPECT_GE(last_priority.priority_bin, priority.priority_bin);
 730     if (last_priority.priority_bin == priority.priority_bin) {
 731       EXPECT_LE(last_tile->required_for_activation(),
 732                 tile->required_for_activation());
 733       if (last_tile->required_for_activation() ==
 734           tile->required_for_activation()) {
 735         if (last_priority.distance_to_visible >= priority.distance_to_visible)
 736           ++distance_decreasing;
 737         else
 738           ++distance_increasing;
 739       }
 740     }
 741
 742     last_tile = tile;
 743     new_content_tiles.insert(tile);
 744     queue->Pop();
 745   }
 746
 747   // Ensure that the distance is decreasing many more times than increasing.
 748   EXPECT_EQ(3, distance_increasing);
 749   EXPECT_EQ(17, distance_decreasing);
 750   EXPECT_EQ(tile_count, new_content_tiles.size());
 751   EXPECT_EQ(all_tiles, new_content_tiles);
 752 }
 753
 754 TEST_F(TileManagerTilePriorityQueueTest,
 755        EvictionTilePriorityQueueWithOcclusion) {
 756   base::TimeTicks time_ticks;
 757   time_ticks += base::TimeDelta::FromMilliseconds(1);
 758   host_impl_.SetCurrentBeginFrameArgs(
 759       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 760
 761   gfx::Size tile_size(102, 102);
 762   gfx::Size layer_bounds(1000, 1000);
 763
 764   host_impl_.SetViewportSize(layer_bounds);
 765
 766   scoped_refptr<FakePicturePileImpl> pending_pile =
 767       FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
 768   SetupPendingTree(pending_pile);
 769
 770   scoped_ptr<FakePictureLayerImpl> pending_child =
 771       FakePictureLayerImpl::CreateWithRasterSource(host_impl_.pending_tree(), 2,
 772                                                    pending_pile);
 773   pending_layer_->AddChild(pending_child.Pass());
 774
 775   FakePictureLayerImpl* pending_child_layer =
 776       static_cast<FakePictureLayerImpl*>(pending_layer_->children()[0]);
 777   pending_child_layer->SetDrawsContent(true);
 778
 779   time_ticks += base::TimeDelta::FromMilliseconds(1);
 780   host_impl_.SetCurrentBeginFrameArgs(
 781       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 782   bool update_lcd_text = false;
 783   host_impl_.pending_tree()->UpdateDrawProperties(update_lcd_text);
 784
 785   ActivateTree();
 786   SetupPendingTree(pending_pile);
 787
 788   FakePictureLayerImpl* active_child_layer =
 789       static_cast<FakePictureLayerImpl*>(active_layer_->children()[0]);
 790
 791   std::set<Tile*> all_tiles;
 792   size_t tile_count = 0;
 793   scoped_ptr<RasterTilePriorityQueue> raster_queue(host_impl_.BuildRasterQueue(
 794       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
 795   while (!raster_queue->IsEmpty()) {
 796     ++tile_count;
 797     EXPECT_TRUE(raster_queue->Top());
 798     all_tiles.insert(raster_queue->Top());
 799     raster_queue->Pop();
 800   }
 801   EXPECT_EQ(tile_count, all_tiles.size());
 802   EXPECT_EQ(32u, tile_count);
 803
 804   pending_layer_->ResetAllTilesPriorities();
 805
 806   // Renew all of the tile priorities.
 807   gfx::Rect viewport(layer_bounds);
 808   pending_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 809                                                             Occlusion());
 810   pending_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 811                                                            Occlusion());
 812   pending_child_layer->HighResTiling()->ComputeTilePriorityRects(
 813       viewport, 1.0f, 1.0, Occlusion());
 814   pending_child_layer->LowResTiling()->ComputeTilePriorityRects(
 815       viewport, 1.0f, 1.0, Occlusion());
 816
 817   active_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 818                                                            Occlusion());
 819   active_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 820                                                           Occlusion());
 821   active_child_layer->HighResTiling()->ComputeTilePriorityRects(
 822       viewport, 1.0f, 1.0, Occlusion());
 823   active_child_layer->LowResTiling()->ComputeTilePriorityRects(
 824       viewport, 1.0f, 1.0, Occlusion());
 825
 826   // Populate all tiles directly from the tilings.
 827   all_tiles.clear();
 828   std::vector<Tile*> pending_high_res_tiles =
 829       pending_layer_->HighResTiling()->AllTilesForTesting();
 830   all_tiles.insert(pending_high_res_tiles.begin(),
 831                    pending_high_res_tiles.end());
 832
 833   std::vector<Tile*> pending_low_res_tiles =
 834       pending_layer_->LowResTiling()->AllTilesForTesting();
 835   all_tiles.insert(pending_low_res_tiles.begin(), pending_low_res_tiles.end());
 836
 837   // Set all tiles on the pending_child_layer as occluded on the pending tree.
 838   std::vector<Tile*> pending_child_high_res_tiles =
 839       pending_child_layer->HighResTiling()->AllTilesForTesting();
 840   pending_child_layer->HighResTiling()->SetAllTilesOccludedForTesting();
 841   active_child_layer->HighResTiling()->SetAllTilesOccludedForTesting();
 842   all_tiles.insert(pending_child_high_res_tiles.begin(),
 843                    pending_child_high_res_tiles.end());
 844
 845   std::vector<Tile*> pending_child_low_res_tiles =
 846       pending_child_layer->LowResTiling()->AllTilesForTesting();
 847   pending_child_layer->LowResTiling()->SetAllTilesOccludedForTesting();
 848   active_child_layer->LowResTiling()->SetAllTilesOccludedForTesting();
 849   all_tiles.insert(pending_child_low_res_tiles.begin(),
 850                    pending_child_low_res_tiles.end());
 851
 852   tile_manager()->InitializeTilesWithResourcesForTesting(
 853       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 854
 855   // Verify occlusion is considered by EvictionTilePriorityQueue.
 856   TreePriority tree_priority = NEW_CONTENT_TAKES_PRIORITY;
 857   size_t occluded_count = 0u;
 858   Tile* last_tile = NULL;
 859   scoped_ptr<EvictionTilePriorityQueue> queue(
 860       host_impl_.BuildEvictionQueue(tree_priority));
 861   while (!queue->IsEmpty()) {
 862     Tile* tile = queue->Top();
 863     if (!last_tile)
 864       last_tile = tile;
 865
 866     bool tile_is_occluded = tile->is_occluded_combined();
 867
 868     // The only way we will encounter an occluded tile after an unoccluded
 869     // tile is if the priorty bin decreased, the tile is required for
 870     // activation, or the scale changed.
 871     if (tile_is_occluded) {
 872       occluded_count++;
 873
 874       bool last_tile_is_occluded = last_tile->is_occluded_combined();
 875       if (!last_tile_is_occluded) {
 876         TilePriority::PriorityBin tile_priority_bin =
 877             tile->priority_for_tree_priority(tree_priority).priority_bin;
 878         TilePriority::PriorityBin last_tile_priority_bin =
 879             last_tile->priority_for_tree_priority(tree_priority).priority_bin;
 880
 881         EXPECT_TRUE((tile_priority_bin < last_tile_priority_bin) ||
 882                     tile->required_for_activation() ||
 883                     (tile->contents_scale() != last_tile->contents_scale()));
 884       }
 885     }
 886     last_tile = tile;
 887     queue->Pop();
 888   }
 889   size_t expected_occluded_count =
 890       pending_child_high_res_tiles.size() + pending_child_low_res_tiles.size();
 891   EXPECT_EQ(expected_occluded_count, occluded_count);
 892 }
 893
 894 TEST_F(TileManagerTilePriorityQueueTest,
 895        EvictionTilePriorityQueueWithTransparentLayer) {
 896   base::TimeTicks time_ticks;
 897   time_ticks += base::TimeDelta::FromMilliseconds(1);
 898   host_impl_.SetCurrentBeginFrameArgs(
 899       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 900
 901   gfx::Size tile_size(102, 102);
 902   gfx::Size layer_bounds(1000, 1000);
 903
 904   scoped_refptr<FakePicturePileImpl> pending_pile =
 905       FakePicturePileImpl::CreateFilledPile(tile_size, layer_bounds);
 906   SetupPendingTree(pending_pile);
 907
 908   scoped_ptr<FakePictureLayerImpl> pending_child =
 909       FakePictureLayerImpl::CreateWithRasterSource(host_impl_.pending_tree(), 2,
 910                                                    pending_pile);
 911   FakePictureLayerImpl* pending_child_layer = pending_child.get();
 912   pending_layer_->AddChild(pending_child.Pass());
 913
 914   // Create a fully transparent child layer so that its tile priorities are not
 915   // considered to be valid.
 916   pending_child_layer->SetDrawsContent(true);
 917
 918   time_ticks += base::TimeDelta::FromMilliseconds(1);
 919   host_impl_.SetCurrentBeginFrameArgs(
 920       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 921   bool update_lcd_text = false;
 922   host_impl_.pending_tree()->UpdateDrawProperties(update_lcd_text);
 923
 924   pending_child_layer->SetOpacity(0.0);
 925
 926   time_ticks += base::TimeDelta::FromMilliseconds(1);
 927   host_impl_.SetCurrentBeginFrameArgs(
 928       CreateBeginFrameArgsForTesting(BEGINFRAME_FROM_HERE, time_ticks));
 929   host_impl_.pending_tree()->UpdateDrawProperties(update_lcd_text);
 930
 931   // Renew all of the tile priorities.
 932   gfx::Rect viewport(layer_bounds);
 933   pending_layer_->HighResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 934                                                             Occlusion());
 935   pending_layer_->LowResTiling()->ComputeTilePriorityRects(viewport, 1.0f, 1.0,
 936                                                            Occlusion());
 937   pending_child_layer->HighResTiling()->ComputeTilePriorityRects(
 938       viewport, 1.0f, 1.0, Occlusion());
 939   pending_child_layer->LowResTiling()->ComputeTilePriorityRects(
 940       viewport, 1.0f, 1.0, Occlusion());
 941
 942   // Populate all tiles directly from the tilings.
 943   std::set<Tile*> all_pending_tiles;
 944   std::vector<Tile*> pending_high_res_tiles =
 945       pending_layer_->HighResTiling()->AllTilesForTesting();
 946   all_pending_tiles.insert(pending_high_res_tiles.begin(),
 947                            pending_high_res_tiles.end());
 948   EXPECT_EQ(16u, pending_high_res_tiles.size());
 949
 950   std::vector<Tile*> pending_low_res_tiles =
 951       pending_layer_->LowResTiling()->AllTilesForTesting();
 952   all_pending_tiles.insert(pending_low_res_tiles.begin(),
 953                            pending_low_res_tiles.end());
 954   EXPECT_EQ(1u, pending_low_res_tiles.size());
 955
 956   std::set<Tile*> all_pending_child_tiles;
 957   std::vector<Tile*> pending_child_high_res_tiles =
 958       pending_child_layer->HighResTiling()->AllTilesForTesting();
 959   all_pending_child_tiles.insert(pending_child_high_res_tiles.begin(),
 960                                  pending_child_high_res_tiles.end());
 961   EXPECT_EQ(16u, pending_child_high_res_tiles.size());
 962
 963   std::vector<Tile*> pending_child_low_res_tiles =
 964       pending_child_layer->LowResTiling()->AllTilesForTesting();
 965   all_pending_child_tiles.insert(pending_child_low_res_tiles.begin(),
 966                                  pending_child_low_res_tiles.end());
 967   EXPECT_EQ(1u, pending_child_low_res_tiles.size());
 968
 969   std::set<Tile*> all_tiles = all_pending_tiles;
 970   all_tiles.insert(all_pending_child_tiles.begin(),
 971                    all_pending_child_tiles.end());
 972
 973   tile_manager()->InitializeTilesWithResourcesForTesting(
 974       std::vector<Tile*>(all_tiles.begin(), all_tiles.end()));
 975
 976   EXPECT_TRUE(pending_layer_->HasValidTilePriorities());
 977   EXPECT_FALSE(pending_child_layer->HasValidTilePriorities());
 978
 979   // Verify that eviction queue returns tiles also from layers without valid
 980   // tile priorities and that the tile priority bin of those tiles is (at most)
 981   // EVENTUALLY.
 982   TreePriority tree_priority = NEW_CONTENT_TAKES_PRIORITY;
 983   std::set<Tile*> new_content_tiles;
 984   size_t tile_count = 0;
 985   scoped_ptr<EvictionTilePriorityQueue> queue(
 986       host_impl_.BuildEvictionQueue(tree_priority));
 987   while (!queue->IsEmpty()) {
 988     Tile* tile = queue->Top();
 989     const TilePriority& pending_priority = tile->priority(PENDING_TREE);
 990     EXPECT_NE(std::numeric_limits<float>::infinity(),
 991               pending_priority.distance_to_visible);
 992     if (all_pending_child_tiles.find(tile) != all_pending_child_tiles.end())
 993       EXPECT_EQ(TilePriority::EVENTUALLY, pending_priority.priority_bin);
 994     else
 995       EXPECT_EQ(TilePriority::NOW, pending_priority.priority_bin);
 996     new_content_tiles.insert(tile);
 997     ++tile_count;
 998     queue->Pop();
 999   }
1000   EXPECT_EQ(tile_count, new_content_tiles.size());
1001   EXPECT_EQ(all_tiles, new_content_tiles);
1002 }
1003
1004 TEST_F(TileManagerTilePriorityQueueTest, RasterTilePriorityQueueEmptyLayers) {
1005   const gfx::Size layer_bounds(1000, 1000);
1006   host_impl_.SetViewportSize(layer_bounds);
1007   SetupDefaultTrees(layer_bounds);
1008
1009   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
1010       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
1011   EXPECT_FALSE(queue->IsEmpty());
1012
1013   size_t tile_count = 0;
1014   std::set<Tile*> all_tiles;
1015   while (!queue->IsEmpty()) {
1016     EXPECT_TRUE(queue->Top());
1017     all_tiles.insert(queue->Top());
1018     ++tile_count;
1019     queue->Pop();
1020   }
1021
1022   EXPECT_EQ(tile_count, all_tiles.size());
1023   EXPECT_EQ(16u, tile_count);
1024
1025   for (int i = 1; i < 10; ++i) {
1026     scoped_ptr<FakePictureLayerImpl> pending_layer =
1027         FakePictureLayerImpl::Create(host_impl_.pending_tree(), id_ + i);
1028     pending_layer->SetDrawsContent(true);
1029     pending_layer->set_has_valid_tile_priorities(true);
1030     pending_layer_->AddChild(pending_layer.Pass());
1031   }
1032
1033   queue = host_impl_.BuildRasterQueue(SAME_PRIORITY_FOR_BOTH_TREES,
1034                                       RasterTilePriorityQueue::Type::ALL);
1035   EXPECT_FALSE(queue->IsEmpty());
1036
1037   tile_count = 0;
1038   all_tiles.clear();
1039   while (!queue->IsEmpty()) {
1040     EXPECT_TRUE(queue->Top());
1041     all_tiles.insert(queue->Top());
1042     ++tile_count;
1043     queue->Pop();
1044   }
1045   EXPECT_EQ(tile_count, all_tiles.size());
1046   EXPECT_EQ(16u, tile_count);
1047 }
1048
1049 TEST_F(TileManagerTilePriorityQueueTest, EvictionTilePriorityQueueEmptyLayers) {
1050   const gfx::Size layer_bounds(1000, 1000);
1051   host_impl_.SetViewportSize(layer_bounds);
1052   SetupDefaultTrees(layer_bounds);
1053
1054   scoped_ptr<RasterTilePriorityQueue> raster_queue(host_impl_.BuildRasterQueue(
1055       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
1056   EXPECT_FALSE(raster_queue->IsEmpty());
1057
1058   size_t tile_count = 0;
1059   std::set<Tile*> all_tiles;
1060   while (!raster_queue->IsEmpty()) {
1061     EXPECT_TRUE(raster_queue->Top());
1062     all_tiles.insert(raster_queue->Top());
1063     ++tile_count;
1064     raster_queue->Pop();
1065   }
1066   EXPECT_EQ(tile_count, all_tiles.size());
1067   EXPECT_EQ(16u, tile_count);
1068
1069   std::vector<Tile*> tiles(all_tiles.begin(), all_tiles.end());
1070   host_impl_.tile_manager()->InitializeTilesWithResourcesForTesting(tiles);
1071
1072   for (int i = 1; i < 10; ++i) {
1073     scoped_ptr<FakePictureLayerImpl> pending_layer =
1074         FakePictureLayerImpl::Create(host_impl_.pending_tree(), id_ + i);
1075     pending_layer->SetDrawsContent(true);
1076     pending_layer->set_has_valid_tile_priorities(true);
1077     pending_layer_->AddChild(pending_layer.Pass());
1078   }
1079
1080   scoped_ptr<EvictionTilePriorityQueue> queue(
1081       host_impl_.BuildEvictionQueue(SAME_PRIORITY_FOR_BOTH_TREES));
1082   EXPECT_FALSE(queue->IsEmpty());
1083
1084   tile_count = 0;
1085   all_tiles.clear();
1086   while (!queue->IsEmpty()) {
1087     EXPECT_TRUE(queue->Top());
1088     all_tiles.insert(queue->Top());
1089     ++tile_count;
1090     queue->Pop();
1091   }
1092   EXPECT_EQ(tile_count, all_tiles.size());
1093   EXPECT_EQ(16u, tile_count);
1094 }
1095
1096 TEST_F(TileManagerTilePriorityQueueTest,
1097        RasterTilePriorityQueueStaticViewport) {
1098   FakePictureLayerTilingClient client;
1099
1100   gfx::Rect viewport(50, 50, 500, 500);
1101   gfx::Size layer_bounds(1600, 1600);
1102
1103   float inset = PictureLayerTiling::CalculateSoonBorderDistance(viewport, 1.0f);
1104   gfx::Rect soon_rect = viewport;
1105   soon_rect.Inset(-inset, -inset);
1106
1107   client.SetTileSize(gfx::Size(30, 30));
1108   client.set_tree(ACTIVE_TREE);
1109   LayerTreeSettings settings;
1110   settings.max_tiles_for_interest_area = 10000;
1111
1112   scoped_ptr<PictureLayerTilingSet> tiling_set = PictureLayerTilingSet::Create(
1113       &client, settings.max_tiles_for_interest_area,
1114       settings.skewport_target_time_in_seconds,
1115       settings.skewport_extrapolation_limit_in_content_pixels);
1116
1117   scoped_refptr<FakePicturePileImpl> pile =
1118       FakePicturePileImpl::CreateFilledPileWithDefaultTileSize(layer_bounds);
1119   PictureLayerTiling* tiling = tiling_set->AddTiling(1.0f, pile);
1120   tiling->set_resolution(HIGH_RESOLUTION);
1121
1122   tiling_set->UpdateTilePriorities(viewport, 1.0f, 1.0, Occlusion(), true);
1123   std::vector<Tile*> all_tiles = tiling->AllTilesForTesting();
1124   // Sanity check.
1125   EXPECT_EQ(3364u, all_tiles.size());
1126
1127   // The explanation of each iteration is as follows:
1128   // 1. First iteration tests that we can get all of the tiles correctly.
1129   // 2. Second iteration ensures that we can get all of the tiles again (first
1130   //    iteration didn't change any tiles), as well set all tiles to be ready to
1131   //    draw.
1132   // 3. Third iteration ensures that no tiles are returned, since they were all
1133   //    marked as ready to draw.
1134   for (int i = 0; i < 3; ++i) {
1135     scoped_ptr<TilingSetRasterQueueAll> queue(
1136         new TilingSetRasterQueueAll(tiling_set.get(), false));
1137
1138     // There are 3 bins in TilePriority.
1139     bool have_tiles[3] = {};
1140
1141     // On the third iteration, we should get no tiles since everything was
1142     // marked as ready to draw.
1143     if (i == 2) {
1144       EXPECT_TRUE(queue->IsEmpty());
1145       continue;
1146     }
1147
1148     EXPECT_FALSE(queue->IsEmpty());
1149     std::set<Tile*> unique_tiles;
1150     unique_tiles.insert(queue->Top());
1151     Tile* last_tile = queue->Top();
1152     have_tiles[last_tile->priority(ACTIVE_TREE).priority_bin] = true;
1153
1154     // On the second iteration, mark everything as ready to draw (solid color).
1155     if (i == 1) {
1156       TileDrawInfo& draw_info = last_tile->draw_info();
1157       draw_info.SetSolidColorForTesting(SK_ColorRED);
1158     }
1159     queue->Pop();
1160     int eventually_bin_order_correct_count = 0;
1161     int eventually_bin_order_incorrect_count = 0;
1162     while (!queue->IsEmpty()) {
1163       Tile* new_tile = queue->Top();
1164       queue->Pop();
1165       unique_tiles.insert(new_tile);
1166
1167       TilePriority last_priority = last_tile->priority(ACTIVE_TREE);
1168       TilePriority new_priority = new_tile->priority(ACTIVE_TREE);
1169       EXPECT_LE(last_priority.priority_bin, new_priority.priority_bin);
1170       if (last_priority.priority_bin == new_priority.priority_bin) {
1171         if (last_priority.priority_bin == TilePriority::EVENTUALLY) {
1172           bool order_correct = last_priority.distance_to_visible <=
1173                                new_priority.distance_to_visible;
1174           eventually_bin_order_correct_count += order_correct;
1175           eventually_bin_order_incorrect_count += !order_correct;
1176         } else if (!soon_rect.Intersects(new_tile->content_rect()) &&
1177                    !soon_rect.Intersects(last_tile->content_rect())) {
1178           EXPECT_LE(last_priority.distance_to_visible,
1179                     new_priority.distance_to_visible);
1180           EXPECT_EQ(TilePriority::NOW, new_priority.priority_bin);
1181         } else if (new_priority.distance_to_visible > 0.f) {
1182           EXPECT_EQ(TilePriority::SOON, new_priority.priority_bin);
1183         }
1184       }
1185       have_tiles[new_priority.priority_bin] = true;
1186
1187       last_tile = new_tile;
1188
1189       // On the second iteration, mark everything as ready to draw (solid
1190       // color).
1191       if (i == 1) {
1192         TileDrawInfo& draw_info = last_tile->draw_info();
1193         draw_info.SetSolidColorForTesting(SK_ColorRED);
1194       }
1195     }
1196
1197     EXPECT_GT(eventually_bin_order_correct_count,
1198               eventually_bin_order_incorrect_count);
1199
1200     // We should have now and eventually tiles, as well as soon tiles from
1201     // the border region.
1202     EXPECT_TRUE(have_tiles[TilePriority::NOW]);
1203     EXPECT_TRUE(have_tiles[TilePriority::SOON]);
1204     EXPECT_TRUE(have_tiles[TilePriority::EVENTUALLY]);
1205
1206     EXPECT_EQ(unique_tiles.size(), all_tiles.size());
1207   }
1208 }
1209
1210 TEST_F(TileManagerTilePriorityQueueTest,
1211        RasterTilePriorityQueueMovingViewport) {
1212   FakePictureLayerTilingClient client;
1213
1214   gfx::Rect viewport(50, 0, 100, 100);
1215   gfx::Rect moved_viewport(50, 0, 100, 500);
1216   gfx::Size layer_bounds(1000, 1000);
1217
1218   client.SetTileSize(gfx::Size(30, 30));
1219   client.set_tree(ACTIVE_TREE);
1220   LayerTreeSettings settings;
1221   settings.max_tiles_for_interest_area = 10000;
1222
1223   scoped_ptr<PictureLayerTilingSet> tiling_set = PictureLayerTilingSet::Create(
1224       &client, settings.max_tiles_for_interest_area,
1225       settings.skewport_target_time_in_seconds,
1226       settings.skewport_extrapolation_limit_in_content_pixels);
1227
1228   scoped_refptr<FakePicturePileImpl> pile =
1229       FakePicturePileImpl::CreateFilledPileWithDefaultTileSize(layer_bounds);
1230   PictureLayerTiling* tiling = tiling_set->AddTiling(1.0f, pile);
1231   tiling->set_resolution(HIGH_RESOLUTION);
1232
1233   tiling_set->UpdateTilePriorities(viewport, 1.0f, 1.0, Occlusion(), true);
1234   tiling_set->UpdateTilePriorities(moved_viewport, 1.0f, 2.0, Occlusion(),
1235                                    true);
1236
1237   float inset =
1238       PictureLayerTiling::CalculateSoonBorderDistance(moved_viewport, 1.0f);
1239   gfx::Rect soon_rect = moved_viewport;
1240   soon_rect.Inset(-inset, -inset);
1241
1242   // There are 3 bins in TilePriority.
1243   bool have_tiles[3] = {};
1244   Tile* last_tile = NULL;
1245   int eventually_bin_order_correct_count = 0;
1246   int eventually_bin_order_incorrect_count = 0;
1247   scoped_ptr<TilingSetRasterQueueAll> queue(
1248       new TilingSetRasterQueueAll(tiling_set.get(), false));
1249   for (; !queue->IsEmpty(); queue->Pop()) {
1250     if (!last_tile)
1251       last_tile = queue->Top();
1252
1253     Tile* new_tile = queue->Top();
1254
1255     TilePriority last_priority = last_tile->priority(ACTIVE_TREE);
1256     TilePriority new_priority = new_tile->priority(ACTIVE_TREE);
1257
1258     have_tiles[new_priority.priority_bin] = true;
1259
1260     EXPECT_LE(last_priority.priority_bin, new_priority.priority_bin);
1261     if (last_priority.priority_bin == new_priority.priority_bin) {
1262       if (last_priority.priority_bin == TilePriority::EVENTUALLY) {
1263         bool order_correct = last_priority.distance_to_visible <=
1264                              new_priority.distance_to_visible;
1265         eventually_bin_order_correct_count += order_correct;
1266         eventually_bin_order_incorrect_count += !order_correct;
1267       } else if (!soon_rect.Intersects(new_tile->content_rect()) &&
1268                  !soon_rect.Intersects(last_tile->content_rect())) {
1269         EXPECT_LE(last_priority.distance_to_visible,
1270                   new_priority.distance_to_visible);
1271       } else if (new_priority.distance_to_visible > 0.f) {
1272         EXPECT_EQ(TilePriority::SOON, new_priority.priority_bin);
1273       }
1274     }
1275     last_tile = new_tile;
1276   }
1277
1278   EXPECT_GT(eventually_bin_order_correct_count,
1279             eventually_bin_order_incorrect_count);
1280
1281   EXPECT_TRUE(have_tiles[TilePriority::NOW]);
1282   EXPECT_TRUE(have_tiles[TilePriority::SOON]);
1283   EXPECT_TRUE(have_tiles[TilePriority::EVENTUALLY]);
1284 }
1285
1286 TEST_F(TileManagerTilePriorityQueueTest, SetIsLikelyToRequireADraw) {
1287   const gfx::Size layer_bounds(1000, 1000);
1288   host_impl_.SetViewportSize(layer_bounds);
1289   SetupDefaultTrees(layer_bounds);
1290
1291   // Verify that the queue has a required for draw tile at Top.
1292   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
1293       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
1294   EXPECT_FALSE(queue->IsEmpty());
1295   EXPECT_TRUE(queue->Top()->required_for_draw());
1296
1297   EXPECT_FALSE(host_impl_.is_likely_to_require_a_draw());
1298   host_impl_.tile_manager()->PrepareTiles(host_impl_.global_tile_state());
1299   EXPECT_TRUE(host_impl_.is_likely_to_require_a_draw());
1300 }
1301
1302 TEST_F(TileManagerTilePriorityQueueTest,
1303        SetIsLikelyToRequireADrawOnZeroMemoryBudget) {
1304   const gfx::Size layer_bounds(1000, 1000);
1305   host_impl_.SetViewportSize(layer_bounds);
1306   SetupDefaultTrees(layer_bounds);
1307
1308   // Verify that the queue has a required for draw tile at Top.
1309   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
1310       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
1311   EXPECT_FALSE(queue->IsEmpty());
1312   EXPECT_TRUE(queue->Top()->required_for_draw());
1313
1314   ManagedMemoryPolicy policy = host_impl_.ActualManagedMemoryPolicy();
1315   policy.bytes_limit_when_visible = 0;
1316   host_impl_.SetMemoryPolicy(policy);
1317
1318   EXPECT_FALSE(host_impl_.is_likely_to_require_a_draw());
1319   host_impl_.tile_manager()->PrepareTiles(host_impl_.global_tile_state());
1320   EXPECT_FALSE(host_impl_.is_likely_to_require_a_draw());
1321 }
1322
1323 TEST_F(TileManagerTilePriorityQueueTest,
1324        SetIsLikelyToRequireADrawOnLimitedMemoryBudget) {
1325   const gfx::Size layer_bounds(1000, 1000);
1326   host_impl_.SetViewportSize(layer_bounds);
1327   SetupDefaultTrees(layer_bounds);
1328
1329   // Verify that the queue has a required for draw tile at Top.
1330   scoped_ptr<RasterTilePriorityQueue> queue(host_impl_.BuildRasterQueue(
1331       SAME_PRIORITY_FOR_BOTH_TREES, RasterTilePriorityQueue::Type::ALL));
1332   EXPECT_FALSE(queue->IsEmpty());
1333   EXPECT_TRUE(queue->Top()->required_for_draw());
1334   EXPECT_EQ(gfx::Size(256, 256), queue->Top()->desired_texture_size());
1335   EXPECT_EQ(RGBA_8888, host_impl_.resource_provider()->best_texture_format());
1336
1337   ManagedMemoryPolicy policy = host_impl_.ActualManagedMemoryPolicy();
1338   policy.bytes_limit_when_visible =
1339       Resource::MemorySizeBytes(gfx::Size(256, 256), RGBA_8888);
1340   host_impl_.SetMemoryPolicy(policy);
1341
1342   EXPECT_FALSE(host_impl_.is_likely_to_require_a_draw());
1343   host_impl_.tile_manager()->PrepareTiles(host_impl_.global_tile_state());
1344   EXPECT_TRUE(host_impl_.is_likely_to_require_a_draw());
1345
1346   scoped_ptr<ScopedResource> resource =
1347       host_impl_.resource_pool()->AcquireResource(gfx::Size(256, 256),
1348                                                   RGBA_8888);
1349
1350   host_impl_.tile_manager()->CheckIfMoreTilesNeedToBePreparedForTesting();
1351   EXPECT_FALSE(host_impl_.is_likely_to_require_a_draw());
1352
1353   host_impl_.resource_pool()->ReleaseResource(resource.Pass());
1354 }
1355
1356 }  // namespace
1357 }  // namespace cc