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..3c27d493ff34a4c889a96a1c6fa9db90c1d8b120
--- /dev/null
+++ b/Source/core/layout/HitTestCache.cpp
@@ -0,0 +1,86 @@
+// 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"
+
+namespace blink {
+
+bool HitTestCache::lookupCachedResult(HitTestResult& hitResult, uint64_t domTreeVersion)
+{
+    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.
+    } else if (domTreeVersion == m_domTreeVersion && !hitResult.hitTestLocation().isRectBasedTest()) {
+        for (size_t i = 0; i < WTF_ARRAY_LENGTH(m_items) && m_items[i].valid; ++i) {
+            if (m_items[i].result.validityRect().contains(hitResult.hitTestLocation().point())) {
+                if (hitResult.hitTestRequest().equalForCacheability(m_items[i].result.hitTestRequest())) {
+                    metric = hitResult.hitTestLocation().point() == m_items[i].result.hitTestLocation().point() ? HitHistogramMetric::HIT_EXACT_MATCH : HitHistogramMetric::HIT_REGION_MATCH;
+                    result = true;
+                    hitResult = m_items[i].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& expected, const HitTestResult& actual)
+{
+    bool pointMatch = actual.hitTestLocation().point() == expected.hitTestLocation().point();
+
+    ValidityHistogramMetric metric;
+    if (!actual.equalForCacheability(expected)) {
+        if (pointMatch) {
+            metric = expected.hitTestLocation().isRectBasedTest() ? ValidityHistogramMetric::INCORRECT_RECT_BASED_EXACT_MATCH : ValidityHistogramMetric::INCORRECT_POINT_EXACT_MATCH;
+        } else {
+            metric = expected.hitTestLocation().isRectBasedTest() ? ValidityHistogramMetric::INCORRECT_RECT_BASED_REGION : ValidityHistogramMetric::INCORRECT_POINT_REGION;
+        }
+
+        // ASSERT that the cache hit is the same as the actual result
+        ASSERT(false);
+    } else {
+        metric = pointMatch ? ValidityHistogramMetric::VALID_EXACT_MATCH : ValidityHistogramMetric::VALID_REGION;
+    }
+    Platform::current()->histogramEnumeration("Event.HitTestValidity", static_cast<int>(metric), static_cast<int>(ValidityHistogramMetric::MAX_VALIDITY_METRIC));
+}
+
+void HitTestCache::addCachedResult(const HitTestResult& result, uint64_t domTreeVersion)
+{
+    // For now we don't support rect based hit results.
+    if (result.hitTestLocation().isRectBasedTest()) {
+        return;
+    }
+    if (domTreeVersion != m_domTreeVersion) {
+        clear();
+    }
+
+    m_items[m_updateIndex].result.cacheValues(result);
+    m_items[m_updateIndex].valid = true;
+    m_domTreeVersion = domTreeVersion;
+
+    m_updateIndex++;
+    if (m_updateIndex >= WTF_ARRAY_LENGTH(m_items))
+        m_updateIndex = 0;
+}
+
+void HitTestCache::clear()
+{
+    m_updateIndex = 0;
+    for (size_t i = 0; i < WTF_ARRAY_LENGTH(m_items); ++i) {
+        if (m_items[i].valid) {
+            m_items[i].valid = false;
+            m_items[i].result = HitTestResult();
+        }
+    }
+}
+
+} // namespace blink