src/graph.cc

   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 #include "graph.h"
  16
  17 #include <stdio.h>
  18
  19 #include "build_log.h"
  20 #include "ninja.h"
  21 #include "parsers.h"
  22
  23 // Canonicalize a path like "foo/../bar.h" into just "bar.h".
  24 bool CanonicalizePath(string* path, string* err) {
  25   // Try to fast-path out the common case.
  26   if (path->find("/.") == string::npos &&
  27       path->find("./") == string::npos) {
  28     return true;
  29   }
  30
  31   string inpath = *path;
  32   vector<const char*> parts;
  33   for (string::size_type start = 0; start < inpath.size(); ++start) {
  34     string::size_type end = inpath.find('/', start);
  35     if (end == string::npos)
  36       end = inpath.size();
  37     else
  38       inpath[end] = 0;
  39     parts.push_back(inpath.data() + start);
  40     start = end;
  41   }
  42
  43   vector<const char*>::iterator i = parts.begin();
  44   while (i != parts.end()) {
  45     const char* part = *i;
  46     if (part[0] == '.') {
  47       if (part[1] == 0) {
  48         // "."; strip.
  49         parts.erase(i);
  50         continue;
  51       } else if (part[1] == '.' && part[2] == 0) {
  52         // ".."; go up one.
  53         if (i == parts.begin()) {
  54           *err = "can't canonicalize path '" + *path + "' that reaches "
  55             "above its directory";
  56           return false;
  57         }
  58         --i;
  59         parts.erase(i, i + 2);
  60         continue;
  61       }
  62     }
  63     ++i;
  64   }
  65   path->clear();
  66
  67   for (i = parts.begin(); i != parts.end(); ++i) {
  68     if (!path->empty())
  69       path->push_back('/');
  70     path->append(*i);
  71   }
  72
  73   return true;
  74 }
  75
  76 bool FileStat::Stat(DiskInterface* disk_interface) {
  77   mtime_ = disk_interface->Stat(path_);
  78   return mtime_ > 0;
  79 }
  80
  81 bool Edge::RecomputeDirty(State* state, DiskInterface* disk_interface,
  82                           string* err) {
  83   bool dirty = false;
  84
  85   if (!rule_->depfile_.empty()) {
  86     if (!LoadDepFile(state, disk_interface, err))
  87       return false;
  88   }
  89
  90   time_t most_recent_input = 1;
  91   for (vector<Node*>::iterator i = inputs_.begin(); i != inputs_.end(); ++i) {
  92     if ((*i)->file_->StatIfNecessary(disk_interface)) {
  93       if (Edge* edge = (*i)->in_edge_) {
  94         if (!edge->RecomputeDirty(state, disk_interface, err))
  95           return false;
  96       } else {
  97         // This input has no in-edge; it is dirty if it is missing.
  98         // But it's ok for implicit deps to be missing.
  99         if (!is_implicit(i - inputs_.begin()))
 100           (*i)->dirty_ = !(*i)->file_->exists();
 101       }
 102     }
 103
 104     if (is_order_only(i - inputs_.begin())) {
 105       // Order-only deps only make us dirty if they're missing.
 106       if (!(*i)->file_->exists())
 107         dirty = true;
 108       continue;
 109     }
 110
 111     // If a regular input is dirty (or missing), we're dirty.
 112     // Otherwise consider mtime.
 113     if ((*i)->dirty_) {
 114       dirty = true;
 115     } else {
 116       if ((*i)->file_->mtime_ > most_recent_input)
 117         most_recent_input = (*i)->file_->mtime_;
 118     }
 119   }
 120
 121   string command = EvaluateCommand();
 122
 123   assert(!outputs_.empty());
 124   for (vector<Node*>::iterator i = outputs_.begin(); i != outputs_.end(); ++i) {
 125     // We may have other outputs, that our input-recursive traversal hasn't hit
 126     // yet (or never will).  Stat them if we haven't already.
 127     (*i)->file_->StatIfNecessary(disk_interface);
 128
 129     // Output is dirty if we're dirty, we're missing the output,
 130     // or if it's older than the most recent input mtime.
 131     if (dirty || !(*i)->file_->exists() ||
 132         (*i)->file_->mtime_ < most_recent_input) {
 133       (*i)->dirty_ = true;
 134     } else {
 135       // May also be dirty due to the command changing since the last build.
 136       BuildLog::LogEntry* entry;
 137       if (state->build_log_ &&
 138           (entry = state->build_log_->LookupByOutput((*i)->file_->path_))) {
 139         if (command != entry->command)
 140           (*i)->dirty_ = true;
 141       }
 142     }
 143   }
 144   return true;
 145 }
 146
 147 struct EdgeEnv : public Env {
 148   EdgeEnv(Edge* edge) : edge_(edge) {}
 149   virtual string LookupVariable(const string& var) {
 150     string result;
 151     if (var == "in") {
 152       int explicit_deps = edge_->inputs_.size() - edge_->implicit_deps_ -
 153           edge_->order_only_deps_;
 154       for (vector<Node*>::iterator i = edge_->inputs_.begin();
 155            i != edge_->inputs_.end() && explicit_deps; ++i, --explicit_deps) {
 156         if (!result.empty())
 157           result.push_back(' ');
 158         result.append((*i)->file_->path_);
 159       }
 160     } else if (var == "out") {
 161       result = edge_->outputs_[0]->file_->path_;
 162     } else if (edge_->env_) {
 163       return edge_->env_->LookupVariable(var);
 164     }
 165     return result;
 166   }
 167   Edge* edge_;
 168 };
 169
 170 string Edge::EvaluateCommand() {
 171   EdgeEnv env(this);
 172   return rule_->command_.Evaluate(&env);
 173 }
 174
 175 string Edge::GetDescription() {
 176   EdgeEnv env(this);
 177   return rule_->description_.Evaluate(&env);
 178 }
 179
 180 bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface,
 181                        string* err) {
 182   EdgeEnv env(this);
 183   string path = rule_->depfile_.Evaluate(&env);
 184
 185   string content = disk_interface->ReadFile(path, err);
 186   if (!err->empty())
 187     return false;
 188   if (content.empty())
 189     return true;
 190
 191   MakefileParser makefile;
 192   string makefile_err;
 193   if (!makefile.Parse(content, &makefile_err)) {
 194     *err = path + ": " + makefile_err;
 195     return false;
 196   }
 197
 198   // Check that this depfile matches our output.
 199   if (outputs_.size() != 1) {
 200     *err = "expected only one output";
 201     return false;
 202   }
 203   if (outputs_[0]->file_->path_ != makefile.out_) {
 204     *err = "expected makefile to mention '" + outputs_[0]->file_->path_ + "', "
 205            "got '" + makefile.out_ + "'";
 206     return false;
 207   }
 208
 209   // Add all its in-edges.
 210   for (vector<string>::iterator i = makefile.ins_.begin();
 211        i != makefile.ins_.end(); ++i) {
 212     if (!CanonicalizePath(&*i, err))
 213       return false;
 214
 215     Node* node = state->GetNode(*i);
 216     inputs_.insert(inputs_.end() - order_only_deps_, node);
 217     node->out_edges_.push_back(this);
 218     ++implicit_deps_;
 219   }
 220
 221   return true;
 222 }
 223
 224 void Edge::Dump() {
 225   printf("[ ");
 226   for (vector<Node*>::iterator i = inputs_.begin(); i != inputs_.end(); ++i) {
 227     printf("%s ", (*i)->file_->path_.c_str());
 228   }
 229   printf("--%s-> ", rule_->name_.c_str());
 230   for (vector<Node*>::iterator i = outputs_.begin(); i != outputs_.end(); ++i) {
 231     printf("%s ", (*i)->file_->path_.c_str());
 232   }
 233   printf("]\n");
 234 }
 235
 236 bool Edge::is_phony() const {
 237   return rule_ == &State::kPhonyRule;
 238 }