//===-- BuildEngine.cpp ---------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2019 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
//
//===----------------------------------------------------------------------===//

#include "llbuild/Core/BuildEngine.h"

#include "llbuild/Basic/Defer.h"
#include "llbuild/Basic/ExecutionQueue.h"
#include "llbuild/Basic/Tracing.h"
#include "llbuild/Core/BuildDB.h"
#include "llbuild/Core/KeyID.h"

#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringMap.h"

#include "BuildEngineTrace.h"

#include <atomic>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <condition_variable>
#include <deque>
#include <memory>
#include <mutex>
#include <thread>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace llbuild;
using namespace llbuild::basic;
using namespace llbuild::core;

Task::~Task() {}

Rule::~Rule() {}
void Rule::updateStatus(BuildEngine&, StatusKind) {}

BuildEngineDelegate::~BuildEngineDelegate() {}

void BuildEngineDelegate::determinedRuleNeedsToRun(Rule* ruleNeedingToRun, Rule::RunReason, Rule* inputRule) {}

bool BuildEngineDelegate::shouldResolveCycle(const std::vector<Rule*>& items,
                                             Rule* candidateRule,
                                             Rule::CycleAction action) {
  return false;
}

CancellationDelegate::~CancellationDelegate() = default;

#pragma mark - BuildEngine implementation

namespace {

class BuildEngineImpl : public BuildDBDelegate {
  struct RuleInfo;
  struct TaskInfo;

  /// Reserved input ID. May be generated by application, but never vended
  /// to the application if the engine generates it itself).
  static constexpr uintptr_t kMustFollowInputID = ~(uintptr_t)0;

  BuildEngine& buildEngine;

  BuildEngineDelegate& delegate;

  /// The key table, used when there is no database.
  llvm::StringMap<KeyID> keyTable;

  /// The mutex that protects the key table.
  std::mutex keyTableMutex;

  /// The build database, if attached.
  std::unique_ptr<BuildDB> db;

  /// The tracing implementation, if enabled.
  std::unique_ptr<BuildEngineTrace> trace;

  /// Path of the trace file to write to, if set.
  std::string traceFile;

  /// Mutex for access to execution queue.
  std::mutex executionQueueMutex;

  /// The execution queue reference; this is only valid while a build is
  /// actually in progress.
  std::unique_ptr<ExecutionQueue> executionQueue;

  /// The current build iteration, used to sequentially timestamp build results.
  Epoch currentEpoch = 0;

  /// Whether the build should be cancelled.
  std::atomic<bool> buildCancelled{ false };

  /// Whether a build is currently running.
  std::atomic<bool> buildRunning{ false };
  std::mutex buildEngineMutex;

  llvm::DenseSet<core::CancellationDelegate *> cancellationDelegates;

  /// The queue of input requests to process.
  struct TaskInputRequest {
    /// The task making the request.
    TaskInfo* taskInfo;
    /// The task provided input ID, for its own use in identifying the input.
    uintptr_t inputID;
    /// The rule for the input which was requested.
    RuleInfo* inputRuleInfo;
    /// Whether this rule is to be executed as order-only.
    bool orderOnly = false;
    /// Force the use of a prior value
    bool forcePriorValue = false;
    /// Whether this rule should be removed as a dependency after execution
    bool singleUse = false;
  };
  std::deque<TaskInputRequest> inputRequests;
  std::vector<TaskInputRequest> finishedInputRequests;

  /// The mutex that protects access to inputRequests
  std::mutex inputRequestsMutex;


  /// The queue of rules being scanned.
  struct RuleScanRequest {
    /// The rule making the request.
    RuleInfo* ruleInfo;
    /// The input index being considered.
    unsigned inputIndex;
    /// The input being considered, if already looked up.
    ///
    /// This is used when a scan request is deferred waiting on its input to be
    /// scanned, to avoid a redundant hash lookup.
    RuleInfo* inputRuleInfo;
    /// Whether the rule is executed in order-only way.
    bool orderOnly;
    /// Whether the rule is cleaned from dependencies after execution.
    bool singleUse = false;
  };
  std::vector<RuleScanRequest> ruleInfosToScan;

  struct RuleScanRecord {
    /// The vector of paused input requests, waiting for the dependency scan on
    /// this rule to complete.
    std::vector<TaskInputRequest> pausedInputRequests;
    /// The vector of deferred scan requests, for rules which are waiting on
    /// this one to be scanned.
    std::vector<RuleScanRequest> deferredScanRequests;
  };

  /// Wrapper for information specific to a single rule.
  struct RuleInfo {
    enum class StateKind {
      /// The initial rule state.
      Incomplete = 0,

      /// The rule is being scanned to determine if it needs to run.
      IsScanning,

      /// The rule needs to run, but has not yet been started.
      NeedsToRun,

      /// The rule does not need to run, but has not yet been marked as
      /// complete.
      DoesNotNeedToRun,

      /// The rule is in progress, but is waiting on additional inputs.
      InProgressWaiting,

      /// The rule is in progress, and is computing its result.
      InProgressComputing,

      /// The rule is complete, with an available result.
      ///
      /// Note that as an optimization, when the build timestamp is incremented
      /// we do not immediately reset the state, rather we do it lazily as part
      /// of \see demandRule() in conjunction with the Result::builtAt field.
      Complete
    };

    RuleInfo(KeyID keyID, std::unique_ptr<Rule>&& rule) : keyID(keyID), rule(std::move(rule)) {}

    /// The ID for the rule key.
    KeyID keyID;

    /// The rule this information describes.
    std::unique_ptr<Rule> rule;

    /// The state dependent record for in-progress information.
    union {
      RuleScanRecord* pendingScanRecord;
      TaskInfo* pendingTaskInfo;
    } inProgressInfo = { nullptr };
    /// The most recent rule result.
    Result result = {};
    /// The current state of the rule.
    StateKind state = StateKind::Incomplete;
    bool wasForced = false;

  public:
    bool isScanning() const {
      return state == StateKind::IsScanning;
    }

    bool isScanned(const BuildEngineImpl* engine) const {
      // If the rule is marked as complete, just check that state.
      if (state == StateKind::Complete)
        return isComplete(engine);

      // Otherwise, the rule is scanned if it has passed the scanning state.
      return int(state) > int(StateKind::IsScanning);
    }

    bool isInProgressWaiting() const {
      return state == StateKind::InProgressWaiting;
    }

    bool isInProgressComputing() const {
      return state == StateKind::InProgressComputing;
    }

    bool isInProgress() const {
      return isInProgressWaiting() || isInProgressComputing();
    }

    bool isComplete(const BuildEngineImpl* engine) const {
      return state == StateKind::Complete &&
        result.builtAt == engine->getCurrentEpoch();
    }

    void setComputing(const BuildEngineImpl* engine) {
      assert(isInProgressWaiting());
      state = StateKind::InProgressComputing;
      result.start = basic::Clock::now();
    }

    void setComplete(const BuildEngineImpl* engine) {
      state = StateKind::Complete;
      // Note we do not push this change to the database. This is essentially a
      // mark we maintain to allow a lazy transition to Incomplete when the
      // timestamp is incremented.
      //
      // FIXME: This is a bit dubious, and wouldn't work anymore if we moved the
      // Result to being totally managed by the database. However, it is just a
      // matter of keeping an extra timestamp outside the Result to fix.
      result.builtAt = engine->getCurrentEpoch();
      result.end = basic::Clock::now();
    }

    void setCancelled() {
      // If we have to cancel a task, it becomes incomplete. We do not need to
      // sync this to the database, the database won't see an updated record and
      // can continue to maintain the previous view of state -- however, we must
      // mark the internal representation as incomplete because the result is no
      // longer valid.
      state = StateKind::Incomplete;
    }

    RuleScanRecord* getPendingScanRecord() {
      assert(isScanning());
      return inProgressInfo.pendingScanRecord;
    }
    const RuleScanRecord* getPendingScanRecord() const {
      assert(isScanning());
      return inProgressInfo.pendingScanRecord;
    }
    void setPendingScanRecord(RuleScanRecord* value) {
      inProgressInfo.pendingScanRecord = value;
    }

    TaskInfo* getPendingTaskInfo() {
      assert(isInProgress());
      return inProgressInfo.pendingTaskInfo;
    }
    const TaskInfo* getPendingTaskInfo() const {
      assert(isInProgress());
      return inProgressInfo.pendingTaskInfo;
    }
    void setPendingTaskInfo(TaskInfo* value) {
      assert(isInProgress());
      inProgressInfo.pendingTaskInfo = value;
    }
  };

