/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing for details.  */
#include "cmCTestMultiProcessHandler.h"

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstddef> // IWYU pragma: keep
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <utility>
#include <vector>

#include <cm/memory>
#include <cmext/algorithm>

#include <cm3p/json/value.h>
#include <cm3p/json/writer.h>
#include <cm3p/uv.h>

#include "cmsys/FStream.hxx"
#include "cmsys/SystemInformation.hxx"

#include "cmAffinity.h"
#include "cmCTest.h"
#include "cmCTestBinPacker.h"
#include "cmCTestRunTest.h"
#include "cmCTestTestHandler.h"
#include "cmDuration.h"
#include "cmListFileCache.h"
#include "cmRange.h"
#include "cmStringAlgorithms.h"
#include "cmSystemTools.h"
#include "cmUVSignalHackRAII.h" // IWYU pragma: keep
#include "cmWorkingDirectory.h"

namespace cmsys {
class RegularExpression;
}

class TestComparator
{
public:
  TestComparator(cmCTestMultiProcessHandler* handler)
    : Handler(handler)
  {
  }

  // Sorts tests in descending order of cost
  bool operator()(int index1, int index2) const
  {
    return Handler->Properties[index1]->Cost >
      Handler->Properties[index2]->Cost;
  }

private:
  cmCTestMultiProcessHandler* Handler;
};

cmCTestMultiProcessHandler::cmCTestMultiProcessHandler()
{
  ParallelLevel = 1;
  TestLoad = 0;
  FakeLoadForTesting = 0;
  Completed = 0;
  RunningCount = 0;
  ProcessorsAvailable = cmAffinity::GetProcessorsAvailable();
  HaveAffinity = ProcessorsAvailable.size();
  HasCycles = false;
  SerialTestRunning = false;
}

cmCTestMultiProcessHandler::~cmCTestMultiProcessHandler() = default;

// Set the tests
void cmCTestMultiProcessHandler::SetTests(TestMap& tests,
                                          PropertiesMap& properties)
{
  Tests = tests;
  Properties = properties;
  Total = Tests.size();
  // set test run map to false for all
  for (auto const& t : Tests) {
    TestRunningMap[t.first] = false;
    TestFinishMap[t.first] = false;
  }
  if (!CTest->GetShowOnly()) {
    ReadCostData();
    HasCycles = !CheckCycles();
    if (HasCycles) {
      return;
    }
    CreateTestCostList();
  }
}

// Set the max number of tests that can be run at the same time.
void cmCTestMultiProcessHandler::SetParallelLevel(size_t level)
{
  ParallelLevel = level < 1 ? 1 : level;
}

void cmCTestMultiProcessHandler::SetTestLoad(unsigned long load)
{
  TestLoad = load;

  std::string fake_load_value;
  if (cmSystemTools::GetEnv("__CTEST_FAKE_LOAD_AVERAGE_FOR_TESTING",
                            fake_load_value)) {
    if (!cmStrToULong(fake_load_value, &FakeLoadForTesting)) {
      cmSystemTools::Error("Failed to parse fake load value: " +
                           fake_load_value);
    }
  }
}

void cmCTestMultiProcessHandler::RunTests()
{
  CheckResume();
  if (HasCycles) {
    return;
  }
#ifdef CMAKE_UV_SIGNAL_HACK
  cmUVSignalHackRAII hackRAII;
#endif
  TestHandler->SetMaxIndex(FindMaxIndex());

  uv_loop_init(&Loop);
  StartNextTests();
  uv_run(&Loop, UV_RUN_DEFAULT);
  uv_loop_close(&Loop);

  if (!StopTimePassed && !CheckStopOnFailure()) {
    assert(Completed == Total);
    assert(Tests.empty());
  }
  assert(AllResourcesAvailable());

  MarkFinished();
  UpdateCostData();
}

