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