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
24using namespace std;
25
26void Pool::EdgeScheduled(const Edge& edge) {
27 if (depth_ != 0)
28 current_use_ += edge.weight();
29}
30
31void Pool::EdgeFinished(const Edge& edge) {
32 if (depth_ != 0)
33 current_use_ -= edge.weight();
34}
35
36void Pool::DelayEdge(Edge* edge) {
37 assert(depth_ != 0);
38 delayed_.insert(edge);
39}
40
41void 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
54void 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
64Pool State::kDefaultPool("", 0);
65Pool State::kConsolePool("console", 1);
66const Rule State::kPhonyRule("phony");
67
68State::State() {
69 bindings_.AddRule(&kPhonyRule);
70 AddPool(&kDefaultPool);
71 AddPool(&kConsolePool);
72}
73
74void State::AddPool(Pool* pool) {
75 assert(LookupPool(pool->name()) == NULL);
76 pools_[pool->name()] = pool;
77}
78
79Pool* 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
86Edge* 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
96Node* 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
105Node* 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
112Node* 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
129void 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
135bool 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
144void 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
150bool 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
160vector<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
178vector<Node*> State::DefaultNodes(string* err) const {
179 return defaults_.empty() ? RootNodes(err) : defaults_;
180}
181
182void 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
192void 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