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
+// 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>
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/bind.h"
+#include "base/memory/ref_counted.h"
+#include "base/synchronization/lock.h"
+#include "base/sequenced_task_runner.h"
+#include "base/tracked_objects.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+
+// Utility class used in the tests below.
+class SeqTaskTracker : public RefCountedThreadSafe<SeqTaskTracker> {

[akalin, 2012/03/13 07:27:11]

SeqTaskTracker -> SequencedTaskTracker (abbreviations are discouraged by style
guide)

[akalin, 2012/03/13 07:27:11]

put this class in the base::internal namespace

(you may want to take another look at task_runner_test_template.{h,cc} -- I
cleaned it up a bit from an earlier version.

[Francois, 2012/03/14 15:43:31]

Done.

[Francois, 2012/03/14 15:43:31]

Done.

+ public:
+  // Keeps track of a task's run status. I.e. whether it has run to completion
+  // and whether its predecessor had run to completion by the time it started
+  // running.
+  class TaskStatus {

[akalin, 2012/03/13 07:27:11]

Hmm I think this class may be overkill.  I was thinking that
SequencedTaskTracker would have a maps from int to vectors of ints protected by
a lock, and it would provide closures that, for given integers i, j appends j to
the vector for i under lock.  Then the tests would simply keep track of the
expected order of the integers (given the STR guarantees) in each vector and
compare the actual order after all the tasks are run.

Basically you have a bunch of tasks sequences and you want to make sure that all
the tasks in each sequence are run in the right order. (but you don't care about
interleavings between the task sequences)

Comparing with TaskTracker, something like:

class SequencedTaskTracker {
  ..
  // Returns a closure that runs the given task and appends |j| to the task
sequence for |i|. |task| may be null.
  // It is guaranteed that only one task wrapped by a given tracker will be run
at a time.
  Closure WrapTask(const Closure& task, int i, int j);

  std::map<int, std::vector<int> > GetTaskSequences() const;

 private:
  mutable Lock task_sequences_lock_;
  std::map<int, std::vector<int> > task_sequences_lock_;
}

I think you should be able to do everything you want with the tests below with
this.  What do you think?

[akalin, 2012/03/13 20:00:10]

Actually a few corrections.  WrapTask should *not* guarantee mutual exclusion,
as that's the STR's job!  It should guarantee only atomic updates to the map of
task sequences.

Also, since SequencedTaskTracker doesn't guarantee FIFOness, we need to track
the order in which tasks start and end rather than when they run.  So instead of
a map of int vectors, probably want to define a struct with an int and enum {
BEGIN, END } and have a map of vectors of those.

[Francois, 2012/03/14 15:43:31]

I like your model because it mirrors the task hierarchy well, but I don't think
it's going to work for all my tests. E.g. I have one
(NonNestablePostFromNonNestableTask) which posts non-nestable tasks from
non-nestable ones. For this one it's important to verify that all tasks, whether
root or sub, were run in the order they were posted and without execution
overlap. The order in which they're posted is unknown because the posts are done
from different threads. With your model I wouldn't be able to verify that if,
for example, the posting order was {T0, ST0_0, T1, ST0_1}, that T1 started only
after ST0_0 had finished, or that ST0_1 started after T1 had finished.

+   public:
+    TaskStatus();
+    TaskStatus(const TaskStatus& ts);
+    TaskStatus& operator=(const TaskStatus& ts);
+    bool operator==(const TaskStatus& ts) const;
+
+    // Claims ownership of this task status for a task.
+    bool Claim();
+    // Whether the owning task has run to completion yet.
+    bool Completed() const;
+    // Whether the previous task (the one which owns the preceding position in
+    // the task status vector) had finished by the time this one started.
+    bool PrevCompletedBefore() const;
+    // Declares that the owning task has run to completion.
+    void SetCompleted();
+    // Declares that the previous task had run to completion by the time the
+    // owning task started.
+    void SetPrevCompletedBefore(const bool b);
+
+   private:
+    mutable Lock lock_;
+    // Whether this status slot has been claimed by a task yet.
+    bool claimed_;
+    bool completed_;
+    // Whether the owning task has set the "completed" flag.
+    bool completed_set_;
+    bool prev_completed_;
+    // Whether the owning task has set the "previous completed" flag.
+    bool prev_completed_set_;
+  };
+
+  typedef std::vector<TaskStatus> TaskStatuses;
+
+  SeqTaskTracker();
+
+  // Pre-allocates memory for the non-nestable task statuses.
+  void SetNonNestableTaskCount(const std::size_t task_count);

[akalin, 2012/03/13 07:27:11]

remove const (doesn't make sense for value parameters)

[Francois, 2012/03/14 15:43:31]

Done. But it does make sense to me :) If something isn't supposed to change (the
function's local copy of the argument, in this case), mark it const. I don't
think it's much different from declaring a regular function-local variable
const.

+
+  // Pre-allocates memory for the nestable task statuses.
+  void SetNestableTaskCount(const std::size_t task_count);
+
+  const TaskStatuses& GetNonNestableTaskStatuses() const;
+  const TaskStatuses& GetNestableTaskStatuses() const;
+
+  // A fast, non-nestable task.
+  void FastNonNestableTask(int base_status_i);
+
+  // A fast, nestable task.
+  void FastNestableTask(int parent_task_status_slot);
+
+  // A slow, non-nestable task (sleeps for 1 second).
+  void SlowNonNestableTask(int base_status_i);
+
+  // Posts a fast, non-nestable task from a slow, non-nestable one.
+  void PostFastNonNestableFromSlowNonNestable(
+      scoped_refptr<SequencedTaskRunner> tr,

[akalin, 2012/03/13 07:27:11]

tr -> task_runner (abbreviations are discouraged)

[Francois, 2012/03/14 15:43:31]

Done.

+      const int base_status_i,
+      const int child_count);
+
+  // Posts a fast, nestable task from a slow, non-nestable one.
+  void PostFastNestableFromSlowNonNestable(
+      scoped_refptr<SequencedTaskRunner> tr,
+      const int base_status_i,
+      const int child_count);
+
+ private:
+  friend class RefCountedThreadSafe<SeqTaskTracker>;
+
+  ~SeqTaskTracker();
+
+  // Finds the lowest-numbered non-nestable task status object, beginning at
+  // position |search_from|, which has not yet been claimed.
+  int ClaimNonNestableTaskStatus(const int search_from = 0);

[akalin, 2012/03/13 07:27:11]

default arguments are prohibited by style guide

[Francois, 2012/03/14 15:43:31]

Done.

+
+  // Finds the lowest-numbered nestable task status object, beginning at
+  // position |search_from|, which has not yet been claimed.
+  int ClaimNestableTaskStatus(const int search_from = 0);

[akalin, 2012/03/13 07:27:11]

here too

[Francois, 2012/03/14 15:43:31]

Done.

+
+  TaskStatuses nestable_statuses_;
+  TaskStatuses non_nestable_statuses_;
+
+  DISALLOW_COPY_AND_ASSIGN(SeqTaskTracker);
+};
+
+std::ostream& operator<<(std::ostream& os,

[akalin, 2012/03/13 07:27:11]

a ToString() member function is preferred to overloading operator<<

[Francois, 2012/03/14 15:43:31]

OK, but I added this to customise the output of EXPECT_EQ when it evaluates to
false. Without this it prints byte values.

+                         const SeqTaskTracker::TaskStatus& ts);
+
+template <typename TaskRunnerTestDelegate>
+class SequencedTaskRunnerTest : public testing::Test {
+ protected:
+  SequencedTaskRunnerTest() : task_tracker_(new SeqTaskTracker()) {
+    good_task_status_prototype_.SetPrevCompletedBefore(true);
+    good_task_status_prototype_.SetCompleted();
+  }
+
+  const scoped_refptr<SeqTaskTracker> task_tracker_;
+  TaskRunnerTestDelegate delegate_;
+  SeqTaskTracker::TaskStatus good_task_status_prototype_;
+};
+
+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.
+//
+// It checks that task0 was done by the time task1 started, and task2 only
+// started after task1 had executed to completion, etc.
+//
+// The first task it starts is a slow one which runs for a second, giving the
+// subsequent ones plenty of time to run if the implementation fails to
+// enforce the non-nestable property.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialNonNestable) {
+  const int task_count = 1000;
+
+  this->task_tracker_->SetNonNestableTaskCount(task_count);
+  SeqTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  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(&SeqTaskTracker::SlowNonNestableTask,
+                  this->task_tracker_, i);
+    } else {
+      task = Bind(&SeqTaskTracker::FastNonNestableTask,
+                  this->task_tracker_, i);
+    }
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+}
+
+// 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.
+//
+// If there are 10 tasks, task1 is posted first with a delay of zero, followed
+// by task2 with a delay of, say, 1, and so forth, until task10 is posted with
+// a delay of 10. It then checks that task2 started after task1, and only
+// after task1 had finished, and so forth.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialDelayedNonNestable) {
+  const int task_count = 20;