  // The map of registered rules.
  //
  // NOTE: We currently rely on the unordered_map behavior that ensures that
  // references to elements are not invalidated by insertion. We will need to
  // move to an alternate allocation strategy if we switch to DenseMap style
  // table. This is probably a good idea in any case, because we would benefit
  // from pool allocating RuleInfo instances.
  std::unordered_map<KeyID, RuleInfo> ruleInfos;

  /// Information tracked for executing tasks.
  //
  // FIXME: Keeping this in a side table is very inefficient, we always have to
  // look it up. It might make much more sense to require the Task to have a
  // private field available for our use to store this.
  struct TaskInfo {
    TaskInfo(Task* task) : task(task) {}

    std::unique_ptr<Task> task;
    /// The list of input requests that are waiting on this task, which will be
    /// fulfilled once the task is complete.
    //
    // FIXME: Note that this structure is redundant here, as
    // (TaskInputRequest::InputTaskInfo == this) for all items, but we reuse the
    // existing structure for simplicity.
    std::vector<TaskInputRequest> requestedBy;
    /// The vector of deferred scan requests, for rules which are waiting on
    /// this one to be scanned.
    //
    // FIXME: As above, this structure has redundancy in it.
    std::vector<RuleScanRequest> deferredScanRequests;
    /// The rule that this task is computing.
    RuleInfo* forRuleInfo = nullptr;
    /// The number of outstanding inputs that this task is waiting on to be
    /// provided.
    unsigned waitCount = 0;
    /// The list of discovered dependencies found during execution of the task.
    DependencyKeyIDs discoveredDependencies;

#ifndef NDEBUG
    void dump() const {
      fprintf(stderr,
              "<TaskInfo:%p: task:%p, for-rule:\"%s\", wait-count:%d>\n",
              this, task.get(),
              forRuleInfo ? forRuleInfo->rule->key.c_str() : "(null)",
              waitCount);
      for (const auto& request: requestedBy) {
        fprintf(stderr, "  requested by: %s\n",
                request.taskInfo->forRuleInfo->rule->key.c_str());
      }
    }
#endif
  };

  /// The tracked information for executing tasks.
  ///
  /// Access to this must be protected via \see taskInfosMutex.
  std::unordered_map<Task*, TaskInfo> taskInfos;

  /// The mutex that protects the task info map.
  std::mutex taskInfosMutex;

  /// The queue of tasks ready to be finalized.
  std::deque<TaskInfo*> readyTaskInfos;

  /// The number of tasks which have been readied but not yet finished.
  unsigned numOutstandingUnfinishedTasks = 0;

  /// The queue of tasks which are complete, accesses to this member variable
  /// must be protected via \see finishedTaskInfosMutex.
  std::vector<TaskInfo*> finishedTaskInfos;

  /// The mutex that protects finished task infos.
  std::mutex finishedTaskInfosMutex;

  /// This variable is used to signal when additional work is added to the
  /// FinishedTaskInfos queue, which the engine may need to wait on.
  std::condition_variable finishedTaskInfosCondition;



private:
  /// @name RuleScanRecord Allocation
  ///
  /// The execution of a single build may use a substantial amount of
  /// additional memory in recording the bookkeeping information used to do
  /// dependency scanning. While we could keep this information adjacent to
  /// every \see RuleInfo, that adds up to a substantial chunk of memory which
  /// is wasted except during dependency scanning.
  ///
  /// Instead, we allocate \see RuleScanRecord objects for each rule only as it
  /// is being scanned, and use a custom allocator for the objects to try and
  /// make this efficient. Currently we use a bounded free-list backed by a slab
  /// allocator.
  ///
  /// Note that this still has a fairly large impact on dependency scanning
  /// performance, in the worst case a deep linear graph takes ~50% longer to
  /// scan, but it also provides an overall 15-20% memory savings on resident
  /// engine size.
  ///
  /// @{

  // FIXME: This should be abstracted into a helper class.

  /// A free-list of RuleScanRecord objects.
  std::vector<RuleScanRecord*> freeRuleScanRecords;
  /// The maximum number of free-list items to keep.
  const size_t maximumFreeRuleScanRecords = 8096;
  /// The list of blocks (of size \see NumScanRecordsPerBlock) we have
  /// allocated.
  std::vector<RuleScanRecord*> ruleScanRecordBlocks;
  /// The number of records to allocate per block.
  const size_t numScanRecordsPerBlock = 4096;
  /// The buffer positions of the current block.
  RuleScanRecord* currentBlockPos = nullptr, * currentBlockEnd = nullptr;

  RuleScanRecord* newRuleScanRecord() {
    // If we have an item on the free list, return it.
    if (!freeRuleScanRecords.empty()) {
      auto result = freeRuleScanRecords.back();
      freeRuleScanRecords.pop_back();
      return result;
    }

    // If we are at the end of a block, allocate a new one.
    if (currentBlockPos == currentBlockEnd) {
      currentBlockPos = new RuleScanRecord[numScanRecordsPerBlock];
      ruleScanRecordBlocks.push_back(currentBlockPos);
      currentBlockEnd = currentBlockPos + numScanRecordsPerBlock;
    }
    return currentBlockPos++;
  }

  void freeRuleScanRecord(RuleScanRecord* scanRecord) {
    if (freeRuleScanRecords.size() < maximumFreeRuleScanRecords) {
      scanRecord->pausedInputRequests.clear();
      scanRecord->deferredScanRequests.clear();
      freeRuleScanRecords.push_back(scanRecord);
    }
  }

  /// @}

  /// @name Build Execution
  /// @{

  /// Request the scanning of the given rule to determine if it needs to run in
  /// the current environment.
  ///
  /// \returns True if the rule is already scanned, otherwise the rule will be
  /// enqueued for processing.
  bool scanRule(RuleInfo& ruleInfo) {
    // If the rule is already scanned, we are done.
    if (ruleInfo.isScanned(this))
      return true;

    // If the rule is being scanned, we don't need to do anything.
    if (ruleInfo.isScanning())
      return false;
    
    /// Cleans up single use dependencies that should not be considered for incremental builds.
    ruleInfo.result.dependencies.cleanSingleUseDependencies();

    // Otherwise, start scanning the rule.
    if (trace)
      trace->checkingRuleNeedsToRun(ruleInfo.rule.get());

    // Report the status change.
    ruleInfo.rule->updateStatus(buildEngine, Rule::StatusKind::IsScanning);

    ruleInfo.wasForced = false;

    // If the rule has never been run, it needs to run.
    if (ruleInfo.result.builtAt == 0) {
      if (trace)
        trace->ruleNeedsToRunBecauseNeverBuilt(ruleInfo.rule.get());
      ruleInfo.state = RuleInfo::StateKind::NeedsToRun;
      delegate.determinedRuleNeedsToRun(ruleInfo.rule.get(), Rule::RunReason::NeverBuilt, nullptr);
      return true;
    }

    if (ruleInfo.rule->signature != ruleInfo.result.signature) {
      if (trace)
        trace->ruleNeedsToRunBecauseSignatureChanged(ruleInfo.rule.get());
      ruleInfo.state = RuleInfo::StateKind::NeedsToRun;
      delegate.determinedRuleNeedsToRun(ruleInfo.rule.get(), Rule::RunReason::SignatureChanged, nullptr);
      return true;
    }

    // If the rule indicates its computed value is out of date, it needs to run.
    //
    // FIXME: We should probably try and move this so that it can be done by
    // clients in the background, either by us backgrounding it, or by using a
    // completion model as we do for inputs.
    if (!ruleInfo.rule->isResultValid(buildEngine, ruleInfo.result.value)) {
      if (trace)
        trace->ruleNeedsToRunBecauseInvalidValue(ruleInfo.rule.get());
      ruleInfo.state = RuleInfo::StateKind::NeedsToRun;
      delegate.determinedRuleNeedsToRun(ruleInfo.rule.get(), Rule::RunReason::InvalidValue, nullptr);
      return true;
    }

    // If the rule has no dependencies, then it is ready to run.
    if (ruleInfo.result.dependencies.empty()) {
      if (trace)
        trace->ruleDoesNotNeedToRun(ruleInfo.rule.get());
      ruleInfo.state = RuleInfo::StateKind::DoesNotNeedToRun;
      return true;
    }

    // Otherwise, we need to do a recursive scan of the inputs so enqueue this
    // rule for scanning.
    //
    // We could also take an approach where we enqueue each of the individual
    // inputs, but in my experiments with that approach it has always performed
    // significantly worse.
    if (trace)
      trace->ruleScheduledForScanning(ruleInfo.rule.get());
    ruleInfo.state = RuleInfo::StateKind::IsScanning;
    ruleInfo.setPendingScanRecord(newRuleScanRecord());
    ruleInfosToScan.push_back({ &ruleInfo, /*InputIndex=*/0, nullptr, false });

    return false;
  }

