Cache reverse dependencies for dependency exposure. This is part of a larger process to improve the performance of suggestions, but does not have change the time complexity until gn-review.googlesource.com/c/gn/+/26242 is submitted (benchmarks in that commit) Change-Id: Ic0bd366f7b2639f16a9e633dde527cec6a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/26281 Commit-Queue: Matt Stark <msta@google.com> Reviewed-by: Takuto Ikuta <tikuta@google.com>

diff --git a/src/gn/command_suggest.cc b/src/gn/command_suggest.cc
index 2aadfdd..9a0ca03 100644
--- a/src/gn/command_suggest.cc
+++ b/src/gn/command_suggest.cc

@@ -187,38 +187,6 @@
   return SourceFile();
 }
 
-// Returns true if depending on target is supposed to give you access to
-// everything in the underlying target.
-bool Exposes(const Target& target, const Target& underlying) {
-  std::vector<const Target*> stack = {&target};
-  std::unordered_set<const Target*> visited;
-  while (!stack.empty()) {
-    const Target* current = stack.back();
-    stack.pop_back();
-    if (visited.insert(current).second) {
-      if (current == &underlying) {
-        return true;
-      }
-      // If we have no headers and no sources, then the only use of depending
-      // on this target is to gain access to its dependencies.
-      if (current->sources().empty() && current->public_headers().empty()) {
-        for (const auto& dep : current->public_deps()) {
-          stack.push_back(dep.ptr);
-        }
-        // If you declare `public_deps = ...` on a group, it shows up as a
-        // private dep. Probably because groups don't distinguish between
-        // public and private deps.
-        if (current->output_type() == Target::GROUP) {
-          for (const auto& dep : current->private_deps()) {
-            stack.push_back(dep.ptr);
-          }
-        }
-      }
-    }
-  }
-  return false;
-}
-
 // Finds the shortest dependency path from `from` to `to`.
 // Returns a vector where the first element is `from` and the last is `to`.
 // Returns the empty vector if no path was found.
@@ -307,6 +275,65 @@
   return it->second;
 }
 
+// Returns targets that directly expose a given target
+// (all targets that forward target through groups or header-less source sets).
+std::vector<const Target*> TargetResolutionCache::GetTargetsExposing(
+    const Target& target,
+    const std::vector<const Target*>& all_targets) {
+  std::call_once(forwarding_parents_initialized_, [&]() {
+    for (const Target* t : all_targets) {
+      // If we have no headers and no sources, then the only use of depending
+      // on this target is to gain access to its dependencies.
+      if (t->sources().empty() && t->public_headers().empty()) {
+        for (const auto& dep : t->public_deps()) {
+          if (dep.ptr) {
+            forwarding_parents_[dep.ptr].push_back(t);
+          }
+        }
+        // If you declare `public_deps = ...` on a group, it shows up as a
+        // private dep. Probably because groups don't distinguish between
+        // public and private deps.
+        if (t->output_type() == Target::GROUP) {
+          for (const auto& dep : t->private_deps()) {
+            if (dep.ptr) {
+              forwarding_parents_[dep.ptr].push_back(t);
+            }
+          }
+        }
+      }
+    }
+  });
+
+  if (!forwarding_parents_.contains(&target)) {
+    return {};
+  }
+
+  std::vector<const Target*> results;
+  std::vector<const Target*> stack = {&target};
+  std::unordered_set<const Target*> visited = {&target};
+
+  while (!stack.empty()) {
+    const Target* cur = stack.back();
+    stack.pop_back();
+
+    auto parent_it = forwarding_parents_.find(cur);
+    if (parent_it != forwarding_parents_.end()) {
+      for (const Target* parent : parent_it->second) {
+        if (visited.insert(parent).second) {
+          results.push_back(parent);
+          stack.push_back(parent);
+        }
+      }
+    }
+  }
+
+  std::sort(
+      results.begin(), results.end(),
+      [](const Target* a, const Target* b) { return a->label() < b->label(); });
+
+  return results;
+}
+
 // Resolves an input to a list of targets, and whether each are private.
 // The input can be:
 // * A module name for a target
@@ -866,13 +893,13 @@
   std::vector<const Target*> visible_candidates;
   std::vector<const Target*> nonpublic_candidates;
   std::vector<const Target*> all_candidates;
-  for (const Target* candidate : all_targets) {
+  for (const Target* candidate :
+       cache.GetTargetsExposing(*included, all_targets)) {
     if (candidate == included)
       continue;
     // Check that the toolchains are the same to avoid picking up both //:foo
     // and //:foo(other_toolchain).
-    if (candidate->label().ToolchainsEqual(includer->label()) &&
-        Exposes(*candidate, *included)) {
+    if (candidate->label().ToolchainsEqual(includer->label())) {
       all_candidates.push_back(candidate);
       if (candidate->visibility().CanSeeMe(includer->label())) {
         visible_candidates.push_back(candidate);

diff --git a/src/gn/commands.h b/src/gn/commands.h
index 471ab2f..6325058 100644
--- a/src/gn/commands.h
+++ b/src/gn/commands.h

@@ -143,6 +143,12 @@
       const SourceFile& file,
       const std::vector<const Target*>& all_targets);
 
+  // Returns vector of targets that expose the given target
+  // (e.g. forwarding groups or header-less source sets that depend on it).
+  std::vector<const Target*> GetTargetsExposing(
+      const Target& target,
+      const std::vector<const Target*>& all_targets);
+
  private:
   std::once_flag file_to_target_initialized_;
   std::unordered_map<SourceFile,
@@ -150,6 +156,11 @@
       file_to_targets_;
   // Never mutated. Used when a file is not in any target.
   const std::vector<std::pair<const Target*, ApiScope>> empty_targets_;
+
+  // Maps a Target to the list of forwarding targets that directly expose it.
+  std::once_flag forwarding_parents_initialized_;
+  std::unordered_map<const Target*, std::vector<const Target*>>
+      forwarding_parents_;
 };
 
 SuggestResult OutputSuggestions(const std::vector<const Target*>& all_targets,