TaskScheduler [3/9] Task and Sequence

This change is a subset of https://codereview.chromium.org/1698183005/

A Task is a unit of work in the task scheduler. It has a closure,
a sequenced time, TaskTraits and other metadata inherited from
base::PendingTask.

A Sequence holds Tasks that must run in order. It is ref-counted
and has thread-safe Push, Pop and Peek operations. Priority queues,
worker threads and task runners will have references on Sequences.

BUG=553459

Review URL: https://codereview.chromium.org/1705253002

Cr-Commit-Position: refs/heads/master@{#381638}

13 files changed, 638 insertions, 18 deletions

diff --git a/base/BUILD.gn b/base/BUILD.gn
index 30380c8..e1b1d9d 100644
--- a/base/BUILD.gn
+++ b/base/BUILD.gn
@@ -767,6 +767,12 @@ component("base") {
     "task_scheduler/scheduler_lock.h",
     "task_scheduler/scheduler_lock_impl.cc",
     "task_scheduler/scheduler_lock_impl.h",
+    "task_scheduler/sequence.cc",
+    "task_scheduler/sequence.h",
+    "task_scheduler/sequence_sort_key.cc",
+    "task_scheduler/sequence_sort_key.h",
+    "task_scheduler/task.cc",
+    "task_scheduler/task.h",
     "task_scheduler/task_traits.cc",
     "task_scheduler/task_traits.h",
     "template_util.h",
@@ -1807,6 +1813,8 @@ test("base_unittests") {
     "task/cancelable_task_tracker_unittest.cc",
     "task_runner_util_unittest.cc",
     "task_scheduler/scheduler_lock_unittest.cc",
+    "task_scheduler/sequence_sort_key_unittest.cc",
+    "task_scheduler/sequence_unittest.cc",
     "template_util_unittest.cc",
     "test/histogram_tester_unittest.cc",
     "test/icu_test_util.cc",
diff --git a/base/base.gyp b/base/base.gyp
index d4e5be3..88e27f1 100644
--- a/base/base.gyp
+++ b/base/base.gyp
@@ -549,6 +549,8 @@
         'task/cancelable_task_tracker_unittest.cc',
         'task_runner_util_unittest.cc',
         'task_scheduler/scheduler_lock_unittest.cc',
+        'task_scheduler/sequence_sort_key_unittest.cc',
+        'task_scheduler/sequence_unittest.cc',
         'template_util_unittest.cc',
         'test/histogram_tester_unittest.cc',
         'test/test_pending_task_unittest.cc',
diff --git a/base/base.gypi b/base/base.gypi
index 4bf8ae6..7ef9266 100644
--- a/base/base.gypi
+++ b/base/base.gypi
@@ -637,6 +637,12 @@
           'task_scheduler/scheduler_lock.h',
           'task_scheduler/scheduler_lock_impl.cc',
           'task_scheduler/scheduler_lock_impl.h',
+          'task_scheduler/sequence.cc',
+          'task_scheduler/sequence.h',
+          'task_scheduler/sequence_sort_key.cc',
+          'task_scheduler/sequence_sort_key.h',
+          'task_scheduler/task.cc',
+          'task_scheduler/task.h',
           'task_scheduler/task_traits.cc',
           'task_scheduler/task_traits.h',
           'template_util.h',
diff --git a/base/task_scheduler/sequence.cc b/base/task_scheduler/sequence.cc
new file mode 100644
index 0000000..a05c802
--- /dev/null
+++ b/base/task_scheduler/sequence.cc
@@ -0,0 +1,79 @@
+// Copyright 2016 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 "base/task_scheduler/sequence.h"
+
+#include <utility>
+
+#include "base/logging.h"
+#include "base/time/time.h"
+
+namespace base {
+namespace internal {
+
+Sequence::Sequence() = default;
+
+bool Sequence::PushTask(scoped_ptr<Task> task) {
+  DCHECK(task->sequenced_time.is_null());
+  task->sequenced_time = base::TimeTicks::Now();
+
+  AutoSchedulerLock auto_lock(lock_);
+  ++num_tasks_per_priority_[static_cast<int>(task->traits.priority())];
+  queue_.push(std::move(task));
+
+  // Return true if the sequence was empty before the push.
+  return queue_.size() == 1;
+}
+
+const Task* Sequence::PeekTask() const {
+  AutoSchedulerLock auto_lock(lock_);
+
+  if (queue_.empty())
+    return nullptr;
+
+  return queue_.front().get();
+}
+
+bool Sequence::PopTask() {
+  AutoSchedulerLock auto_lock(lock_);
+  DCHECK(!queue_.empty());
+
+  const int priority_index =
+      static_cast<int>(queue_.front()->traits.priority());
+  DCHECK_GT(num_tasks_per_priority_[priority_index], 0U);
+  --num_tasks_per_priority_[priority_index];
+
+  queue_.pop();
+  return queue_.empty();
+}
+
+SequenceSortKey Sequence::GetSortKey() const {
+  TaskPriority priority = TaskPriority::LOWEST;
+  base::TimeTicks next_task_sequenced_time;
+
+  {
+    AutoSchedulerLock auto_lock(lock_);
+    DCHECK(!queue_.empty());
+
+    // Find the highest task priority in the sequence.
+    const int highest_priority_index = static_cast<int>(TaskPriority::HIGHEST);
+    const int lowest_priority_index = static_cast<int>(TaskPriority::LOWEST);
+    for (int i = highest_priority_index; i > lowest_priority_index; --i) {
+      if (num_tasks_per_priority_[i] > 0) {
+        priority = static_cast<TaskPriority>(i);
+        break;
+      }
+    }
+
+    // Save the sequenced time of the next task in the sequence.
+    next_task_sequenced_time = queue_.front()->sequenced_time;
+  }
+
+  return SequenceSortKey(priority, next_task_sequenced_time);
+}
+
+Sequence::~Sequence() = default;
+
+}  // namespace internal
+}  // namespace base
diff --git a/base/task_scheduler/sequence.h b/base/task_scheduler/sequence.h
new file mode 100644
index 0000000..e86cf59
--- /dev/null
+++ b/base/task_scheduler/sequence.h
@@ -0,0 +1,66 @@
+// Copyright 2016 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.
+
+#ifndef BASE_TASK_SCHEDULER_SEQUENCE_H_
+#define BASE_TASK_SCHEDULER_SEQUENCE_H_
+
+#include <stddef.h>
+
+#include <queue>
+
+#include "base/base_export.h"
+#include "base/macros.h"
+#include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/task_scheduler/scheduler_lock.h"
+#include "base/task_scheduler/sequence_sort_key.h"
+#include "base/task_scheduler/task.h"
+#include "base/task_scheduler/task_traits.h"
+
+namespace base {
+namespace internal {
+
+// A sequence holds tasks that must be executed in posting order.
+// This class is thread-safe.
+class BASE_EXPORT Sequence : public RefCountedThreadSafe<Sequence> {
+ public:
+  Sequence();
+
+  // Adds |task| at the end of the sequence's queue. Returns true if the
+  // sequence was empty before this operation.
+  bool PushTask(scoped_ptr<Task> task);
+
+  // Returns the task in front of the sequence's queue, if any.
+  const Task* PeekTask() const;
+
+  // Removes the task in front of the sequence's queue. Returns true if the
+  // sequence is empty after this operation. Cannot be called on an empty
+  // sequence.
+  bool PopTask();
+
+  // Returns a SequenceSortKey representing the priority of the sequence. Cannot
+  // be called on an empty sequence.
+  SequenceSortKey GetSortKey() const;
+
+ private:
+  friend class RefCountedThreadSafe<Sequence>;
+  ~Sequence();
+
+  // Synchronizes access to all members.
+  mutable SchedulerLock lock_;
+
+  // Queue of tasks to execute.
+  std::queue<scoped_ptr<Task>> queue_;
+
+  // Number of tasks contained in the sequence for each priority.
+  size_t num_tasks_per_priority_[static_cast<int>(TaskPriority::HIGHEST) + 1] =
+      {};
+
+  DISALLOW_COPY_AND_ASSIGN(Sequence);
+};
+
+}  // namespace internal
+}  // namespace base
+
+#endif  // BASE_TASK_SCHEDULER_SEQUENCE_H_
diff --git a/base/task_scheduler/sequence_sort_key.cc b/base/task_scheduler/sequence_sort_key.cc
new file mode 100644
index 0000000..758a411
--- /dev/null
+++ b/base/task_scheduler/sequence_sort_key.cc
@@ -0,0 +1,28 @@
+// Copyright 2016 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 "base/task_scheduler/sequence_sort_key.h"
+
+namespace base {
+namespace internal {
+
+SequenceSortKey::SequenceSortKey(TaskPriority priority,
+                                 TimeTicks next_task_sequenced_time)
+    : priority(priority), next_task_sequenced_time(next_task_sequenced_time) {}
+
+bool SequenceSortKey::operator<(const SequenceSortKey& other) const {
+  // This SequenceSortKey is considered less important than |other| if it has a
+  // lower priority or if it has the same priority but its next task was posted
+  // later than |other|'s.
+  const int priority_diff =
+      static_cast<int>(priority) - static_cast<int>(other.priority);
+  if (priority_diff < 0)
+    return true;
+  if (priority_diff > 0)
+    return false;
+  return next_task_sequenced_time > other.next_task_sequenced_time;
+}
+
+}  // namespace internal
+}  // namespace base
diff --git a/base/task_scheduler/sequence_sort_key.h b/base/task_scheduler/sequence_sort_key.h
new file mode 100644
index 0000000..f2dd561
--- /dev/null
+++ b/base/task_scheduler/sequence_sort_key.h
@@ -0,0 +1,34 @@
+// Copyright 2016 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.
+
+#ifndef BASE_TASK_SCHEDULER_SEQUENCE_SORT_KEY_H_
+#define BASE_TASK_SCHEDULER_SEQUENCE_SORT_KEY_H_
+
+#include "base/base_export.h"
+#include "base/task_scheduler/task_traits.h"
+#include "base/time/time.h"
+
+namespace base {
+namespace internal {
+
+// An immutable representation of the priority of a Sequence.
+struct BASE_EXPORT SequenceSortKey final {
+  SequenceSortKey(TaskPriority priority, TimeTicks next_task_sequenced_time);
+
+  bool operator<(const SequenceSortKey& other) const;
+  bool operator>(const SequenceSortKey& other) const { return other < *this; }
+
+  // Highest task priority in the sequence at the time this sort key was
+  // created.
+  const TaskPriority priority;
+
+  // Sequenced time of the next task to run in the sequence at the time this
+  // sort key was created.
+  const TimeTicks next_task_sequenced_time;
+};
+
+}  // namespace internal
+}  // namespace base
+
+#endif  // BASE_TASK_SCHEDULER_SEQUENCE_SORT_KEY_H_
diff --git a/base/task_scheduler/sequence_sort_key_unittest.cc b/base/task_scheduler/sequence_sort_key_unittest.cc
new file mode 100644
index 0000000..5c6c917
--- /dev/null
+++ b/base/task_scheduler/sequence_sort_key_unittest.cc
@@ -0,0 +1,129 @@
+// Copyright 2016 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 "base/task_scheduler/sequence_sort_key.h"
+
+#include "base/task_scheduler/task_traits.h"
+#include "base/time/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace internal {
+
+TEST(TaskSchedulerSequenceSortKeyTest, OperatorLessThan) {
+  SequenceSortKey key_a(TaskPriority::USER_BLOCKING,
+                        TimeTicks::FromInternalValue(1000));
+  SequenceSortKey key_b(TaskPriority::USER_BLOCKING,
+                        TimeTicks::FromInternalValue(2000));
+  SequenceSortKey key_c(TaskPriority::USER_VISIBLE,
+                        TimeTicks::FromInternalValue(1000));
+  SequenceSortKey key_d(TaskPriority::USER_VISIBLE,
+                        TimeTicks::FromInternalValue(2000));
+  SequenceSortKey key_e(TaskPriority::BACKGROUND,
+                        TimeTicks::FromInternalValue(1000));
+  SequenceSortKey key_f(TaskPriority::BACKGROUND,
+                        TimeTicks::FromInternalValue(2000));
+
+  EXPECT_FALSE(key_a < key_a);
+  EXPECT_LT(key_b, key_a);
+  EXPECT_LT(key_c, key_a);
+  EXPECT_LT(key_d, key_a);
+  EXPECT_LT(key_e, key_a);
+  EXPECT_LT(key_f, key_a);
+
+  EXPECT_FALSE(key_a < key_b);
+  EXPECT_FALSE(key_b < key_b);
+  EXPECT_LT(key_c, key_b);
+  EXPECT_LT(key_d, key_b);
+  EXPECT_LT(key_e, key_b);
+  EXPECT_LT(key_f, key_b);
+
+  EXPECT_FALSE(key_a < key_c);
+  EXPECT_FALSE(key_b < key_c);
+  EXPECT_FALSE(key_c < key_c);
+  EXPECT_LT(key_d, key_c);
+  EXPECT_LT(key_e, key_c);
+  EXPECT_LT(key_f, key_c);
+
+  EXPECT_FALSE(key_a < key_d);
+  EXPECT_FALSE(key_b < key_d);
+  EXPECT_FALSE(key_c < key_d);
+  EXPECT_FALSE(key_d < key_d);
+  EXPECT_LT(key_e, key_d);
+  EXPECT_LT(key_f, key_d);
+
+  EXPECT_FALSE(key_a < key_e);
+  EXPECT_FALSE(key_b < key_e);
+  EXPECT_FALSE(key_c < key_e);
+  EXPECT_FALSE(key_d < key_e);
+  EXPECT_FALSE(key_e < key_e);
+  EXPECT_LT(key_f, key_e);
+
+  EXPECT_FALSE(key_a < key_f);
+  EXPECT_FALSE(key_b < key_f);
+  EXPECT_FALSE(key_c < key_f);
+  EXPECT_FALSE(key_d < key_f);
+  EXPECT_FALSE(key_e < key_f);
+  EXPECT_FALSE(key_f < key_f);
+}
+
+TEST(TaskSchedulerSequenceSortKeyTest, OperatorGreaterThan) {
+  SequenceSortKey key_a(TaskPriority::USER_BLOCKING,
+                        TimeTicks::FromInternalValue(1000));
+  SequenceSortKey key_b(TaskPriority::USER_BLOCKING,
+                        TimeTicks::FromInternalValue(2000));
+  SequenceSortKey key_c(TaskPriority::USER_VISIBLE,
+                        TimeTicks::FromInternalValue(1000));
+  SequenceSortKey key_d(TaskPriority::USER_VISIBLE,
+                        TimeTicks::FromInternalValue(2000));
+  SequenceSortKey key_e(TaskPriority::BACKGROUND,
+                        TimeTicks::FromInternalValue(1000));
+  SequenceSortKey key_f(TaskPriority::BACKGROUND,
+                        TimeTicks::FromInternalValue(2000));
+
+  EXPECT_FALSE(key_a > key_a);
+  EXPECT_FALSE(key_b > key_a);
+  EXPECT_FALSE(key_c > key_a);
+  EXPECT_FALSE(key_d > key_a);
+  EXPECT_FALSE(key_e > key_a);
+  EXPECT_FALSE(key_f > key_a);
+
+  EXPECT_GT(key_a, key_b);
+  EXPECT_FALSE(key_b > key_b);
+  EXPECT_FALSE(key_c > key_b);
+  EXPECT_FALSE(key_d > key_b);
+  EXPECT_FALSE(key_e > key_b);
+  EXPECT_FALSE(key_f > key_b);
+
+  EXPECT_GT(key_a, key_c);
+  EXPECT_GT(key_b, key_c);
+  EXPECT_FALSE(key_c > key_c);
+  EXPECT_FALSE(key_d > key_c);
+  EXPECT_FALSE(key_e > key_c);
+  EXPECT_FALSE(key_f > key_c);
+
+  EXPECT_GT(key_a, key_d);
+  EXPECT_GT(key_b, key_d);
+  EXPECT_GT(key_c, key_d);
+  EXPECT_FALSE(key_d > key_d);
+  EXPECT_FALSE(key_e > key_d);
+  EXPECT_FALSE(key_f > key_d);
+
+  EXPECT_GT(key_a, key_e);
+  EXPECT_GT(key_b, key_e);
+  EXPECT_GT(key_c, key_e);
+  EXPECT_GT(key_d, key_e);
+  EXPECT_FALSE(key_e > key_e);
+  EXPECT_FALSE(key_f > key_e);
+
+  EXPECT_GT(key_a, key_f);
+  EXPECT_GT(key_b, key_f);
+  EXPECT_GT(key_c, key_f);
+  EXPECT_GT(key_d, key_f);
+  EXPECT_GT(key_e, key_f);
+  EXPECT_FALSE(key_f > key_f);
+}
+
+}  // namespace internal
+}  // namespace base
diff --git a/base/task_scheduler/sequence_unittest.cc b/base/task_scheduler/sequence_unittest.cc
new file mode 100644
index 0000000..d81fece
--- /dev/null
+++ b/base/task_scheduler/sequence_unittest.cc
@@ -0,0 +1,184 @@
+// Copyright 2016 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 "base/task_scheduler/sequence.h"
+
+#include "base/macros.h"
+#include "base/time/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace internal {
+
+namespace {
+
+class TaskSchedulerSequenceTest : public testing::Test {
+ public:
+  TaskSchedulerSequenceTest()
+      : task_a_owned_(
+            new Task(FROM_HERE,
+                     Closure(),
+                     TaskTraits().WithPriority(TaskPriority::BACKGROUND))),
+        task_b_owned_(
+            new Task(FROM_HERE,
+                     Closure(),
+                     TaskTraits().WithPriority(TaskPriority::USER_VISIBLE))),
+        task_c_owned_(
+            new Task(FROM_HERE,
+                     Closure(),
+                     TaskTraits().WithPriority(TaskPriority::USER_BLOCKING))),
+        task_d_owned_(
+            new Task(FROM_HERE,
+                     Closure(),
+                     TaskTraits().WithPriority(TaskPriority::USER_BLOCKING))),
+        task_e_owned_(
+            new Task(FROM_HERE,
+                     Closure(),
+                     TaskTraits().WithPriority(TaskPriority::BACKGROUND))),
+        task_a_(task_a_owned_.get()),
+        task_b_(task_b_owned_.get()),
+        task_c_(task_c_owned_.get()),
+        task_d_(task_d_owned_.get()),
+        task_e_(task_e_owned_.get()) {}
+
+ protected:
+  // Tasks to be handed off to a Sequence for testing.
+  scoped_ptr<Task> task_a_owned_;
+  scoped_ptr<Task> task_b_owned_;
+  scoped_ptr<Task> task_c_owned_;
+  scoped_ptr<Task> task_d_owned_;
+  scoped_ptr<Task> task_e_owned_;
+
+  // Raw pointers to those same tasks for verification. This is needed because
+  // the scoped_ptrs above no longer point to the tasks once they have been
+  // moved into a Sequence.
+  const Task* task_a_;
+  const Task* task_b_;
+  const Task* task_c_;
+  const Task* task_d_;
+  const Task* task_e_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(TaskSchedulerSequenceTest);
+};
+
+void ExpectSortKey(TaskPriority expected_priority,
+                   TimeTicks expected_sequenced_time,
+                   const SequenceSortKey& actual_sort_key) {
+  EXPECT_EQ(expected_priority, actual_sort_key.priority);
+  EXPECT_EQ(expected_sequenced_time, actual_sort_key.next_task_sequenced_time);
+}
+
+}  // namespace
+
+TEST_F(TaskSchedulerSequenceTest, PushPopPeek) {
+  scoped_refptr<Sequence> sequence(new Sequence);
+
+  // Push task A in the sequence. Its sequenced time should be updated and it
+  // should be in front of the sequence.
+  EXPECT_TRUE(sequence->PushTask(std::move(task_a_owned_)));
+  EXPECT_FALSE(task_a_->sequenced_time.is_null());
+  EXPECT_EQ(task_a_, sequence->PeekTask());
+
+  // Push task B, C and D in the sequence. Their sequenced time should be
+  // updated and task A should always remain in front of the sequence.
+  EXPECT_FALSE(sequence->PushTask(std::move(task_b_owned_)));
+  EXPECT_FALSE(task_b_->sequenced_time.is_null());
+  EXPECT_EQ(task_a_, sequence->PeekTask());
+
+  EXPECT_FALSE(sequence->PushTask(std::move(task_c_owned_)));
+  EXPECT_FALSE(task_c_->sequenced_time.is_null());
+  EXPECT_EQ(task_a_, sequence->PeekTask());
+
+  EXPECT_FALSE(sequence->PushTask(std::move(task_d_owned_)));
+  EXPECT_FALSE(task_d_->sequenced_time.is_null());
+  EXPECT_EQ(task_a_, sequence->PeekTask());
+
+  // Pop task A. Task B should now be in front.
+  EXPECT_FALSE(sequence->PopTask());
+  EXPECT_EQ(task_b_, sequence->PeekTask());
+
+  // Pop task B. Task C should now be in front.
+  EXPECT_FALSE(sequence->PopTask());
+  EXPECT_EQ(task_c_, sequence->PeekTask());
+
+  // Pop task C. Task D should now be in front.
+  EXPECT_FALSE(sequence->PopTask());
+  EXPECT_EQ(task_d_, sequence->PeekTask());
+
+  // Push task E in the sequence. Its sequenced time should be updated and
+  // task D should remain in front.
+  EXPECT_FALSE(sequence->PushTask(std::move(task_e_owned_)));
+  EXPECT_FALSE(task_e_->sequenced_time.is_null());
+  EXPECT_EQ(task_d_, sequence->PeekTask());
+
+  // Pop task D. Task E should now be in front.
+  EXPECT_FALSE(sequence->PopTask());
+  EXPECT_EQ(task_e_, sequence->PeekTask());
+
+  // Pop task E. The sequence should now be empty.
+  EXPECT_TRUE(sequence->PopTask());
+  EXPECT_EQ(nullptr, sequence->PeekTask());
+}
+
+TEST_F(TaskSchedulerSequenceTest, GetSortKey) {
+  scoped_refptr<Sequence> sequence(new Sequence);
+
+  // Push task A in the sequence. The highest priority is from task A
+  // (BACKGROUND). Task A is in front of the sequence.
+  sequence->PushTask(std::move(task_a_owned_));
+  ExpectSortKey(TaskPriority::BACKGROUND, task_a_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Push task B in the sequence. The highest priority is from task B
+  // (USER_VISIBLE). Task A is still in front of the sequence.
+  sequence->PushTask(std::move(task_b_owned_));
+  ExpectSortKey(TaskPriority::USER_VISIBLE, task_a_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Push task C in the sequence. The highest priority is from task C
+  // (USER_BLOCKING). Task A is still in front of the sequence.
+  sequence->PushTask(std::move(task_c_owned_));
+  ExpectSortKey(TaskPriority::USER_BLOCKING, task_a_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Push task D in the sequence. The highest priority is from tasks C/D
+  // (USER_BLOCKING). Task A is still in front of the sequence.
+  sequence->PushTask(std::move(task_d_owned_));
+  ExpectSortKey(TaskPriority::USER_BLOCKING, task_a_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Pop task A. The highest priority is still USER_BLOCKING. The task in front
+  // of the sequence is now task B.
+  sequence->PopTask();
+  ExpectSortKey(TaskPriority::USER_BLOCKING, task_b_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Pop task B. The highest priority is still USER_BLOCKING. The task in front
+  // of the sequence is now task C.
+  sequence->PopTask();
+  ExpectSortKey(TaskPriority::USER_BLOCKING, task_c_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Pop task C. The highest priority is still USER_BLOCKING. The task in front
+  // of the sequence is now task D.
+  sequence->PopTask();
+  ExpectSortKey(TaskPriority::USER_BLOCKING, task_d_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Push task E in the sequence. The highest priority is still USER_BLOCKING.
+  // The task in front of the sequence is still task D.
+  sequence->PushTask(std::move(task_e_owned_));
+  ExpectSortKey(TaskPriority::USER_BLOCKING, task_d_->sequenced_time,
+                sequence->GetSortKey());
+
+  // Pop task D. The highest priority is now from task E (BACKGROUND). The
+  // task in front of the sequence is now task E.
+  sequence->PopTask();
+  ExpectSortKey(TaskPriority::BACKGROUND, task_e_->sequenced_time,
+                sequence->GetSortKey());
+}
+
+}  // namespace internal
+}  // namespace base
diff --git a/base/task_scheduler/task.cc b/base/task_scheduler/task.cc
new file mode 100644
index 0000000..ae63403
--- /dev/null
+++ b/base/task_scheduler/task.cc
@@ -0,0 +1,22 @@
+// Copyright 2016 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 "base/task_scheduler/task.h"
+
+namespace base {
+namespace internal {
+
+Task::Task(const tracked_objects::Location& posted_from,
+           const Closure& task,
+           const TaskTraits& traits)
+    : PendingTask(posted_from,
+                  task,
+                  TimeTicks(),  // No delayed run time.
+                  false),       // Not nestable.
+      traits(traits) {}
+
+Task::~Task() = default;
+
+}  // namespace internal
+}  // namespace base
diff --git a/base/task_scheduler/task.h b/base/task_scheduler/task.h
new file mode 100644
index 0000000..6ac483d
--- /dev/null
+++ b/base/task_scheduler/task.h
@@ -0,0 +1,39 @@
+// Copyright 2016 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.
+
+#ifndef BASE_TASK_SCHEDULER_TASK_H_
+#define BASE_TASK_SCHEDULER_TASK_H_
+
+#include "base/base_export.h"
+#include "base/callback_forward.h"
+#include "base/location.h"
+#include "base/pending_task.h"
+#include "base/task_scheduler/task_traits.h"
+#include "base/time/time.h"
+
+namespace base {
+namespace internal {
+
+// A task is a unit of work inside the task scheduler. Support for tracing and
+// profiling inherited from PendingTask.
+struct BASE_EXPORT Task : public PendingTask {
+  Task(const tracked_objects::Location& posted_from,
+       const Closure& task,
+       const TaskTraits& traits);
+  ~Task();
+
+  // The TaskTraits of this task.
+  const TaskTraits traits;
+
+  // The time at which the task was inserted in its sequence. For an undelayed
+  // task, this happens at post time. For a delayed task, this happens some
+  // time after the task's delay has expired. If the task hasn't been inserted
+  // in a sequence yet, this defaults to a null TimeTicks.
+  TimeTicks sequenced_time;
+};
+
+}  // namespace internal
+}  // namespace base
+
+#endif  // BASE_TASK_SCHEDULER_TASK_H_
diff --git a/base/task_scheduler/task_traits.cc b/base/task_scheduler/task_traits.cc
index be77ba9..9e5be32 100644
--- a/base/task_scheduler/task_traits.cc
+++ b/base/task_scheduler/task_traits.cc
@@ -4,6 +4,8 @@
 
 #include "base/task_scheduler/task_traits.h"
 
+#include <ostream>
+
 namespace base {
 
 // Do not rely on defaults hard-coded below beyond the guarantees described in
@@ -32,4 +34,18 @@ TaskTraits& TaskTraits::WithShutdownBehavior(
   return *this;
 }
 
+void PrintTo(const TaskPriority& task_priority, std::ostream* os) {
+  switch (task_priority) {
+    case TaskPriority::BACKGROUND:
+      *os << "BACKGROUND";
+      break;
+    case TaskPriority::USER_VISIBLE:
+      *os << "USER_VISIBLE";
+      break;
+    case TaskPriority::USER_BLOCKING:
+      *os << "USER_BLOCKING";
+      break;
+  }
+}
+
 }  // namespace base
diff --git a/base/task_scheduler/task_traits.h b/base/task_scheduler/task_traits.h
index 1566241..fbd63c5 100644
--- a/base/task_scheduler/task_traits.h
+++ b/base/task_scheduler/task_traits.h
@@ -5,37 +5,38 @@
 #ifndef BASE_TASK_SCHEDULER_TASK_TRAITS_H_
 #define BASE_TASK_SCHEDULER_TASK_TRAITS_H_
 
+#include <stdint.h>
+
+#include <iosfwd>
+
 #include "base/base_export.h"
 #include "build/build_config.h"
 
 namespace base {
 
-using TaskPriorityUnderlyingType = char;
-
-// Valid priorities supported by the task scheduler.
-// A higher value means a higher priority in the scheduler.
-enum class TaskPriority : TaskPriorityUnderlyingType {
-  // This task affects UI immediately after a user interaction.
-  // Example: Generating data shown in the UI immediately after a click.
-  USER_BLOCKING = 2,
+// Valid priorities supported by the task scheduler. Note: internal algorithms
+// depend on priorities being expressed as a continuous zero-based list from
+// lowest to highest priority. Users of this API shouldn't otherwise care about
+// nor use the underlying values.
+enum class TaskPriority {
+  // This will always be equal to the lowest priority available.
+  LOWEST = 0,
+  // User won't notice if this task takes an arbitrarily long time to complete.
+  BACKGROUND = LOWEST,
   // This task affects UI or responsiveness of future user interactions. It is
   // not an immediate response to a user interaction.
   // Examples:
   // - Updating the UI to reflect progress on a long task.
   // - Loading data that might be shown in the UI after a future user
   //   interaction.
-  USER_VISIBLE = 1,
-  // Everything else (user won't notice if this takes an arbitrarily long time
-  // to complete).
-  BACKGROUND = 0,
+  USER_VISIBLE,
+  // This task affects UI immediately after a user interaction.
+  // Example: Generating data shown in the UI immediately after a click.
+  USER_BLOCKING,
+  // This will always be equal to the highest priority available.
+  HIGHEST = USER_BLOCKING,
 };
 
-static_assert(TaskPriority::BACKGROUND < TaskPriority::USER_VISIBLE &&
-                  TaskPriority::USER_VISIBLE < TaskPriority::USER_BLOCKING,
-              "Higher priorities must correspond to higher underlying values.");
-
-const TaskPriorityUnderlyingType kNumTaskPriorities = 3;
-
 // Valid shutdown behaviors supported by the task scheduler.
 enum class TaskShutdownBehavior {
   // Tasks posted with this mode which have not started executing before
@@ -76,6 +77,7 @@ enum class TaskShutdownBehavior {
 
 // Describes metadata for a single task or a group of tasks.
 class BASE_EXPORT TaskTraits {
+ public:
   // Constructs a default TaskTraits for tasks with
   //     (1) no I/O,
   //     (2) low priority, and
@@ -83,6 +85,8 @@ class BASE_EXPORT TaskTraits {
   // Tasks that require stricter guarantees should highlight those by requesting
   // explicit traits below.
   TaskTraits();
+  TaskTraits(const TaskTraits& other) = default;
+  TaskTraits& operator=(const TaskTraits& other) = default;
   ~TaskTraits();
 
   // Allows tasks with these traits to do file I/O.
@@ -122,6 +126,9 @@ enum class ExecutionMode {
   SINGLE_THREADED,
 };
 
+// Pretty Printer for Google Test.
+void BASE_EXPORT PrintTo(const TaskPriority& task_priority, std::ostream* os);
+
 }  // namespace base
 
 #endif  // BASE_TASK_SCHEDULER_TASK_TRAITS_H_