src/tools/gn/builder.cc

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "tools/gn/builder.h"
   6
   7 #include "tools/gn/config.h"
   8 #include "tools/gn/err.h"
   9 #include "tools/gn/loader.h"
  10 #include "tools/gn/scheduler.h"
  11 #include "tools/gn/settings.h"
  12 #include "tools/gn/target.h"
  13 #include "tools/gn/trace.h"
  14
  15 namespace {
  16
  17 typedef BuilderRecord::BuilderRecordSet BuilderRecordSet;
  18
  19 // Recursively looks in the tree for a given node, returning true if it
  20 // was found in the dependecy graph. This is used to see if a given node
  21 // participates in a cycle.
  22 //
  23 // If this returns true, the cycle will be in *path. This should point to an
  24 // empty vector for the first call. During computation, the path will contain
  25 // the full dependency path to the current node.
  26 //
  27 // Return false means no cycle was found.
  28 bool RecursiveFindCycle(const BuilderRecord* search_in,
  29                         std::vector<const BuilderRecord*>* path) {
  30   path->push_back(search_in);
  31
  32   const BuilderRecord::BuilderRecordSet& unresolved =
  33       search_in->unresolved_deps();
  34   for (BuilderRecord::BuilderRecordSet::const_iterator i = unresolved.begin();
  35        i != unresolved.end(); ++i) {
  36     const BuilderRecord* cur = *i;
  37
  38     std::vector<const BuilderRecord*>::iterator found =
  39         std::find(path->begin(), path->end(), cur);
  40     if (found != path->end()) {
  41       // This item is already in the set, we found the cycle. Everything before
  42       // the first definition of cur is irrelevant to the cycle.
  43       path->erase(path->begin(), found);
  44       path->push_back(cur);
  45       return true;
  46     }
  47
  48     if (RecursiveFindCycle(cur, path))
  49       return true;  // Found cycle.
  50   }
  51   path->pop_back();
  52   return false;
  53 }
  54
  55 }  // namespace
  56
  57 Builder::Builder(Loader* loader) : loader_(loader) {
  58 }
  59
  60 Builder::~Builder() {
  61 }
  62
  63 void Builder::ItemDefined(scoped_ptr<Item> item) {
  64   ScopedTrace trace(TraceItem::TRACE_DEFINE_TARGET, item->label());
  65   trace.SetToolchain(item->settings()->toolchain_label());
  66
  67   BuilderRecord::ItemType type = BuilderRecord::TypeOfItem(item.get());
  68
  69   Err err;
  70   BuilderRecord* record =
  71       GetOrCreateRecordOfType(item->label(), item->defined_from(), type, &err);
  72   if (!record) {
  73     g_scheduler->FailWithError(err);
  74     return;
  75   }
  76
  77   // Check that it's not been already defined.
  78   if (record->item()) {
  79     err = Err(item->defined_from(), "Duplicate definition.",
  80         "The item\n  " + item->label().GetUserVisibleName(false) +
  81         "\nwas already defined.");
  82     err.AppendSubErr(Err(record->item()->defined_from(),
  83                          "Previous definition:"));
  84     g_scheduler->FailWithError(err);
  85     return;
  86   }
  87
  88   record->set_item(item.Pass());
  89
  90   // Do target-specific dependency setup. This will also schedule dependency
  91   // loads for targets that are required.
  92   switch (type) {
  93     case BuilderRecord::ITEM_TARGET:
  94       if (!TargetDefined(record, &err)) {
  95         g_scheduler->FailWithError(err);
  96         return;
  97       }
  98       break;
  99     case BuilderRecord::ITEM_TOOLCHAIN:
 100       loader_->ToolchainLoaded(record->item()->AsToolchain());
 101       break;
 102     default:
 103       break;
 104   }
 105
 106   if (record->can_resolve()) {
 107     if (!ResolveItem(record, &err)) {
 108       g_scheduler->FailWithError(err);
 109       return;
 110     }
 111   }
 112 }
 113
 114 const Item* Builder::GetItem(const Label& label) const {
 115   const BuilderRecord* record = GetRecord(label);
 116   if (!record)
 117     return NULL;
 118   return record->item();
 119 }
 120
 121 const Toolchain* Builder::GetToolchain(const Label& label) const {
 122   const BuilderRecord* record = GetRecord(label);
 123   if (!record)
 124     return NULL;
 125   if (!record->item())
 126     return NULL;
 127   return record->item()->AsToolchain();
 128 }
 129
 130 std::vector<const BuilderRecord*> Builder::GetAllRecords() const {
 131   std::vector<const BuilderRecord*> result;
 132   result.reserve(records_.size());
 133   for (RecordMap::const_iterator i = records_.begin();
 134        i != records_.end(); ++i)
 135     result.push_back(i->second);
 136   return result;
 137 }
 138
 139 std::vector<const Target*> Builder::GetAllResolvedTargets() const {
 140   std::vector<const Target*> result;
 141   result.reserve(records_.size());
 142   for (RecordMap::const_iterator i = records_.begin();
 143        i != records_.end(); ++i) {
 144     if (i->second->type() == BuilderRecord::ITEM_TARGET &&
 145         i->second->should_generate() && i->second->item())
 146       result.push_back(i->second->item()->AsTarget());
 147   }
 148   return result;
 149 }
 150
 151 const BuilderRecord* Builder::GetRecord(const Label& label) const {
 152   // Forward to the non-const version.
 153   return const_cast<Builder*>(this)->GetRecord(label);
 154 }
 155
 156 BuilderRecord* Builder::GetRecord(const Label& label) {
 157   RecordMap::iterator found = records_.find(label);
 158   if (found == records_.end())
 159     return NULL;
 160   return found->second;
 161 }
 162
 163 bool Builder::CheckForBadItems(Err* err) const {
 164   // Look for errors where we find a defined node with an item that refers to
 165   // an undefined one with no item. There may be other nodes in turn depending
 166   // on our defined one, but listing those isn't helpful: we want to find the
 167   // broken link.
 168   //
 169   // This finds normal "missing dependency" errors but does not find circular
 170   // dependencies because in this case all items in the cycle will be GENERATED
 171   // but none will be resolved. If this happens, we'll check explicitly for
 172   // that below.
 173   std::vector<const BuilderRecord*> bad_records;
 174   std::string depstring;
 175   for (RecordMap::const_iterator i = records_.begin();
 176        i != records_.end(); ++i) {
 177     const BuilderRecord* src = i->second;
 178     if (!src->should_generate())
 179       continue;  // Skip ungenerated nodes.
 180
 181     if (!src->resolved()) {
 182       bad_records.push_back(src);
 183
 184       // Check dependencies.
 185       for (BuilderRecord::BuilderRecordSet::const_iterator dest_iter =
 186                src->unresolved_deps().begin();
 187           dest_iter != src->unresolved_deps().end();
 188           ++dest_iter) {
 189         const BuilderRecord* dest = *dest_iter;
 190         if (!dest->item()) {
 191           depstring += src->label().GetUserVisibleName(true) +
 192               "\n  needs " + dest->label().GetUserVisibleName(true) + "\n";
 193         }
 194       }
 195     }
 196   }
 197
 198   if (!depstring.empty()) {
 199     *err = Err(Location(), "Unresolved dependencies.", depstring);
 200     return false;
 201   }
 202
 203   if (!bad_records.empty()) {
 204     // Our logic above found a bad node but didn't identify the problem. This
 205     // normally means a circular dependency.
 206     depstring = CheckForCircularDependencies(bad_records);
 207     if (depstring.empty()) {
 208       // Something's very wrong, just dump out the bad nodes.
 209       depstring = "I have no idea what went wrong, but these are unresolved, "
 210           "possible due to an\ninternal error:";
 211       for (size_t i = 0; i < bad_records.size(); i++) {
 212         depstring += "\n\"" +
 213             bad_records[i]->label().GetUserVisibleName(false) + "\"";
 214       }
 215       *err = Err(Location(), "", depstring);
 216     } else {
 217       *err = Err(Location(), "Dependency cycle:", depstring);
 218     }
 219     return false;
 220   }
 221
 222   return true;
 223 }
 224
 225 bool Builder::TargetDefined(BuilderRecord* record, Err* err) {
 226   Target* target = record->item()->AsTarget();
 227
 228   if (!AddDeps(record, target->deps(), err) ||
 229       !AddDeps(record, target->datadeps(), err) ||
 230       !AddDeps(record, target->configs(), err) ||
 231       !AddDeps(record, target->all_dependent_configs(), err) ||
 232       !AddDeps(record, target->direct_dependent_configs(), err) ||
 233       !AddToolchainDep(record, target, err))
 234     return false;
 235
 236   // All targets in the default toolchain get generated by default. We also
 237   // check if this target was previously marked as "required" and force setting
 238   // the bit again so the target's dependencies (which we now know) get the
 239   // required bit pushed to them.
 240   if (record->should_generate() || target->settings()->is_default())
 241     RecursiveSetShouldGenerate(record, true);
 242
 243   return true;
 244 }
 245
 246 BuilderRecord* Builder::GetOrCreateRecordOfType(const Label& label,
 247                                                 const ParseNode* request_from,
 248                                                 BuilderRecord::ItemType type,
 249                                                 Err* err) {
 250   BuilderRecord* record = GetRecord(label);
 251   if (!record) {
 252     // Not seen this record yet, create a new one.
 253     record = new BuilderRecord(type, label);
 254     record->set_originally_referenced_from(request_from);
 255     records_[label] = record;
 256     return record;
 257   }
 258
 259   // Check types.
 260   if (record->type() != type) {
 261     *err = Err(request_from, "Item type does not match.",
 262         "The item \"" + label.GetUserVisibleName(false) +
 263         "\"\nwas expected to be a " +
 264         BuilderRecord::GetNameForType(type) +
 265         " but was previously referenced as a " +
 266         BuilderRecord::GetNameForType(record->type()));
 267     if (record->originally_referenced_from()) {
 268       err->AppendSubErr(Err(record->originally_referenced_from(),
 269                             "The previous reference was here."));
 270     }
 271     return NULL;
 272   }
 273
 274   return record;
 275 }
 276
 277 BuilderRecord* Builder::GetResolvedRecordOfType(const Label& label,
 278                                                 const ParseNode* origin,
 279                                                 BuilderRecord::ItemType type,
 280                                                 Err* err) {
 281   BuilderRecord* record = GetRecord(label);
 282   if (!record) {
 283     *err = Err(origin, "Item not found",
 284         "\"" + label.GetUserVisibleName(false) + "\" doesn't\n"
 285         "refer to an existent thing.");
 286     return NULL;
 287   }
 288
 289   const Item* item = record->item();
 290   if (!item) {
 291     *err = Err(origin, "Item not resolved.",
 292         "\"" + label.GetUserVisibleName(false) + "\" hasn't been resolved.\n");
 293     return NULL;
 294   }
 295
 296   if (!BuilderRecord::IsItemOfType(item, type)) {
 297     *err = Err(origin,
 298         std::string("This is not a ") + BuilderRecord::GetNameForType(type),
 299         "\"" + label.GetUserVisibleName(false) + "\" refers to a " +
 300         item->GetItemTypeName() + " instead of a " +
 301         BuilderRecord::GetNameForType(type) + ".");
 302     return NULL;
 303   }
 304   return record;
 305 }
 306
 307 bool Builder::AddDeps(BuilderRecord* record,
 308                       const LabelConfigVector& configs,
 309                       Err* err) {
 310   for (size_t i = 0; i < configs.size(); i++) {
 311     BuilderRecord* dep_record = GetOrCreateRecordOfType(
 312         configs[i].label, configs[i].origin, BuilderRecord::ITEM_CONFIG, err);
 313     if (!dep_record)
 314       return false;
 315     record->AddDep(dep_record);
 316   }
 317   return true;
 318 }
 319
 320 bool Builder::AddDeps(BuilderRecord* record,
 321                       const LabelTargetVector& targets,
 322                       Err* err) {
 323   for (size_t i = 0; i < targets.size(); i++) {
 324     BuilderRecord* dep_record = GetOrCreateRecordOfType(
 325         targets[i].label, targets[i].origin, BuilderRecord::ITEM_TARGET, err);
 326     if (!dep_record)
 327       return false;
 328     record->AddDep(dep_record);
 329   }
 330   return true;
 331 }
 332
 333 bool Builder::AddToolchainDep(BuilderRecord* record,
 334                               const Target* target,
 335                               Err* err) {
 336   BuilderRecord* toolchain_record = GetOrCreateRecordOfType(
 337       target->settings()->toolchain_label(), target->defined_from(),
 338       BuilderRecord::ITEM_TOOLCHAIN, err);
 339   if (!toolchain_record)
 340     return false;
 341   record->AddDep(toolchain_record);
 342
 343   return true;
 344 }
 345
 346 void Builder::RecursiveSetShouldGenerate(BuilderRecord* record,
 347                                          bool force) {
 348   if (!force && record->should_generate())
 349     return;  // Already set.
 350   record->set_should_generate(true);
 351
 352   const BuilderRecordSet& deps = record->all_deps();
 353   for (BuilderRecordSet::const_iterator i = deps.begin();
 354        i != deps.end(); i++) {
 355     BuilderRecord* cur = *i;
 356     if (!cur->should_generate()) {
 357       ScheduleItemLoadIfNecessary(cur);
 358       RecursiveSetShouldGenerate(cur, false);
 359     }
 360   }
 361 }
 362
 363 void Builder::ScheduleItemLoadIfNecessary(BuilderRecord* record) {
 364   loader_->Load(record->label());
 365 }
 366
 367 bool Builder::ResolveItem(BuilderRecord* record, Err* err) {
 368   DCHECK(record->can_resolve() && !record->resolved());
 369
 370   if (record->type() == BuilderRecord::ITEM_TARGET) {
 371     Target* target = record->item()->AsTarget();
 372     if (!ResolveDeps(&target->deps(), err) ||
 373         !ResolveDeps(&target->datadeps(), err) ||
 374         !ResolveConfigs(&target->configs(), err) ||
 375         !ResolveConfigs(&target->all_dependent_configs(), err) ||
 376         !ResolveConfigs(&target->direct_dependent_configs(), err) ||
 377         !ResolveForwardDependentConfigs(target, err))
 378       return false;
 379   }
 380
 381   record->set_resolved(true);
 382   record->item()->OnResolved();
 383   if (!resolved_callback_.is_null())
 384     resolved_callback_.Run(record);
 385
 386   // Recursively update everybody waiting on this item to be resolved.
 387   BuilderRecordSet& waiting_set = record->waiting_on_resolution();
 388   for (BuilderRecordSet::iterator i = waiting_set.begin();
 389        i != waiting_set.end(); ++i) {
 390     BuilderRecord* waiting = *i;
 391     DCHECK(waiting->unresolved_deps().find(record) !=
 392            waiting->unresolved_deps().end());
 393     waiting->unresolved_deps().erase(record);
 394
 395     if (waiting->can_resolve()) {
 396       if (!ResolveItem(waiting, err))
 397         return false;
 398     }
 399   }
 400   waiting_set.clear();
 401   return true;
 402 }
 403
 404 bool Builder::ResolveDeps(LabelTargetVector* deps, Err* err) {
 405   for (size_t i = 0; i < deps->size(); i++) {
 406     LabelTargetPair& cur = (*deps)[i];
 407     DCHECK(!cur.ptr);
 408
 409     BuilderRecord* record = GetResolvedRecordOfType(
 410         cur.label, cur.origin, BuilderRecord::ITEM_TARGET, err);
 411     if (!record)
 412       return false;
 413     cur.ptr = record->item()->AsTarget();
 414   }
 415   return true;
 416 }
 417
 418 bool Builder::ResolveConfigs(LabelConfigVector* configs, Err* err) {
 419   for (size_t i = 0; i < configs->size(); i++) {
 420     LabelConfigPair& cur = (*configs)[i];
 421     DCHECK(!cur.ptr);
 422
 423     BuilderRecord* record = GetResolvedRecordOfType(
 424         cur.label, cur.origin, BuilderRecord::ITEM_CONFIG, err);
 425     if (!record)
 426       return false;
 427     cur.ptr = record->item()->AsConfig();
 428   }
 429   return true;
 430 }
 431
 432 // "Forward dependent configs" should refer to targets in the deps that should
 433 // have their configs forwarded.
 434 bool Builder::ResolveForwardDependentConfigs(Target* target, Err* err) {
 435   const LabelTargetVector& deps = target->deps();
 436   LabelTargetVector& configs = target->forward_dependent_configs();
 437
 438   // Assume that the lists are small so that brute-force n^2 is appropriate.
 439   for (size_t config_i = 0; config_i < configs.size(); config_i++) {
 440     for (size_t dep_i = 0; dep_i < deps.size(); dep_i++) {
 441       if (configs[config_i].label == deps[dep_i].label) {
 442         DCHECK(deps[dep_i].ptr);  // Should already be resolved.
 443         configs[config_i].ptr = deps[dep_i].ptr;
 444         break;
 445       }
 446     }
 447     if (!configs[config_i].ptr) {
 448       *err = Err(target->defined_from(),
 449           "Target in forward_dependent_configs_from was not listed in the deps",
 450           "The target \"" + configs[config_i].label.GetUserVisibleName(false) +
 451           "\"\n was not present in the deps. This thing is used to forward\n"
 452           "configs from direct dependents.");
 453       return false;
 454     }
 455   }
 456   return true;
 457 }
 458
 459 std::string Builder::CheckForCircularDependencies(
 460     const std::vector<const BuilderRecord*>& bad_records) const {
 461   std::vector<const BuilderRecord*> cycle;
 462   if (!RecursiveFindCycle(bad_records[0], &cycle))
 463     return std::string();  // Didn't find a cycle, something else is wrong.
 464
 465   // Walk backwards since the dependency arrows point in the reverse direction.
 466   std::string ret;
 467   for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) {
 468     ret += "  " + cycle[i]->label().GetUserVisibleName(false);
 469     if (i != 0)
 470       ret += " ->\n";
 471   }
 472
 473   return ret;
 474 }