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