Implementation of SequencedTaskRunner based on SequencedWorkerPool.

base/test/sequenced_task_runner_test_template.h

+// Copyright (c) 2012 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.
+
+// This class defines tests that implementations of SequencedTaskRunner should
+// pass in order to be conformant.  Here's how you use it to test your

[akalin, 2012/03/20 22:16:08]

Remove 2nd sentence, merge paragraph below with this one

[Francois, 2012/03/26 09:33:21]

Done.

+// implementation.
+//
+// See task_runner_test_template.h for a description of how to use the
+// constructs in this file; these work the same.
+
+#ifndef BASE_SEQUENCED_TASK_RUNNER_TEST_TEMPLATE_H_
+#define BASE_SEQUENCED_TASK_RUNNER_TEST_TEMPLATE_H_
+#pragma once
+
+#include <cstddef>
+

[akalin, 2012/03/20 22:16:08]

remove extra newline

[Francois, 2012/03/26 09:33:21]

Done.

+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/bind.h"
+#include "base/memory/ref_counted.h"
+#include "base/sequenced_task_runner.h"
+#include "base/synchronization/lock.h"
+#include "base/tracked_objects.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+
+namespace internal {
+
+// Utility class used in the tests below.
+class SequencedTaskTracker : public RefCountedThreadSafe<SequencedTaskTracker> {
+ public:
+  struct TaskPhase {

[akalin, 2012/03/20 22:16:08]

I think TaskEvent is a better name

[Francois, 2012/03/26 09:33:21]

Done.

+    enum Type { POST, START, END };
+    TaskPhase(int i, Type type) : i_(i), type_(type) {}
+    bool operator==(const TaskPhase& phase) {

[akalin, 2012/03/20 22:16:08]

prefer

bool Equals(const TaskPhase& phase) const {
}

[Francois, 2012/03/26 09:33:21]

Will do next time, but it isn't required anymore, so I've removed it.

+      return (i_ == phase.i_ && type_ == phase.type_);
+    }
+    int i_;

[akalin, 2012/03/20 22:16:08]

typically public member variables don't have an appended _

[Francois, 2012/03/26 09:33:21]

Done.

+    Type type_;
+  };
+
+  SequencedTaskTracker();
+
+  int GetNextPostOrdinal();

[akalin, 2012/03/20 22:16:08]

shouldn't need this function (see comments below)

[Francois, 2012/03/26 09:33:21]

Done.

+
+  void TaskPosted(int i);

[akalin, 2012/03/20 22:16:08]

these functions shouldn't be exposed.  Instead, you should expose something
like:

void PostWrappedTask(const scoped_refptr<TaskRunner>&, const Closure& task, int
i);

which should call TaskPosted and post a wrapper task that calls
TaskStarted/TaskEnded, etc. (also, it should support a null task)

Then you can just define:

void DoNothing() {
}

void SleepForOneSecond() {
  ...Sleep(...);
}

etc.

and post those

[Francois, 2012/03/26 09:33:21]

Done. And DoNothing isn't required if null tasks are supported, right?

+  void TaskStarted(int i);
+  void TaskEnded(int i);
+
+  const std::vector<TaskPhase>& GetTaskPhases() const;
+
+  void FastTask(int i);
+  void SlowTask(int i);
+
+  // Task which posts a fast, non-nestable task.
+  void PostFastNonNestableFromSlowNonNestable(
+      scoped_refptr<SequencedTaskRunner> task_runner,
+      const int base_status_i,
+      const int child_count);
+
+ private:
+  friend class RefCountedThreadSafe<SequencedTaskTracker>;
+
+  ~SequencedTaskTracker();
+
+ public:

[akalin, 2012/03/20 22:16:08]

these shouldn't be public

[Francois, 2012/03/26 09:33:21]

Done.

+  std::vector<TaskPhase> phases_;
+  mutable Lock phase_lock_;

[akalin, 2012/03/20 22:16:08]

add a comment saying that phase_lock_ protects phases_ (even though it's
obvious)

[Francois, 2012/03/26 09:33:21]

Done.

+
+ private:
+  int next_post_i_;
+
+  DISALLOW_COPY_AND_ASSIGN(SequencedTaskTracker);
+};
+
+}  // namespace internal
+
+template <typename TaskRunnerTestDelegate>
+class SequencedTaskRunnerTest : public testing::Test {
+ protected:
+  SequencedTaskRunnerTest()
+  : task_tracker_(new internal::SequencedTaskTracker()) {}
+
+  // Checks that each phase type occurs in the same order as the tasks were
+  // posted, and that the phases for each given task occur in the expected
+  // order (POST, START, END).
+  ::testing::AssertionResult TaskPhasesInOrder(int task_count);
+
+  const scoped_refptr<internal::SequencedTaskTracker> task_tracker_;
+  TaskRunnerTestDelegate delegate_;
+};
+
+TYPED_TEST_CASE_P(SequencedTaskRunnerTest);
+
+// This test posts N non-nestable tasks in sequence, and expects them to run
+// in FIFO order, with no part of any two tasks' execution
+// overlapping. I.e. that each task starts only after the previously-posted
+// one has finished.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialNonNestable) {
+  const int task_count = 1000;
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task;
+    if (i == 0) {

[akalin, 2012/03/20 22:16:08]

with the comments above, you can move the i=0 case out of the loop, e.g.

this->task_tracker_->PostNonNestableWrappedTask(FROM_HERE,
Bind(&SleepForOneSecond), 0);
for (int i = 0; i < task_count; ++i) {
  this->task_tracker_->PostNonNestableWrappedTask(FROM_HERE, Closure(), i);
}

[Francois, 2012/03/26 09:33:21]

Done.

+      task = Bind(&internal::SequencedTaskTracker::SlowTask,
+                  this->task_tracker_, i);
+    } else {
+      task = Bind(&internal::SequencedTaskTracker::FastTask,
+                  this->task_tracker_, i);
+    }
+    this->task_tracker_->TaskPosted(i);
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_TRUE(this->TaskPhasesInOrder(task_count));
+}
+
+// This test posts N nestable tasks in sequence. It has the same expectations
+// as SequentialNonNestable because even though the tasks are nestable, they
+// will not be run nestedly in this case.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialNestable) {
+  const int task_count = 1000;
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task;
+    if (i == 0) {
+      task = Bind(&internal::SequencedTaskTracker::SlowTask,
+                  this->task_tracker_, i);
+    } else {
+      task = Bind(&internal::SequencedTaskTracker::FastTask,
+                  this->task_tracker_, i);
+    }
+    this->task_tracker_->TaskPosted(i);
+    task_runner->PostTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_TRUE(this->TaskPhasesInOrder(task_count));
+}
+
+// This test posts non-nestable tasks in order of increasing delay, and checks
+// that that the tasks are run in FIFO order and that there is no execution
+// overlap whatsoever between any two tasks.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialDelayedNonNestable) {
+  if (!this->delegate_.TaskRunnerHandlesNonZeroDelays()) {
+    DLOG(INFO) << "This SequencedTaskRunner doesn't handle "
+        "non-zero delays; skipping";
+    return;
+  }
+
+  const int task_count = 20;
+  const int delay_increment_ms = 50;
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task = Bind(&internal::SequencedTaskTracker::FastTask,
+                        this->task_tracker_, i);
+    this->task_tracker_->TaskPosted(i);
+    task_runner->PostNonNestableDelayedTask(
+        FROM_HERE,
+        task,
+        TimeDelta::FromMilliseconds(delay_increment_ms * i));
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_TRUE(this->TaskPhasesInOrder(task_count));
+}
+
+// This test posts a fast, non-nestable task from within each of a number of
+// slow, non-nestable tasks and checks that they all run in the sequence they
+// were posted in and that there is no execution overlap whatsoever.
+TYPED_TEST_P(SequencedTaskRunnerTest, NonNestablePostFromNonNestableTask) {
+  const int parent_count = 10;
+  const int children_per_parent = 10;
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  const int end = parent_count;
+  for (int i = 0; i < end; ++i) {
+    AutoLock phase_lock(this->task_tracker_->phase_lock_);
+    const int post_i = this->task_tracker_->GetNextPostOrdinal();
+    Closure task = Bind(
+        &internal::SequencedTaskTracker::PostFastNonNestableFromSlowNonNestable,
+        this->task_tracker_,
+        task_runner,
+        post_i,
+        children_per_parent);
+    this->task_tracker_->phases_.push_back(
+        internal::SequencedTaskTracker::TaskPhase(
+            post_i, internal::SequencedTaskTracker::TaskPhase::POST));
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_TRUE(this->TaskPhasesInOrder(parent_count *
+                                      (children_per_parent + 1)));
+}
+
+// TODO(francoisk777@gmail.com) Add a test, similiar to the above, which which
+// runs some tasked nestedly (which should be implemented in the test
+// delegate). Also add, to the the test delegate, a predicate which checks
+// whether the implementation supports nested tasks.
+//
+
+REGISTER_TYPED_TEST_CASE_P(SequencedTaskRunnerTest,
+                           SequentialNonNestable,
+                           SequentialNestable,
+                           SequentialDelayedNonNestable,
+                           NonNestablePostFromNonNestableTask
+                           );
+
+template <typename TaskRunnerTestDelegate>

[akalin, 2012/03/20 22:16:08]

the code below should probably go before the unit tests themselves

[Francois, 2012/03/26 09:33:21]

Done.

+::testing::AssertionResult
+SequencedTaskRunnerTest<TaskRunnerTestDelegate>::TaskPhasesInOrder(

[akalin, 2012/03/20 22:16:08]

this function does a bit too much -- it's complicated.  I think it would be
better to split out the tests.  Here's what I suggest:

- Define the function:

std::vector<int> GetEventTypeOrder(const std::vector<TaskEvent>& events,
TaskEvent::Type type);

which basically filters by type and returns the i's.

Then you can check that GetEventTypeOrder(events, POST) ==
GetEventTypeOrder(events, START) and ...START) == ...END) (which holds if there
are no nested tasks, but all of the current tests assume that anyway, and we can
handle nestable tasks later).