[akalin, 2012/03/13 07:27:11]

if you change the logs in PostDelayed...Task to use NOTREACHED(), you'll have to
use this->delegate_.SupportsDelayedTasks() (or whatever it's called here)

[Francois, 2012/03/14 15:43:31]

Done.

+  const int delay_increment_ms = 50;
+
+  this->task_tracker_->SetNonNestableTaskCount(task_count);
+  SeqTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task = Bind(&SeqTaskTracker::FastNonNestableTask,
+                        this->task_tracker_, i);
+    task_runner->PostNonNestableDelayedTask(
+        FROM_HERE,
+        task,
+        TimeDelta::FromMilliseconds(delay_increment_ms * i));
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+}
+
+// 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 = 1000;
+  const int children_per_parent = 2;
+  const int task_count = parent_count * (children_per_parent + 1);
+
+  this->task_tracker_->SetNonNestableTaskCount(task_count);
+  SeqTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  const int end = parent_count;
+  for (int i = 0; i < end; ++i) {
+    Closure task = Bind(
+        &SeqTaskTracker::PostFastNonNestableFromSlowNonNestable,
+        this->task_tracker_,
+        task_runner,
+        i,
+        children_per_parent);
+    DLOG(INFO) << "XXX Posted parent task " << i;
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+}
+
+// This test posts a number of fast, nestable tasks from within each of a
+// number of slow, non-nestable tasks and checks that the non-nestable ones
+// all run in the sequence they were posted in and that there is no execution
+// overlap whatsoever.
+TYPED_TEST_P(SequencedTaskRunnerTest,
+             NestablePostFromNonNestableTask) {
+  const int parent_count = 500;
+  const int children_per_parent = 2;
+
+  this->task_tracker_->SetNonNestableTaskCount(parent_count);
+  SeqTaskTracker::TaskStatuses expected_non_nestable_statuses(
+      parent_count,
+      this->good_task_status_prototype_);
+  this->task_tracker_->SetNestableTaskCount(children_per_parent * parent_count);
+  SeqTaskTracker::TaskStatuses expected_nestable_statuses(
+      children_per_parent * parent_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  const int end = parent_count;
+  for (int i = 0; i < end; ++i) {
+    Closure task = Bind(
+        &SeqTaskTracker::PostFastNestableFromSlowNonNestable,
+        this->task_tracker_,
+        task_runner,
+        i,
+        children_per_parent);
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_non_nestable_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+  EXPECT_EQ(expected_nestable_statuses,
+            this->task_tracker_->GetNestableTaskStatuses());
+}
+

[akalin, 2012/03/13 07:27:11]

Add a TODO for a test similar to the above, but having some of the tasks call a
method on the delegate that runs tasks nestedly.  You'll also need to add some
sort of query method for whether the implementation has such a method.  The test
won't be useful for STRImpl, but would be for e.g. MessageLoopProxy.

[Francois, 2012/03/14 15:43:31]

Done.

+REGISTER_TYPED_TEST_CASE_P(SequencedTaskRunnerTest,
+                           SequentialNonNestable,
+                           SequentialDelayedNonNestable,
+                           NonNestablePostFromNonNestableTask,
+                           NestablePostFromNonNestableTask);
+
+}  // namespace base
+
+#endif  //#define BASE_TASK_RUNNER_TEST_TEMPLATE_H_

[akalin, 2012/03/13 07:27:11]

no '#define' in comment

[Francois, 2012/03/14 15:43:31]

Done.