Added touch event permutations test to touch_exploration_controller.

ui/chromeos/touch_exploration_controller_unittest.cc

Index: ui/chromeos/touch_exploration_controller_unittest.cc
diff --git a/ui/chromeos/touch_exploration_controller_unittest.cc b/ui/chromeos/touch_exploration_controller_unittest.cc
index 10da4b1f3a7f5a272d86d88d1a10daae2f1d1e22..b154135e7e7b7e9dcb0a6379e5fad5ef91d52436 100644
--- a/ui/chromeos/touch_exploration_controller_unittest.cc
+++ b/ui/chromeos/touch_exploration_controller_unittest.cc
@@ -13,6 +13,7 @@
 #include "ui/aura/window.h"
 #include "ui/events/event.h"
 #include "ui/events/event_utils.h"
+#include "ui/events/test/events_test_utils.h"
 #include "ui/gfx/geometry/point.h"
 #include "ui/gl/gl_implementation.h"
 #include "ui/gl/gl_surface.h"
@@ -57,6 +58,16 @@ class EventCapturer : public ui::EventHandler {
   DISALLOW_COPY_AND_ASSIGN(EventCapturer);
 };
 
+int Factorial(int n) {
+  if (n <= 0)
+    return 0;
+  if (n == 1)
+    return 1;
+  if (n == 2)
+      return 2;
+  return n * Factorial(n - 1);
+}
+
 }  // namespace
 
 class TouchExplorationTest : public aura::test::AuraTestBase {
@@ -948,4 +959,107 @@ TEST_F(TouchExplorationTest, Passthrough) {
   EXPECT_TRUE(IsInNoFingersDownState());
 }
 
+TEST_F(TouchExplorationTest, AllFingerPermutations) {
+  SwitchTouchExplorationMode(true);
+
+  // We will test all permutations of events from three different fingers
+  // to ensure that we return to NO_FINGERS_DOWN when fingers have been
+  // released.
+  ScopedVector<ui::TouchEvent> all_events;
+  for (int touch_id = 0; touch_id < 3; touch_id++){
+    int x = 10*touch_id + 1;

[aboxhall, 2014/06/30 18:19:36]

I think you might want to initialise these outside the for loop (and then
increment them at the end of the loop as well), otherwise you will have events
which are occurring at the same point but with different touch_ids.

Also, is there any reason you can't just increment them by one?

[evy, 2014/06/30 18:35:26]

Oh, yeah I guess I can just increment by one each.
I need to keep it inside the loop through, I think, because the events need to
occur at different points depending on the touch ids, which is why x and y are
initialized here using the touch_id value

+    int y = 10*touch_id + 2;
+    all_events.push_back(new TouchEvent(
+        ui::ET_TOUCH_PRESSED, gfx::Point(x, y), touch_id, Now()));
+    x += 2;
+    y += 2;
+    all_events.push_back(
+        new TouchEvent(ui::ET_TOUCH_MOVED, gfx::Point(x, y), touch_id, Now()));
+    x += 2;
+    y += 2;
+    all_events.push_back(new TouchEvent(
+        ui::ET_TOUCH_RELEASED, gfx::Point(x, y), touch_id, Now()));
+  }
+
+  // I'm going to explain this algorithm, and use an example in parenthesis.
+  // The example will be all permutations of a b c d.
+  // There are four letters and 4! = 24 permutations.
+  const int num_events = all_events.size();
+  const int num_permutations = Factorial(num_events);
+
+  for (int p = 0; p < num_permutations; p++) {
+    std::vector<ui::TouchEvent*> queued_events = all_events.get();
+    std::vector<bool> fingers_pressed(3, false);
+    // Branching out from the first event, there are num_permutations
+    // permutations, and each value of p is associated with one of these
+    // permutations. However, once the first event is chosen, there
+    // are now num_events - 1 events left, so the number of permutations
+    // for the rest of the events changes, and will always be equal to
+    // the factorial of the events_left.
+    // (e.g. There are 3! = 6 permutations that start with 'a', so if we
+    // start with 'a' there will be 6 ways to then choose from b c d.)
+    int current_num_permutations = num_permutations;
+    for (int events_left = num_events; events_left > 0; events_left--) {
+      // p indexes to each permutation when there are num_permutations
+      // permutations. (e.g. 0 is abcd and 1 is abdc.)
+      // But how do we find the index for current_num_permutations?

[aboxhall, 2014/06/30 18:19:36]

This sentence took me a couple of goes to understand. How about "To find the
permutation within the part of the sequence we're currently looking at, we need
a number..."

[evy, 2014/06/30 18:35:26]

Done.

+      // We need a number between 0 and current_num_permutations - 1.
+      // (e.g. if we already chose the first letter, there are 3! = 6
+      // options left, so we do p % 6. So current_permutation would go
+      // from 0 to 5 and then reset to 0 again, for all combinations of
+      // whichever three letters are remaining, as we loop through the
+      // permutations)
+      int current_permutation = p % current_num_permutations;
+      // Since this is is the total number of permutations starting with
+      // this event and including future events, there could be multiple
+      // values of current_permutation that will generate the same event
+      // in this iteration.
+      // (e.g. If we chose 'a' but have b c d to choose from, we choose b when
+      // current_permutation = 0, 1 and c when current_permutation = 2, 3.)
+      // So to figure out what current event we want to choose, we divide

[aboxhall, 2014/06/30 18:19:36]

This step is still a little unclear to me. I think you explained the
(current_num_permutations / events_left) part more clearly in the previous
patch.

I do think it might be clearer if you pulled that number out into a local
variable, particularly since you set current_num_permutations to the same number
below.

[evy, 2014/06/30 18:35:26]

Done.

+      // current_num_permutations by the  number of events to choose from,
+      // events_left. We then integer divide the current permutation by
+      // this new value.
+      // (e.g. If there are 4 letters a b c d and 24 permutations, we divide
+      // by 24/4 = 6. Values 0 to 5 when divided by 6 equals 0, so the first
+      // 6 permutations start with 'a', and the last 6 will start with 'd'.)
+      int index =
+          current_permutation / (current_num_permutations / events_left);
+      // We now adjust the current_num_permutations to be equal to the
+      // factorial of the next number of events left.
+      current_num_permutations /= events_left;

[aboxhall, 2014/06/30 18:19:36]

I think it's worth noting that this is just set-up for the next iteration.

[evy, 2014/06/30 18:35:26]

Done.

+
+      ui::TouchEvent* next_dispatch = queued_events[index];
+      ASSERT_TRUE(next_dispatch != NULL);
+      // |next_dispatch| has to be put in this container so that its time
+      // stamp can be changed to this point in the test, when it is being
+      // dispatched..
+      EventTestApi test_dispatch(next_dispatch);
+      test_dispatch.set_time_stamp(Now());
+      generator_->Dispatch(next_dispatch);
+      queued_events.erase(queued_events.begin() + index);
+      // Keep track of what fingers have been pressed, to release
+      // only those fingers at the end, so the check for being in
+      // no fingers down can be accurate.
+      if (next_dispatch->type() == ET_TOUCH_PRESSED) {
+        fingers_pressed[next_dispatch->touch_id()] = true;
+      } else if (next_dispatch->type() == ET_TOUCH_RELEASED) {
+        fingers_pressed[next_dispatch->touch_id()] = false;
+      }
+    }
+    ASSERT_EQ(queued_events.size(), 0u);
+
+    // Release fingers recorded as pressed.
+    for(int j = 0; j < int(fingers_pressed.size()); j++){
+      if (fingers_pressed[j] == true) {
+        generator_->ReleaseTouchId(j);
+        fingers_pressed[j] = false;
+      }
+    }
+    AdvanceSimulatedTimePastTapDelay();
+    EXPECT_TRUE(IsInNoFingersDownState());
+    ClearCapturedEvents();
+  }
+}
+
 }  // namespace ui