Use LayerListIterator when hit testing.

cc/trees/layer_tree_impl.cc

 // Copyright 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/trees/layer_tree_impl.h"
 
 #include <stddef.h>
 #include <stdint.h>
 
 #include <algorithm>
 #include <limits>
 #include <set>
 
+#include "base/containers/adapters.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/timer/elapsed_timer.h"
 #include "base/trace_event/trace_event.h"
 #include "base/trace_event/trace_event_argument.h"
 #include "cc/animation/animation_host.h"
 #include "cc/animation/keyframed_animation_curve.h"
 #include "cc/animation/mutable_properties.h"
 #include "cc/base/histograms.h"
 #include "cc/base/math_util.h"
 #include "cc/base/synced_property.h"
 #include "cc/debug/devtools_instrumentation.h"
 #include "cc/debug/traced_value.h"
 #include "cc/input/page_scale_animation.h"
 #include "cc/input/scrollbar_animation_controller.h"
 #include "cc/input/scrollbar_animation_controller_linear_fade.h"
 #include "cc/input/scrollbar_animation_controller_thinning.h"
 #include "cc/layers/heads_up_display_layer_impl.h"
 #include "cc/layers/layer.h"
 #include "cc/layers/layer_iterator.h"
+#include "cc/layers/layer_list_iterator.h"
 #include "cc/layers/render_surface_impl.h"
 #include "cc/layers/scrollbar_layer_impl_base.h"
 #include "cc/resources/ui_resource_request.h"
 #include "cc/trees/draw_property_utils.h"
 #include "cc/trees/layer_tree_host_common.h"
 #include "cc/trees/layer_tree_host_impl.h"
 #include "cc/trees/occlusion_tracker.h"
 #include "cc/trees/property_tree.h"
 #include "cc/trees/property_tree_builder.h"
 #include "ui/gfx/geometry/box_f.h"
@@ skipping 318 matching lines @@
       EventListenerClass::kMouseWheel,
       event_listener_properties(EventListenerClass::kMouseWheel));
 
   if (ViewportSizeInvalid())
     target_tree->SetViewportSizeInvalid();
   else
     target_tree->ResetViewportSizeInvalid();
 
   if (hud_layer())
     target_tree->set_hud_layer(static_cast<HeadsUpDisplayLayerImpl*>(
-        LayerTreeHostCommon::FindLayerInSubtree(
-            target_tree->root_layer(), hud_layer()->id())));
+        LayerTreeHostCommon::FindLayerInSubtree(target_tree->root_layer(),
+                                                hud_layer()->id())));
   else
     target_tree->set_hud_layer(NULL);
 
   target_tree->has_ever_been_drawn_ = false;
 }
 
 LayerListIterator LayerTreeImpl::begin() {
   return LayerListIterator(root_layer_.get());
 }
 
@@ skipping 512 matching lines @@
       tile_priorities_updated |= layer->UpdateTiles();
     }
 
     if (tile_priorities_updated)
       DidModifyTilePriorities();
 
     TRACE_EVENT_END1("cc", "LayerTreeImpl::UpdateDrawProperties::UpdateTiles",
                      "layers_updated_count", layers_updated_count);
   }
 
-  DCHECK(!needs_update_draw_properties_) <<
-      "CalcDrawProperties should not set_needs_update_draw_properties()";
+  DCHECK(!needs_update_draw_properties_)
+      << "CalcDrawProperties should not set_needs_update_draw_properties()";
   return true;
 }
 
 void LayerTreeImpl::BuildPropertyTreesForTesting() {
   LayerTreeHostCommon::PreCalculateMetaInformationForTesting(root_layer_.get());
   PropertyTreeBuilder::BuildPropertyTrees(
       root_layer_.get(), PageScaleLayer(), InnerViewportScrollLayer(),
       OuterViewportScrollLayer(), OverscrollElasticityLayer(),
       elastic_overscroll()->Current(IsActiveTree()),
       current_page_scale_factor(), device_scale_factor(),
@@ skipping 487 matching lines @@
         << i << " of " << layers_with_copy_output_request_.size();
   }
   layers_with_copy_output_request_.push_back(layer);
 }
 
 void LayerTreeImpl::RemoveLayerWithCopyOutputRequest(LayerImpl* layer) {
   // Only the active tree needs to know about layers with copy requests, as
   // they are aborted if not serviced during draw.
   DCHECK(IsActiveTree());
 
-  std::vector<LayerImpl*>::iterator it = std::find(
-      layers_with_copy_output_request_.begin(),
-      layers_with_copy_output_request_.end(),
-      layer);
+  std::vector<LayerImpl*>::iterator it =
+      std::find(layers_with_copy_output_request_.begin(),
+                layers_with_copy_output_request_.end(), layer);
   DCHECK(it != layers_with_copy_output_request_.end());
   layers_with_copy_output_request_.erase(it);
 
   // TODO(danakj): Remove this once crash is found crbug.com/309777
   for (size_t i = 0; i < layers_with_copy_output_request_.size(); ++i) {
     CHECK(layers_with_copy_output_request_[i] != layer)
         << i << " of " << layers_with_copy_output_request_.size();
   }
 }
 
