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..6ffe241e34628d1a11ff67b02529b08b38e94b7a 100644
--- a/cc/test/ordered_simple_task_runner.cc
+++ b/cc/test/ordered_simple_task_runner.cc
@@ -4,38 +4,358 @@
 
 #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::TestOrderablePendingTask::task_id_counter = 0;
 
-OrderedSimpleTaskRunner::OrderedSimpleTaskRunner() {}
+TestOrderablePendingTask::~TestOrderablePendingTask() {
+}
+
+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;
+}
+
+//
+bool OrderedSimpleTaskRunner::RunPendingTasks() {
+  return RunTasksUntil(RunOnlyExisting(this));
+}
+
+bool OrderedSimpleTaskRunner::RunUntilIdle() {
+  std::vector<base::Callback<bool(void)> > check_callbacks;
+  return RunTasksUntil(check_callbacks);
+}
+
+bool OrderedSimpleTaskRunner::RunForPeriod(base::TimeDelta period) {
+  return RunUntilTime(now_src_->Now() + period);
+}
+
+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 = RunTasksUntil(RunOnlyBefore(this, now_src_, time));
+
+  // If we didn't end up at exactly the time given, force now forward to the
+  // time.
+  if (!result || pending_tasks_.begin()->GetTimeToRun() > time)
+    now_src_->SetNow(time);
+
+  return result;
+}
+
+bool OrderedSimpleTaskRunner::RunTasksUntil(const RunCheck& check_callback) {
+  return RunTasksUntil(check_callback.AsCallback());
+}
+
+bool OrderedSimpleTaskRunner::RunTasksUntil(RunCheck* check_callback) {
+  return RunTasksUntil(check_callback->AsCallback());
+}
+
+bool OrderedSimpleTaskRunner::RunTasksUntil(
+    const std::vector<RunCheck*> check_callbacks) {
+  std::vector<base::Callback<bool(void)> > check_callbacks_converted(
+      check_callbacks.size());
+  for (size_t i = 0; i < check_callbacks.size(); i++) {
+    check_callbacks_converted[i] = check_callbacks[i]->AsCallback();
+  }
+
+  return RunTasksUntil(check_callbacks_converted);
+}
+
+bool OrderedSimpleTaskRunner::RunTasksUntil(
+    base::Callback<bool(void)> check_callback) {
+  std::vector<base::Callback<bool(void)> > check_callbacks = {check_callback};
+  return RunTasksUntil(check_callbacks);
+}
+
+bool OrderedSimpleTaskRunner::RunTasksUntil(
+    const std::vector<base::Callback<bool(void)> > check_callbacks) {
+  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)> > usable_check_callbacks(
+      check_callbacks);
+
+  // Provide a timeout so this doesn't loop forever.
+  RunNTasks timeout(max_tasks_);
+  usable_check_callbacks.push_back(timeout.AsCallback());
+
+  // If to advance now or not
+  RunOnlyBefore only_before(this, now_src_, now_src_->Now());
+  RunAdvanceNow advance_now(this, now_src_);
+  if (!advance_now_) {
+    usable_check_callbacks.push_back(only_before.AsCallback());
+  } else {
+    usable_check_callbacks.push_back(advance_now.AsCallback());
+  }
+
+  if (inside_run_tasks_until_)
+    return true;
+  inside_run_tasks_until_ = true;
+
+  while (pending_tasks_.size() > 0) {
+    std::set<TestOrderablePendingTask>::iterator task_to_run =
+        pending_tasks_.begin();
+
+    // Check if we should continue to run the tasks
+    for (std::vector<base::Callback<bool(void)> >::iterator it =
+             usable_check_callbacks.begin();
+         it != usable_check_callbacks.end();
+         it++) {
+      if (!it->Run()) {
+        goto run_tasks_until_exit;
+      }
+    }
+
+    {
+      TRACE_EVENT1("cc",
+                   "OrderedSimpleTaskRunner::RunPendingTasks running",
+                   "task",
+                   task_to_run->AsValue());
+      task_to_run->task.Run();
+    }
+
+    pending_tasks_.erase(task_to_run);
+  }
+
+run_tasks_until_exit:
+  inside_run_tasks_until_ = false;
+
+  return pending_tasks_.size() > 0;
+}
+
+base::TimeDelta OrderedSimpleTaskRunner::DelayToNextPendingTask() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  if (pending_tasks_.size() <= 0)
+    return base::TimeDelta::FromInternalValue(
+        std::numeric_limits<int64_t>::max());
+
+  base::TimeDelta delay =
+      pending_tasks_.begin()->GetTimeToRun() - now_src_->Now();
+  if (delay > base::TimeDelta())
+    return delay;
+  return base::TimeDelta();
+}
+
+// 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::RunCheck::AsCallback()
+    const {
+  return base::Bind(
+      &RunCheck::Check,
+      base::Unretained(const_cast<OrderedSimpleTaskRunner::RunCheck*>(this)));
+}
+
+OrderedSimpleTaskRunner::RunCheckNeedsNextTask::RunCheckNeedsNextTask(
+    OrderedSimpleTaskRunner* task_runner)
+    : task_runner_(task_runner) {
+}
+bool OrderedSimpleTaskRunner::RunCheckNeedsNextTask::Check() {
+  DCHECK(task_runner_);
+  DCHECK_GT(task_runner_->pending_tasks_.size(), 0U);
+  return CheckWithTask(*task_runner_->pending_tasks_.begin());
+}
+
+OrderedSimpleTaskRunner::RunNTasks::RunNTasks(size_t number)
+    : tasks_run_(0), tasks_to_run_(number) {
+}
+OrderedSimpleTaskRunner::RunNTasks::~RunNTasks() {
+}
+bool OrderedSimpleTaskRunner::RunNTasks::Check() {
+  return tasks_run_++ < tasks_to_run_;
+}
+
+OrderedSimpleTaskRunner::RunCheckNeedsNextTaskTime::RunCheckNeedsNextTaskTime(
+    OrderedSimpleTaskRunner* task_runner,
+    scoped_refptr<TestNowSource> now_src)
+    : RunCheckNeedsNextTask(task_runner), now_src_(now_src) {
+}
+OrderedSimpleTaskRunner::RunCheckNeedsNextTaskTime::
+    ~RunCheckNeedsNextTaskTime() {
+}
+bool OrderedSimpleTaskRunner::RunCheckNeedsNextTaskTime::CheckWithTask(
+    const TestOrderablePendingTask& next_task) {
+  return CheckWithTaskTime(now_src_->Now(), next_task.GetTimeToRun());
+}
+
+OrderedSimpleTaskRunner::RunOnlyBefore::RunOnlyBefore(
+    OrderedSimpleTaskRunner* task_runner,
+    scoped_refptr<TestNowSource> now_src,
+    base::TimeTicks stop_at)
+    : RunCheckNeedsNextTaskTime(task_runner, now_src), stop_at_(stop_at) {
+}
+OrderedSimpleTaskRunner::RunOnlyBefore::~RunOnlyBefore() {
+}
+bool OrderedSimpleTaskRunner::RunOnlyBefore::CheckWithTaskTime(
+    base::TimeTicks now,
+    base::TimeTicks next_task) {
+  return next_task <= stop_at_;
+}
+
+OrderedSimpleTaskRunner::RunOnlyExisting::RunOnlyExisting(
+    OrderedSimpleTaskRunner* task_runner)
+    : RunCheckNeedsNextTask(task_runner),
+      pending_tasks_(task_runner->pending_tasks_) {
+}
+OrderedSimpleTaskRunner::RunOnlyExisting::~RunOnlyExisting() {
+}
+bool OrderedSimpleTaskRunner::RunOnlyExisting::CheckWithTask(
+    const TestOrderablePendingTask& next_task) {
+  return pending_tasks_.find(next_task) != pending_tasks_.end();
+}
+
+OrderedSimpleTaskRunner::RunAdvanceNow::RunAdvanceNow(
+    OrderedSimpleTaskRunner* task_runner,
+    scoped_refptr<TestNowSource> now_src)
+    : RunCheckNeedsNextTaskTime(task_runner, now_src) {
+}
+OrderedSimpleTaskRunner::RunAdvanceNow::~RunAdvanceNow() {
+}
+bool OrderedSimpleTaskRunner::RunAdvanceNow::CheckWithTaskTime(
+    base::TimeTicks now,
+    base::TimeTicks next_task) {
+  if (now < next_task) {
+    now_src_->SetNow(next_task);
   }
+  return true;
 }
 
 }  // namespace cc