cc: Implement geometry-based tile eviction

cc/layers/picture_layer_impl_unittest.cc

Index: cc/layers/picture_layer_impl_unittest.cc
diff --git a/cc/layers/picture_layer_impl_unittest.cc b/cc/layers/picture_layer_impl_unittest.cc
index d18e97a553baaf9bf7e99432f33a2e7d80615918..5a6455bcc8c3dafb86147676668e8e8907d8bdc4 100644
--- a/cc/layers/picture_layer_impl_unittest.cc
+++ b/cc/layers/picture_layer_impl_unittest.cc
@@ -2976,6 +2976,8 @@ TEST_F(PictureLayerImplTest, TilingSetEvictionQueue) {
   size_t scale_index = 0;
   bool reached_visible = false;
   Tile* last_tile = nullptr;
+  int distance_decreasing = 0;
+  int distance_increasing = 0;
   queue = pending_layer_->CreateEvictionQueue(SAME_PRIORITY_FOR_BOTH_TREES);
   while (!queue->IsEmpty()) {
     Tile* tile = queue->Top();
@@ -3003,22 +3005,26 @@ TEST_F(PictureLayerImplTest, TilingSetEvictionQueue) {
     EXPECT_FLOAT_EQ(tile->contents_scale(), expected_scales[scale_index]);
     unique_tiles.insert(tile);
 
-    // If the tile is the same rough bin as last tile (same activation, bin, and
-    // scale), then distance should be decreasing.
     if (tile->required_for_activation() ==
             last_tile->required_for_activation() &&
         priority.priority_bin ==
             last_tile->priority(PENDING_TREE).priority_bin &&
         std::abs(tile->contents_scale() - last_tile->contents_scale()) <
             std::numeric_limits<float>::epsilon()) {
-      EXPECT_LE(priority.distance_to_visible,
-                last_tile->priority(PENDING_TREE).distance_to_visible);
+      if (priority.distance_to_visible <=
+          last_tile->priority(PENDING_TREE).distance_to_visible)
+        ++distance_decreasing;
+      else
+        ++distance_increasing;
     }
 
     last_tile = tile;
     queue->Pop();
   }
 
+  EXPECT_EQ(7, distance_increasing);
+  EXPECT_EQ(55, distance_decreasing);
+
   EXPECT_TRUE(reached_visible);
   EXPECT_EQ(65u, unique_tiles.size());
 
@@ -3828,14 +3834,17 @@ class OcclusionTrackingPictureLayerImplTest : public PictureLayerImplTest {
   OcclusionTrackingPictureLayerImplTest()
       : PictureLayerImplTest(OcclusionTrackingSettings()) {}
 
-  void VerifyEvictionConsidersOcclusion(
-      PictureLayerImpl* layer,
-      size_t expected_occluded_tile_count[NUM_TREE_PRIORITIES]) {
+  void VerifyEvictionConsidersOcclusion(FakePictureLayerImpl* layer,
+                                        FakePictureLayerImpl* twin_layer,
+                                        WhichTree tree,
+                                        size_t expected_occluded_tile_count) {
+    twin_layer->set_has_valid_tile_priorities(false);
     for (int priority_count = 0; priority_count < NUM_TREE_PRIORITIES;
          ++priority_count) {
       TreePriority tree_priority = static_cast<TreePriority>(priority_count);
       size_t occluded_tile_count = 0u;
       Tile* last_tile = nullptr;
+      std::set<Tile*> shared_tiles;
 
       scoped_ptr<TilingSetEvictionQueue> queue =
           layer->CreateEvictionQueue(tree_priority);
@@ -3843,23 +3852,22 @@ class OcclusionTrackingPictureLayerImplTest : public PictureLayerImplTest {
         Tile* tile = queue->Top();
         if (!last_tile)
           last_tile = tile;
+        if (tile->is_shared())
+          EXPECT_TRUE(shared_tiles.insert(tile).second);
 
         // The only way we will encounter an occluded tile after an unoccluded
         // tile is if the priorty bin decreased, the tile is required for
         // activation, or the scale changed.
-        bool tile_is_occluded =
-            tile->is_occluded_for_tree_priority(tree_priority);
+        bool tile_is_occluded = tile->is_occluded(tree);
         if (tile_is_occluded) {
           occluded_tile_count++;
 
-          bool last_tile_is_occluded =
-              last_tile->is_occluded_for_tree_priority(tree_priority);
+          bool last_tile_is_occluded = last_tile->is_occluded(tree);
           if (!last_tile_is_occluded) {
             TilePriority::PriorityBin tile_priority_bin =
-                tile->priority_for_tree_priority(tree_priority).priority_bin;
+                tile->priority(tree).priority_bin;
             TilePriority::PriorityBin last_tile_priority_bin =
-                last_tile->priority_for_tree_priority(tree_priority)
-                    .priority_bin;
+                last_tile->priority(tree).priority_bin;
 
             EXPECT_TRUE(
                 (tile_priority_bin < last_tile_priority_bin) ||
@@ -3870,9 +3878,19 @@ class OcclusionTrackingPictureLayerImplTest : public PictureLayerImplTest {
         last_tile = tile;
         queue->Pop();
       }
-      EXPECT_EQ(expected_occluded_tile_count[priority_count],
-                occluded_tile_count);
+      queue = twin_layer->CreateEvictionQueue(tree_priority);
+      while (!queue->IsEmpty()) {
+        Tile* tile = queue->Top();
+        if (tile->is_shared()) {
+          EXPECT_TRUE(shared_tiles.insert(tile).second);
+          if (tile->is_occluded(tree))

[vmpstr, 2014/12/09 02:10:58]

This should happen outside of the if (is shared) block

[USE eero AT chromium.org, 2014/12/09 18:44:14]

No, it should not.
The purpose of this second while loop is to count tiles which are occluded and
which belong to the layer (passed as the first parameter) but which are not
returned by the first eviction queue. This can happen for tiles which are shared
and those priority for tree priority is closer to the priority for the twin tree
and therefore they would be out of order tiles if they were returned by the
first eviction queue. So they are returned by the twin eviction queue.

My idea here was to modify unit tests as little as possible. Therefore I did not
modify numbers such as expected_occluded_tile_count. If you would like a
different approach, please say so.

[vmpstr, 2014/12/10 18:01:15]

I think that makes sense, thanks for the explanation. Can you leave a comment
explaining this? At a first glance, it seems that we're ignoring unshared tiles
erroneously. 

[USE eero AT chromium.org, 2014/12/11 15:21:59]

Done.

+            ++occluded_tile_count;
+        }
+        queue->Pop();
+      }
+      EXPECT_EQ(expected_occluded_tile_count, occluded_tile_count);
     }
+    twin_layer->set_has_valid_tile_priorities(true);
   }
 };
 
@@ -4345,11 +4363,7 @@ TEST_F(OcclusionTrackingPictureLayerImplTest,
   size_t expected_occluded_tile_count_on_active[] = {30u, 5u, 4u, 2u, 2u};
   size_t expected_occluded_tile_count_on_pending[] = {30u, 5u, 4u, 2u, 2u};
 
-  // The total expected number of occluded tiles on all tilings for each of the
-  // 3 tree priorities.
-  size_t total_expected_occluded_tile_count[] = {13u, 43u, 43u};
-
-  ASSERT_EQ(arraysize(total_expected_occluded_tile_count), NUM_TREE_PRIORITIES);
+  size_t total_expected_occluded_tile_count_on_trees[] = {43u, 43u};
 
   // Verify number of occluded tiles on the pending layer for each tiling.
   for (size_t i = 0; i < pending_layer_->num_tilings(); ++i) {
@@ -4432,10 +4446,12 @@ TEST_F(OcclusionTrackingPictureLayerImplTest,
 
   host_impl_.tile_manager()->InitializeTilesWithResourcesForTesting(all_tiles);
 
-  VerifyEvictionConsidersOcclusion(pending_layer_,
-                                   total_expected_occluded_tile_count);
-  VerifyEvictionConsidersOcclusion(active_layer_,
-                                   total_expected_occluded_tile_count);
+  VerifyEvictionConsidersOcclusion(
+      pending_layer_, active_layer_, PENDING_TREE,
+      total_expected_occluded_tile_count_on_trees[PENDING_TREE]);
+  VerifyEvictionConsidersOcclusion(
+      active_layer_, pending_layer_, ACTIVE_TREE,
+      total_expected_occluded_tile_count_on_trees[ACTIVE_TREE]);
 }
 
 TEST_F(PictureLayerImplTest, PendingOrActiveTwinLayer) {