//===- 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/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(BuildEngine& Engine) override {
    // Request all of the inputs.
    for (int i = 0, e = Inputs.size(); i != e; ++i) {
      Engine.taskNeedsInput(this, Inputs[i], i);
    }
  }

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

  virtual void inputsAvailable(core::BuildEngine& Engine) override {
      Engine.taskIsComplete(this, IntToValue(Compute(InputValues)));
  }
};

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

static ActionFn simpleAction(const std::vector<KeyType>& Inputs,
                             SimpleTask::ComputeFnType Compute) {
  return [=] (BuildEngine& engine) {
    return engine.registerTask(new SimpleTask(Inputs, Compute)); };
}

}

@implementation CorePerfTests

#pragma mark - "buildengine ack" Performance Tests

- (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 {
    virtual 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 core::Rule();
    }
    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();
    }
  } Delegate;
  __block core::BuildEngine Engine(Delegate);
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    char Name[32];
    sprintf(Name, "i%d", i);
    if (i != M) {
      char InputName[32];
      sprintf(InputName, "i%d", i+1);
      Engine.addRule({
          Name, simpleAction({ InputName },
                             [] (const std::vector<int>& Inputs) {
                               return Inputs[0]; }) });
    } else {
      Engine.addRule({
          Name,
          simpleAction({},
                       [&] (const std::vector<int>& Inputs) {
                         return LastInputValue; }),
          [&](BuildEngine&, const Rule& rule, 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 measureBlock:^{
      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 {
    virtual 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 core::Rule();
    }
    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();
    }
  } Delegate;
  __block 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];
      sprintf(Name, "i%d,%d", i, j);
      if (i != M) {
        std::vector<KeyType> Inputs;
        for (int k = 1; k <= N; ++k) {
          char InputName[32];
          sprintf(InputName, "i%d,%d", i+1, 1 + (j - 1)*N + (k - 1));
          Inputs.push_back(InputName);
        }
        Engine.addRule({
            Name, simpleAction(Inputs, [] (const std::vector<int>& Inputs) {
                return Inputs[0]; }) });
      } else {
        Engine.addRule({
            Name,
            simpleAction({},
                         [&] (const std::vector<int>& Inputs) {
                           return LastInputValue; }),
            [&](BuildEngine&, const Rule& rule, 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 measureBlock:^{
      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 = 1000, N = 1000; // Use a graph of 1 million nodes.

  // Set up the build rules.
  struct MatrixDelegate : public BuildEngineDelegate {
    virtual 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 core::Rule();
    }
    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();
    }
  } Delegate;
  __block core::BuildEngine Engine(Delegate);
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    for (int j = 1; j <= N; ++j) {
      char Name[32];
      sprintf(Name, "i%d,%d", i, j);
      if (i != M && j != N) {
        // Nodes not on an edge.
        char InputAName[32];
        sprintf(InputAName, "i%d,%d", i+1, j);
        char InputBName[32];
        sprintf(InputBName, "i%d,%d", i, j+1);
        Engine.addRule({
            Name, simpleAction({ InputAName, InputBName },
                               [] (const std::vector<int>& Inputs) {
                                 return Inputs[0]; }) });
      } else if (i != M) {
        // Top edge.
        assert(j == N);
        char InputName[32];
        sprintf(InputName, "i%d,%d", i+1, j);
        Engine.addRule({
            Name, simpleAction({ InputName },
                               [] (const std::vector<int>& Inputs) {
                                 return Inputs[0]; }) });
      } else if (j != N) {
        // Right edge.
        assert(i == M);
        char InputName[32];
        sprintf(InputName, "i%d,%d", i, j+1);
        Engine.addRule({
            Name, simpleAction({ InputName },
                               [] (const std::vector<int>& Inputs) {
                                 return Inputs[0]; }) });
      } else {
        // Top-right corner node.
        assert(i == M && j == N);
        Engine.addRule({
            Name,
            simpleAction({},
                         [&] (const std::vector<int>& Inputs) {
                           return LastInputValue; }),
            [&](BuildEngine&, const Rule& rule, 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 measureBlock:^{
      auto Result = IntFromValue(Engine.build("i1,1"));
      (void)Result;
      assert(Result == LastInputValue);
    }];
}

@end