// Copyright 2012 The Chromium Authors
// 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,
    OnceClosure task) {
  AutoLock event_lock(lock_);
  const int post_i = next_post_i_++;
  auto wrapped_task =
      BindOnce(&SequencedTaskTracker::RunTask, this, std::move(task), post_i);
  task_runner->PostNonNestableTask(FROM_HERE, std::move(wrapped_task));
  TaskPosted(post_i);
}

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

void SequencedTaskTracker::PostWrappedDelayedNonNestableTask(
    SequencedTaskRunner* task_runner,
    OnceClosure task,
    TimeDelta delay) {
  AutoLock event_lock(lock_);
  const int post_i = next_post_i_++;
  auto wrapped_task =
      BindOnce(&SequencedTaskTracker::RunTask, this, std::move(task), post_i);
  task_runner->PostNonNestableDelayedTask(FROM_HERE, std::move(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, OnceClosure());
  }
}

void SequencedTaskTracker::RunTask(OnceClosure task, int task_i) {
  TaskStarted(task_i);
  if (!task.is_null()) {
    std::move(task).Run();
  }
  TaskEnded(task_i);
}

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

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

void SequencedTaskTracker::TaskEnded(int i) {
  AutoLock lock(lock_);
  events_.emplace_back(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

// This suite is instantiated in binaries that use //base:test_support.
GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(SequencedTaskRunnerTest);

}  // namespace base