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 "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 }