//===- CorePerfTests.mm ---------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#import "llbuild/Commands/Commands.h"

#import "llbuild/Basic/ExecutionQueue.h"
#import "llbuild/Core/BuildEngine.h"

#import <XCTest/XCTest.h>

#import <functional>

using namespace llbuild;
using namespace llbuild::core;

@interface CorePerfTests : XCTestCase

@end

#pragma mark - Support Classes

namespace {

static int32_t IntFromValue(const core::ValueType& Value) {
  assert(Value.size() == 4);
  return ((Value[0] << 0) |
          (Value[1] << 8) |
          (Value[2] << 16) |
          (Value[3] << 24));
}
static core::ValueType IntToValue(int32_t Value) {
  std::vector<uint8_t> Result(4);
  Result[0] = (Value >> 0) & 0xFF;
  Result[1] = (Value >> 8) & 0xFF;
  Result[2] = (Value >> 16) & 0xFF;
  Result[3] = (Value >> 24) & 0xFF;
  return Result;
}

// Simple task implementation which takes a fixed set of dependencies, evaluates
// them all, and then provides the output.
//
// FIXME: This is copied from the Core BuildEngine unittest, we should figure
// out if it should be shared in a common build engine support library at some
// point.
class SimpleTask : public Task {
public:
  typedef std::function<int(const std::vector<int>&)> ComputeFnType;

private:
  std::vector<KeyType> Inputs;
  std::vector<int> InputValues;
  ComputeFnType Compute;

public:
  SimpleTask(const std::vector<KeyType>& Inputs, ComputeFnType Compute)
    : Inputs(Inputs), Compute(Compute)
  {
    InputValues.resize(Inputs.size());
  }

  virtual void start(TaskInterface ti) override {
    // Request all of the inputs.
    for (int i = 0, e = Inputs.size(); i != e; ++i) {
      ti.request(Inputs[i], i);
    }
  }

  virtual void provideValue(TaskInterface, uintptr_t InputID,
                            const KeyType& key, const ValueType& Value) override {
    // Update the input values.
    assert(InputID < InputValues.size());
    InputValues[InputID] = IntFromValue(Value);
  }

  virtual void inputsAvailable(TaskInterface ti) override {
      ti.complete(IntToValue(Compute(InputValues)));
  }
};

// Helper function for creating a simple action.
typedef std::function<Task*(BuildEngine&)> ActionFn;


class SimpleRule: public Rule {
public:
    typedef std::function<bool(const ValueType& value)> ValidFnType;

private:
    SimpleTask::ComputeFnType compute;
    std::vector<KeyType> inputs;
    ValidFnType valid;
public:
    SimpleRule(const KeyType& key, SimpleTask::ComputeFnType compute,
               const std::vector<KeyType>& inputs, ValidFnType valid = nullptr)
        : Rule(key), compute(compute), inputs(inputs), valid(valid) { }

    Task* createTask(BuildEngine&) override { return new SimpleTask(inputs, compute); }

    bool isResultValid(BuildEngine&, const ValueType& value) override {
        if (!valid) return true;
        return valid(value);
    }
};

}

@implementation CorePerfTests

#pragma mark - "buildengine ack" Performance Tests

- (void)measurePerformance:(std::function<void()>)body {
    [self measureBlock:^() {
        body();
    }];
}

- (void)testBuildEngineBasicPerf {
  // Test the timing of 'buildengine ack 3 14'.
  //
  // This test uses ~300k rules, and is a good stress test for the core engine
  // operation.

  [self measureBlock:^{
      llbuild::commands::executeBuildEngineCommand({
          "ack", "3", "14" });
    }];
}

- (void)testBuildEngineDependencyScanningCorePerf {
  // Test the timing of 'buildengine ack 3 11', with a high recompute count.
  //
  // This test uses ~40k rules, but then recomputes the results multiple times,
  // which is a stress test of the dependency scanning performance.

  [self measureBlock:^{
      llbuild::commands::executeBuildEngineCommand({
          "ack", "--recompute", "100", "3", "11" });
    }];
}

#pragma mark - Synthetic Graph Dependency Scanning Tests

