Speed up "gn path".

tools/gn/command_path.cc

Index: tools/gn/command_path.cc
diff --git a/tools/gn/command_path.cc b/tools/gn/command_path.cc
index 573e8cbfeed214a684de0733d8421ce768df563c..ae39c8c557191789a2ac2b358fb640ccb8413b95 100644
--- a/tools/gn/command_path.cc
+++ b/tools/gn/command_path.cc
@@ -3,6 +3,7 @@
 // found in the LICENSE file.
 
 #include "base/command_line.h"
+#include "base/containers/hash_tables.h"
 #include "base/strings/stringprintf.h"
 #include "tools/gn/commands.h"
 #include "tools/gn/setup.h"
@@ -24,6 +25,8 @@ enum DepType {
 using TargetDep = std::pair<const Target*, DepType>;
 using DepStack = std::vector<TargetDep>;
 
+using DepSet = base::hash_set<const Target*>;
+
 void PrintDepStack(const DepStack& stack) {
   // Don't print toolchains unless they differ from the first target.
   const Label& default_toolchain = stack[0].first->label().GetToolchainLabel();
@@ -50,11 +53,19 @@ void PrintDepStack(const DepStack& stack) {
 
 // Increments *found_count to reflect how many results are found. If print_all
 // is not set, only the first result will be printed.
+//
+// As an optimization, targets that do not have any paths are added to
+// *reject so this function doesn't waste time revisiting them.
 void RecursiveFindPath(const Target* current,
                        const Target* desired,
                        DepStack* stack,
+                       DepSet* reject,
                        int* found_count,
                        bool print_all) {
+  if (reject->find(current) != reject->end())
+    return;
+  int initial_found_count = *found_count;
+
   if (current == desired) {
     (*found_count)++;
     if (print_all || *found_count == 1) {
@@ -67,16 +78,19 @@ void RecursiveFindPath(const Target* current,
 
   stack->push_back(TargetDep(current, DEP_PUBLIC));
   for (const auto& pair : current->public_deps())
-    RecursiveFindPath(pair.ptr, desired, stack, found_count, print_all);
+    RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all);
 
   stack->back().second = DEP_PRIVATE;
   for (const auto& pair : current->private_deps())
-    RecursiveFindPath(pair.ptr, desired, stack, found_count, print_all);
+    RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all);
 
   stack->back().second = DEP_DATA;
   for (const auto& pair : current->data_deps())
-    RecursiveFindPath(pair.ptr, desired, stack, found_count, print_all);
+    RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all);
   stack->pop_back();
+
+  if (*found_count == initial_found_count)
+    reject->insert(current);  // Eliminated this target.
 }
 
 }  // namespace
@@ -132,10 +146,15 @@ int RunPath(const std::vector<std::string>& args) {
   // can only go in one direction without having a cycle, which will have
   // caused a run failure above.
   DepStack stack;
+  DepSet rejected;
   int found = 0;
-  RecursiveFindPath(target1, target2, &stack, &found, print_all);
-  if (found == 0)
-    RecursiveFindPath(target2, target1, &stack, &found, print_all);
+  RecursiveFindPath(target1, target2, &stack, &rejected, &found, print_all);
+  if (found == 0) {
+    // Need to reset the rejected set for a new invocation since the reverse
+    // search will revisit the same targets looking for something else.
+    rejected.clear();
+    RecursiveFindPath(target2, target1, &stack, &rejected, &found, print_all);
+  }
 
   if (found == 0) {
     OutputString("No paths found between these two targets.\n",