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 <algorithm>
19#include <set>
20#include <string>
21#include <vector>
22
23#include "dyndep.h"
24#include "eval_env.h"
25#include "timestamp.h"
26#include "util.h"
27
28struct BuildLog;
29struct DepfileParserOptions;
30struct DiskInterface;
31struct DepsLog;
32struct Edge;
33struct Node;
34struct Pool;
35struct State;
36
37/// Information about a node in the dependency graph: the file, whether
38/// it's dirty, mtime, etc.
39struct Node {
40 Node(const std::string& path, uint64_t slash_bits)
41 : path_(path),
42 slash_bits_(slash_bits),
43 mtime_(-1),
44 exists_(ExistenceStatusUnknown),
45 dirty_(false),
46 dyndep_pending_(false),
47 in_edge_(NULL),
48 id_(-1) {}
49
50 /// Return false on error.
51 bool Stat(DiskInterface* disk_interface, std::string* err);
52
53 /// If the file doesn't exist, set the mtime_ from its dependencies
54 void UpdatePhonyMtime(TimeStamp mtime);
55
56 /// Return false on error.
57 bool StatIfNecessary(DiskInterface* disk_interface, std::string* err) {
58 if (status_known())
59 return true;
60 return Stat(disk_interface, err);
61 }
62
63 /// Mark as not-yet-stat()ed and not dirty.
64 void ResetState() {
65 mtime_ = -1;
66 exists_ = ExistenceStatusUnknown;
67 dirty_ = false;
68 }
69
70 /// Mark the Node as already-stat()ed and missing.
71 void MarkMissing() {
72 if (mtime_ == -1) {
73 mtime_ = 0;
74 }
75 exists_ = ExistenceStatusMissing;
76 }
77
78 bool exists() const {
79 return exists_ == ExistenceStatusExists;
80 }
81
82 bool status_known() const {
83 return exists_ != ExistenceStatusUnknown;
84 }
85
86 const std::string& path() const { return path_; }
87 /// Get |path()| but use slash_bits to convert back to original slash styles.
88 std::string PathDecanonicalized() const {
89 return PathDecanonicalized(path_, slash_bits_);
90 }
91 static std::string PathDecanonicalized(const std::string& path,
92 uint64_t slash_bits);
93 uint64_t slash_bits() const { return slash_bits_; }
94
95 TimeStamp mtime() const { return mtime_; }
96
97 bool dirty() const { return dirty_; }
98 void set_dirty(bool dirty) { dirty_ = dirty; }
99 void MarkDirty() { dirty_ = true; }
100
101 bool dyndep_pending() const { return dyndep_pending_; }
102 void set_dyndep_pending(bool pending) { dyndep_pending_ = pending; }
103
104 Edge* in_edge() const { return in_edge_; }
105 void set_in_edge(Edge* edge) { in_edge_ = edge; }
106
107 int id() const { return id_; }
108 void set_id(int id) { id_ = id; }
109
110 const std::vector<Edge*>& out_edges() const { return out_edges_; }
111 const std::vector<Edge*>& validation_out_edges() const { return validation_out_edges_; }
112 void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
113 void AddValidationOutEdge(Edge* edge) { validation_out_edges_.push_back(edge); }
114
115 void Dump(const char* prefix="") const;
116
117private:
118 std::string path_;
119
120 /// Set bits starting from lowest for backslashes that were normalized to
121 /// forward slashes by CanonicalizePath. See |PathDecanonicalized|.
122 uint64_t slash_bits_;
123
124 /// Possible values of mtime_:
125 /// -1: file hasn't been examined
126 /// 0: we looked, and file doesn't exist
127 /// >0: actual file's mtime, or the latest mtime of its dependencies if it doesn't exist
128 TimeStamp mtime_;
129
130 enum ExistenceStatus {
131 /// The file hasn't been examined.
132 ExistenceStatusUnknown,
133 /// The file doesn't exist. mtime_ will be the latest mtime of its dependencies.
134 ExistenceStatusMissing,
135 /// The path is an actual file. mtime_ will be the file's mtime.
136 ExistenceStatusExists
137 };
138 ExistenceStatus exists_;
139
140 /// Dirty is true when the underlying file is out-of-date.
141 /// But note that Edge::outputs_ready_ is also used in judging which
142 /// edges to build.
143 bool dirty_;
144
145 /// Store whether dyndep information is expected from this node but
146 /// has not yet been loaded.
147 bool dyndep_pending_;
148
149 /// The Edge that produces this Node, or NULL when there is no
150 /// known edge to produce it.
151 Edge* in_edge_;
152
153 /// All Edges that use this Node as an input.
154 std::vector<Edge*> out_edges_;
155
156 /// All Edges that use this Node as a validation.
157 std::vector<Edge*> validation_out_edges_;
158
159 /// A dense integer id for the node, assigned and used by DepsLog.
160 int id_;
161};
162
163/// An edge in the dependency graph; links between Nodes using Rules.
164struct Edge {
165 enum VisitMark {
166 VisitNone,
167 VisitInStack,
168 VisitDone
169 };
170
171 Edge()
172 : rule_(NULL), pool_(NULL), dyndep_(NULL), env_(NULL), mark_(VisitNone),
173 id_(0), outputs_ready_(false), deps_loaded_(false),
174 deps_missing_(false), generated_by_dep_loader_(false),
175 command_start_time_(0), implicit_deps_(0), order_only_deps_(0),
176 implicit_outs_(0) {}
177
178 /// Return true if all inputs' in-edges are ready.
179 bool AllInputsReady() const;
180
181 /// Expand all variables in a command and return it as a string.
182 /// If incl_rsp_file is enabled, the string will also contain the
183 /// full contents of a response file (if applicable)
184 std::string EvaluateCommand(bool incl_rsp_file = false) const;
185
186 /// Returns the shell-escaped value of |key|.
187 std::string GetBinding(const std::string& key) const;
188 bool GetBindingBool(const std::string& key) const;
189
190 /// Like GetBinding("depfile"), but without shell escaping.
191 std::string GetUnescapedDepfile() const;
192 /// Like GetBinding("dyndep"), but without shell escaping.
193 std::string GetUnescapedDyndep() const;
194 /// Like GetBinding("rspfile"), but without shell escaping.
195 std::string GetUnescapedRspfile() const;
196
197 void Dump(const char* prefix="") const;
198
199 // Append all edge explicit inputs to |*out|. Possibly with shell escaping.
200 void CollectInputs(bool shell_escape, std::vector<std::string>* out) const;
201
202 const Rule* rule_;
203 Pool* pool_;
204 std::vector<Node*> inputs_;
205 std::vector<Node*> outputs_;
206 std::vector<Node*> validations_;
207 Node* dyndep_;
208 BindingEnv* env_;
209 VisitMark mark_;
210 size_t id_;
211 bool outputs_ready_;
212 bool deps_loaded_;
213 bool deps_missing_;
214 bool generated_by_dep_loader_;
215 TimeStamp command_start_time_;
216
217 const Rule& rule() const { return *rule_; }
218 Pool* pool() const { return pool_; }
219 int weight() const { return 1; }
220 bool outputs_ready() const { return outputs_ready_; }
221
222 // There are three types of inputs.
223 // 1) explicit deps, which show up as $in on the command line;
224 // 2) implicit deps, which the target depends on implicitly (e.g. C headers),
225 // and changes in them cause the target to rebuild;
226 // 3) order-only deps, which are needed before the target builds but which
227 // don't cause the target to rebuild.
228 // These are stored in inputs_ in that order, and we keep counts of
229 // #2 and #3 when we need to access the various subsets.
230 int implicit_deps_;
231 int order_only_deps_;
232 bool is_implicit(size_t index) {
233 return index >= inputs_.size() - order_only_deps_ - implicit_deps_ &&
234 !is_order_only(index);
235 }
236 bool is_order_only(size_t index) {
237 return index >= inputs_.size() - order_only_deps_;
238 }
239
240 // There are two types of outputs.
241 // 1) explicit outs, which show up as $out on the command line;
242 // 2) implicit outs, which the target generates but are not part of $out.
243 // These are stored in outputs_ in that order, and we keep a count of
244 // #2 to use when we need to access the various subsets.
245 int implicit_outs_;
246 bool is_implicit_out(size_t index) const {
247 return index >= outputs_.size() - implicit_outs_;
248 }
249
250 bool is_phony() const;
251 bool use_console() const;
252 bool maybe_phonycycle_diagnostic() const;
253};
254
255struct EdgeCmp {
256 bool operator()(const Edge* a, const Edge* b) const {
257 return a->id_ < b->id_;
258 }
259};
260
261typedef std::set<Edge*, EdgeCmp> EdgeSet;
262
263/// ImplicitDepLoader loads implicit dependencies, as referenced via the
264/// "depfile" attribute in build files.
265struct ImplicitDepLoader {
266 ImplicitDepLoader(State* state, DepsLog* deps_log,
267 DiskInterface* disk_interface,
268 DepfileParserOptions const* depfile_parser_options)
269 : state_(state), disk_interface_(disk_interface), deps_log_(deps_log),
270 depfile_parser_options_(depfile_parser_options) {}
271
272 /// Load implicit dependencies for \a edge.
273 /// @return false on error (without filling \a err if info is just missing
274 // or out of date).
275 bool LoadDeps(Edge* edge, std::string* err);
276
277 DepsLog* deps_log() const {
278 return deps_log_;
279 }
280
281 protected:
282 /// Process loaded implicit dependencies for \a edge and update the graph
283 /// @return false on error (without filling \a err if info is just missing)
284 virtual bool ProcessDepfileDeps(Edge* edge,
285 std::vector<StringPiece>* depfile_ins,
286 std::string* err);
287
288 /// Load implicit dependencies for \a edge from a depfile attribute.
289 /// @return false on error (without filling \a err if info is just missing).
290 bool LoadDepFile(Edge* edge, const std::string& path, std::string* err);
291
292 /// Load implicit dependencies for \a edge from the DepsLog.
293 /// @return false on error (without filling \a err if info is just missing).
294 bool LoadDepsFromLog(Edge* edge, std::string* err);
295
296 /// Preallocate \a count spaces in the input array on \a edge, returning
297 /// an iterator pointing at the first new space.
298 std::vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
299
300 /// If we don't have a edge that generates this input already,
301 /// create one; this makes us not abort if the input is missing,
302 /// but instead will rebuild in that circumstance.
303 void CreatePhonyInEdge(Node* node);
304
305 State* state_;
306 DiskInterface* disk_interface_;
307 DepsLog* deps_log_;
308 DepfileParserOptions const* depfile_parser_options_;
309};
310
311
312/// DependencyScan manages the process of scanning the files in a graph
313/// and updating the dirty/outputs_ready state of all the nodes and edges.
314struct DependencyScan {
315 DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log,
316 DiskInterface* disk_interface,
317 DepfileParserOptions const* depfile_parser_options)
318 : build_log_(build_log),
319 disk_interface_(disk_interface),
320 dep_loader_(state, deps_log, disk_interface, depfile_parser_options),
321 dyndep_loader_(state, disk_interface) {}
322
323 /// Update the |dirty_| state of the given nodes by transitively inspecting
324 /// their input edges.
325 /// Examine inputs, outputs, and command lines to judge whether an edge
326 /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
327 /// state accordingly.
328 /// Appends any validation nodes found to the nodes parameter.
329 /// Returns false on failure.
330 bool RecomputeDirty(Node* node, std::vector<Node*>* validation_nodes, std::string* err);
331
332 /// Recompute whether any output of the edge is dirty, if so sets |*dirty|.
333 /// Returns false on failure.
334 bool RecomputeOutputsDirty(Edge* edge, Node* most_recent_input,
335 bool* dirty, std::string* err);
336
337 BuildLog* build_log() const {
338 return build_log_;
339 }
340 void set_build_log(BuildLog* log) {
341 build_log_ = log;
342 }
343
344 DepsLog* deps_log() const {
345 return dep_loader_.deps_log();
346 }
347
348 /// Load a dyndep file from the given node's path and update the
349 /// build graph with the new information. One overload accepts
350 /// a caller-owned 'DyndepFile' object in which to store the
351 /// information loaded from the dyndep file.
352 bool LoadDyndeps(Node* node, std::string* err) const;
353 bool LoadDyndeps(Node* node, DyndepFile* ddf, std::string* err) const;
354
355 private:
356 bool RecomputeNodeDirty(Node* node, std::vector<Node*>* stack,
357 std::vector<Node*>* validation_nodes, std::string* err);
358 bool VerifyDAG(Node* node, std::vector<Node*>* stack, std::string* err);
359
360 /// Recompute whether a given single output should be marked dirty.
361 /// Returns true if so.
362 bool RecomputeOutputDirty(const Edge* edge, const Node* most_recent_input,
363 const std::string& command, Node* output);
364
365 BuildLog* build_log_;
366 DiskInterface* disk_interface_;
367 ImplicitDepLoader dep_loader_;
368 DyndepLoader dyndep_loader_;
369};
370
371#endif // NINJA_GRAPH_H_
372