Implement a Hit Test Cache.

Source/core/layout/HitTestCache.cpp

Index: Source/core/layout/HitTestCache.cpp
diff --git a/Source/core/layout/HitTestCache.cpp b/Source/core/layout/HitTestCache.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..75c79a75e97c0db6a20fcf8afd8230d269f0d335
--- /dev/null
+++ b/Source/core/layout/HitTestCache.cpp
@@ -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.
+
+#include "config.h"
+#include "core/layout/HitTestCache.h"
+
+#include "public/platform/Platform.h"
+#include <base/macros.h>

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

What do you need this for?  It's still very rare for blink to depend on base
(outside of tests).  Not sure if it really matters, just curious.

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

I think you want WTF_ARRAY_SIZE, lets not use base yet.

[Rick Byers, 2015/06/07 04:44:57]

Note that there is at least one non-test use of base in blink (in
WebPluginContainerImpl.cpp).  If this matters, maybe we need to enforce it, or
at least mention it in the style guide?

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

it was used for arraysize(...) macro; esprehn pointed out there is
WTF_ARRAY_LENGTH.

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

Acknowledged.

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

Done.

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

Done.

+
+namespace blink {
+
+bool HitTestCache::check(HitTestResult& hitResult)

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

verify() I think is better than check.

[Rick Byers, 2015/06/07 04:44:57]

Verify is below.  Maybe call this lookup?

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

Acknowledged.

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

Changed to lookupCacheValue... to model after the addCacheValue method name;
esprehn requested below.

+{
+    bool result = false;
+    HitHistogramMetric metric = HitHistogramMetric::MISS;
+    if (hitResult.hitTestRequest().avoidCache()) {
+        metric = HitHistogramMetric::MISS_EXPLICIT_AVOID;
+    // For now we don't support rect based hit results.

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

But list-based tests (like elementsFromPoint) work OK?  Please add a basic test
that covers that.

+    } else if (!hitResult.hitTestLocation().isRectBasedTest()) {
+        for (size_t i = 0; m_items[i].m_valid && i < arraysize(m_items); ++i) {

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

i < arraysize(m_items) should come before the m_valid check to avoid reading
past the end of m_items.

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

Done.

+            if (m_items[i].m_result.validityRect().contains(hitResult.hitTestLocation().point())) {
+                if (hitResult.hitTestRequest().equalForCacheability(m_items[i].m_result.hitTestRequest())) {
+                    metric = hitResult.hitTestLocation().point() == m_items[i].m_result.hitTestLocation().point() ? HitHistogramMetric::HIT_EXACT_MATCH : HitHistogramMetric::HIT_REGION_MATCH;
+                    result = true;
+                    hitResult = m_items[i].m_result;
+                    break;
+                }
+            }
+            metric = HitHistogramMetric::MISS_VALIDITY_RECT_MATCHES;
+        }
+    }
+    Platform::current()->histogramEnumeration("Event.HitTest", static_cast<int>(metric), static_cast<int>(HitHistogramMetric::MAX_HIT_METRIC));
+    return result;
+}
+
+void HitTestCache::verify(const HitTestResult& result, const HitTestResult& cacheResult)
+{
+    bool pointMatch = cacheResult.hitTestLocation().point() == result.hitTestLocation().point();
+
+    VerifyHistogramMetric metric;
+    if (!cacheResult.equalForCacheability(result)) {
+        if (pointMatch) {
+            metric = result.hitTestLocation().isRectBasedTest() ? VerifyHistogramMetric::INCORRECT_RECT_BASED_EXACT_MATCH : VerifyHistogramMetric::INCORRECT_POINT_EXACT_MATCH;
+        } else {
+            metric = result.hitTestLocation().isRectBasedTest() ? VerifyHistogramMetric::INCORRECT_RECT_BASED_REGION : VerifyHistogramMetric::INCORRECT_POINT_REGION;
+        }
+
+        // ASSERT that the cache hit is the same as the actual result
+        ASSERT(false);
+    } else {
+        metric = pointMatch ? VerifyHistogramMetric::VALID_EXACT_MATCH : VerifyHistogramMetric::VALID_REGION;
+    }
+    Platform::current()->histogramEnumeration("Event.HitTestVerify", static_cast<int>(metric), static_cast<int>(VerifyHistogramMetric::MAX_VERIFY_METRIC));
+}
+
+void HitTestCache::cacheValue(const HitTestResult& result)

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

addCacheValue, in blink cacheValue() is a getter (I know cache is also a verb,
but  it's confusing here)

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

Done.

+{
+    // For now we don't support rect based hit results.
+    if (result.hitTestLocation().isRectBasedTest()) {
+        return;
+    }
+    m_items[m_updateIndex].m_result.cacheValues(result);
+    m_items[m_updateIndex].m_valid = true;
+
+    m_updateIndex++;
+    if (m_updateIndex >= arraysize(m_items))
+        m_updateIndex = 0;
+}
+
+void HitTestCache::clear()
+{
+    m_updateIndex = 0;
+    for (size_t i = 0; i < arraysize(m_items); ++i) {
+        if (m_items[i].m_valid) {
+            m_items[i].m_valid = false;
+            m_items[i].m_result = HitTestResult();
+        }
+    }
+}
+
+} // namespace blink