Revert "Revert "Allow clipping by scroll parents." and "Improve perf of CalculateDrawPropertiesInternal when there are no scroll parents.""

This reverts commit 97ada322de9f492e3f0d1741ac117fc42599451b.

This was a speculative perf revert; seems not to be the issue. Relanding.

Local tests with and without this patch on a Nexus 4 with and without my patch didn't show a perf regression (in fact, perf seemed to mysteriously improve -- I assume this is noise).

TBR=danakj@chromium.org
BUG=306926

Review URL: https://codereview.chromium.org/26135005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@229221 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 792 insertions, 12 deletions

diff --git a/cc/layers/draw_properties.h b/cc/layers/draw_properties.h
index 06c8834..b81bec7 100644
--- a/cc/layers/draw_properties.h
+++ b/cc/layers/draw_properties.h
@@ -29,7 +29,13 @@ struct CC_EXPORT DrawProperties {
         num_descendants_that_draw_content(0),
         num_unclipped_descendants(0),
         can_draw_directly_to_backbuffer(false),
-        layer_or_descendant_has_copy_request(false) {}
+        layer_or_descendant_has_copy_request(false),
+        has_child_with_a_scroll_parent(false),
+        sorted_for_recursion(false),
+        index_of_first_descendants_addition(0),
+        num_descendants_added(0),
+        index_of_first_render_surface_layer_list_addition(0),
+        num_render_surfaces_added(0) {}
 
   // Transforms objects from content space to target surface space, where
   // this layer would be drawn.
@@ -97,6 +103,24 @@ struct CC_EXPORT DrawProperties {
   // If true, the layer or some layer in its sub-tree has a CopyOutputRequest
   // present on it.
   bool layer_or_descendant_has_copy_request;
+
+  // This is true if the layer has any direct child that has a scroll parent.
+  // This layer will not be the scroll parent in this case. This information
+  // lets us avoid work in CalculateDrawPropertiesInternal -- if none of our
+  // children have scroll parents, we will not need to recur out of order.
+  bool has_child_with_a_scroll_parent;
+
+  // This is true if the order (wrt to its siblings in the tree) in which the
+  // layer will be visited while computing draw properties has been determined.
+  bool sorted_for_recursion;
+
+  // If this layer is visited out of order, its contribution to the descendant
+  // and render surface layer lists will be put aside in a temporary list.
+  // These values will allow for an efficient reordering of these additions.
+  size_t index_of_first_descendants_addition;
+  size_t num_descendants_added;
+  size_t index_of_first_render_surface_layer_list_addition;
+  size_t num_render_surfaces_added;
 };
 
 }  // namespace cc
