src/state.cc

   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
  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(set<Edge*>* 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 bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) {
  65   if (!a) return b;
  66   if (!b) return false;
  67   int weight_diff = a->weight() - b->weight();
  68   return ((weight_diff < 0) || (weight_diff == 0 && a < b));
  69 }
  70
  71 Pool State::kDefaultPool("", 0);
  72 Pool State::kConsolePool("console", 1);
  73 const Rule State::kPhonyRule("phony");
  74
  75 State::State() {
  76   bindings_.AddRule(&kPhonyRule);
  77   AddPool(&kDefaultPool);
  78   AddPool(&kConsolePool);
  79 }
  80
  81 void State::AddPool(Pool* pool) {
  82   assert(LookupPool(pool->name()) == NULL);
  83   pools_[pool->name()] = pool;
  84 }
  85
  86 Pool* State::LookupPool(const string& pool_name) {
  87   map<string, Pool*>::iterator i = pools_.find(pool_name);
  88   if (i == pools_.end())
  89     return NULL;
  90   return i->second;
  91 }
  92
  93 Edge* State::AddEdge(const Rule* rule) {
  94   Edge* edge = new Edge();
  95   edge->rule_ = rule;
  96   edge->pool_ = &State::kDefaultPool;
  97   edge->env_ = &bindings_;
  98   edges_.push_back(edge);
  99   return edge;
 100 }
 101
 102 Node* State::GetNode(StringPiece path, unsigned int slash_bits) {
 103   Node* node = LookupNode(path);
 104   if (node)
 105     return node;
 106   node = new Node(path.AsString(), slash_bits);
 107   paths_[node->path()] = node;
 108   return node;
 109 }
 110
 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())
 115     return i->second;
 116   return NULL;
 117 }
 118
 119 Node* State::SpellcheckNode(const string& path) {
 120   const bool kAllowReplacements = true;
 121   const int kMaxValidEditDistance = 3;
 122
 123   int min_distance = kMaxValidEditDistance + 1;
 124   Node* result = NULL;
 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;
 130       result = i->second;
 131     }
 132   }
 133   return result;
 134 }
 135
 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);
 140 }
 141
 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; "
 147             "continuing anyway",
 148             path.AsString().c_str());
 149     return;
 150   }
 151   edge->outputs_.push_back(node);
 152   node->set_in_edge(edge);
 153 }
 154
 155 bool State::AddDefault(StringPiece path, string* err) {
 156   Node* node = LookupNode(path);
 157   if (!node) {
 158     *err = "unknown target '" + path.AsString() + "'";
 159     return false;
 160   }
 161   defaults_.push_back(node);
 162   return true;
 163 }
 164
 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);
 173     }
 174   }
 175
 176   if (!edges_.empty() && root_nodes.empty())
 177     *err = "could not determine root nodes of build graph";
 178
 179   return root_nodes;
 180 }
 181
 182 vector<Node*> State::DefaultNodes(string* err) {
 183   return defaults_.empty() ? RootNodes(err) : defaults_;
 184 }
 185
 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;
 191 }
 192
 193 void State::Dump() {
 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")
 199                                 : "unknown",
 200            node->id());
 201   }
 202   if (!pools_.empty()) {
 203     printf("resource_pools:\n");
 204     for (map<string, Pool*>::const_iterator it = pools_.begin();
 205          it != pools_.end(); ++it)
 206     {
 207       if (!it->second->name().empty()) {
 208         it->second->Dump();
 209       }
 210     }
 211   }
 212 }