1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
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;
}
|
