1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "base/test/sequenced_task_runner_test_template.h"
6
7#include <ostream>
8
9#include "base/location.h"
10
11namespace base {
12
13namespace internal {
14
15TaskEvent::TaskEvent(int i, Type type)
16  : i(i), type(type) {
17}
18
19SequencedTaskTracker::SequencedTaskTracker()
20    : next_post_i_(0),
21      task_end_count_(0),
22      task_end_cv_(&lock_) {
23}
24
25void SequencedTaskTracker::PostWrappedNonNestableTask(
26    const scoped_refptr<SequencedTaskRunner>& task_runner,
27    const Closure& task) {
28  AutoLock event_lock(lock_);
29  const int post_i = next_post_i_++;
30  Closure wrapped_task = Bind(&SequencedTaskTracker::RunTask, this,
31                              task, post_i);
32  task_runner->PostNonNestableTask(FROM_HERE, wrapped_task);
33  TaskPosted(post_i);
34}
35
36void SequencedTaskTracker::PostWrappedNestableTask(
37    const scoped_refptr<SequencedTaskRunner>& task_runner,
38    const Closure& task) {
39  AutoLock event_lock(lock_);
40  const int post_i = next_post_i_++;
41  Closure wrapped_task = Bind(&SequencedTaskTracker::RunTask, this,
42                              task, post_i);
43  task_runner->PostTask(FROM_HERE, wrapped_task);
44  TaskPosted(post_i);
45}
46
47void SequencedTaskTracker::PostWrappedDelayedNonNestableTask(
48    const scoped_refptr<SequencedTaskRunner>& task_runner,
49    const Closure& task,
50    TimeDelta delay) {
51  AutoLock event_lock(lock_);
52  const int post_i = next_post_i_++;
53  Closure wrapped_task = Bind(&SequencedTaskTracker::RunTask, this,
54                              task, post_i);
55  task_runner->PostNonNestableDelayedTask(FROM_HERE, wrapped_task, delay);
56  TaskPosted(post_i);
57}
58
59void SequencedTaskTracker::PostNonNestableTasks(
60    const scoped_refptr<SequencedTaskRunner>& task_runner,
61    int task_count) {
62  for (int i = 0; i < task_count; ++i) {
63    PostWrappedNonNestableTask(task_runner, Closure());
64  }
65}
66
67void SequencedTaskTracker::RunTask(const Closure& task, int task_i) {
68  TaskStarted(task_i);
69  if (!task.is_null())
70    task.Run();
71  TaskEnded(task_i);
72}
73
74void SequencedTaskTracker::TaskPosted(int i) {
75  // Caller must own |lock_|.
76  events_.push_back(TaskEvent(i, TaskEvent::POST));
77}
78
79void SequencedTaskTracker::TaskStarted(int i) {
80  AutoLock lock(lock_);
81  events_.push_back(TaskEvent(i, TaskEvent::START));
82}
83
84void SequencedTaskTracker::TaskEnded(int i) {
85  AutoLock lock(lock_);
86  events_.push_back(TaskEvent(i, TaskEvent::END));
87  ++task_end_count_;
88  task_end_cv_.Signal();
89}
90
91const std::vector<TaskEvent>&
92SequencedTaskTracker::GetTaskEvents() const {
93  return events_;
94}
95
96void SequencedTaskTracker::WaitForCompletedTasks(int count) {
97  AutoLock lock(lock_);
98  while (task_end_count_ < count)
99    task_end_cv_.Wait();
100}
101
102SequencedTaskTracker::~SequencedTaskTracker() {
103}
104
105void PrintTo(const TaskEvent& event, std::ostream* os) {
106  *os << "(i=" << event.i << ", type=";
107  switch (event.type) {
108    case TaskEvent::POST: *os << "POST"; break;
109    case TaskEvent::START: *os << "START"; break;
110    case TaskEvent::END: *os << "END"; break;
111  }
112  *os << ")";
113}
114
115namespace {
116
117// Returns the task ordinals for the task event type |type| in the order that
118// they were recorded.
119std::vector<int> GetEventTypeOrder(const std::vector<TaskEvent>& events,
120                                   TaskEvent::Type type) {
121  std::vector<int> tasks;
122  std::vector<TaskEvent>::const_iterator event;
123  for (event = events.begin(); event != events.end(); ++event) {
124    if (event->type == type)
125      tasks.push_back(event->i);
126  }
127  return tasks;
128}
129
130// Returns all task events for task |task_i|.
131std::vector<TaskEvent::Type> GetEventsForTask(
132    const std::vector<TaskEvent>& events,
133    int task_i) {
134  std::vector<TaskEvent::Type> task_event_orders;
135  std::vector<TaskEvent>::const_iterator event;
136  for (event = events.begin(); event != events.end(); ++event) {
137    if (event->i == task_i)
138      task_event_orders.push_back(event->type);
139  }
140  return task_event_orders;
141}
142
143// Checks that the task events for each task in |events| occur in the order
144// {POST, START, END}, and that there is only one instance of each event type
145// per task.
146::testing::AssertionResult CheckEventOrdersForEachTask(
147    const std::vector<TaskEvent>& events,
148    int task_count) {
149  std::vector<TaskEvent::Type> expected_order;
150  expected_order.push_back(TaskEvent::POST);
151  expected_order.push_back(TaskEvent::START);
152  expected_order.push_back(TaskEvent::END);
153
154  // This is O(n^2), but it runs fast enough currently so is not worth
155  // optimizing.
156  for (int i = 0; i < task_count; ++i) {
157    const std::vector<TaskEvent::Type> task_events =
158        GetEventsForTask(events, i);
159    if (task_events != expected_order) {
160      return ::testing::AssertionFailure()
161          << "Events for task " << i << " are out of order; expected: "
162          << ::testing::PrintToString(expected_order) << "; actual: "
163          << ::testing::PrintToString(task_events);
164    }
165  }
166  return ::testing::AssertionSuccess();
167}
168
169// Checks that no two tasks were running at the same time. I.e. the only
170// events allowed between the START and END of a task are the POSTs of other
171// tasks.
172::testing::AssertionResult CheckNoTaskRunsOverlap(
173    const std::vector<TaskEvent>& events) {
174  // If > -1, we're currently inside a START, END pair.
175  int current_task_i = -1;
176
177  std::vector<TaskEvent>::const_iterator event;
178  for (event = events.begin(); event != events.end(); ++event) {
179    bool spurious_event_found = false;
180
181    if (current_task_i == -1) {  // Not inside a START, END pair.
182      switch (event->type) {
183        case TaskEvent::POST:
184          break;
185        case TaskEvent::START:
186          current_task_i = event->i;
187          break;
188        case TaskEvent::END:
189          spurious_event_found = true;
190          break;
191      }
192
193    } else {  // Inside a START, END pair.
194      bool interleaved_task_detected = false;
195
196      switch (event->type) {
197        case TaskEvent::POST:
198          if (event->i == current_task_i)
199            spurious_event_found = true;
200          break;
201        case TaskEvent::START:
202          interleaved_task_detected = true;
203          break;
204        case TaskEvent::END:
205          if (event->i != current_task_i)
206            interleaved_task_detected = true;
207          else
208            current_task_i = -1;
209          break;
210      }
211
212      if (interleaved_task_detected) {
213        return ::testing::AssertionFailure()
214            << "Found event " << ::testing::PrintToString(*event)
215            << " between START and END events for task " << current_task_i
216            << "; event dump: " << ::testing::PrintToString(events);
217      }
218    }
219
220    if (spurious_event_found) {
221      const int event_i = event - events.begin();
222      return ::testing::AssertionFailure()
223          << "Spurious event " << ::testing::PrintToString(*event)
224          << " at position " << event_i << "; event dump: "
225          << ::testing::PrintToString(events);
226    }
227  }
228
229  return ::testing::AssertionSuccess();
230}
231
232}  // namespace
233
234::testing::AssertionResult CheckNonNestableInvariants(
235    const std::vector<TaskEvent>& events,
236    int task_count) {
237  const std::vector<int> post_order =
238      GetEventTypeOrder(events, TaskEvent::POST);
239  const std::vector<int> start_order =
240      GetEventTypeOrder(events, TaskEvent::START);
241  const std::vector<int> end_order =
242      GetEventTypeOrder(events, TaskEvent::END);
243
244  if (start_order != post_order) {
245    return ::testing::AssertionFailure()
246        << "Expected START order (which equals actual POST order): \n"
247        << ::testing::PrintToString(post_order)
248        << "\n Actual START order:\n"
249        << ::testing::PrintToString(start_order);
250  }
251
252  if (end_order != post_order) {
253    return ::testing::AssertionFailure()
254        << "Expected END order (which equals actual POST order): \n"
255        << ::testing::PrintToString(post_order)
256        << "\n Actual END order:\n"
257        << ::testing::PrintToString(end_order);
258  }
259
260  const ::testing::AssertionResult result =
261      CheckEventOrdersForEachTask(events, task_count);
262  if (!result)
263    return result;
264
265  return CheckNoTaskRunsOverlap(events);
266}
267
268}  // namespace internal
269
270}  // namespace base
271