TaskScheduler [4/9] Priority Queue

base/task_scheduler/priority_queue_unittest.cc

+// 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/priority_queue.h"
+
+#include "base/bind.h"
+#include "base/bind_helpers.h"
+#include "base/macros.h"
+#include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/task_scheduler/sequence.h"
+#include "base/task_scheduler/task.h"
+#include "base/task_scheduler/task_traits.h"
+#include "base/threading/platform_thread.h"
+#include "base/threading/simple_thread.h"
+#include "base/time/time.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace internal {
+
+namespace {
+
+class PriorityQueueCallbackMock {
+ public:
+  PriorityQueueCallbackMock() = default;
+  MOCK_METHOD0(SequenceInsertedInPriorityQueue, void());
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(PriorityQueueCallbackMock);
+};
+
+class ThreadBeginningTransaction : public SimpleThread {
+ public:
+  explicit ThreadBeginningTransaction(PriorityQueue* priority_queue)
+      : SimpleThread("ThreadBeginningTransaction"),
+        priority_queue_(priority_queue),
+        transaction_began_(false) {}
+
+  // SimpleThread:
+  void Run() override {
+    scoped_ptr<PriorityQueue::Transaction> transaction =
+        priority_queue_->BeginTransaction();
+    transaction_began_ = true;
+  }
+
+  bool transaction_began() const { return transaction_began_; }
+
+ private:
+  PriorityQueue* const priority_queue_;
+  bool transaction_began_;
+
+  DISALLOW_COPY_AND_ASSIGN(ThreadBeginningTransaction);
+};
+
+void ExpectSequenceAndSortKey(const PriorityQueue::SequenceAndSortKey& expected,
+                              const PriorityQueue::SequenceAndSortKey& actual) {
+  EXPECT_EQ(expected.sequence, actual.sequence);
+  EXPECT_EQ(expected.sort_key.priority, actual.sort_key.priority);
+  EXPECT_EQ(expected.sort_key.next_task_sequenced_time,
+            actual.sort_key.next_task_sequenced_time);
+}
+
+}  // namespace
+
+TEST(TaskSchedulerPriorityQueueTest, PushPopPeek) {
+  // Create test sequences.
+  scoped_refptr<Sequence> sequence_a = new Sequence;
+  sequence_a->PushTask(make_scoped_ptr(
+      new Task(FROM_HERE, Closure(),
+               TaskTraits().WithPriority(TaskPriority::USER_VISIBLE))));
+  SequenceSortKey sort_key_a = sequence_a->GetSortKey();
+
+  scoped_refptr<Sequence> sequence_b = new Sequence;
+  sequence_b->PushTask(make_scoped_ptr(
+      new Task(FROM_HERE, Closure(),
+               TaskTraits().WithPriority(TaskPriority::USER_BLOCKING))));
+  SequenceSortKey sort_key_b = sequence_b->GetSortKey();
+
+  scoped_refptr<Sequence> sequence_c = new Sequence;
+  sequence_c->PushTask(make_scoped_ptr(
+      new Task(FROM_HERE, Closure(),
+               TaskTraits().WithPriority(TaskPriority::USER_BLOCKING))));
+  SequenceSortKey sort_key_c = sequence_c->GetSortKey();
+
+  scoped_refptr<Sequence> sequence_d = new Sequence;
+  sequence_d->PushTask(make_scoped_ptr(
+      new Task(FROM_HERE, Closure(),
+               TaskTraits().WithPriority(TaskPriority::BACKGROUND))));
+  SequenceSortKey sort_key_d = sequence_d->GetSortKey();
+
+  // Create a priority queue and a transaction.
+  testing::StrictMock<PriorityQueueCallbackMock> mock;
+  PriorityQueue pq(
+      Bind(&PriorityQueueCallbackMock::SequenceInsertedInPriorityQueue,
+           Unretained(&mock)));
+  scoped_ptr<PriorityQueue::Transaction> transaction(pq.BeginTransaction());
+  ExpectSequenceAndSortKey(PriorityQueue::SequenceAndSortKey(),
+                           transaction->Peek());
+
+  // Push sequences in the priority queue.
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_a, sort_key_a)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_a, sort_key_a),
+      transaction->Peek());
+
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b),
+      transaction->Peek());
+
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_c, sort_key_c)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b),
+      transaction->Peek());
+
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_d, sort_key_d)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b),
+      transaction->Peek());
+
+  // Pop sequences from the priority queue.
+  transaction->Pop();
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_c, sort_key_c),
+      transaction->Peek());
+
+  transaction->Pop();
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_a, sort_key_a),
+      transaction->Peek());
+
+  transaction->Pop();
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_d, sort_key_d),
+      transaction->Peek());
+
+  transaction->Pop();
+  ExpectSequenceAndSortKey(PriorityQueue::SequenceAndSortKey(),
+                           transaction->Peek());
+
+  // Expect 4 calls to mock.SequenceInsertedInPriorityQueue() when the
+  // Transaction is destroyed.
+  EXPECT_CALL(mock, SequenceInsertedInPriorityQueue()).Times(4);
+  transaction.reset();
+}
+
+// Check that creating Transactions on the same thread for 2 unrelated
+// PriorityQueues causes a crash.
+TEST(TaskSchedulerPriorityQueueTest, IllegalTwoTransactionsSameThread) {
+  PriorityQueue pq_a(Bind(&DoNothing));
+  PriorityQueue pq_b(Bind(&DoNothing));
+
+  EXPECT_DEBUG_DEATH({
+    scoped_ptr<PriorityQueue::Transaction> transaction_a =
+        pq_a.BeginTransaction();
+    scoped_ptr<PriorityQueue::Transaction> transaction_b =
+        pq_b.BeginTransaction();
+  }, "");
+}
+
+// Check that there is no crash when Transactions are created on the same thread
+// for 2 PriorityQueues which have a predecessor relationship.
+TEST(TaskSchedulerPriorityQueueTest, LegalTwoTransactionsSameThread) {
+  PriorityQueue pq_a(Bind(&DoNothing));
+  PriorityQueue pq_b(Bind(&DoNothing), &pq_a);
+
+  // This shouldn't crash.
+  scoped_ptr<PriorityQueue::Transaction> transaction_a =
+      pq_a.BeginTransaction();
+  scoped_ptr<PriorityQueue::Transaction> transaction_b =
+      pq_b.BeginTransaction();
+}
+
+// Check that it is possible to begin multiple Transactions for the same
+// PriorityQueue on different threads. The call to BeginTransaction() on the
+// second thread should block until the Transaction has ended on the first
+// thread.
+TEST(TaskSchedulerPriorityQueueTest, TwoTransactionsTwoThreads) {
+  PriorityQueue pq(Bind(&DoNothing));
+
+  // Call BeginTransaction() on this thread and keep the Transaction alive.
+  scoped_ptr<PriorityQueue::Transaction> transaction = pq.BeginTransaction();
+
+  // Call BeginTransaction() on another thread.
+  ThreadBeginningTransaction thread_beginning_transaction(&pq);
+  thread_beginning_transaction.Start();
+
+  // After a few milliseconds, the call to BeginTransaction() on the other
+  // thread should stil not have returned.
+  PlatformThread::Sleep(TimeDelta::FromMilliseconds(200));
+  EXPECT_FALSE(thread_beginning_transaction.transaction_began());
+
+  // End the Transaction on the current thread.
+  transaction.reset();
+
+  // The other thread should exit after its call to BeginTransaction() returns.
+  thread_beginning_transaction.Join();
+  EXPECT_TRUE(thread_beginning_transaction.transaction_began());
+}
+
+TEST(TaskSchedulerPriorityQueueTest, SequenceAndSortKeyIsNull) {
+  EXPECT_TRUE(PriorityQueue::SequenceAndSortKey().is_null());
+
+  scoped_refptr<Sequence> sequence = new Sequence;
+  sequence->PushTask(make_scoped_ptr(
+      new Task(FROM_HERE, Closure(),
+               TaskTraits().WithPriority(TaskPriority::USER_VISIBLE))));

[gab, 2016/02/24 18:07:38]

Does the sequence need to have a task in it for this test to be valid? If not
I'd vote for keeping it minimalistic.

[fdoray, 2016/02/24 18:18:42]

Done.

+  EXPECT_FALSE(
+      PriorityQueue::SequenceAndSortKey(sequence, sequence->GetSortKey())
+          .is_null());
+}
+
+}  // namespace internal
+}  // namespace base