v1.12.0v1.12.0

1 files changed, 89 insertions, 38 deletions

diff --git a/src/graph.h b/src/graph.h
index 9de67d2..820a265 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -19,6 +19,7 @@
 #include <set>
 #include <string>
 #include <vector>
+#include <queue>
 
 #include "dyndep.h"
 #include "eval_env.h"
@@ -38,14 +39,7 @@ struct State;
 /// it's dirty, mtime, etc.
 struct Node {
   Node(const std::string& path, uint64_t slash_bits)
-      : path_(path),
-        slash_bits_(slash_bits),
-        mtime_(-1),
-        exists_(ExistenceStatusUnknown),
-        dirty_(false),
-        dyndep_pending_(false),
-        in_edge_(NULL),
-        id_(-1) {}
+      : path_(path), slash_bits_(slash_bits) {}
 
   /// Return false on error.
   bool Stat(DiskInterface* disk_interface, std::string* err);
@@ -104,6 +98,14 @@ struct Node {
   Edge* in_edge() const { return in_edge_; }
   void set_in_edge(Edge* edge) { in_edge_ = edge; }
 
+  /// Indicates whether this node was generated from a depfile or dyndep file,
+  /// instead of being a regular input or output from the Ninja manifest.
+  bool generated_by_dep_loader() const { return generated_by_dep_loader_; }
+
+  void set_generated_by_dep_loader(bool value) {
+    generated_by_dep_loader_ = value;
+  }
+
   int id() const { return id_; }
   void set_id(int id) { id_ = id; }
 
@@ -119,13 +121,13 @@ private:
 
   /// Set bits starting from lowest for backslashes that were normalized to
   /// forward slashes by CanonicalizePath. See |PathDecanonicalized|.
-  uint64_t slash_bits_;
+  uint64_t slash_bits_ = 0;
 
   /// Possible values of mtime_:
   ///   -1: file hasn't been examined
   ///   0:  we looked, and file doesn't exist
   ///   >0: actual file's mtime, or the latest mtime of its dependencies if it doesn't exist
-  TimeStamp mtime_;
+  TimeStamp mtime_ = -1;
 
   enum ExistenceStatus {
     /// The file hasn't been examined.
@@ -135,20 +137,27 @@ private:
     /// The path is an actual file. mtime_ will be the file's mtime.
     ExistenceStatusExists
   };
-  ExistenceStatus exists_;
+  ExistenceStatus exists_ = ExistenceStatusUnknown;
 
   /// Dirty is true when the underlying file is out-of-date.
   /// But note that Edge::outputs_ready_ is also used in judging which
   /// edges to build.
-  bool dirty_;
+  bool dirty_ = false;
 
   /// Store whether dyndep information is expected from this node but
   /// has not yet been loaded.
-  bool dyndep_pending_;
+  bool dyndep_pending_ = false;
+
+  /// Set to true when this node comes from a depfile, a dyndep file or the
+  /// deps log. If it does not have a producing edge, the build should not
+  /// abort if it is missing (as for regular source inputs). By default
+  /// all nodes have this flag set to true, since the deps and build logs
+  /// can be loaded before the manifest.
+  bool generated_by_dep_loader_ = true;
 
   /// The Edge that produces this Node, or NULL when there is no
   /// known edge to produce it.
-  Edge* in_edge_;
+  Edge* in_edge_ = nullptr;
 
   /// All Edges that use this Node as an input.
   std::vector<Edge*> out_edges_;
@@ -157,7 +166,7 @@ private:
   std::vector<Edge*> validation_out_edges_;
 
   /// A dense integer id for the node, assigned and used by DepsLog.
-  int id_;
+  int id_ = -1;
 };
 
 /// An edge in the dependency graph; links between Nodes using Rules.
@@ -168,11 +177,7 @@ struct Edge {
     VisitDone
   };
 
-  Edge()
-      : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL), mark_(VisitNone),
-        id_(0), outputs_ready_(false), deps_loaded_(false),
-        deps_missing_(false), generated_by_dep_loader_(false),
-        implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {}
+  Edge() = default;
 
   /// Return true if all inputs' in-edges are ready.
   bool AllInputsReady() const;