bool cmCTestMultiProcessHandler::StartTestProcess(int test)
{
  if (HaveAffinity && Properties[test]->WantAffinity) {
    size_t needProcessors = GetProcessorsUsed(test);
    if (needProcessors > ProcessorsAvailable.size()) {
      return false;
    }
    std::vector<size_t> affinity;
    affinity.reserve(needProcessors);
    for (size_t i = 0; i < needProcessors; ++i) {
      auto p = ProcessorsAvailable.begin();
      affinity.push_back(*p);
      ProcessorsAvailable.erase(p);
    }
    Properties[test]->Affinity = std::move(affinity);
  }

  cmCTestOptionalLog(CTest, HANDLER_VERBOSE_OUTPUT, "test " << test << "\n",
                     Quiet);
  TestRunningMap[test] = true; // mark the test as running
  // now remove the test itself
  EraseTest(test);
  RunningCount += GetProcessorsUsed(test);

  auto testRun = cm::make_unique<cmCTestRunTest>(*this);

  if (RepeatMode != cmCTest::Repeat::Never) {
    testRun->SetRepeatMode(RepeatMode);
    testRun->SetNumberOfRuns(RepeatCount);
  }
  testRun->SetIndex(test);
  testRun->SetTestProperties(Properties[test]);
  if (TestHandler->UseResourceSpec) {
    testRun->SetUseAllocatedResources(true);
    testRun->SetAllocatedResources(AllocatedResources[test]);
  }

  // Find any failed dependencies for this test. We assume the more common
  // scenario has no failed tests, so make it the outer loop.
  for (std::string const& f : *Failed) {
    if (cm::contains(Properties[test]->RequireSuccessDepends, f)) {
      testRun->AddFailedDependency(f);
    }
  }

  // Always lock the resources we'll be using, even if we fail to set the
  // working directory because FinishTestProcess() will try to unlock them
  LockResources(test);

  if (!ResourceAllocationErrors[test].empty()) {
    std::ostringstream e;
    e << "Insufficient resources for test " << Properties[test]->Name
      << ":\n\n";
    for (auto const& it : ResourceAllocationErrors[test]) {
      switch (it.second) {
        case ResourceAllocationError::NoResourceType:
          e << "  Test requested resources of type '" << it.first
            << "' which does not exist\n";
          break;

        case ResourceAllocationError::InsufficientResources:
          e << "  Test requested resources of type '" << it.first
            << "' in the following amounts:\n";
          for (auto const& group : Properties[test]->ResourceGroups) {
            for (auto const& requirement : group) {
              if (requirement.ResourceType == it.first) {
                e << "    " << requirement.SlotsNeeded
                  << (requirement.SlotsNeeded == 1 ? " slot\n" : " slots\n");
              }
            }
          }
          e << "  but only the following units were available:\n";
          for (auto const& res :
               ResourceAllocator.GetResources().at(it.first)) {
            e << "    '" << res.first << "': " << res.second.Total
              << (res.second.Total == 1 ? " slot\n" : " slots\n");
          }
          break;
      }
      e << "\n";
    }
    e << "Resource spec file:\n\n  " << TestHandler->ResourceSpecFile;
    cmCTestRunTest::StartFailure(std::move(testRun), e.str(),
                                 "Insufficient resources");
    return false;
  }

  cmWorkingDirectory workdir(Properties[test]->Directory);
  if (workdir.Failed()) {
    cmCTestRunTest::StartFailure(std::move(testRun),
                                 "Failed to change working directory to " +
                                   Properties[test]->Directory + " : " +
                                   std::strerror(workdir.GetLastResult()),
                                 "Failed to change working directory");
    return false;
  }

  // Ownership of 'testRun' has moved to another structure.
  // When the test finishes, FinishTestProcess will be called.
  return cmCTestRunTest::StartTest(std::move(testRun), Completed, Total);
}

bool cmCTestMultiProcessHandler::AllocateResources(int index)
{
  if (!TestHandler->UseResourceSpec) {
    return true;
  }

  std::map<std::string, std::vector<cmCTestBinPackerAllocation>> allocations;
  if (!TryAllocateResources(index, allocations)) {
    return false;
  }

  auto& allocatedResources = AllocatedResources[index];
  allocatedResources.resize(Properties[index]->ResourceGroups.size());
  for (auto const& it : allocations) {
    for (auto const& alloc : it.second) {
      bool result = ResourceAllocator.AllocateResource(it.first, alloc.Id,
                                                       alloc.SlotsNeeded);
      (void)result;
      assert(result);
      allocatedResources[alloc.ProcessIndex][it.first].push_back(
        { alloc.Id, static_cast<unsigned int>(alloc.SlotsNeeded) });
    }
  }

  return true;
}

bool cmCTestMultiProcessHandler::TryAllocateResources(
  int index,
  std::map<std::string, std::vector<cmCTestBinPackerAllocation>>& allocations,
  std::map<std::string, ResourceAllocationError>* errors)
{
  allocations.clear();

  std::size_t processIndex = 0;
  for (auto const& process : Properties[index]->ResourceGroups) {
    for (auto const& requirement : process) {
      for (int i = 0; i < requirement.UnitsNeeded; ++i) {
        allocations[requirement.ResourceType].push_back(
          { processIndex, requirement.SlotsNeeded, "" });
      }
    }
    ++processIndex;
  }

  bool result = true;
  auto const& availableResources = ResourceAllocator.GetResources();
  for (auto& it : allocations) {
    if (!availableResources.count(it.first)) {
      if (errors) {
        (*errors)[it.first] = ResourceAllocationError::NoResourceType;
        result = false;
      } else {
        return false;
      }
    } else if (!cmAllocateCTestResourcesRoundRobin(
                 availableResources.at(it.first), it.second)) {
      if (errors) {
        (*errors)[it.first] = ResourceAllocationError::InsufficientResources;
        result = false;
      } else {
        return false;
      }
    }
  }

  return result;
}

void cmCTestMultiProcessHandler::DeallocateResources(int index)
{
  if (!TestHandler->UseResourceSpec) {
    return;
  }

  {
    auto& allocatedResources = AllocatedResources[index];
    for (auto const& processAlloc : allocatedResources) {
      for (auto const& it : processAlloc) {
        auto resourceType = it.first;
        for (auto const& it2 : it.second) {
          bool success = ResourceAllocator.DeallocateResource(
            resourceType, it2.Id, it2.Slots);
          (void)success;
          assert(success);
        }
      }
    }
  }
  AllocatedResources.erase(index);
}

bool cmCTestMultiProcessHandler::AllResourcesAvailable()
{
  for (auto const& it : ResourceAllocator.GetResources()) {
    for (auto const& it2 : it.second) {
      if (it2.second.Locked != 0) {
        return false;
      }
    }
  }

  return true;
}

void cmCTestMultiProcessHandler::CheckResourcesAvailable()
{
  if (TestHandler->UseResourceSpec) {
    for (auto test : SortedTests) {
      std::map<std::string, std::vector<cmCTestBinPackerAllocation>>
        allocations;
      TryAllocateResources(test, allocations, &ResourceAllocationErrors[test]);
    }
  }
}

bool cmCTestMultiProcessHandler::CheckStopOnFailure()
{
  return CTest->GetStopOnFailure();
}

bool cmCTestMultiProcessHandler::CheckStopTimePassed()
{
  if (!StopTimePassed) {
    std::chrono::system_clock::time_point stop_time = CTest->GetStopTime();
    if (stop_time != std::chrono::system_clock::time_point() &&
        stop_time <= std::chrono::system_clock::now()) {
      SetStopTimePassed();
    }
  }
  return StopTimePassed;
}

