Fixing and enhancing OrderedSimpleTaskRunner to allow 100% deterministic tests.

cc/test/ordered_simple_task_runner.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "cc/test/ordered_simple_task_runner.h"
 
-#include <algorithm>
-#include <deque>
-
-#include "base/logging.h"
-
-namespace {
-
-bool TestPendingTaskComparator(const base::TestPendingTask& lhs,
-                               const base::TestPendingTask& rhs) {
-  return lhs.ShouldRunBefore(rhs);
-}
-
-}
+#include <limits>
+#include <set>
+#include <sstream>
+#include <string>
+#include <vector>
+
+#include "base/auto_reset.h"
+#include "base/debug/trace_event.h"
+#include "base/debug/trace_event_argument.h"
+#include "base/strings/string_number_conversions.h"
+
+#define TRACE_TASK(function, task) \
+  TRACE_EVENT_INSTANT1(            \
+      "cc", function, TRACE_EVENT_SCOPE_THREAD, "task", task.AsValue());
+
+#define TRACE_TASK_RUN(function, tag, task)
 
 namespace cc {
 
-OrderedSimpleTaskRunner::OrderedSimpleTaskRunner() {}
+// 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++) {
+}
+
+size_t TestOrderablePendingTask::task_id_counter = 0;
+
+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_(kAbsoluteMaxTasks),
+      inside_run_tasks_until_(false) {
+}
 
 OrderedSimpleTaskRunner::~OrderedSimpleTaskRunner() {}
 
-void OrderedSimpleTaskRunner::RunPendingTasks() {
-  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();
-  }
+// 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) {
+    return TestNowSource::kAbsoluteMaxNow;
+  }
+
+  return pending_tasks_.begin()->GetTimeToRun();
+}
+
+base::TimeDelta OrderedSimpleTaskRunner::DelayToNextTaskTime() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  if (pending_tasks_.size() <= 0) {
+    return TestNowSource::kAbsoluteMaxNow - base::TimeTicks();
+  }
+
+  base::TimeDelta delay = NextTaskTime() - now_src_->Now();
+  if (delay > base::TimeDelta())
+    return delay;
+  return base::TimeDelta();
+}
+
+const size_t OrderedSimpleTaskRunner::kAbsoluteMaxTasks =
+    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());
+
+  // 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());
+  }
+
+  if (inside_run_tasks_until_)

[brianderson, 2014/09/05 02:48:03]

Should this early out and the AutoReset move up?

[mithro-old, 2014/09/08 12:52:19]

Done.

+    return true;
+
+  base::AutoReset<bool> reset_inside_run_tasks_until_(&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()) {
+        return pending_tasks_.size() > 0;

[brianderson, 2014/09/05 02:48:03]

Can you just return true here?

[mithro-old, 2014/09/08 12:52:19]

A condition could possibly modify the queue size and return false. Maybe  a
"FlushAndExit()" type condition?

[brianderson, 2014/09/08 19:24:08]

A comment explaining that a condition might modify the queue size is good
enough.

Is it possible that a callback empties the pending_tasks_? If so, would we need
an additional check before running the first task, which might not exist?

[mithro-old, 2014/09/09 02:39:44]

Done.

+      }
+    }
+
+    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);
+  }
+
+  return false;
+}
+
+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(
+    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(
+    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) {
+  return NextTaskTime() <= stop_at;
+}
+
+base::Callback<bool(void)> OrderedSimpleTaskRunner::AdvanceNow() {

[brianderson, 2014/09/05 02:48:03]

I would want to explictly disallow side-effects like this if we could, but I
can't think of a way to enforce it either at compile time or run time - just
review time.

It's convenient that you can implement AdvanceNow like this, but it seems like
an abuse of the condition argument, which I wouldn't expect to have any side
effects when run. If we are going to allow side-effects, I would suggest
renaming the condition argument to something different.

[mithro-old, 2014/09/08 12:52:19]

We also need side-effects for the "WhileTaskRunCountBelow" and similar
conditions.
Very open to suggestions...

[brianderson, 2014/09/08 19:24:08]

Argh, naming is hard. I can't think of any better name that isn't suuper long.

You already make it clear in the RunTasksWhile comments that there's
short-circuit evaluation; can you also put in a warning about side-effects?

[mithro-old, 2014/09/09 02:39:44]

Done.

+  return base::Bind(&OrderedSimpleTaskRunner::AdvanceNowCallback,
+                    base::Unretained(this));
+}
+
+bool OrderedSimpleTaskRunner::AdvanceNowCallback() {
+  base::TimeTicks next_task_time = NextTaskTime();
+  if (now_src_->Now() == TestNowSource::kAbsoluteMaxNow ||
+      next_task_time == TestNowSource::kAbsoluteMaxNow)
+    return false;

[brianderson, 2014/09/05 02:48:03]

This "return false" seems redundant with the existing pending_tasks_.size() > 0
check in RunTasks. Is there any reason to keep it?

[mithro-old, 2014/09/08 12:52:19]

Removed.

+
+  if (now_src_->Now() < next_task_time) {
+    now_src_->SetNow(next_task_time);
+  }
+  return true;
 }
 
 }  // namespace cc