@@ -198,19 +203,30 @@ struct Edge {
   // Append all edge explicit inputs to |*out|. Possibly with shell escaping.
   void CollectInputs(bool shell_escape, std::vector<std::string>* out) const;
 
-  const Rule* rule_;
-  Pool* pool_;
+  // critical_path_weight is the priority during build scheduling. The
+  // "critical path" between this edge's inputs and any target node is
+  // the path which maximises the sum oof weights along that path.
+  // NOTE: Defaults to -1 as a marker smaller than any valid weight
+  int64_t critical_path_weight() const { return critical_path_weight_; }
+  void set_critical_path_weight(int64_t critical_path_weight) {
+    critical_path_weight_ = critical_path_weight;
+  }
+
+  const Rule* rule_ = nullptr;
+  Pool* pool_ = nullptr;
   std::vector<Node*> inputs_;
   std::vector<Node*> outputs_;
   std::vector<Node*> validations_;
-  Node* dyndep_;
-  BindingEnv* env_;
-  VisitMark mark_;
-  size_t id_;
-  bool outputs_ready_;
-  bool deps_loaded_;
-  bool deps_missing_;
-  bool generated_by_dep_loader_;
+  Node* dyndep_ = nullptr;
+  BindingEnv* env_ = nullptr;
+  VisitMark mark_ = VisitNone;
+  size_t id_ = 0;
+  int64_t critical_path_weight_ = -1;
+  bool outputs_ready_ = false;
+  bool deps_loaded_ = false;
+  bool deps_missing_ = false;
+  bool generated_by_dep_loader_ = false;
+  TimeStamp command_start_time_ = 0;
 
   const Rule& rule() const { return *rule_; }
   Pool* pool() const { return pool_; }
@@ -225,8 +241,8 @@ struct Edge {
   //                     don't cause the target to rebuild.
   // These are stored in inputs_ in that order, and we keep counts of
   // #2 and #3 when we need to access the various subsets.
-  int implicit_deps_;
-  int order_only_deps_;
+  int implicit_deps_ = 0;
+  int order_only_deps_ = 0;
   bool is_implicit(size_t index) {
     return index >= inputs_.size() - order_only_deps_ - implicit_deps_ &&
         !is_order_only(index);
@@ -240,7 +256,7 @@ struct Edge {
   // 2) implicit outs, which the target generates but are not part of $out.
   // These are stored in outputs_ in that order, and we keep a count of
   // #2 to use when we need to access the various subsets.
-  int implicit_outs_;
+  int implicit_outs_ = 0;
   bool is_implicit_out(size_t index) const {
     return index >= outputs_.size() - implicit_outs_;
   }
@@ -248,6 +264,10 @@ struct Edge {
   bool is_phony() const;
   bool use_console() const;
   bool maybe_phonycycle_diagnostic() const;
+
+  // Historical info: how long did this edge take last time,
+  // as per .ninja_log, if known? Defaults to -1 if unknown.
+  int64_t prev_elapsed_time_millis = -1;
 };
 
 struct EdgeCmp {
@@ -295,11 +315,6 @@ struct ImplicitDepLoader {
   /// an iterator pointing at the first new space.
   std::vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
 
-  /// If we don't have a edge that generates this input already,
-  /// create one; this makes us not abort if the input is missing,
-  /// but instead will rebuild in that circumstance.
-  void CreatePhonyInEdge(Node* node);
-
   State* state_;
   DiskInterface* disk_interface_;
   DepsLog* deps_log_;
@@ -366,4 +381,40 @@ struct DependencyScan {
   DyndepLoader dyndep_loader_;
 };
 
+// Implements a less comparison for edges by priority, where highest
+// priority is defined lexicographically first by largest critical
+// time, then lowest ID.
+//
+// Including ID means that wherever the critical path weights are the
+// same, the edges are executed in ascending ID order which was
+// historically how all tasks were scheduled.
+struct EdgePriorityLess {
+  bool operator()(const Edge* e1, const Edge* e2) const {
+    const int64_t cw1 = e1->critical_path_weight();
+    const int64_t cw2 = e2->critical_path_weight();
+    if (cw1 != cw2) {
+      return cw1 < cw2;
+    }
+    return e1->id_ > e2->id_;
+  }
+};
+
+// Reverse of EdgePriorityLess, e.g. to sort by highest priority first
+struct EdgePriorityGreater {
+  bool operator()(const Edge* e1, const Edge* e2) const {
+    return EdgePriorityLess()(e2, e1);
+  }
+};
+
+// A priority queue holding non-owning Edge pointers. top() will
+// return the edge with the largest critical path weight, and lowest
+// ID if more than one edge has the same critical path weight.
+class EdgePriorityQueue:
+  public std::priority_queue<Edge*, std::vector<Edge*>, EdgePriorityLess>{
+public:
+  void clear() {
+    c.clear();
+  }
+};
+
 #endif  // NINJA_GRAPH_H_