void cmCTestMultiProcessHandler::SetStopTimePassed()
{
  if (!StopTimePassed) {
    cmCTestLog(CTest, ERROR_MESSAGE,
               "The stop time has been passed. "
               "Stopping all tests."
                 << std::endl);
    StopTimePassed = true;
  }
}

void cmCTestMultiProcessHandler::LockResources(int index)
{
  LockedResources.insert(Properties[index]->LockedResources.begin(),
                         Properties[index]->LockedResources.end());

  if (Properties[index]->RunSerial) {
    SerialTestRunning = true;
  }
}

void cmCTestMultiProcessHandler::UnlockResources(int index)
{
  for (std::string const& i : Properties[index]->LockedResources) {
    LockedResources.erase(i);
  }
  if (Properties[index]->RunSerial) {
    SerialTestRunning = false;
  }
}

void cmCTestMultiProcessHandler::EraseTest(int test)
{
  Tests.erase(test);
  SortedTests.erase(std::find(SortedTests.begin(), SortedTests.end(), test));
}

inline size_t cmCTestMultiProcessHandler::GetProcessorsUsed(int test)
{
  size_t processors = static_cast<int>(Properties[test]->Processors);
  // If processors setting is set higher than the -j
  // setting, we default to using all of the process slots.
  if (processors > ParallelLevel) {
    processors = ParallelLevel;
  }
  // Cap tests that want affinity to the maximum affinity available.
  if (HaveAffinity && processors > HaveAffinity &&
      Properties[test]->WantAffinity) {
    processors = HaveAffinity;
  }
  return processors;
}

std::string cmCTestMultiProcessHandler::GetName(int test)
{
  return Properties[test]->Name;
}

bool cmCTestMultiProcessHandler::StartTest(int test)
{
  // Check for locked resources
  for (std::string const& i : Properties[test]->LockedResources) {
    if (cm::contains(LockedResources, i)) {
      return false;
    }
  }

  // Allocate resources
  if (ResourceAllocationErrors[test].empty() && !AllocateResources(test)) {
    DeallocateResources(test);
    return false;
  }

  // if there are no depends left then run this test
  if (Tests[test].empty()) {
    return StartTestProcess(test);
  }
  // This test was not able to start because it is waiting
  // on depends to run
  DeallocateResources(test);
  return false;
}

void cmCTestMultiProcessHandler::StartNextTests()
{
  if (TestLoadRetryTimer.get() != nullptr) {
    // This timer may be waiting to call StartNextTests again.
    // Since we have been called it is no longer needed.
    uv_timer_stop(TestLoadRetryTimer);
  }

  if (Tests.empty()) {
    TestLoadRetryTimer.reset();
    return;
  }

  if (CheckStopTimePassed()) {
    return;
  }

  if (CheckStopOnFailure() && !Failed->empty()) {
    return;
  }

  size_t numToStart = 0;

  if (RunningCount < ParallelLevel) {
    numToStart = ParallelLevel - RunningCount;
  }

  if (numToStart == 0) {
    return;
  }

  // Don't start any new tests if one with the RUN_SERIAL property
  // is already running.
  if (SerialTestRunning) {
    return;
  }

  bool allTestsFailedTestLoadCheck = false;
  size_t minProcessorsRequired = ParallelLevel;
  std::string testWithMinProcessors;

  cmsys::SystemInformation info;

  unsigned long systemLoad = 0;
  size_t spareLoad = 0;
  if (TestLoad > 0) {
    // Activate possible wait.
    allTestsFailedTestLoadCheck = true;

    // Check for a fake load average value used in testing.
    if (FakeLoadForTesting > 0) {
      systemLoad = FakeLoadForTesting;
      // Drop the fake load for the next iteration to a value low enough
      // that the next iteration will start tests.
      FakeLoadForTesting = 1;
    }
    // If it's not set, look up the true load average.
    else {
      systemLoad = static_cast<unsigned long>(ceil(info.GetLoadAverage()));
    }
    spareLoad = (TestLoad > systemLoad ? TestLoad - systemLoad : 0);

    // Don't start more tests than the spare load can support.
    if (numToStart > spareLoad) {
      numToStart = spareLoad;
    }
  }

  TestList copy = SortedTests;
  for (auto const& test : copy) {
    // Take a nap if we're currently performing a RUN_SERIAL test.
    if (SerialTestRunning) {
      break;
    }
    // We can only start a RUN_SERIAL test if no other tests are also
    // running.
    if (Properties[test]->RunSerial && RunningCount > 0) {
      continue;
    }

    size_t processors = GetProcessorsUsed(test);
    bool testLoadOk = true;
    if (TestLoad > 0) {
      if (processors <= spareLoad) {
        cmCTestLog(CTest, DEBUG,
                   "OK to run " << GetName(test) << ", it requires "
                                << processors << " procs & system load is: "
                                << systemLoad << std::endl);
        allTestsFailedTestLoadCheck = false;
      } else {
        testLoadOk = false;
      }
    }

    if (processors <= minProcessorsRequired) {
      minProcessorsRequired = processors;
      testWithMinProcessors = GetName(test);
    }

    if (testLoadOk && processors <= numToStart && StartTest(test)) {
      numToStart -= processors;
    } else if (numToStart == 0) {
      break;
    }
  }

  if (allTestsFailedTestLoadCheck) {
    // Find out whether there are any non RUN_SERIAL tests left, so that the
    // correct warning may be displayed.
    bool onlyRunSerialTestsLeft = true;
    for (auto const& test : copy) {
      if (!Properties[test]->RunSerial) {
        onlyRunSerialTestsLeft = false;
      }
    }
    cmCTestLog(CTest, HANDLER_OUTPUT, "***** WAITING, ");

    if (SerialTestRunning) {
      cmCTestLog(CTest, HANDLER_OUTPUT,
                 "Waiting for RUN_SERIAL test to finish.");
    } else if (onlyRunSerialTestsLeft) {
      cmCTestLog(CTest, HANDLER_OUTPUT,
                 "Only RUN_SERIAL tests remain, awaiting available slot.");
    } else {
      /* clang-format off */
      cmCTestLog(CTest, HANDLER_OUTPUT,
                 "System Load: " << systemLoad << ", "
                 "Max Allowed Load: " << TestLoad << ", "
                 "Smallest test " << testWithMinProcessors <<
                 " requires " << minProcessorsRequired);
      /* clang-format on */
    }
    cmCTestLog(CTest, HANDLER_OUTPUT, "*****" << std::endl);

    // Wait between 1 and 5 seconds before trying again.
    unsigned int milliseconds = (cmSystemTools::RandomSeed() % 5 + 1) * 1000;
    if (FakeLoadForTesting) {
      milliseconds = 10;
    }
    if (TestLoadRetryTimer.get() == nullptr) {
      TestLoadRetryTimer.init(Loop, this);
    }
    TestLoadRetryTimer.start(&cmCTestMultiProcessHandler::OnTestLoadRetryCB,
                             milliseconds, 0);
  }
}

