Fixing and enhancing OrderedSimpleTaskRunner to allow 100% deterministic tests.

cc/test/ordered_simple_task_runner.cc

Index: cc/test/ordered_simple_task_runner.cc
diff --git a/cc/test/ordered_simple_task_runner.cc b/cc/test/ordered_simple_task_runner.cc
index 188ffe72b5f8adea6208635d68263b3139811000..bf9ed29ddb0c06da8d3081721060a5efabf26b97 100644
--- a/cc/test/ordered_simple_task_runner.cc
+++ b/cc/test/ordered_simple_task_runner.cc
@@ -4,38 +4,311 @@
 
 #include "cc/test/ordered_simple_task_runner.h"
 
-#include <algorithm>
-#include <deque>
+#include <limits>
+#include <set>
+#include <sstream>
+#include <string>
+#include <vector>
 
-#include "base/logging.h"
+#include "base/debug/trace_event.h"
+#include "base/debug/trace_event_argument.h"
+#include "base/strings/string_number_conversions.h"
 
-namespace {
+#define TRACE_TASK(function, task) \
+  TRACE_EVENT_INSTANT1(            \
+      "cc", function, TRACE_EVENT_SCOPE_THREAD, "task", task.AsValue());
 
-bool TestPendingTaskComparator(const base::TestPendingTask& lhs,
-                               const base::TestPendingTask& rhs) {
-  return lhs.ShouldRunBefore(rhs);
+#define TRACE_TASK_RUN(function, tag, task)
+
+namespace cc {
+
+// TestOrderablePendingTask implementation
+TestOrderablePendingTask::TestOrderablePendingTask()
+    : base::TestPendingTask(),
+      task_id_(TestOrderablePendingTask::task_id_counter++) {
 }
 
+TestOrderablePendingTask::TestOrderablePendingTask(
+    const tracked_objects::Location& location,
+    const base::Closure& task,
+    base::TimeTicks post_time,
+    base::TimeDelta delay,
+    TestNestability nestability)
+    : base::TestPendingTask(location, task, post_time, delay, nestability),
+      task_id_(TestOrderablePendingTask::task_id_counter++) {
 }
 
-namespace cc {
+size_t TestOrderablePendingTask::task_id_counter = 0;
+
+TestOrderablePendingTask::~TestOrderablePendingTask() {
+}
 
-OrderedSimpleTaskRunner::OrderedSimpleTaskRunner() {}
+bool TestOrderablePendingTask::operator==(
+    const TestOrderablePendingTask& other) const {
+  return task_id_ == other.task_id_;
+}
+
+bool TestOrderablePendingTask::operator<(
+    const TestOrderablePendingTask& other) const {
+  if (*this == other)
+    return false;
+
+  if (GetTimeToRun() == other.GetTimeToRun()) {
+    return task_id_ < other.task_id_;
+  }
+  return ShouldRunBefore(other);
+}
+
+scoped_refptr<base::debug::ConvertableToTraceFormat>
+TestOrderablePendingTask::AsValue() const {
+  scoped_refptr<base::debug::TracedValue> state =
+      new base::debug::TracedValue();
+  AsValueInto(state);
+  return state;
+}
+
+void TestOrderablePendingTask::AsValueInto(
+    base::debug::TracedValue* state) const {
+  state->SetInteger("id", task_id_);
+  state->SetInteger("run_at", GetTimeToRun().ToInternalValue());
+  state->SetString("posted_from", location.ToString());
+}
+
+OrderedSimpleTaskRunner::OrderedSimpleTaskRunner()
+    : advance_now_(true),
+      now_src_(TestNowSource::Create(0)),
+      inside_run_tasks_until_(false) {
+}
+
+OrderedSimpleTaskRunner::OrderedSimpleTaskRunner(
+    scoped_refptr<TestNowSource> now_src,
+    bool advance_now)
+    : advance_now_(advance_now),
+      now_src_(now_src),
+      max_tasks_(absolute_max_tasks),
+      inside_run_tasks_until_(false) {
+}
 
 OrderedSimpleTaskRunner::~OrderedSimpleTaskRunner() {}
 
-void OrderedSimpleTaskRunner::RunPendingTasks() {
+// base::TestSimpleTaskRunner implementation
+bool OrderedSimpleTaskRunner::PostDelayedTask(
+    const tracked_objects::Location& from_here,
+    const base::Closure& task,
+    base::TimeDelta delay) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  TestOrderablePendingTask pt(
+      from_here, task, now_src_->Now(), delay, base::TestPendingTask::NESTABLE);
+
+  TRACE_TASK("OrderedSimpleTaskRunner::PostDelayedTask", pt);
+  pending_tasks_.insert(pt);
+  return true;
+}
+
+bool OrderedSimpleTaskRunner::PostNonNestableDelayedTask(
+    const tracked_objects::Location& from_here,
+    const base::Closure& task,
+    base::TimeDelta delay) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  TestOrderablePendingTask pt(from_here,
+                              task,
+                              now_src_->Now(),
+                              delay,
+                              base::TestPendingTask::NON_NESTABLE);
+
+  TRACE_TASK("OrderedSimpleTaskRunner::PostNonNestableDelayedTask", pt);
+  pending_tasks_.insert(pt);
+  return true;
+}
+
+bool OrderedSimpleTaskRunner::RunsTasksOnCurrentThread() const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return true;
+}
+
+base::TimeTicks OrderedSimpleTaskRunner::NextTaskTime() {
+  if (pending_tasks_.size() <= 0)

[Sami, 2014/09/01 11:35:33]

nit: Add braces

[mithro-old, 2014/09/01 12:00:19]

Done.

[Sami, 2014/09/01 12:50:29]

No need for them now but oh well :)

+    return base::TimeTicks::FromInternalValue(
+        std::numeric_limits<int64_t>::max());
+
+  return pending_tasks_.begin()->GetTimeToRun();
+}
+
+base::TimeDelta OrderedSimpleTaskRunner::DelayToNextTaskTime() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  if (pending_tasks_.size() <= 0)

[Sami, 2014/09/01 11:35:33]

nit: Add braces

[mithro-old, 2014/09/01 12:00:19]

Done.

+    return base::TimeDelta::FromInternalValue(
+        std::numeric_limits<int64_t>::max());
+
+  base::TimeDelta delay = NextTaskTime() - now_src_->Now();
+  if (delay > base::TimeDelta())
+    return delay;
+  return base::TimeDelta();
+}
+
+const size_t OrderedSimpleTaskRunner::absolute_max_tasks =
+    std::numeric_limits<size_t>::max();
+
+bool OrderedSimpleTaskRunner::RunTasks(base::Callback<bool(void)> condition) {
+  std::vector<base::Callback<bool(void)> > conditions(1);
+  conditions[0] = condition;
+  return RunTasks(conditions);
+}
+
+bool OrderedSimpleTaskRunner::RunTasks(
+    const std::vector<base::Callback<bool(void)> > conditions) {
+  TRACE_EVENT1(
+      "cc", "OrderedSimpleTaskRunner::RunPendingTasks", "this", AsValue());
   DCHECK(thread_checker_.CalledOnValidThread());
-  // Swap with a local variable to avoid re-entrancy problems.
-  std::deque<base::TestPendingTask> tasks_to_run;
-  tasks_to_run.swap(pending_tasks_);
-  std::stable_sort(tasks_to_run.begin(),
-                   tasks_to_run.end(),
-                   TestPendingTaskComparator);
-  for (std::deque<base::TestPendingTask>::iterator it = tasks_to_run.begin();
-       it != tasks_to_run.end(); ++it) {
-    it->task.Run();
+
+  // Make a copy so we can append some extra run checks.
+  std::vector<base::Callback<bool(void)> > modifiable_conditions(conditions);
+
+  // Provide a timeout base on number of tasks run so this doesn't loop
+  // forever.
+  modifiable_conditions.push_back(WhileTaskRunCountBelow(max_tasks_));
+
+  // If to advance now or not
+  if (!advance_now_) {
+    modifiable_conditions.push_back(WhileNowBefore(now_src_->Now()));
+  } else {
+    modifiable_conditions.push_back(AdvanceNow());

[Sami, 2014/09/01 11:35:33]

It's clever but having AdvanceNow() as a condition feels wrong, since always
returns true and is there just for the side-effect. How about inlining the code
in the run loop instead? I think it would be easier to read that way.

[mithro-old, 2014/09/01 12:00:19]

Actually, come to think of it - there is actually a condition AdvanceNow should
return false on, is kind of silly however? See the change...

I do think conditions having side effects is probably a very useful thing to
allow as it means you can use them to effect the running tasks?

[Sami, 2014/09/01 12:50:29]

I'm fine with conditions having side effects, but the problem with AdvanceNow()
is that it introduces an ordering constraint between conditions. It only really
works if it's the last condition. That's why I still feel it would be better to
just have three lines here:

   if (advance_now_ && now_src_->Now() < next_task_time) {
     now_src_->SetNow(next_task_time);
   }

The special case you added could also be an assertion here.

+  }
+
+  if (inside_run_tasks_until_)
+    return true;
+  inside_run_tasks_until_ = true;
+
+  while (pending_tasks_.size() > 0) {
+    // Check if we should continue to run pending tasks
+    for (std::vector<base::Callback<bool(void)> >::iterator it =
+             modifiable_conditions.begin();
+         it != modifiable_conditions.end();
+         it++) {
+      if (!it->Run()) {
+        goto run_tasks_exit;

[Sami, 2014/09/01 11:35:32]

I feel like I almost have to offer an alternative here :) How about wrapping
inside_run_tasks_until_ in a base::AutoReset and just returning here?

[mithro-old, 2014/09/01 12:00:19]

Done.

Never seen base::AutoReset before! LGTM.

+      }
+    }
+
+    std::set<TestOrderablePendingTask>::iterator task_to_run =
+        pending_tasks_.begin();
+    {
+      TRACE_EVENT1("cc",
+                   "OrderedSimpleTaskRunner::RunPendingTasks running",
+                   "task",
+                   task_to_run->AsValue());
+      task_to_run->task.Run();
+    }
+
+    pending_tasks_.erase(task_to_run);
+  }
+
+run_tasks_exit:
+
+  inside_run_tasks_until_ = false;
+  return pending_tasks_.size() > 0;
+}
+
+bool OrderedSimpleTaskRunner::RunPendingTasks() {
+  return RunTasks(WhileTaskExistedInitially());
+}
+
+bool OrderedSimpleTaskRunner::RunUntilIdle() {
+  return RunTasks(std::vector<base::Callback<bool(void)> >());
+}
+
+bool OrderedSimpleTaskRunner::RunUntilTime(base::TimeTicks time) {
+  // If we are not auto advancing, force now forward to the time.
+  if (!advance_now_ && now_src_->Now() < time)
+    now_src_->SetNow(time);
+
+  // Run tasks
+  bool result = RunTasks(WhileNowBefore(time));
+
+  // If the next task is after the stopping time and auto-advancing now, then
+  // force time to be the stopping time.
+  if (!result && advance_now_ && now_src_->Now() < time) {
+    now_src_->SetNow(time);
+  }
+
+  return result;
+}
+
+bool OrderedSimpleTaskRunner::RunForPeriod(base::TimeDelta period) {
+  return RunUntilTime(now_src_->Now() + period);
+}
+
+// base::debug tracing functionality
+scoped_refptr<base::debug::ConvertableToTraceFormat>
+OrderedSimpleTaskRunner::AsValue() const {
+  scoped_refptr<base::debug::TracedValue> state =
+      new base::debug::TracedValue();
+  AsValueInto(state);
+  return state;
+}
+
+void OrderedSimpleTaskRunner::AsValueInto(
+    base::debug::TracedValue* state) const {
+  state->SetInteger("pending_tasks", pending_tasks_.size());
+  for (std::set<TestOrderablePendingTask>::const_iterator it =
+           pending_tasks_.begin();
+       it != pending_tasks_.end();
+       ++it) {
+    state->BeginDictionary(
+        base::SizeTToString(std::distance(pending_tasks_.begin(), it)).c_str());
+    it->AsValueInto(state);
+    state->EndDictionary();
+  }
+  now_src_->AsValueInto(state);
+}
+
+base::Callback<bool(void)> OrderedSimpleTaskRunner::WhileTaskRunCountBelow(
+    size_t max_tasks) {
+  return base::Bind(&OrderedSimpleTaskRunner::WhileTaskRunCountBelowCallback,
+                    base::Unretained(this),
+                    max_tasks,
+                    base::Owned(new size_t(0)));
+}
+bool OrderedSimpleTaskRunner::WhileTaskRunCountBelowCallback(

[Sami, 2014/09/01 11:35:33]

nit: Add blank line.

[mithro-old, 2014/09/01 12:00:19]

Done.

+    size_t max_tasks,
+    size_t* tasks_run) {
+  return (*tasks_run)++ < max_tasks;
+}
+
+base::Callback<bool(void)>
+OrderedSimpleTaskRunner::WhileTaskExistedInitially() {
+  // base::Bind takes a copy of pending_tasks_
+  return base::Bind(&OrderedSimpleTaskRunner::WhileTaskExistedInitiallyCallback,
+                    base::Unretained(this),
+                    pending_tasks_);
+}
+bool OrderedSimpleTaskRunner::WhileTaskExistedInitiallyCallback(

[Sami, 2014/09/01 11:35:33]

nit: Add blank line.

[mithro-old, 2014/09/01 12:00:19]

Done.

+    const std::set<TestOrderablePendingTask>& existing_tasks) {
+  return existing_tasks.find(*pending_tasks_.begin()) != existing_tasks.end();
+}
+
+base::Callback<bool(void)> OrderedSimpleTaskRunner::WhileNowBefore(
+    base::TimeTicks stop_at) {
+  return base::Bind(&OrderedSimpleTaskRunner::WhileNowBeforeCallback,
+                    base::Unretained(this),
+                    stop_at);
+}
+bool OrderedSimpleTaskRunner::WhileNowBeforeCallback(base::TimeTicks stop_at) {

[Sami, 2014/09/01 11:35:33]

nit: add Blank line.

[mithro-old, 2014/09/01 12:00:19]

Done.

+  return NextTaskTime() <= stop_at;
+}
+
+base::Callback<bool(void)> OrderedSimpleTaskRunner::AdvanceNow() {
+  return base::Bind(&OrderedSimpleTaskRunner::AdvanceNowCallback,
+                    base::Unretained(this));
+}
+
+bool OrderedSimpleTaskRunner::AdvanceNowCallback() {
+  base::TimeTicks next_task_time = NextTaskTime();
+  if (now_src_->Now() < next_task_time) {
+    now_src_->SetNow(next_task_time);
   }
+  return true;
 }
 
 }  // namespace cc