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 const Rule State::kPhonyRule("phony");
00073 
00074 State::State() {
00075   AddRule(&kPhonyRule);
00076   AddPool(&kDefaultPool);
00077 }
00078 
00079 void State::AddRule(const Rule* rule) {
00080   assert(LookupRule(rule->name()) == NULL);
00081   rules_[rule->name()] = rule;
00082 }
00083 
00084 const Rule* State::LookupRule(const string& rule_name) {
00085   map<string, const Rule*>::iterator i = rules_.find(rule_name);
00086   if (i == rules_.end())
00087     return NULL;
00088   return i->second;
00089 }
00090 
00091 void State::AddPool(Pool* pool) {
00092   assert(LookupPool(pool->name()) == NULL);
00093   pools_[pool->name()] = pool;
00094 }
00095 
00096 Pool* State::LookupPool(const string& pool_name) {
00097   map<string, Pool*>::iterator i = pools_.find(pool_name);
00098   if (i == pools_.end())
00099     return NULL;
00100   return i->second;
00101 }
00102 
00103 Edge* State::AddEdge(const Rule* rule) {
00104   Edge* edge = new Edge();
00105   edge->rule_ = rule;
00106   edge->pool_ = &State::kDefaultPool;
00107   edge->env_ = &bindings_;
00108   edges_.push_back(edge);
00109   return edge;
00110 }
00111 
00112 Node* State::GetNode(StringPiece path) {
00113   Node* node = LookupNode(path);
00114   if (node)
00115     return node;
00116   node = new Node(path.AsString());
00117   paths_[node->path()] = node;
00118   return node;
00119 }
00120 
00121 Node* State::LookupNode(StringPiece path) {
00122   METRIC_RECORD("lookup node");
00123   Paths::iterator i = paths_.find(path);
00124   if (i != paths_.end())
00125     return i->second;
00126   return NULL;
00127 }
00128 
00129 Node* State::SpellcheckNode(const string& path) {
00130   const bool kAllowReplacements = true;
00131   const int kMaxValidEditDistance = 3;
00132 
00133   int min_distance = kMaxValidEditDistance + 1;
00134   Node* result = NULL;
00135   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
00136     int distance = EditDistance(
00137         i->first, path, kAllowReplacements, kMaxValidEditDistance);
00138     if (distance < min_distance && i->second) {
00139       min_distance = distance;
00140       result = i->second;
00141     }
00142   }
00143   return result;
00144 }
00145 
00146 void State::AddIn(Edge* edge, StringPiece path) {
00147   Node* node = GetNode(path);
00148   edge->inputs_.push_back(node);
00149   node->AddOutEdge(edge);
00150 }
00151 
00152 void State::AddOut(Edge* edge, StringPiece path) {
00153   Node* node = GetNode(path);
00154   edge->outputs_.push_back(node);
00155   if (node->in_edge()) {
00156     Warning("multiple rules generate %s. "
00157             "builds involving this target will not be correct; "
00158             "continuing anyway",
00159             path.AsString().c_str());
00160   }
00161   node->set_in_edge(edge);
00162 }
00163 
00164 bool State::AddDefault(StringPiece path, string* err) {
00165   Node* node = LookupNode(path);
00166   if (!node) {
00167     *err = "unknown target '" + path.AsString() + "'";
00168     return false;
00169   }
00170   defaults_.push_back(node);
00171   return true;
00172 }
00173 
00174 vector<Node*> State::RootNodes(string* err) {
00175   vector<Node*> root_nodes;
00176   // Search for nodes with no output.
00177   for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
00178     for (vector<Node*>::iterator out = (*e)->outputs_.begin();
00179          out != (*e)->outputs_.end(); ++out) {
00180       if ((*out)->out_edges().empty())
00181         root_nodes.push_back(*out);
00182     }
00183   }
00184 
00185   if (!edges_.empty() && root_nodes.empty())
00186     *err = "could not determine root nodes of build graph";
00187 
00188   assert(edges_.empty() || !root_nodes.empty());
00189   return root_nodes;
00190 }
00191 
00192 vector<Node*> State::DefaultNodes(string* err) {
00193   return defaults_.empty() ? RootNodes(err) : defaults_;
00194 }
00195 
00196 void State::Reset() {
00197   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
00198     i->second->ResetState();
00199   for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
00200     (*e)->outputs_ready_ = false;
00201 }
00202 
00203 void State::Dump() {
00204   for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
00205     Node* node = i->second;
00206     printf("%s %s [id:%d]\n",
00207            node->path().c_str(),
00208            node->status_known() ? (node->dirty() ? "dirty" : "clean")
00209                                 : "unknown",
00210            node->id());
00211   }
00212   if (!pools_.empty()) {
00213     printf("resource_pools:\n");
00214     for (map<string, Pool*>::const_iterator it = pools_.begin();
00215          it != pools_.end(); ++it)
00216     {
00217       if (!it->second->name().empty()) {
00218         it->second->Dump();
00219       }
00220     }
00221   }
00222 }