Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(8)

Unified Diff: tools/gn/builder.cc

Issue 56433003: GN threading refactor (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Created 7 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « tools/gn/builder.h ('k') | tools/gn/builder_record.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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;
+}
« no previous file with comments | « tools/gn/builder.h ('k') | tools/gn/builder_record.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698