Add initial prototype for the GN meta-buildsystem.

tools/gn/item_tree.cc

+// 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/item_tree.h"
+
+#include <algorithm>
+
+#include "base/stl_util.h"
+#include "tools/gn/err.h"
+#include "tools/gn/item.h"
+#include "tools/gn/item_node.h"
+
+namespace {
+
+// 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.
+//
+// Note that "look_for" and "search_in" will be the same node when starting the
+// search, so we don't want to return true in that case.
+//
+// If a cycle is found, the return value will be true and the cycle vector will
+// be filled with the path (in reverse order).
+bool RecursiveFindCycle(const ItemNode* look_for,
+                        const ItemNode* search_in,
+                        std::vector<const ItemNode*>* cycle) {
+  const ItemNode::ItemNodeSet& unresolved =
+      search_in->unresolved_dependencies();
+  for (ItemNode::ItemNodeSet::const_iterator i = unresolved.begin();
+       i != unresolved.end(); ++i) {
+    if (*i == look_for) {
+      cycle->push_back(*i);
+      return true;
+    }
+
+    if (RecursiveFindCycle(look_for, *i, cycle)) {
+      // Found a cycle inside this one, record our path and return.
+      cycle->push_back(*i);
+      return true;
+    }
+  }
+  return false;
+}
+
+}  // namespace
+
+ItemTree::ItemTree() {
+}
+
+ItemTree::~ItemTree() {
+  STLDeleteContainerPairSecondPointers(items_.begin(), items_.end());
+}
+
+ItemNode* ItemTree::GetExistingNodeLocked(const Label& label) {
+  lock_.AssertAcquired();
+  StringToNodeHash::iterator found = items_.find(label);
+  if (found == items_.end())
+    return NULL;
+  return found->second;
+}
+
+void ItemTree::AddNodeLocked(ItemNode* node) {
+  lock_.AssertAcquired();
+  DCHECK(items_.find(node->item()->label()) == items_.end());
+  items_[node->item()->label()] = node;
+}
+
+Err ItemTree::MarkItemGeneratedLocked(const Label& label) {
+  lock_.AssertAcquired();
+  DCHECK(items_.find(label) != items_.end());
+
+  ItemNode* node = items_[label];
+
+  if (!node->unresolved_dependencies().empty()) {
+    // Still some pending dependencies, wait for those to be resolved.
+    node->SetGenerated();
+    return Err();
+  }
+  return MarkItemResolvedLocked(node);
+}
+
+void ItemTree::GetAllItemsLocked(std::vector<const Item*>* dest) const {
+  lock_.AssertAcquired();
+  dest->reserve(items_.size());
+  for (StringToNodeHash::const_iterator i = items_.begin();
+       i != items_.end(); ++i) {
+    dest->push_back(i->second->item());
+  }
+}
+
+Err ItemTree::CheckForBadItems() const {
+  base::AutoLock lock(lock_);
+
+  // Look for errors where we find a GENERATED node that refers to a REFERENCED
+  // one. There may be other nodes depending on the GENERATED one, but listing
+  // all of 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 ItemNode*> bad_nodes;
+  std::string depstring;
+  for (StringToNodeHash::const_iterator i = items_.begin();
+       i != items_.end(); ++i) {
+    const ItemNode* src = i->second;
+
+    if (src->state() == ItemNode::GENERATED) {
+      bad_nodes.push_back(src);
+
+      // Check dependencies.
+      for (ItemNode::ItemNodeSet::const_iterator dest =
+               src->unresolved_dependencies().begin();
+          dest != src->unresolved_dependencies().end();
+          ++dest) {
+        if ((*dest)->state() == ItemNode::REFERENCED) {
+          depstring += "\"" + src->item()->label().GetUserVisibleName(false) +
+              "\" needs " + (*dest)->item()->GetItemTypeName() +
+              " \"" + (*dest)->item()->label().GetUserVisibleName(false) +
+              "\"\n";
+        }
+      }
+    }
+  }
+
+  if (!bad_nodes.empty() && depstring.empty()) {
+    // Our logic above found a bad node but didn't identify the problem. This
+    // normally means a circular dependency.
+    depstring = CheckForCircularDependenciesLocked(bad_nodes);
+    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_nodes.size(); i++) {
+        depstring += "\n\"" +
+            bad_nodes[i]->item()->label().GetUserVisibleName(false) + "\"";
+      }
+    }
+  }
+
+  if (depstring.empty())
+    return Err();
+  return Err(Location(), "Unresolved dependencies.", depstring);
+}
+
+Err ItemTree::MarkItemResolvedLocked(ItemNode* node) {
+  node->SetResolved();
+  node->item()->OnResolved();
+
+  // Now update our waiters, pushing the "resolved" bit.
+  ItemNode::ItemNodeSet waiting;
+  node->SwapOutWaitingDependencySet(&waiting);
+  for (ItemNode::ItemNodeSet::iterator i = waiting.begin();
+       i != waiting.end(); ++i) {
+    ItemNode* waiter = *i;
+
+    // Our node should be unresolved in the waiter.
+    DCHECK(waiter->unresolved_dependencies().find(node) !=
+           waiter->unresolved_dependencies().end());
+    waiter->MarkDirectDependencyResolved(node);
+
+    // Recursively mark nodes as resolved.
+    if (waiter->state() == ItemNode::GENERATED &&
+        waiter->unresolved_dependencies().empty()) {
+      Err err = MarkItemResolvedLocked(waiter);
+      if (err.has_error())
+        return err;
+    }
+  }
+
+  return Err();
+}
+
+std::string ItemTree::CheckForCircularDependenciesLocked(
+    const std::vector<const ItemNode*>& bad_nodes) const {
+  std::vector<const ItemNode*> cycle;
+  if (!RecursiveFindCycle(bad_nodes[0], bad_nodes[0], &cycle))
+    return std::string();  // Didn't find a cycle, something else is wrong.
+
+  cycle.push_back(bad_nodes[0]);
+  std::string ret = "There is a dependency cycle:";
+
+  // Walk backwards since the dependency arrows point in the reverse direction.
+  for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) {
+    ret += "\n  \"" + cycle[i]->item()->label().GetUserVisibleName(false) +
+        "\"";
+    if (i != 0)
+      ret += " ->";
+  }
+
+  return ret;
+}