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 | |
28 | struct BuildLog; |
29 | struct DepfileParserOptions; |
30 | struct DiskInterface; |
31 | struct DepsLog; |
32 | struct Edge; |
33 | struct Node; |
34 | struct Pool; |
35 | struct State; |
36 | |
37 | /// Information about a node in the dependency graph: the file, whether |
38 | /// it's dirty, mtime, etc. |
39 | struct 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 | |
117 | private: |
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. |
164 | struct 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 | |
255 | struct EdgeCmp { |
256 | bool operator()(const Edge* a, const Edge* b) const { |
257 | return a->id_ < b->id_; |
258 | } |
259 | }; |
260 | |
261 | typedef std::set<Edge*, EdgeCmp> EdgeSet; |
262 | |
263 | /// ImplicitDepLoader loads implicit dependencies, as referenced via the |
264 | /// "depfile" attribute in build files. |
265 | struct 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. |
314 | struct 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 | |