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 <map>
6#include <set>
7
8#include "base/command_line.h"
9#include "tools/gn/commands.h"
10#include "tools/gn/deps_iterator.h"
11#include "tools/gn/filesystem_utils.h"
12#include "tools/gn/input_file.h"
13#include "tools/gn/item.h"
14#include "tools/gn/setup.h"
15#include "tools/gn/standard_out.h"
16#include "tools/gn/target.h"
17
18namespace commands {
19
20namespace {
21
22typedef std::set<const Target*> TargetSet;
23typedef std::vector<const Target*> TargetVector;
24
25// Maps targets to the list of targets that depend on them.
26typedef std::multimap<const Target*, const Target*> DepMap;
27
28// Populates the reverse dependency map for the targets in the Setup.
29void FillDepMap(Setup* setup, DepMap* dep_map) {
30  std::vector<const Target*> targets =
31      setup->builder()->GetAllResolvedTargets();
32
33  for (size_t target_i = 0; target_i < targets.size(); target_i++) {
34    for (DepsIterator iter(targets[target_i]); !iter.done(); iter.Advance())
35      dep_map->insert(std::make_pair(iter.target(), targets[target_i]));
36  }
37}
38
39// Returns the file path generating this item.
40base::FilePath FilePathForItem(const Item* item) {
41  return item->defined_from()->GetRange().begin().file()->physical_name();
42}
43
44// Prints the targets which are the result of a query. This list is sorted
45// and, if as_files is set, the unique filenames matching those targets will
46// be used.
47void OutputResultSet(const TargetSet& results, bool as_files) {
48  if (results.empty())
49    return;
50
51  if (as_files) {
52    // Output the set of unique source files.
53    std::set<std::string> unique_files;
54    for (TargetSet::const_iterator iter = results.begin();
55         iter != results.end(); ++iter)
56      unique_files.insert(FilePathToUTF8(FilePathForItem(*iter)));
57
58    for (std::set<std::string>::const_iterator iter = unique_files.begin();
59         iter != unique_files.end(); ++iter) {
60      OutputString(*iter + "\n");
61    }
62  } else {
63    // Output sorted and uniquified list of labels. The set will sort the
64    // labels.
65    std::set<Label> unique_labels;
66    for (TargetSet::const_iterator iter = results.begin();
67         iter != results.end(); ++iter)
68      unique_labels.insert((*iter)->label());
69
70    // Grab the label of the default toolchain from a random target.
71    Label default_tc_label =
72        (*results.begin())->settings()->default_toolchain_label();
73
74    for (std::set<Label>::const_iterator iter = unique_labels.begin();
75         iter != unique_labels.end(); ++iter) {
76      // Print toolchain only for ones not in the default toolchain.
77      OutputString(iter->GetUserVisibleName(
78          iter->GetToolchainLabel() != default_tc_label));
79      OutputString("\n");
80    }
81  }
82}
83
84// Prints refs of the given target (not the target itself). If the set is
85// non-null, new targets encountered will be added to the set, and if a ref is
86// in the set already, it will not be recused into. When the set is null, all
87// refs will be printed.
88void RecursivePrintTree(const DepMap& dep_map,
89                        const Target* target,
90                        TargetSet* seen_targets,
91                        int indent_level) {
92  std::string indent(indent_level * 2, ' ');
93
94  DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
95  DepMap::const_iterator dep_end = dep_map.upper_bound(target);
96  for (DepMap::const_iterator cur_dep = dep_begin;
97       cur_dep != dep_end; cur_dep++) {
98    const Target* cur_target = cur_dep->second;
99
100    // Only print the toolchain for non-default-toolchain targets.
101    OutputString(indent + cur_target->label().GetUserVisibleName(
102        !cur_target->settings()->is_default()));
103
104    bool print_children = true;
105    if (seen_targets) {
106      if (seen_targets->find(cur_target) == seen_targets->end()) {
107        // New target, mark it visited.
108        seen_targets->insert(cur_target);
109      } else {
110        // Already seen.
111        print_children = false;
112        // Only print "..." if something is actually elided, which means that
113        // the current target has children.
114        if (dep_map.lower_bound(cur_target) != dep_map.upper_bound(cur_target))
115          OutputString("...");
116      }
117    }
118
119    OutputString("\n");
120    if (print_children)
121      RecursivePrintTree(dep_map, cur_target, seen_targets, indent_level + 1);
122  }
123}
124
125void RecursiveCollectChildRefs(const DepMap& dep_map,
126                               const Target* target,
127                               TargetSet* results);
128
129// Recursively finds all targets that reference the given one, and additionally
130// adds the current one to the list.
131void RecursiveCollectRefs(const DepMap& dep_map,
132                          const Target* target,
133                          TargetSet* results) {
134  if (results->find(target) != results->end())
135    return;  // Already found this target.
136  results->insert(target);
137  RecursiveCollectChildRefs(dep_map, target, results);
138}
139
140// Recursively finds all targets that reference the given one.
141void RecursiveCollectChildRefs(const DepMap& dep_map,
142                               const Target* target,
143                               TargetSet* results) {
144  DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
145  DepMap::const_iterator dep_end = dep_map.upper_bound(target);
146  for (DepMap::const_iterator cur_dep = dep_begin;
147       cur_dep != dep_end; cur_dep++)
148    RecursiveCollectRefs(dep_map, cur_dep->second, results);
149}
150
151}  // namespace
152
153const char kRefs[] = "refs";
154const char kRefs_HelpShort[] =
155    "refs: Find stuff referencing a target, directory, or config.";
156const char kRefs_Help[] =
157    "gn refs <build_dir> <label_pattern> [--files] [--tree] [--all]\n"
158    "        [--all-toolchains]\n"
159    "\n"
160    "  Finds which targets reference a given target or targets (reverse\n"
161    "  dependencies).\n"
162    "\n"
163    "  The <label_pattern> can take exact labels or patterns that match more\n"
164    "  than one (although not general regular expressions).\n"
165    "  See \"gn help label_pattern\" for details.\n"
166    "\n"
167    "  --all\n"
168    "      When used without --tree, will recurse and display all unique\n"
169    "      dependencies of the given targets. When used with --tree, turns\n"
170    "      off eliding to show a complete tree.\n"
171    "\n"
172    "  --all-toolchains\n"
173    "      Make the label pattern matche all toolchains. If the label pattern\n"
174    "      does not specify an explicit toolchain, labels from all toolchains\n"
175    "      will be matched (normally only the default toolchain is matched\n"
176    "      when no toolchain is specified).\n"
177    "\n"
178    "  --files\n"
179    "      Output unique filenames referencing a matched target or config.\n"
180    "      These will be relative to the source root directory such that they\n"
181    "      are suitable for piping to other commands.\n"
182    "\n"
183    "  --tree\n"
184    "      Outputs a reverse dependency tree from the given target. The label\n"
185    "      pattern must match one target exactly. Duplicates will be elided.\n"
186    "      Combine with --all to see a full dependency tree.\n"
187    "\n"
188    "Examples\n"
189    "\n"
190    "  gn refs out/Debug //tools/gn:gn\n"
191    "      Find all targets depending on the given exact target name.\n"
192    "\n"
193    "  gn refs out/Debug //base:i18n --files | xargs gvim\n"
194    "      Edit all files containing references to //base:i18n\n"
195    "\n"
196    "  gn refs out/Debug //base --all\n"
197    "      List all targets depending directly or indirectly on //base:base.\n"
198    "\n"
199    "  gn refs out/Debug \"//base/*\"\n"
200    "      List all targets depending directly on any target in //base or\n"
201    "      its subdirectories.\n"
202    "\n"
203    "  gn refs out/Debug \"//base:*\"\n"
204    "      List all targets depending directly on any target in\n"
205    "      //base/BUILD.gn.\n"
206    "\n"
207    "  gn refs out/Debug //base --tree\n"
208    "      Print a reverse dependency tree of //base:base\n";
209
210int RunRefs(const std::vector<std::string>& args) {
211  if (args.size() != 2) {
212    Err(Location(), "You're holding it wrong.",
213        "Usage: \"gn refs <build_dir> <label_pattern>\"").PrintToStdout();
214    return 1;
215  }
216
217  const CommandLine* cmdline = CommandLine::ForCurrentProcess();
218  bool tree = cmdline->HasSwitch("tree");
219  bool all = cmdline->HasSwitch("all");
220  bool all_toolchains = cmdline->HasSwitch("all-toolchains");
221  bool files = cmdline->HasSwitch("files");
222
223  Setup* setup = new Setup;
224  setup->set_check_for_bad_items(false);
225  if (!setup->DoSetup(args[0], false) || !setup->Run())
226    return 1;
227
228  // Figure out the target or targets that the user is querying.
229  std::vector<const Target*> query;
230  if (!ResolveTargetsFromCommandLinePattern(setup, args[1], all_toolchains,
231                                            &query))
232    return 1;
233  if (query.empty()) {
234    OutputString("\"" + args[1] + "\" matches no targets.\n");
235    return 0;
236  }
237
238  // Construct the reverse dependency tree.
239  DepMap dep_map;
240  FillDepMap(setup, &dep_map);
241
242  if (tree) {
243    // Output dependency tree.
244    if (files) {
245      Err(NULL, "--files option can't be used with --tree option.")
246          .PrintToStdout();
247      return 1;
248    }
249    if (query.size() != 1) {
250      Err(NULL, "Query matches more than one target.",
251          "--tree only supports a single target as input.").PrintToStdout();
252      return 1;
253    }
254    if (all) {
255      // Recursively print all targets.
256      RecursivePrintTree(dep_map, query[0], NULL, 0);
257    } else {
258      // Recursively print unique targets.
259      TargetSet seen_targets;
260      RecursivePrintTree(dep_map, query[0], &seen_targets, 0);
261    }
262  } else if (all) {
263    // Output recursive dependencies, uniquified and flattened.
264    TargetSet results;
265    for (size_t query_i = 0; query_i < query.size(); query_i++)
266      RecursiveCollectChildRefs(dep_map, query[query_i], &results);
267    OutputResultSet(results, files);
268  } else {
269    // Output direct references of everything in the query.
270    TargetSet results;
271    for (size_t query_i = 0; query_i < query.size(); query_i++) {
272      DepMap::const_iterator dep_begin = dep_map.lower_bound(query[query_i]);
273      DepMap::const_iterator dep_end = dep_map.upper_bound(query[query_i]);
274      for (DepMap::const_iterator cur_dep = dep_begin;
275           cur_dep != dep_end; cur_dep++)
276        results.insert(cur_dep->second);
277    }
278    OutputResultSet(results, files);
279  }
280
281  return 0;
282}
283
284}  // namespace commands
285