void cmCTestMultiProcessHandler::OnTestLoadRetryCB(uv_timer_t* timer)
{
  auto self = static_cast<cmCTestMultiProcessHandler*>(timer->data);
  self->StartNextTests();
}

void cmCTestMultiProcessHandler::FinishTestProcess(
  std::unique_ptr<cmCTestRunTest> runner, bool started)
{
  Completed++;

  int test = runner->GetIndex();
  auto properties = runner->GetTestProperties();

  bool testResult = runner->EndTest(Completed, Total, started);
  if (runner->TimedOutForStopTime()) {
    SetStopTimePassed();
  }
  if (started) {
    if (!StopTimePassed &&
        cmCTestRunTest::StartAgain(std::move(runner), Completed)) {
      Completed--; // remove the completed test because run again
      return;
    }
  }

  if (testResult) {
    Passed->push_back(properties->Name);
  } else if (!properties->Disabled) {
    Failed->push_back(properties->Name);
  }

  for (auto& t : Tests) {
    t.second.erase(test);
  }

  TestFinishMap[test] = true;
  TestRunningMap[test] = false;
  WriteCheckpoint(test);
  DeallocateResources(test);
  UnlockResources(test);
  RunningCount -= GetProcessorsUsed(test);

  for (auto p : properties->Affinity) {
    ProcessorsAvailable.insert(p);
  }
  properties->Affinity.clear();

  runner.reset();
  if (started) {
    StartNextTests();
  }
}

void cmCTestMultiProcessHandler::UpdateCostData()
{
  std::string fname = CTest->GetCostDataFile();
  std::string tmpout = fname + ".tmp";
  cmsys::ofstream fout;
  fout.open(tmpout.c_str());

  PropertiesMap temp = Properties;

  if (cmSystemTools::FileExists(fname)) {
    cmsys::ifstream fin;
    fin.open(fname.c_str());

    std::string line;
    while (std::getline(fin, line)) {
      if (line == "---") {
        break;
      }
      std::vector<std::string> parts = cmSystemTools::SplitString(line, ' ');
      // Format: <name> <previous_runs> <avg_cost>
      if (parts.size() < 3) {
        break;
      }

      std::string name = parts[0];
      int prev = atoi(parts[1].c_str());
      float cost = static_cast<float>(atof(parts[2].c_str()));

      int index = SearchByName(name);
      if (index == -1) {
        // This test is not in memory. We just rewrite the entry
        fout << name << " " << prev << " " << cost << "\n";
      } else {
        // Update with our new average cost
        fout << name << " " << Properties[index]->PreviousRuns << " "
             << Properties[index]->Cost << "\n";
        temp.erase(index);
      }
    }
    fin.close();
    cmSystemTools::RemoveFile(fname);
  }

  // Add all tests not previously listed in the file
  for (auto const& i : temp) {
    fout << i.second->Name << " " << i.second->PreviousRuns << " "
         << i.second->Cost << "\n";
  }

  // Write list of failed tests
  fout << "---\n";
  for (std::string const& f : *Failed) {
    fout << f << "\n";
  }
  fout.close();
  cmSystemTools::RenameFile(tmpout, fname);
}

void cmCTestMultiProcessHandler::ReadCostData()
{
  std::string fname = CTest->GetCostDataFile();

  if (cmSystemTools::FileExists(fname, true)) {
    cmsys::ifstream fin;
    fin.open(fname.c_str());
    std::string line;
    while (std::getline(fin, line)) {
      if (line == "---") {
        break;
      }

      std::vector<std::string> parts = cmSystemTools::SplitString(line, ' ');

      // Probably an older version of the file, will be fixed next run
      if (parts.size() < 3) {
        fin.close();
        return;
      }

      std::string name = parts[0];
      int prev = atoi(parts[1].c_str());
      float cost = static_cast<float>(atof(parts[2].c_str()));

      int index = SearchByName(name);
      if (index == -1) {
        continue;
      }

      Properties[index]->PreviousRuns = prev;
      // When not running in parallel mode, don't use cost data
      if (ParallelLevel > 1 && Properties[index] &&
          Properties[index]->Cost == 0) {
        Properties[index]->Cost = cost;
      }
    }
    // Next part of the file is the failed tests
    while (std::getline(fin, line)) {
      if (!line.empty()) {
        LastTestsFailed.push_back(line);
      }
    }
    fin.close();
  }
}

