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 the critical path of a given 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.
  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 }.
  using GetEdgeInputsFunc = std::function<EdgePtrList(EdgePtr)>;

 public:
  /// Result of a Compute() call, which can be an ordered list of
  /// edges, on success, or an error message, on failure.
  struct Result {
    EdgePtrList critical_path;
    std::string error;

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

    /// Return true if this instance contains a valid path.
    bool HasPath() const { return !HasError(); }

    /// Create new instance holding a path.
    static Result MakePath(EdgePtrList&& critical_path) {
      return { std::move(critical_path), {} };
    }

    /// Creating new instance storing an error message.
    static Result MakeError(std::string&& msg) {
      return { {}, std::move(msg) };
    }
  };

  /// 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. On success, its HasPath()
  static Result Compute(const std::vector<BuiltEdgeInfo>& built_edges,
                        GetEdgeInputsFunc get_edge_inputs,
                        GetEdgeNameFunc get_edge_name);
};

#endif  // NINJA_CRITICAL_PATH_H_