  /// Request the construction of the key specified by the given rule.
  ///
  /// \returns True if the rule is already available, otherwise the rule will be
  /// enqueued for processing.
  bool demandRule(RuleInfo& ruleInfo) {
    // The rule must have already been scanned.
    assert(ruleInfo.isScanned(this));

    // If the rule is complete, we are done.
    if (ruleInfo.isComplete(this))
      return true;

    // If the rule is in progress, we don't need to do anything.
    if (ruleInfo.isInProgress())
      return false;

    // If the rule isn't marked complete, but doesn't need to actually run, then
    // just update it.
    if (ruleInfo.state == RuleInfo::StateKind::DoesNotNeedToRun) {
      ruleInfo.setComplete(this);

      // Report the status change.
      ruleInfo.rule->updateStatus(buildEngine, Rule::StatusKind::IsUpToDate);

      return true;
    }

    // Otherwise, we actually need to initiate the processing of this rule.
    assert(ruleInfo.state == RuleInfo::StateKind::NeedsToRun);

    // Create the task for this rule.
    Task* task = ruleInfo.rule->createTask(buildEngine);
    assert(task && "rule action returned null task");

    // register the task
    taskInfosMutex.lock();
    auto result = taskInfos.emplace(task, TaskInfo(task));
    assert(result.second && "task already registered");
    auto taskInfo = &(result.first)->second;
    taskInfosMutex.unlock();
    taskInfo->forRuleInfo = &ruleInfo;

    if (trace)
      trace->createdTaskForRule(taskInfo->task.get(), ruleInfo.rule.get());

    // Transition the rule state.
    ruleInfo.state = RuleInfo::StateKind::InProgressWaiting;
    ruleInfo.setPendingTaskInfo(taskInfo);

    // Reset the Rule Dependencies, which we just append to during processing,
    // but we reset the others to ensure no one ever inadvertently uses them
    // during an invalid state.
    ruleInfo.result.dependencies.clear();

    // Inform the task it should start.
    {
      TracingEngineTaskCallback i(EngineTaskCallbackKind::Start, ruleInfo.keyID);
      TaskInterface iface{this, task};
      task->start(iface);
    }

    // Provide the task the prior result, if present.
    //
    // FIXME: This should perhaps just be lumped in with the start call? Or
    // alternately, maybe there should just be an API call to fetch this, and
    // the clients that want it can ask? It's cheap to provide here, so
    // ultimately this is mostly a matter of cleanliness.
    if (ruleInfo.result.builtAt != 0 &&
        ruleInfo.rule->signature == ruleInfo.result.signature) {
      TracingEngineTaskCallback i(EngineTaskCallbackKind::ProvidePriorValue, ruleInfo.keyID);
      TaskInterface iface{this, task};
      task->providePriorValue(iface, ruleInfo.result.value);
    }

    // If this task has no waiters, schedule it immediately for finalization.
    if (!taskInfo->waitCount) {
      readyTaskInfos.push_back(taskInfo);
    }

    return false;
  }

  /// Process an individual scan request.
  ///
  /// This will process all of the inputs required by the requesting rule, in
  /// order, unless the scan needs to be deferred waiting for an input.
  void processRuleScanRequest(RuleScanRequest request) {
    auto& ruleInfo = *request.ruleInfo;

    // With forced builds in cycle breaking, we may end up being asked to scan
    // something that has already been 'scanned'
    assert(ruleInfo.isScanning() || ruleInfo.wasForced);
    if (!ruleInfo.isScanning())
      return;

    // Process each of the remaining inputs.
    do {
      // Look up the input rule info, if not yet cached.
      if (!request.inputRuleInfo) {
        const auto& keyAndFlag = ruleInfo.result.dependencies[request.inputIndex];
        request.inputRuleInfo = &getRuleInfoForKey(keyAndFlag.keyID);
        request.orderOnly = keyAndFlag.orderOnly;
        request.singleUse = keyAndFlag.singleUse;
      }

      auto& inputRuleInfo = *request.inputRuleInfo;

      // Scan the input.
      bool isScanned = scanRule(inputRuleInfo);

      // If the input isn't scanned yet, enqueue this input scan request.
      if (!isScanned) {
        assert(inputRuleInfo.isScanning());
        if (trace)
          trace->ruleScanningDeferredOnInput(ruleInfo.rule.get(),
                                             inputRuleInfo.rule.get());
        inputRuleInfo.getPendingScanRecord()
          ->deferredScanRequests.push_back(request);
        return;
      }

      if (trace)
        trace->ruleScanningNextInput(ruleInfo.rule.get(), inputRuleInfo.rule.get());

      // Demand the input.
      bool isAvailable = demandRule(inputRuleInfo);

      // If the input isn't already available, enqueue this scan request on the
      // input.
      //
      // FIXME: We need to continue scanning the rest of the inputs to ensure we
      // are not delaying necessary work. See <rdar://problem/20248283>.
      if (!isAvailable) {
        if (trace)
          trace->ruleScanningDeferredOnTask(
            ruleInfo.rule.get(), inputRuleInfo.getPendingTaskInfo()->task.get());
        assert(inputRuleInfo.isInProgress());
        inputRuleInfo.getPendingTaskInfo()->
            deferredScanRequests.push_back(request);
        return;
      }

      if (request.orderOnly) {
        // If the input is an order-only input it is just enough that it
        // is available. No need to run anew.
      } else {
        // If the input has been computed since the last time this rule was
        // built, it needs to run.
        if (ruleInfo.result.builtAt < inputRuleInfo.result.computedAt) {
          if (trace)
            trace->ruleNeedsToRunBecauseInputRebuilt(
              ruleInfo.rule.get(), inputRuleInfo.rule.get());
          finishScanRequest(ruleInfo, RuleInfo::StateKind::NeedsToRun);
          delegate.determinedRuleNeedsToRun(ruleInfo.rule.get(), Rule::RunReason::InputRebuilt, inputRuleInfo.rule.get());
          return;
        }
      }

      // Otherwise, increment the scan index.
      ++request.inputIndex;
      request.inputRuleInfo = nullptr;
      request.orderOnly = false;
      request.singleUse = false;
    } while (request.inputIndex != ruleInfo.result.dependencies.size());

    // If we reached the end of the inputs, the rule does not need to run.
    if (trace)
      trace->ruleDoesNotNeedToRun(ruleInfo.rule.get());
    finishScanRequest(ruleInfo, RuleInfo::StateKind::DoesNotNeedToRun);
  }

  void finishScanRequest(RuleInfo& inputRuleInfo,
                         RuleInfo::StateKind newState) {
    assert(inputRuleInfo.isScanning());
    auto scanRecord = inputRuleInfo.getPendingScanRecord();

    // Wake up all of the pending scan requests.
    for (const auto& request: scanRecord->deferredScanRequests) {
      ruleInfosToScan.push_back(request);
    }

    // Wake up all of the input requests on this rule.
    {
      std::lock_guard<std::mutex> guard(inputRequestsMutex);
      for (const auto& request: scanRecord->pausedInputRequests) {
        inputRequests.push_back(request);
      }
    }

    // Update the rule state.
    freeRuleScanRecord(scanRecord);
    inputRuleInfo.setPendingScanRecord(nullptr);
    inputRuleInfo.state = newState;
  }

  /// Decrement the task's wait count, and move it to the ready queue if
  /// necessary.
  void decrementTaskWaitCount(TaskInfo* taskInfo) {
    --taskInfo->waitCount;
    if (trace)
      trace->updatedTaskWaitCount(taskInfo->task.get(), taskInfo->waitCount);
    if (taskInfo->waitCount == 0) {
      if (trace)
        trace->unblockedTask(taskInfo->task.get());
      readyTaskInfos.push_back(taskInfo);
    }
  }

