1 // Copyright 2011 Google Inc. All Rights Reserved.
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
7 // http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include "edit_distance.h"
26 void Pool::EdgeScheduled(const Edge& edge) {
28 current_use_ += edge.weight();
31 void Pool::EdgeFinished(const Edge& edge) {
33 current_use_ -= edge.weight();
36 void Pool::DelayEdge(Edge* edge) {
38 delayed_.insert(edge);
41 void Pool::RetrieveReadyEdges(set<Edge*>* ready_queue) {
42 DelayedEdges::iterator it = delayed_.begin();
43 while (it != delayed_.end()) {
45 if (current_use_ + edge->weight() > depth_)
47 ready_queue->insert(edge);
51 delayed_.erase(delayed_.begin(), it);
54 void Pool::Dump() const {
55 printf("%s (%d/%d) ->\n", name_.c_str(), current_use_, depth_);
56 for (DelayedEdges::const_iterator it = delayed_.begin();
57 it != delayed_.end(); ++it)
64 bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
67 int weight_diff = a->weight() - b->weight();
68 return ((weight_diff < 0) || (weight_diff == 0 && a < b));
71 Pool State::kDefaultPool("", 0);
72 Pool State::kConsolePool("console", 1);
73 const Rule State::kPhonyRule("phony");
76 bindings_.AddRule(&kPhonyRule);
77 AddPool(&kDefaultPool);
78 AddPool(&kConsolePool);
81 void State::AddPool(Pool* pool) {
82 assert(LookupPool(pool->name()) == NULL);
83 pools_[pool->name()] = pool;
86 Pool* State::LookupPool(const string& pool_name) {
87 map<string, Pool*>::iterator i = pools_.find(pool_name);
88 if (i == pools_.end())
93 Edge* State::AddEdge(const Rule* rule) {
94 Edge* edge = new Edge();
96 edge->pool_ = &State::kDefaultPool;
97 edge->env_ = &bindings_;
98 edges_.push_back(edge);
102 Node* State::GetNode(StringPiece path, unsigned int slash_bits) {
103 Node* node = LookupNode(path);
106 node = new Node(path.AsString(), slash_bits);
107 paths_[node->path()] = node;
111 Node* State::LookupNode(StringPiece path) const {
112 METRIC_RECORD("lookup node");
113 Paths::const_iterator i = paths_.find(path);
114 if (i != paths_.end())
119 Node* State::SpellcheckNode(const string& path) {
120 const bool kAllowReplacements = true;
121 const int kMaxValidEditDistance = 3;
123 int min_distance = kMaxValidEditDistance + 1;
125 for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
126 int distance = EditDistance(
127 i->first, path, kAllowReplacements, kMaxValidEditDistance);
128 if (distance < min_distance && i->second) {
129 min_distance = distance;
136 void State::AddIn(Edge* edge, StringPiece path, unsigned int slash_bits) {
137 Node* node = GetNode(path, slash_bits);
138 edge->inputs_.push_back(node);
139 node->AddOutEdge(edge);
142 void State::AddOut(Edge* edge, StringPiece path, unsigned int slash_bits) {
143 Node* node = GetNode(path, slash_bits);
144 if (node->in_edge()) {
145 Warning("multiple rules generate %s. "
146 "builds involving this target will not be correct; "
148 path.AsString().c_str());
151 edge->outputs_.push_back(node);
152 node->set_in_edge(edge);
155 bool State::AddDefault(StringPiece path, string* err) {
156 Node* node = LookupNode(path);
158 *err = "unknown target '" + path.AsString() + "'";
161 defaults_.push_back(node);
165 vector<Node*> State::RootNodes(string* err) {
166 vector<Node*> root_nodes;
167 // Search for nodes with no output.
168 for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
169 for (vector<Node*>::iterator out = (*e)->outputs_.begin();
170 out != (*e)->outputs_.end(); ++out) {
171 if ((*out)->out_edges().empty())
172 root_nodes.push_back(*out);
176 if (!edges_.empty() && root_nodes.empty())
177 *err = "could not determine root nodes of build graph";
182 vector<Node*> State::DefaultNodes(string* err) {
183 return defaults_.empty() ? RootNodes(err) : defaults_;
186 void State::Reset() {
187 for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
188 i->second->ResetState();
189 for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e)
190 (*e)->outputs_ready_ = false;
194 for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
195 Node* node = i->second;
196 printf("%s %s [id:%d]\n",
197 node->path().c_str(),
198 node->status_known() ? (node->dirty() ? "dirty" : "clean")
202 if (!pools_.empty()) {
203 printf("resource_pools:\n");
204 for (map<string, Pool*>::const_iterator it = pools_.begin();
205 it != pools_.end(); ++it)
207 if (!it->second->name().empty()) {