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

#include "base/test/sequenced_task_runner_test_template.h"

#include <ostream>

#include "base/location.h"

namespace base {

namespace internal {

TaskEvent::TaskEvent(int i, Type type)
  : i(i), type(type) {
}

SequencedTaskTracker::SequencedTaskTracker()
    : next_post_i_(0),
      task_end_count_(0),
      task_end_cv_(&lock_) {
}

void SequencedTaskTracker::PostWrappedNonNestableTask(
    SequencedTaskRunner* task_runner,
    const Closure& task) {
  AutoLock event_lock(lock_);
  const int post_i = next_post_i_++;
  Closure wrapped_task = Bind(&SequencedTaskTracker::RunTask, this,
                              task, post_i);
  task_runner->PostNonNestableTask(FROM_HERE, wrapped_task);
  TaskPosted(post_i);
}

void SequencedTaskTracker::PostWrappedNestableTask(
    SequencedTaskRunner* task_runner,
    const Closure& task) {
  AutoLock event_lock(lock_);
  const int post_i = next_post_i_++;
  Closure wrapped_task = Bind(&SequencedTaskTracker::RunTask, this,
                              task, post_i);
  task_runner->PostTask(FROM_HERE, wrapped_task);
  TaskPosted(post_i);
}

void SequencedTaskTracker::PostWrappedDelayedNonNestableTask(
    SequencedTaskRunner* task_runner,
    const Closure& task,
    TimeDelta delay) {
  AutoLock event_lock(lock_);
  const int post_i = next_post_i_++;
  Closure wrapped_task = Bind(&SequencedTaskTracker::RunTask, this,
                              task, post_i);
  task_runner->PostNonNestableDelayedTask(FROM_HERE, wrapped_task, delay);
  TaskPosted(post_i);
}

void SequencedTaskTracker::PostNonNestableTasks(
    SequencedTaskRunner* task_runner,
    int task_count) {
  for (int i = 0; i < task_count; ++i) {
    PostWrappedNonNestableTask(task_runner, Closure());
  }
}

void SequencedTaskTracker::RunTask(const Closure& task, int task_i) {
  TaskStarted(task_i);
  if (!task.is_null())
    task.Run();
  TaskEnded(task_i);
}

void SequencedTaskTracker::TaskPosted(int i) {
  // Caller must own |lock_|.
  events_.push_back(TaskEvent(i, TaskEvent::POST));
}

void SequencedTaskTracker::TaskStarted(int i) {
  AutoLock lock(lock_);
  events_.push_back(TaskEvent(i, TaskEvent::START));
}

void SequencedTaskTracker::TaskEnded(int i) {
  AutoLock lock(lock_);
  events_.push_back(TaskEvent(i, TaskEvent::END));
  ++task_end_count_;
  task_end_cv_.Signal();
}

const std::vector<TaskEvent>&
SequencedTaskTracker::GetTaskEvents() const {
  return events_;
}

void SequencedTaskTracker::WaitForCompletedTasks(int count) {
  AutoLock lock(lock_);
  while (task_end_count_ < count)
    task_end_cv_.Wait();
}

SequencedTaskTracker::~SequencedTaskTracker() = default;

void PrintTo(const TaskEvent& event, std::ostream* os) {
  *os << "(i=" << event.i << ", type=";
  switch (event.type) {
    case TaskEvent::POST: *os << "POST"; break;
    case TaskEvent::START: *os << "START"; break;
    case TaskEvent::END: *os << "END"; break;
  }
  *os << ")";
}

namespace {

// Returns the task ordinals for the task event type |type| in the order that
// they were recorded.
std::vector<int> GetEventTypeOrder(const std::vector<TaskEvent>& events,
                                   TaskEvent::Type type) {
  std::vector<int> tasks;
  std::vector<TaskEvent>::const_iterator event;
  for (event = events.begin(); event != events.end(); ++event) {
    if (event->type == type)
      tasks.push_back(event->i);
  }
  return tasks;
}

// Returns all task events for task |task_i|.
std::vector<TaskEvent::Type> GetEventsForTask(
    const std::vector<TaskEvent>& events,
    int task_i) {
  std::vector<TaskEvent::Type> task_event_orders;
  std::vector<TaskEvent>::const_iterator event;
  for (event = events.begin(); event != events.end(); ++event) {
    if (event->i == task_i)
      task_event_orders.push_back(event->type);
  }
  return task_event_orders;
}

// Checks that the task events for each task in |events| occur in the order
// {POST, START, END}, and that there is only one instance of each event type
// per task.
::testing::AssertionResult CheckEventOrdersForEachTask(
    const std::vector<TaskEvent>& events,
    int task_count) {
  std::vector<TaskEvent::Type> expected_order;
  expected_order.push_back(TaskEvent::POST);
  expected_order.push_back(TaskEvent::START);
  expected_order.push_back(TaskEvent::END);

  // This is O(n^2), but it runs fast enough currently so is not worth
  // optimizing.
  for (int i = 0; i < task_count; ++i) {
    const std::vector<TaskEvent::Type> task_events =
        GetEventsForTask(events, i);
    if (task_events != expected_order) {
      return ::testing::AssertionFailure()
          << "Events for task " << i << " are out of order; expected: "
          << ::testing::PrintToString(expected_order) << "; actual: "
          << ::testing::PrintToString(task_events);
    }
  }
  return ::testing::AssertionSuccess();
}

// Checks that no two tasks were running at the same time. I.e. the only
// events allowed between the START and END of a task are the POSTs of other
// tasks.
::testing::AssertionResult CheckNoTaskRunsOverlap(
    const std::vector<TaskEvent>& events) {
  // If > -1, we're currently inside a START, END pair.
  int current_task_i = -1;

  std::vector<TaskEvent>::const_iterator event;
  for (event = events.begin(); event != events.end(); ++event) {
    bool spurious_event_found = false;

    if (current_task_i == -1) {  // Not inside a START, END pair.
      switch (event->type) {
        case TaskEvent::POST:
          break;
        case TaskEvent::START:
          current_task_i = event->i;
          break;
        case TaskEvent::END:
          spurious_event_found = true;
          break;
      }

    } else {  // Inside a START, END pair.
      bool interleaved_task_detected = false;

      switch (event->type) {
        case TaskEvent::POST:
          if (event->i == current_task_i)
            spurious_event_found = true;
          break;
        case TaskEvent::START:
          interleaved_task_detected = true;
          break;
        case TaskEvent::END:
          if (event->i != current_task_i)
            interleaved_task_detected = true;
          else
            current_task_i = -1;
          break;
      }

      if (interleaved_task_detected) {
        return ::testing::AssertionFailure()
            << "Found event " << ::testing::PrintToString(*event)
            << " between START and END events for task " << current_task_i
            << "; event dump: " << ::testing::PrintToString(events);
      }
    }

    if (spurious_event_found) {
      const int event_i = event - events.begin();
      return ::testing::AssertionFailure()
          << "Spurious event " << ::testing::PrintToString(*event)
          << " at position " << event_i << "; event dump: "
          << ::testing::PrintToString(events);
    }
  }

  return ::testing::AssertionSuccess();
}

}  // namespace

::testing::AssertionResult CheckNonNestableInvariants(
    const std::vector<TaskEvent>& events,
    int task_count) {
  const std::vector<int> post_order =
      GetEventTypeOrder(events, TaskEvent::POST);
  const std::vector<int> start_order =
      GetEventTypeOrder(events, TaskEvent::START);
  const std::vector<int> end_order =
      GetEventTypeOrder(events, TaskEvent::END);

  if (start_order != post_order) {
    return ::testing::AssertionFailure()
        << "Expected START order (which equals actual POST order): \n"
        << ::testing::PrintToString(post_order)
        << "\n Actual START order:\n"
        << ::testing::PrintToString(start_order);
  }

  if (end_order != post_order) {
    return ::testing::AssertionFailure()
        << "Expected END order (which equals actual POST order): \n"
        << ::testing::PrintToString(post_order)
        << "\n Actual END order:\n"
        << ::testing::PrintToString(end_order);
  }

  const ::testing::AssertionResult result =
      CheckEventOrdersForEachTask(events, task_count);
  if (!result)
    return result;

  return CheckNoTaskRunsOverlap(events);
}

}  // namespace internal

}  // namespace base