Index: cc/trees/layer_tree_host_common.cc |
diff --git a/cc/trees/layer_tree_host_common.cc b/cc/trees/layer_tree_host_common.cc |
index 03b6ccffc8303f28509d8e3fee09da016728eb1d..840a32b2ef4a59037f22e33e251c9edee72bc649 100644 |
--- a/cc/trees/layer_tree_host_common.cc |
+++ b/cc/trees/layer_tree_host_common.cc |
@@ -202,27 +202,14 @@ |
TranslateRectDirectionToDescendant); |
} else { |
// If we're being clipped by our scroll parent, we must translate through |
- // our common ancestor. |
- const LayerType* lca = |
- HighestScrollParentAncestorNotOnChildAncestorChain( |
- layer->draw_properties().sequence_number, layer, clip_parent) |
- ->parent(); |
- |
+ // 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>(*lca, |
+ TranslateRectToTargetSpace<LayerType>(*layer->parent(), |
*clip_parent, |
*clip_rect_in_parent_target_space, |
TranslateRectDirectionToAncestor); |
- |
- // The lowest common ancestor is usually, but not always, our parent. We |
- // must check if we need to transform from the lca's space to our parent's. |
- if (lca != layer->parent()) { |
- *clip_rect_in_parent_target_space = TranslateRectToTargetSpace<LayerType>( |
- *lca, |
- *layer->parent(), |
- *clip_rect_in_parent_target_space, |
- TranslateRectDirectionToDescendant); |
- } |
} |
} |
@@ -1168,18 +1155,6 @@ |
} |
template <typename LayerType> |
-static inline bool HaveVisited(LayerType* layer, int sequence_number) { |
- return layer->draw_properties().sequence_number == sequence_number; |
-} |
- |
-template <typename LayerType> |
-static inline bool HaveAssignedSortWeight(LayerType* layer, |
- int sequence_number) { |
- return layer->draw_properties().sort_weight_sequence_number == |
- sequence_number; |
-} |
- |
-template <typename LayerType> |
static inline void RemoveSurfaceForEarlyExit( |
LayerType* layer_to_remove, |
typename LayerType::RenderSurfaceListType* render_surface_layer_list) { |
@@ -1206,73 +1181,6 @@ |
layer_to_remove->ClearRenderSurfaceLayerList(); |
} |
-template <typename LayerType> |
-static inline LayerType* HighestScrollParentAncestorNotOnChildAncestorChain( |
- int sequence_number, |
- LayerType* scroll_child, |
- LayerType* scroll_parent) { |
- // Say we have the following tree. |
- // |
- // a |
- // +-b |
- // | +-c |
- // | +-scroll_child |
- // +-d |
- // +-e |
- // +-scroll_parent |
- // |
- // This function aims to find find the highest ancestor of |scroll_parent| |
- // that's not on |scroll_child|'s ancestor chain. d, in this case. |
- // |
- // Fortunately, we have some hints that make finding the lowest common |
- // ancestor a bit easier than usual. We know if we've visited a layer, and for |
- // those layers that we've visited, we know their depth in the tree. |
- if (!HaveVisited(scroll_parent, sequence_number)) { |
- DCHECK(scroll_parent->parent()); |
- // This case is easy. Since we walk the tree in DFS order, if we haven't |
- // visited the scroll parent, we just have to walk up to the first visited |
- // layer, which will be the LCA. |
- while (!HaveVisited(scroll_parent->parent(), sequence_number)) |
- scroll_parent = scroll_parent->parent(); |
- // This would mean that |scroll_parent| is a descendant of |scroll_child|, |
- // which is an error. |
- DCHECK_NE(scroll_child, scroll_parent->parent()); |
- } else { |
- // In this case, we've visited both the scroll_parent and scroll_child, so |
- // it's not as easy as walking to the first visited ancestor of the scroll |
- // parent. But since we've visited the layers, we know their depths, and we |
- // can efficiently find the LCA by walking up nodes at the same height. |
- |
- // First, walk up from the deeper layer until we reach two layers at the |
- // same depth in the tree. |
- while (scroll_child->draw_properties().depth != |
- scroll_parent->draw_properties().depth) { |
- int child_is_deeper = scroll_child->draw_properties().depth > |
- scroll_parent->draw_properties().depth; |
- if (child_is_deeper) |
- scroll_child = scroll_child->parent(); |
- else |
- scroll_parent = scroll_parent->parent(); |
- } |
- |
- // This would only happen if |scroll_child| and |scroll_parent| were on the |
- // same ancestor chain, which is an error. We only ever set up scroll parent |
- // scroll child relationships if scroll child is not a descendant of the |
- // scroll parent and will therefore not scroll with it naturally and needs |
- // special treatment by the compositor. |
- DCHECK_NE(scroll_child, scroll_parent); |
- |
- // Now that scroll_child and scroll_parent are at the same depth, we can |
- // walk up in tandem to find the LCA. |
- while (scroll_child->parent() != scroll_parent->parent()) { |
- scroll_child = scroll_child->parent(); |
- scroll_parent = scroll_parent->parent(); |
- } |
- } |
- |
- return scroll_parent; |
-} |
- |
struct PreCalculateMetaInformationRecursiveData { |
bool layer_or_descendant_has_copy_request; |
bool layer_or_descendant_has_input_handler; |
@@ -1293,93 +1201,15 @@ |
} |
}; |
-static int next_sort_weight(int* last_sort_weight) { |
- return ++(*last_sort_weight); |
-} |
- |
-template <typename LayerType> |
-static inline void AssignSortWeights(LayerType* layer, |
- int sequence_number, |
- int* last_sort_weight) { |
- // Give |layer| the highest sort weight in the tree so far. |
- if (!HaveAssignedSortWeight(layer, sequence_number)) { |
- layer->draw_properties().sort_weight = next_sort_weight(last_sort_weight); |
- layer->draw_properties().sort_weight_sequence_number = sequence_number; |
- } |
- |
- if (LayerType* scroll_parent = layer->scroll_parent()) { |
- // It's important to note where we need to take care of ordering so that |
- // scroll parents are visited before scroll children; it's at their lowest |
- // common ancestor. |
- // |
- // LCA |
- // +-scroll_parent_ancestor |
- // | +- ... |
- // | + scroll_parent |
- // | |
- // +-scroll_child_ancestor |
- // +- .. |
- // + scroll_child |
- // |
- // So given the above tree, we need to guarentee that scroll_parent_ancestor |
- // is processed before scroll_child. We ensure that by assigning it the |
- // lowest sort weight in the tree. We also want to flag LCA if we need to do |
- // any funny business with sort weights so that it knows to do special |
- // sorting of its descendants. |
- LayerType* scroll_parent_ancestor = |
- HighestScrollParentAncestorNotOnChildAncestorChain( |
- sequence_number, layer, scroll_parent); |
- |
- // We know we need to reorder if we haven't yet assigned |
- // |scroll_parent_ancestor| a sort weight. Sort weights are monotonically |
- // increasing, so unless we intervene, it will be given a higher sort weight |
- // than |layer|. |
- bool need_to_reorder = |
- !HaveAssignedSortWeight(scroll_parent_ancestor, sequence_number); |
- |
- LayerType* lca = scroll_parent_ancestor->parent(); |
- |
- // We also might need to reorder if scroll_parent_ancestor has been visited |
- // and has an unacceptable sort weight. |
- if (!need_to_reorder) { |
- LayerType* scroll_child_ancestor = layer; |
- while (scroll_child_ancestor->parent() && |
- scroll_child_ancestor->parent() != lca) { |
- scroll_child_ancestor = scroll_child_ancestor->parent(); |
- } |
- // We must have assigned a sort weight to this layer since its on our |
- // ancestor chain. |
- DCHECK(HaveAssignedSortWeight(scroll_child_ancestor, sequence_number)); |
- if (scroll_child_ancestor->draw_properties().sort_weight < |
- scroll_parent_ancestor->draw_properties().sort_weight) |
- need_to_reorder = true; |
- } |
- |
- if (need_to_reorder) { |
- // Give |scroll_parent_ancestor| the lowest weight in the tree so far. |
- scroll_parent_ancestor->draw_properties().sort_weight = |
- -next_sort_weight(last_sort_weight); |
- scroll_parent_ancestor->draw_properties().sort_weight_sequence_number = |
- sequence_number; |
- |
- // Mark the LCA as needing to sort. |
- lca->draw_properties().children_need_sorting = true; |
- } |
- } |
-} |
- |
// Recursively walks the layer tree to compute any information that is needed |
// before doing the main recursion. |
template <typename LayerType> |
static void PreCalculateMetaInformation( |
LayerType* layer, |
- PreCalculateMetaInformationRecursiveData* recursive_data, |
- int depth, |
- int sequence_number, |
- int* last_sort_weight) { |
- layer->draw_properties().children_need_sorting = false; |
- layer->draw_properties().depth = depth; |
- layer->draw_properties().sequence_number = sequence_number; |
+ PreCalculateMetaInformationRecursiveData* recursive_data) { |
+ |
+ layer->draw_properties().sorted_for_recursion = false; |
+ layer->draw_properties().has_child_with_a_scroll_parent = false; |
if (!HasInvertibleOrAnimatedTransform(layer)) { |
// Layers with singular transforms should not be drawn, the whole subtree |
@@ -1390,17 +1220,15 @@ |
if (layer->clip_parent()) |
recursive_data->num_unclipped_descendants++; |
- AssignSortWeights(layer, sequence_number, last_sort_weight); |
- |
for (size_t i = 0; i < layer->children().size(); ++i) { |
LayerType* child_layer = |
LayerTreeHostCommon::get_layer_as_raw_ptr(layer->children(), i); |
+ |
PreCalculateMetaInformationRecursiveData data_for_child; |
- PreCalculateMetaInformation(child_layer, |
- &data_for_child, |
- depth + 1, |
- sequence_number, |
- last_sort_weight); |
+ PreCalculateMetaInformation(child_layer, &data_for_child); |
+ |
+ if (child_layer->scroll_parent()) |
+ layer->draw_properties().has_child_with_a_scroll_parent = true; |
recursive_data->Merge(data_for_child); |
} |
@@ -1487,23 +1315,77 @@ |
}; |
template <typename LayerType> |
-struct AscendingScrollWeightComparator { |
- bool operator()(LayerType* lhs, LayerType* rhs) { |
- return lhs->draw_properties().sort_weight < |
- rhs->draw_properties().sort_weight; |
- } |
-}; |
- |
-template <typename LayerType> |
-static void SortChildrenForRecursion(std::vector<LayerType*>* out, |
+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->resize(parent.children().size()); |
- for (size_t i = 0; i < parent.children().size(); ++i) |
- (*out)[i] = LayerTreeHostCommon::get_layer_as_raw_ptr(parent.children(), i); |
- |
- // Ensures the children are sorted in ascending sort weight. |
- std::sort( |
- out->begin(), out->end(), AscendingScrollWeightComparator<LayerType>()); |
+ out->reserve(parent.children().size()); |
+ bool order_changed = false; |
+ for (size_t i = 0; i < parent.children().size(); ++i) { |
+ LayerType* current = |
+ LayerTreeHostCommon::get_layer_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> |
@@ -2229,8 +2111,9 @@ |
} |
std::vector<LayerType*> sorted_children; |
- if (layer_draw_properties.children_need_sorting) |
- SortChildrenForRecursion(&sorted_children, *layer); |
+ bool child_order_changed = false; |
+ if (layer_draw_properties.has_child_with_a_scroll_parent) |
+ child_order_changed = SortChildrenForRecursion(&sorted_children, *layer); |
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 |
@@ -2238,7 +2121,7 @@ |
// sorted_children. Otherwise, we'll grab the child directly from the |
// layer's list of children. |
LayerType* child = |
- layer_draw_properties.children_need_sorting |
+ layer_draw_properties.has_child_with_a_scroll_parent |
? sorted_children[i] |
: LayerTreeHostCommon::get_layer_as_raw_ptr(layer->children(), i); |
@@ -2276,7 +2159,7 @@ |
} |
// Add the unsorted layer list contributions, if necessary. |
- if (layer_draw_properties.children_need_sorting) { |
+ if (child_order_changed) { |
SortLayerListContributions( |
*layer, |
GetLayerListForSorting(render_surface_layer_list), |
@@ -2507,15 +2390,8 @@ |
DataForRecursion<Layer> data_for_recursion; |
ProcessCalcDrawPropsInputs(*inputs, &globals, &data_for_recursion); |
- // This is used as a global throughout the precalculate recursion. |
- int last_sort_weight = 0; |
PreCalculateMetaInformationRecursiveData recursive_data; |
- PreCalculateMetaInformation(inputs->root_layer, |
- &recursive_data, |
- 0, |
- inputs->current_render_surface_layer_list_id, |
- &last_sort_weight); |
- |
+ PreCalculateMetaInformation(inputs->root_layer, &recursive_data); |
std::vector<AccumulatedSurfaceState<Layer> > accumulated_surface_state; |
CalculateDrawPropertiesInternal<Layer>( |
inputs->root_layer, |
@@ -2543,15 +2419,8 @@ |
LayerSorter layer_sorter; |
globals.layer_sorter = &layer_sorter; |
- // This is used as a global throughout the precalculate recursion. |
- int last_sort_weight = 0; |
PreCalculateMetaInformationRecursiveData recursive_data; |
- PreCalculateMetaInformation(inputs->root_layer, |
- &recursive_data, |
- 0, |
- inputs->current_render_surface_layer_list_id, |
- &last_sort_weight); |
- |
+ PreCalculateMetaInformation(inputs->root_layer, &recursive_data); |
std::vector<AccumulatedSurfaceState<LayerImpl> > |
accumulated_surface_state; |
CalculateDrawPropertiesInternal<LayerImpl>( |