  /// Execute all of the work pending in the engine queues until they are empty.
  ///
  /// \param buildKey The key to build.
  /// \returns True on success, false if the build could not be completed; the
  /// latter only occurs when the build contains a cycle currently.
  bool executeTasks(const KeyType& buildKey) {
    // Clear any previous build state
    finishedInputRequests.clear();

    // Push a dummy input request for the rule to build.
    inputRequests.push_back({ nullptr, 0, &getRuleInfoForKey(buildKey), false, false, false });

    // Process requests as long as we have work to do.
    while (true) {
      bool didWork = false;

      // Cancel the build, if requested.
      if (buildCancelled) {
        // Force completion of all outstanding tasks.
        cancelRemainingTasks();
        return false;
      }

      // Process all of the pending rule scan requests.
      //
      // FIXME: We don't want to process all of these requests, this amounts to
      // doing all of the dependency scanning up-front.
      while (!ruleInfosToScan.empty()) {
        TracingEngineQueueItemEvent i(EngineQueueItemKind::RuleToScan, buildKey.c_str());

        didWork = true;

        auto request = ruleInfosToScan.back();
        ruleInfosToScan.pop_back();

        processRuleScanRequest(request);
      }

      // Process all of the pending input requests.
      while (true) {
        TracingEngineQueueItemEvent i(EngineQueueItemKind::InputRequest, buildKey.c_str());

        TaskInputRequest request;
        bool found = false;
        {
          std::lock_guard<std::mutex> guard(inputRequestsMutex);
          if (!inputRequests.empty()) {
            // IMPORTANT: Dependency recording below relies on the assumption
            // that we will process input requests in FIFO order. DO NOT CHANGE
            // this without adjusting for this expectation.
            request = inputRequests.front();
            inputRequests.pop_front();
            found = true;
          }
        }
        if (!found)
          break;

        didWork = true;

        if (trace) {
          if (request.taskInfo) {
            trace->handlingTaskInputRequest(request.taskInfo->task.get(),
                                            request.inputRuleInfo->rule.get());
          } else {
            trace->handlingBuildInputRequest(request.inputRuleInfo->rule.get());
          }
        }

        // Request the input rule be scanned.
        bool isScanned = scanRule(*request.inputRuleInfo);

        // If the rule is not yet scanned, suspend this input request.
        if (!isScanned) {
          assert(request.inputRuleInfo->isScanning());
          if (trace)
            trace->pausedInputRequestForRuleScan(
              request.inputRuleInfo->rule.get());
          request.inputRuleInfo->getPendingScanRecord()
            ->pausedInputRequests.push_back(request);
          continue;
        }

        // Request the input rule be computed.
        bool isAvailable = demandRule(*request.inputRuleInfo);

        // If this is a dummy input request, we are done.
        if (!request.taskInfo)
          continue;

        // Update the recorded dependencies of this task.
        //
        // FIXME: This is very performance critical and should be highly
        // optimized. By itself, this addition added about 25% user time to the
        // "ack 3 16" experiment.
        //
        // There are multiple options for when to record these dependencies:
        // 1. Record at the time it is requested.
        // 2. Record at the time it is popped off the input request queue.
        // 3. Record at the time the input is supplied.
        //
        // Here we have chosen option 2 for two reasons. First, we want to avoid
        // the need to synchronize concurrent access to the rule info data
        // structure, therefore we want to perform this work on the engine
        // thread (and as such rules out option 1).
        //
        // Second, we explicitly wish to record dependencies in the order in
        // which they have been requested by the task/client. This ensures that
        // dependencies will be recorded in a deterministic order that is under
        // client control. This can be important for performance in subsequent
        // incremental builds, where scanning order is important for discovering
        // work.
        //
        // NOTE: In order to achieve the latter, we rely processing input
        // requests in FIFO order.
        //
        request.taskInfo->forRuleInfo->result.dependencies.push_back(
            request.inputRuleInfo->keyID, request.orderOnly, request.singleUse);


        // If the rule is already available, enqueue the finalize request.
        if (isAvailable) {
          if (trace)
            trace->readyingTaskInputRequest(request.taskInfo->task.get(),
                                            request.inputRuleInfo->rule.get());
          finishedInputRequests.push_back(request);
        } else {
          // Otherwise, record the pending input request.
          assert(request.inputRuleInfo->getPendingTaskInfo());
          if (trace)
            trace->addedRulePendingTask(request.inputRuleInfo->rule.get(),
                                        request.taskInfo->task.get());
          request.inputRuleInfo->getPendingTaskInfo()->requestedBy.push_back(
            request);
        }
      }

      // Process all of the finished inputs.
      while (!finishedInputRequests.empty()) {
        TracingEngineQueueItemEvent i(EngineQueueItemKind::FinishedInputRequest, buildKey.c_str());

        didWork = true;

        auto request = finishedInputRequests.back();
        finishedInputRequests.pop_back();

        if (trace)
          trace->completedTaskInputRequest(request.taskInfo->task.get(),
                                           request.inputRuleInfo->rule.get());

        // Otherwise, we are processing a regular input dependency.

        // Provide the requesting task with the input.
        //
        // FIXME: Should we provide the input key here? We have it available
        // cheaply.
        assert(request.inputRuleInfo->isComplete(this) || request.forcePriorValue || request.orderOnly);
        if (request.orderOnly) {
          assert(request.inputID == kMustFollowInputID);
        } else {
          TracingEngineTaskCallback i(EngineTaskCallbackKind::ProvideValue, request.inputRuleInfo->keyID);
          TaskInterface iface{this, request.taskInfo->task.get()};
          request.taskInfo->task->provideValue(
              iface, request.inputID, request.inputRuleInfo->result.value);
        }

        // Decrement the wait count, and move to finish queue if necessary.
        decrementTaskWaitCount(request.taskInfo);
      }

      // Process all of the ready to run tasks.
      while (!readyTaskInfos.empty()) {
        TracingEngineQueueItemEvent i(EngineQueueItemKind::ReadyTask, buildKey.c_str());

        didWork = true;

        // Process ready tasks FIFO to preserve the relative ordering they were
        // requested by tasks above.
        TaskInfo* taskInfo = readyTaskInfos.front();
        readyTaskInfos.pop_front();

        RuleInfo* ruleInfo = taskInfo->forRuleInfo;
        assert(taskInfo == ruleInfo->getPendingTaskInfo());

        if (trace)
            trace->readiedTask(taskInfo->task.get(), ruleInfo->rule.get());

        // Transition the rule state.
        ruleInfo->setComputing(this);

        // Inform the task its inputs are ready and it should finish.
        //
        // FIXME: We need to track this state, and generate an error if this
        // task ever requests additional inputs.
        {
          TracingEngineTaskCallback i(EngineTaskCallbackKind::InputsAvailable, ruleInfo->keyID);
          TaskInterface iface{this, taskInfo->task.get()};
          taskInfo->task->inputsAvailable(iface);
        }

        // Increment our count of outstanding tasks.
        ++numOutstandingUnfinishedTasks;
      }

      // Process all of the finished tasks.
      while (true) {
        TracingEngineQueueItemEvent i(EngineQueueItemKind::FinishedTask, buildKey.c_str());

        // Try to take a task from the finished queue.
        TaskInfo* taskInfo = nullptr;
        {
          std::lock_guard<std::mutex> guard(finishedTaskInfosMutex);
          if (!finishedTaskInfos.empty()) {
            taskInfo = finishedTaskInfos.back();
            finishedTaskInfos.pop_back();
          }
        }
        if (!taskInfo)
          break;

        didWork = true;

        RuleInfo* ruleInfo = taskInfo->forRuleInfo;
        assert(taskInfo == ruleInfo->getPendingTaskInfo());

        // The task was changed if was computed in the current iteration.
        if (trace) {
          bool wasChanged = ruleInfo->result.computedAt == currentEpoch;
          trace->finishedTask(taskInfo->task.get(), ruleInfo->rule.get(),
                              wasChanged);
        }

        // Transition the rule state by completing the rule (the value itself is
        // stored in the taskIsFinished call).
        assert(ruleInfo->state == RuleInfo::StateKind::InProgressComputing);
        ruleInfo->setPendingTaskInfo(nullptr);
        ruleInfo->setComplete(this);

        // Report the status change.
        ruleInfo->rule->updateStatus(buildEngine, Rule::StatusKind::IsComplete);

        // Add all of the task's discovered dependencies.
        //
        // FIXME: We could audit these dependencies at this point to verify that
        // they are not keys for rules which have not been run, which would
        // indicate an underspecified build (e.g., a generated header).
        ruleInfo->result.dependencies.append(taskInfo->discoveredDependencies);

        // Push back dummy input requests for any discovered dependencies, which
        // must be at least built in order to be brought up-to-date.
        //
        // FIXME: The need to do this makes it questionable that we use this
        // approach for discovered dependencies instead of just providing
        // support for request() even after the task has started computing and
        // from parallel contexts.
        {
          std::lock_guard<std::mutex> guard(inputRequestsMutex);
          for (auto dependency: taskInfo->discoveredDependencies) {
            inputRequests.push_back({ nullptr, 0, &getRuleInfoForKey(dependency.keyID), dependency.orderOnly, false , dependency.singleUse});
          }
        }

        // Update the database record, if attached.
        if (db) {
          std::string error;
          bool result = db->setRuleResult(
              ruleInfo->keyID, *ruleInfo->rule, ruleInfo->result, &error);
          if (!result) {
            delegate.error(error);

            // Decrement our count of outstanding tasks. This must be done prior
            // the subsequent synchronous cancellation, since it will otherwise
            // deadlock waiting for the task we have already popped off the
            // queue. rdar://problem/50203529
            --numOutstandingUnfinishedTasks;

            cancelRemainingTasks();
            return false;
          }
        }

        // Wake up all of the pending scan requests.
        for (const auto& request: taskInfo->deferredScanRequests) {
          ruleInfosToScan.push_back(request);
        }

        // Push all pending input requests onto the work queue.
        if (trace) {
          for (auto& request: taskInfo->requestedBy) {
            trace->readyingTaskInputRequest(request.taskInfo->task.get(),
                                            request.inputRuleInfo->rule.get());
          }
        }
        finishedInputRequests.insert(finishedInputRequests.end(),
                                     taskInfo->requestedBy.begin(),
                                     taskInfo->requestedBy.end());

        // Decrement our count of outstanding tasks.
        --numOutstandingUnfinishedTasks;

        // Delete the pending task.
        {
          std::lock_guard<std::mutex> guard(taskInfosMutex);
          auto it = taskInfos.find(taskInfo->task.get());
          assert(it != taskInfos.end());
          taskInfos.erase(it);
        }
      }

      // If we haven't done any other work at this point but we have pending
      // tasks, we need to wait for a task to complete.
      //
      // NOTE: Cancellation also implements this process, if you modify this
      // code please also validate that \see cancelRemainingTasks() is still
      // correct.
      if (!didWork && numOutstandingUnfinishedTasks != 0) {
        TracingEngineQueueItemEvent i(EngineQueueItemKind::Waiting, buildKey.c_str());

        // Wait for our condition variable.
        std::unique_lock<std::mutex> lock(finishedTaskInfosMutex);

        // Ensure we still don't have enqueued operations under the protection
        // of the mutex, if one has been added then we may have already missed
        // the condition notification and cannot safely wait.
        if (finishedTaskInfos.empty()) {
          finishedTaskInfosCondition.wait(lock);
        }

        didWork = true;
      }

      if (!didWork) {
        // If there was no work to do, but we still have running tasks, then
        // we have found a cycle. Try to resolve it and continue.
        if (!taskInfos.empty()) {
          if (resolveCycle(buildKey)) {
            continue;
          } else {
            cancelRemainingTasks();
            return false;
          }
        }

        // We didn't do any work, and we have nothing more we can/need to do.
        break;
      }
    }

    return true;
  }

