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..64a749380cf717abdc35bf6c52306f6318735327
--- /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 successful hit tests to DOM nodes
+// 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 decrease 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/
+//
+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

[tdresser, 2015/06/10 13:35:21]

exepcted -> expected

[dtapuska, 2015/06/10 14:04:48]

Done.

+    // log UMA metrics indicating failure.

[tdresser, 2015/06/10 13:35:21]

This is a bit misleading, in that we log UMA metrics either way.

[dtapuska, 2015/06/10 14:04:48]

Done.

+    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.

[tdresser, 2015/06/10 13:35:21]

Don't you need a few more constraints here (and below)?
Shouldn't this be kept in sync with histograms.xml?
Also, it wouldn't hurt to mention that new values should be added to the end.

[dtapuska, 2015/06/10 14:04:48]

Done.

+    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

[tdresser, 2015/06/10 13:35:21]

incrased -> increased

[dtapuska, 2015/06/10 14:04:48]

Done.

+    // size of 1.
+    CacheItem m_items[2];

[tdresser, 2015/06/10 13:35:21]

Once this is in, it would be interesting to run an experiment to tune this. A
finch trial where we bumped this up to 3/4 could generate some interesting data.

[dtapuska, 2015/06/10 14:04:48]

Acknowledged.

+    uint64_t m_domTreeVersion = 0;
+};
+
+} // namespace blink
+
+#endif // HitTestCache_h