- (void)testBuildEngineDependencyScanningOnLinearChain {
  // Test the scanning performance on a deep linear build graph of M nodes::
  //
  //   i1 -> i2 -> ... -> iM
  int M = 1000000; // Use a graph of 1 million nodes.

  // Set up the build rules.
  struct LinearDelegate : public BuildEngineDelegate, public basic::ExecutionQueueDelegate {
    virtual std::unique_ptr<core::Rule> lookupRule(const core::KeyType& Key) override {
      // We never expect dynamic rule lookup.
      fprintf(stderr, "error: unexpected rule lookup for \"%s\"\n",
              Key.c_str());
      abort();
      return nullptr;
    }
    virtual void cycleDetected(const std::vector<core::Rule*>& Cycle) override {
      // We never expect to find a cycle.
      fprintf(stderr, "error: unexpected cycle\n");
      abort();
    }

    virtual void error(const Twine& message) override {
      fprintf(stderr, "error: %s\n", message.str().c_str());
      abort();
    }

    void processStarted(basic::ProcessContext*, basic::ProcessHandle, llbuild_pid_t) override { }
    void processHadError(basic::ProcessContext*, basic::ProcessHandle, const Twine&) override { }
    void processHadOutput(basic::ProcessContext*, basic::ProcessHandle, StringRef) override { }
    void processFinished(basic::ProcessContext*, basic::ProcessHandle, const basic::ProcessResult&) override { }
    void queueJobStarted(basic::JobDescriptor*) override { }
    void queueJobFinished(basic::JobDescriptor*) override { }

    std::unique_ptr<basic::ExecutionQueue> createExecutionQueue() override {
    return createSerialQueue(*this, nullptr);
    }
  } Delegate;
  core::BuildEngine Engine(Delegate);

  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    char Name[32];
    snprintf(Name, sizeof(Name), "i%d", i);
    if (i != M) {
      char InputName[32];
      snprintf(InputName, sizeof(InputName), "i%d", i+1);
      Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(Name,
                                    [] (const std::vector<int>& Inputs) {
                                        return Inputs[0];
                                    },
                                    { InputName })));
    } else {
      Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(Name,
                       [&] (const std::vector<int>& Inputs) {
          return LastInputValue; }, {},
          [&](const ValueType& value) {
              return LastInputValue == IntFromValue(value);
          })));
    }
  }

  // Build the first result.
  LastInputValue = 42;
  auto Result = IntFromValue(Engine.build("i1"));
  (void)Result;
  assert(Result == LastInputValue);

  // Run a single initial null build to try and warm the timings below.
  Engine.build("i1");

  // Measure the null build time.
    [self measurePerformance: [&] {
      auto Result = IntFromValue(Engine.build("i1"));
      (void)Result;
      assert(Result == LastInputValue);
    }];
}

static int64_t i64pow(int64_t Value, int64_t Exponent) {
  int64_t Result = 1;
  for (int64_t i = 0; i != Exponent; ++i)
    Result *= Value;
  return Result;
}

- (void)testBuildEngineDependencyScanningOnNaryTree {
  // Test the scanning performance on an M-height N-ary tree with no sharing::
  //
  //   i1,1 ---> i2,1 ... ---> iM,1
  //         \-> i2,2       ...
  //         \-> i2,N          iM,{N**(M-1)}

  int M = 13, N = 3; // Use a graph of 797,161 nodes.
  int NumTotalNodes = (i64pow(N, M) - 1) / (N - 1);
  NSLog(@"running test with %d-ary tree of depth %d (%d nodes)\n",
         N, M, NumTotalNodes);

  // Set up the build rules.
  struct NaryTreeDelegate : public BuildEngineDelegate, public basic::ExecutionQueueDelegate {
    virtual std::unique_ptr<core::Rule> lookupRule(const core::KeyType& Key) override {
      // We never expect dynamic rule lookup.
      fprintf(stderr, "error: unexpected rule lookup for \"%s\"\n",
              Key.c_str());
      abort();
      return nullptr;
    }
    virtual void cycleDetected(const std::vector<core::Rule*>& Cycle) override {
      // We never expect to find a cycle.
      fprintf(stderr, "error: unexpected cycle\n");
      abort();
    }

    virtual void error(const Twine& message) override {
      fprintf(stderr, "error: %s\n", message.str().c_str());
      abort();
    }

    void processStarted(basic::ProcessContext*, basic::ProcessHandle, llbuild_pid_t) override { }
    void processHadError(basic::ProcessContext*, basic::ProcessHandle, const Twine&) override { }
    void processHadOutput(basic::ProcessContext*, basic::ProcessHandle, StringRef) override { }
    void processFinished(basic::ProcessContext*, basic::ProcessHandle, const basic::ProcessResult&) override { }
    void queueJobStarted(basic::JobDescriptor*) override { }
    void queueJobFinished(basic::JobDescriptor*) override { }

    std::unique_ptr<basic::ExecutionQueue> createExecutionQueue() override {
    return createSerialQueue(*this, nullptr);
    }
  } Delegate;
  core::BuildEngine Engine(Delegate);
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    // Compute the total number of groups at this depth.
    int NumNodes = i64pow(N, i - 1);
    for (int j = 1; j <= NumNodes; ++j) {
      char Name[32];
      snprintf(Name, sizeof(Name), "i%d,%d", i, j);
      if (i != M) {
        std::vector<KeyType> Inputs;
        for (int k = 1; k <= N; ++k) {
          char InputName[32];
          snprintf(InputName, sizeof(InputName), "i%d,%d", i+1, 1 + (j - 1)*N + (k - 1));
          Inputs.push_back(InputName);
        }
        Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(
            Name, [] (const std::vector<int>& Inputs) {
            return Inputs[0]; }, Inputs)));
      } else {
        Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(
            Name,
            [&] (const std::vector<int>& Inputs) {
            return LastInputValue; }, {},
            [&](const ValueType& value) {
                return LastInputValue == IntFromValue(value);
            })));
      }
    }
  }

  // Build the first result.
  LastInputValue = 42;
  auto Result = IntFromValue(Engine.build("i1,1"));
  (void)Result;
  assert(Result == LastInputValue);

  // Run a single initial null build to try and warm the timings below.
  Engine.build("i1,1");

  // Measure the null build time.
  [self measurePerformance: [&] {
      auto Result = IntFromValue(Engine.build("i1,1"));
      (void)Result;
      assert(Result == LastInputValue);
    }];
}

