Adds support for hittesting points on surface quads.

This is the first patch towards adding support for browser-process quad hittesting. This will be used for out of process iframes as a way to determine which process should receive input events.

BUG=491334
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

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

Cr-Commit-Position: refs/heads/master@{#342362}

7 files changed, 371 insertions, 0 deletions

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 1f3e4ee..cf62411 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -844,6 +844,7 @@ test("cc_unittests") {
     "surfaces/surface_aggregator_test_helpers.cc",
     "surfaces/surface_aggregator_test_helpers.h",
     "surfaces/surface_aggregator_unittest.cc",
+    "surfaces/surface_hittest_unittest.cc",
     "surfaces/surface_unittest.cc",
     "surfaces/surfaces_pixeltest.cc",
 
diff --git a/cc/cc.gyp b/cc/cc.gyp
index 44c35d7..f08c499 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp
@@ -607,6 +607,8 @@
         'surfaces/surface_factory.cc',
         'surfaces/surface_factory.h',
         'surfaces/surface_factory_client.h',
+        'surfaces/surface_hittest.cc',
+        'surfaces/surface_hittest.h',
         'surfaces/surface_id.h',
         'surfaces/surface_id_allocator.cc',
         'surfaces/surface_id_allocator.h',
diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index 61ba1cf..47a505a 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp
@@ -148,6 +148,7 @@
       'surfaces/surface_aggregator_unittest.cc',
       'surfaces/surface_display_output_surface_unittest.cc',
       'surfaces/surface_factory_unittest.cc',
+      'surfaces/surface_hittest_unittest.cc',
       'surfaces/surface_unittest.cc',
       'surfaces/surfaces_pixeltest.cc',
     ],
diff --git a/cc/surfaces/BUILD.gn b/cc/surfaces/BUILD.gn
index 0f2c950..3345caa 100644
--- a/cc/surfaces/BUILD.gn
+++ b/cc/surfaces/BUILD.gn
@@ -31,6 +31,8 @@ component("surfaces") {
     "surface_factory.cc",
     "surface_factory.h",
     "surface_factory_client.h",
+    "surface_hittest.cc",
+    "surface_hittest.h",
     "surface_id_allocator.cc",
     "surface_id_allocator.h",
     "surface_manager.cc",
diff --git a/cc/surfaces/surface_hittest.cc b/cc/surfaces/surface_hittest.cc
new file mode 100644
index 0000000..c2f96c5
--- /dev/null
+++ b/cc/surfaces/surface_hittest.cc
@@ -0,0 +1,151 @@
+// Copyright 2015 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/surfaces/surface_hittest.h"
+
+#include "cc/output/compositor_frame.h"
+#include "cc/output/delegated_frame_data.h"
+#include "cc/quads/draw_quad.h"
+#include "cc/quads/render_pass_draw_quad.h"
+#include "cc/quads/surface_draw_quad.h"
+#include "cc/surfaces/surface.h"
+#include "cc/surfaces/surface_manager.h"
+#include "ui/gfx/geometry/point.h"
+#include "ui/gfx/transform.h"
+
+namespace cc {
+namespace {
+const RenderPass* GetRootRenderPass(SurfaceManager* manager,
+                                    SurfaceId surface_id) {
+  Surface* surface = manager->GetSurfaceForId(surface_id);
+
+  const CompositorFrame* surface_frame = surface->GetEligibleFrame();
+  if (!surface_frame)
+    return nullptr;
+
+  const DelegatedFrameData* frame_data =
+      surface_frame->delegated_frame_data.get();
+  return frame_data->render_pass_list.empty()
+             ? nullptr
+             : frame_data->render_pass_list.back();
+}
+}
+
+SurfaceHittest::SurfaceHittest(SurfaceManager* manager) : manager_(manager) {}
+
+SurfaceHittest::~SurfaceHittest() {}
+
+SurfaceId SurfaceHittest::Hittest(SurfaceId surface_id,
+                                  const gfx::Point& point,
+                                  gfx::Point* transformed_point) {
+  SurfaceId hittest_surface_id = surface_id;
+
+  if (transformed_point)
+    *transformed_point = point;
+
+  HittestInternal(surface_id, GetRootRenderPass(manager_, surface_id), point,
+                  &hittest_surface_id, transformed_point);
+
+  referenced_passes_.clear();
+
+  return hittest_surface_id;
+}
+
+bool SurfaceHittest::HittestInternal(SurfaceId surface_id,
+                                     const RenderPass* render_pass,
+                                     const gfx::Point& point,
+                                     SurfaceId* out_surface_id,
+                                     gfx::Point* out_transformed_point) {
+  // To avoid an infinite recursion, we need to skip the RenderPass if it's
+  // already been referenced.
+  if (referenced_passes_.find(render_pass) != referenced_passes_.end())
+    return false;
+  referenced_passes_.insert(render_pass);
+
+  gfx::Transform transform_from_root_target;
+  if (!render_pass ||
+      !render_pass->transform_to_root_target.GetInverse(
+          &transform_from_root_target)) {
+    return false;
+  }
+
+  gfx::Point point_in_target_space(point);
+  transform_from_root_target.TransformPoint(&point_in_target_space);
+
+  for (const auto* quad : render_pass->quad_list) {
+    // First we test against the clip_rect. The clip_rect is in target space, so
+    // we can test the point directly.
+    if (!quad->shared_quad_state->is_clipped ||
+        quad->shared_quad_state->clip_rect.Contains(point_in_target_space)) {
+      // We now transform the point to content space and test if it hits the
+      // rect.
+      gfx::Transform target_to_quad_transform;
+      if (quad->shared_quad_state->quad_to_target_transform.GetInverse(
+              &target_to_quad_transform)) {
+        gfx::Point transformed_point(point_in_target_space);
+        target_to_quad_transform.TransformPoint(&transformed_point);
+
+        if (quad->rect.Contains(transformed_point)) {
+          if (quad->material == DrawQuad::SURFACE_CONTENT) {
+            // We've hit a SurfaceDrawQuad, we need to recurse into this
+            // Surface.
+            const SurfaceDrawQuad* surface_quad =
+                SurfaceDrawQuad::MaterialCast(quad);
+
+            gfx::Point point_in_current_surface;
+            if (out_transformed_point) {
+              point_in_current_surface = *out_transformed_point;
+              *out_transformed_point = transformed_point;
+            }
+
+            if (HittestInternal(
+                    surface_quad->surface_id,
+                    GetRootRenderPass(manager_, surface_quad->surface_id),
+                    transformed_point, out_surface_id, out_transformed_point)) {
+              return true;
+            } else {
+              if (out_transformed_point)
+                *out_transformed_point = point_in_current_surface;
+            }
+          } else if (quad->material == DrawQuad::RENDER_PASS) {
+            // We've hit a RenderPassDrawQuad, we need to recurse into this
+            // RenderPass.
+            const RenderPassDrawQuad* render_quad =
+                RenderPassDrawQuad::MaterialCast(quad);
+
+            Surface* surface = manager_->GetSurfaceForId(surface_id);
+            const CompositorFrame* surface_frame = surface->GetEligibleFrame();
+            DCHECK(surface_frame);
+            const DelegatedFrameData* frame_data =
+                surface_frame->delegated_frame_data.get();
+
+            const RenderPass* quad_render_pass = nullptr;
+            for (const auto* render_pass : frame_data->render_pass_list) {
+              if (render_pass->id == render_quad->render_pass_id) {
+                quad_render_pass = render_pass;
+                break;
+              }
+            }
+
+            if (quad_render_pass &&
+                HittestInternal(surface_id, quad_render_pass,
+                                point_in_target_space, out_surface_id,
+                                out_transformed_point)) {
+              return true;
+            }
+          } else {
+            // We've hit a different type of quad in the current Surface,
+            // there's no need to iterate anymore, this is the quad that
+            // receives the event;
+            *out_surface_id = surface_id;
+            return true;
+          }
+        }
+      }
+    }
+  }
+
+  return false;
+}
+}  // namespace cc
diff --git a/cc/surfaces/surface_hittest.h b/cc/surfaces/surface_hittest.h
new file mode 100644
index 0000000..4036165
--- /dev/null
+++ b/cc/surfaces/surface_hittest.h
@@ -0,0 +1,46 @@
+// Copyright 2015 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.
+
+#ifndef CC_SURFACES_SURFACE_HITTEST_H_
+#define CC_SURFACES_SURFACE_HITTEST_H_
+
+#include <set>
+
+#include "cc/surfaces/surface_id.h"
+#include "cc/surfaces/surfaces_export.h"
+
+namespace gfx {
+class Point;
+}
+
+namespace cc {
+class RenderPass;
+class SurfaceManager;
+
+// Performs a hittest in surface quads.
+class CC_SURFACES_EXPORT SurfaceHittest {
+ public:
+  explicit SurfaceHittest(SurfaceManager* manager);
+  ~SurfaceHittest();
+
+  // Hittests against Surface with SurfaceId |surface_id|, return the contained
+  // surface that the point is hitting and the |transformed_point| in the
+  // surface space.
+  SurfaceId Hittest(SurfaceId surface_id,
+                    const gfx::Point& point,
+                    gfx::Point* transformed_point);
+
+ private:
+  bool HittestInternal(SurfaceId surface_id,
+                       const RenderPass* render_pass,
+                       const gfx::Point& point,
+                       SurfaceId* out_surface_id,
+                       gfx::Point* out_transformed_point);
+
+  SurfaceManager* const manager_;
+  std::set<const RenderPass*> referenced_passes_;
+};
+}  // namespace cc
+
+#endif  // CC_SURFACES_SURFACE_HITTEST_H_
diff --git a/cc/surfaces/surface_hittest_unittest.cc b/cc/surfaces/surface_hittest_unittest.cc
new file mode 100644
index 0000000..0929259
--- /dev/null
+++ b/cc/surfaces/surface_hittest_unittest.cc
@@ -0,0 +1,168 @@
+// Copyright 2015 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/output/compositor_frame.h"
+#include "cc/output/delegated_frame_data.h"
+#include "cc/quads/render_pass.h"
+#include "cc/quads/render_pass_id.h"
+#include "cc/quads/solid_color_draw_quad.h"
+#include "cc/quads/surface_draw_quad.h"
+#include "cc/surfaces/surface.h"
+#include "cc/surfaces/surface_factory.h"
+#include "cc/surfaces/surface_factory_client.h"
+#include "cc/surfaces/surface_hittest.h"
+#include "cc/surfaces/surface_id_allocator.h"
+#include "cc/surfaces/surface_manager.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "third_party/skia/include/core/SkColor.h"
+#include "ui/gfx/geometry/size.h"
+
+namespace cc {
+
+class EmptySurfaceFactoryClient : public SurfaceFactoryClient {
+ public:
+  void ReturnResources(const ReturnedResourceArray& resources) override {}
+};
+
+TEST(SurfaceHittestTest, Hittest_SingleSurface) {
+  SurfaceManager manager;
+  EmptySurfaceFactoryClient client;
+  SurfaceFactory factory(&manager, &client);
+  SurfaceIdAllocator root_allocator(2);
+
+  // Creates a root surface.
+  SurfaceId root_surface_id = root_allocator.GenerateId();
+  factory.Create(root_surface_id);
+  gfx::Rect rect(300, 300);
+  RenderPassId id(1, 1);
+  scoped_ptr<RenderPass> pass = RenderPass::Create();
+  pass->SetNew(id, rect, rect, gfx::Transform());
+  scoped_ptr<DelegatedFrameData> delegated_frame_data(new DelegatedFrameData);
+  delegated_frame_data->render_pass_list.push_back(pass.Pass());
+  scoped_ptr<CompositorFrame> root_frame(new CompositorFrame);
+  root_frame->delegated_frame_data = delegated_frame_data.Pass();
+  factory.SubmitFrame(root_surface_id, root_frame.Pass(),
+                      SurfaceFactory::DrawCallback());
+
+  {
+    SurfaceHittest hittest(&manager);
+    gfx::Point transformed_point;
+    EXPECT_EQ(root_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(100, 100),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(100, 100), transformed_point);
+  }
+
+  factory.Destroy(root_surface_id);
+}
+
+TEST(SurfaceHittestTest, Hittest_ChildSurface) {
+  SurfaceManager manager;
+  EmptySurfaceFactoryClient client;
+  SurfaceFactory factory(&manager, &client);
+  SurfaceIdAllocator root_allocator(2);
+  SurfaceIdAllocator child_allocator(3);
+
+  SurfaceId root_surface_id = root_allocator.GenerateId();
+  SurfaceId child_surface_id = child_allocator.GenerateId();
+  gfx::Size root_size(300, 300);
+  gfx::Rect root_rect(root_size);
+  gfx::Size child_size(200, 200);
+  gfx::Rect child_rect(child_size);
+  gfx::Rect child_solid_quad_size(100, 100);
+  gfx::Rect child_solid_quad_rect(child_solid_quad_size);
+
+  // Creates a root surface.
+  factory.Create(root_surface_id);
+  RenderPassId root_id(1, 1);
+  scoped_ptr<RenderPass> root_pass = RenderPass::Create();
+  root_pass->SetNew(root_id, root_rect, root_rect, gfx::Transform());
+
+  // Add a reference to the child surface on the root surface.
+  SharedQuadState* root_shared_state =
+      root_pass->CreateAndAppendSharedQuadState();
+  root_shared_state->SetAll(gfx::Transform(1.0f, 0.0f, 0.0f, 50.0f,
+                                           0.0f, 1.0f, 0.0f, 50.0f,
+                                           0.0f, 0.0f, 1.0f, 0.0f,
+                                           0.0f, 0.0f, 0.0f, 1.0f),
+                            root_size, root_rect, root_rect, false, 1.0f,
+                            SkXfermode::kSrcOver_Mode, 0);
+  SurfaceDrawQuad* surface_quad =
+      root_pass->CreateAndAppendDrawQuad<SurfaceDrawQuad>();
+  surface_quad->SetNew(root_pass->shared_quad_state_list.back(), child_rect,
+                       child_rect, child_surface_id);
+
+  // Submit the root frame.
+  scoped_ptr<DelegatedFrameData> root_delegated_frame_data(
+      new DelegatedFrameData);
+  root_delegated_frame_data->render_pass_list.push_back(root_pass.Pass());
+  scoped_ptr<CompositorFrame> root_frame(new CompositorFrame);
+  root_frame->delegated_frame_data = root_delegated_frame_data.Pass();
+  factory.SubmitFrame(root_surface_id, root_frame.Pass(),
+                      SurfaceFactory::DrawCallback());
+
+  // Creates a child surface.
+  factory.Create(child_surface_id);
+  RenderPassId child_id(1, 1);
+  scoped_ptr<RenderPass> child_pass = RenderPass::Create();
+  child_pass->SetNew(child_id, child_rect, child_rect, gfx::Transform());
+
+  // Add a solid quad in the child surface.
+  SharedQuadState* child_shared_state =
+      child_pass->CreateAndAppendSharedQuadState();
+  child_shared_state->SetAll(gfx::Transform(1.0f, 0.0f, 0.0f, 50.0f,
+                                            0.0f, 1.0f, 0.0f, 50.0f,
+                                            0.0f, 0.0f, 1.0f, 0.0f,
+                                            0.0f, 0.0f, 0.0f, 1.0f),
+                             root_size, root_rect, root_rect, false, 1.0f,
+                             SkXfermode::kSrcOver_Mode, 0);
+  SolidColorDrawQuad* color_quad =
+      child_pass->CreateAndAppendDrawQuad<SolidColorDrawQuad>();
+  color_quad->SetNew(child_pass->shared_quad_state_list.back(),
+                     child_solid_quad_rect, child_solid_quad_rect,
+                     SK_ColorYELLOW, false);
+
+  // Submit the frame.
+  scoped_ptr<DelegatedFrameData> child_delegated_frame_data(
+      new DelegatedFrameData);
+  child_delegated_frame_data->render_pass_list.push_back(child_pass.Pass());
+  scoped_ptr<CompositorFrame> child_frame(new CompositorFrame);
+  child_frame->delegated_frame_data = child_delegated_frame_data.Pass();
+  factory.SubmitFrame(child_surface_id, child_frame.Pass(),
+                      SurfaceFactory::DrawCallback());
+
+  {
+    SurfaceHittest hittest(&manager);
+    gfx::Point transformed_point;
+    EXPECT_EQ(root_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(10, 10),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(10, 10), transformed_point);
+    EXPECT_EQ(root_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(99, 99),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(99, 99), transformed_point);
+    EXPECT_EQ(child_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(100, 100),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(50, 50), transformed_point);
+    EXPECT_EQ(child_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(199, 199),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(149, 149), transformed_point);
+    EXPECT_EQ(root_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(200, 200),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(200, 200), transformed_point);
+    EXPECT_EQ(root_surface_id,
+              hittest.Hittest(root_surface_id, gfx::Point(290, 290),
+                              &transformed_point));
+    EXPECT_EQ(gfx::Point(290, 290), transformed_point);
+  }
+
+  factory.Destroy(root_surface_id);
+  factory.Destroy(child_surface_id);
+}
+
+}  // namespace cc