@@ skipping 174 matching lines @@
                                         transform_tree, clip_tree))
     return false;
 
   // Skip the HUD layer.
   if (layer == layer->layer_tree_impl()->hud_layer())
     return false;
 
   return true;
 }
 
-struct FindClosestMatchingLayerDataForRecursion {
-  FindClosestMatchingLayerDataForRecursion()
+struct FindClosestMatchingLayerState {
+  FindClosestMatchingLayerState()
       : closest_match(NULL),
         closest_distance(-std::numeric_limits<float>::infinity()) {}
   LayerImpl* closest_match;
   // Note that the positive z-axis points towards the camera, so bigger means
   // closer in this case, counterintuitively.
   float closest_distance;
 };
 
 template <typename Functor>
-static void FindClosestMatchingLayer(
-    const gfx::PointF& screen_space_point,
-    LayerImpl* layer,
-    const Functor& func,
-    const TransformTree& transform_tree,
-    const ClipTree& clip_tree,
-    FindClosestMatchingLayerDataForRecursion* data_for_recursion) {
-  size_t children_size = layer->children().size();
-  for (size_t i = 0; i < children_size; ++i) {
-    size_t index = children_size - 1 - i;
-    FindClosestMatchingLayer(screen_space_point, layer->children()[index].get(),
-                             func, transform_tree, clip_tree,
-                             data_for_recursion);
-  }
+static void FindClosestMatchingLayer(const gfx::PointF& screen_space_point,
+                                     LayerImpl* root_layer,
+                                     const Functor& func,
+                                     const TransformTree& transform_tree,
+                                     const ClipTree& clip_tree,
+                                     FindClosestMatchingLayerState* state) {
+  // We want to iterate from front to back when hit testing.
+  for (auto* layer : base::Reversed(*root_layer->layer_tree_impl())) {
+    if (!func(layer))
+      continue;
 
-  if (!func(layer))
-    return;
+    float distance_to_intersection = 0.f;
+    bool hit = false;
+    if (layer->Is3dSorted())
+      hit = PointHitsLayer(layer, screen_space_point, &distance_to_intersection,
+                           transform_tree, clip_tree);
+    else
+      hit = PointHitsLayer(layer, screen_space_point, nullptr, transform_tree,
+                           clip_tree);
 
-  float distance_to_intersection = 0.f;
-  bool hit = false;
-  if (layer->Is3dSorted())
-    hit = PointHitsLayer(layer, screen_space_point, &distance_to_intersection,
-                         transform_tree, clip_tree);
-  else
-    hit = PointHitsLayer(layer, screen_space_point, nullptr, transform_tree,
-                         clip_tree);
+    if (!hit)
+      continue;
 
-  if (!hit)
-    return;
+    bool in_front_of_previous_candidate =
+        state->closest_match &&
+        layer->sorting_context_id() ==
+            state->closest_match->sorting_context_id() &&
+        distance_to_intersection >
+            state->closest_distance + std::numeric_limits<float>::epsilon();
 
-  bool in_front_of_previous_candidate =
-      data_for_recursion->closest_match &&
-      layer->sorting_context_id() ==
-          data_for_recursion->closest_match->sorting_context_id() &&
-      distance_to_intersection > data_for_recursion->closest_distance +
-                                     std::numeric_limits<float>::epsilon();
-
-  if (!data_for_recursion->closest_match || in_front_of_previous_candidate) {
-    data_for_recursion->closest_distance = distance_to_intersection;
-    data_for_recursion->closest_match = layer;
+    if (!state->closest_match || in_front_of_previous_candidate) {
+      state->closest_distance = distance_to_intersection;
+      state->closest_match = layer;
+    }
   }
 }
 
 static bool ScrollsAnyDrawnRenderSurfaceLayerListMember(LayerImpl* layer) {
   if (!layer->scrollable())
     return false;
   if (layer->layer_or_descendant_is_drawn())
     return true;
 
   if (!layer->scroll_children())
     return false;
   for (std::set<LayerImpl*>::const_iterator it =
            layer->scroll_children()->begin();
-       it != layer->scroll_children()->end();
-       ++it) {
+       it != layer->scroll_children()->end(); ++it) {
     if ((*it)->layer_or_descendant_is_drawn())
       return true;
   }
   return false;
 }
 
 struct FindScrollingLayerFunctor {
   bool operator()(LayerImpl* layer) const {
     return ScrollsAnyDrawnRenderSurfaceLayerListMember(layer);
   }
 };
 
 LayerImpl* LayerTreeImpl::FindFirstScrollingLayerThatIsHitByPoint(
     const gfx::PointF& screen_space_point) {
-  FindClosestMatchingLayerDataForRecursion data_for_recursion;
-  FindClosestMatchingLayer(screen_space_point, root_layer(),
-                           FindScrollingLayerFunctor(),
-                           property_trees_.transform_tree,
-                           property_trees_.clip_tree, &data_for_recursion);
-  return data_for_recursion.closest_match;
+  FindClosestMatchingLayerState state;
+  FindClosestMatchingLayer(
+      screen_space_point, root_layer(), FindScrollingLayerFunctor(),
+      property_trees_.transform_tree, property_trees_.clip_tree, &state);
+  return state.closest_match;
 }
 
 struct HitTestVisibleScrollableOrTouchableFunctor {
   bool operator()(LayerImpl* layer) const {
     return layer->IsDrawnRenderSurfaceLayerListMember() ||
            ScrollsAnyDrawnRenderSurfaceLayerListMember(layer) ||
            !layer->touch_event_handler_region().IsEmpty() ||
            layer->layer_tree_impl()->event_listener_properties(
                EventListenerClass::kMouseWheel) !=
                EventListenerProperties::kNone;
   }
 };
 
 LayerImpl* LayerTreeImpl::FindLayerThatIsHitByPoint(
     const gfx::PointF& screen_space_point) {
   if (!root_layer())
     return NULL;
   bool update_lcd_text = false;
   if (!UpdateDrawProperties(update_lcd_text))
     return NULL;
-  FindClosestMatchingLayerDataForRecursion data_for_recursion;
+  FindClosestMatchingLayerState state;
   FindClosestMatchingLayer(screen_space_point, root_layer(),
                            HitTestVisibleScrollableOrTouchableFunctor(),
                            property_trees_.transform_tree,
-                           property_trees_.clip_tree, &data_for_recursion);
-  return data_for_recursion.closest_match;
+                           property_trees_.clip_tree, &state);
+  return state.closest_match;
 }
 
 static bool LayerHasTouchEventHandlersAt(const gfx::PointF& screen_space_point,
                                          LayerImpl* layer_impl,
                                          const TransformTree& transform_tree,
                                          const ClipTree& clip_tree) {
   if (layer_impl->touch_event_handler_region().IsEmpty())
     return false;
 
   if (!PointHitsRegion(screen_space_point, layer_impl->ScreenSpaceTransform(),
@@ skipping 24 matching lines @@
 LayerImpl* LayerTreeImpl::FindLayerThatIsHitByPointInTouchHandlerRegion(
     const gfx::PointF& screen_space_point) {
   if (!root_layer())
     return NULL;
   bool update_lcd_text = false;
   if (!UpdateDrawProperties(update_lcd_text))
     return NULL;
   FindTouchEventLayerFunctor func = {screen_space_point,
                                      property_trees_.transform_tree,
                                      property_trees_.clip_tree};
-  FindClosestMatchingLayerDataForRecursion data_for_recursion;
+  FindClosestMatchingLayerState state;
   FindClosestMatchingLayer(screen_space_point, root_layer(), func,
                            property_trees_.transform_tree,
-                           property_trees_.clip_tree, &data_for_recursion);
-  return data_for_recursion.closest_match;
+                           property_trees_.clip_tree, &state);
+  return state.closest_match;
 }
 
 void LayerTreeImpl::RegisterSelection(const LayerSelection& selection) {
   selection_ = selection;
 }
 
 static ViewportSelectionBound ComputeViewportSelectionBound(
     const LayerSelectionBound& layer_bound,
     LayerImpl* layer,
     float device_scale_factor,
@@ skipping 84 matching lines @@
     const {
   return layer_tree_host_impl_;
 }
 
 void LayerTreeImpl::SetPendingPageScaleAnimation(
     scoped_ptr<PendingPageScaleAnimation> pending_animation) {
   pending_page_scale_animation_ = std::move(pending_animation);
 }
 
 scoped_ptr<PendingPageScaleAnimation>
-    LayerTreeImpl::TakePendingPageScaleAnimation() {
+LayerTreeImpl::TakePendingPageScaleAnimation() {
   return std::move(pending_page_scale_animation_);
 }
 
 bool LayerTreeImpl::IsAnimatingFilterProperty(const LayerImpl* layer) const {
   LayerTreeType tree_type =
       IsActiveTree() ? LayerTreeType::ACTIVE : LayerTreeType::PENDING;
   return layer_tree_host_impl_->animation_host()
              ? layer_tree_host_impl_->animation_host()
                    ->IsAnimatingFilterProperty(layer->id(), tree_type)
              : false;
@@ skipping 165 matching lines @@
                                                    const gfx::BoxF& box,
                                                    gfx::BoxF* bounds) const {
   *bounds = gfx::BoxF();
   return layer_tree_host_impl_->animation_host()
              ? layer_tree_host_impl_->animation_host()
                    ->TransformAnimationBoundsForBox(layer->id(), box, bounds)
              : true;
 }
 
 }  // namespace cc