From 6e183a441def233594601b53c092734ec2a37520 Mon Sep 17 00:00:00 2001 From: Harrison Klaperman Date: Mon, 3 Apr 2017 16:31:57 -0700 Subject: [PATCH] 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 --- folly/futures/ManualExecutor.h | 6 ++-- folly/futures/test/ExecutorTest.cpp | 43 +++++++++++++++++++++++++++++ 2 files changed, 47 insertions(+), 2 deletions(-) diff --git a/folly/futures/ManualExecutor.h b/folly/futures/ManualExecutor.h index a37b92ff..d4fb8db6 100644 --- 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 index 02554638..d21f1079 100644 --- 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()); -- 2.34.1