int cmCTestMultiProcessHandler::SearchByName(std::string const& name)
{
  int index = -1;

  for (auto const& p : Properties) {
    if (p.second->Name == name) {
      index = p.first;
    }
  }
  return index;
}

void cmCTestMultiProcessHandler::CreateTestCostList()
{
  if (ParallelLevel > 1) {
    CreateParallelTestCostList();
  } else {
    CreateSerialTestCostList();
  }
}

void cmCTestMultiProcessHandler::CreateParallelTestCostList()
{
  TestSet alreadySortedTests;

  std::list<TestSet> priorityStack;
  priorityStack.emplace_back();
  TestSet& topLevel = priorityStack.back();

  // In parallel test runs add previously failed tests to the front
  // of the cost list and queue other tests for further sorting
  for (auto const& t : Tests) {
    if (cm::contains(LastTestsFailed, Properties[t.first]->Name)) {
      // If the test failed last time, it should be run first.
      SortedTests.push_back(t.first);
      alreadySortedTests.insert(t.first);
    } else {
      topLevel.insert(t.first);
    }
  }

  // In parallel test runs repeatedly move dependencies of the tests on
  // the current dependency level to the next level until no
  // further dependencies exist.
  while (!priorityStack.back().empty()) {
    TestSet& previousSet = priorityStack.back();
    priorityStack.emplace_back();
    TestSet& currentSet = priorityStack.back();

    for (auto const& i : previousSet) {
      TestSet const& dependencies = Tests[i];
      currentSet.insert(dependencies.begin(), dependencies.end());
    }

    for (auto const& i : currentSet) {
      previousSet.erase(i);
    }
  }

  // Remove the empty dependency level
  priorityStack.pop_back();

  // Reverse iterate over the different dependency levels (deepest first).
  // Sort tests within each level by COST and append them to the cost list.
  for (TestSet const& currentSet : cmReverseRange(priorityStack)) {
    TestList sortedCopy;
    cm::append(sortedCopy, currentSet);
    std::stable_sort(sortedCopy.begin(), sortedCopy.end(),
                     TestComparator(this));

    for (auto const& j : sortedCopy) {
      if (!cm::contains(alreadySortedTests, j)) {
        SortedTests.push_back(j);
        alreadySortedTests.insert(j);
      }
    }
  }
}

void cmCTestMultiProcessHandler::GetAllTestDependencies(int test,
                                                        TestList& dependencies)
{
  TestSet const& dependencySet = Tests[test];
  for (int i : dependencySet) {
    GetAllTestDependencies(i, dependencies);
    dependencies.push_back(i);
  }
}

void cmCTestMultiProcessHandler::CreateSerialTestCostList()
{
  TestList presortedList;

  for (auto const& i : Tests) {
    presortedList.push_back(i.first);
  }

  std::stable_sort(presortedList.begin(), presortedList.end(),
                   TestComparator(this));

  TestSet alreadySortedTests;

  for (int test : presortedList) {
    if (cm::contains(alreadySortedTests, test)) {
      continue;
    }

    TestList dependencies;
    GetAllTestDependencies(test, dependencies);

    for (int testDependency : dependencies) {
      if (!cm::contains(alreadySortedTests, testDependency)) {
        alreadySortedTests.insert(testDependency);
        SortedTests.push_back(testDependency);
      }
    }

    alreadySortedTests.insert(test);
    SortedTests.push_back(test);
  }
}

void cmCTestMultiProcessHandler::WriteCheckpoint(int index)
{
  std::string fname =
    CTest->GetBinaryDir() + "/Testing/Temporary/CTestCheckpoint.txt";
  cmsys::ofstream fout;
  fout.open(fname.c_str(), std::ios::app);
  fout << index << "\n";
  fout.close();
}

void cmCTestMultiProcessHandler::MarkFinished()
{
  std::string fname =
    CTest->GetBinaryDir() + "/Testing/Temporary/CTestCheckpoint.txt";
  cmSystemTools::RemoveFile(fname);
}

static Json::Value DumpToJsonArray(const std::set<std::string>& values)
{
  Json::Value jsonArray = Json::arrayValue;
  for (auto& it : values) {
    jsonArray.append(it);
  }
  return jsonArray;
}

static Json::Value DumpToJsonArray(const std::vector<std::string>& values)
{
  Json::Value jsonArray = Json::arrayValue;
  for (auto& it : values) {
    jsonArray.append(it);
  }
  return jsonArray;
}

static Json::Value DumpRegExToJsonArray(
  const std::vector<std::pair<cmsys::RegularExpression, std::string>>& values)
{
  Json::Value jsonArray = Json::arrayValue;
  for (auto& it : values) {
    jsonArray.append(it.second);
  }
  return jsonArray;
}

static Json::Value DumpMeasurementToJsonArray(
  const std::map<std::string, std::string>& values)
{
  Json::Value jsonArray = Json::arrayValue;
  for (auto& it : values) {
    Json::Value measurement = Json::objectValue;
    measurement["measurement"] = it.first;
    measurement["value"] = it.second;
    jsonArray.append(measurement);
  }
  return jsonArray;
}

static Json::Value DumpTimeoutAfterMatch(
  cmCTestTestHandler::cmCTestTestProperties& testProperties)
{
  Json::Value timeoutAfterMatch = Json::objectValue;
  timeoutAfterMatch["timeout"] = testProperties.AlternateTimeout.count();
  timeoutAfterMatch["regex"] =
    DumpRegExToJsonArray(testProperties.TimeoutRegularExpressions);
  return timeoutAfterMatch;
}