- (void)testBuildEngineDependencyScanningOn2DMatrix {
  // Test the scanning performance on a 2D {M+1}x{N+1} matrix where each node
  // depends on nodes which are adjacent above or to the right::
  //
  //   i1,N --> i2,N --> ... --> iM,N
  //    ^        ^       ...      ^
  //    |        |                |
  //   i1,2 --> i2,2 --> ... --> iM,2
  //    ^        ^       ...      ^
  //    |        |                |
  //   i1,1 --> i2,1 --> ... --> iM,1
  //
  // This is an easy to construct synthetic graph which is scalable and has
  // sharing.
  int M = 100, N = 100; // Use a graph of 1 million nodes.

  // Set up the build rules.
  struct MatrixDelegate : public BuildEngineDelegate, public basic::ExecutionQueueDelegate {
    virtual std::unique_ptr<core::Rule> lookupRule(const core::KeyType& Key) override {
      // We never expect dynamic rule lookup.
      fprintf(stderr, "error: unexpected rule lookup for \"%s\"\n",
              Key.c_str());
      abort();
      return nullptr;
    }
    virtual void cycleDetected(const std::vector<core::Rule*>& Cycle) override {
      // We never expect to find a cycle.
      fprintf(stderr, "error: unexpected cycle\n");
      abort();
    }

    virtual void error(const Twine& message) override {
      fprintf(stderr, "error: %s\n", message.str().c_str());
      abort();
    }

    void processStarted(basic::ProcessContext*, basic::ProcessHandle, llbuild_pid_t) override { }
    void processHadError(basic::ProcessContext*, basic::ProcessHandle, const Twine&) override { }
    void processHadOutput(basic::ProcessContext*, basic::ProcessHandle, StringRef) override { }
    void processFinished(basic::ProcessContext*, basic::ProcessHandle, const basic::ProcessResult&) override { }
    void queueJobStarted(basic::JobDescriptor*) override { }
    void queueJobFinished(basic::JobDescriptor*) override { }

    std::unique_ptr<basic::ExecutionQueue> createExecutionQueue() override {
    return createSerialQueue(*this, nullptr);
    }
  } Delegate;
  core::BuildEngine Engine(Delegate);
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    for (int j = 1; j <= N; ++j) {
      char Name[32];
      snprintf(Name, sizeof(Name), "i%d,%d", i, j);
      if (i != M && j != N) {
        // Nodes not on an edge.
        char InputAName[32];
        snprintf(InputAName, sizeof(InputAName), "i%d,%d", i+1, j);
        char InputBName[32];
        snprintf(InputBName, sizeof(InputBName), "i%d,%d", i, j+1);
        Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(
            Name, [] (const std::vector<int>& Inputs) { return Inputs[0]; }, { InputAName, InputBName })));
      } else if (i != M) {
        // Top edge.
        assert(j == N);
        char InputName[32];
        snprintf(InputName, sizeof(InputName), "i%d,%d", i+1, j);
        Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(
            Name, [] (const std::vector<int>& Inputs) { return Inputs[0]; }, { InputName })));
      } else if (j != N) {
        // Right edge.
        assert(i == M);
        char InputName[32];
        snprintf(InputName, sizeof(InputName), "i%d,%d", i, j+1);
        Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(
            Name, [] (const std::vector<int>& Inputs) { return Inputs[0]; }, { InputName })));
      } else {
        // Top-right corner node.
        assert(i == M && j == N);
        Engine.addRule(std::unique_ptr<core::Rule>(new SimpleRule(
            Name, [&] (const std::vector<int>& Inputs) { return LastInputValue; },
            {},
            [&](const ValueType& value) {
              return LastInputValue == IntFromValue(value);
            })));
      }
    }
  }

  // Build the first result.
  LastInputValue = 42;
  auto Result = IntFromValue(Engine.build("i1,1"));
  (void)Result;
  assert(Result == LastInputValue);

  // Run a single initial null build to try and warm the timings below.
  Engine.build("i1,1");

  // Measure the null build time.
  [self measurePerformance: [&] {
      auto Result = IntFromValue(Engine.build("i1,1"));
      (void)Result;
      assert(Result == LastInputValue);
    }];
}

@end