Ninja
|
00001 // Copyright 2011 Google Inc. All Rights Reserved. 00002 // 00003 // Licensed under the Apache License, Version 2.0 (the "License"); 00004 // you may not use this file except in compliance with the License. 00005 // You may obtain a copy of the License at 00006 // 00007 // http://www.apache.org/licenses/LICENSE-2.0 00008 // 00009 // Unless required by applicable law or agreed to in writing, software 00010 // distributed under the License is distributed on an "AS IS" BASIS, 00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00012 // See the License for the specific language governing permissions and 00013 // limitations under the License. 00014 00015 #include "graph.h" 00016 00017 #include <assert.h> 00018 #include <stdio.h> 00019 00020 #include "build_log.h" 00021 #include "depfile_parser.h" 00022 #include "deps_log.h" 00023 #include "disk_interface.h" 00024 #include "explain.h" 00025 #include "manifest_parser.h" 00026 #include "metrics.h" 00027 #include "state.h" 00028 #include "util.h" 00029 00030 bool Node::Stat(DiskInterface* disk_interface) { 00031 METRIC_RECORD("node stat"); 00032 mtime_ = disk_interface->Stat(path_); 00033 return mtime_ > 0; 00034 } 00035 00036 void Rule::AddBinding(const string& key, const EvalString& val) { 00037 bindings_[key] = val; 00038 } 00039 00040 const EvalString* Rule::GetBinding(const string& key) const { 00041 map<string, EvalString>::const_iterator i = bindings_.find(key); 00042 if (i == bindings_.end()) 00043 return NULL; 00044 return &i->second; 00045 } 00046 00047 // static 00048 bool Rule::IsReservedBinding(const string& var) { 00049 return var == "command" || 00050 var == "depfile" || 00051 var == "description" || 00052 var == "deps" || 00053 var == "generator" || 00054 var == "pool" || 00055 var == "restat" || 00056 var == "rspfile" || 00057 var == "rspfile_content"; 00058 } 00059 00060 bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { 00061 bool dirty = false; 00062 edge->outputs_ready_ = true; 00063 00064 TimeStamp deps_mtime = 0; 00065 if (!dep_loader_.LoadDeps(edge, &deps_mtime, err)) { 00066 if (!err->empty()) 00067 return false; 00068 // Failed to load dependency info: rebuild to regenerate it. 00069 dirty = true; 00070 } 00071 00072 // Visit all inputs; we're dirty if any of the inputs are dirty. 00073 Node* most_recent_input = NULL; 00074 for (vector<Node*>::iterator i = edge->inputs_.begin(); 00075 i != edge->inputs_.end(); ++i) { 00076 if ((*i)->StatIfNecessary(disk_interface_)) { 00077 if (Edge* in_edge = (*i)->in_edge()) { 00078 if (!RecomputeDirty(in_edge, err)) 00079 return false; 00080 } else { 00081 // This input has no in-edge; it is dirty if it is missing. 00082 if (!(*i)->exists()) 00083 EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str()); 00084 (*i)->set_dirty(!(*i)->exists()); 00085 } 00086 } 00087 00088 // If an input is not ready, neither are our outputs. 00089 if (Edge* in_edge = (*i)->in_edge()) { 00090 if (!in_edge->outputs_ready_) 00091 edge->outputs_ready_ = false; 00092 } 00093 00094 if (!edge->is_order_only(i - edge->inputs_.begin())) { 00095 // If a regular input is dirty (or missing), we're dirty. 00096 // Otherwise consider mtime. 00097 if ((*i)->dirty()) { 00098 EXPLAIN("%s is dirty", (*i)->path().c_str()); 00099 dirty = true; 00100 } else { 00101 if (!most_recent_input || (*i)->mtime() > most_recent_input->mtime()) { 00102 most_recent_input = *i; 00103 } 00104 } 00105 } 00106 } 00107 00108 // We may also be dirty due to output state: missing outputs, out of 00109 // date outputs, etc. Visit all outputs and determine whether they're dirty. 00110 if (!dirty) { 00111 string command = edge->EvaluateCommand(true); 00112 00113 for (vector<Node*>::iterator i = edge->outputs_.begin(); 00114 i != edge->outputs_.end(); ++i) { 00115 (*i)->StatIfNecessary(disk_interface_); 00116 if (RecomputeOutputDirty(edge, most_recent_input, deps_mtime, 00117 command, *i)) { 00118 dirty = true; 00119 break; 00120 } 00121 } 00122 } 00123 00124 // Finally, visit each output to mark off that we've visited it, and update 00125 // their dirty state if necessary. 00126 for (vector<Node*>::iterator i = edge->outputs_.begin(); 00127 i != edge->outputs_.end(); ++i) { 00128 (*i)->StatIfNecessary(disk_interface_); 00129 if (dirty) 00130 (*i)->MarkDirty(); 00131 } 00132 00133 // If an edge is dirty, its outputs are normally not ready. (It's 00134 // possible to be clean but still not be ready in the presence of 00135 // order-only inputs.) 00136 // But phony edges with no inputs have nothing to do, so are always 00137 // ready. 00138 if (dirty && !(edge->is_phony() && edge->inputs_.empty())) 00139 edge->outputs_ready_ = false; 00140 00141 return true; 00142 } 00143 00144 bool DependencyScan::RecomputeOutputDirty(Edge* edge, 00145 Node* most_recent_input, 00146 TimeStamp deps_mtime, 00147 const string& command, 00148 Node* output) { 00149 if (edge->is_phony()) { 00150 // Phony edges don't write any output. Outputs are only dirty if 00151 // there are no inputs and we're missing the output. 00152 return edge->inputs_.empty() && !output->exists(); 00153 } 00154 00155 BuildLog::LogEntry* entry = 0; 00156 00157 // Dirty if we're missing the output. 00158 if (!output->exists()) { 00159 EXPLAIN("output %s doesn't exist", output->path().c_str()); 00160 return true; 00161 } 00162 00163 // Dirty if the output is older than the input. 00164 if (most_recent_input && output->mtime() < most_recent_input->mtime()) { 00165 TimeStamp output_mtime = output->mtime(); 00166 00167 // If this is a restat rule, we may have cleaned the output with a restat 00168 // rule in a previous run and stored the most recent input mtime in the 00169 // build log. Use that mtime instead, so that the file will only be 00170 // considered dirty if an input was modified since the previous run. 00171 bool used_restat = false; 00172 if (edge->GetBindingBool("restat") && build_log() && 00173 (entry = build_log()->LookupByOutput(output->path()))) { 00174 output_mtime = entry->restat_mtime; 00175 used_restat = true; 00176 } 00177 00178 if (output_mtime < most_recent_input->mtime()) { 00179 EXPLAIN("%soutput %s older than most recent input %s " 00180 "(%d vs %d)", 00181 used_restat ? "restat of " : "", output->path().c_str(), 00182 most_recent_input->path().c_str(), 00183 output_mtime, most_recent_input->mtime()); 00184 return true; 00185 } 00186 } 00187 00188 // Dirty if the output is newer than the deps. 00189 if (deps_mtime && output->mtime() > deps_mtime) { 00190 EXPLAIN("stored deps info out of date for for %s (%d vs %d)", 00191 output->path().c_str(), deps_mtime, output->mtime()); 00192 return true; 00193 } 00194 00195 // May also be dirty due to the command changing since the last build. 00196 // But if this is a generator rule, the command changing does not make us 00197 // dirty. 00198 if (!edge->GetBindingBool("generator") && build_log()) { 00199 if (entry || (entry = build_log()->LookupByOutput(output->path()))) { 00200 if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) { 00201 EXPLAIN("command line changed for %s", output->path().c_str()); 00202 return true; 00203 } 00204 } 00205 if (!entry) { 00206 EXPLAIN("command line not found in log for %s", output->path().c_str()); 00207 return true; 00208 } 00209 } 00210 00211 return false; 00212 } 00213 00214 bool Edge::AllInputsReady() const { 00215 for (vector<Node*>::const_iterator i = inputs_.begin(); 00216 i != inputs_.end(); ++i) { 00217 if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready()) 00218 return false; 00219 } 00220 return true; 00221 } 00222 00223 /// An Env for an Edge, providing $in and $out. 00224 struct EdgeEnv : public Env { 00225 explicit EdgeEnv(Edge* edge) : edge_(edge) {} 00226 virtual string LookupVariable(const string& var); 00227 00228 /// Given a span of Nodes, construct a list of paths suitable for a command 00229 /// line. 00230 string MakePathList(vector<Node*>::iterator begin, 00231 vector<Node*>::iterator end, 00232 char sep); 00233 00234 Edge* edge_; 00235 }; 00236 00237 string EdgeEnv::LookupVariable(const string& var) { 00238 if (var == "in" || var == "in_newline") { 00239 int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ - 00240 edge_->order_only_deps_; 00241 return MakePathList(edge_->inputs_.begin(), 00242 edge_->inputs_.begin() + explicit_deps_count, 00243 var == "in" ? ' ' : '\n'); 00244 } else if (var == "out") { 00245 return MakePathList(edge_->outputs_.begin(), 00246 edge_->outputs_.end(), 00247 ' '); 00248 } 00249 00250 // See notes on BindingEnv::LookupWithFallback. 00251 const EvalString* eval = edge_->rule_->GetBinding(var); 00252 return edge_->env_->LookupWithFallback(var, eval, this); 00253 } 00254 00255 string EdgeEnv::MakePathList(vector<Node*>::iterator begin, 00256 vector<Node*>::iterator end, 00257 char sep) { 00258 string result; 00259 for (vector<Node*>::iterator i = begin; i != end; ++i) { 00260 if (!result.empty()) 00261 result.push_back(sep); 00262 const string& path = (*i)->path(); 00263 if (path.find(" ") != string::npos) { 00264 result.append("\""); 00265 result.append(path); 00266 result.append("\""); 00267 } else { 00268 result.append(path); 00269 } 00270 } 00271 return result; 00272 } 00273 00274 string Edge::EvaluateCommand(bool incl_rsp_file) { 00275 string command = GetBinding("command"); 00276 if (incl_rsp_file) { 00277 string rspfile_content = GetBinding("rspfile_content"); 00278 if (!rspfile_content.empty()) 00279 command += ";rspfile=" + rspfile_content; 00280 } 00281 return command; 00282 } 00283 00284 string Edge::GetBinding(const string& key) { 00285 EdgeEnv env(this); 00286 return env.LookupVariable(key); 00287 } 00288 00289 bool Edge::GetBindingBool(const string& key) { 00290 return !GetBinding(key).empty(); 00291 } 00292 00293 void Edge::Dump(const char* prefix) const { 00294 printf("%s[ ", prefix); 00295 for (vector<Node*>::const_iterator i = inputs_.begin(); 00296 i != inputs_.end() && *i != NULL; ++i) { 00297 printf("%s ", (*i)->path().c_str()); 00298 } 00299 printf("--%s-> ", rule_->name().c_str()); 00300 for (vector<Node*>::const_iterator i = outputs_.begin(); 00301 i != outputs_.end() && *i != NULL; ++i) { 00302 printf("%s ", (*i)->path().c_str()); 00303 } 00304 if (pool_) { 00305 if (!pool_->name().empty()) { 00306 printf("(in pool '%s')", pool_->name().c_str()); 00307 } 00308 } else { 00309 printf("(null pool?)"); 00310 } 00311 printf("] 0x%p\n", this); 00312 } 00313 00314 bool Edge::is_phony() const { 00315 return rule_ == &State::kPhonyRule; 00316 } 00317 00318 void Node::Dump(const char* prefix) const { 00319 printf("%s <%s 0x%p> mtime: %d%s, (:%s), ", 00320 prefix, path().c_str(), this, 00321 mtime(), mtime() ? "" : " (:missing)", 00322 dirty() ? " dirty" : " clean"); 00323 if (in_edge()) { 00324 in_edge()->Dump("in-edge: "); 00325 } else { 00326 printf("no in-edge\n"); 00327 } 00328 printf(" out edges:\n"); 00329 for (vector<Edge*>::const_iterator e = out_edges().begin(); 00330 e != out_edges().end() && *e != NULL; ++e) { 00331 (*e)->Dump(" +- "); 00332 } 00333 } 00334 00335 bool ImplicitDepLoader::LoadDeps(Edge* edge, TimeStamp* mtime, string* err) { 00336 string deps_type = edge->GetBinding("deps"); 00337 if (!deps_type.empty()) { 00338 if (!LoadDepsFromLog(edge, mtime, err)) { 00339 if (!err->empty()) 00340 return false; 00341 EXPLAIN("deps for %s are missing", edge->outputs_[0]->path().c_str()); 00342 return false; 00343 } 00344 return true; 00345 } 00346 00347 string depfile = edge->GetBinding("depfile"); 00348 if (!depfile.empty()) { 00349 if (!LoadDepFile(edge, depfile, err)) { 00350 if (!err->empty()) 00351 return false; 00352 EXPLAIN("depfile '%s' is missing", depfile.c_str()); 00353 return false; 00354 } 00355 return true; 00356 } 00357 00358 // No deps to load. 00359 return true; 00360 } 00361 00362 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path, 00363 string* err) { 00364 METRIC_RECORD("depfile load"); 00365 string content = disk_interface_->ReadFile(path, err); 00366 if (!err->empty()) { 00367 *err = "loading '" + path + "': " + *err; 00368 return false; 00369 } 00370 // On a missing depfile: return false and empty *err. 00371 if (content.empty()) 00372 return false; 00373 00374 DepfileParser depfile; 00375 string depfile_err; 00376 if (!depfile.Parse(&content, &depfile_err)) { 00377 *err = path + ": " + depfile_err; 00378 return false; 00379 } 00380 00381 // Check that this depfile matches the edge's output. 00382 Node* first_output = edge->outputs_[0]; 00383 StringPiece opath = StringPiece(first_output->path()); 00384 if (opath != depfile.out_) { 00385 *err = "expected depfile '" + path + "' to mention '" + 00386 first_output->path() + "', got '" + depfile.out_.AsString() + "'"; 00387 return false; 00388 } 00389 00390 // Preallocate space in edge->inputs_ to be filled in below. 00391 vector<Node*>::iterator implicit_dep = 00392 PreallocateSpace(edge, depfile.ins_.size()); 00393 00394 // Add all its in-edges. 00395 for (vector<StringPiece>::iterator i = depfile.ins_.begin(); 00396 i != depfile.ins_.end(); ++i, ++implicit_dep) { 00397 if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err)) 00398 return false; 00399 00400 Node* node = state_->GetNode(*i); 00401 *implicit_dep = node; 00402 node->AddOutEdge(edge); 00403 CreatePhonyInEdge(node); 00404 } 00405 00406 return true; 00407 } 00408 00409 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, TimeStamp* deps_mtime, 00410 string* err) { 00411 DepsLog::Deps* deps = deps_log_->GetDeps(edge->outputs_[0]); 00412 if (!deps) 00413 return false; 00414 00415 *deps_mtime = deps->mtime; 00416 00417 vector<Node*>::iterator implicit_dep = 00418 PreallocateSpace(edge, deps->node_count); 00419 for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) { 00420 *implicit_dep = deps->nodes[i]; 00421 deps->nodes[i]->AddOutEdge(edge); 00422 CreatePhonyInEdge(*implicit_dep); 00423 } 00424 return true; 00425 } 00426 00427 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge, 00428 int count) { 00429 edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_, 00430 (size_t)count, 0); 00431 edge->implicit_deps_ += count; 00432 return edge->inputs_.end() - edge->order_only_deps_ - count; 00433 } 00434 00435 void ImplicitDepLoader::CreatePhonyInEdge(Node* node) { 00436 if (node->in_edge()) 00437 return; 00438 00439 Edge* phony_edge = state_->AddEdge(&State::kPhonyRule); 00440 node->set_in_edge(phony_edge); 00441 phony_edge->outputs_.push_back(node); 00442 00443 // RecomputeDirty might not be called for phony_edge if a previous call 00444 // to RecomputeDirty had caused the file to be stat'ed. Because previous 00445 // invocations of RecomputeDirty would have seen this node without an 00446 // input edge (and therefore ready), we have to set outputs_ready_ to true 00447 // to avoid a potential stuck build. If we do call RecomputeDirty for 00448 // this node, it will simply set outputs_ready_ to the correct value. 00449 phony_edge->outputs_ready_ = true; 00450 }