[perf] Cache dependency checks in HeaderChecker

This optimization introduces a thread-safe cache for IsDependencyOf
results in HeaderChecker.

On large projects like Chromium, 'gn gen --check' performs a massive
number of include validations. Many of these involve checking
reachability between the same pairs of targets over and over again. Each
check previously required a full BFS traversal of the dependency graph.

By caching whether target A can depend on target B (and if the path is
publicly permitted), we avoid the vast majority of these expensive
traversals.

Performance on Chromium 'gn gen --check':
- Before: ~125 seconds
- After: ~66 seconds (approx. 47% faster)
- CPU user time reduced from ~16 minutes to ~8 minutes.

Bug: 484862257
Change-Id: Ib46fef088039a145a53f1eb541c27f296a4df3ba
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/21001
Commit-Queue: Takuto Ikuta <tikuta@google.com>
Reviewed-by: David Turner <digit@google.com>

src/gn/header_checker.cc

diff --git a/src/gn/header_checker.cc b/src/gn/header_checker.cc
index 1ecc90a..20ed4bc 100644
--- a/src/gn/header_checker.cc
+++ b/src/gn/header_checker.cc
@@ -186,7 +186,7 @@
   task_count_.Decrement();
 
   // Wait for all tasks posted by this method to complete.
-  std::unique_lock<std::mutex> auto_lock(lock_);
+  std::unique_lock<std::mutex> auto_lock(task_count_lock_);
   while (!task_count_.IsZero())
     task_count_cv_.wait(auto_lock);
 }
@@ -194,13 +194,13 @@
 void HeaderChecker::DoWork(const Target* target, const SourceFile& file) {
   std::vector<Err> errors;
   if (!CheckFile(target, file, &errors)) {
-    std::lock_guard<std::mutex> lock(lock_);
+    std::lock_guard<std::shared_mutex> lock(lock_);
     errors_.insert(errors_.end(), errors.begin(), errors.end());
   }
 
   if (!task_count_.Decrement()) {
     // Signal |task_count_cv_| when |task_count_| becomes zero.
-    std::unique_lock<std::mutex> auto_lock(lock_);
+    std::unique_lock<std::mutex> auto_lock(task_count_lock_);
     task_count_cv_.notify_one();
   }
 }
@@ -528,19 +528,48 @@
     return false;
   }
 
+  {
+    std::shared_lock<std::shared_mutex> lock(lock_);
+    auto it = dependency_cache_.find(std::make_pair(search_for, search_from));
+    if (it != dependency_cache_.end()) {
+      if (it->second == DependencyState::kNotADependency) {
+        *is_permitted = false;
+        return false;
+      }
+      *is_permitted = (it->second == DependencyState::kPermittedDependency);
+      if (*is_permitted) {
+        // For permitted chains, we often don't need the chain itself (it's
+        // only used for error reporting). If the caller provided a null
+        // chain, we can return immediately.
+        if (!chain)
+          return true;
+      }
+      // If we need the chain, we have to re-run the BFS.
+    }
+  }
+
   // Find the shortest public dependency chain.
   if (IsDependencyOf(search_for, search_from, true, chain)) {
     *is_permitted = true;
+    std::unique_lock<std::shared_mutex> lock(lock_);
+    dependency_cache_[std::make_pair(search_for, search_from)] =
+        DependencyState::kPermittedDependency;
     return true;
   }
 
   // If not, try to find any dependency chain at all.
   if (IsDependencyOf(search_for, search_from, false, chain)) {
     *is_permitted = false;
+    std::unique_lock<std::shared_mutex> lock(lock_);
+    dependency_cache_[std::make_pair(search_for, search_from)] =
+        DependencyState::kNonPermittedDependency;
     return true;
   }
 
   *is_permitted = false;
+  std::unique_lock<std::shared_mutex> lock(lock_);
+  dependency_cache_[std::make_pair(search_for, search_from)] =
+      DependencyState::kNotADependency;
   return false;
 }
 

src/gn/header_checker.h

diff --git a/src/gn/header_checker.h b/src/gn/header_checker.h
index fd053dd..0c88149 100644
--- a/src/gn/header_checker.h
+++ b/src/gn/header_checker.h
@@ -10,6 +10,7 @@
 #include <map>
 #include <mutex>
 #include <set>
+#include <shared_mutex>
 #include <string_view>
 #include <vector>
 
@@ -191,14 +192,29 @@
   // execution.
   base::AtomicRefCount task_count_;
 
+  // Maps (target_to, target_from) -> is_permitted.
+  enum class DependencyState {
+    kNotADependency,
+    kNonPermittedDependency,
+    kPermittedDependency,
+  };
+  using DependencyCache =
+      std::map<std::pair<const Target*, const Target*>, DependencyState>;
+
   // Locked variables ----------------------------------------------------------
   //
   // These are mutable during runtime and require locking.
 
-  std::mutex lock_;
+  mutable std::shared_mutex lock_;
 
   std::vector<Err> errors_;
 
+  mutable DependencyCache dependency_cache_;
+
+  // Separate lock for task count synchronization since std::condition_variable
+  // only works with std::unique_lock<std::mutex>.
+  std::mutex task_count_lock_;
+
   // Signaled when |task_count_| becomes zero.
   std::condition_variable task_count_cv_;