OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2016 The Chromium Authors. All rights reserved. | |
brettw
2016/08/22 21:08:26
No (c)
| |
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/graph.h" | |
6 | |
7 #include <algorithm> | |
8 #include <iterator> | |
9 #include <set> | |
10 #include <vector> | |
11 | |
12 #include "base/json/json_reader.h" | |
13 #include "base/json/json_writer.h" | |
14 #include "base/memory/ptr_util.h" | |
15 #include "base/strings/string_util.h" | |
16 #include "base/strings/string_util.h" | |
17 #include "base/values.h" | |
18 #include "tools/gn/deps_iterator.h" | |
19 #include "tools/gn/err.h" | |
20 #include "tools/gn/location.h" | |
21 #include "tools/gn/source_file.h" | |
22 #include "tools/gn/target.h" | |
23 | |
24 Graph::Graph(const TargetVector& all_targets, const Label& default_toolchain) | |
25 : all_targets_(all_targets), default_toolchain_(default_toolchain) { | |
26 for (auto* target : all_targets_) { | |
27 labels_to_targets_[target->label()] = target; | |
28 for (const auto& dep_pair : target->GetDeps(Target::DEPS_ALL)) | |
29 dep_map_.insert(std::make_pair(dep_pair.ptr, target)); | |
30 } | |
31 for (const auto& target : all_targets_) { | |
32 if (dep_map_.find(target) == dep_map_.end()) | |
33 roots_.insert(target); | |
34 } | |
35 } | |
36 | |
37 Graph::~Graph() {} | |
38 | |
39 TargetSet Graph::Prune(const TargetSet& targets) { | |
40 TargetSet seen; | |
41 TargetSet pruned; | |
42 for (const auto& target : targets) | |
43 PruneTarget(target, seen, pruned); | |
44 return pruned; | |
45 } | |
46 | |
47 TargetSet Graph::AllAffectedTargets(const SourceFileSet& source_files) { | |
48 TargetSet direct_matches; | |
49 for (const auto& source_file : source_files) | |
50 AddTargetsDirectlyReferringToFileTo(source_file, &direct_matches); | |
51 TargetSet all_matches; | |
52 for (const auto& match : direct_matches) | |
53 AddAllRefsTo(match, &all_matches); | |
54 return all_matches; | |
55 } | |
56 | |
57 LabelSet Graph::InvalidLabels(const LabelSet& labels) { | |
58 LabelSet invalid_labels; | |
59 for (const auto& label : labels) { | |
60 if (labels_to_targets_.find(*label) == labels_to_targets_.end()) | |
61 invalid_labels.insert(label); | |
62 } | |
63 return invalid_labels; | |
64 } | |
65 | |
66 TargetSet Graph::TargetsFor(const LabelSet& labels) { | |
67 TargetSet targets; | |
68 for (const auto& label : labels) { | |
69 auto it = labels_to_targets_.find(*label); | |
70 if (it != labels_to_targets_.end()) | |
71 targets.insert(it->second); | |
72 } | |
73 return targets; | |
74 } | |
75 | |
76 void Graph::PruneTarget(const Target* target, | |
77 TargetSet& seen, | |
78 TargetSet& pruned) { | |
79 if (seen.find(target) == seen.end()) { | |
80 seen.insert(target); | |
81 if (target->output_type() != Target::GROUP) { | |
82 pruned.insert(target); | |
83 } else { | |
84 for (const auto& pair : target->GetDeps(Target::DEPS_ALL)) | |
85 PruneTarget(pair.ptr, seen, pruned); | |
86 } | |
87 } | |
88 } | |
89 | |
90 bool Graph::TargetRefersToFile(const Target* target, const SourceFile* file) { | |
91 for (const auto& cur_file : target->sources()) { | |
92 if (cur_file == *file) | |
93 return true; | |
94 } | |
95 for (const auto& cur_file : target->public_headers()) { | |
96 if (cur_file == *file) | |
97 return true; | |
98 } | |
99 for (const auto& cur_file : target->inputs()) { | |
100 if (cur_file == *file) | |
101 return true; | |
102 } | |
103 for (const auto& cur_file : target->data()) { | |
104 if (cur_file == file->value()) | |
105 return true; | |
106 if (cur_file.back() == '/' && | |
107 base::StartsWith(file->value(), cur_file, base::CompareCase::SENSITIVE)) | |
108 return true; | |
109 } | |
110 | |
111 if (target->action_values().script().value() == file->value()) | |
112 return true; | |
113 | |
114 std::vector<SourceFile> outputs; | |
115 target->action_values().GetOutputsAsSourceFiles(target, &outputs); | |
116 for (const auto& cur_file : outputs) { | |
117 if (cur_file == *file) | |
118 return true; | |
119 } | |
120 return false; | |
121 } | |
122 | |
123 void Graph::AddTargetsDirectlyReferringToFileTo(const SourceFile* file, | |
124 TargetSet* matches) { | |
125 for (const auto& target : all_targets_) { | |
126 // Only handles targets in the default toolchain. | |
127 if ((target->label().GetToolchainLabel() == default_toolchain_) && | |
128 TargetRefersToFile(target, file)) | |
129 matches->insert(target); | |
130 } | |
131 } | |
132 | |
133 void Graph::AddAllRefsTo(const Target* target, TargetSet* results) { | |
134 if (results->find(target) != results->end()) | |
135 return; // Already found this target. | |
136 results->insert(target); | |
137 | |
138 DepMap::const_iterator dep_begin = dep_map_.lower_bound(target); | |
139 DepMap::const_iterator dep_end = dep_map_.upper_bound(target); | |
140 for (DepMap::const_iterator cur_dep = dep_begin; cur_dep != dep_end; | |
141 cur_dep++) | |
142 AddAllRefsTo(cur_dep->second, results); | |
143 } | |
144 | |
145 namespace { | |
146 | |
147 using Inputs = struct Inputs { | |
148 std::vector<SourceFile> source_vec; | |
149 std::vector<Label> compile_vec; | |
150 std::vector<Label> test_vec; | |
151 bool compile_included_all; | |
152 SourceFileSet source_files; | |
153 LabelSet compile_labels; | |
154 LabelSet test_labels; | |
155 }; | |
156 | |
157 using Outputs = struct Outputs { | |
158 std::string status; | |
159 std::string error; | |
160 LabelSet compile_labels; | |
161 LabelSet test_labels; | |
162 LabelSet invalid_labels; | |
163 }; | |
164 | |
165 LabelSet InvalidLabels(Graph& graph, const Inputs& inputs) { | |
166 LabelSet invalid_labels; | |
167 for (const auto& label : graph.InvalidLabels(inputs.compile_labels)) | |
168 invalid_labels.insert(label); | |
169 for (const auto& label : graph.InvalidLabels(inputs.test_labels)) | |
170 invalid_labels.insert(label); | |
171 return invalid_labels; | |
172 } | |
173 | |
174 LabelSet LabelsFor(const TargetSet& targets) { | |
175 LabelSet labels; | |
176 for (const auto& target : targets) | |
177 labels.insert(&target->label()); | |
178 return labels; | |
179 } | |
180 | |
181 bool AnyBuildFilesWereModified(const SourceFileSet& source_files) { | |
182 for (const auto& file : source_files) { | |
183 if (base::EndsWith(file->value(), ".gn", base::CompareCase::SENSITIVE) || | |
184 base::EndsWith(file->value(), ".gni", base::CompareCase::SENSITIVE)) | |
185 return true; | |
186 } | |
187 return false; | |
188 } | |
189 | |
190 TargetSet Intersect(const TargetSet& l, const TargetSet& r) { | |
191 TargetSet result; | |
192 std::set_intersection(l.begin(), l.end(), r.begin(), r.end(), | |
193 std::inserter(result, result.begin())); | |
194 return result; | |
195 } | |
196 | |
197 Err GetStringVector(const base::DictionaryValue& dict, | |
198 const std::string& key, | |
199 std::vector<std::string>* strings) { | |
200 const base::ListValue* lst; | |
201 bool ret = dict.GetList(key, &lst); | |
202 if (!ret) | |
203 return Err(Location(), "Input does not have a key named \"" + key + | |
204 "\" with a list value."); | |
205 | |
206 strings->clear(); | |
207 for (size_t i = 0; i < lst->GetSize(); i++) { | |
208 std::string s; | |
209 ret = lst->GetString(i, &s); | |
210 if (!ret) | |
211 return Err(Location(), "Item " + std::to_string(i) + " of \"" + key + | |
212 "\" is not a string."); | |
213 strings->push_back(s); | |
214 } | |
215 return Err(); | |
216 } | |
217 | |
218 void WriteString(base::DictionaryValue& dict, | |
219 const std::string& key, | |
220 const std::string& value) { | |
221 dict.SetString(key, value); | |
222 }; | |
223 | |
224 void WriteLabels(const Label& default_toolchain, | |
225 base::DictionaryValue& dict, | |
226 const std::string& key, | |
227 const LabelSet& labels) { | |
228 std::vector<std::string> strings; | |
229 auto value = base::WrapUnique(new base::ListValue()); | |
230 for (const auto& l : labels) | |
231 strings.push_back(l->GetUserVisibleName(default_toolchain)); | |
232 std::sort(strings.begin(), strings.end()); | |
233 value->AppendStrings(strings); | |
234 dict.Set(key, std::move(value)); | |
235 } | |
236 | |
237 Label StringToLabel(const Label& default_toolchain, const std::string path) { | |
238 SourceDir source_root("//"); | |
239 Err err; | |
240 Value v(nullptr, Value::STRING); | |
241 v.string_value() = path; | |
242 return Label::Resolve(source_root, default_toolchain, v, &err); | |
243 } | |
244 | |
245 Err JSONToInputs(const Label& default_toolchain, | |
246 const std::string input, | |
247 Inputs* inputs) { | |
248 int error_code_out; | |
249 std::string error_msg_out; | |
250 int error_line_out; | |
251 int error_column_out; | |
252 std::unique_ptr<base::Value> value = base::JSONReader().ReadAndReturnError( | |
253 input, base::JSONParserOptions::JSON_PARSE_RFC, &error_code_out, | |
254 &error_msg_out, &error_line_out, &error_column_out); | |
255 if (value == nullptr) | |
256 return Err(Location(), "Input is not valid JSON:" + error_msg_out); | |
257 | |
258 const base::DictionaryValue* dict; | |
259 if (!value->GetAsDictionary(&dict)) | |
260 return Err(Location(), "Input is not a dictionary."); | |
261 | |
262 std::vector<std::string> strings; | |
263 Err err = GetStringVector(*dict, "files", &strings); | |
264 if (err.has_error()) | |
265 return err; | |
266 for (auto s : strings) | |
267 inputs->source_vec.push_back(SourceFile(s)); | |
268 | |
269 err = GetStringVector(*dict, "compile_targets", &strings); | |
270 if (err.has_error()) | |
271 return err; | |
272 | |
273 inputs->compile_included_all = false; | |
274 for (auto& s : strings) { | |
275 if (s == "all") | |
276 inputs->compile_included_all = true; | |
277 else { | |
278 inputs->compile_vec.push_back(StringToLabel(default_toolchain, s)); | |
279 } | |
280 } | |
281 | |
282 err = GetStringVector(*dict, "test_targets", &strings); | |
283 if (err.has_error()) | |
284 return err; | |
285 for (auto& s : strings) | |
286 inputs->test_vec.push_back(StringToLabel(default_toolchain, s)); | |
287 | |
288 for (auto& s : inputs->source_vec) | |
289 inputs->source_files.insert(&s); | |
290 for (auto& l : inputs->compile_vec) | |
291 inputs->compile_labels.insert(&l); | |
292 for (auto& l : inputs->test_vec) | |
293 inputs->test_labels.insert(&l); | |
294 return Err(); | |
295 } | |
296 | |
297 void OutputsToJSON(const Label& default_toolchain, | |
298 const Outputs& outputs, | |
299 std::string* output) { | |
300 auto value = base::MakeUnique<base::DictionaryValue>(); | |
301 | |
302 if (outputs.error.size()) { | |
303 WriteString(*value, "error", outputs.error); | |
304 WriteLabels(default_toolchain, *value, "invalid_targets", | |
305 outputs.invalid_labels); | |
306 } else { | |
307 WriteString(*value, "status", outputs.status); | |
308 WriteLabels(default_toolchain, *value, "compile_targets", | |
309 outputs.compile_labels); | |
310 WriteLabels(default_toolchain, *value, "test_targets", outputs.test_labels); | |
311 } | |
312 | |
313 base::JSONWriter::WriteWithOptions( | |
314 *value.get(), base::JSONWriter::OPTIONS_PRETTY_PRINT, output); | |
315 } | |
316 | |
317 } // namespace | |
318 | |
319 Err Analyze(Graph& graph, const std::string& input, std::string* output) { | |
320 Inputs inputs; | |
321 Outputs outputs; | |
322 const Label default_toolchain = graph.default_toolchain(); | |
323 | |
324 Err err = JSONToInputs(default_toolchain, input, &inputs); | |
325 if (err.has_error()) | |
326 return err; | |
327 | |
328 LabelSet invalid_labels = InvalidLabels(graph, inputs); | |
329 if (!invalid_labels.empty()) { | |
330 outputs.error = "Invalid targets"; | |
331 outputs.invalid_labels = invalid_labels; | |
332 OutputsToJSON(default_toolchain, outputs, output); | |
333 return Err(); | |
334 } | |
335 | |
336 TargetSet affected_targets = graph.AllAffectedTargets(inputs.source_files); | |
337 if (affected_targets.empty()) { | |
338 outputs.status = "No dependency"; | |
339 OutputsToJSON(default_toolchain, outputs, output); | |
340 return Err(); | |
341 } | |
342 | |
343 // TODO: We can do smarter things when we detect changes to build files. | |
344 // For example, if all of the ninja files are unchanged, we know that we | |
345 // can ignore changes to these files. Also, for most .gn files, we can | |
346 // treat a change as simply affecting every target, config, or toolchain | |
347 // defined in that file. | |
348 if (AnyBuildFilesWereModified(inputs.source_files)) { | |
349 outputs.status = "Found dependency (all)"; | |
350 outputs.compile_labels = inputs.compile_labels; | |
351 outputs.test_labels = inputs.test_labels; | |
352 OutputsToJSON(default_toolchain, outputs, output); | |
353 return Err(); | |
354 } | |
355 | |
356 TargetSet compile_targets = graph.TargetsFor(inputs.compile_labels); | |
357 if (inputs.compile_included_all) { | |
358 for (auto& root : graph.roots()) { | |
359 compile_targets.insert(root); | |
360 } | |
361 } | |
362 TargetSet pruned_targets = graph.Prune(compile_targets); | |
363 outputs.compile_labels = | |
364 LabelsFor(Intersect(pruned_targets, affected_targets)); | |
365 | |
366 TargetSet test_targets = graph.TargetsFor(inputs.test_labels); | |
367 outputs.test_labels = LabelsFor(Intersect(test_targets, affected_targets)); | |
368 | |
369 if (outputs.compile_labels.empty() && outputs.test_labels.empty()) | |
370 outputs.status = "No dependency"; | |
371 else | |
372 outputs.status = "Found dependency"; | |
373 OutputsToJSON(default_toolchain, outputs, output); | |
374 return Err(); | |
375 } | |
OLD | NEW |