Enhance GN diagnostic tools

tools/gn/command_refs.cc

Index: tools/gn/command_refs.cc
diff --git a/tools/gn/command_refs.cc b/tools/gn/command_refs.cc
index e54d1f393c9047424bb2ad658f7ad7b0114d1666..d00149f372add32a03c9a771fa78796aca362f25 100644
--- a/tools/gn/command_refs.cc
+++ b/tools/gn/command_refs.cc
@@ -2,6 +2,7 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <map>
 #include <set>
 
 #include "base/command_line.h"
@@ -9,7 +10,6 @@
 #include "tools/gn/filesystem_utils.h"
 #include "tools/gn/input_file.h"
 #include "tools/gn/item.h"
-#include "tools/gn/pattern.h"
 #include "tools/gn/setup.h"
 #include "tools/gn/standard_out.h"
 #include "tools/gn/target.h"
@@ -18,12 +18,142 @@ namespace commands {
 
 namespace {
 
-// Returns the file path generating this record.
-base::FilePath FilePathForRecord(const BuilderRecord* record) {
-  if (!record->item())
-    return base::FilePath(FILE_PATH_LITERAL("=UNRESOLVED DEPENDENCY="));
-  return record->item()->defined_from()->GetRange().begin().file()
-      ->physical_name();
+typedef std::set<const Target*> TargetSet;
+typedef std::vector<const Target*> TargetVector;
+
+// Maps targets to the list of targets that depend on them.
+typedef std::multimap<const Target*, const Target*> DepMap;
+
+// Populates the reverse dependency map for the targets in the Setup.
+void FillDepMap(Setup* setup, DepMap* dep_map) {
+  std::vector<const Target*> targets =
+      setup->builder()->GetAllResolvedTargets();
+
+  for (size_t target_i = 0; target_i < targets.size(); target_i++) {
+    const Target* target = targets[target_i];
+
+    // Add all deps to the map.
+    const LabelTargetVector& deps = target->deps();
+    for (size_t dep_i = 0; dep_i < deps.size(); dep_i++)
+      dep_map->insert(std::make_pair(deps[dep_i].ptr, target));
+
+    // Include data deps as well.
+    const LabelTargetVector& datadeps = target->datadeps();
+    for (size_t dep_i = 0; dep_i < datadeps.size(); dep_i++)
+      dep_map->insert(std::make_pair(datadeps[dep_i].ptr, target));
+  }
+}
+
+// Returns the file path generating this item.
+base::FilePath FilePathForItem(const Item* item) {
+  return item->defined_from()->GetRange().begin().file()->physical_name();
+}
+
+// Prints the targets which are the result of a query. This list is sorted
+// and, if as_files is set, the unique filenames matching those targets will
+// be used.
+void OutputResultSet(const TargetSet& results, bool as_files) {
+  if (results.empty())
+    return;
+
+  if (as_files) {
+    // Output the set of unique source files.
+    std::set<std::string> unique_files;
+    for (TargetSet::const_iterator iter = results.begin();
+         iter != results.end(); ++iter)
+      unique_files.insert(FilePathToUTF8(FilePathForItem(*iter)));
+
+    for (std::set<std::string>::const_iterator iter = unique_files.begin();
+         iter != unique_files.end(); ++iter) {
+      OutputString(*iter + "\n");
+    }
+  } else {
+    // Output sorted and uniquified list of labels. The set will sort the
+    // labels.
+    std::set<Label> unique_labels;
+    for (TargetSet::const_iterator iter = results.begin();
+         iter != results.end(); ++iter)
+      unique_labels.insert((*iter)->label());
+
+    // Grab the label of the default toolchain from a random target.
+    Label default_tc_label =
+        (*results.begin())->settings()->default_toolchain_label();
+
+    for (std::set<Label>::const_iterator iter = unique_labels.begin();
+         iter != unique_labels.end(); ++iter) {
+      // Print toolchain only for ones not in the default toolchain.
+      OutputString(iter->GetUserVisibleName(
+          iter->GetToolchainLabel() != default_tc_label));
+      OutputString("\n");
+    }
+  }
+}
+
+// Prints refs of the given target (not the target itself). If the set is
+// non-null, new targets encountered will be added to the set, and if a ref is
+// in the set already, it will not be recused into. When the set is null, all
+// refs will be printed.
+void RecursivePrintTree(const DepMap& dep_map,
+                        const Target* target,
+                        TargetSet* seen_targets,
+                        int indent_level) {
+  std::string indent(indent_level * 2, ' ');
+
+  DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
+  DepMap::const_iterator dep_end = dep_map.upper_bound(target);
+  for (DepMap::const_iterator cur_dep = dep_begin;
+       cur_dep != dep_end; cur_dep++) {
+    const Target* cur_target = cur_dep->second;
+
+    // Only print the toolchain for non-default-toolchain targets.
+    OutputString(indent + cur_target->label().GetUserVisibleName(
+        !cur_target->settings()->is_default()));
+
+    bool print_children = true;
+    if (seen_targets) {
+      if (seen_targets->find(cur_target) == seen_targets->end()) {
+        // New target, mark it visited.
+        seen_targets->insert(cur_target);
+      } else {
+        // Already seen.
+        print_children = false;
+        // Only print "..." if something is actually elided, which means that
+        // the current target has children.
+        if (dep_map.lower_bound(cur_target) != dep_map.upper_bound(cur_target))
+          OutputString("...");
+      }
+    }
+
+    OutputString("\n");
+    if (print_children)
+      RecursivePrintTree(dep_map, cur_target, seen_targets, indent_level + 1);
+  }
+}
+
+void RecursiveCollectChildRefs(const DepMap& dep_map,
+                               const Target* target,
+                               TargetSet* results);
+
+// Recursively finds all targets that reference the given one, and additionally
+// adds the current one to the list.
+void RecursiveCollectRefs(const DepMap& dep_map,
+                          const Target* target,
+                          TargetSet* results) {
+  if (results->find(target) != results->end())
+    return;  // Already found this target.
+  results->insert(target);
+  RecursiveCollectChildRefs(dep_map, target, results);
+}
+
+// Recursively finds all targets that reference the given one.
+void RecursiveCollectChildRefs(const DepMap& dep_map,
+                               const Target* target,
+                               TargetSet* results) {
+  DepMap::const_iterator dep_begin = dep_map.lower_bound(target);
+  DepMap::const_iterator dep_end = dep_map.upper_bound(target);
+  for (DepMap::const_iterator cur_dep = dep_begin;
+       cur_dep != dep_end; cur_dep++)
+    RecursiveCollectRefs(dep_map, cur_dep->second, results);
 }
 
 }  // namespace
@@ -32,95 +162,130 @@ const char kRefs[] = "refs";
 const char kRefs_HelpShort[] =
     "refs: Find stuff referencing a target, directory, or config.";
 const char kRefs_Help[] =
-    "gn refs <label_pattern> [--files]\n"
+    "gn refs <build_dir> <label_pattern> [--files] [--tree] [--all]\n"
+    "        [--all-toolchains]\n"
     "\n"
-    "  Finds code referencing a given label. The label can be a\n"
-    "  target or config name. Unlike most other commands, unresolved\n"
-    "  dependencies will be tolerated. This allows you to use this command\n"
-    "  to find references to targets you're in the process of moving.\n"
+    "  Finds which targets reference a given target or targets (reverse\n"
+    "  dependencies).\n"
     "\n"
-    "  By default, the mapping from source item to dest item (where the\n"
-    "  pattern matches the dest item). See \"gn help pattern\" for\n"
-    "  information on pattern-matching rules.\n"
+    "  The <label_pattern> can take exact labels or patterns that match more\n"
+    "  than one (although not general regular expressions).\n"
+    "  See \"gn help label_pattern\" for details.\n"
+    "\n"
+    "  --all\n"
+    "      When used without --tree, will recurse and display all unique\n"
+    "      dependencies of the given targets. When used with --tree, turns\n"
+    "      off eliding to show a complete tree.\n"
+    "\n"
+    "  --all-toolchains\n"
+    "      Make the label pattern matche all toolchains. If the label pattern\n"
+    "      does not specify an explicit toolchain, labels from all toolchains\n"
+    "      will be matched (normally only the default toolchain is matched\n"
+    "      when no toolchain is specified).\n"
     "\n"
-    "Option:\n"
     "  --files\n"
     "      Output unique filenames referencing a matched target or config.\n"
+    "      These will be relative to the source root directory such that they\n"
+    "      are suitable for piping to other commands.\n"
+    "\n"
+    "  --tree\n"
+    "      Outputs a reverse dependency tree from the given target. The label\n"
+    "      pattern must match one target exactly. Duplicates will be elided.\n"
+    "      Combine with --all to see a full dependency tree.\n"
     "\n"
-    "Examples:\n"
-    "  gn refs \"//tools/gn/*\"\n"
-    "      Find all targets depending on any target or config in the\n"
-    "      \"tools/gn\" directory.\n"
+    "Examples\n"
     "\n"
-    "  gn refs //tools/gn:gn\n"
+    "  gn refs out/Debug //tools/gn:gn\n"
     "      Find all targets depending on the given exact target name.\n"
     "\n"
-    "  gn refs \"*gtk*\" --files\n"
-    "      Find all unique buildfiles with a dependency on a target that has\n"
-    "      the substring \"gtk\" in the name.\n";
+    "  gn refs out/Debug //base:i18n --files | xargs gvim\n"
+    "      Edit all files containing references to //base:i18n\n"
+    "\n"
+    "  gn refs out/Debug //base --all\n"
+    "      List all targets depending directly or indirectly on //base:base.\n"
+    "\n"
+    "  gn refs out/Debug \"//base/*\"\n"
+    "      List all targets depending directly on any target in //base or\n"
+    "      its subdirectories.\n"
+    "\n"
+    "  gn refs out/Debug \"//base:*\"\n"
+    "      List all targets depending directly on any target in\n"
+    "      //base/BUILD.gn.\n"
+    "\n"
+    "  gn refs out/Debug //base --tree\n"
+    "      Print a reverse dependency tree of //base:base\n";
 
 int RunRefs(const std::vector<std::string>& args) {
-  if (args.size() != 1 && args.size() != 2) {
+  if (args.size() != 2) {
     Err(Location(), "You're holding it wrong.",
-        "Usage: \"gn refs <label_pattern>\"").PrintToStdout();
+        "Usage: \"gn refs <build_dir> <label_pattern>\"").PrintToStdout();
     return 1;
   }
 
-  Pattern pattern(args[0]);
-  // Check for common errors on input.
-  if (args[0].find('*') == std::string::npos) {
-    // We need to begin with a "//" and have a colon if there's no "*" or it
-    // will be impossible to match anything.
-    if (args[0].size() < 2 ||
-        (args[0][0] != '/' && args[0][1] != '/') ||
-        args[0].find(':') == std::string::npos) {
-      OutputString("Assuming \"*" + args[0] +
-                       "*\". See \"gn help refs\" for more information.\n",
-                   DECORATION_YELLOW);
-      pattern = Pattern("*" + args[0] + "*");
-    }
-  }
+  const CommandLine* cmdline = CommandLine::ForCurrentProcess();
+  bool tree = cmdline->HasSwitch("tree");
+  bool all = cmdline->HasSwitch("all");
+  bool all_toolchains = cmdline->HasSwitch("all-toolchains");
+  bool files = cmdline->HasSwitch("files");
 
   Setup* setup = new Setup;
   setup->set_check_for_bad_items(false);
-  // TODO(brettw) bug 343726: Use a temporary directory instead of this
-  // default one to avoid messing up any build that's in there.
-  if (!setup->DoSetup("//out/Default/") || !setup->Run())
+  if (!setup->DoSetup(args[0]) || !setup->Run())
     return 1;
 
-  std::vector<const BuilderRecord*> records = setup->builder()->GetAllRecords();
+  // Figure out the target or targets that the user is querying.
+  std::vector<const Target*> query;
+  if (!ResolveTargetsFromCommandLinePattern(setup, args[1], all_toolchains,
+                                            &query))
+    return 1;
+  if (query.empty()) {
+    OutputString("\"" + args[1] + "\" matches no targets.\n");
+    return 0;
+  }
 
-  const CommandLine* cmdline = CommandLine::ForCurrentProcess();
+  // Construct the reverse dependency tree.
+  DepMap dep_map;
+  FillDepMap(setup, &dep_map);
 
-  bool file_output = cmdline->HasSwitch("files");
-  std::set<std::string> unique_output;
-
-  for (size_t record_index = 0; record_index < records.size(); record_index++) {
-    const BuilderRecord* record = records[record_index];
-    const BuilderRecord::BuilderRecordSet& deps = record->all_deps();
-    for (BuilderRecord::BuilderRecordSet::const_iterator d = deps.begin();
-         d != deps.end(); ++d) {
-      std::string label = (*d)->label().GetUserVisibleName(false);
-      if (pattern.MatchesString(label)) {
-        // Got a match.
-        if (file_output) {
-          unique_output.insert(FilePathToUTF8(FilePathForRecord(record)));
-          break;  // Found a match for this target's file, don't need more.
-        } else {
-          // We can get dupes when there are differnet toolchains involved,
-          // so we want to send all output through the de-duper.
-          unique_output.insert(
-              record->item()->label().GetUserVisibleName(false) + " -> " +
-              label);
-        }
-      }
+  if (tree) {
+    // Output dependency tree.
+    if (files) {
+      Err(NULL, "--files option can't be used with --tree option.")
+          .PrintToStdout();
+      return 1;
+    }
+    if (query.size() != 1) {
+      Err(NULL, "Query matches more than one target.",
+          "--tree only supports a single target as input.").PrintToStdout();
+      return 1;
     }
+    if (all) {
+      // Recursively print all targets.
+      RecursivePrintTree(dep_map, query[0], NULL, 0);
+    } else {
+      // Recursively print unique targets.
+      TargetSet seen_targets;
+      RecursivePrintTree(dep_map, query[0], &seen_targets, 0);
+    }
+  } else if (all) {
+    // Output recursive dependencies, uniquified and flattened.
+    TargetSet results;
+    for (size_t query_i = 0; query_i < query.size(); query_i++)
+      RecursiveCollectChildRefs(dep_map, query[query_i], &results);
+    OutputResultSet(results, files);
+  } else {
+    // Output direct references of everything in the query.
+    TargetSet results;
+    for (size_t query_i = 0; query_i < query.size(); query_i++) {
+      DepMap::const_iterator dep_begin = dep_map.lower_bound(query[query_i]);
+      DepMap::const_iterator dep_end = dep_map.upper_bound(query[query_i]);
+      for (DepMap::const_iterator cur_dep = dep_begin;
+           cur_dep != dep_end; cur_dep++)
+        results.insert(cur_dep->second);
+    }
+    OutputResultSet(results, files);
   }
 
-  for (std::set<std::string>::iterator i = unique_output.begin();
-       i != unique_output.end(); ++i)
-    OutputString(*i + "\n");
-
   return 0;
 }