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