static Json::Value DumpResourceGroupsToJsonArray(
  const std::vector<
    std::vector<cmCTestTestHandler::cmCTestTestResourceRequirement>>&
    resourceGroups)
{
  Json::Value jsonResourceGroups = Json::arrayValue;
  for (auto const& it : resourceGroups) {
    Json::Value jsonResourceGroup = Json::objectValue;
    Json::Value requirements = Json::arrayValue;
    for (auto const& it2 : it) {
      Json::Value res = Json::objectValue;
      res[".type"] = it2.ResourceType;
      // res[".units"] = it2.UnitsNeeded; // Intentionally commented out
      res["slots"] = it2.SlotsNeeded;
      requirements.append(res);
    }
    jsonResourceGroup["requirements"] = requirements;
    jsonResourceGroups.append(jsonResourceGroup);
  }
  return jsonResourceGroups;
}

static Json::Value DumpCTestProperty(std::string const& name,
                                     Json::Value value)
{
  Json::Value property = Json::objectValue;
  property["name"] = name;
  property["value"] = std::move(value);
  return property;
}

static Json::Value DumpCTestProperties(
  cmCTestTestHandler::cmCTestTestProperties& testProperties)
{
  Json::Value properties = Json::arrayValue;
  if (!testProperties.AttachOnFail.empty()) {
    properties.append(DumpCTestProperty(
      "ATTACHED_FILES_ON_FAIL", DumpToJsonArray(testProperties.AttachOnFail)));
  }
  if (!testProperties.AttachedFiles.empty()) {
    properties.append(DumpCTestProperty(
      "ATTACHED_FILES", DumpToJsonArray(testProperties.AttachedFiles)));
  }
  if (testProperties.Cost != 0.0f) {
    properties.append(
      DumpCTestProperty("COST", static_cast<double>(testProperties.Cost)));
  }
  if (!testProperties.Depends.empty()) {
    properties.append(
      DumpCTestProperty("DEPENDS", DumpToJsonArray(testProperties.Depends)));
  }
  if (testProperties.Disabled) {
    properties.append(DumpCTestProperty("DISABLED", testProperties.Disabled));
  }
  if (!testProperties.Environment.empty()) {
    properties.append(DumpCTestProperty(
      "ENVIRONMENT", DumpToJsonArray(testProperties.Environment)));
  }
  if (!testProperties.ErrorRegularExpressions.empty()) {
    properties.append(DumpCTestProperty(
      "FAIL_REGULAR_EXPRESSION",
      DumpRegExToJsonArray(testProperties.ErrorRegularExpressions)));
  }
  if (!testProperties.SkipRegularExpressions.empty()) {
    properties.append(DumpCTestProperty(
      "SKIP_REGULAR_EXPRESSION",
      DumpRegExToJsonArray(testProperties.SkipRegularExpressions)));
  }
  if (!testProperties.FixturesCleanup.empty()) {
    properties.append(DumpCTestProperty(
      "FIXTURES_CLEANUP", DumpToJsonArray(testProperties.FixturesCleanup)));
  }
  if (!testProperties.FixturesRequired.empty()) {
    properties.append(DumpCTestProperty(
      "FIXTURES_REQUIRED", DumpToJsonArray(testProperties.FixturesRequired)));
  }
  if (!testProperties.FixturesSetup.empty()) {
    properties.append(DumpCTestProperty(
      "FIXTURES_SETUP", DumpToJsonArray(testProperties.FixturesSetup)));
  }
  if (!testProperties.Labels.empty()) {
    properties.append(
      DumpCTestProperty("LABELS", DumpToJsonArray(testProperties.Labels)));
  }
  if (!testProperties.Measurements.empty()) {
    properties.append(DumpCTestProperty(
      "MEASUREMENT", DumpMeasurementToJsonArray(testProperties.Measurements)));
  }
  if (!testProperties.RequiredRegularExpressions.empty()) {
    properties.append(DumpCTestProperty(
      "PASS_REGULAR_EXPRESSION",
      DumpRegExToJsonArray(testProperties.RequiredRegularExpressions)));
  }
  if (!testProperties.ResourceGroups.empty()) {
    properties.append(DumpCTestProperty(
      "RESOURCE_GROUPS",
      DumpResourceGroupsToJsonArray(testProperties.ResourceGroups)));
  }
  if (testProperties.WantAffinity) {
    properties.append(
      DumpCTestProperty("PROCESSOR_AFFINITY", testProperties.WantAffinity));
  }
  if (testProperties.Processors != 1) {
    properties.append(
      DumpCTestProperty("PROCESSORS", testProperties.Processors));
  }
  if (!testProperties.RequiredFiles.empty()) {
    properties.append(DumpCTestProperty(
      "REQUIRED_FILES", DumpToJsonArray(testProperties.RequiredFiles)));
  }
  if (!testProperties.LockedResources.empty()) {
    properties.append(DumpCTestProperty(
      "RESOURCE_LOCK", DumpToJsonArray(testProperties.LockedResources)));
  }
  if (testProperties.RunSerial) {
    properties.append(
      DumpCTestProperty("RUN_SERIAL", testProperties.RunSerial));
  }
  if (testProperties.SkipReturnCode != -1) {
    properties.append(
      DumpCTestProperty("SKIP_RETURN_CODE", testProperties.SkipReturnCode));
  }
  if (testProperties.ExplicitTimeout) {
    properties.append(
      DumpCTestProperty("TIMEOUT", testProperties.Timeout.count()));
  }
  if (!testProperties.TimeoutRegularExpressions.empty()) {
    properties.append(DumpCTestProperty(
      "TIMEOUT_AFTER_MATCH", DumpTimeoutAfterMatch(testProperties)));
  }
  if (testProperties.WillFail) {
    properties.append(DumpCTestProperty("WILL_FAIL", testProperties.WillFail));
  }
  if (!testProperties.Directory.empty()) {
    properties.append(
      DumpCTestProperty("WORKING_DIRECTORY", testProperties.Directory));
  }
  return properties;
}

