src/critical_path.h

// 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.

#ifndef NINJA_CRITICAL_PATH_H_
#define NINJA_CRITICAL_PATH_H_

#include <inttypes.h>

#include <functional>
#include <string>
#include <vector>

/// A class used to compute a critical path from a given build.
/// Note that any build has at least one critical path.
///
/// This also computes the float value for each edge in the
/// build.
struct CriticalPath {
  /// All edges are described as opaque pointers, whose properties
  /// are queried through GetEdgeXXXFunc() getter functions.
  using EdgePtr = const void*;

  /// An ordered list of edges, e.g. a critical path.
  using EdgePtrList = std::vector<EdgePtr>;

  /// Information about edge start and stop times, used as input
  /// for the Compute() function.
  struct BuiltEdgeInfo {
    EdgePtr edge;
    int64_t start_time_ms;
    int64_t stop_time_ms;
  };

  /// A callable that returns the name of a given edge.
  /// Only used in case of error.
  using GetEdgeNameFunc = std::function<std::string(EdgePtr)>;

  /// A callable that returns the non-phony input edges of a
  /// given input edge. This must collect transitive inputs of
  /// phony edges, but stop at non-phony ones. For example
  /// if edgeA --> edgeB(phony) --> [edgeC, edgeD]
  /// then get_edge_input(edgeA) should return { edgeC, edgeD }.
  /// Edges in the result that were not part of the build will be
  /// ignored.
  using GetEdgeInputsFunc = std::function<EdgePtrList(EdgePtr)>;

 public:
  /// Result of a Compute() call. In case of success, this returns
  /// one critical path, and the float values for all edges, and
  /// an empty error string. On failure, only set the error string.
  struct Result {
    /// One critical path for the input build.
    EdgePtrList critical_path;

    /// The float values for all input built edges.
    /// floats[n] is the value for built_edges[n].
    std::vector<int64_t> floats;

    /// Empty on success, error message on failure.
    std::string error;

    /// Return true if this instance contains an error message.
    bool HasError() const { return !error.empty(); }

    /// Return true if this instance contains values.
    bool HasValues() const { return !HasError(); }
  };

  /// Compute the critical path of a given build.
  /// @arg built_edges is a list of BuiltEdgeInfo values describing when
  /// each edge was started and stopped in the current build.
  /// @arg get_edge_inputs is a callable that returns the list of
  /// non-phony input edges for a given edge.
  /// @arg get_edge_name is a callable that returns a name for the
  /// a given edge, used in error messages.
  ///
  /// This returns a Result value.
  static Result Compute(const std::vector<BuiltEdgeInfo>& built_edges,
                        GetEdgeInputsFunc get_edge_inputs,
                        GetEdgeNameFunc get_edge_name);
};

#endif  // NINJA_CRITICAL_PATH_H_