  /// Attempt to resolve a cycle which has called the engine to be unable to make forward
  /// progress.
  ///
  /// \param buildKey The key which was requested to build (the reported cycle
  /// with start with this node).
  /// \returns True if the engine should try to proceed, false if the build the could not
  /// be broken.
  bool resolveCycle(const KeyType& buildKey) {
    // Take all available locks, to ensure we dump a consistent state.
    std::lock_guard<std::mutex> guard1(taskInfosMutex);
    std::lock_guard<std::mutex> guard2(finishedTaskInfosMutex);

    std::vector<Rule*> cycleList = findCycle(buildKey);
    assert(!cycleList.empty());

    if (breakCycle(cycleList))
      return true;

    delegate.cycleDetected(cycleList);
    return false;
  }

  std::vector<Rule*> findCycle(const KeyType& buildKey) {
    TracingEngineQueueItemEvent i(EngineQueueItemKind::FindingCycle, buildKey.c_str());

    // Gather all of the successor relationships.
    std::unordered_map<Rule*, std::vector<Rule*>> successorGraph;
    std::vector<const RuleScanRecord *> activeRuleScanRecords;
    for (const auto& it: taskInfos) {
      const TaskInfo& taskInfo = it.second;
      assert(taskInfo.forRuleInfo);
      std::vector<Rule*> successors;
      for (const auto& request: taskInfo.requestedBy) {
        assert(request.taskInfo->forRuleInfo);
        successors.push_back(request.taskInfo->forRuleInfo->rule.get());
      }
      for (const auto& request: taskInfo.deferredScanRequests) {
        // Add the sucessor for the deferred relationship itself.
        successors.push_back(request.ruleInfo->rule.get());
      }
      successorGraph.insert({ taskInfo.forRuleInfo->rule.get(), successors });
    }

    // Add the pending scan records for every rule.
    //
    // NOTE: There is a very subtle condition around this versus adding the ones
    // accessible via the tasks, see https://bugs.swift.org/browse/SR-1948.
    // Unfortunately, we do not have a test case for this!
    for (const auto& it: ruleInfos) {
      const RuleInfo& ruleInfo = it.second;
      if (ruleInfo.isScanning()) {
        const auto* scanRecord = ruleInfo.getPendingScanRecord();
        activeRuleScanRecords.push_back(scanRecord);
      }
    }

    // Gather dependencies from all of the active scan records.
    std::unordered_set<const RuleScanRecord*> visitedRuleScanRecords;
    while (!activeRuleScanRecords.empty()) {
      const auto* record = activeRuleScanRecords.back();
      activeRuleScanRecords.pop_back();

      // Mark the record and ignore it if not scanned.
      if (!visitedRuleScanRecords.insert(record).second)
        continue;

      // For each paused request, add the dependency.
      for (const auto& request: record->pausedInputRequests) {
        if (request.taskInfo) {
          successorGraph[request.inputRuleInfo->rule.get()].push_back(request.taskInfo->forRuleInfo->rule.get());
        }
      }

      // Process the deferred scan requests.
      for (const auto& request: record->deferredScanRequests) {
        // Add the sucessor for the deferred relationship itself.
        successorGraph[request.inputRuleInfo->rule.get()].push_back(request.ruleInfo->rule.get());

        // Add the active rule scan record which needs to be traversed.
        assert(request.ruleInfo->isScanning() || request.ruleInfo->wasForced);
        if (request.ruleInfo->isScanning()) {
          activeRuleScanRecords.push_back(
            request.ruleInfo->getPendingScanRecord());
        }
      }
    }

    // Invert the graph, so we can search from the root.
    std::unordered_map<Rule*, std::vector<Rule*>> predecessorGraph;
    for (auto& entry: successorGraph) {
      Rule* node = entry.first;
      for (auto& succ: entry.second) {
        predecessorGraph[succ].push_back(node);
      }
    }

    // Normalize predecessor order, to ensure a deterministic result (at least,
    // if the graph reaches the same cycle).
    for (auto& entry: predecessorGraph) {
      std::sort(entry.second.begin(), entry.second.end(), [](Rule* a, Rule* b) {
        return a->key < b->key;
      });
    }

    // Find the cycle by searching from the entry node.
    struct WorkItem {
      WorkItem(Rule * node) { this->node = node; }

      Rule* node;
      unsigned predecessorIndex = 0;
    };
    std::vector<Rule*> cycleList;
    std::unordered_set<Rule*> cycleItems;
    std::vector<WorkItem> stack{
      WorkItem{ getRuleInfoForKey(buildKey).rule.get() } };
    while (!stack.empty()) {
      // Take the top item.
      auto& entry = stack.back();
      const auto& predecessors = predecessorGraph[entry.node];

      // If the index is 0, we just started visiting the node.
      if (entry.predecessorIndex == 0) {
        // Push the node on the stack.
        cycleList.push_back(entry.node);
        auto it = cycleItems.insert(entry.node);

        // If the node is already in the stack, we found a cycle.
        if (!it.second)
          break;
      }

      // Visit the next predecessor, if possible.
      if (entry.predecessorIndex != predecessors.size()) {
        auto* child = predecessors[entry.predecessorIndex];
        entry.predecessorIndex += 1;
        stack.emplace_back(WorkItem{ child });
        continue;
      }

      // Otherwise, we are done visiting this node.
      cycleItems.erase(entry.node);
      cycleList.pop_back();
      stack.pop_back();
    }

    return cycleList;
  }

