src/graph.h

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef NINJA_GRAPH_H_
  16 #define NINJA_GRAPH_H_
  17
  18 #include <string>
  19 #include <vector>
  20 using namespace std;
  21
  22 #include "eval_env.h"
  23 #include "timestamp.h"
  24 #include "util.h"
  25
  26 struct BuildLog;
  27 struct DiskInterface;
  28 struct DepsLog;
  29 struct Edge;
  30 struct Node;
  31 struct Pool;
  32 struct State;
  33
  34 /// Information about a node in the dependency graph: the file, whether
  35 /// it's dirty, mtime, etc.
  36 struct Node {
  37   Node(const string& path, uint64_t slash_bits)
  38       : path_(path),
  39         slash_bits_(slash_bits),
  40         mtime_(-1),
  41         dirty_(false),
  42         in_edge_(NULL),
  43         id_(-1) {}
  44
  45   /// Return false on error.
  46   bool Stat(DiskInterface* disk_interface, string* err);
  47
  48   /// Return false on error.
  49   bool StatIfNecessary(DiskInterface* disk_interface, string* err) {
  50     if (status_known())
  51       return true;
  52     return Stat(disk_interface, err);
  53   }
  54
  55   /// Mark as not-yet-stat()ed and not dirty.
  56   void ResetState() {
  57     mtime_ = -1;
  58     dirty_ = false;
  59   }
  60
  61   /// Mark the Node as already-stat()ed and missing.
  62   void MarkMissing() {
  63     mtime_ = 0;
  64   }
  65
  66   bool exists() const {
  67     return mtime_ != 0;
  68   }
  69
  70   bool status_known() const {
  71     return mtime_ != -1;
  72   }
  73
  74   const string& path() const { return path_; }
  75   /// Get |path()| but use slash_bits to convert back to original slash styles.
  76   string PathDecanonicalized() const {
  77     return PathDecanonicalized(path_, slash_bits_);
  78   }
  79   static string PathDecanonicalized(const string& path,
  80                                     uint64_t slash_bits);
  81   uint64_t slash_bits() const { return slash_bits_; }
  82
  83   TimeStamp mtime() const { return mtime_; }
  84
  85   bool dirty() const { return dirty_; }
  86   void set_dirty(bool dirty) { dirty_ = dirty; }
  87   void MarkDirty() { dirty_ = true; }
  88
  89   Edge* in_edge() const { return in_edge_; }
  90   void set_in_edge(Edge* edge) { in_edge_ = edge; }
  91
  92   int id() const { return id_; }
  93   void set_id(int id) { id_ = id; }
  94
  95   const vector<Edge*>& out_edges() const { return out_edges_; }
  96   void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
  97
  98   void Dump(const char* prefix="") const;
  99
 100 private:
 101   string path_;
 102
 103   /// Set bits starting from lowest for backslashes that were normalized to
 104   /// forward slashes by CanonicalizePath. See |PathDecanonicalized|.
 105   uint64_t slash_bits_;
 106
 107   /// Possible values of mtime_:
 108   ///   -1: file hasn't been examined
 109   ///   0:  we looked, and file doesn't exist
 110   ///   >0: actual file's mtime
 111   TimeStamp mtime_;
 112
 113   /// Dirty is true when the underlying file is out-of-date.
 114   /// But note that Edge::outputs_ready_ is also used in judging which
 115   /// edges to build.
 116   bool dirty_;
 117
 118   /// The Edge that produces this Node, or NULL when there is no
 119   /// known edge to produce it.
 120   Edge* in_edge_;
 121
 122   /// All Edges that use this Node as an input.
 123   vector<Edge*> out_edges_;
 124
 125   /// A dense integer id for the node, assigned and used by DepsLog.
 126   int id_;
 127 };
 128
 129 /// An edge in the dependency graph; links between Nodes using Rules.
 130 struct Edge {
 131   enum VisitMark {
 132     VisitNone,
 133     VisitInStack,
 134     VisitDone
 135   };
 136
 137   Edge() : rule_(NULL), pool_(NULL), env_(NULL), mark_(VisitNone),
 138            outputs_ready_(false), deps_missing_(false),
 139            implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {}
 140
 141   /// Return true if all inputs' in-edges are ready.
 142   bool AllInputsReady() const;
 143
 144   /// Expand all variables in a command and return it as a string.
 145   /// If incl_rsp_file is enabled, the string will also contain the
 146   /// full contents of a response file (if applicable)
 147   string EvaluateCommand(bool incl_rsp_file = false);
 148
 149   /// Returns the shell-escaped value of |key|.
 150   string GetBinding(const string& key);
 151   bool GetBindingBool(const string& key);
 152
 153   /// Like GetBinding("depfile"), but without shell escaping.
 154   string GetUnescapedDepfile();
 155   /// Like GetBinding("rspfile"), but without shell escaping.
 156   string GetUnescapedRspfile();
 157
 158   void Dump(const char* prefix="") const;
 159
 160   const Rule* rule_;
 161   Pool* pool_;
 162   vector<Node*> inputs_;
 163   vector<Node*> outputs_;
 164   BindingEnv* env_;
 165   VisitMark mark_;
 166   bool outputs_ready_;
 167   bool deps_missing_;
 168
 169   const Rule& rule() const { return *rule_; }
 170   Pool* pool() const { return pool_; }
 171   int weight() const { return 1; }
 172   bool outputs_ready() const { return outputs_ready_; }
 173
 174   // There are three types of inputs.
 175   // 1) explicit deps, which show up as $in on the command line;
 176   // 2) implicit deps, which the target depends on implicitly (e.g. C headers),
 177   //                   and changes in them cause the target to rebuild;
 178   // 3) order-only deps, which are needed before the target builds but which
 179   //                     don't cause the target to rebuild.
 180   // These are stored in inputs_ in that order, and we keep counts of
 181   // #2 and #3 when we need to access the various subsets.
 182   int implicit_deps_;
 183   int order_only_deps_;
 184   bool is_implicit(size_t index) {
 185     return index >= inputs_.size() - order_only_deps_ - implicit_deps_ &&
 186         !is_order_only(index);
 187   }
 188   bool is_order_only(size_t index) {
 189     return index >= inputs_.size() - order_only_deps_;
 190   }
 191
 192   // There are two types of outputs.
 193   // 1) explicit outs, which show up as $out on the command line;
 194   // 2) implicit outs, which the target generates but are not part of $out.
 195   // These are stored in outputs_ in that order, and we keep a count of
 196   // #2 to use when we need to access the various subsets.
 197   int implicit_outs_;
 198   bool is_implicit_out(size_t index) const {
 199     return index >= outputs_.size() - implicit_outs_;
 200   }
 201
 202   bool is_phony() const;
 203   bool use_console() const;
 204 };
 205
 206
 207 /// ImplicitDepLoader loads implicit dependencies, as referenced via the
 208 /// "depfile" attribute in build files.
 209 struct ImplicitDepLoader {
 210   ImplicitDepLoader(State* state, DepsLog* deps_log,
 211                     DiskInterface* disk_interface)
 212       : state_(state), disk_interface_(disk_interface), deps_log_(deps_log) {}
 213
 214   /// Load implicit dependencies for \a edge.
 215   /// @return false on error (without filling \a err if info is just missing
 216   //                          or out of date).
 217   bool LoadDeps(Edge* edge, string* err);
 218
 219   DepsLog* deps_log() const {
 220     return deps_log_;
 221   }
 222
 223  private:
 224   /// Load implicit dependencies for \a edge from a depfile attribute.
 225   /// @return false on error (without filling \a err if info is just missing).
 226   bool LoadDepFile(Edge* edge, const string& path, string* err);
 227
 228   /// Load implicit dependencies for \a edge from the DepsLog.
 229   /// @return false on error (without filling \a err if info is just missing).
 230   bool LoadDepsFromLog(Edge* edge, string* err);
 231
 232   /// Preallocate \a count spaces in the input array on \a edge, returning
 233   /// an iterator pointing at the first new space.
 234   vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
 235
 236   /// If we don't have a edge that generates this input already,
 237   /// create one; this makes us not abort if the input is missing,
 238   /// but instead will rebuild in that circumstance.
 239   void CreatePhonyInEdge(Node* node);
 240
 241   State* state_;
 242   DiskInterface* disk_interface_;
 243   DepsLog* deps_log_;
 244 };
 245
 246
 247 /// DependencyScan manages the process of scanning the files in a graph
 248 /// and updating the dirty/outputs_ready state of all the nodes and edges.
 249 struct DependencyScan {
 250   DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log,
 251                  DiskInterface* disk_interface)
 252       : build_log_(build_log),
 253         disk_interface_(disk_interface),
 254         dep_loader_(state, deps_log, disk_interface) {}
 255
 256   /// Update the |dirty_| state of the given node by inspecting its input edge.
 257   /// Examine inputs, outputs, and command lines to judge whether an edge
 258   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
 259   /// state accordingly.
 260   /// Returns false on failure.
 261   bool RecomputeDirty(Node* node, string* err);
 262
 263   /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
 264   /// Returns false on failure.
 265   bool RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
 266                              bool* dirty, string* err);
 267
 268   BuildLog* build_log() const {
 269     return build_log_;
 270   }
 271   void set_build_log(BuildLog* log) {
 272     build_log_ = log;
 273   }
 274
 275   DepsLog* deps_log() const {
 276     return dep_loader_.deps_log();
 277   }
 278
 279  private:
 280   bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err);
 281   bool VerifyDAG(Node* node, vector<Node*>* stack, string* err);
 282
 283   /// Recompute whether a given single output should be marked dirty.
 284   /// Returns true if so.
 285   bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,
 286                             const string& command, Node* output);
 287
 288   BuildLog* build_log_;
 289   DiskInterface* disk_interface_;
 290   ImplicitDepLoader dep_loader_;
 291 };
 292
 293 #endif  // NINJA_GRAPH_H_