tools/gn/command_refs.cc

   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
  18 namespace commands {
  19
  20 namespace {
  21
  22 typedef std::set<const Target*> TargetSet;
  23 typedef std::vector<const Target*> TargetVector;
  24
  25 // Maps targets to the list of targets that depend on them.
  26 typedef std::multimap<const Target*, const Target*> DepMap;
  27
  28 // Populates the reverse dependency map for the targets in the Setup.
  29 void FillDepMap(Setup* setup, DepMap* dep_map) {
  30   for (const auto& target : setup->builder()->GetAllResolvedTargets()) {
  31     for (const auto& dep_pair : target->GetDeps(Target::DEPS_ALL))
  32       dep_map->insert(std::make_pair(dep_pair.ptr, target));
  33   }
  34 }
  35
  36 // Forward declaration for function below.
  37 void RecursivePrintTargetDeps(const DepMap& dep_map,
  38                               const Target* target,
  39                               TargetSet* seen_targets,
  40                               int indent_level);
  41
  42 // Prints the target and its dependencies in tree form. If the set is non-null,
  43 // new targets encountered will be added to the set, and if a ref is in the set
  44 // already, it will not be recused into. When the set is null, all refs will be
  45 // printed.
  46 void RecursivePrintTarget(const DepMap& dep_map,
  47                           const Target* target,
  48                           TargetSet* seen_targets,
  49                           int indent_level) {
  50   std::string indent(indent_level * 2, ' ');
  51
  52   // Only print the toolchain for non-default-toolchain targets.
  53   OutputString(indent + target->label().GetUserVisibleName(
  54       !target->settings()->is_default()));
  55
  56   bool print_children = true;
  57   if (seen_targets) {
  58     if (seen_targets->find(target) == seen_targets->end()) {
  59       // New target, mark it visited.
  60       seen_targets->insert(target);
  61     } else {
  62       // Already seen.
  63       print_children = false;
  64       // Only print "..." if something is actually elided, which means that
  65       // the current target has children.
  66       if (dep_map.lower_bound(target) != dep_map.upper_bound(target))
  67         OutputString("...");
  68     }
  69   }
  70
  71   OutputString("\n");
  72   if (print_children)
  73     RecursivePrintTargetDeps(dep_map, target, seen_targets, indent_level + 1);
  74 }
  75
  76 // Prints refs of the given target (not the target itself). See
  77 // RecursivePrintTarget.
  78 void RecursivePrintTargetDeps(const DepMap& dep_map,
  79                               const Target* target,
  80                               TargetSet* seen_targets,
  81                               int indent_level) {
  82   DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
  83   DepMap::const_iterator dep_end = dep_map.upper_bound(target);
  84   for (DepMap::const_iterator cur_dep = dep_begin;
  85        cur_dep != dep_end; cur_dep++) {
  86     RecursivePrintTarget(dep_map, cur_dep->second, seen_targets, indent_level);
  87   }
  88 }
  89
  90 void RecursiveCollectChildRefs(const DepMap& dep_map,
  91                                const Target* target,
  92                                TargetSet* results);
  93
  94 // Recursively finds all targets that reference the given one, and additionally
  95 // adds the current one to the list.
  96 void RecursiveCollectRefs(const DepMap& dep_map,
  97                           const Target* target,
  98                           TargetSet* results) {
  99   if (results->find(target) != results->end())
 100     return;  // Already found this target.
 101   results->insert(target);
 102   RecursiveCollectChildRefs(dep_map, target, results);
 103 }
 104
 105 // Recursively finds all targets that reference the given one.
 106 void RecursiveCollectChildRefs(const DepMap& dep_map,
 107                                const Target* target,
 108                                TargetSet* results) {
 109   DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
 110   DepMap::const_iterator dep_end = dep_map.upper_bound(target);
 111   for (DepMap::const_iterator cur_dep = dep_begin;
 112        cur_dep != dep_end; cur_dep++)
 113     RecursiveCollectRefs(dep_map, cur_dep->second, results);
 114 }
 115
 116 bool TargetContainsFile(const Target* target, const SourceFile& file) {
 117   for (const auto& cur_file : target->sources()) {
 118     if (cur_file == file)
 119       return true;
 120   }
 121   for (const auto& cur_file : target->public_headers()) {
 122     if (cur_file == file)
 123       return true;
 124   }
 125   for (const auto& cur_file : target->inputs()) {
 126     if (cur_file == file)
 127       return true;
 128   }
 129   for (const auto& cur_file : target->data()) {
 130     if (cur_file == file)
 131       return true;
 132   }
 133   return false;
 134 }
 135
 136 void GetTargetsContainingFile(Setup* setup,
 137                               const std::vector<const Target*>& all_targets,
 138                               const SourceFile& file,
 139                               bool all_toolchains,
 140                               UniqueVector<const Target*>* matches) {
 141   Label default_toolchain = setup->loader()->default_toolchain_label();
 142   for (const auto& target : all_targets) {
 143     if (!all_toolchains) {
 144       // Only check targets in the default toolchain.
 145       if (target->label().GetToolchainLabel() != default_toolchain)
 146         continue;
 147     }
 148     if (TargetContainsFile(target, file))
 149       matches->push_back(target);
 150   }
 151 }
 152
 153 bool TargetReferencesConfig(const Target* target, const Config* config) {
 154   for (const LabelConfigPair& cur : target->configs()) {
 155     if (cur.ptr == config)
 156       return true;
 157   }
 158   for (const LabelConfigPair& cur : target->public_configs()) {
 159     if (cur.ptr == config)
 160       return true;
 161   }
 162   return false;
 163 }
 164
 165 void GetTargetsReferencingConfig(Setup* setup,
 166                                  const std::vector<const Target*>& all_targets,
 167                                  const Config* config,
 168                                  bool all_toolchains,
 169                                  UniqueVector<const Target*>* matches) {
 170   Label default_toolchain = setup->loader()->default_toolchain_label();
 171   for (const auto& target : all_targets) {
 172     if (!all_toolchains) {
 173       // Only check targets in the default toolchain.
 174       if (target->label().GetToolchainLabel() != default_toolchain)
 175         continue;
 176     }
 177     if (TargetReferencesConfig(target, config))
 178       matches->push_back(target);
 179   }
 180 }
 181
 182 void DoTreeOutput(const DepMap& dep_map,
 183                   const UniqueVector<const Target*>& implicit_target_matches,
 184                   const UniqueVector<const Target*>& explicit_target_matches,
 185                   bool all) {
 186   TargetSet seen_targets;
 187
 188   // Implicit targets don't get printed themselves.
 189   for (const Target* target : implicit_target_matches) {
 190     if (all)
 191       RecursivePrintTargetDeps(dep_map, target, nullptr, 0);
 192     else
 193       RecursivePrintTargetDeps(dep_map, target, &seen_targets, 0);
 194   }
 195
 196   // Explicit targets appear in the output.
 197   for (const Target* target : implicit_target_matches) {
 198     if (all)
 199       RecursivePrintTarget(dep_map, target, nullptr, 0);
 200     else
 201       RecursivePrintTarget(dep_map, target, &seen_targets, 0);
 202   }
 203 }
 204
 205 void DoAllListOutput(
 206     const DepMap& dep_map,
 207     const UniqueVector<const Target*>& implicit_target_matches,
 208     const UniqueVector<const Target*>& explicit_target_matches) {
 209   // Output recursive dependencies, uniquified and flattened.
 210   TargetSet results;
 211
 212   for (const Target* target : implicit_target_matches)
 213     RecursiveCollectChildRefs(dep_map, target, &results);
 214   for (const Target* target : explicit_target_matches) {
 215     // Explicit targets also get added to the output themselves.
 216     results.insert(target);
 217     RecursiveCollectChildRefs(dep_map, target, &results);
 218   }
 219
 220   FilterAndPrintTargetSet(false, results);
 221 }
 222
 223 void DoDirectListOutput(
 224     const DepMap& dep_map,
 225     const UniqueVector<const Target*>& implicit_target_matches,
 226     const UniqueVector<const Target*>& explicit_target_matches) {
 227   TargetSet results;
 228
 229   // Output everything that refers to the implicit ones.
 230   for (const Target* target : implicit_target_matches) {
 231     DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
 232     DepMap::const_iterator dep_end = dep_map.upper_bound(target);
 233     for (DepMap::const_iterator cur_dep = dep_begin;
 234          cur_dep != dep_end; cur_dep++)
 235       results.insert(cur_dep->second);
 236   }
 237
 238   // And just output the explicit ones directly (these are the target matches
 239   // when referring to what references a file or config).
 240   for (const Target* target : explicit_target_matches)
 241     results.insert(target);
 242
 243   FilterAndPrintTargetSet(false, results);
 244 }
 245
 246 }  // namespace
 247
 248 const char kRefs[] = "refs";
 249 const char kRefs_HelpShort[] =
 250     "refs: Find stuff referencing a target or file.";
 251 const char kRefs_Help[] =
 252     "gn refs <out_dir> (<label_pattern>|<label>|<file>)* [--all]\n"
 253     "        [--all-toolchains] [--as=...] [--testonly=...] [--type=...]\n"
 254     "\n"
 255     "  Finds reverse dependencies (which targets reference something). The\n"
 256     "  input is a list containing:\n"
 257     "\n"
 258     "   - Target label: The result will be which targets depend on it.\n"
 259     "\n"
 260     "   - Config label: The result will be which targets list the given\n"
 261     "     config in its \"configs\" or \"public_configs\" list.\n"
 262     "\n"
 263     "   - Label pattern: The result will be which targets depend on any\n"
 264     "     target matching the given pattern. Patterns will not match\n"
 265     "     configs. These are not general regular expressions, see\n"
 266     "     \"gn help label_pattern\" for details.\n"
 267     "\n"
 268     "   - File name: The result will be which targets list the given file in\n"
 269     "     its \"inputs\", \"sources\", \"public\", or \"data\". Any input\n"
 270     "     that does not contain wildcards and does not match a target or a\n"
 271     "     config will be treated as a file.\n"
 272     "\n"
 273     "Options\n"
 274     "\n"
 275     "  --all\n"
 276     "      When used without --tree, will recurse and display all unique\n"
 277     "      dependencies of the given targets. For example, if the input is\n"
 278     "      a target, this will output all targets that depend directly or\n"
 279     "      indirectly on the input. If the input is a file, this will output\n"
 280     "      all targets that depend directly or indirectly on that file.\n"
 281     "\n"
 282     "      When used with --tree, turns off eliding to show a complete tree.\n"
 283     "\n"
 284     "  --all-toolchains\n"
 285     "      Normally only inputs in the default toolchain will be included.\n"
 286     "      This switch will turn on matching all toolchains.\n"
 287     "\n"
 288     "      For example, a file is in a target might be compiled twice:\n"
 289     "      once in the default toolchain and once in a secondary one. Without\n"
 290     "      this flag, only the default toolchain one will be matched and\n"
 291     "      printed (potentially with its recursive dependencies, depending on\n"
 292     "      the other options). With this flag, both will be printed\n"
 293     "      (potentially with both of their recursive dependencies).\n"
 294     "\n"
 295     TARGET_PRINTING_MODE_COMMAND_LINE_HELP
 296     "\n"
 297     TARGET_TESTONLY_FILTER_COMMAND_LINE_HELP
 298     "\n"
 299     "  --tree\n"
 300     "      Outputs a reverse dependency tree from the given target.\n"
 301     "      Duplicates will be elided. Combine with --all to see a full\n"
 302     "      dependency tree.\n"
 303     "\n"
 304     "      Tree output can not be used with the filtering or output flags:\n"
 305     "      --as, --type, --testonly.\n"
 306     "\n"
 307     TARGET_TYPE_FILTER_COMMAND_LINE_HELP
 308     "\n"
 309     "Examples (target input)\n"
 310     "\n"
 311     "  gn refs out/Debug //tools/gn:gn\n"
 312     "      Find all targets depending on the given exact target name.\n"
 313     "\n"
 314     "  gn refs out/Debug //base:i18n --as=buildfiles | xargs gvim\n"
 315     "      Edit all .gn files containing references to //base:i18n\n"
 316     "\n"
 317     "  gn refs out/Debug //base --all\n"
 318     "      List all targets depending directly or indirectly on //base:base.\n"
 319     "\n"
 320     "  gn refs out/Debug \"//base/*\"\n"
 321     "      List all targets depending directly on any target in //base or\n"
 322     "      its subdirectories.\n"
 323     "\n"
 324     "  gn refs out/Debug \"//base:*\"\n"
 325     "      List all targets depending directly on any target in\n"
 326     "      //base/BUILD.gn.\n"
 327     "\n"
 328     "  gn refs out/Debug //base --tree\n"
 329     "      Print a reverse dependency tree of //base:base\n"
 330     "\n"
 331     "Examples (file input)\n"
 332     "\n"
 333     "  gn refs out/Debug //base/macros.h\n"
 334     "      Print target(s) listing //base/macros.h as a source.\n"
 335     "\n"
 336     "  gn refs out/Debug //base/macros.h --tree\n"
 337     "      Display a reverse dependency tree to get to the given file. This\n"
 338     "      will show how dependencies will reference that file.\n"
 339     "\n"
 340     "  gn refs out/Debug //base/macros.h //base/basictypes.h --all\n"
 341     "      Display all unique targets with some dependency path to a target\n"
 342     "      containing either of the given files as a source.\n"
 343     "\n"
 344     "  gn refs out/Debug //base/macros.h --testonly=true --type=executable\n"
 345     "          --all --as=output\n"
 346     "      Display the executable file names of all test executables\n"
 347     "      potentially affected by a change to the given file.\n";
 348
 349 int RunRefs(const std::vector<std::string>& args) {
 350   if (args.size() != 2) {
 351     Err(Location(), "You're holding it wrong.",
 352         "Usage: \"gn refs <out_dir> (<label_pattern>|<file>)\"")
 353         .PrintToStdout();
 354     return 1;
 355   }
 356
 357   const base::CommandLine* cmdline = base::CommandLine::ForCurrentProcess();
 358   bool tree = cmdline->HasSwitch("tree");
 359   bool all = cmdline->HasSwitch("all");
 360   bool all_toolchains = cmdline->HasSwitch("all-toolchains");
 361
 362   Setup* setup = new Setup;
 363   setup->set_check_for_bad_items(false);
 364   if (!setup->DoSetup(args[0], false) || !setup->Run())
 365     return 1;
 366
 367   // The inputs are everything but the first arg (which is the build dir).
 368   std::vector<std::string> inputs(args.begin() + 1, args.end());
 369
 370   // Get the matches for the command-line input.
 371   UniqueVector<const Target*> target_matches;
 372   UniqueVector<const Config*> config_matches;
 373   UniqueVector<const Toolchain*> toolchain_matches;
 374   UniqueVector<SourceFile> file_matches;
 375   if (!ResolveFromCommandLineInput(setup, inputs, all_toolchains,
 376                                    &target_matches, &config_matches,
 377                                    &toolchain_matches, &file_matches))
 378     return 1;
 379
 380   // When you give a file or config as an input, you want the targets that are
 381   // associated with it. We don't want to just append this to the
 382   // target_matches, however, since these targets should actually be listed in
 383   // the output, while for normal targets you don't want to see the inputs,
 384   // only what refers to them.
 385   std::vector<const Target*> all_targets =
 386       setup->builder()->GetAllResolvedTargets();
 387   UniqueVector<const Target*> explicit_target_matches;
 388   for (const auto& file : file_matches) {
 389     GetTargetsContainingFile(setup, all_targets, file, all_toolchains,
 390                              &explicit_target_matches);
 391   }
 392   for (const auto& config : config_matches) {
 393     GetTargetsReferencingConfig(setup, all_targets, config, all_toolchains,
 394                                 &explicit_target_matches);
 395   }
 396
 397   // Construct the reverse dependency tree.
 398   DepMap dep_map;
 399   FillDepMap(setup, &dep_map);
 400
 401   if (tree)
 402     DoTreeOutput(dep_map, target_matches, explicit_target_matches, all);
 403   else if (all)
 404     DoAllListOutput(dep_map, target_matches, explicit_target_matches);
 405   else
 406     DoDirectListOutput(dep_map, target_matches, explicit_target_matches);
 407
 408   return 0;
 409 }
 410
 411 }  // namespace commands