  bool breakCycle(const std::vector<Rule*>& cycleList) {
    // BreakingCycle doesn't need a key since it will not be called in parallel
    TracingEngineQueueItemEvent _(EngineQueueItemKind::BreakingCycle, "0");

    // Search the cycle for potential means for breaking the cycle. Right now
    // we use two principle approaches, force a rule to be built (skipping
    // scanning its dependencies) and supply a previously built result.
    for (auto ruleIt = cycleList.rbegin(); ruleIt != cycleList.rend(); ruleIt++) {
      auto& ruleInfo = getRuleInfoForKey((*ruleIt)->key);

      // If this rule is scanning, try to force a rebuild to break the cycle
      if (ruleInfo.isScanning()) {
        // Ask the delegate if we should try to resolve this cycle by forcing
        // a rule to be built?
        if (!delegate.shouldResolveCycle(cycleList, ruleInfo.rule.get(), Rule::CycleAction::ForceBuild))
          return false;

        if (trace) {
          trace->cycleForceRuleNeedsToRun(ruleInfo.rule.get());
        }

        // Find the rule scan request, if not already deferred, for this rule
        // and remove it. If the rule scan request was already deferred, we use
        // the wasForced condition to ignore it later.
        auto it = findRuleScanRequestForRule(ruleInfosToScan, &ruleInfo);
        if (it != ruleInfosToScan.end()) {
          ruleInfosToScan.erase(it);
        }

        // mark this rule as needs to run (forced)
        finishScanRequest(ruleInfo, RuleInfo::StateKind::NeedsToRun);
        delegate.determinedRuleNeedsToRun(ruleInfo.rule.get(), Rule::RunReason::Forced, nullptr);
        ruleInfo.wasForced = true;

        return true;
      }

      // Check if this rule has a (potentially) valid previous result and if so
      // try to provide it to the node requesting it to break the cycle.
      if (ruleInfo.isInProgressWaiting() && ruleInfo.result.builtAt != 0) {
        auto* taskInfo = ruleInfo.getPendingTaskInfo();

        // find downstream node in the cycle that wants this input
        auto& nextRuleInfo = getRuleInfoForKey((*std::next(ruleIt))->key);

        // find the corresponding request on this task
        auto it = findTaskInputRequestForRule(taskInfo->requestedBy, &nextRuleInfo);
        if (it == taskInfo->requestedBy.end()) {
          // this rule has not generated an input request yet, so we cannot
          // provide a value to it
          continue;
        }

        // Ask the delegate if we should try to resolve this cycle by supplying
        // a prior value?
        if (!delegate.shouldResolveCycle(cycleList, ruleInfo.rule.get(), Rule::CycleAction::SupplyPriorValue))
          return false;

        // supply the prior value to the node
        if (trace) {
          trace->cycleSupplyPriorValue(ruleInfo.rule.get(), it->taskInfo->task.get());
        }
        it->forcePriorValue = true;
        finishedInputRequests.insert(finishedInputRequests.end(), *it);

        // remove this request from the task info
        taskInfo->requestedBy.erase(it);
        return true;
      }
    }

    return false;
  }

  // Helper function for breakCycle, finds a rule in a RuleScanRequest vector
  std::vector<RuleScanRequest>::iterator findRuleScanRequestForRule(
    std::vector<RuleScanRequest>& requests, RuleInfo* ruleInfo) {
    for (auto it = requests.begin(); it != requests.end(); it++) {
      if (it->ruleInfo == ruleInfo) {
        return it;
      }
    }

    return requests.end();
  }

  // Helper function for breakCycle, finds a rule in a TaskInputRequest vector
  std::vector<TaskInputRequest>::iterator findTaskInputRequestForRule(
    std::vector<TaskInputRequest>& requests, RuleInfo* ruleInfo)  {
    for (auto it = requests.begin(); it != requests.end(); it++) {
      if (it->taskInfo->forRuleInfo == ruleInfo) {
        return it;
      }
    }

    return requests.end();
  }

  // Cancel all of the remaining tasks.
  void cancelRemainingTasks() {
    // We need to wait for any currently running tasks to be reported as
    // complete. Not doing this would mean we could get asynchronous calls
    // attempting to modify the task state concurrently with the cancellation
    // process, which isn't something we want to need to synchronize on.
    //
    // We don't process the requests at all, we simply drain them. In practice,
    // we expect clients to implement cancellation in conjection with causing
    // long-running tasks to also cancel and fail, so preserving those results
    // is not valuable.
    while (numOutstandingUnfinishedTasks != 0) {
        std::unique_lock<std::mutex> lock(finishedTaskInfosMutex);
        if (finishedTaskInfos.empty()) {
          finishedTaskInfosCondition.wait(lock);
        } else {
          assert(finishedTaskInfos.size() <= numOutstandingUnfinishedTasks);
          numOutstandingUnfinishedTasks -= finishedTaskInfos.size();
          finishedTaskInfos.clear();
        }
    }

    std::lock_guard<std::mutex> guard(taskInfosMutex);

    for (auto& it: taskInfos) {
      // Cancel the task, marking it incomplete.
      //
      // This will force it to rerun in a later build, but since it was already
      // running in this build that was almost certainly going to be
      // required. Technically, there are rare situations where it wouldn't have
      // to rerun (e.g., if resultIsValid becomes true after being false in this
      // run), and if we were willing to restore the tasks state--either by
      // keeping the old one or by restoring from the database--we could ensure
      // that doesn't happen.
      //
      // NOTE: Actually, we currently don't sync this write to the database, so
      // in some cases we do actually preserve this information (if the client
      // ends up cancelling, then reloading froom the database).
      TaskInfo* taskInfo = &it.second;
      RuleInfo* ruleInfo = taskInfo->forRuleInfo;
      assert(taskInfo == ruleInfo->getPendingTaskInfo());
      ruleInfo->setPendingTaskInfo(nullptr);
      ruleInfo->setCancelled();
    }

    // FIXME: This is currently an O(n) operation that could be relatively
    // expensive on larger projects.  We should be able to do something more
    // targeted. rdar://problem/39386591
    for (auto& it: ruleInfos) {
      // Cancel outstanding activity on rules
      if (it.second.isScanning()) {
        it.second.setCancelled();
      }
    }

    // Delete all of the tasks.
    ruleInfosToScan.clear();
    inputRequests.clear();
    finishedInputRequests.clear();
    readyTaskInfos.clear();
    finishedTaskInfos.clear();
    taskInfos.clear();
  }

public:
  BuildEngineImpl(class BuildEngine& buildEngine,
                  BuildEngineDelegate& delegate)
    : buildEngine(buildEngine), delegate(delegate) {}

  ~BuildEngineImpl() {
    // Make sure that there aren't any currently running builds before
    // tearing down.
    std::lock_guard<std::mutex> lock(buildEngineMutex);
  }

  BuildEngineDelegate* getDelegate() {
    return &delegate;
  }

  ExecutionQueue& getExecutionQueue() {
    return *executionQueue;
  }

  Epoch getCurrentEpoch() {
    return currentEpoch;
  }

  // When changing the implementation of those, do also copy
  // the changes to CAPIBuildDB.
  virtual const KeyID getKeyID(const KeyType& key) override {
    std::lock_guard<std::mutex> guard(keyTableMutex);

    // The RHS of the mapping is actually ignored, we use the StringMap's ptr
    // identity because it allows us to efficiently map back to the key string
    // in `getRuleInfoForKey`.
    auto it = keyTable.insert(std::make_pair(key.str(), KeyID::novalue())).first;
    return KeyID(it->getKey().data());
  }

  virtual KeyType getKeyForID(const KeyID key) override {
    // Note that we don't need to lock `keyTable` here because the key entries
    // themselves don't change once created.
    return llvm::StringMapEntry<KeyID>::GetStringMapEntryFromKeyData(
      (const char*)(uintptr_t)key).getKey();
  }

  RuleInfo& getRuleInfoForKey(const KeyType& key) {
    auto keyID = getKeyID(key);

    // Check if we have already found the rule.
    auto it = ruleInfos.find(keyID);
    if (it != ruleInfos.end())
      return it->second;

    // Otherwise, request it from the delegate and add it.
    return addRule(keyID, delegate.lookupRule(key));
  }

  RuleInfo& getRuleInfoForKey(KeyID keyID) {
    // Check if we have already found the rule.
    auto it = ruleInfos.find(keyID);
    if (it != ruleInfos.end())
      return it->second;

    // Otherwise, we need to resolve the full key so we can request it from the
    // delegate.
    return addRule(keyID, delegate.lookupRule(getKeyForID(keyID)));
  }

