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 } 542