| // 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; |
| } |