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..11fd7a534484fa697619beb7d6d100c7ab416ab5
--- /dev/null
+++ b/Source/core/layout/HitTestCache.h
@@ -0,0 +1,62 @@
+// 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 {
+
+class HitTestCache {

[Rick Byers, 2015/06/05 20:48:59]

Please add a brief comment describing the overall intention here (maybe making
specific reference to the issues like GestureTap where normally the target
doesn't change but occasionally it needs to - or just link to your doc for
details).

[dtapuska, 2015/06/09 18:21:24]

Done.

+public:
+    HitTestCache() = default;
+
+    // Check the cache for a possible hit and update |result| if
+    // hit encountered; returning true. Otherwise false.
+    bool check(HitTestResult& /*result*/);

[Rick Byers, 2015/06/06 16:12:54]

nit: no need for /*result*/

[dtapuska, 2015/06/09 18:21:24]

Done.

+
+    void clear();
+    static void verify(const HitTestResult&, const HitTestResult&);

[Rick Byers, 2015/06/05 20:48:59]

the other two methods seem self explanatory here, but this one doesn't
necessarily - please add a comment.

[Rick Byers, 2015/06/06 16:12:54]

Since the order of the arguments are important (at least to the metric
generated), please include the argument names here since they do communicate
some extra value.  See #9 at
https://www.chromium.org/blink/coding-style#TOC-Names for a good rule of thumb.

[dtapuska, 2015/06/09 18:21:24]

Done.

[dtapuska, 2015/06/09 18:21:24]

Done.

+    void cacheValue(const HitTestResult&);
+
+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 by request type doesn't.

[Rick Byers, 2015/06/05 20:48:59]

s/by/but/

[dtapuska, 2015/06/09 18:21:24]

Done.

+        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 VerifyHistogramMetric {
+        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_VERIFY_METRIC = INCORRECT_POINT_REGION,
+    };
+
+    struct CacheItem {
+        bool m_valid = false;

[esprehn, 2015/06/06 21:14:30]

no m_ prefix on public fields.

[dtapuska, 2015/06/09 18:21:24]

Done.

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

[Rick Byers, 2015/06/05 20:48:59]

Do you think such ping-ponging of flags that affect the hit test could be fixed?
 Seems like it probably shouldn't happen? Maybe file a separate bug to track
that.

[dtapuska, 2015/06/09 18:21:24]

I don't think the ping pong can be changed. I believe there is a penetration
testing; looking inside iframes on the hover happens in between the processing.
We might be able to move it to the end of the flow; but then you'd loose the
cache if there was a similar event next with slightly different flags.

+    CacheItem m_items[2];

[esprehn, 2015/06/06 21:14:30]

We're probably going to need to hook this up to memory pressure notifications,
you're keeping DOM trees alive inside the CacheItems.

[Rick Byers, 2015/06/07 04:34:46]

I was concerned about this at first too, but thought it was unlikely to be a
real problem because the only way we could hold the only ref here is if it was
just removed from a document, and so we should be just about to flush the cache.
 Right?  Can you think of a real scenario where we could actually prolong
lifetime non-trivially?

[dtapuska, 2015/06/09 18:21:24]

The refs are explicitly purged on clear; I wondered about this as well as
tracing with oilpan..

But the fields should be ref'd elsewhere; and really this is just a weak cache.

[dtapuska, 2015/06/09 18:21:24]

I couldn't think of any; since the fields are cleared on dom modifications.

+};
+
+} // namespace blink
+
+#endif // HitTestCache_h