Allow clipping by scroll parents.

Previously, we had required that we inherit our clip from our direct ancestor or
our clip parent (which has to be an ancestor). This CL loosens that restriction
and allows clipping by our scroll parent, which will not be our ancestor.

In order for this to work, we must ensure that the scroll parent's clip is
computed before we compute the clip children's. This is accomplished by changing
the order in which we recur through the layer tree and sorting layer lists
afterward to ensure that we ultimately stack correctly.

NB: I have taken care to only sort the newly added layers, and to only sort when
the child order has actually changed, which should happen rarely.

Tests:
 1. LayerTreeHostCommonTest.ClippedByScrollParent
   - Checks that the simple case (where the scroll parent is naturally processed
     before the scroll child) results in the correct clips.
 2. LayerTreeHostCommonTest.ClippedByOutOfOrderScrollParent
   - Identical to (1) but checks that clips are still correct when the scroll
     parent needs to be visited out of order.
 3. LayerTreeHostCommonTest.ClippedByOutOfOrderScrollGrandparent
   - Similar to (2), but also checks that clips are set up correctly if the
     scroll parent has yet another scroll parent (sorting for recursion is a bit
     tougher in this case).
   - Also checks that despite visiting layers out of order, that the layer list
     ends up in paint order.
 4. LayerTreeHostCommonTest.OutOfOrderClippingRequiresRSLLSorting
   - Similar to (3), but includes several render surfaces in the tree and checks
     that the resulting render surface layer list is ordered correctly.
5. LayerTreeHostCommonTest.DoNotClobberSorting
   - Ensures that if we have to reorder layer list contributions that we do not break 3d sorting.

BUG=291413
R=danakj@chromium.org, enne@chromium.org, hartmanng@chromium.org

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=225858

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=226219

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

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

3 files changed, 773 insertions, 14 deletions

diff --git a/cc/layers/draw_properties.h b/cc/layers/draw_properties.h
index 06c8834..bb8dcc0 100644
--- a/cc/layers/draw_properties.h
+++ b/cc/layers/draw_properties.h
@@ -29,7 +29,12 @@ 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),
+        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 +102,18 @@ 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 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 9556b68..a9828a7 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,8 @@ static void PreCalculateMetaInformation(
     num_descendants_that_draw_content = 1000;
   }
 
+  layer->draw_properties().sorted_for_recursion = false;
+
   if (layer->clip_parent())
     recursive_data->num_unclipped_descendants++;
 
@@ -1134,6 +1153,116 @@ 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) {
+  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,24 +1889,75 @@ static void CalculateDrawPropertiesInternal(
     data_for_children.subtree_is_visible_from_ancestor = layer_is_visible;
   }
 
-  for (size_t i = 0; i < layer->children().size(); ++i) {
-    LayerType* child =
-        LayerTreeHostCommon::get_child_as_raw_ptr(layer->children(), i);
+  // 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 = 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 < sorted_children.size(); ++i) {
+    LayerType* child = sorted_children[i];
     gfx::Rect drawable_content_rect_of_child_subtree;
     gfx::Transform identity_matrix;
+
+    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