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

Unified Diff: tools/gn/item_tree.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/item_tree.h ('k') | tools/gn/label_ptr.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: tools/gn/item_tree.cc
diff --git a/tools/gn/item_tree.cc b/tools/gn/item_tree.cc
deleted file mode 100644
index 42e005b5990e53cfbb46a711a3194df347ee5560..0000000000000000000000000000000000000000
--- a/tools/gn/item_tree.cc
+++ /dev/null
@@ -1,208 +0,0 @@
-// 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::ItemNodeMap& unresolved =
- search_in->unresolved_dependencies();
- for (ItemNode::ItemNodeMap::const_iterator i = unresolved.begin();
- i != unresolved.end(); ++i) {
- ItemNode* cur = i->first;
- if (cur == look_for) {
- cycle->push_back(cur);
- return true;
- }
-
- if (RecursiveFindCycle(look_for, cur, cycle)) {
- // Found a cycle inside this one, record our path and return.
- cycle->push_back(cur);
- 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;
-}
-
-bool ItemTree::MarkItemDefinedLocked(const BuildSettings* build_settings,
- const Label& label,
- Err* err) {
- 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.
- if (!node->SetDefined(build_settings, err))
- return false;
- return true;
- }
-
- // No more pending deps.
- MarkItemResolvedLocked(node);
- return true;
-}
-
-void ItemTree::GetAllItemNodesLocked(std::vector<const ItemNode*>* dest) const {
- lock_.AssertAcquired();
- dest->reserve(items_.size());
- for (StringToNodeHash::const_iterator i = items_.begin();
- i != items_.end(); ++i)
- dest->push_back(i->second);
-}
-
-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->should_generate())
- continue; // Skip ungenerated nodes.
-
- if (src->state() == ItemNode::DEFINED ||
- src->state() == ItemNode::PENDING_DEPS) {
- bad_nodes.push_back(src);
-
- // Check dependencies.
- for (ItemNode::ItemNodeMap::const_iterator dest =
- src->unresolved_dependencies().begin();
- dest != src->unresolved_dependencies().end();
- ++dest) {
- const ItemNode* dest_node = dest->first;
- if (dest_node->state() == ItemNode::REFERENCED) {
- depstring += "\"" + src->item()->label().GetUserVisibleName(false) +
- "\" needs " + dest_node->item()->GetItemTypeName() +
- " \"" + dest_node->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);
-}
-
-void ItemTree::MarkItemResolvedLocked(ItemNode* node) {
- node->SetResolved();
- node->item()->OnResolved();
-
- // Now update our waiters, pushing the "resolved" bit.
- ItemNode::ItemNodeMap waiting;
- node->SwapOutWaitingDependencySet(&waiting);
- for (ItemNode::ItemNodeMap::iterator i = waiting.begin();
- i != waiting.end(); ++i) {
- ItemNode* waiter = i->first;
-
- // 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::DEFINED ||
- waiter->state() == ItemNode::PENDING_DEPS) &&
- waiter->unresolved_dependencies().empty())
- MarkItemResolvedLocked(waiter);
- }
-}
-
-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;
-}
« no previous file with comments | « tools/gn/item_tree.h ('k') | tools/gn/label_ptr.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698