Index: tools/gn/builder.cc |
diff --git a/tools/gn/builder.cc b/tools/gn/builder.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..2c3bfdb61185ee463c04990eb9437d1356491da3 |
--- /dev/null |
+++ b/tools/gn/builder.cc |
@@ -0,0 +1,471 @@ |
+// Copyright (c) 2013 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "tools/gn/builder.h" |
+ |
+#include "tools/gn/config.h" |
+#include "tools/gn/err.h" |
+#include "tools/gn/loader.h" |
+#include "tools/gn/scheduler.h" |
+#include "tools/gn/settings.h" |
+#include "tools/gn/target.h" |
+#include "tools/gn/trace.h" |
+ |
+namespace { |
+ |
+typedef BuilderRecord::BuilderRecordSet BuilderRecordSet; |
+ |
+// Recursively looks in the tree for a given node, returning true if it |
+// was found in the dependecy graph. This is used to see if a given node |
+// participates in a cycle. |
+// |
+// If this returns true, the cycle will be in *path. This should point to an |
+// empty vector for the first call. During computation, the path will contain |
+// the full dependency path to the current node. |
+// |
+// Return false means no cycle was found. |
+bool RecursiveFindCycle(const BuilderRecord* search_in, |
+ std::vector<const BuilderRecord*>* path) { |
+ path->push_back(search_in); |
+ |
+ const BuilderRecord::BuilderRecordSet& unresolved = |
+ search_in->unresolved_deps(); |
+ for (BuilderRecord::BuilderRecordSet::const_iterator i = unresolved.begin(); |
+ i != unresolved.end(); ++i) { |
+ const BuilderRecord* cur = *i; |
+ |
+ std::vector<const BuilderRecord*>::iterator found = |
+ std::find(path->begin(), path->end(), cur); |
+ if (found != path->end()) { |
+ // This item is already in the set, we found the cycle. Everything before |
+ // the first definition of cur is irrelevant to the cycle. |
+ path->erase(path->begin(), found); |
+ path->push_back(cur); |
+ return true; |
+ } |
+ |
+ if (RecursiveFindCycle(cur, path)) |
+ return true; // Found cycle. |
+ } |
+ path->pop_back(); |
+ return false; |
+} |
+ |
+} // namespace |
+ |
+Builder::Builder(Loader* loader) : loader_(loader) { |
+} |
+ |
+Builder::~Builder() { |
+} |
+ |
+void Builder::ItemDefined(scoped_ptr<Item> item) { |
+ ScopedTrace trace(TraceItem::TRACE_DEFINE_TARGET, item->label()); |
+ trace.SetToolchain(item->settings()->toolchain_label()); |
+ |
+ BuilderRecord::ItemType type = BuilderRecord::TypeOfItem(item.get()); |
+ |
+ Err err; |
+ BuilderRecord* record = |
+ GetOrCreateRecordOfType(item->label(), item->defined_from(), type, &err); |
+ if (!record) { |
+ g_scheduler->FailWithError(err); |
+ return; |
+ } |
+ |
+ // Check that it's not been already defined. |
+ if (record->item()) { |
+ err = Err(item->defined_from(), "Duplicate definition.", |
+ "The item\n " + item->label().GetUserVisibleName(false) + |
+ "\nwas already defined."); |
+ err.AppendSubErr(Err(record->item()->defined_from(), |
+ "Previous definition:")); |
+ g_scheduler->FailWithError(err); |
+ return; |
+ } |
+ |
+ record->set_item(item.Pass()); |
+ |
+ // Do target-specific dependency setup. This will also schedule dependency |
+ // loads for targets that are required. |
+ switch (type) { |
+ case BuilderRecord::ITEM_TARGET: |
+ if (!TargetDefined(record, &err)) { |
+ g_scheduler->FailWithError(err); |
+ return; |
+ } |
+ break; |
+ case BuilderRecord::ITEM_TOOLCHAIN: |
+ loader_->ToolchainLoaded(record->item()->AsToolchain()); |
+ break; |
+ default: |
+ break; |
+ } |
+ |
+ if (record->can_resolve()) { |
+ if (!ResolveItem(record, &err)) { |
+ g_scheduler->FailWithError(err); |
+ return; |
+ } |
+ } |
+} |
+ |
+const Item* Builder::GetItem(const Label& label) const { |
+ const BuilderRecord* record = GetRecord(label); |
+ if (!record) |
+ return NULL; |
+ return record->item(); |
+} |
+ |
+const Toolchain* Builder::GetToolchain(const Label& label) const { |
+ const BuilderRecord* record = GetRecord(label); |
+ if (!record) |
+ return NULL; |
+ if (!record->item()) |
+ return NULL; |
+ return record->item()->AsToolchain(); |
+} |
+ |
+std::vector<const BuilderRecord*> Builder::GetAllRecords() const { |
+ std::vector<const BuilderRecord*> result; |
+ result.reserve(records_.size()); |
+ for (RecordMap::const_iterator i = records_.begin(); |
+ i != records_.end(); ++i) |
+ result.push_back(i->second); |
+ return result; |
+} |
+ |
+std::vector<const Target*> Builder::GetAllResolvedTargets() const { |
+ std::vector<const Target*> result; |
+ result.reserve(records_.size()); |
+ for (RecordMap::const_iterator i = records_.begin(); |
+ i != records_.end(); ++i) { |
+ if (i->second->type() == BuilderRecord::ITEM_TARGET && |
+ i->second->should_generate() && i->second->item()) |
+ result.push_back(i->second->item()->AsTarget()); |
+ } |
+ return result; |
+} |
+ |
+const BuilderRecord* Builder::GetRecord(const Label& label) const { |
+ // Forward to the non-const version. |
+ return const_cast<Builder*>(this)->GetRecord(label); |
+} |
+ |
+BuilderRecord* Builder::GetRecord(const Label& label) { |
+ RecordMap::iterator found = records_.find(label); |
+ if (found == records_.end()) |
+ return NULL; |
+ return found->second; |
+} |
+ |
+bool Builder::CheckForBadItems(Err* err) const { |
+ // Look for errors where we find a defined node with an item that refers to |
+ // an undefined one with no item. There may be other nodes in turn depending |
+ // on our defined one, but listing those isn't helpful: we want to find the |
+ // broken link. |
+ // |
+ // This finds normal "missing dependency" errors but does not find circular |
+ // dependencies because in this case all items in the cycle will be GENERATED |
+ // but none will be resolved. If this happens, we'll check explicitly for |
+ // that below. |
+ std::vector<const BuilderRecord*> bad_records; |
+ std::string depstring; |
+ for (RecordMap::const_iterator i = records_.begin(); |
+ i != records_.end(); ++i) { |
+ const BuilderRecord* src = i->second; |
+ if (!src->should_generate()) |
+ continue; // Skip ungenerated nodes. |
+ |
+ if (!src->resolved()) { |
+ bad_records.push_back(src); |
+ |
+ // Check dependencies. |
+ for (BuilderRecord::BuilderRecordSet::const_iterator dest_iter = |
+ src->unresolved_deps().begin(); |
+ dest_iter != src->unresolved_deps().end(); |
+ ++dest_iter) { |
+ const BuilderRecord* dest = *dest_iter; |
+ if (!dest->item()) { |
+ depstring += src->label().GetUserVisibleName(true) + |
+ "\n needs " + dest->label().GetUserVisibleName(true) + "\n"; |
+ } |
+ } |
+ } |
+ } |
+ |
+ if (!depstring.empty()) { |
+ *err = Err(Location(), "Unresolved dependencies.", depstring); |
+ return false; |
+ } |
+ |
+ if (!bad_records.empty()) { |
+ // Our logic above found a bad node but didn't identify the problem. This |
+ // normally means a circular dependency. |
+ depstring = CheckForCircularDependencies(bad_records); |
+ if (depstring.empty()) { |
+ // Something's very wrong, just dump out the bad nodes. |
+ depstring = "I have no idea what went wrong, but these are unresolved, " |
+ "possible due to an\ninternal error:"; |
+ for (size_t i = 0; i < bad_records.size(); i++) { |
+ depstring += "\n\"" + |
+ bad_records[i]->label().GetUserVisibleName(false) + "\""; |
+ } |
+ *err = Err(Location(), "", depstring); |
+ } else { |
+ *err = Err(Location(), "Dependency cycle:", depstring); |
+ } |
+ return false; |
+ } |
+ |
+ return true; |
+} |
+ |
+bool Builder::TargetDefined(BuilderRecord* record, Err* err) { |
+ Target* target = record->item()->AsTarget(); |
+ |
+ if (!AddDeps(record, target->deps(), err) || |
+ !AddDeps(record, target->datadeps(), err) || |
+ !AddDeps(record, target->configs(), err) || |
+ !AddDeps(record, target->all_dependent_configs(), err) || |
+ !AddDeps(record, target->direct_dependent_configs(), err) || |
+ !AddToolchainDep(record, target, err)) |
+ return false; |
+ |
+ // All targets in the default toolchain get generated by default. We also |
+ // check if this target was previously marked as "required" and force setting |
+ // the bit again so the target's dependencies (which we now know) get the |
+ // required bit pushed to them. |
+ if (record->should_generate() || target->settings()->is_default()) |
+ RecursiveSetShouldGenerate(record, true); |
+ |
+ return true; |
+} |
+ |
+BuilderRecord* Builder::GetOrCreateRecordOfType(const Label& label, |
+ const ParseNode* request_from, |
+ BuilderRecord::ItemType type, |
+ Err* err) { |
+ BuilderRecord* record = GetRecord(label); |
+ if (!record) { |
+ // Not seen this record yet, create a new one. |
+ record = new BuilderRecord(type, label); |
+ records_[label] = record; |
+ return record; |
+ } |
+ |
+ // Check types. |
+ if (record->type() != type) { |
+ *err = Err(request_from, "Item type does not match.", |
+ "The item \"" + label.GetUserVisibleName(false) + |
+ "\" was expected\nto be a " + |
+ BuilderRecord::GetNameForType(type) + |
+ " but was previously\n referenced as a " + |
+ BuilderRecord::GetNameForType(record->type())); |
+ err->AppendSubErr(Err(record->originally_referenced_from(), |
+ "The previous reference was here.")); |
+ return NULL; |
+ } |
+ |
+ return record; |
+} |
+ |
+BuilderRecord* Builder::GetResolvedRecordOfType(const Label& label, |
+ const ParseNode* origin, |
+ BuilderRecord::ItemType type, |
+ Err* err) { |
+ BuilderRecord* record = GetRecord(label); |
+ if (!record) { |
+ *err = Err(origin, "Item not found", |
+ "\"" + label.GetUserVisibleName(false) + "\" doesn't\n" |
+ "refer to an existant thing."); |
+ return NULL; |
+ } |
+ |
+ const Item* item = record->item(); |
+ if (!item) { |
+ *err = Err(origin, "Item not resolved.", |
+ "\"" + label.GetUserVisibleName(false) + "\" hasn't been resolved.\n"); |
+ return NULL; |
+ } |
+ |
+ if (!BuilderRecord::IsItemOfType(item, type)) { |
+ *err = Err(origin, |
+ std::string("This is not a ") + BuilderRecord::GetNameForType(type), |
+ "\"" + label.GetUserVisibleName(false) + "\" refers to a " + |
+ item->GetItemTypeName() + " instead of a " + |
+ BuilderRecord::GetNameForType(type) + "."); |
+ return NULL; |
+ } |
+ return record; |
+} |
+ |
+bool Builder::AddDeps(BuilderRecord* record, |
+ const LabelConfigVector& configs, |
+ Err* err) { |
+ for (size_t i = 0; i < configs.size(); i++) { |
+ BuilderRecord* dep_record = GetOrCreateRecordOfType( |
+ configs[i].label, configs[i].origin, BuilderRecord::ITEM_CONFIG, err); |
+ if (!dep_record) |
+ return false; |
+ record->AddDep(dep_record); |
+ } |
+ return true; |
+} |
+ |
+bool Builder::AddDeps(BuilderRecord* record, |
+ const LabelTargetVector& targets, |
+ Err* err) { |
+ for (size_t i = 0; i < targets.size(); i++) { |
+ BuilderRecord* dep_record = GetOrCreateRecordOfType( |
+ targets[i].label, targets[i].origin, BuilderRecord::ITEM_TARGET, err); |
+ if (!dep_record) |
+ return false; |
+ record->AddDep(dep_record); |
+ } |
+ return true; |
+} |
+ |
+bool Builder::AddToolchainDep(BuilderRecord* record, |
+ const Target* target, |
+ Err* err) { |
+ BuilderRecord* toolchain_record = GetOrCreateRecordOfType( |
+ target->settings()->toolchain_label(), target->defined_from(), |
+ BuilderRecord::ITEM_TOOLCHAIN, err); |
+ if (!toolchain_record) |
+ return false; |
+ record->AddDep(toolchain_record); |
+ |
+ return true; |
+} |
+ |
+void Builder::RecursiveSetShouldGenerate(BuilderRecord* record, |
+ bool force) { |
+ if (!force && record->should_generate()) |
+ return; // Already set. |
+ record->set_should_generate(true); |
+ |
+ const BuilderRecordSet& deps = record->all_deps(); |
+ for (BuilderRecordSet::const_iterator i = deps.begin(); |
+ i != deps.end(); i++) { |
+ BuilderRecord* cur = *i; |
+ if (!cur->should_generate()) { |
+ ScheduleItemLoadIfNecessary(cur); |
+ RecursiveSetShouldGenerate(cur, false); |
+ } |
+ } |
+} |
+ |
+void Builder::ScheduleItemLoadIfNecessary(BuilderRecord* record) { |
+ loader_->Load(record->label()); |
+} |
+ |
+bool Builder::ResolveItem(BuilderRecord* record, Err* err) { |
+ DCHECK(record->can_resolve() && !record->resolved()); |
+ |
+ if (record->type() == BuilderRecord::ITEM_TARGET) { |
+ Target* target = record->item()->AsTarget(); |
+ if (!ResolveDeps(&target->deps(), err) || |
+ !ResolveDeps(&target->datadeps(), err) || |
+ !ResolveConfigs(&target->configs(), err) || |
+ !ResolveConfigs(&target->all_dependent_configs(), err) || |
+ !ResolveConfigs(&target->direct_dependent_configs(), err) || |
+ !ResolveForwardDependentConfigs(target, err)) |
+ return false; |
+ } |
+ |
+ record->set_resolved(true); |
+ record->item()->OnResolved(); |
+ if (!resolved_callback_.is_null()) |
+ resolved_callback_.Run(record->item()); |
+ |
+ // Recursively update everybody waiting on this item to be resolved. |
+ BuilderRecordSet& waiting_set = record->waiting_on_resolution(); |
+ for (BuilderRecordSet::iterator i = waiting_set.begin(); |
+ i != waiting_set.end(); ++i) { |
+ BuilderRecord* waiting = *i; |
+ DCHECK(waiting->unresolved_deps().find(record) != |
+ waiting->unresolved_deps().end()); |
+ waiting->unresolved_deps().erase(record); |
+ |
+ if (waiting->can_resolve()) { |
+ if (!ResolveItem(waiting, err)) |
+ return false; |
+ } |
+ } |
+ waiting_set.clear(); |
+ return true; |
+} |
+ |
+bool Builder::ResolveDeps(LabelTargetVector* deps, Err* err) { |
+ for (size_t i = 0; i < deps->size(); i++) { |
+ LabelTargetPair& cur = (*deps)[i]; |
+ DCHECK(!cur.ptr); |
+ |
+ BuilderRecord* record = GetResolvedRecordOfType( |
+ cur.label, cur.origin, BuilderRecord::ITEM_TARGET, err); |
+ if (!record) |
+ return false; |
+ cur.ptr = record->item()->AsTarget(); |
+ } |
+ return true; |
+} |
+ |
+bool Builder::ResolveConfigs(LabelConfigVector* configs, Err* err) { |
+ for (size_t i = 0; i < configs->size(); i++) { |
+ LabelConfigPair& cur = (*configs)[i]; |
+ DCHECK(!cur.ptr); |
+ |
+ BuilderRecord* record = GetResolvedRecordOfType( |
+ cur.label, cur.origin, BuilderRecord::ITEM_CONFIG, err); |
+ if (!record) |
+ return false; |
+ cur.ptr = record->item()->AsConfig(); |
+ } |
+ return true; |
+} |
+ |
+// "Forward dependent configs" should refer to targets in the deps that should |
+// have their configs forwarded. |
+bool Builder::ResolveForwardDependentConfigs(Target* target, Err* err) { |
+ const LabelTargetVector& deps = target->deps(); |
+ LabelTargetVector& configs = target->forward_dependent_configs(); |
+ |
+ // Assume that the lists are small so that brute-force n^2 is appropriate. |
+ for (size_t config_i = 0; config_i < configs.size(); config_i++) { |
+ for (size_t dep_i = 0; dep_i < deps.size(); dep_i++) { |
+ if (configs[config_i].label == deps[dep_i].label) { |
+ DCHECK(deps[dep_i].ptr); // Should already be resolved. |
+ configs[config_i].ptr = deps[dep_i].ptr; |
+ break; |
+ } |
+ } |
+ if (!configs[config_i].ptr) { |
+ *err = Err(target->defined_from(), |
+ "Target in forward_dependent_configs_from was not listed in the deps", |
+ "The target \"" + configs[config_i].label.GetUserVisibleName(false) + |
+ "\"\n was not present in the deps. This thing is used to forward\n" |
+ "configs from direct dependents."); |
+ return false; |
+ } |
+ } |
+ return true; |
+} |
+ |
+std::string Builder::CheckForCircularDependencies( |
+ const std::vector<const BuilderRecord*>& bad_records) const { |
+ std::vector<const BuilderRecord*> cycle; |
+ if (!RecursiveFindCycle(bad_records[0], &cycle)) |
+ return std::string(); // Didn't find a cycle, something else is wrong. |
+ |
+ // Walk backwards since the dependency arrows point in the reverse direction. |
+ std::string ret; |
+ for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) { |
+ ret += " " + cycle[i]->label().GetUserVisibleName(false); |
+ if (i != 0) |
+ ret += " ->\n"; |
+ } |
+ |
+ return ret; |
+} |