Refactor the GN threading model to reduce locking and simplify execution.

Old design: item_tree manages dependency resolution, target_manager creates and hooks up the target dependencies, and the toolchain manager does all kinds of crazy ordering and loading stuff on every thread. There is lots of locking every time the dependency tree is modified.

This patch completely deletes the toolchain manager, item tree, item node, and target manager.

The new design is that the build files are executed on background threads, but then they come back to the main thread which assembles the dependency tree and schedules other file loads. This eliminates almost all locking and a lot of complexity.

The Loader now manages loading the different build files in the correct context, and managing dependencies (loading the build config first, for example). The Builder manages the dependency tree and requests that the Loader load files that it encounters references to.

This simpler design reduces non-test code by ~350 lines. In the current gn build, lock acquisitions go down from 1808 to 116 and it saves about 20ms wall clock time (8% faster). This is a bit deceiving, though, because most of the time is spent on pkg-config which is constant. It speeds up running individual build files by 1000-1500%.

The work of putting the tree together that used to take up this time inside locks is now transferred to the main thread, which looks like it is *sometimes* a bottleneck. This should be easier to optimize in the future, though.

Other tweaks:
 - I fixed cycle finding
 - Directories look prettier on Windows using the "desc" command
 - Tracing output now includes the main thread and marks it as such
 - I updated the base BUILD.gn file for the more recent tree.

R=scottmg@chromium.org

Review URL: https://codereview.chromium.org/56433003

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@234032 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 471 insertions, 0 deletions

diff --git a/tools/gn/builder.cc b/tools/gn/builder.cc
new file mode 100644
index 0000000..07a308b
--- /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;
+}