OLD | NEW |
| (Empty) |
1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "tools/gn/item_tree.h" | |
6 | |
7 #include <algorithm> | |
8 | |
9 #include "base/stl_util.h" | |
10 #include "tools/gn/err.h" | |
11 #include "tools/gn/item.h" | |
12 #include "tools/gn/item_node.h" | |
13 | |
14 namespace { | |
15 | |
16 // Recursively looks in the tree for a given node, returning true if it | |
17 // was found in the dependecy graph. This is used to see if a given node | |
18 // participates in a cycle. | |
19 // | |
20 // Note that "look_for" and "search_in" will be the same node when starting the | |
21 // search, so we don't want to return true in that case. | |
22 // | |
23 // If a cycle is found, the return value will be true and the cycle vector will | |
24 // be filled with the path (in reverse order). | |
25 bool RecursiveFindCycle(const ItemNode* look_for, | |
26 const ItemNode* search_in, | |
27 std::vector<const ItemNode*>* cycle) { | |
28 const ItemNode::ItemNodeMap& unresolved = | |
29 search_in->unresolved_dependencies(); | |
30 for (ItemNode::ItemNodeMap::const_iterator i = unresolved.begin(); | |
31 i != unresolved.end(); ++i) { | |
32 ItemNode* cur = i->first; | |
33 if (cur == look_for) { | |
34 cycle->push_back(cur); | |
35 return true; | |
36 } | |
37 | |
38 if (RecursiveFindCycle(look_for, cur, cycle)) { | |
39 // Found a cycle inside this one, record our path and return. | |
40 cycle->push_back(cur); | |
41 return true; | |
42 } | |
43 } | |
44 return false; | |
45 } | |
46 | |
47 } // namespace | |
48 | |
49 ItemTree::ItemTree() { | |
50 } | |
51 | |
52 ItemTree::~ItemTree() { | |
53 STLDeleteContainerPairSecondPointers(items_.begin(), items_.end()); | |
54 } | |
55 | |
56 ItemNode* ItemTree::GetExistingNodeLocked(const Label& label) { | |
57 lock_.AssertAcquired(); | |
58 StringToNodeHash::iterator found = items_.find(label); | |
59 if (found == items_.end()) | |
60 return NULL; | |
61 return found->second; | |
62 } | |
63 | |
64 void ItemTree::AddNodeLocked(ItemNode* node) { | |
65 lock_.AssertAcquired(); | |
66 DCHECK(items_.find(node->item()->label()) == items_.end()); | |
67 items_[node->item()->label()] = node; | |
68 } | |
69 | |
70 bool ItemTree::MarkItemDefinedLocked(const BuildSettings* build_settings, | |
71 const Label& label, | |
72 Err* err) { | |
73 lock_.AssertAcquired(); | |
74 DCHECK(items_.find(label) != items_.end()); | |
75 | |
76 ItemNode* node = items_[label]; | |
77 | |
78 if (!node->unresolved_dependencies().empty()) { | |
79 // Still some pending dependencies, wait for those to be resolved. | |
80 if (!node->SetDefined(build_settings, err)) | |
81 return false; | |
82 return true; | |
83 } | |
84 | |
85 // No more pending deps. | |
86 MarkItemResolvedLocked(node); | |
87 return true; | |
88 } | |
89 | |
90 void ItemTree::GetAllItemNodesLocked(std::vector<const ItemNode*>* dest) const { | |
91 lock_.AssertAcquired(); | |
92 dest->reserve(items_.size()); | |
93 for (StringToNodeHash::const_iterator i = items_.begin(); | |
94 i != items_.end(); ++i) | |
95 dest->push_back(i->second); | |
96 } | |
97 | |
98 void ItemTree::GetAllItemsLocked(std::vector<const Item*>* dest) const { | |
99 lock_.AssertAcquired(); | |
100 dest->reserve(items_.size()); | |
101 for (StringToNodeHash::const_iterator i = items_.begin(); | |
102 i != items_.end(); ++i) { | |
103 dest->push_back(i->second->item()); | |
104 } | |
105 } | |
106 | |
107 Err ItemTree::CheckForBadItems() const { | |
108 base::AutoLock lock(lock_); | |
109 | |
110 // Look for errors where we find a GENERATED node that refers to a REFERENCED | |
111 // one. There may be other nodes depending on the GENERATED one, but listing | |
112 // all of those isn't helpful, we want to find the broken link. | |
113 // | |
114 // This finds normal "missing dependency" errors but does not find circular | |
115 // dependencies because in this case all items in the cycle will be GENERATED | |
116 // but none will be resolved. If this happens, we'll check explicitly for | |
117 // that below. | |
118 std::vector<const ItemNode*> bad_nodes; | |
119 std::string depstring; | |
120 for (StringToNodeHash::const_iterator i = items_.begin(); | |
121 i != items_.end(); ++i) { | |
122 const ItemNode* src = i->second; | |
123 if (!src->should_generate()) | |
124 continue; // Skip ungenerated nodes. | |
125 | |
126 if (src->state() == ItemNode::DEFINED || | |
127 src->state() == ItemNode::PENDING_DEPS) { | |
128 bad_nodes.push_back(src); | |
129 | |
130 // Check dependencies. | |
131 for (ItemNode::ItemNodeMap::const_iterator dest = | |
132 src->unresolved_dependencies().begin(); | |
133 dest != src->unresolved_dependencies().end(); | |
134 ++dest) { | |
135 const ItemNode* dest_node = dest->first; | |
136 if (dest_node->state() == ItemNode::REFERENCED) { | |
137 depstring += "\"" + src->item()->label().GetUserVisibleName(false) + | |
138 "\" needs " + dest_node->item()->GetItemTypeName() + | |
139 " \"" + dest_node->item()->label().GetUserVisibleName(false) + | |
140 "\"\n"; | |
141 } | |
142 } | |
143 } | |
144 } | |
145 | |
146 if (!bad_nodes.empty() && depstring.empty()) { | |
147 // Our logic above found a bad node but didn't identify the problem. This | |
148 // normally means a circular dependency. | |
149 depstring = CheckForCircularDependenciesLocked(bad_nodes); | |
150 if (depstring.empty()) { | |
151 // Something's very wrong, just dump out the bad nodes. | |
152 depstring = "I have no idea what went wrong, but these are unresolved, " | |
153 "possible due to an\ninternal error:"; | |
154 for (size_t i = 0; i < bad_nodes.size(); i++) { | |
155 depstring += "\n\"" + | |
156 bad_nodes[i]->item()->label().GetUserVisibleName(false) + "\""; | |
157 } | |
158 } | |
159 } | |
160 | |
161 if (depstring.empty()) | |
162 return Err(); | |
163 return Err(Location(), "Unresolved dependencies.", depstring); | |
164 } | |
165 | |
166 void ItemTree::MarkItemResolvedLocked(ItemNode* node) { | |
167 node->SetResolved(); | |
168 node->item()->OnResolved(); | |
169 | |
170 // Now update our waiters, pushing the "resolved" bit. | |
171 ItemNode::ItemNodeMap waiting; | |
172 node->SwapOutWaitingDependencySet(&waiting); | |
173 for (ItemNode::ItemNodeMap::iterator i = waiting.begin(); | |
174 i != waiting.end(); ++i) { | |
175 ItemNode* waiter = i->first; | |
176 | |
177 // Our node should be unresolved in the waiter. | |
178 DCHECK(waiter->unresolved_dependencies().find(node) != | |
179 waiter->unresolved_dependencies().end()); | |
180 waiter->MarkDirectDependencyResolved(node); | |
181 | |
182 // Recursively mark nodes as resolved. | |
183 if ((waiter->state() == ItemNode::DEFINED || | |
184 waiter->state() == ItemNode::PENDING_DEPS) && | |
185 waiter->unresolved_dependencies().empty()) | |
186 MarkItemResolvedLocked(waiter); | |
187 } | |
188 } | |
189 | |
190 std::string ItemTree::CheckForCircularDependenciesLocked( | |
191 const std::vector<const ItemNode*>& bad_nodes) const { | |
192 std::vector<const ItemNode*> cycle; | |
193 if (!RecursiveFindCycle(bad_nodes[0], bad_nodes[0], &cycle)) | |
194 return std::string(); // Didn't find a cycle, something else is wrong. | |
195 | |
196 cycle.push_back(bad_nodes[0]); | |
197 std::string ret = "There is a dependency cycle:"; | |
198 | |
199 // Walk backwards since the dependency arrows point in the reverse direction. | |
200 for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) { | |
201 ret += "\n \"" + cycle[i]->item()->label().GetUserVisibleName(false) + | |
202 "\""; | |
203 if (i != 0) | |
204 ret += " ->"; | |
205 } | |
206 | |
207 return ret; | |
208 } | |
OLD | NEW |