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