Prevent flings in the direction opposite the user's finger movement.

This previously could occur, as we use a quadratic regression to estimate
finger velocity. Rapid deceleration would result in a fling in the
wrong direction.

BUG=417855
TEST=VelocityTrackerTest.NoDirectionReversal

Review URL: https://codereview.chromium.org/610583002

Cr-Commit-Position: refs/heads/master@{#301648}

12 files changed, 128 insertions, 36 deletions

diff --git a/ui/aura/gestures/gesture_recognizer_unittest.cc b/ui/aura/gestures/gesture_recognizer_unittest.cc
index 89e46b2..482fa60 100644
--- a/ui/aura/gestures/gesture_recognizer_unittest.cc
+++ b/ui/aura/gestures/gesture_recognizer_unittest.cc
@@ -3112,7 +3112,7 @@ TEST_F(GestureRecognizerTest, GestureEventScrollTwoFingerTouchMoveConsumed) {
 
   EXPECT_3_EVENTS(delegate->events(),
                   ui::ET_GESTURE_END,
-                  ui::ET_GESTURE_SCROLL_END,
+                  ui::ET_SCROLL_FLING_START,
                   ui::ET_GESTURE_END);
 }
 
diff --git a/ui/events/gesture_detection/gesture_configuration.cc b/ui/events/gesture_detection/gesture_configuration.cc
index 57a3060..b93ab06 100644
--- a/ui/events/gesture_detection/gesture_configuration.cc
+++ b/ui/events/gesture_detection/gesture_configuration.cc
@@ -32,6 +32,7 @@ GestureConfiguration::GestureConfiguration()
       // The default value of min_scaling_touch_major_ is 2 * default_radius_.
       min_scaling_touch_major_(50),
       min_swipe_velocity_(20),
+      velocity_tracker_strategy_(VelocityTracker::Strategy::STRATEGY_DEFAULT),
 // TODO(jdduke): Disable and remove entirely when issues with intermittent
 // scroll end detection on the Pixel are resolved, crbug.com/353702.
 #if defined(OS_CHROMEOS)
diff --git a/ui/events/gesture_detection/gesture_configuration.h b/ui/events/gesture_detection/gesture_configuration.h
index 983c665..de05e11 100644
--- a/ui/events/gesture_detection/gesture_configuration.h
+++ b/ui/events/gesture_detection/gesture_configuration.h
@@ -8,6 +8,7 @@
 #include "base/basictypes.h"
 #include "base/memory/singleton.h"
 #include "ui/events/gesture_detection/gesture_detection_export.h"
+#include "ui/events/gesture_detection/velocity_tracker.h"
 
 namespace ui {
 
@@ -117,6 +118,9 @@ class GESTURE_DETECTION_EXPORT GestureConfiguration {
   int semi_long_press_time_in_ms() const {
     return semi_long_press_time_in_ms_;
   }
+  VelocityTracker::Strategy velocity_tracker_strategy() const {
+    return velocity_tracker_strategy_;
+  }
   void set_semi_long_press_time_in_ms(int val) {
     semi_long_press_time_in_ms_ = val;
     double_tap_timeout_in_ms_ = val;
@@ -163,6 +167,9 @@ class GESTURE_DETECTION_EXPORT GestureConfiguration {
   void set_min_scaling_touch_major(float val) {
     min_scaling_touch_major_ = val;
   }
+  void set_velocity_tracker_strategy(VelocityTracker::Strategy val) {
+    velocity_tracker_strategy_ = val;
+  }
   void set_span_slop(float val) { span_slop_ = val; }
   void set_swipe_enabled(bool val) { swipe_enabled_ = val; }
   void set_two_finger_tap_enabled(bool val) { two_finger_tap_enabled_ = val; }
@@ -204,6 +211,7 @@ class GESTURE_DETECTION_EXPORT GestureConfiguration {
   float min_scaling_span_in_pixels_;
   float min_scaling_touch_major_;
   float min_swipe_velocity_;
+  VelocityTracker::Strategy velocity_tracker_strategy_;
   int scroll_debounce_interval_in_ms_;
   int semi_long_press_time_in_ms_;
   int show_press_delay_in_ms_;
diff --git a/ui/events/gesture_detection/gesture_configuration_aura.cc b/ui/events/gesture_detection/gesture_configuration_aura.cc
index 1106ca3..5561688 100644
--- a/ui/events/gesture_detection/gesture_configuration_aura.cc
+++ b/ui/events/gesture_detection/gesture_configuration_aura.cc
@@ -29,6 +29,7 @@ class GestureConfigurationAura : public GestureConfiguration {
             switches::kCompensateForUnstablePinchZoom)
             ? 5 : 0);
     set_min_scaling_touch_major(default_radius() * 2);
+    set_velocity_tracker_strategy(VelocityTracker::Strategy::LSQ2_RESTRICTED);
     set_span_slop(max_touch_move_in_pixels_for_click() * 2);
     set_swipe_enabled(true);
     set_two_finger_tap_enabled(true);
diff --git a/ui/events/gesture_detection/gesture_detector.cc b/ui/events/gesture_detection/gesture_detector.cc
index c092448..50cae59 100644
--- a/ui/events/gesture_detection/gesture_detector.cc
+++ b/ui/events/gesture_detection/gesture_detector.cc
@@ -53,7 +53,8 @@ GestureDetector::Config::Config()
       maximum_swipe_deviation_angle(20.f),
       two_finger_tap_enabled(false),
       two_finger_tap_max_separation(300),
-      two_finger_tap_timeout(base::TimeDelta::FromMilliseconds(700)) {
+      two_finger_tap_timeout(base::TimeDelta::FromMilliseconds(700)),
+      velocity_tracker_strategy(VelocityTracker::Strategy::STRATEGY_DEFAULT) {
 }
 
 GestureDetector::Config::~Config() {}
@@ -134,7 +135,8 @@ GestureDetector::GestureDetector(
       longpress_enabled_(true),
       showpress_enabled_(true),
       swipe_enabled_(false),
-      two_finger_tap_enabled_(false) {
+      two_finger_tap_enabled_(false),
+      velocity_tracker_(config.velocity_tracker_strategy) {
   DCHECK(listener_);
   Init(config);
 }
diff --git a/ui/events/gesture_detection/gesture_detector.h b/ui/events/gesture_detection/gesture_detector.h
index 91b2786..07e90e1 100644
--- a/ui/events/gesture_detection/gesture_detector.h
+++ b/ui/events/gesture_detection/gesture_detector.h
@@ -68,6 +68,8 @@ class GESTURE_DETECTION_EXPORT GestureDetector {
 
     // Maximum time the second pointer can be active for a two finger tap.
     base::TimeDelta two_finger_tap_timeout;
+
+    VelocityTracker::Strategy velocity_tracker_strategy;
   };
 
   GestureDetector(const Config& config,
diff --git a/ui/events/gesture_detection/gesture_provider_config_helper.cc b/ui/events/gesture_detection/gesture_provider_config_helper.cc
index c5e9d70..537bd72 100644
--- a/ui/events/gesture_detection/gesture_provider_config_helper.cc
+++ b/ui/events/gesture_detection/gesture_provider_config_helper.cc
@@ -33,6 +33,8 @@ GestureDetector::Config DefaultGestureDetectorConfig(
       gesture_config->max_distance_for_two_finger_tap_in_pixels();
   config.two_finger_tap_timeout = base::TimeDelta::FromMilliseconds(
       gesture_config->max_touch_down_duration_for_click_in_ms());
+  config.velocity_tracker_strategy =
+      gesture_config->velocity_tracker_strategy();
   return config;
 }
 
diff --git a/ui/events/gesture_detection/velocity_tracker.cc b/ui/events/gesture_detection/velocity_tracker.cc
index 46f87d4..782d926 100644
--- a/ui/events/gesture_detection/velocity_tracker.cc
+++ b/ui/events/gesture_detection/velocity_tracker.cc
@@ -113,12 +113,24 @@ class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
     WEIGHTING_RECENT,
   };
 
+  enum Restriction {
+    // There's no restriction on the output of the velocity tracker.
+    RESTRICTION_NONE,
+
+    // If the velocity determined by the tracker is in a sufficiently different
+    // direction from the primary motion of the finger for the events being
+    // considered for velocity calculation, return a velocity of 0.
+    RESTRICTION_ALIGNED_DIRECTIONS
+  };
+
   // Number of samples to keep.
   static const uint8_t kHistorySize = 20;
 
   // Degree must be no greater than Estimator::kMaxDegree.
-  LeastSquaresVelocityTrackerStrategy(uint32_t degree,
-                                      Weighting weighting = WEIGHTING_NONE);
+  LeastSquaresVelocityTrackerStrategy(
+      uint32_t degree,
+      Weighting weighting,
+      Restriction restriction);
   ~LeastSquaresVelocityTrackerStrategy() override;
 
   void Clear() override;
@@ -148,6 +160,7 @@ class LeastSquaresVelocityTrackerStrategy : public VelocityTrackerStrategy {
 
   const uint32_t degree_;
   const Weighting weighting_;
+  const Restriction restriction_;
   uint32_t index_;
   Movement movements_[kHistorySize];
 };
@@ -192,28 +205,40 @@ class IntegratingVelocityTrackerStrategy : public VelocityTrackerStrategy {
 };
 
 VelocityTrackerStrategy* CreateStrategy(VelocityTracker::Strategy strategy) {
+  LeastSquaresVelocityTrackerStrategy::Weighting none =
+      LeastSquaresVelocityTrackerStrategy::WEIGHTING_NONE;
+  LeastSquaresVelocityTrackerStrategy::Restriction no_restriction =
+      LeastSquaresVelocityTrackerStrategy::RESTRICTION_NONE;
   switch (strategy) {
     case VelocityTracker::LSQ1:
-      return new LeastSquaresVelocityTrackerStrategy(1);
+      return new LeastSquaresVelocityTrackerStrategy(1, none, no_restriction);
     case VelocityTracker::LSQ2:
-      return new LeastSquaresVelocityTrackerStrategy(2);
+      return new LeastSquaresVelocityTrackerStrategy(2, none, no_restriction);
+    case VelocityTracker::LSQ2_RESTRICTED:
+      return new LeastSquaresVelocityTrackerStrategy(
+          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_NONE,
+          LeastSquaresVelocityTrackerStrategy::RESTRICTION_ALIGNED_DIRECTIONS);
     case VelocityTracker::LSQ3:
-      return new LeastSquaresVelocityTrackerStrategy(3);
+      return new LeastSquaresVelocityTrackerStrategy(3, none, no_restriction);
     case VelocityTracker::WLSQ2_DELTA:
       return new LeastSquaresVelocityTrackerStrategy(
-          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_DELTA);
+          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_DELTA,
+          no_restriction);
     case VelocityTracker::WLSQ2_CENTRAL:
       return new LeastSquaresVelocityTrackerStrategy(
-          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_CENTRAL);
+          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_CENTRAL,
+          no_restriction);
     case VelocityTracker::WLSQ2_RECENT:
       return new LeastSquaresVelocityTrackerStrategy(
-          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_RECENT);
+          2, LeastSquaresVelocityTrackerStrategy::WEIGHTING_RECENT,
+          no_restriction);
     case VelocityTracker::INT1:
       return new IntegratingVelocityTrackerStrategy(1);
     case VelocityTracker::INT2:
       return new IntegratingVelocityTrackerStrategy(2);
   }
   NOTREACHED() << "Unrecognized velocity tracker strategy: " << strategy;
+  // Quadratic regression is a safe default.
   return CreateStrategy(VelocityTracker::STRATEGY_DEFAULT);
 }
 
@@ -221,11 +246,6 @@ VelocityTrackerStrategy* CreateStrategy(VelocityTracker::Strategy strategy) {
 
 // --- VelocityTracker ---
 
-VelocityTracker::VelocityTracker()
-    : current_pointer_id_bits_(0),
-      active_pointer_id_(-1),
-      strategy_(CreateStrategy(STRATEGY_DEFAULT)) {}
-
 VelocityTracker::VelocityTracker(Strategy strategy)
     : current_pointer_id_bits_(0),
       active_pointer_id_(-1),
@@ -391,8 +411,11 @@ bool VelocityTracker::GetEstimator(uint32_t id,
 
 LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(
     uint32_t degree,
-    Weighting weighting)
-    : degree_(degree), weighting_(weighting) {
+    Weighting weighting,
+    Restriction restriction)
+    : degree_(degree),
+      weighting_(weighting),
+      restriction_(restriction) {
   DCHECK_LT(degree_, static_cast<uint32_t>(Estimator::kMaxDegree));
   Clear();
 }
@@ -578,11 +601,14 @@ bool LeastSquaresVelocityTrackerStrategy::GetEstimator(
   uint32_t index = index_;
   const base::TimeDelta horizon = base::TimeDelta::FromMilliseconds(kHorizonMS);
   const Movement& newest_movement = movements_[index_];
+  const Movement* first_movement = nullptr;
+
   do {
     const Movement& movement = movements_[index];
     if (!movement.id_bits.has_bit(id))
       break;
 
+    first_movement = &movement;
     TimeDelta age = newest_movement.event_time - movement.event_time;
     if (age > horizon)
       break;
@@ -608,6 +634,19 @@ bool LeastSquaresVelocityTrackerStrategy::GetEstimator(
     uint32_t n = degree + 1;
     if (SolveLeastSquares(time, x, w, m, n, out_estimator->xcoeff, &xdet) &&
         SolveLeastSquares(time, y, w, m, n, out_estimator->ycoeff, &ydet)) {
+      if (restriction_ == RESTRICTION_ALIGNED_DIRECTIONS) {
+        DCHECK(first_movement);
+        float dx = newest_movement.GetPosition(id).x -
+                   first_movement->GetPosition(id).x;
+        float dy = newest_movement.GetPosition(id).y -
+                   first_movement->GetPosition(id).y;
+
+        // If the velocity is in a sufficiently different direction from the
+        // primary movement, ignore it.
+        if (out_estimator->xcoeff[1] * dx + out_estimator->ycoeff[1] * dy < 0)
+          return false;
+      }
+
       out_estimator->time = newest_movement.event_time;
       out_estimator->degree = degree;
       out_estimator->confidence = xdet * ydet;
diff --git a/ui/events/gesture_detection/velocity_tracker.h b/ui/events/gesture_detection/velocity_tracker.h
index 8147695..8a57150 100644
--- a/ui/events/gesture_detection/velocity_tracker.h
+++ b/ui/events/gesture_detection/velocity_tracker.h
@@ -42,10 +42,20 @@ class VelocityTracker {
 
     // 2nd order least squares.  Quality: VERY GOOD.
     // Pretty much ideal, but can be confused by certain kinds of touch data,
-    // particularly if the panel has a tendency to generate delayed,
-    // duplicate or jittery touch coordinates when the finger is released.
+    // particularly if the panel has a tendency to generate delayed, duplicate
+    // or jittery touch coordinates when the finger is released.  This is the
+    // default velocity tracker strategy.  Although other strategies are
+    // available for testing and comparison purposes, this is the strategy that
+    // applications will actually use.  Be very careful when adjusting the
+    // default strategy because it can dramatically affect (often in a bad way)
+    // the user experience.
     LSQ2,
 
+    // The same as LSQ2, but reports 0 if the direction of the velocity returned
+    // is sufficiently different from the primary direction of movement of the
+    // touches contributing to the velocity.
+    LSQ2_RESTRICTED,
+
     // 3rd order least squares.  Quality: UNUSABLE.
     // Frequently overfits the touch data yielding wildly divergent estimates
     // of the velocity when the finger is released.
@@ -78,16 +88,9 @@ class VelocityTracker {
     STRATEGY_MAX = INT2,
 
     // The default velocity tracker strategy.
-    // Although other strategies are available for testing and comparison
-    // purposes, this is the strategy that applications will actually use.  Be
-    // very careful when adjusting the default strategy because it can
-    // dramatically affect (often in a bad way) the user experience.
     STRATEGY_DEFAULT = LSQ2,
   };
 
-  // Creates a velocity tracker using the default strategy for the platform.
-  VelocityTracker();
-
   // Creates a velocity tracker using the specified strategy.
   // If strategy is NULL, uses the default strategy for the platform.
   explicit VelocityTracker(Strategy strategy);
@@ -133,8 +136,7 @@ class VelocityTracker {
                    const Position* positions);
 
   // Gets an estimator for the recent movements of the specified pointer id.
-  // Returns false and clears the estimator if there is no information available
-  // about the pointer.
+  // Returns false if the pointer velocity is unknown.
   bool GetEstimator(uint32_t id, Estimator* out_estimator) const;
 
   base::TimeTicks last_event_time_;
diff --git a/ui/events/gesture_detection/velocity_tracker_state.cc b/ui/events/gesture_detection/velocity_tracker_state.cc
index 1216856..fdae25f 100644
--- a/ui/events/gesture_detection/velocity_tracker_state.cc
+++ b/ui/events/gesture_detection/velocity_tracker_state.cc
@@ -13,10 +13,6 @@ namespace {
 const int ACTIVE_POINTER_ID = -1;
 }
 
-VelocityTrackerState::VelocityTrackerState()
-    : velocity_tracker_(VelocityTracker::STRATEGY_DEFAULT),
-      active_pointer_id_(ACTIVE_POINTER_ID) {}
-
 VelocityTrackerState::VelocityTrackerState(VelocityTracker::Strategy strategy)
     : velocity_tracker_(strategy), active_pointer_id_(ACTIVE_POINTER_ID) {}
 
diff --git a/ui/events/gesture_detection/velocity_tracker_state.h b/ui/events/gesture_detection/velocity_tracker_state.h
index 780871c..37906f5 100644
--- a/ui/events/gesture_detection/velocity_tracker_state.h
+++ b/ui/events/gesture_detection/velocity_tracker_state.h
@@ -20,7 +20,6 @@ class MotionEvent;
 // * Please update the Change-Id as upstream Android changes are pulled.
 class GESTURE_DETECTION_EXPORT VelocityTrackerState {
  public:
-  VelocityTrackerState();
   explicit VelocityTrackerState(VelocityTracker::Strategy strategy);
   ~VelocityTrackerState();
 
diff --git a/ui/events/gesture_detection/velocity_tracker_unittest.cc b/ui/events/gesture_detection/velocity_tracker_unittest.cc
index 1fa5edc..85a1f5d 100644
--- a/ui/events/gesture_detection/velocity_tracker_unittest.cc
+++ b/ui/events/gesture_detection/velocity_tracker_unittest.cc
@@ -27,6 +27,7 @@ const char* GetStrategyName(VelocityTracker::Strategy strategy) {
   switch (strategy) {
     case VelocityTracker::LSQ1: return "LSQ1";
     case VelocityTracker::LSQ2: return "LSQ2";
+    case VelocityTracker::LSQ2_RESTRICTED: return "LSQ2_RESTRICTED";
     case VelocityTracker::LSQ3: return "LSQ3";
     case VelocityTracker::WLSQ2_DELTA: return "WLSQ2_DELTA";
     case VelocityTracker::WLSQ2_CENTRAL: return "WLSQ2_CENTRAL";
@@ -127,7 +128,7 @@ TEST_F(VelocityTrackerTest, MaxVelocity) {
   const size_t samples = 3;
   const base::TimeDelta dt = kTenMillis * 2;
 
-  VelocityTrackerState state;
+  VelocityTrackerState state(VelocityTracker::Strategy::LSQ2);
   ApplyMovementSequence(&state, p0, v, TimeTicks::Now(), dt, samples);
 
   // The computed velocity should be restricted to the provided maximum.
@@ -197,7 +198,7 @@ TEST_F(VelocityTrackerTest, DelayedActionUp) {
   const base::TimeTicks t0 = base::TimeTicks::Now();
   const base::TimeDelta dt = kTenMillis * 2;
 
-  VelocityTrackerState state;
+  VelocityTrackerState state(VelocityTracker::Strategy::LSQ2);
   state.AddMovement(
       Sample(MotionEvent::ACTION_DOWN, p0, t0, v, base::TimeDelta()));
 
@@ -219,4 +220,43 @@ TEST_F(VelocityTrackerTest, DelayedActionUp) {
   EXPECT_EQ(0.f, state.GetYVelocity(0));
 }
 
+// Tests that a rapid deceleration won't result in a velocity going in the
+// opposite direction to the pointers primary movement, with the LSQ_RESTRICTED
+// strategy. See crbug.com/417855.
+TEST_F(VelocityTrackerTest, NoDirectionReversal) {
+  VelocityTrackerState state_unrestricted(VelocityTracker::LSQ2);
+  VelocityTrackerState state_restricted(VelocityTracker::LSQ2_RESTRICTED);
+  const base::TimeTicks t0 = base::TimeTicks::Now();
+  const base::TimeDelta dt = base::TimeDelta::FromMilliseconds(1);
+  const size_t samples = 60;
+
+  gfx::PointF p(0, 0);
+
+  MockMotionEvent m1(MotionEvent::ACTION_DOWN, t0, p.x(), p.y());
+  state_unrestricted.AddMovement(m1);
+  state_restricted.AddMovement(m1);
+
+  for (size_t i = 0; i < samples; ++i) {
+    if (i < 50)
+      p.set_y(p.y() + 10);
+    MockMotionEvent mi(MotionEvent::ACTION_MOVE, t0 + dt * i, p.x(), p.y());
+    state_unrestricted.AddMovement(mi);
+    state_restricted.AddMovement(mi);
+  }
+
+  // The computed velocity be zero, as we stopped at the end of the gesture. In
+  // particular, it should not be negative, as all movement was in the positive
+  // direction.
+  state_restricted.ComputeCurrentVelocity(1000, 20000);
+  EXPECT_EQ(0, state_restricted.GetXVelocity(0));
+  EXPECT_EQ(0, state_restricted.GetYVelocity(0));
+
+  // This does not hold for the unrestricted LSQ2 strategy.
+  state_unrestricted.ComputeCurrentVelocity(1000, 20000);
+  EXPECT_EQ(0, state_unrestricted.GetXVelocity(0));
+  // Y velocity is negative, despite the fact that the finger only moved in the
+  // positive y direction.
+  EXPECT_GT(0, state_unrestricted.GetYVelocity(0));
+}
+
 }  // namespace ui