Fix broken ManualExecutor

Summary: The priority queue in the manual executor implementation is backwards. This means that scheduled things run in reverse order, and a later thing will block an earlier thing if you advance to a timestamp in between the two. This diff fixes the problem and adds tests to confirm the fix. These tests fail on the old implementation. Reviewed By: yfeldblum Differential Revision: D4739101 fbshipit-source-id: 6e429828460df5b3c656580568a9ae1eb4009527
mtabebe · Apr 3, 2017 · 6e183a4 · 6e183a4
1 parent 30df094
commit 6e183a4
Show file tree

Hide file tree

Showing 2 changed files with 47 additions and 2 deletions.
diff --git a/folly/futures/ManualExecutor.h b/folly/futures/ManualExecutor.h
@@ -128,9 +128,11 @@ namespace folly {
       }
 
       bool operator<(ScheduledFunc const& b) const {
+        // Earlier-scheduled things must be *higher* priority
+        // in the max-based std::priority_queue
         if (time == b.time)
-          return ordinal < b.ordinal;
-        return time < b.time;
+          return ordinal > b.ordinal;
+        return time > b.time;
       }
 
       Func&& moveOutFunc() const {

diff --git a/folly/futures/test/ExecutorTest.cpp b/folly/futures/test/ExecutorTest.cpp
@@ -46,6 +46,49 @@ TEST(ManualExecutor, scheduleDur) {
   EXPECT_EQ(count, 1);
 }
 
+TEST(ManualExecutor, laterThingsDontBlockEarlierOnes) {
+  ManualExecutor x;
+  auto first = false;
+  std::chrono::milliseconds dur{10};
+  x.schedule([&] { first = true; }, dur);
+  x.schedule([] {}, 2 * dur);
+  EXPECT_FALSE(first);
+  x.advance(dur);
+  EXPECT_TRUE(first);
+}
+
+TEST(ManualExecutor, orderWillNotBeQuestioned) {
+  ManualExecutor x;
+  auto first = false;
+  auto second = false;
+  std::chrono::milliseconds dur{10};
+  x.schedule([&] { first = true; }, dur);
+  x.schedule([&] { second = true; }, 2 * dur);
+  EXPECT_FALSE(first);
+  EXPECT_FALSE(second);
+  x.advance(dur);
+  EXPECT_TRUE(first);
+  EXPECT_FALSE(second);
+  x.advance(dur);
+  EXPECT_TRUE(first);
+  EXPECT_TRUE(second);
+}
+
+TEST(ManualExecutor, evenWhenYouSkipAheadEventsRunInProperOrder) {
+  ManualExecutor x;
+  auto counter = 0;
+  auto first = 0;
+  auto second = 0;
+  std::chrono::milliseconds dur{10};
+  x.schedule([&] { first = ++counter; }, dur);
+  x.schedule([&] { second = ++counter; }, 2 * dur);
+  EXPECT_EQ(first, 0);
+  EXPECT_EQ(second, 0);
+  x.advance(3 * dur);
+  EXPECT_EQ(first, 1);
+  EXPECT_EQ(second, 2);
+}
+
 TEST(ManualExecutor, clockStartsAt0) {
   ManualExecutor x;
   EXPECT_EQ(x.now(), x.now().min());