Implement a Hit Test Cache.

Source/core/layout/HitTestCache.h

Index: Source/core/layout/HitTestCache.h
diff --git a/Source/core/layout/HitTestCache.h b/Source/core/layout/HitTestCache.h
new file mode 100644
index 0000000000000000000000000000000000000000..cf8ed32e804d4f6bbb7ec3c58f6a99970897d992
--- /dev/null
+++ b/Source/core/layout/HitTestCache.h
@@ -0,0 +1,82 @@
+// Copyright (c) 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 HitTestCache_h
+#define HitTestCache_h
+
+#include "core/layout/HitTestResult.h"
+
+namespace blink {
+
+// This object implements a cache for storing successfuly hit tests to DOM nodes

[Rick Byers, 2015/06/09 21:08:20]

nit: successful

[dtapuska, 2015/06/09 21:13:01]

Done.

+// in the visible viewport. The cache is cleared on dom modifications,
+// scrolling, CSS style modifications.
+//
+// Multiple hit tests can occur when processing events. Typically the DOM doesn't
+// change when each event is processed so in order to increase the time spent
+// processing the events a hit cache is useful. For example a GestureTap event
+// will generate a series of simulated mouse events (move, down, up, click)
+// with the same co-ordinates and ideally we'd like to do the hit test once
+// and use the result for the targetting of each event.
+//
+// Some of the related design, motivation can be found in:
+// https://docs.google.com/document/d/1b0NYAD4S9BJIpHGa4JD2HLmW28f2rUh1jlqrgpU3zVU/
+//

[Rick Byers, 2015/06/09 21:08:20]

Nice comment, thank you!

+class HitTestCache {
+public:
+    HitTestCache() = default;
+
+    // Check the cache for a possible hit and update |result| if
+    // hit encountered; returning true. Otherwise false.
+    bool lookupCachedResult(HitTestResult&, uint64_t domTreeVersion);
+
+    void clear();
+
+    // Verify that the |actual| object matches the |exepcted| object; otherwise
+    // log UMA metrics indicating failure.
+    static void verify(const HitTestResult& expected, const HitTestResult& actual);
+
+    // Adds a HitTestResult to the cache.
+    void addCachedResult(const HitTestResult&, uint64_t domTreeVersion);
+
+private:
+    // These values are reported in UMA. Try not to reorder/modify.
+    enum class HitHistogramMetric {
+        MISS, // A cache miss.
+        MISS_EXPLICIT_AVOID, // Explicitly asked by caller to avoid cache.
+        MISS_VALIDITY_RECT_MATCHES, // Region matches but request type doesn't.
+        HIT_EXACT_MATCH, // Exact point/rect hit.
+        HIT_REGION_MATCH, // Region match.
+        MAX_HIT_METRIC = HIT_REGION_MATCH,
+    };
+
+    // These values are reported in UMA. Try not to reorder/modify.
+    enum class ValidityHistogramMetric {
+        VALID_EXACT_MATCH, // Correct node for exact point test.
+        VALID_REGION, // Correct node for region check.
+        INCORRECT_RECT_BASED_EXACT_MATCH, // Wrong node returned for cache hit with point was exact match and rect based test.
+        INCORRECT_POINT_EXACT_MATCH, // Wrong node returned for cache hit with exact point match and was explicit point test.
+        INCORRECT_RECT_BASED_REGION, // Wrong node returned for rect with region matching and was rect based test.
+        INCORRECT_POINT_REGION, // Wrong node returned for point with region matching and was explicit point test.
+        MAX_VALIDITY_METRIC = INCORRECT_POINT_REGION,
+    };
+
+    struct CacheItem {
+        bool valid = false;
+        HitTestResult result;
+    };
+
+    unsigned m_updateIndex = 0;
+
+    // A cache size of 2 is used because it is relatively cheap to store;
+    // and the ping-pong behaviour of some of the HitTestRequest flags during
+    // Mouse/Touch/Pointer events can generate incrased cache misses with
+    // size of 1.
+    CacheItem m_items[2];
+    uint64_t m_domTreeVersion = 0;
+};
+
+} // namespace blink
+
+#endif // HitTestCache_h