Add UserInputTracker, which keeps track of recent user input events.

chrome/browser/page_load_metrics/user_input_tracker.cc

+// Copyright 2016 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 "chrome/browser/page_load_metrics/user_input_tracker.h"
+
+#include <algorithm>
+
+#include "third_party/WebKit/public/platform/WebInputEvent.h"
+
+namespace page_load_metrics {
+
+namespace {
+
+// Blink's UserGestureIndicator allows events to be associated with gestures
+// that are up to 1 second old, based on guidance in the HTML spec:
+// https://html.spec.whatwg.org/multipage/interaction.html#triggered-by-user-activation.
+const int kMaxEventAgeSeconds = 1;
+
+// Allow for up to 2x the oldest time. This allows consumers to continue to
+// find events for timestamps up to 1 second in the past.
+const int kOldestAllowedEventAgeSeconds = kMaxEventAgeSeconds * 2;
+
+// In order to limit to at most kMaxTrackedEvents, we rate limit the recorded
+// events,
+// allowing one per rate limit period.
+const int kRateLimitClampMillis = (kOldestAllowedEventAgeSeconds * 1000) /
+                                  UserInputTracker::kMaxTrackedEvents;
+
+bool IsInterestingInputEvent(const blink::WebInputEvent& event) {
+  // Ignore synthesized auto repeat events.
+  if (event.modifiers & blink::WebInputEvent::IsAutoRepeat)
+    return false;
+
+  switch (event.type) {
+    case blink::WebInputEvent::MouseDown:
+    case blink::WebInputEvent::MouseUp:
+    case blink::WebInputEvent::RawKeyDown:
+    case blink::WebInputEvent::KeyDown:
+    case blink::WebInputEvent::Char:
+    case blink::WebInputEvent::TouchStart:
+    case blink::WebInputEvent::TouchEnd:
+      return true;
+    default:
+      return false;
+  }
+}
+
+base::TimeTicks GetTimeTicksFromSeconds(double seconds) {
+  // WebInputEvent::timeStampSeconds is a double representing number of
+  // monotonic seconds in TimeTicks time base. There's no convenience API for
+  // initializing a TimeTicks from such a value. The canonical way to perform
+  // this initialization is to create a TimeTicks with value 0 and add a
+  // TimeDelta to it.
+  return base::TimeTicks() + base::TimeDelta::FromSecondsD(seconds);
+}
+
+}  // namespace
+
+UserInputTracker::UserInputTracker() {
+  sorted_event_times_.reserve(kMaxTrackedEvents);
+}
+
+UserInputTracker::~UserInputTracker() {}
+
+const size_t UserInputTracker::kMaxTrackedEvents = 100;
+
+// static
+base::TimeTicks UserInputTracker::GetEventTime(
+    const blink::WebInputEvent& event) {
+  return GetTimeTicksFromSeconds(event.timeStampSeconds);
+}
+
+// static
+base::TimeTicks UserInputTracker::RoundToRateLimitedOffset(
+    base::TimeTicks time) {
+  base::TimeDelta time_as_delta = time - base::TimeTicks();
+  base::TimeDelta rate_limit_remainder =
+      time_as_delta % base::TimeDelta::FromMilliseconds(kRateLimitClampMillis);
+  return time - rate_limit_remainder;
+}
+
+void UserInputTracker::OnInputEvent(const blink::WebInputEvent& event) {
+  RemoveOldInputEvents();
+
+  if (!IsInterestingInputEvent(event))
+    return;
+
+  // TODO(bmcquade): ideally we'd limit tracking to events generated by a user
+  // action, as opposed to those generated from JavaScript. The JS API isTrusted
+  // can be used to distinguish these cases. isTrusted isn't yet a property of
+  // WebInputEvent. We should consider adding it.
+
+  const base::TimeTicks now = base::TimeTicks::Now();
+  base::TimeTicks time = RoundToRateLimitedOffset(GetEventTime(event));
+  if (time <=
+      std::max(most_recent_consumed_time_, GetOldestAllowedEventTime(now)))
+    return;
+
+  if (time > now) {
+    DCHECK(!base::TimeTicks::IsHighResolution());
+    return;
+  }
+
+  // lower_bound finds the first element >= |time|.
+  auto it = std::lower_bound(sorted_event_times_.begin(),
+                             sorted_event_times_.end(), time);
+  if (it != sorted_event_times_.end() && *it == time) {
+    // Don't insert duplicate values.
+    return;
+  }
+
+  sorted_event_times_.insert(it, time);
+  DCHECK(sorted_event_times_.size() <= kMaxTrackedEvents);

[Charlie Harrison, 2016/12/06 18:43:09]

DCHECK_LE

[Bryan McQuade, 2016/12/06 20:10:03]

Done

+  DCHECK(
+      std::is_sorted(sorted_event_times_.begin(), sorted_event_times_.end()));
+}
+
+bool UserInputTracker::FindAndConsumeInputEventsBefore(base::TimeTicks time) {
+  base::TimeTicks recent_input_event_time =
+      FindMostRecentUserInputEventBefore(time);
+
+  if (recent_input_event_time.is_null())
+    return false;
+
+  RemoveInputEventsUpToInclusive(recent_input_event_time);
+  return true;
+}
+
+base::TimeTicks UserInputTracker::FindMostRecentUserInputEventBefore(
+    base::TimeTicks time) {
+  RemoveOldInputEvents();
+
+  if (sorted_event_times_.empty())
+    return base::TimeTicks();
+
+  // lower_bound finds the first element >= |time|.
+  auto it = std::lower_bound(sorted_event_times_.begin(),
+                             sorted_event_times_.end(), time);
+
+  // If all times are after the requested time, then we don't have a time to
+  // return.
+  if (it == sorted_event_times_.begin())
+    return base::TimeTicks();
+
+  // |it| points to the first event >= the specified time, so decrement once to
+  // find the greatest event before the specified time.
+  --it;
+  base::TimeTicks candidate = *it;
+  DCHECK(candidate < time);

[Charlie Harrison, 2016/12/06 18:43:09]

DCHECK_LT

[Bryan McQuade, 2016/12/06 20:10:03]

Done

+
+  // If the most recent event is too old, then don't return it.
+  if (candidate < time - base::TimeDelta::FromSeconds(kMaxEventAgeSeconds))
+    return base::TimeTicks();
+
+  return candidate;
+}
+
+void UserInputTracker::RemoveOldInputEvents() {
+  RemoveInputEventsUpToInclusive(
+      GetOldestAllowedEventTime(base::TimeTicks::Now()));
+}
+
+void UserInputTracker::RemoveInputEventsUpToInclusive(base::TimeTicks cutoff) {
+  cutoff = std::max(RoundToRateLimitedOffset(cutoff),
+                    GetOldestAllowedEventTime(base::TimeTicks::Now()));
+  most_recent_consumed_time_ = std::max(most_recent_consumed_time_, cutoff);
+  sorted_event_times_.erase(
+      sorted_event_times_.begin(),
+      std::upper_bound(sorted_event_times_.begin(), sorted_event_times_.end(),
+                       cutoff));
+}
+
+// static
+base::TimeTicks UserInputTracker::GetOldestAllowedEventTime(
+    base::TimeTicks now) {
+  return now - base::TimeDelta::FromSeconds(kOldestAllowedEventAgeSeconds);
+}
+
+}  // namespace page_load_metrics