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