diff --git a/cc/trees/layer_tree_host_common.cc b/cc/trees/layer_tree_host_common.cc
index 5e9ac7f..c9d453f 100644
--- a/cc/trees/layer_tree_host_common.cc
+++ b/cc/trees/layer_tree_host_common.cc
@@ -170,7 +170,11 @@ static void UpdateClipRectsForClipChild(
   // If the layer has no clip_parent, or the ancestor is the same as its actual
   // parent, then we don't need special clip rects. Bail now and leave the out
   // parameters untouched.
-  const LayerType* clip_parent = layer->clip_parent();
+  const LayerType* clip_parent = layer->scroll_parent();
+
+  if (!clip_parent)
+    clip_parent = layer->clip_parent();
+
   if (!clip_parent || clip_parent == layer->parent())
     return;
 
@@ -187,12 +191,25 @@ static void UpdateClipRectsForClipChild(
   // wanted to. But more importantly, this matches the expectations of
   // CalculateDrawPropertiesInternal. If we, say, create a render surface, these
   // clip rects will want to be in its target space, not ours.
-  *clip_rect_in_parent_target_space =
-      TranslateRectToTargetSpace<LayerType, RenderSurfaceType>(
-          *clip_parent,
-          *layer->parent(),
-          *clip_rect_in_parent_target_space,
-          TranslateRectDirectionToDescendant);
+  if (clip_parent == layer->clip_parent()) {
+    *clip_rect_in_parent_target_space =
+        TranslateRectToTargetSpace<LayerType, RenderSurfaceType>(
+            *clip_parent,
+            *layer->parent(),
+            *clip_rect_in_parent_target_space,
+            TranslateRectDirectionToDescendant);
+  } else {
+    // If we're being clipped by our scroll parent, we must translate through
+    // our common ancestor. This happens to be our parent, so it is sufficent to
+    // translate from our clip parent's space to the space of its ancestor (our
+    // parent).
+    *clip_rect_in_parent_target_space =
+        TranslateRectToTargetSpace<LayerType, RenderSurfaceType>(
+            *layer->parent(),
+            *clip_parent,
+            *clip_rect_in_parent_target_space,
+            TranslateRectDirectionToAncestor);
+  }
 }
 
 // We collect an accumulated drawable content rect per render surface.
@@ -1045,6 +1062,9 @@ static void PreCalculateMetaInformation(
     num_descendants_that_draw_content = 1000;
   }
 
+  layer->draw_properties().sorted_for_recursion = false;
+  layer->draw_properties().has_child_with_a_scroll_parent = false;
+
   if (layer->clip_parent())
     recursive_data->num_unclipped_descendants++;
 
@@ -1059,6 +1079,8 @@ static void PreCalculateMetaInformation(
     num_descendants_that_draw_content +=
         child_layer->draw_properties().num_descendants_that_draw_content;
 
+    if (child_layer->scroll_parent())
+      layer->draw_properties().has_child_with_a_scroll_parent = true;
     recursive_data->Merge(data_for_child);
   }
 
@@ -1134,6 +1156,117 @@ struct DataForRecursion {
   bool subtree_is_visible_from_ancestor;
 };
 
+template <typename LayerType>
+static LayerType* GetChildContainingLayer(const LayerType& parent,
+                                          LayerType* layer) {
+  for (LayerType* ancestor = layer; ancestor; ancestor = ancestor->parent()) {
+    if (ancestor->parent() == &parent)
+      return ancestor;
+  }
+  NOTREACHED();
+  return 0;
+}
+
+template <typename LayerType>
+static void AddScrollParentChain(std::vector<LayerType*>* out,
+                                 const LayerType& parent,
+                                 LayerType* layer) {
+  // At a high level, this function walks up the chain of scroll parents
+  // recursively, and once we reach the end of the chain, we add the child
+  // of |parent| containing each scroll ancestor as we unwind. The result is
+  // an ordering of parent's children that ensures that scroll parents are
+  // visited before their descendants.
+  // Take for example this layer tree:
+  //
+  // + stacking_context
+  //   + scroll_child (1)
+  //   + scroll_parent_graphics_layer (*)
+  //   | + scroll_parent_scrolling_layer
+  //   |   + scroll_parent_scrolling_content_layer (2)
+  //   + scroll_grandparent_graphics_layer (**)
+  //     + scroll_grandparent_scrolling_layer
+  //       + scroll_grandparent_scrolling_content_layer (3)
+  //
+  // The scroll child is (1), its scroll parent is (2) and its scroll
+  // grandparent is (3). Note, this doesn't mean that (2)'s scroll parent is
+  // (3), it means that (*)'s scroll parent is (3). We don't want our list to
+  // look like [ (3), (2), (1) ], even though that does have the ancestor chain
+  // in the right order. Instead, we want [ (**), (*), (1) ]. That is, only want
+  // (1)'s siblings in the list, but we want them to appear in such an order
+  // that the scroll ancestors get visited in the correct order.
+  //
+  // So our first task at this step of the recursion is to determine the layer
+  // that we will potentionally add to the list. That is, the child of parent
+  // containing |layer|.
+  LayerType* child = GetChildContainingLayer(parent, layer);
+  if (child->draw_properties().sorted_for_recursion)
+    return;
+
+  if (LayerType* scroll_parent = child->scroll_parent())
+    AddScrollParentChain(out, parent, scroll_parent);
+
+  out->push_back(child);
+  child->draw_properties().sorted_for_recursion = true;
+}
+
+template <typename LayerType>
+static bool SortChildrenForRecursion(std::vector<LayerType*>* out,
+                                     const LayerType& parent) {
+  out->reserve(parent.children().size());
+  bool order_changed = false;
+  for (size_t i = 0; i < parent.children().size(); ++i) {
+    LayerType* current =
+        LayerTreeHostCommon::get_child_as_raw_ptr(parent.children(), i);
+
+    if (current->draw_properties().sorted_for_recursion) {
+      order_changed = true;
+      continue;
+    }
+
+    AddScrollParentChain(out, parent, current);
+  }
+
+  DCHECK_EQ(parent.children().size(), out->size());
+  return order_changed;
+}
+
+template <typename LayerType>
+static void GetNewDescendantsStartIndexAndCount(LayerType* layer,
+                                                size_t* start_index,
+                                                size_t* count) {
+  *start_index = layer->draw_properties().index_of_first_descendants_addition;
+  *count = layer->draw_properties().num_descendants_added;
+}
+
+template <typename LayerType>
+static void GetNewRenderSurfacesStartIndexAndCount(LayerType* layer,
+                                                   size_t* start_index,
+                                                   size_t* count) {
+  *start_index = layer->draw_properties()
+                     .index_of_first_render_surface_layer_list_addition;
+  *count = layer->draw_properties().num_render_surfaces_added;
+}
+
+template <typename LayerType,
+          typename LayerListType,
+          typename GetIndexAndCountType>
+static void AddUnsortedLayerListContributions(
+    const LayerType& parent,
+    const LayerListType& source,
+    LayerListType* target,
+    GetIndexAndCountType get_index_and_count) {
+  for (size_t i = 0; i < parent.children().size(); ++i) {
+    LayerType* child =
+        LayerTreeHostCommon::get_child_as_raw_ptr(parent.children(), i);
+
+    size_t start_index = 0;
+    size_t count = 0;
+    get_index_and_count(child, &start_index, &count);
+    for (size_t j = start_index; j < start_index + count; ++j)
+      target->push_back(source.at(j));
+  }
+}
+
 // Recursively walks the layer tree starting at the given node and computes all
 // the necessary transformations, clip rects, render surfaces, etc.
 template <typename LayerType,
@@ -1760,22 +1893,83 @@ static void CalculateDrawPropertiesInternal(
     data_for_children.subtree_is_visible_from_ancestor = layer_is_visible;
   }
 
+  // These are the layer lists that will be passed to our children to populate.
+  LayerListType* render_surface_layer_list_for_children =
+      render_surface_layer_list;
+  LayerListType* descendants_for_children = &descendants;
+
+  // If we visit our children out of order, we will put their contributions to
+  // descendants and render_surface_layer_list aside during recursion and add
+  // them to the real lists afterwards in the correct order.
+  scoped_ptr<LayerListType> unsorted_render_surface_layer_list;
+  scoped_ptr<LayerListType> unsorted_descendants;
+
+  std::vector<LayerType*> sorted_children;
+  bool child_order_changed = false;
+  if (layer_draw_properties.has_child_with_a_scroll_parent)
+    child_order_changed = SortChildrenForRecursion(&sorted_children, *layer);
+
+  if (child_order_changed) {
+    // We'll be visiting our children out of order; use the temporary lists.
+    unsorted_render_surface_layer_list.reset(new LayerListType);
+    unsorted_descendants.reset(new LayerListType);
+    render_surface_layer_list_for_children =
+        unsorted_render_surface_layer_list.get();
+    descendants_for_children = unsorted_descendants.get();
+  }
+
   for (size_t i = 0; i < layer->children().size(); ++i) {
+    // If one of layer's children has a scroll parent, then we may have to
+    // visit the children out of order. The new order is stored in
+    // sorted_children. Otherwise, we'll grab the child directly from the
+    // layer's list of children.
     LayerType* child =
-        LayerTreeHostCommon::get_child_as_raw_ptr(layer->children(), i);
+        layer_draw_properties.has_child_with_a_scroll_parent
+            ? sorted_children[i]
+            : LayerTreeHostCommon::get_child_as_raw_ptr(layer->children(), i);
+
+    child->draw_properties().index_of_first_descendants_addition =
+        descendants_for_children->size();
+    child->draw_properties().index_of_first_render_surface_layer_list_addition =
+        render_surface_layer_list_for_children->size();
+
     CalculateDrawPropertiesInternal<LayerType,
                                     LayerListType,
                                     RenderSurfaceType>(
         child,
         globals,
         data_for_children,
-        render_surface_layer_list,
-        &descendants,
+        render_surface_layer_list_for_children,
+        descendants_for_children,
         accumulated_surface_state);
+
     if (child->render_surface() &&
         !child->render_surface()->content_rect().IsEmpty()) {
-      descendants.push_back(child);
+      descendants_for_children->push_back(child);
     }
+
+    child->draw_properties().num_descendants_added =
+        descendants_for_children->size() -
+        child->draw_properties().index_of_first_descendants_addition;
+    child->draw_properties().num_render_surfaces_added =
+        render_surface_layer_list_for_children->size() -
+        child->draw_properties()
+            .index_of_first_render_surface_layer_list_addition;
+  }
+
+  // Add the unsorted layer list contributions, if necessary.
+  if (child_order_changed) {
+    AddUnsortedLayerListContributions(
+        *layer,
+        *unsorted_render_surface_layer_list,
+        render_surface_layer_list,
+        &GetNewRenderSurfacesStartIndexAndCount<LayerType>);
+
+    AddUnsortedLayerListContributions(
+        *layer,
+        *unsorted_descendants,
+        &descendants,
+        &GetNewDescendantsStartIndexAndCount<LayerType>);
   }
 
   // Compute the total drawable_content_rect for this subtree (the rect is in
diff --git a/cc/trees/layer_tree_host_common_unittest.cc b/cc/trees/layer_tree_host_common_unittest.cc
index 6b02c96..e9182e8 100644
--- a/cc/trees/layer_tree_host_common_unittest.cc
+++ b/cc/trees/layer_tree_host_common_unittest.cc
@@ -4,12 +4,15 @@
 
 #include "cc/trees/layer_tree_host_common.h"
 
+#include <set>
+
 #include "cc/animation/layer_animation_controller.h"
 #include "cc/base/math_util.h"
 #include "cc/layers/content_layer.h"
 #include "cc/layers/content_layer_client.h"
 #include "cc/layers/heads_up_display_layer_impl.h"
 #include "cc/layers/layer.h"
+#include "cc/layers/layer_client.h"
 #include "cc/layers/layer_impl.h"
 #include "cc/layers/render_surface.h"
 #include "cc/layers/render_surface_impl.h"
@@ -8982,5 +8985,564 @@ TEST_F(LayerTreeHostCommonTest, DoNotIncludeBackfaceInvisibleSurfaces) {
                 ->render_surface()->layer_list().size());
 }
 