  TaskInfo* getTaskInfo(Task* task) {
    std::lock_guard<std::mutex> guard(taskInfosMutex);
    auto it = taskInfos.find(task);
    return it == taskInfos.end() ? nullptr : &it->second;
  }

  /// @name Rule Definition
  /// @{

  RuleInfo& addRule(std::unique_ptr<Rule>&& rule) {
    return addRule(getKeyID(rule->key), std::move(rule));
  }

  RuleInfo& addRule(KeyID keyID, std::unique_ptr<Rule>&& rule) {
    auto result = ruleInfos.emplace(keyID, RuleInfo(keyID, std::move(rule)));
    if (!result.second) {
      RuleInfo& ruleInfo = result.first->second;
      delegate.error("attempt to register duplicate rule \"" + ruleInfo.rule->key.str() + "\"\n");

      // Set cancelled, but return something 'valid' for use until it is
      // processed.
      buildCancelled = true;
      return ruleInfo;
    }

    // If we have a database attached, retrieve any stored result.
    //
    // FIXME: Investigate retrieving this result lazily. If the DB is
    // particularly efficient, it may be best to retrieve this only when we need
    // it and never duplicate it.
    RuleInfo& ruleInfo = result.first->second;
    if (db) {
      std::string error;
      db->lookupRuleResult(ruleInfo.keyID, *ruleInfo.rule, &ruleInfo.result, &error);
      if (!error.empty()) {
        // FIXME: Investigate changing the database error handling model to
        // allow builds to proceed without the database.
        delegate.error(error);
        buildCancelled = true;
      }
    }

    return ruleInfo;
  }

  /// @}

  /// @name Client API
  /// @{

  const ValueType& build(const KeyType& key) {
    // Soft protect the engine against invalid concurrent use.
    if (buildRunning.exchange(true)) {
      delegate.error("build engine busy");
      static ValueType emptyValue{};
      return emptyValue;
    }
    llbuild_defer {
      buildRunning = false;
    };

    // Hard protection against concurrent use and tear down
    std::lock_guard<std::mutex> lock(buildEngineMutex);

    if (db) {
      std::string error;
      bool result = db->buildStarted(&error);
      if (!result) {
        delegate.error(error);
        static ValueType emptyValue{};
        return emptyValue;
      }
    }
    llbuild_defer {
      if (db)
        db->buildComplete();
    };

    // Aquire lock and create execution queue.
    {
      std::lock_guard<std::mutex> guard(executionQueueMutex);
      if (buildCancelled) {
        static ValueType emptyValue{};
        return emptyValue;
      }
      executionQueue = delegate.createExecutionQueue();
    }

    llbuild_defer {
      // Release the execution queue, impicitly waiting for it to complete. The
      // asynchronous nature of the engine callbacks means it is possible for
      // the queue to have notified the engine of the last task completion, but
      // still have other work to perform (e.g., informing the client of command
      // completion).
      //
      // This must hold the lock to prevent data racing on the executionQueue
      // pointer (as can happen with cancellation) - rdar://problem/50993380
      std::lock_guard<std::mutex> guard(executionQueueMutex);
      executionQueue.reset();
    };

    // Increment our running iteration count.
    //
    // At this point, we should conceptually mark each complete rule as
    // incomplete. However, instead of doing all that work immediately, we
    // perform it lazily by reusing the Result::builtAt field for each rule as
    // an additional mark. When a rule is demanded, if its builtAt index isn't
    // up-to-date then we lazily reset it to be Incomplete, \see demandRule()
    // and \see RuleInfo::isComplete().
    ++currentEpoch;

    if (!traceFile.empty()) {
      auto trace = llvm::make_unique<BuildEngineTrace>();

      std::string error;
      if (!trace->open(traceFile, &error))
        delegate.error(error);

      this->trace = std::move(trace);
    }

    llbuild_defer {
      std::string error;
      if (trace && trace->isOpen() && !trace->close(&error)) {
        delegate.error(error);
      }

      trace = nullptr;
    };

    if (trace)
      trace->buildStarted();


    llbuild_defer {
      // Clear the rule scan free-lists.
      //
      // FIXME: Introduce a per-build context object to hold this.
      for (auto block: ruleScanRecordBlocks)
        delete[] block;
      currentBlockPos = currentBlockEnd = nullptr;
      freeRuleScanRecords.clear();
      ruleScanRecordBlocks.clear();
    };

    // Run the build engine, to process any necessary tasks.
    bool success = executeTasks(key);

    // Update the build database, if attached.
    //
    // FIXME: Is it correct to do this here, or earlier?
    if (db) {
      std::string error;
      bool result = db->setCurrentIteration(currentEpoch, &error);
      if (!result) {
        delegate.error(error);
        static ValueType emptyValue{};
        return emptyValue;
      }
    }

    if (trace)
      trace->buildEnded();

    // If the build failed, return the empty result.
    if (!success) {
      static ValueType emptyValue{};
      return emptyValue;
    }

    // The task queue should be empty and the rule complete.
    auto& ruleInfo = getRuleInfoForKey(key);
    assert(taskInfos.empty() && ruleInfo.isComplete(this));
    return ruleInfo.result.value;
  }

  void resetForBuild() {
    std::lock_guard<std::mutex> guard(executionQueueMutex);
    buildCancelled = false;
  }

  void cancelBuild() {
    std::lock_guard<std::mutex> guard(executionQueueMutex);

    if (!buildCancelled) {
      for (const auto &del : cancellationDelegates) {
        del->buildCancelled();
      }
    }

    // Set the build cancelled marker.
    //
    // We do not need to handle waking the engine up, if it is waiting, because
    // our current cancellation model requires us to wait for all outstanding
    // tasks in any case.
    buildCancelled = true;

    // Cancel jobs if we actually have a queue.
    if (executionQueue.get() != nullptr) {
      // Ask the execution queue to cancel currently running jobs.
      executionQueue->cancelAllJobs();
    }
  }

  bool isCancelled() {
    return buildCancelled;
  }

  void addCancellationDelegate(CancellationDelegate* del) {
    std::lock_guard<std::mutex> guard(executionQueueMutex);
    if (buildCancelled) {
      del->buildCancelled();
      return;
    }
    cancellationDelegates.insert(del);
  }

  void removeCancellationDelegate(CancellationDelegate* del) {
    std::lock_guard<std::mutex> guard(executionQueueMutex);
    cancellationDelegates.erase(del);
  }

  bool attachDB(std::unique_ptr<BuildDB> database, std::string* error_out) {
    assert(!db && "invalid attachDB() call");
    assert(currentEpoch == 0 && "invalid attachDB() call");
    assert(ruleInfos.empty() && "invalid attachDB() call");
    db = std::move(database);
    db->attachDelegate(this);

    // Load our initial state from the database.
    bool success;
    currentEpoch = db->getCurrentEpoch(&success, error_out);
    return success;
  }

  bool enableTracing(const std::string& filename, std::string* error_out) {
    traceFile = filename;
    return true;
  }

  /// Dump the build state to a file in Graphviz DOT format.
  void dumpGraphToFile(const std::string& path) {
    FILE* fp = ::fopen(path.c_str(), "w");
    if (!fp) {
      delegate.error("unable to open graph output path \"" + path + "\"");
      return;
    }

    // Write the graph header.
    fprintf(fp, "digraph llbuild {\n");
    fprintf(fp, "rankdir=\"LR\"\n");
    fprintf(fp, "node [fontsize=10, shape=box, height=0.25]\n");
    fprintf(fp, "edge [fontsize=10]\n");
    fprintf(fp, "\n");

    // Create a canonical node ordering.
    std::vector<const RuleInfo*> orderedRuleInfos;
    for (const auto& entry: ruleInfos)
      orderedRuleInfos.push_back(&entry.second);
    std::sort(orderedRuleInfos.begin(), orderedRuleInfos.end(),
              [] (const RuleInfo* a, const RuleInfo* b) {
        return a->rule->key < b->rule->key;
      });

    // Write out all of the rules.
    for (const auto& ruleInfo: orderedRuleInfos) {
      fprintf(fp, "\"%s\"\n", ruleInfo->rule->key.c_str());
      for (auto keyIDAndFlag: ruleInfo->result.dependencies) {
        const auto& dependency = getRuleInfoForKey(keyIDAndFlag.keyID);
        fprintf(fp, "\"%s\" -> \"%s\"\n", ruleInfo->rule->key.c_str(),
                dependency.rule->key.c_str());
      }
      fprintf(fp, "\n");
    }

    // Write the footer and close.
    fprintf(fp, "}\n");
    fclose(fp);
  }

