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  explicit Node(const string& path)
37  : path_(path),
38  mtime_(-1),
39  dirty_(false),
40  in_edge_(NULL),
41  id_(-1) {}
42 
43  /// Return true if the file exists (mtime_ got a value).
44  bool Stat(DiskInterface* disk_interface);
45 
46  /// Return true if we needed to stat.
47  bool StatIfNecessary(DiskInterface* disk_interface) {
48  if (status_known())
49  return false;
50  Stat(disk_interface);
51  return true;
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  TimeStamp mtime() const { return mtime_; }
75 
76  bool dirty() const { return dirty_; }
77  void set_dirty(bool dirty) { dirty_ = dirty; }
78  void MarkDirty() { dirty_ = true; }
79 
80  Edge* in_edge() const { return in_edge_; }
81  void set_in_edge(Edge* edge) { in_edge_ = edge; }
82 
83  int id() const { return id_; }
84  void set_id(int id) { id_ = id; }
85 
86  const vector<Edge*>& out_edges() const { return out_edges_; }
87  void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
88 
89  void Dump(const char* prefix="") const;
90 
91 private:
92  string path_;
93  /// Possible values of mtime_:
94  /// -1: file hasn't been examined
95  /// 0: we looked, and file doesn't exist
96  /// >0: actual file's mtime
98 
99  /// Dirty is true when the underlying file is out-of-date.
100  /// But note that Edge::outputs_ready_ is also used in judging which
101  /// edges to build.
102  bool dirty_;
103 
104  /// The Edge that produces this Node, or NULL when there is no
105  /// known edge to produce it.
107 
108  /// All Edges that use this Node as an input.
109  vector<Edge*> out_edges_;
110 
111  /// A dense integer id for the node, assigned and used by DepsLog.
112  int id_;
113 };
114 
115 /// An invokable build command and associated metadata (description, etc.).
116 struct Rule {
117  explicit Rule(const string& name) : name_(name) {}
118 
119  const string& name() const { return name_; }
120 
121  typedef map<string, EvalString> Bindings;
122  void AddBinding(const string& key, const EvalString& val);
123 
124  static bool IsReservedBinding(const string& var);
125 
126  const EvalString* GetBinding(const string& key) const;
127 
128  private:
129  // Allow the parsers to reach into this object and fill out its fields.
130  friend struct ManifestParser;
131 
132  string name_;
133  map<string, EvalString> bindings_;
134 };
135 
136 /// An edge in the dependency graph; links between Nodes using Rules.
137 struct Edge {
138  Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), implicit_deps_(0),
139  order_only_deps_(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  string GetBinding(const string& key);
150  bool GetBindingBool(const string& key);
151 
152  void Dump(const char* prefix="") const;
153 
154  const Rule* rule_;
156  vector<Node*> inputs_;
157  vector<Node*> outputs_;
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.
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  bool is_phony() const;
185 };
186 
187 
188 /// ImplicitDepLoader loads implicit dependencies, as referenced via the
189 /// "depfile" attribute in build files.
191  ImplicitDepLoader(State* state, DepsLog* deps_log,
192  DiskInterface* disk_interface)
193  : state_(state), disk_interface_(disk_interface), deps_log_(deps_log) {}
194 
195  /// Load implicit dependencies for \a edge. May fill in \a mtime with
196  /// the timestamp of the loaded information.
197  /// @return false on error (without filling \a err if info is just missing).
198  bool LoadDeps(Edge* edge, TimeStamp* mtime, string* err);
199 
200  DepsLog* deps_log() const {
201  return deps_log_;
202  }
203 
204  private:
205  /// Load implicit dependencies for \a edge from a depfile attribute.
206  /// @return false on error (without filling \a err if info is just missing).
207  bool LoadDepFile(Edge* edge, const string& path, string* err);
208 
209  /// Load implicit dependencies for \a edge from the DepsLog.
210  /// @return false on error (without filling \a err if info is just missing).
211  bool LoadDepsFromLog(Edge* edge, TimeStamp* mtime, string* err);
212 
213  /// Preallocate \a count spaces in the input array on \a edge, returning
214  /// an iterator pointing at the first new space.
215  vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
216 
217  /// If we don't have a edge that generates this input already,
218  /// create one; this makes us not abort if the input is missing,
219  /// but instead will rebuild in that circumstance.
220  void CreatePhonyInEdge(Node* node);
221 
225 };
226 
227 
228 /// DependencyScan manages the process of scanning the files in a graph
229 /// and updating the dirty/outputs_ready state of all the nodes and edges.
231  DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log,
232  DiskInterface* disk_interface)
233  : build_log_(build_log),
234  disk_interface_(disk_interface),
235  dep_loader_(state, deps_log, disk_interface) {}
236 
237  /// Examine inputs, outputs, and command lines to judge whether an edge
238  /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
239  /// state accordingly.
240  /// Returns false on failure.
241  bool RecomputeDirty(Edge* edge, string* err);
242 
243  /// Recompute whether a given single output should be marked dirty.
244  /// Returns true if so.
245  bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,
246  TimeStamp deps_mtime,
247  const string& command, Node* output);
248 
249  BuildLog* build_log() const {
250  return build_log_;
251  }
252  void set_build_log(BuildLog* log) {
253  build_log_ = log;
254  }
255 
256  DepsLog* deps_log() const {
257  return dep_loader_.deps_log();
258  }
259 
260  private:
264 };
265 
266 #endif // NINJA_GRAPH_H_