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