  void addTaskInputRequest(Task* task, const KeyType& key, uintptr_t inputID, bool orderOnly, bool singleUse) {
    auto taskInfo = getTaskInfo(task);

    // Validate that the task is in a valid state to request inputs.
    if (!taskInfo->forRuleInfo->isInProgressWaiting()) {
      // FIXME: Error handling.
      abort();
    }

    // Lookup the rule for this task.
    RuleInfo* ruleInfo = &getRuleInfoForKey(key);

    std::lock_guard<std::mutex> guard(inputRequestsMutex);
    inputRequests.push_back({ taskInfo, inputID, ruleInfo, orderOnly, false, singleUse });
    taskInfo->waitCount++;
  }

  /// @}

  /// @name Task Management Client APIs
  /// @{

  void taskNeedsInput(Task* task, const KeyType& key, uintptr_t inputID) {
    // Validate the InputID.
    if (inputID > BuildEngine::kMaximumInputID) {
      delegate.error("attempt to use reserved input ID");
      buildCancelled = true;
      return;
    }

    addTaskInputRequest(task, key, inputID, false, false);
  }
  
  void taskNeedsSingleUseInput(Task* task, const KeyType& key, uintptr_t inputID) {
    // Validate the InputID.
    if (inputID > BuildEngine::kMaximumInputID) {
      delegate.error("attempt to use reserved input ID");
      buildCancelled = true;
      return;
    }

    addTaskInputRequest(task, key, inputID, false, true);
  }

  void taskMustFollow(Task* task, const KeyType& key) {
    // The inputID is not used when taskMustFollow is used.
    // (The user-supplied provideValue() is not called).
    addTaskInputRequest(task, key, kMustFollowInputID, true, false);
  }

  void taskDiscoveredDependency(Task* task, const KeyType& key) {
    // Find the task info.
    auto taskInfo = getTaskInfo(task);
    assert(taskInfo && "cannot request inputs for an unknown task");

    if (!taskInfo->forRuleInfo->isInProgressComputing()) {
      delegate.error("invalid state for adding discovered dependency");
      buildCancelled = true;
      return;
    }

    auto dependencyID = getKeyID(key);
    taskInfo->discoveredDependencies.push_back(dependencyID, false, false);
  }

  void taskIsComplete(Task* task, ValueType&& value, bool forceChange) {
    // FIXME: We should flag the task to ensure this is only called once, and
    // that no other API calls are made once complete.

    auto taskInfo = getTaskInfo(task);
    assert(taskInfo && "cannot request inputs for an unknown task");

    if (!taskInfo->forRuleInfo->isInProgressComputing()) {
      delegate.error("invalid state for marking task complete");
      buildCancelled = true;
      return;
    }

    RuleInfo* ruleInfo = taskInfo->forRuleInfo;
    assert(taskInfo == ruleInfo->getPendingTaskInfo());

    // Update the signature of the result (even if we ultimately computed the
    // same value).
    ruleInfo->result.signature = ruleInfo->rule->signature;

    // Process the provided result.
    if (!forceChange && value == ruleInfo->result.value) {
        // If the value is unchanged, do nothing.
    } else {
        // Otherwise, updated the result and the computed at time.
        ruleInfo->result.value = std::move(value);
        ruleInfo->result.computedAt = currentEpoch;
    }

    // Enqueue the finished task.
    {
      std::lock_guard<std::mutex> guard(finishedTaskInfosMutex);
      finishedTaskInfos.push_back(taskInfo);
    }

    // Notify the engine to wake up, if necessary.
    finishedTaskInfosCondition.notify_one();
  }

  /// @}

  /// @name Internal APIs
  /// @{

  Epoch getCurrentEpoch() const { return currentEpoch; }

  /// @}
};

}

#pragma mark - TaskInterface

Epoch TaskInterface::currentEpoch() {
  return static_cast<BuildEngineImpl*>(impl)->getCurrentEpoch();
}

bool TaskInterface::isCancelled() {
  return static_cast<BuildEngineImpl*>(impl)->isCancelled();
}

BuildEngineDelegate* TaskInterface::delegate() {
  return static_cast<BuildEngineImpl*>(impl)->getDelegate();
}

void TaskInterface::request(const KeyType& key, uintptr_t inputID) {
  Task* task = static_cast<Task*>(ctx);
  static_cast<BuildEngineImpl*>(impl)->taskNeedsInput(task, key, inputID);
}

void TaskInterface::requestSingleUse(const KeyType &key, uintptr_t inputID) {
  Task* task = static_cast<Task*>(ctx);
  static_cast<BuildEngineImpl*>(impl)->taskNeedsSingleUseInput(task, key, inputID);
}

void TaskInterface::mustFollow(const KeyType& key) {
  Task* task = static_cast<Task*>(ctx);
  static_cast<BuildEngineImpl*>(impl)->taskMustFollow(task, key);
}

void TaskInterface::discoveredDependency(const KeyType& key) {
  Task* task = static_cast<Task*>(ctx);
  static_cast<BuildEngineImpl*>(impl)->taskDiscoveredDependency(task, key);
}

void TaskInterface::complete(ValueType &&value, bool forceChange) {
  Task* task = static_cast<Task*>(ctx);
  static_cast<BuildEngineImpl*>(impl)->taskIsComplete(task, std::move(value),
                                                      forceChange);
}

void TaskInterface::spawn(basic::QueueJob&& job, basic::QueueJobPriority priority) {
  // FIXME: handle environment
  static_cast<BuildEngineImpl*>(impl)->getExecutionQueue().addJob(std::move(job), priority);
}

void TaskInterface::spawn(basic::QueueJobContext *context,
                          ArrayRef<StringRef> commandLine,
                          ArrayRef<std::pair<StringRef, StringRef> > environment,
                          basic::ProcessAttributes attributes,
                          llvm::Optional<basic::ProcessCompletionFn> completionFn,
                          basic::ProcessDelegate* delegate) {
  static_cast<BuildEngineImpl*>(impl)->getExecutionQueue().executeProcess(
    context, commandLine, environment, attributes, completionFn, delegate);
}

basic::ProcessStatus TaskInterface::spawn(basic::QueueJobContext *context,
                                          ArrayRef<StringRef> commandLine) {
  // FIXME: handle environment
  return static_cast<BuildEngineImpl*>(impl)->getExecutionQueue().executeProcess(
    context, commandLine);
}

#pragma mark - BuildEngine

BuildEngine::BuildEngine(BuildEngineDelegate& delegate)
  : impl(new BuildEngineImpl(*this, delegate))
{
}

BuildEngine::~BuildEngine() {
  delete static_cast<BuildEngineImpl*>(impl);
}

BuildEngineDelegate* BuildEngine::getDelegate() {
  return static_cast<BuildEngineImpl*>(impl)->getDelegate();
}

Epoch BuildEngine::getCurrentEpoch() {
  return static_cast<BuildEngineImpl*>(impl)->getCurrentEpoch();
}

void BuildEngine::addRule(std::unique_ptr<Rule>&& rule) {
  static_cast<BuildEngineImpl*>(impl)->addRule(std::move(rule));
}

const ValueType& BuildEngine::build(const KeyType& key) {
  return static_cast<BuildEngineImpl*>(impl)->build(key);
}

void BuildEngine::resetForBuild() {
  static_cast<BuildEngineImpl*>(impl)->resetForBuild();
}

void BuildEngine::cancelBuild() {
  static_cast<BuildEngineImpl*>(impl)->cancelBuild();
}

bool BuildEngine::isCancelled() {
  return static_cast<BuildEngineImpl*>(impl)->isCancelled();
}

void BuildEngine::addCancellationDelegate(CancellationDelegate* del) {
  static_cast<BuildEngineImpl*>(impl)->addCancellationDelegate(std::move(del));
}

void BuildEngine::removeCancellationDelegate(CancellationDelegate* del) {
  static_cast<BuildEngineImpl*>(impl)->removeCancellationDelegate(del);
}

void BuildEngine::dumpGraphToFile(const std::string& path) {
  static_cast<BuildEngineImpl*>(impl)->dumpGraphToFile(path);
}

bool BuildEngine::attachDB(std::unique_ptr<BuildDB> database, std::string* error_out) {
  return static_cast<BuildEngineImpl*>(impl)->attachDB(std::move(database), error_out);
}

bool BuildEngine::enableTracing(const std::string& path,
                                std::string* error_out) {
  return static_cast<BuildEngineImpl*>(impl)->enableTracing(path, error_out);
}