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 std::string msg = 262 "The type of " + label.GetUserVisibleName(false) + 263 "\nhere is a " + BuilderRecord::GetNameForType(type) + 264 " but was previously seen as a " + 265 BuilderRecord::GetNameForType(record->type()) + ".\n\n" 266 "The most common cause is that the label of a config was put in the\n" 267 "in the deps section of a target (or vice-versa)."; 268 *err = Err(request_from, "Item type does not match.", msg); 269 if (record->originally_referenced_from()) { 270 err->AppendSubErr(Err(record->originally_referenced_from(), 271 std::string())); 272 } 273 return NULL; 274 } 275 276 return record; 277 } 278 279 BuilderRecord* Builder::GetResolvedRecordOfType(const Label& label, 280 const ParseNode* origin, 281 BuilderRecord::ItemType type, 282 Err* err) { 283 BuilderRecord* record = GetRecord(label); 284 if (!record) { 285 *err = Err(origin, "Item not found", 286 "\"" + label.GetUserVisibleName(false) + "\" doesn't\n" 287 "refer to an existent thing."); 288 return NULL; 289 } 290 291 const Item* item = record->item(); 292 if (!item) { 293 *err = Err(origin, "Item not resolved.", 294 "\"" + label.GetUserVisibleName(false) + "\" hasn't been resolved.\n"); 295 return NULL; 296 } 297 298 if (!BuilderRecord::IsItemOfType(item, type)) { 299 *err = Err(origin, 300 std::string("This is not a ") + BuilderRecord::GetNameForType(type), 301 "\"" + label.GetUserVisibleName(false) + "\" refers to a " + 302 item->GetItemTypeName() + " instead of a " + 303 BuilderRecord::GetNameForType(type) + "."); 304 return NULL; 305 } 306 return record; 307 } 308 309 bool Builder::AddDeps(BuilderRecord* record, 310 const LabelConfigVector& configs, 311 Err* err) { 312 for (size_t i = 0; i < configs.size(); i++) { 313 BuilderRecord* dep_record = GetOrCreateRecordOfType( 314 configs[i].label, configs[i].origin, BuilderRecord::ITEM_CONFIG, err); 315 if (!dep_record) 316 return false; 317 record->AddDep(dep_record); 318 } 319 return true; 320 } 321 322 bool Builder::AddDeps(BuilderRecord* record, 323 const LabelTargetVector& targets, 324 Err* err) { 325 for (size_t i = 0; i < targets.size(); i++) { 326 BuilderRecord* dep_record = GetOrCreateRecordOfType( 327 targets[i].label, targets[i].origin, BuilderRecord::ITEM_TARGET, err); 328 if (!dep_record) 329 return false; 330 record->AddDep(dep_record); 331 } 332 return true; 333 } 334 335 bool Builder::AddToolchainDep(BuilderRecord* record, 336 const Target* target, 337 Err* err) { 338 BuilderRecord* toolchain_record = GetOrCreateRecordOfType( 339 target->settings()->toolchain_label(), target->defined_from(), 340 BuilderRecord::ITEM_TOOLCHAIN, err); 341 if (!toolchain_record) 342 return false; 343 record->AddDep(toolchain_record); 344 345 return true; 346 } 347 348 void Builder::RecursiveSetShouldGenerate(BuilderRecord* record, 349 bool force) { 350 if (!force && record->should_generate()) 351 return; // Already set. 352 record->set_should_generate(true); 353 354 const BuilderRecordSet& deps = record->all_deps(); 355 for (BuilderRecordSet::const_iterator i = deps.begin(); 356 i != deps.end(); i++) { 357 BuilderRecord* cur = *i; 358 if (!cur->should_generate()) { 359 ScheduleItemLoadIfNecessary(cur); 360 RecursiveSetShouldGenerate(cur, false); 361 } 362 } 363 } 364 365 void Builder::ScheduleItemLoadIfNecessary(BuilderRecord* record) { 366 const ParseNode* origin = record->originally_referenced_from(); 367 loader_->Load(record->label(), 368 origin ? origin->GetRange() : LocationRange()); 369 } 370 371 bool Builder::ResolveItem(BuilderRecord* record, Err* err) { 372 DCHECK(record->can_resolve() && !record->resolved()); 373 374 if (record->type() == BuilderRecord::ITEM_TARGET) { 375 Target* target = record->item()->AsTarget(); 376 if (!ResolveDeps(&target->deps(), err) || 377 !ResolveDeps(&target->datadeps(), err) || 378 !ResolveConfigs(&target->configs(), err) || 379 !ResolveConfigs(&target->all_dependent_configs(), err) || 380 !ResolveConfigs(&target->direct_dependent_configs(), err) || 381 !ResolveForwardDependentConfigs(target, err)) 382 return false; 383 } 384 385 record->set_resolved(true); 386 record->item()->OnResolved(); 387 if (!resolved_callback_.is_null()) 388 resolved_callback_.Run(record); 389 390 // Recursively update everybody waiting on this item to be resolved. 391 BuilderRecordSet& waiting_set = record->waiting_on_resolution(); 392 for (BuilderRecordSet::iterator i = waiting_set.begin(); 393 i != waiting_set.end(); ++i) { 394 BuilderRecord* waiting = *i; 395 DCHECK(waiting->unresolved_deps().find(record) != 396 waiting->unresolved_deps().end()); 397 waiting->unresolved_deps().erase(record); 398 399 if (waiting->can_resolve()) { 400 if (!ResolveItem(waiting, err)) 401 return false; 402 } 403 } 404 waiting_set.clear(); 405 return true; 406 } 407 408 bool Builder::ResolveDeps(LabelTargetVector* deps, Err* err) { 409 for (size_t i = 0; i < deps->size(); i++) { 410 LabelTargetPair& cur = (*deps)[i]; 411 DCHECK(!cur.ptr); 412 413 BuilderRecord* record = GetResolvedRecordOfType( 414 cur.label, cur.origin, BuilderRecord::ITEM_TARGET, err); 415 if (!record) 416 return false; 417 cur.ptr = record->item()->AsTarget(); 418 } 419 return true; 420 } 421 422 bool Builder::ResolveConfigs(LabelConfigVector* configs, Err* err) { 423 for (size_t i = 0; i < configs->size(); i++) { 424 LabelConfigPair& cur = (*configs)[i]; 425 DCHECK(!cur.ptr); 426 427 BuilderRecord* record = GetResolvedRecordOfType( 428 cur.label, cur.origin, BuilderRecord::ITEM_CONFIG, err); 429 if (!record) 430 return false; 431 cur.ptr = record->item()->AsConfig(); 432 } 433 return true; 434 } 435 436 // "Forward dependent configs" should refer to targets in the deps that should 437 // have their configs forwarded. 438 bool Builder::ResolveForwardDependentConfigs(Target* target, Err* err) { 439 const LabelTargetVector& deps = target->deps(); 440 LabelTargetVector& configs = target->forward_dependent_configs(); 441 442 // Assume that the lists are small so that brute-force n^2 is appropriate. 443 for (size_t config_i = 0; config_i < configs.size(); config_i++) { 444 for (size_t dep_i = 0; dep_i < deps.size(); dep_i++) { 445 if (configs[config_i].label == deps[dep_i].label) { 446 DCHECK(deps[dep_i].ptr); // Should already be resolved. 447 configs[config_i].ptr = deps[dep_i].ptr; 448 break; 449 } 450 } 451 if (!configs[config_i].ptr) { 452 *err = Err(target->defined_from(), 453 "Target in forward_dependent_configs_from was not listed in the deps", 454 "This target has a forward_dependent_configs_from entry that was " 455 "not present in\nthe deps. A target can only forward things it " 456 "depends on. It was forwarding:\n " + 457 configs[config_i].label.GetUserVisibleName(false)); 458 return false; 459 } 460 } 461 return true; 462 } 463 464 std::string Builder::CheckForCircularDependencies( 465 const std::vector<const BuilderRecord*>& bad_records) const { 466 std::vector<const BuilderRecord*> cycle; 467 if (!RecursiveFindCycle(bad_records[0], &cycle)) 468 return std::string(); // Didn't find a cycle, something else is wrong. 469 470 // Walk backwards since the dependency arrows point in the reverse direction. 471 std::string ret; 472 for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) { 473 ret += " " + cycle[i]->label().GetUserVisibleName(false); 474 if (i != 0) 475 ret += " ->\n"; 476 } 477 478 return ret; 479 } 480