Index: tools/gn/item_tree.cc |
diff --git a/tools/gn/item_tree.cc b/tools/gn/item_tree.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..a4d11812e9f363bb0342a3d48c7b2182ce64cec9 |
--- /dev/null |
+++ b/tools/gn/item_tree.cc |
@@ -0,0 +1,193 @@ |
+// 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; |
+} |