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