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   explicit EdgeEnv(Edge* edge) : edge_(edge) {}
00219   virtual string LookupVariable(const string& var);
00220 
00221   /// Given a span of Nodes, construct a list of paths suitable for a command
00222   /// line.
00223   string MakePathList(vector<Node*>::iterator begin,
00224                       vector<Node*>::iterator end,
00225                       char sep);
00226 
00227   Edge* edge_;
00228 };
00229 
00230 string EdgeEnv::LookupVariable(const string& var) {
00231   if (var == "in" || var == "in_newline") {
00232     int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ -
00233       edge_->order_only_deps_;
00234     return MakePathList(edge_->inputs_.begin(),
00235                         edge_->inputs_.begin() + explicit_deps_count,
00236                         var == "in" ? ' ' : '\n');
00237   } else if (var == "out") {
00238     return MakePathList(edge_->outputs_.begin(),
00239                         edge_->outputs_.end(),
00240                         ' ');
00241   }
00242 
00243   // See notes on BindingEnv::LookupWithFallback.
00244   const EvalString* eval = edge_->rule_->GetBinding(var);
00245   return edge_->env_->LookupWithFallback(var, eval, this);
00246 }
00247 
00248 string EdgeEnv::MakePathList(vector<Node*>::iterator begin,
00249                              vector<Node*>::iterator end,
00250                              char sep) {
00251   string result;
00252   for (vector<Node*>::iterator i = begin; i != end; ++i) {
00253     if (!result.empty())
00254       result.push_back(sep);
00255     const string& path = (*i)->path();
00256     if (path.find(" ") != string::npos) {
00257       result.append("\"");
00258       result.append(path);
00259       result.append("\"");
00260     } else {
00261       result.append(path);
00262     }
00263   }
00264   return result;
00265 }
00266 
00267 string Edge::EvaluateCommand(bool incl_rsp_file) {
00268   string command = GetBinding("command");
00269   if (incl_rsp_file) {
00270     string rspfile_content = GetBinding("rspfile_content");
00271     if (!rspfile_content.empty())
00272       command += ";rspfile=" + rspfile_content;
00273   }
00274   return command;
00275 }
00276 
00277 string Edge::GetBinding(const string& key) {
00278   EdgeEnv env(this);
00279   return env.LookupVariable(key);
00280 }
00281 
00282 bool Edge::GetBindingBool(const string& key) {
00283   return !GetBinding(key).empty();
00284 }
00285 
00286 void Edge::Dump(const char* prefix) const {
00287   printf("%s[ ", prefix);
00288   for (vector<Node*>::const_iterator i = inputs_.begin();
00289        i != inputs_.end() && *i != NULL; ++i) {
00290     printf("%s ", (*i)->path().c_str());
00291   }
00292   printf("--%s-> ", rule_->name().c_str());
00293   for (vector<Node*>::const_iterator i = outputs_.begin();
00294        i != outputs_.end() && *i != NULL; ++i) {
00295     printf("%s ", (*i)->path().c_str());
00296   }
00297   if (pool_) {
00298     if (!pool_->name().empty()) {
00299       printf("(in pool '%s')", pool_->name().c_str());
00300     }
00301   } else {
00302     printf("(null pool?)");
00303   }
00304   printf("] 0x%p\n", this);
00305 }
00306 
00307 bool Edge::is_phony() const {
00308   return rule_ == &State::kPhonyRule;
00309 }
00310 
00311 void Node::Dump(const char* prefix) const {
00312   printf("%s <%s 0x%p> mtime: %d%s, (:%s), ",
00313          prefix, path().c_str(), this,
00314          mtime(), mtime() ? "" : " (:missing)",
00315          dirty() ? " dirty" : " clean");
00316   if (in_edge()) {
00317     in_edge()->Dump("in-edge: ");
00318   } else {
00319     printf("no in-edge\n");
00320   }
00321   printf(" out edges:\n");
00322   for (vector<Edge*>::const_iterator e = out_edges().begin();
00323        e != out_edges().end() && *e != NULL; ++e) {
00324     (*e)->Dump(" +- ");
00325   }
00326 }
00327 
00328 bool ImplicitDepLoader::LoadDeps(Edge* edge, string* err) {
00329   string deps_type = edge->GetBinding("deps");
00330   if (!deps_type.empty())
00331     return LoadDepsFromLog(edge, err);
00332 
00333   string depfile = edge->GetBinding("depfile");
00334   if (!depfile.empty())
00335     return LoadDepFile(edge, depfile, err);
00336 
00337   // No deps to load.
00338   return true;
00339 }
00340 
00341 bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path,
00342                                     string* err) {
00343   METRIC_RECORD("depfile load");
00344   string content = disk_interface_->ReadFile(path, err);
00345   if (!err->empty()) {
00346     *err = "loading '" + path + "': " + *err;
00347     return false;
00348   }
00349   // On a missing depfile: return false and empty *err.
00350   if (content.empty()) {
00351     EXPLAIN("depfile '%s' is missing", path.c_str());
00352     return false;
00353   }
00354 
00355   DepfileParser depfile;
00356   string depfile_err;
00357   if (!depfile.Parse(&content, &depfile_err)) {
00358     *err = path + ": " + depfile_err;
00359     return false;
00360   }
00361 
00362   // Check that this depfile matches the edge's output.
00363   Node* first_output = edge->outputs_[0];
00364   StringPiece opath = StringPiece(first_output->path());
00365   if (opath != depfile.out_) {
00366     *err = "expected depfile '" + path + "' to mention '" +
00367         first_output->path() + "', got '" + depfile.out_.AsString() + "'";
00368     return false;
00369   }
00370 
00371   // Preallocate space in edge->inputs_ to be filled in below.
00372   vector<Node*>::iterator implicit_dep =
00373       PreallocateSpace(edge, depfile.ins_.size());
00374 
00375   // Add all its in-edges.
00376   for (vector<StringPiece>::iterator i = depfile.ins_.begin();
00377        i != depfile.ins_.end(); ++i, ++implicit_dep) {
00378     if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, err))
00379       return false;
00380 
00381     Node* node = state_->GetNode(*i);
00382     *implicit_dep = node;
00383     node->AddOutEdge(edge);
00384     CreatePhonyInEdge(node);
00385   }
00386 
00387   return true;
00388 }
00389 
00390 bool ImplicitDepLoader::LoadDepsFromLog(Edge* edge, string* err) {
00391   // NOTE: deps are only supported for single-target edges.
00392   Node* output = edge->outputs_[0];
00393   DepsLog::Deps* deps = deps_log_->GetDeps(output);
00394   if (!deps) {
00395     EXPLAIN("deps for '%s' are missing", output->path().c_str());
00396     return false;
00397   }
00398 
00399   // Deps are invalid if the output is newer than the deps.
00400   if (output->mtime() > deps->mtime) {
00401     EXPLAIN("stored deps info out of date for for '%s' (%d vs %d)",
00402             output->path().c_str(), deps->mtime, output->mtime());
00403     return false;
00404   }
00405 
00406   vector<Node*>::iterator implicit_dep =
00407       PreallocateSpace(edge, deps->node_count);
00408   for (int i = 0; i < deps->node_count; ++i, ++implicit_dep) {
00409     Node* node = deps->nodes[i];
00410     *implicit_dep = node;
00411     node->AddOutEdge(edge);
00412     CreatePhonyInEdge(node);
00413   }
00414   return true;
00415 }
00416 
00417 vector<Node*>::iterator ImplicitDepLoader::PreallocateSpace(Edge* edge,
00418                                                             int count) {
00419   edge->inputs_.insert(edge->inputs_.end() - edge->order_only_deps_,
00420                        (size_t)count, 0);
00421   edge->implicit_deps_ += count;
00422   return edge->inputs_.end() - edge->order_only_deps_ - count;
00423 }
00424 
00425 void ImplicitDepLoader::CreatePhonyInEdge(Node* node) {
00426   if (node->in_edge())
00427     return;
00428 
00429   Edge* phony_edge = state_->AddEdge(&State::kPhonyRule);
00430   node->set_in_edge(phony_edge);
00431   phony_edge->outputs_.push_back(node);
00432 
00433   // RecomputeDirty might not be called for phony_edge if a previous call
00434   // to RecomputeDirty had caused the file to be stat'ed.  Because previous
00435   // invocations of RecomputeDirty would have seen this node without an
00436   // input edge (and therefore ready), we have to set outputs_ready_ to true
00437   // to avoid a potential stuck build.  If we do call RecomputeDirty for
00438   // this node, it will simply set outputs_ready_ to the correct value.
00439   phony_edge->outputs_ready_ = true;
00440 }