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