+TEST_F(LayerTreeHostCommonTest, ClippedByScrollParent) {
+  // Checks that the simple case (being clipped by a scroll parent that would
+  // have been processed before you anyhow) results in the right clips.
+  //
+  // + root
+  //   + scroll_parent_border
+  //   | + scroll_parent_clip
+  //   |   + scroll_parent
+  //   + scroll_child
+  //
+  scoped_refptr<Layer> root = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_border = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_clip = Layer::Create();
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_parent =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_child =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  root->AddChild(scroll_child);
+
+  root->AddChild(scroll_parent_border);
+  scroll_parent_border->AddChild(scroll_parent_clip);
+  scroll_parent_clip->AddChild(scroll_parent);
+
+  scroll_parent_clip->SetMasksToBounds(true);
+
+  scroll_child->SetScrollParent(scroll_parent.get());
+
+  gfx::Transform identity_transform;
+  SetLayerPropertiesForTesting(root.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(30, 30),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_child.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+
+  scoped_ptr<FakeLayerTreeHost> host = FakeLayerTreeHost::Create();
+  host->SetRootLayer(root);
+
+  ExecuteCalculateDrawProperties(root.get());
+
+  EXPECT_TRUE(root->render_surface());
+
+  EXPECT_EQ(gfx::Rect(0, 0, 30, 30).ToString(),
+            scroll_child->clip_rect().ToString());
+  EXPECT_TRUE(scroll_child->is_clipped());
+}
+
+TEST_F(LayerTreeHostCommonTest, ClippedByOutOfOrderScrollParent) {
+  // Checks that clipping by a scroll parent that follows you in paint order
+  // still results in correct clipping.
+  //
+  // + root
+  //   + scroll_child
+  //   + scroll_parent_border
+  //     + scroll_parent_clip
+  //       + scroll_parent
+  //
+  scoped_refptr<Layer> root = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_border = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_clip = Layer::Create();
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_parent =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_child =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  root->AddChild(scroll_parent_border);
+  scroll_parent_border->AddChild(scroll_parent_clip);
+  scroll_parent_clip->AddChild(scroll_parent);
+
+  root->AddChild(scroll_child);
+
+  scroll_parent_clip->SetMasksToBounds(true);
+
+  scroll_child->SetScrollParent(scroll_parent.get());
+
+  gfx::Transform identity_transform;
+  SetLayerPropertiesForTesting(root.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(30, 30),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_child.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+
+  scoped_ptr<FakeLayerTreeHost> host = FakeLayerTreeHost::Create();
+  host->SetRootLayer(root);
+
+  ExecuteCalculateDrawProperties(root.get());
+
+  EXPECT_TRUE(root->render_surface());
+
+  EXPECT_EQ(gfx::Rect(0, 0, 30, 30).ToString(),
+            scroll_child->clip_rect().ToString());
+  EXPECT_TRUE(scroll_child->is_clipped());
+}
+
+TEST_F(LayerTreeHostCommonTest, ClippedByOutOfOrderScrollGrandparent) {
+  // Checks that clipping by a scroll parent and scroll grandparent that follow
+  // you in paint order still results in correct clipping.
+  //
+  // + root
+  //   + scroll_child
+  //   + scroll_parent_border
+  //   | + scroll_parent_clip
+  //   |   + scroll_parent
+  //   + scroll_grandparent_border
+  //     + scroll_grandparent_clip
+  //       + scroll_grandparent
+  //
+  scoped_refptr<Layer> root = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_border = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_clip = Layer::Create();
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_parent =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  scoped_refptr<Layer> scroll_grandparent_border = Layer::Create();
+  scoped_refptr<Layer> scroll_grandparent_clip = Layer::Create();
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_grandparent =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_child =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  root->AddChild(scroll_child);
+
+  root->AddChild(scroll_parent_border);
+  scroll_parent_border->AddChild(scroll_parent_clip);
+  scroll_parent_clip->AddChild(scroll_parent);
+
+  root->AddChild(scroll_grandparent_border);
+  scroll_grandparent_border->AddChild(scroll_grandparent_clip);
+  scroll_grandparent_clip->AddChild(scroll_grandparent);
+
+  scroll_parent_clip->SetMasksToBounds(true);
+  scroll_grandparent_clip->SetMasksToBounds(true);
+
+  scroll_child->SetScrollParent(scroll_parent.get());
+  scroll_parent_border->SetScrollParent(scroll_grandparent.get());
+
+  gfx::Transform identity_transform;
+  SetLayerPropertiesForTesting(root.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_grandparent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_grandparent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(20, 20),
+                               false);
+  SetLayerPropertiesForTesting(scroll_grandparent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(30, 30),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_child.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+
+  scoped_ptr<FakeLayerTreeHost> host = FakeLayerTreeHost::Create();
+  host->SetRootLayer(root);
+
+  ExecuteCalculateDrawProperties(root.get());
+
+  EXPECT_TRUE(root->render_surface());
+
+  EXPECT_EQ(gfx::Rect(0, 0, 20, 20).ToString(),
+            scroll_child->clip_rect().ToString());
+  EXPECT_TRUE(scroll_child->is_clipped());
+
+  // Despite the fact that we visited the above layers out of order to get the
+  // correct clip, the layer lists should be unaffected.
+  EXPECT_EQ(3u, root->render_surface()->layer_list().size());
+  EXPECT_EQ(scroll_child.get(),
+            root->render_surface()->layer_list().at(0));
+  EXPECT_EQ(scroll_parent.get(),
+            root->render_surface()->layer_list().at(1));
+  EXPECT_EQ(scroll_grandparent.get(),
+            root->render_surface()->layer_list().at(2));
+}
+
+TEST_F(LayerTreeHostCommonTest, OutOfOrderClippingRequiresRSLLSorting) {
+  // Ensures that even if we visit layers out of order, we still produce a
+  // correctly order render surface layer list.
+  // + root
+  //   + scroll_child
+  //   + scroll_parent_border
+  //     + scroll_parent_clip
+  //       + scroll_parent
+  //         + render_surface1
+  //   + scroll_grandparent_border
+  //     + scroll_grandparent_clip
+  //       + scroll_grandparent
+  //         + render_surface2
+  //
+  scoped_refptr<Layer> root = Layer::Create();
+
+  scoped_refptr<Layer> scroll_parent_border = Layer::Create();
+  scoped_refptr<Layer> scroll_parent_clip = Layer::Create();
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_parent =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+  scoped_refptr<LayerWithForcedDrawsContent> render_surface1 =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  scoped_refptr<Layer> scroll_grandparent_border = Layer::Create();
+  scoped_refptr<Layer> scroll_grandparent_clip = Layer::Create();
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_grandparent =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+  scoped_refptr<LayerWithForcedDrawsContent> render_surface2 =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  scoped_refptr<LayerWithForcedDrawsContent> scroll_child =
+      make_scoped_refptr(new LayerWithForcedDrawsContent);
+
+  root->AddChild(scroll_child);
+
+  root->AddChild(scroll_parent_border);
+  scroll_parent_border->AddChild(scroll_parent_clip);
+  scroll_parent_clip->AddChild(scroll_parent);
+  scroll_parent->AddChild(render_surface2);
+
+  root->AddChild(scroll_grandparent_border);
+  scroll_grandparent_border->AddChild(scroll_grandparent_clip);
+  scroll_grandparent_clip->AddChild(scroll_grandparent);
+  scroll_grandparent->AddChild(render_surface1);
+
+  scroll_parent_clip->SetMasksToBounds(true);
+  scroll_grandparent_clip->SetMasksToBounds(true);
+
+  scroll_child->SetScrollParent(scroll_parent.get());
+  scroll_parent_border->SetScrollParent(scroll_grandparent.get());
+
+  render_surface1->SetForceRenderSurface(true);
+  render_surface2->SetForceRenderSurface(true);
+
+  gfx::Transform identity_transform;
+  SetLayerPropertiesForTesting(root.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_grandparent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_grandparent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(20, 20),
+                               false);
+  SetLayerPropertiesForTesting(scroll_grandparent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(render_surface1.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(30, 30),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(render_surface2.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_child.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+
+  scoped_ptr<FakeLayerTreeHost> host = FakeLayerTreeHost::Create();
+  host->SetRootLayer(root);
+
+  RenderSurfaceLayerList render_surface_layer_list;
+  LayerTreeHostCommon::CalcDrawPropsMainInputsForTesting inputs(
+      root.get(),
+      root->bounds(),
+      identity_transform,
+      &render_surface_layer_list);
+
+  LayerTreeHostCommon::CalculateDrawProperties(&inputs);
+
+  EXPECT_TRUE(root->render_surface());
+
+  EXPECT_EQ(gfx::Rect(0, 0, 20, 20).ToString(),
+            scroll_child->clip_rect().ToString());
+  EXPECT_TRUE(scroll_child->is_clipped());
+
+  // Despite the fact that we had to process the layers out of order to get the
+  // right clip, our render_surface_layer_list's order should be unaffected.
+  EXPECT_EQ(3u, render_surface_layer_list.size());
+  EXPECT_EQ(root.get(), render_surface_layer_list.at(0));
+  EXPECT_EQ(render_surface2.get(), render_surface_layer_list.at(1));
+  EXPECT_EQ(render_surface1.get(), render_surface_layer_list.at(2));
+}
+
+TEST_F(LayerTreeHostCommonTest, DoNotClobberSorting) {
+  // We rearrange layer list contributions if we have to visit children out of
+  // order, but it should be a 'stable' rearrangement. That is, the layer list
+  // additions for a single layer should not be reordered, though their position
+  // wrt to the contributions due to a sibling may vary.
+  //
+  // + root
+  //   + scroll_child
+  //     + top_content
+  //     + bottom_content
+  //   + scroll_parent_border
+  //     + scroll_parent_clip
+  //       + scroll_parent
+  //
+  FakeImplProxy proxy;
+  FakeLayerTreeHostImpl host_impl(&proxy);
+  host_impl.CreatePendingTree();
+  scoped_ptr<LayerImpl> root = LayerImpl::Create(host_impl.active_tree(), 1);
+  scoped_ptr<LayerImpl> scroll_parent_border =
+      LayerImpl::Create(host_impl.active_tree(), 2);
+  scoped_ptr<LayerImpl> scroll_parent_clip =
+      LayerImpl::Create(host_impl.active_tree(), 3);
+  scoped_ptr<LayerImpl> scroll_parent =
+      LayerImpl::Create(host_impl.active_tree(), 4);
+  scoped_ptr<LayerImpl> scroll_child =
+      LayerImpl::Create(host_impl.active_tree(), 5);
+  scoped_ptr<LayerImpl> bottom_content =
+      LayerImpl::Create(host_impl.active_tree(), 6);
+  scoped_ptr<LayerImpl> top_content =
+      LayerImpl::Create(host_impl.active_tree(), 7);
+
+  scroll_parent_clip->SetMasksToBounds(true);
+
+  scroll_child->SetScrollParent(scroll_parent.get());
+  scoped_ptr<std::set<LayerImpl*> > scroll_children(new std::set<LayerImpl*>);
+  scroll_children->insert(scroll_child.get());
+  scroll_parent->SetScrollChildren(scroll_children.release());
+
+  scroll_child->SetDrawsContent(true);
+  scroll_parent->SetDrawsContent(true);
+  top_content->SetDrawsContent(true);
+  bottom_content->SetDrawsContent(true);
+
+  gfx::Transform identity_transform;
+  gfx::Transform top_transform;
+  top_transform.Translate3d(0.0, 0.0, 5.0);
+  gfx::Transform bottom_transform;
+  bottom_transform.Translate3d(0.0, 0.0, 3.0);
+
+  SetLayerPropertiesForTesting(root.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_border.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(40, 40),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent_clip.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(30, 30),
+                               false);
+  SetLayerPropertiesForTesting(scroll_parent.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(scroll_child.get(),
+                               identity_transform,
+                               identity_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(top_content.get(),
+                               top_transform,
+                               top_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+  SetLayerPropertiesForTesting(bottom_content.get(),
+                               bottom_transform,
+                               bottom_transform,
+                               gfx::PointF(),
+                               gfx::PointF(),
+                               gfx::Size(50, 50),
+                               false);
+
+  scroll_child->SetPreserves3d(true);
+
+  scroll_child->AddChild(top_content.Pass());
+  scroll_child->AddChild(bottom_content.Pass());
+  root->AddChild(scroll_child.Pass());
+
+  scroll_parent_clip->AddChild(scroll_parent.Pass());
+  scroll_parent_border->AddChild(scroll_parent_clip.Pass());
+  root->AddChild(scroll_parent_border.Pass());
+
+  LayerImplList render_surface_layer_list;
+  LayerTreeHostCommon::CalcDrawPropsImplInputsForTesting inputs(
+      root.get(), root->bounds(), &render_surface_layer_list);
+
+  LayerTreeHostCommon::CalculateDrawProperties(&inputs);
+
+  EXPECT_TRUE(root->render_surface());
+
+  // If we don't sort by depth and let the layers get added in the order they
+  // would normally be visited in, then layers 6 and 7 will be out of order. In
+  // other words, although we've had to shift 5, 6, and 7 to appear before 4
+  // in the list (because of the scroll parent relationship), this should not
+  // have an effect on the the order of 5, 6, and 7 (which had been reordered
+  // due to layer sorting).
+  EXPECT_EQ(4u, root->render_surface()->layer_list().size());
+  EXPECT_EQ(5, root->render_surface()->layer_list().at(0)->id());
+  EXPECT_EQ(6, root->render_surface()->layer_list().at(1)->id());
+  EXPECT_EQ(7, root->render_surface()->layer_list().at(2)->id());
+  EXPECT_EQ(4, root->render_surface()->layer_list().at(3)->id());
+}
+
 }  // namespace
 }  // namespace cc