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