TaskScheduler [4/9] Priority Queue

base/task_scheduler/priority_queue_unittest.cc

Index: base/task_scheduler/priority_queue_unittest.cc
diff --git a/base/task_scheduler/priority_queue_unittest.cc b/base/task_scheduler/priority_queue_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..041a062c1a44e25b442563743eded8f355cc66da
--- /dev/null
+++ b/base/task_scheduler/priority_queue_unittest.cc
@@ -0,0 +1,229 @@
+// 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) {}
+
+  // 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_ = false;
+
+  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;

[danakj, 2016/03/17 21:32:15]

use the constructor rather than assigning a raw pointer, for all of these. ie
scoped_refptr<T> t(new T);

[fdoray, 2016/03/18 16:06:56]

Done.

+  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 PriorityQueue and a Transaction.
+  testing::StrictMock<PriorityQueueCallbackMock> mock;
+  PriorityQueue pq(
+      Bind(&PriorityQueueCallbackMock::SequenceInsertedInPriorityQueue,
+           Unretained(&mock)));
+  scoped_ptr<PriorityQueue::Transaction> transaction(pq.BeginTransaction());
+  ExpectSequenceAndSortKey(PriorityQueue::SequenceAndSortKey(),

[danakj, 2016/03/17 21:32:15]

You can use a SCOPED_TRACE() to make errors show which call to
ExpectSequenceAndSortKey failed.

If you want, you could macro this

#define EXPECT_SEQUENCE_AND_SORT_KEY_EQ(e, a) { \
  TRACE_SCOPED(""); \
  ExpectS...(e, a); \
}

[fdoray, 2016/03/18 16:06:56]

Done.

+                           transaction->Peek());
+
+  // Push |sequence_a| in the PriorityQueue. It becomes the sequence with the
+  // highest priority.
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_a, sort_key_a)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_a, sort_key_a),
+      transaction->Peek());
+
+  // Push |sequence_b| in the PriorityQueue. It becomes the sequence with the
+  // highest priority.
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b),
+      transaction->Peek());
+
+  // Push |sequence_c| in the PriorityQueue. |sequence_b| is still the sequence
+  // with the highest priority.
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_c, sort_key_c)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b),
+      transaction->Peek());
+
+  // Push |sequence_d| in the PriorityQueue. |sequence_b| is still the sequence
+  // with the highest priority.
+  transaction->Push(make_scoped_ptr(
+      new PriorityQueue::SequenceAndSortKey(sequence_d, sort_key_d)));
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_b, sort_key_b),
+      transaction->Peek());
+
+  // Pop |sequence_b| from the PriorityQueue. |sequence_c| becomes the sequence
+  // with the highest priority.
+  transaction->Pop();
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_c, sort_key_c),
+      transaction->Peek());
+
+  // Pop |sequence_c| from the PriorityQueue. |sequence_a| becomes the sequence
+  // with the highest priority.
+  transaction->Pop();
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_a, sort_key_a),
+      transaction->Peek());
+
+  // Pop |sequence_a| from the PriorityQueue. |sequence_d| becomes the sequence
+  // with the highest priority.
+  transaction->Pop();
+  ExpectSequenceAndSortKey(
+      PriorityQueue::SequenceAndSortKey(sequence_d, sort_key_d),
+      transaction->Peek());
+
+  // Pop |sequence_d| from the PriorityQueue. It is now empty.
+  transaction->Pop();
+  ExpectSequenceAndSortKey(PriorityQueue::SequenceAndSortKey(),
+                           transaction->Peek());
+
+  // Expect 4 calls to mock.SequenceInsertedInPriorityQueue() when the
+  // Transaction is destroyed.

[danakj, 2016/03/17 21:32:15]

Can you VerifyAndClearExpectations(); before the EXPECT_CALL, so we can tell
that these come from the reset() and not from the Pushes above?

[fdoray, 2016/03/18 16:06:55]

This is already covered by using a StrictMock: the test fails if there are calls
to the mock function before EXPECT_CALL.

+  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({

[robliao, 2016/03/17 17:48:10]

We'll want to start using EXPECT_DCHECK_DEATH here.

[fdoray, 2016/03/17 19:12:02]

Done.

+    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.

[danakj, 2016/03/17 21:32:15]

"still", though the word is superfluous here.

[fdoray, 2016/03/18 16:06:56]

Done.

+  PlatformThread::Sleep(TimeDelta::FromMilliseconds(200));
+  EXPECT_FALSE(thread_beginning_transaction.transaction_began());

[danakj, 2016/03/17 21:32:15]

This is a data race. You need a lock to access this variable on multiple
threads.

[fdoray, 2016/03/18 16:06:55]

I used a WaitableEvent to fix the data race because IMO
transaction_began_.Signal() is simpler than lock+set boolean. WDYT?

+
+  // 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());

[danakj, 2016/03/17 21:32:15]

ditto

[fdoray, 2016/03/18 16:06:55]

Done.

+}
+
+TEST(TaskSchedulerPriorityQueueTest, SequenceAndSortKeyIsNull) {
+  EXPECT_TRUE(PriorityQueue::SequenceAndSortKey().is_null());
+  EXPECT_FALSE(PriorityQueue::SequenceAndSortKey(
+                   new Sequence,

[danakj, 2016/03/17 21:32:15]

make_scoped_refptr

[fdoray, 2016/03/18 16:06:56]

Done.

+                   SequenceSortKey(TaskPriority::USER_VISIBLE, TimeTicks()))
+                   .is_null());

[danakj, 2016/03/17 21:32:15]

consider making the key outside of the EXPECT statement so this reads better

[fdoray, 2016/03/18 16:06:55]

Done.

+}
+
+}  // namespace internal
+}  // namespace base