src/critical_path.cc

// Copyright 2025 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "critical_path.h"

#include <algorithm>
#include <unordered_map>

#include "util.h"

// Set to 1 to print debug traces.
#define DEBUG 0

#if DEBUG
#include <stdio.h>
#endif  // DEBUG

// static
CriticalPath::Result CriticalPath::Compute(
    const std::vector<BuiltEdgeInfo>& built_edges,
    CriticalPath::GetEdgeInputsFunc get_edge_inputs,
    CriticalPath::GetEdgeNameFunc get_edge_name) {
  struct EdgeTimings {
    // edge/command duration in milliseconds
    int64_t duration_ms = 0;

    // The minimal time it takes to complete this edge in *any* build.
    // This only depends on the duration of its inputs, and ignores
    // the start/stop timestamps provided as input intentionally, as
    // these are influenced by external factors like cpu or i/o contention
    // or even Ninja pools.
    int64_t critical_build_time_ms = 0;

    // The input edge that has the higher critical_build_time_ms or nullptr.
    EdgePtr critical_input_edge = nullptr;

    // The earliest time, in milliseconds, that this edge can complete
    // without impacting build time. This depends on the earliest finish time
    // of all its inputs.
    int64_t earliest_finish_ms = 0;

    // The latest time, in milliseconds, that this edge can complete without
    // impacting build time. This depends on the earliest start time of all
    // its successors.
    int64_t latest_finish_ms = 0;

    // The earliest time, in milliseconds, that this edge can start.
    int64_t earliest_start_ms() const {
      return earliest_finish_ms - duration_ms;
    }

    // The latest time, in milliseconds, that this edge can start.
    int64_t latest_start_ms() const { return latest_finish_ms - duration_ms; }

    // The float, also called slack, is the time, in milliseconds, that this
    // edge's start time can be moved without impacting build time. Edges on
    // a critical path have a value of 0.
    // See https://en.wikipedia.org/wiki/Critical_path_method.
    int64_t float_value() const {
      return latest_finish_ms - earliest_finish_ms;
    }
  };
  Result result;
  result.floats.reserve(built_edges.size());

  // A map recording timing values for each edge for the computations
  // below. It is important to use std::unordered_map<> here for
  // the build_order variable definition below.
  using EdgeTimingsMap = std::unordered_map<EdgePtr, EdgeTimings>;
  EdgeTimingsMap edge_timings;

  // A vector to (edge, timings) in build order to avoid
  // repeated map lookups during the forward and backwards passes.
  // This leverages the fact that std::unordered_map<> provides
  // pointer stability to its elements, even in the case of
  // re-hashing.
  using EdgeTimingsPairPtr = EdgeTimingsMap::value_type*;
  std::vector<EdgeTimingsPairPtr> build_order;

  // A map recording the list of successors for each build edge.
  // This really points to the (edge, info) pair in |edge_timings| for
  // each successor to avoid unnecessary lookups.
  // Used to perform the backwards pass required to compute float values.
  std::unordered_map<EdgePtr, std::vector<EdgeTimingsPairPtr>> successors;

  int64_t max_stop_time_ms = 0;

  // A vector reused in each loop iteration to store the predecessors
  // of each edge (i.e. its inputs that are also part of the build).
  EdgePtrList predecessors;

  // A forward pass, used to perform several tasks:
  // - Verify that built_edges is properly ordered in non-decreasing
  //   stop_time_ms values.
  // - Verify that an edge doesn't appear several times in the input.
  // - Compute the earliest start and finish times for each edge.
  // - Retrieve static inputs and filter out those that are not part of
  //   built_edges.
  for (const auto& info : built_edges) {
    EdgePtr edge = info.edge;

    // Verify built_edges are ordered in increasing stop_time_ms values.
    if (info.stop_time_ms < max_stop_time_ms) {
      result.error = StringFormat("Edge %s stop time (%" PRId64
                                  ") smaller than current max (%" PRId64 ")",
                                  get_edge_name(edge).c_str(),
                                  info.stop_time_ms, max_stop_time_ms);
      return result;
    }
    max_stop_time_ms = std::max(info.stop_time_ms, max_stop_time_ms);

    int64_t duration_ms = info.stop_time_ms - info.start_time_ms;
    int64_t earliest_start_ms = 0;
    int64_t critical_build_time_ms = 0;
    EdgePtr critical_input_edge = 0;

    predecessors.clear();
    for (EdgePtr input : get_edge_inputs(edge)) {
      auto input_it = edge_timings.find(input);
      if (input_it == edge_timings.end())
        continue;

      auto& input_timings = input_it->second;
      earliest_start_ms =
          std::max(earliest_start_ms, input_timings.earliest_finish_ms);

      if (critical_build_time_ms < input_timings.critical_build_time_ms) {
        critical_build_time_ms = input_timings.critical_build_time_ms;
        critical_input_edge = input;
      }
      predecessors.push_back(input);
    }

    auto ret = edge_timings.emplace(
        edge, EdgeTimings{
                  duration_ms, critical_build_time_ms + duration_ms,
                  critical_input_edge, earliest_start_ms + duration_ms,
                  0,  // computed in second pass.
              });
    if (!ret.second) {
      result.error = StringFormat("Edge %s appears multiple times in input",
                                  get_edge_name(edge).c_str());
      return result;
    }

    EdgeTimingsPairPtr pair = &(*ret.first);
#if DEBUG
    fprintf(stderr, "\n==> edge %p: dur=%ld es=%ld ef=%ld bt=%ld", pair->first,
            pair->second.duration_ms, pair->second.earliest_start_ms,
            pair->second.earliest_finish_ms,
            pair->second.critical_build_time_ms);
#endif  // DEBUG
    build_order.push_back(pair);
    for (EdgePtr predecessor : predecessors)
      successors[predecessor].push_back(pair);
  }

  predecessors.clear();

  if (!build_order.empty()) {
    int64_t max_build_time_ms =
        build_order.back()->second.critical_build_time_ms;

    // Backwards pass to compute the latest start and finish times
    // for each edge.
    for (auto it = build_order.rbegin(); it != build_order.rend(); ++it) {
      EdgeTimingsPairPtr pair = *it;
      EdgePtr edge = pair->first;
      EdgeTimings& info = pair->second;
      int64_t latest_finish_ms = max_build_time_ms;

      auto successor_it = successors.find(edge);
      if (successor_it != successors.end()) {
        for (EdgeTimingsPairPtr successor_pair : successor_it->second) {
          EdgeTimings& successor_info = successor_pair->second;
          latest_finish_ms =
              std::min(latest_finish_ms, successor_info.latest_start_ms());
        }
      }
      info.latest_finish_ms = latest_finish_ms;
#if DEBUG
      fprintf(stderr,
              "\n<== edge %p: dur=%ld es=%ld ef=%ld ls=%ld lf=%ld float=%ld\n",
              edge, info.duration_ms, info.earliest_start_ms,
              info.earliest_finish_ms, info.latest_start_ms,
              info.latest_finish_ms, info.float_value());
#endif  // DEBUG
    }

    // Another backwards pass to compute a critical path, starting from
    // the last edge in the build. This should be fast as it only touches
    // a small fraction of build edges.
    EdgeTimingsPairPtr last_pair = build_order.back();
    while (true) {
      EdgePtr last_edge = last_pair->first;
      result.critical_path.push_back(last_edge);
      last_edge = last_pair->second.critical_input_edge;
      if (!last_edge)
        break;

      auto it = edge_timings.find(last_edge);
      if (it == edge_timings.end()) {
        result.error =
            StringFormat("Edge %s unknown", get_edge_name(last_edge).c_str());
        return result;
      }
      last_pair = &(*it);
    }
    // Reverse critical path array.
    std::reverse(result.critical_path.begin(), result.critical_path.end());
  }

  // Compute the floats for all edges.
  for (EdgeTimingsPairPtr pair : build_order) {
    auto& info = pair->second;
    result.floats.push_back(info.float_value());
  }

  return result;
}