class BacktraceData
{
  std::unordered_map<std::string, Json::ArrayIndex> CommandMap;
  std::unordered_map<std::string, Json::ArrayIndex> FileMap;
  std::unordered_map<cmListFileContext const*, Json::ArrayIndex> NodeMap;
  Json::Value Commands = Json::arrayValue;
  Json::Value Files = Json::arrayValue;
  Json::Value Nodes = Json::arrayValue;

  Json::ArrayIndex AddCommand(std::string const& command)
  {
    auto i = CommandMap.find(command);
    if (i == CommandMap.end()) {
      i = CommandMap.emplace(command, Commands.size()).first;
      Commands.append(command);
    }
    return i->second;
  }

  Json::ArrayIndex AddFile(std::string const& file)
  {
    auto i = FileMap.find(file);
    if (i == FileMap.end()) {
      i = FileMap.emplace(file, Files.size()).first;
      Files.append(file);
    }
    return i->second;
  }

public:
  bool Add(cmListFileBacktrace const& bt, Json::ArrayIndex& index);
  Json::Value Dump();
};

bool BacktraceData::Add(cmListFileBacktrace const& bt, Json::ArrayIndex& index)
{
  if (bt.Empty()) {
    return false;
  }
  cmListFileContext const* top = &bt.Top();
  auto found = NodeMap.find(top);
  if (found != NodeMap.end()) {
    index = found->second;
    return true;
  }
  Json::Value entry = Json::objectValue;
  entry["file"] = AddFile(top->FilePath);
  if (top->Line) {
    entry["line"] = static_cast<int>(top->Line);
  }
  if (!top->Name.empty()) {
    entry["command"] = AddCommand(top->Name);
  }
  Json::ArrayIndex parent;
  if (Add(bt.Pop(), parent)) {
    entry["parent"] = parent;
  }
  index = NodeMap[top] = Nodes.size();
  this->Nodes.append(std::move(entry)); // NOLINT(*)
  return true;
}

Json::Value BacktraceData::Dump()
{
  Json::Value backtraceGraph;
  CommandMap.clear();
  FileMap.clear();
  NodeMap.clear();
  backtraceGraph["commands"] = std::move(Commands);
  backtraceGraph["files"] = std::move(Files);
  backtraceGraph["nodes"] = std::move(Nodes);
  return backtraceGraph;
}

static void AddBacktrace(BacktraceData& backtraceGraph, Json::Value& object,
                         cmListFileBacktrace const& bt)
{
  Json::ArrayIndex backtrace;
  if (backtraceGraph.Add(bt, backtrace)) {
    object["backtrace"] = backtrace;
  }
}

static Json::Value DumpCTestInfo(
  cmCTestRunTest& testRun,
  cmCTestTestHandler::cmCTestTestProperties& testProperties,
  BacktraceData& backtraceGraph)
{
  Json::Value testInfo = Json::objectValue;
  // test name should always be present
  testInfo["name"] = testProperties.Name;
  std::string const& config = testRun.GetCTest()->GetConfigType();
  if (!config.empty()) {
    testInfo["config"] = config;
  }
  std::string const& command = testRun.GetActualCommand();
  if (!command.empty()) {
    std::vector<std::string> commandAndArgs;
    commandAndArgs.push_back(command);
    const std::vector<std::string>& args = testRun.GetArguments();
    if (!args.empty()) {
      commandAndArgs.reserve(args.size() + 1);
      cm::append(commandAndArgs, args);
    }
    testInfo["command"] = DumpToJsonArray(commandAndArgs);
  }
  Json::Value properties = DumpCTestProperties(testProperties);
  if (!properties.empty()) {
    testInfo["properties"] = properties;
  }
  if (!testProperties.Backtrace.Empty()) {
    AddBacktrace(backtraceGraph, testInfo, testProperties.Backtrace);
  }
  return testInfo;
}

static Json::Value DumpVersion(int major, int minor)
{
  Json::Value version = Json::objectValue;
  version["major"] = major;
  version["minor"] = minor;
  return version;
}

void cmCTestMultiProcessHandler::PrintOutputAsJson()
{
  TestHandler->SetMaxIndex(FindMaxIndex());

  Json::Value result = Json::objectValue;
  result["kind"] = "ctestInfo";
  result["version"] = DumpVersion(1, 0);

  BacktraceData backtraceGraph;
  Json::Value tests = Json::arrayValue;
  for (auto& it : Properties) {
    cmCTestTestHandler::cmCTestTestProperties& p = *it.second;

    // Don't worry if this fails, we are only showing the test list, not
    // running the tests
    cmWorkingDirectory workdir(p.Directory);
    cmCTestRunTest testRun(*this);
    testRun.SetIndex(p.Index);
    testRun.SetTestProperties(&p);
    testRun.ComputeArguments();

    // Skip tests not available in this configuration.
    if (p.Args.size() >= 2 && p.Args[1] == "NOT_AVAILABLE") {
      continue;
    }

    Json::Value testInfo = DumpCTestInfo(testRun, p, backtraceGraph);
    tests.append(testInfo);
  }
  result["backtraceGraph"] = backtraceGraph.Dump();
  result["tests"] = std::move(tests);

  Json::StreamWriterBuilder builder;
  builder["indentation"] = "  ";
  std::unique_ptr<Json::StreamWriter> jout(builder.newStreamWriter());
  jout->write(result, &std::cout);
}

