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 "state.h"
16
17 #include <assert.h>
18 #include <stdio.h>
19
20 #include "edit_distance.h"
21 #include "graph.h"
22 #include "metrics.h"
23 #include "util.h"
24
25 using namespace std;
26
EdgeScheduled(const Edge & edge)27 void Pool::EdgeScheduled(const Edge& edge) {
28 if (depth_ != 0)
29 current_use_ += edge.weight();
30 }
31
EdgeFinished(const Edge & edge)32 void Pool::EdgeFinished(const Edge& edge) {
33 if (depth_ != 0)
34 current_use_ -= edge.weight();
35 }
36
DelayEdge(Edge * edge)37 void Pool::DelayEdge(Edge* edge) {
38 assert(depth_ != 0);
39 delayed_.insert(edge);
40 }
41
RetrieveReadyEdges(set<Edge * > * ready_queue)42 void Pool::RetrieveReadyEdges(set<Edge*>* ready_queue) {
43 DelayedEdges::iterator it = delayed_.begin();
44 while (it != delayed_.end()) {
45 Edge* edge = *it;
46 if (current_use_ + edge->weight() > depth_)
47 break;
48 ready_queue->insert(edge);
49 EdgeScheduled(*edge);
50 ++it;
51 }
52 delayed_.erase(delayed_.begin(), it);
53 }
54
Dump() const55 void Pool::Dump() const {
56 printf("%s (%d/%d) ->\n", name_.c_str(), current_use_, depth_);
57 for (DelayedEdges::const_iterator it = delayed_.begin();
58 it != delayed_.end(); ++it)
59 {
60 printf("\t");
61 (*it)->Dump();
62 }
63 }
64
65 // static
WeightedEdgeCmp(const Edge * a,const Edge * b)66 bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
67 if (!a) return b;
68 if (!b) return false;
69 int weight_diff = a->weight() - b->weight();
70 return ((weight_diff < 0) || (weight_diff == 0 && a < b));
71 }
72
73 Pool State::kDefaultPool("", 0);
74 Pool State::kConsolePool("console", 1);
75 const Rule State::kPhonyRule("phony");
76
State()77 State::State() {
78 bindings_.AddRule(&kPhonyRule);
79 AddPool(&kDefaultPool);
80 AddPool(&kConsolePool);
81 }
82
AddPool(Pool * pool)83 void State::AddPool(Pool* pool) {
84 assert(LookupPool(pool->name()) == NULL);
85 pools_[pool->name()] = pool;
86 }
87
LookupPool(const string & pool_name)88 Pool* State::LookupPool(const string& pool_name) {
89 map<string, Pool*>::iterator i = pools_.find(pool_name);
90 if (i == pools_.end())
91 return NULL;
92 return i->second;
93 }
94
AddEdge(const Rule * rule)95 Edge* State::AddEdge(const Rule* rule) {
96 Edge* edge = new Edge();
97 edge->rule_ = rule;
98 edge->pool_ = &State::kDefaultPool;
99 edge->env_ = &bindings_;
100 edges_.push_back(edge);
101 return edge;
102 }
103
GetNode(StringPiece path,uint64_t slash_bits)104 Node* State::GetNode(StringPiece path, uint64_t slash_bits) {
105 Node* node = LookupNode(path);
106 if (node)
107 return node;
108 node = new Node(path.AsString(), slash_bits);
109 paths_[node->path()] = node;
110 return node;
111 }
112
LookupNode(StringPiece path) const113 Node* State::LookupNode(StringPiece path) const {
114 METRIC_RECORD("lookup node");
115 Paths::const_iterator i = paths_.find(path);
116 if (i != paths_.end())
117 return i->second;
118 return NULL;
119 }
120
SpellcheckNode(const string & path)121 Node* State::SpellcheckNode(const string& path) {
122 const bool kAllowReplacements = true;
123 const int kMaxValidEditDistance = 3;
124
125 int min_distance = kMaxValidEditDistance + 1;
126 Node* result = NULL;
127 for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
128 int distance = EditDistance(
129 i->first, path, kAllowReplacements, kMaxValidEditDistance);
130 if (distance < min_distance && i->second) {
131 min_distance = distance;
132 result = i->second;
133 }
134 }
135 return result;
136 }
137
AddIn(Edge * edge,StringPiece path,uint64_t slash_bits)138 void State::AddIn(Edge* edge, StringPiece path, uint64_t slash_bits) {
139 Node* node = GetNode(path, slash_bits);
140 edge->inputs_.push_back(node);
141 node->AddOutEdge(edge);
142 }
143
AddOut(Edge * edge,StringPiece path,uint64_t slash_bits)144 bool State::AddOut(Edge* edge, StringPiece path, uint64_t slash_bits) {
145 Node* node = GetNode(path, slash_bits);
146 if (node->in_edge())
147 return false;
148 edge->outputs_.push_back(node);
149 node->set_in_edge(edge);
150 return true;
151 }
152
AddDefault(StringPiece path,string * err)153 bool State::AddDefault(StringPiece path, string* err) {
154 Node* node = LookupNode(path);
155 if (!node) {
156 *err = "unknown target '" + path.AsString() + "'";
157 return false;
158 }
159 defaults_.push_back(node);
160 return true;
161 }
162
RootNodes(string * err) const163 vector<Node*> State::RootNodes(string* err) const {
164 vector<Node*> root_nodes;
165 // Search for nodes with no output.
166 for (vector<Edge*>::const_iterator e = edges_.begin();
167 e != edges_.end(); ++e) {
168 for (vector<Node*>::const_iterator out = (*e)->outputs_.begin();
169 out != (*e)->outputs_.end(); ++out) {
170 if ((*out)->out_edges().empty())
171 root_nodes.push_back(*out);
172 }
173 }
174
175 if (!edges_.empty() && root_nodes.empty())
176 *err = "could not determine root nodes of build graph";
177
178 return root_nodes;
179 }
180
DefaultNodes(string * err) const181 vector<Node*> State::DefaultNodes(string* err) const {
182 return defaults_.empty() ? RootNodes(err) : defaults_;
183 }
184
Reset()185 void State::Reset() {
186 for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i)
187 i->second->ResetState();
188 for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) {
189 (*e)->outputs_ready_ = false;
190 (*e)->deps_loaded_ = false;
191 (*e)->mark_ = Edge::VisitNone;
192 }
193 }
194
Dump()195 void State::Dump() {
196 for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) {
197 Node* node = i->second;
198 printf("%s %s [id:%d]\n",
199 node->path().c_str(),
200 node->status_known() ? (node->dirty() ? "dirty" : "clean")
201 : "unknown",
202 node->id());
203 }
204 if (!pools_.empty()) {
205 printf("resource_pools:\n");
206 for (map<string, Pool*>::const_iterator it = pools_.begin();
207 it != pools_.end(); ++it)
208 {
209 if (!it->second->name().empty()) {
210 it->second->Dump();
211 }
212 }
213 }
214 }
215