Ninja
graph.cc
Go to the documentation of this file.
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 "debug_flags.h"
00022 #include "depfile_parser.h"
00023 #include "deps_log.h"
00024 #include "disk_interface.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   edge->deps_missing_ = false;
00064 
00065   if (!dep_loader_.LoadDeps(edge, err)) {
00066     if (!err->empty())
00067       return false;
00068     // Failed to load dependency info: rebuild to regenerate it.
00069     dirty = edge->deps_missing_ = 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     dirty = RecomputeOutputsDirty(edge, most_recent_input);
00112 
00113   // Finally, visit each output to mark off that we've visited it, and update
00114   // their dirty state if necessary.
00115   for (vector<Node*>::iterator i = edge->outputs_.begin();
00116        i != edge->outputs_.end(); ++i) {
00117     (*i)->StatIfNecessary(disk_interface_);
00118     if (dirty)
00119       (*i)->MarkDirty();
00120   }
00121 
00122   // If an edge is dirty, its outputs are normally not ready.  (It's
00123   // possible to be clean but still not be ready in the presence of
00124   // order-only inputs.)
00125   // But phony edges with no inputs have nothing to do, so are always
00126   // ready.
00127   if (dirty && !(edge->is_phony() && edge->inputs_.empty()))
00128     edge->outputs_ready_ = false;
00129 
00130   return true;
00131 }
00132 
00133 bool DependencyScan::RecomputeOutputsDirty(Edge* edge,
00134                                            Node* most_recent_input) {   
00135   string command = edge->EvaluateCommand(true);
00136   for (vector<Node*>::iterator i = edge->outputs_.begin();
00137        i != edge->outputs_.end(); ++i) {
00138     (*i)->StatIfNecessary(disk_interface_);
00139     if (RecomputeOutputDirty(edge, most_recent_input, command, *i))
00140       return true;
00141   }
00142   return false;
00143 }
00144 
00145 bool DependencyScan::RecomputeOutputDirty(Edge* edge,
00146                                           Node* most_recent_input,
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   // May also be dirty due to the command changing since the last build.
00189   // But if this is a generator rule, the command changing does not make us
00190   // dirty.
00191   if (!edge->GetBindingBool("generator") && build_log()) {
00192     if (entry || (entry = build_log()->LookupByOutput(output->path()))) {
00193       if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) {
00194         EXPLAIN("command line changed for %s", output->path().c_str());
00195         return true;
00196       }
00197     }
00198     if (!entry) {
00199       EXPLAIN("command line not found in log for %s", output->path().c_str());
00200       return true;
00201     }
00202   }
00203 
00204   return false;
00205 }
00206 
00207 bool Edge::AllInputsReady() const {
00208   for (vector<Node*>::const_iterator i = inputs_.begin();
00209        i != inputs_.end(); ++i) {
00210     if ((*i)->in_edge() && !(*i)->in_edge()->outputs_ready())
00211       return false;
00212   }
00213   return true;
00214 }
00215 
00216 /// An Env for an Edge, providing $in and $out.
00217 struct EdgeEnv : public Env {
00218   enum EscapeKind { kShellEscape, kDoNotEscape };
00219 
00220   explicit EdgeEnv(Edge* edge, EscapeKind escape)
00221       : edge_(edge), escape_in_out_(escape) {}
00222   virtual string LookupVariable(const string& var);
00223 
00224   /// Given a span of Nodes, construct a list of paths suitable for a command
00225   /// line.
00226   string MakePathList(vector<Node*>::iterator begin,
00227                       vector<Node*>::iterator end,
00228                       char sep);
00229 
00230   Edge* edge_;
00231   EscapeKind escape_in_out_;
00232 };
00233 
00234 string EdgeEnv::LookupVariable(const string& var) {
00235   if (var == "in" || var == "in_newline") {
00236     int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
00237       edge_->order_only_deps_;
00238     return MakePathList(edge_->inputs_.begin(),
00239                         edge_->inputs_.begin() + explicit_deps_count,
00240                         var == "in" ? ' ' : '\n');
00241   } else if (var == "out") {
00242     return MakePathList(edge_->outputs_.begin(),
00243                         edge_->outputs_.end(),
00244                         ' ');
00245   }
00246 
00247   // See notes on BindingEnv::LookupWithFallback.
00248   const EvalString* eval = edge_->rule_->GetBinding(var);
00249   return edge_->env_->LookupWithFallback(var, eval, this);
00250 }
00251 
00252 string EdgeEnv::MakePathList(vector<Node*>::iterator begin,
00253                              vector<Node*>::iterator end,
00254                              char sep) {
00255   string result;
00256   for (vector<Node*>::iterator i = begin; i != end; ++i) {
00257     if (!result.empty())
00258       result.push_back(sep);
00259     const string& path = (*i)->path();
00260     if (escape_in_out_ == kShellEscape) {
00261 #if _WIN32
00262       GetWin32EscapedString(path, &result);
00263 #else
00264       GetShellEscapedString(path, &result);
00265 #endif
00266     } else {
00267       result.append(path);
00268     }
00269   }
00270   return result;
00271 }
00272 
00273 string Edge::EvaluateCommand(bool incl_rsp_file) {
00274   string command = GetBinding("command");
00275   if (incl_rsp_file) {
00276     string rspfile_content = GetBinding("rspfile_content");
00277     if (!rspfile_content.empty())
00278       command += ";rspfile=" + rspfile_content;
00279   }
00280   return command;
00281 }
00282 
00283 string Edge::GetBinding(const string& key) {
00284   EdgeEnv env(this, EdgeEnv::kShellEscape);
00285   return env.LookupVariable(key);
00286 }
00287 
00288 bool Edge::GetBindingBool(const string& key) {
00289   return !GetBinding(key).empty();
00290 }
00291 
00292 string Edge::GetUnescapedDepfile() {
00293   EdgeEnv env(this, EdgeEnv::kDoNotEscape);
00294   return env.LookupVariable("depfile");
00295 }
00296 
00297 string Edge::GetUnescapedRspfile() {
00298   EdgeEnv env(this, EdgeEnv::kDoNotEscape);
00299   return env.LookupVariable("rspfile");
00300 }
00301 
00302 void Edge::Dump(const char* prefix) const {
00303   printf("%s[ ", prefix);
00304   for (vector<Node*>::const_iterator i = inputs_.begin();
00305        i != inputs_.end() && *i != NULL; ++i) {
00306     printf("%s ", (*i)->path().c_str());
00307   }
00308   printf("--%s-> ", rule_->name().c_str());
00309   for (vector<Node*>::const_iterator i = outputs_.begin();
00310        i != outputs_.end() && *i != NULL; ++i) {
00311     printf("%s ", (*i)->path().c_str());
00312   }
00313   if (pool_) {
00314     if (!pool_->name().empty()) {
00315       printf("(in pool '%s')", pool_->name().c_str());
00316     }
00317   } else {
00318     printf("(null pool?)");
00319   }
00320   printf("] 0x%p\n", this);
00321 }
00322 
00323 bool Edge::is_phony() const {
00324   return rule_ == &State::kPhonyRule;
00325 }
00326 
00327 bool Edge::use_console() const {
00328   return pool() == &State::kConsolePool;
00329 }
00330 
00331 void Node::Dump(const char* prefix) const {
00332   printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
00333          prefix, path().c_str(), this,
00334          mtime(), mtime() ? "" : " (:missing)",
00335          dirty() ? " dirty" : " clean");
00336   if (in_edge()) {
00337     in_edge()->Dump("in-edge: ");
00338   } else {
00339     printf("no in-edge\n");
00340   }
00341   printf(" out edges:\n");
00342   for (vector<Edge*>::const_iterator e = out_edges().begin();
00343        e != out_edges().end() && *e != NULL; ++e) {
00344     (*e)->Dump(" +- ");
00345   }
00346 }
00347 
00348 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
00349   string deps_type = edge->GetBinding("deps");
00350   if (!deps_type.empty())
00351     return LoadDepsFromLog(edge, err);
00352 
00353   string depfile = edge->GetUnescapedDepfile();
00354   if (!depfile.empty())
00355     return LoadDepFile(edge, depfile, err);
00356 
00357   // No deps to load.
00358   return true;
00359 }
00360 
00361 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
00362                                     string* err) {
00363   METRIC_RECORD("depfile load");
00364   string content = disk_interface_->ReadFile(path, err);
00365   if (!err->empty()) {
00366     *err = "loading '" + path + "': " + *err;
00367     return false;
00368   }
00369   // On a missing depfile: return false and empty *err.
00370   if (content.empty()) {
00371     EXPLAIN("depfile '%s' is missing", path.c_str());
00372     return false;
00373   }
00374 
00375   DepfileParser depfile;
00376   string depfile_err;
00377   if (!depfile.Parse(&content, &depfile_err)) {
00378     *err = path + ": " + depfile_err;
00379     return false;
00380   }
00381 
00382   // Check that this depfile matches the edge's output.
00383   Node* first_output = edge->outputs_[0];
00384   StringPiece opath = StringPiece(first_output->path());
00385   if (opath != depfile.out_) {
00386     *err = "expected depfile '" + path + "' to mention '" +
00387         first_output->path() + "', got '" + depfile.out_.AsString() + "'";
00388     return false;
00389   }
00390 
00391   // Preallocate space in edge->inputs_ to be filled in below.
00392   vector<Node*>::iterator implicit_dep =
00393       PreallocateSpace(edge, depfile.ins_.size());
00394 
00395   // Add all its in-edges.
00396   for (vector<StringPiece>::iterator i = depfile.ins_.begin();
00397        i != depfile.ins_.end(); ++i, ++implicit_dep) {
00398     if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err))
00399       return false;
00400 
00401     Node* node = state_->GetNode(*i);
00402     *implicit_dep = node;
00403     node->AddOutEdge(edge);
00404     CreatePhonyInEdge(node);
00405   }
00406 
00407   return true;
00408 }
00409 
00410 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
00411   // NOTE: deps are only supported for single-target edges.
00412   Node* output = edge->outputs_[0];
00413   DepsLog::Deps* deps = deps_log_->GetDeps(output);
00414   if (!deps) {
00415     EXPLAIN("deps for '%s' are missing", output->path().c_str());
00416     return false;
00417   }
00418 
00419   // Deps are invalid if the output is newer than the deps.
00420   if (output->mtime() > deps->mtime) {
00421     EXPLAIN("stored deps info out of date for for '%s' (%d vs %d)",
00422             output->path().c_str(), deps->mtime, output->mtime());
00423     return false;
00424   }
00425 
00426   vector<Node*>::iterator implicit_dep =
00427       PreallocateSpace(edge, deps->node_count);
00428   for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
00429     Node* node = deps->nodes[i];
00430     *implicit_dep = node;
00431     node->AddOutEdge(edge);
00432     CreatePhonyInEdge(node);
00433   }
00434   return true;
00435 }
00436 
00437 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
00438                                                             int count) {
00439   edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
00440                        (size_t)count, 0);
00441   edge->implicit_deps_ += count;
00442   return edge->inputs_.end() - edge->order_only_deps_ - count;
00443 }
00444 
00445 void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
00446   if (node->in_edge())
00447     return;
00448 
00449   Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
00450   node->set_in_edge(phony_edge);
00451   phony_edge->outputs_.push_back(node);
00452 
00453   // RecomputeDirty might not be called for phony_edge if a previous call
00454   // to RecomputeDirty had caused the file to be stat'ed.  Because previous
00455   // invocations of RecomputeDirty would have seen this node without an
00456   // input edge (and therefore ready), we have to set outputs_ready_ to true
00457   // to avoid a potential stuck build.  If we do call RecomputeDirty for
00458   // this node, it will simply set outputs_ready_ to the correct value.
00459   phony_edge->outputs_ready_ = true;
00460 }