// For ShowOnly mode
void cmCTestMultiProcessHandler::PrintTestList()
{
  if (CTest->GetOutputAsJson()) {
    PrintOutputAsJson();
    return;
  }

  TestHandler->SetMaxIndex(FindMaxIndex());
  int count = 0;

  for (auto& it : Properties) {
    count++;
    cmCTestTestHandler::cmCTestTestProperties& p = *it.second;

    // Don't worry if this fails, we are only showing the test list, not
    // running the tests
    cmWorkingDirectory workdir(p.Directory);

    cmCTestRunTest testRun(*this);
    testRun.SetIndex(p.Index);
    testRun.SetTestProperties(&p);
    testRun.ComputeArguments(); // logs the command in verbose mode

    if (!p.Labels.empty()) // print the labels
    {
      cmCTestOptionalLog(CTest, HANDLER_VERBOSE_OUTPUT, "Labels:", Quiet);
    }
    for (std::string const& label : p.Labels) {
      cmCTestOptionalLog(CTest, HANDLER_VERBOSE_OUTPUT, " " << label, Quiet);
    }
    if (!p.Labels.empty()) // print the labels
    {
      cmCTestOptionalLog(CTest, HANDLER_VERBOSE_OUTPUT, std::endl, Quiet);
    }

    if (TestHandler->MemCheck) {
      cmCTestOptionalLog(CTest, HANDLER_OUTPUT, "  Memory Check", Quiet);
    } else {
      cmCTestOptionalLog(CTest, HANDLER_OUTPUT, "  Test", Quiet);
    }
    std::ostringstream indexStr;
    indexStr << " #" << p.Index << ":";
    cmCTestOptionalLog(CTest, HANDLER_OUTPUT,
                       std::setw(3 + getNumWidth(TestHandler->GetMaxIndex()))
                         << indexStr.str(),
                       Quiet);
    cmCTestOptionalLog(CTest, HANDLER_OUTPUT, " " << p.Name, Quiet);
    if (p.Disabled) {
      cmCTestOptionalLog(CTest, HANDLER_OUTPUT, " (Disabled)", Quiet);
    }
    cmCTestOptionalLog(CTest, HANDLER_OUTPUT, std::endl, Quiet);
  }

  cmCTestOptionalLog(CTest, HANDLER_OUTPUT,
                     std::endl
                       << "Total Tests: " << Total << std::endl,
                     Quiet);
}

void cmCTestMultiProcessHandler::PrintLabels()
{
  std::set<std::string> allLabels;
  for (auto& it : Properties) {
    cmCTestTestHandler::cmCTestTestProperties& p = *it.second;
    allLabels.insert(p.Labels.begin(), p.Labels.end());
  }

  if (!allLabels.empty()) {
    cmCTestOptionalLog(CTest, HANDLER_OUTPUT, "All Labels:" << std::endl,
                       Quiet);
  } else {
    cmCTestOptionalLog(CTest, HANDLER_OUTPUT, "No Labels Exist" << std::endl,
                       Quiet);
  }
  for (std::string const& label : allLabels) {
    cmCTestOptionalLog(CTest, HANDLER_OUTPUT, "  " << label << std::endl,
                       Quiet);
  }
}

void cmCTestMultiProcessHandler::CheckResume()
{
  std::string fname =
    CTest->GetBinaryDir() + "/Testing/Temporary/CTestCheckpoint.txt";
  if (CTest->GetFailover()) {
    if (cmSystemTools::FileExists(fname, true)) {
      *TestHandler->LogFile
        << "Resuming previously interrupted test set" << std::endl
        << "----------------------------------------------------------"
        << std::endl;

      cmsys::ifstream fin;
      fin.open(fname.c_str());
      std::string line;
      while (std::getline(fin, line)) {
        int index = atoi(line.c_str());
        RemoveTest(index);
      }
      fin.close();
    }
  } else if (cmSystemTools::FileExists(fname, true)) {
    cmSystemTools::RemoveFile(fname);
  }
}

void cmCTestMultiProcessHandler::RemoveTest(int index)
{
  EraseTest(index);
  Properties.erase(index);
  TestRunningMap[index] = false;
  TestFinishMap[index] = true;
  Completed++;
}

int cmCTestMultiProcessHandler::FindMaxIndex()
{
  int max = 0;
  for (auto const& i : Tests) {
    if (i.first > max) {
      max = i.first;
    }
  }
  return max;
}

// Returns true if no cycles exist in the dependency graph
bool cmCTestMultiProcessHandler::CheckCycles()
{
  cmCTestOptionalLog(CTest, HANDLER_VERBOSE_OUTPUT,
                     "Checking test dependency graph..." << std::endl, Quiet);
  for (auto const& it : Tests) {
    // DFS from each element to itself
    int root = it.first;
    std::set<int> visited;
    std::stack<int> s;
    s.push(root);
    while (!s.empty()) {
      int test = s.top();
      s.pop();
      if (visited.insert(test).second) {
        for (auto const& d : Tests[test]) {
          if (d == root) {
            // cycle exists
            cmCTestLog(
              CTest, ERROR_MESSAGE,
              "Error: a cycle exists in the test dependency graph "
              "for the test \""
                << Properties[root]->Name
                << "\".\nPlease fix the cycle and run ctest again.\n");
            return false;
          }
          s.push(d);
        }
      }
    }
  }
  cmCTestOptionalLog(CTest, HANDLER_VERBOSE_OUTPUT,
                     "Checking test dependency graph end" << std::endl, Quiet);
  return true;
}
