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

Side by Side Diff: tools/gn/graph.cc

Issue 2265833002: Implement `gn analyze`. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 4 years, 3 months 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 unified diff | Download patch
« no previous file with comments | « tools/gn/graph.h ('k') | tools/gn/graph_unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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 }
OLDNEW
« no previous file with comments | « tools/gn/graph.h ('k') | tools/gn/graph_unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698