1 // Copyright 2015 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 <stddef.h>
6
7 #include <algorithm>
8
9 #include "base/command_line.h"
10 #include "base/strings/stringprintf.h"
11 #include "gn/commands.h"
12 #include "gn/setup.h"
13 #include "gn/standard_out.h"
14
15 namespace commands {
16
17 namespace {
18
19 enum class DepType { NONE, PUBLIC, PRIVATE, DATA };
20
21 // The dependency paths are stored in a vector. Assuming the chain:
22 // A --[public]--> B --[private]--> C
23 // The stack will look like:
24 // [0] = A, NONE (this has no dep type since nobody depends on it)
25 // [1] = B, PUBLIC
26 // [2] = C, PRIVATE
27 using TargetDep = std::pair<const Target*, DepType>;
28 using PathVector = std::vector<TargetDep>;
29
30 // How to search.
31 enum class PrivateDeps { INCLUDE, EXCLUDE };
32 enum class DataDeps { INCLUDE, EXCLUDE };
33 enum class PrintWhat { ONE, ALL };
34
35 struct Options {
Optionscommands::__anon4847b7c30111::Options36 Options()
37 : print_what(PrintWhat::ONE), public_only(false), with_data(false) {}
38
39 PrintWhat print_what;
40 bool public_only;
41 bool with_data;
42 };
43
44 using WorkQueue = std::list<PathVector>;
45
46 struct Stats {
Statscommands::__anon4847b7c30111::Stats47 Stats() : public_paths(0), other_paths(0) {}
48
total_pathscommands::__anon4847b7c30111::Stats49 int total_paths() const { return public_paths + other_paths; }
50
51 int public_paths;
52 int other_paths;
53
54 // Stores targets that have a path to the destination, and whether that
55 // path is public, private, or data.
56 std::map<const Target*, DepType> found_paths;
57 };
58
59 // If the implicit_last_dep is not "none", this type indicates the
60 // classification of the elided last part of path.
ClassifyPath(const PathVector & path,DepType implicit_last_dep)61 DepType ClassifyPath(const PathVector& path, DepType implicit_last_dep) {
62 DepType result;
63 if (implicit_last_dep != DepType::NONE)
64 result = implicit_last_dep;
65 else
66 result = DepType::PUBLIC;
67
68 // Skip the 0th one since that is always NONE.
69 for (size_t i = 1; i < path.size(); i++) {
70 // PRIVATE overrides PUBLIC, and DATA overrides everything (the idea is
71 // to find the worst link in the path).
72 if (path[i].second == DepType::PRIVATE) {
73 if (result == DepType::PUBLIC)
74 result = DepType::PRIVATE;
75 } else if (path[i].second == DepType::DATA) {
76 result = DepType::DATA;
77 }
78 }
79 return result;
80 }
81
StringForDepType(DepType type)82 const char* StringForDepType(DepType type) {
83 switch (type) {
84 case DepType::PUBLIC:
85 return "public";
86 case DepType::PRIVATE:
87 return "private";
88 case DepType::DATA:
89 return "data";
90 break;
91 case DepType::NONE:
92 default:
93 return "";
94 }
95 }
96
97 // Prints the given path. If the implicit_last_dep is not "none", the last
98 // dependency will show an elided dependency with the given annotation.
PrintPath(const PathVector & path,DepType implicit_last_dep)99 void PrintPath(const PathVector& path, DepType implicit_last_dep) {
100 if (path.empty())
101 return;
102
103 // Don't print toolchains unless they differ from the first target.
104 const Label& default_toolchain = path[0].first->label().GetToolchainLabel();
105
106 for (size_t i = 0; i < path.size(); i++) {
107 OutputString(path[i].first->label().GetUserVisibleName(default_toolchain));
108
109 // Output dependency type.
110 if (i == path.size() - 1) {
111 // Last one either gets the implicit last dep type or nothing.
112 if (implicit_last_dep != DepType::NONE) {
113 OutputString(std::string(" --> see ") +
114 StringForDepType(implicit_last_dep) +
115 " chain printed above...",
116 DECORATION_DIM);
117 }
118 } else {
119 // Take type from the next entry.
120 OutputString(
121 std::string(" --[") + StringForDepType(path[i + 1].second) + "]-->",
122 DECORATION_DIM);
123 }
124 OutputString("\n");
125 }
126
127 OutputString("\n");
128 }
129
InsertTargetsIntoFoundPaths(const PathVector & path,DepType implicit_last_dep,Stats * stats)130 void InsertTargetsIntoFoundPaths(const PathVector& path,
131 DepType implicit_last_dep,
132 Stats* stats) {
133 DepType type = ClassifyPath(path, implicit_last_dep);
134
135 bool inserted = false;
136
137 // Don't try to insert the 0th item in the list which is the "from" target.
138 // The search will be run more than once (for the different path types) and
139 // if the "from" target was in the list, subsequent passes could never run
140 // the starting point is alredy in the list of targets considered).
141 //
142 // One might imagine an alternate implementation where all items are counted
143 // here but the "from" item is erased at the beginning of each search, but
144 // that will mess up the metrics (the private search pass will find the
145 // same public paths as the previous public pass, "inserted" will be true
146 // here since the item wasn't found, and the public path will be
147 // double-counted in the stats.
148 for (size_t i = 1; i < path.size(); i++) {
149 const auto& pair = path[i];
150
151 // Don't overwrite an existing one. The algorithm works by first doing
152 // public, then private, then data, so anything already there is guaranteed
153 // at least as good as our addition.
154 if (stats->found_paths.find(pair.first) == stats->found_paths.end()) {
155 stats->found_paths.insert(std::make_pair(pair.first, type));
156 inserted = true;
157 }
158 }
159
160 if (inserted) {
161 // Only count this path in the stats if any part of it was actually new.
162 if (type == DepType::PUBLIC)
163 stats->public_paths++;
164 else
165 stats->other_paths++;
166 }
167 }
168
BreadthFirstSearch(const Target * from,const Target * to,PrivateDeps private_deps,DataDeps data_deps,PrintWhat print_what,Stats * stats)169 void BreadthFirstSearch(const Target* from,
170 const Target* to,
171 PrivateDeps private_deps,
172 DataDeps data_deps,
173 PrintWhat print_what,
174 Stats* stats) {
175 // Seed the initial stack with just the "from" target.
176 PathVector initial_stack;
177 initial_stack.emplace_back(from, DepType::NONE);
178 WorkQueue work_queue;
179 work_queue.push_back(initial_stack);
180
181 // Track checked targets to avoid checking the same once more than once.
182 std::set<const Target*> visited;
183
184 while (!work_queue.empty()) {
185 PathVector current_path = work_queue.front();
186 work_queue.pop_front();
187
188 const Target* current_target = current_path.back().first;
189
190 if (current_target == to) {
191 // Found a new path.
192 if (stats->total_paths() == 0 || print_what == PrintWhat::ALL)
193 PrintPath(current_path, DepType::NONE);
194
195 // Insert all nodes on the path into the found paths list. Since we're
196 // doing search breadth first, we know that the current path is the best
197 // path for all nodes on it.
198 InsertTargetsIntoFoundPaths(current_path, DepType::NONE, stats);
199 } else {
200 // Check for a path that connects to an already known-good one. Printing
201 // this here will mean the results aren't strictly in depth-first order
202 // since there could be many items on the found path this connects to.
203 // Doing this here will mean that the output is sorted by length of items
204 // printed (with the redundant parts of the path omitted) rather than
205 // complete path length.
206 const auto& found_current_target =
207 stats->found_paths.find(current_target);
208 if (found_current_target != stats->found_paths.end()) {
209 if (stats->total_paths() == 0 || print_what == PrintWhat::ALL)
210 PrintPath(current_path, found_current_target->second);
211
212 // Insert all nodes on the path into the found paths list since we know
213 // everything along this path also leads to the destination.
214 InsertTargetsIntoFoundPaths(current_path, found_current_target->second,
215 stats);
216 continue;
217 }
218 }
219
220 // If we've already checked this one, stop. This should be after the above
221 // check for a known-good check, because known-good ones will always have
222 // been previously visited.
223 if (visited.find(current_target) == visited.end())
224 visited.insert(current_target);
225 else
226 continue;
227
228 // Add public deps for this target to the queue.
229 for (const auto& pair : current_target->public_deps()) {
230 work_queue.push_back(current_path);
231 work_queue.back().push_back(TargetDep(pair.ptr, DepType::PUBLIC));
232 }
233
234 if (private_deps == PrivateDeps::INCLUDE) {
235 // Add private deps.
236 for (const auto& pair : current_target->private_deps()) {
237 work_queue.push_back(current_path);
238 work_queue.back().push_back(TargetDep(pair.ptr, DepType::PRIVATE));
239 }
240 }
241
242 if (data_deps == DataDeps::INCLUDE) {
243 // Add data deps.
244 for (const auto& pair : current_target->data_deps()) {
245 work_queue.push_back(current_path);
246 work_queue.back().push_back(TargetDep(pair.ptr, DepType::DATA));
247 }
248 }
249 }
250 }
251
DoSearch(const Target * from,const Target * to,const Options & options,Stats * stats)252 void DoSearch(const Target* from,
253 const Target* to,
254 const Options& options,
255 Stats* stats) {
256 BreadthFirstSearch(from, to, PrivateDeps::EXCLUDE, DataDeps::EXCLUDE,
257 options.print_what, stats);
258 if (!options.public_only) {
259 // Check private deps.
260 BreadthFirstSearch(from, to, PrivateDeps::INCLUDE, DataDeps::EXCLUDE,
261 options.print_what, stats);
262 if (options.with_data) {
263 // Check data deps.
264 BreadthFirstSearch(from, to, PrivateDeps::INCLUDE, DataDeps::INCLUDE,
265 options.print_what, stats);
266 }
267 }
268 }
269
270 } // namespace
271
272 const char kPath[] = "path";
273 const char kPath_HelpShort[] = "path: Find paths between two targets.";
274 const char kPath_Help[] =
275 R"(gn path <out_dir> <target_one> <target_two>
276
277 Finds paths of dependencies between two targets. Each unique path will be
278 printed in one group, and groups will be separate by newlines. The two
279 targets can appear in either order (paths will be found going in either
280 direction).
281
282 By default, a single path will be printed. If there is a path with only
283 public dependencies, the shortest public path will be printed. Otherwise, the
284 shortest path using either public or private dependencies will be printed. If
285 --with-data is specified, data deps will also be considered. If there are
286 multiple shortest paths, an arbitrary one will be selected.
287
288 Interesting paths
289
290 In a large project, there can be 100's of millions of unique paths between a
291 very high level and a common low-level target. To make the output more useful
292 (and terminate in a reasonable time), GN will not revisit sub-paths
293 previously known to lead to the target.
294
295 Options
296
297 --all
298 Prints all "interesting" paths found rather than just the first one.
299 Public paths will be printed first in order of increasing length, followed
300 by non-public paths in order of increasing length.
301
302 --public
303 Considers only public paths. Can't be used with --with-data.
304
305 --with-data
306 Additionally follows data deps. Without this flag, only public and private
307 linked deps will be followed. Can't be used with --public.
308
309 Example
310
311 gn path out/Default //base //gn
312 )";
313
RunPath(const std::vector<std::string> & args)314 int RunPath(const std::vector<std::string>& args) {
315 if (args.size() != 3) {
316 Err(Location(), "You're holding it wrong.",
317 "Usage: \"gn path <out_dir> <target_one> <target_two>\"")
318 .PrintToStdout();
319 return 1;
320 }
321
322 // Deliberately leaked to avoid expensive process teardown.
323 Setup* setup = new Setup;
324 if (!setup->DoSetup(args[0], false))
325 return 1;
326 if (!setup->Run())
327 return 1;
328
329 const Target* target1 = ResolveTargetFromCommandLineString(setup, args[1]);
330 if (!target1)
331 return 1;
332 const Target* target2 = ResolveTargetFromCommandLineString(setup, args[2]);
333 if (!target2)
334 return 1;
335
336 Options options;
337 options.print_what = base::CommandLine::ForCurrentProcess()->HasSwitch("all")
338 ? PrintWhat::ALL
339 : PrintWhat::ONE;
340 options.public_only =
341 base::CommandLine::ForCurrentProcess()->HasSwitch("public");
342 options.with_data =
343 base::CommandLine::ForCurrentProcess()->HasSwitch("with-data");
344 if (options.public_only && options.with_data) {
345 Err(Location(), "Can't use --public with --with-data for 'gn path'.",
346 "Your zealous over-use of arguments has inevitably resulted in an "
347 "invalid\ncombination of flags.")
348 .PrintToStdout();
349 return 1;
350 }
351
352 Stats stats;
353 DoSearch(target1, target2, options, &stats);
354 if (stats.total_paths() == 0) {
355 // If we don't find a path going "forwards", try the reverse direction.
356 // Deps can only go in one direction without having a cycle, which will
357 // have caused a run failure above.
358 DoSearch(target2, target1, options, &stats);
359 }
360
361 // This string is inserted in the results to annotate whether the result
362 // is only public or includes data deps or not.
363 const char* path_annotation = "";
364 if (options.public_only)
365 path_annotation = "public ";
366 else if (!options.with_data)
367 path_annotation = "non-data ";
368
369 if (stats.total_paths() == 0) {
370 // No results.
371 OutputString(
372 base::StringPrintf("No %spaths found between these two targets.\n",
373 path_annotation),
374 DECORATION_YELLOW);
375 } else if (stats.total_paths() == 1) {
376 // Exactly one result.
377 OutputString(base::StringPrintf("1 %spath found.", path_annotation),
378 DECORATION_YELLOW);
379 if (!options.public_only) {
380 if (stats.public_paths)
381 OutputString(" It is public.");
382 else
383 OutputString(" It is not public.");
384 }
385 OutputString("\n");
386 } else {
387 if (options.print_what == PrintWhat::ALL) {
388 // Showing all paths when there are many.
389 OutputString(base::StringPrintf("%d \"interesting\" %spaths found.",
390 stats.total_paths(), path_annotation),
391 DECORATION_YELLOW);
392 if (!options.public_only) {
393 OutputString(
394 base::StringPrintf(" %d of them are public.", stats.public_paths));
395 }
396 OutputString("\n");
397 } else {
398 // Showing one path when there are many.
399 OutputString(
400 base::StringPrintf("Showing one of %d \"interesting\" %spaths.",
401 stats.total_paths(), path_annotation),
402 DECORATION_YELLOW);
403 if (!options.public_only) {
404 OutputString(
405 base::StringPrintf(" %d of them are public.", stats.public_paths));
406 }
407 OutputString("\nUse --all to print all paths.\n");
408 }
409 }
410 return 0;
411 }
412
413 } // namespace commands
414