Then you can similarly define a function that checks that for all i, POST comes
before START comes before END, and then another one that makes sure the only
thing between START and END (for a given i) are POST events (for j != i, no
nestable tasks).  Then I think you can wrap all those checks in some function
CheckNonNestableInvariants(...) and call that from the tests.

These functions should be free functions (i.e., not part of a class).

[Francois, 2012/03/26 09:33:21]

Done.

+    int task_count) {
+  typedef internal::SequencedTaskTracker::TaskPhase TaskPhase;
+
+  std::vector<TaskPhase> phases = task_tracker_->GetTaskPhases();
+
+  if (phases.size() != task_count * 3U) {
+    return ::testing::AssertionFailure()
+        << "Expecting " << (task_count * 3) << " task phases, but found only"
+        << phases.size();
+  }
+
+  // Stores the order of phases for each task.
+  std::vector<std::vector<TaskPhase::Type> > phase_orders(task_count);
+
+  int expected_post_task = 0;
+  int expected_start_task = 0;
+  int expected_end_task = 0;
+
+  std::vector<TaskPhase>::const_iterator phase;
+  for (phase = phases.begin(); phase != phases.end(); ++phase) {
+    switch (phase->type_) {
+      case TaskPhase::POST:
+        if (phase->i_ != expected_post_task) {
+          return ::testing::AssertionFailure()
+              << "POST phase for task " << phase->i_
+              << " is out of order; expecting one for task "
+              << expected_post_task << ", instead";
+        }
+        phase_orders[expected_post_task].push_back(TaskPhase::POST);
+        ++expected_post_task;
+        break;
+      case TaskPhase::START:
+        if (phase->i_ != expected_start_task) {
+          return ::testing::AssertionFailure()
+              << "START phase for task " << phase->i_
+              << " is out of order; expecting one for task "
+              << expected_start_task << ", instead";
+        }
+        phase_orders[expected_start_task].push_back(TaskPhase::START);
+        ++expected_start_task;
+        break;
+      case TaskPhase::END:
+        if (phase->i_ != expected_end_task) {
+          return ::testing::AssertionFailure()
+              << "END phase for task " << phase->i_
+              << " is out of order; expecting one for task "
+              << expected_end_task << ", instead";
+        }
+        if (phase_orders[expected_end_task].size() != 2) {
+          return ::testing::AssertionFailure()
+              << "POST and/or START phase(s) for task " << phase->i_
+              << " did not occur before its END phase";
+        }
+        if (phase_orders[expected_end_task][1] != TaskPhase::START) {
+          return ::testing::AssertionFailure()
+              << "START phase for task " << phase->i_
+              << " did not occur before its END phase";
+        }
+        if (phase_orders[expected_end_task][0] != TaskPhase::POST) {
+          return ::testing::AssertionFailure()
+              << "POST phase for task " << phase->i_
+              << " did not occur before its START and END phases";
+        }
+        ++expected_end_task;
+        break;
+    }
+  }
+  return ::testing::AssertionSuccess();
+}
+
+}  // namespace base
+
+#endif  // BASE_TASK_RUNNER_TEST_TEMPLATE_H_