Ninja
state.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 "state.h"
00016 
00017 #include <assert.h>
00018 #include <stdio.h>
00019 
00020 #include "edit_distance.h"
00021 #include "graph.h"
00022 #include "metrics.h"
00023 #include "util.h"
00024 
00025 
00026 void Pool::EdgeScheduled(const Edge& edge) {
00027   if (depth_ != 0)
00028     current_use_ += edge.weight();
00029 }
00030 
00031 void Pool::EdgeFinished(const Edge& edge) {
00032   if (depth_ != 0)
00033     current_use_ -= edge.weight();
00034 }
00035 
00036 void Pool::DelayEdge(Edge* edge) {
00037   assert(depth_ != 0);
00038   delayed_.insert(edge);
00039 }
00040 
00041 void Pool::RetrieveReadyEdges(set<Edge*>* ready_queue) {
00042   DelayedEdges::iterator it = delayed_.begin();
00043   while (it != delayed_.end()) {
00044     Edge* edge = *it;
00045     if (current_use_ + edge->weight() > depth_)
00046       break;
00047     ready_queue->insert(edge);
00048     EdgeScheduled(*edge);
00049     ++it;
00050   }
00051   delayed_.erase(delayed_.begin(), it);
00052 }
00053 
00054 void Pool::Dump() const {
00055   printf("%s (%d/%d) ->\n", name_.c_str(), current_use_, depth_);
00056   for (DelayedEdges::const_iterator it = delayed_.begin();
00057        it != delayed_.end(); ++it)
00058   {
00059     printf("\t");
00060     (*it)->Dump();
00061   }
00062 }
00063 
00064 bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
00065   if (!a) return b;
00066   if (!b) return false;
00067   int weight_diff = a->weight() - b->weight();
00068   return ((weight_diff < 0) || (weight_diff == 0 && a < b));
00069 }
00070 
00071 Pool State::kDefaultPool("", 0);
00072 Pool State::kConsolePool("console", 1);
00073 const Rule State::kPhonyRule("phony");
00074 
00075 State::State() {
00076   AddRule(&kPhonyRule);
00077   AddPool(&kDefaultPool);
00078   AddPool(&kConsolePool);
00079 }
00080 
00081 void State::AddRule(const Rule* rule) {
00082   assert(LookupRule(rule->name()) == NULL);
00083   rules_[rule->name()] = rule;
00084 }
00085 
00086 const Rule* State::LookupRule(const string& rule_name) {
00087   map<string, const Rule*>::iterator i = rules_.find(rule_name);
00088   if (i == rules_.end())
00089     return NULL;
00090   return i->second;
00091 }
00092 
00093 void State::AddPool(Pool* pool) {
00094   assert(LookupPool(pool->name()) == NULL);
00095   pools_[pool->name()] = pool;
00096 }
00097 
00098 Pool* State::LookupPool(const string& pool_name) {
00099   map<string, Pool*>::iterator i = pools_.find(pool_name);
00100   if (i == pools_.end())
00101     return NULL;
00102   return i->second;
00103 }
00104 
00105 Edge* State::AddEdge(const Rule* rule) {
00106   Edge* edge = new Edge();
00107   edge->rule_ = rule;
00108   edge->pool_ = &State::kDefaultPool;
00109   edge->env_ = &bindings_;
00110   edges_.push_back(edge);
00111   return edge;
00112 }
00113 
00114 Node* State::GetNode(StringPiece path) {
00115   Node* node = LookupNode(path);
00116   if (node)
00117     return node;
00118   node = new Node(path.AsString());
00119   paths_[node->path()] = node;
00120   return node;
00121 }
00122 
00123 Node* State::LookupNode(StringPiece path) const {
00124   METRIC_RECORD("lookup node");
00125   Paths::const_iterator i = paths_.find(path);
00126   if (i != paths_.end())
00127     return i->second;
00128   return NULL;
00129 }
00130 
00131 Node* State::SpellcheckNode(const string& path) {
00132   const bool kAllowReplacements = true;
00133   const int kMaxValidEditDistance = 3;
00134 
00135   int min_distance = kMaxValidEditDistance + 1;
00136   Node* result = NULL;
00137   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
00138     int distance = EditDistance(
00139         i->first, path, kAllowReplacements, kMaxValidEditDistance);
00140     if (distance < min_distance && i->second) {
00141       min_distance = distance;
00142       result = i->second;
00143     }
00144   }
00145   return result;
00146 }
00147 
00148 void State::AddIn(Edge* edge, StringPiece path) {
00149   Node* node = GetNode(path);
00150   edge->inputs_.push_back(node);
00151   node->AddOutEdge(edge);
00152 }
00153 
00154 void State::AddOut(Edge* edge, StringPiece path) {
00155   Node* node = GetNode(path);
00156   edge->outputs_.push_back(node);
00157   if (node->in_edge()) {
00158     Warning("multiple rules generate %s. "
00159             "builds involving this target will not be correct; "
00160             "continuing anyway",
00161             path.AsString().c_str());
00162   }
00163   node->set_in_edge(edge);
00164 }
00165 
00166 bool State::AddDefault(StringPiece path, string* err) {
00167   Node* node = LookupNode(path);
00168   if (!node) {
00169     *err = "unknown target '" + path.AsString() + "'";
00170     return false;
00171   }
00172   defaults_.push_back(node);
00173   return true;
00174 }
00175 
00176 vector<Node*> State::RootNodes(string* err) {
00177   vector<Node*> root_nodes;
00178   // Search for nodes with no output.
00179   for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
00180     for (vector<Node*>::iterator out = (*e)->outputs_.begin();
00181          out != (*e)->outputs_.end(); ++out) {
00182       if ((*out)->out_edges().empty())
00183         root_nodes.push_back(*out);
00184     }
00185   }
00186 
00187   if (!edges_.empty() && root_nodes.empty())
00188     *err = "could not determine root nodes of build graph";
00189 
00190   assert(edges_.empty() || !root_nodes.empty());
00191   return root_nodes;
00192 }
00193 
00194 vector<Node*> State::DefaultNodes(string* err) {
00195   return defaults_.empty() ? RootNodes(err) : defaults_;
00196 }
00197 
00198 void State::Reset() {
00199   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
00200     i->second->ResetState();
00201   for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
00202     (*e)->outputs_ready_ = false;
00203 }
00204 
00205 void State::Dump() {
00206   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
00207     Node* node = i->second;
00208     printf("%s %s [id:%d]\n",
00209            node->path().c_str(),
00210            node->status_known() ? (node->dirty() ? "dirty" : "clean")
00211                                 : "unknown",
00212            node->id());
00213   }
00214   if (!pools_.empty()) {
00215     printf("resource_pools:\n");
00216     for (map<string, Pool*>::const_iterator it = pools_.begin();
00217          it != pools_.end(); ++it)
00218     {
00219       if (!it->second->name().empty()) {
00220         it->second->Dump();
00221       }
00222     }
00223   }
00224 }