diff --git a/src/gn/header_checker.cc b/src/gn/header_checker.cc
index 562644d..c5c2bfe 100644
--- a/src/gn/header_checker.cc
+++ b/src/gn/header_checker.cc
@@ -5,6 +5,7 @@
 #include "gn/header_checker.h"
 
 #include <algorithm>
+
 #include "base/containers/queue.h"
 #include "base/files/file_util.h"
 #include "base/strings/string_util.h"
@@ -22,6 +23,27 @@
 #include "gn/trace.h"
 #include "util/worker_pool.h"
 
+// This class includes a list of all known files in the build and which targets
+// they are in. When CheckFile is called, it identifies which targets the file
+// is in. If it is in at least one binary target (like a static or shared
+// library, but not a config or an action), then the toolchain is following
+// the rules.
+//
+// The rules are:
+//    1. A target lists a header as public (the default) or private (detected
+//       properly).
+//
+//    2. A target lists a header as private. Then another target depends on the
+//       first target. The second target cannot include the private header.
+//       This is the more advanced check.
+//
+//    3. A target lists a header as public (the default). Then another target
+//       depends on the first target. The second target can include the public
+//       header.
+//
+//    4. A target lists a header. Another target that does not depend on the
+//       first target cannot include the header.
+//
 namespace {
 
 struct PublicGeneratedPair {
@@ -114,59 +136,6 @@
                                      is_marked_friend->label());
 }
 
-// Data for BreadcrumbNode.
-//
-// This class is a trivial type so it can be used in HashTableBase.
-struct BreadcrumbNode {
-  const Target* target;
-  const Target* src_target;
-  bool is_public;
-
-  bool is_null() const { return !target; }
-  static bool is_tombstone() { return false; }
-  bool is_valid() const { return !is_null(); }
-  size_t hash_value() const { return std::hash<const Target*>()(target); }
-};
-
-struct BreadcrumbTable : public HashTableBase<BreadcrumbNode> {
-  using Base = HashTableBase<BreadcrumbNode>;
-  using Node = Base::Node;
-
-  // Since we only insert, we don't need to return success/failure.
-  // We can also assume that key uniqueness is checked before insertion if
-  // necessary, or that we simply overwrite (though BFS usually checks existence
-  // first).
-  //
-  // In IsDependencyOf, we use the return value checking if it was already
-  // there. So we need an Insert that returns whether it was new.
-  bool Insert(const Target* target, const Target* src_target, bool is_public) {
-    size_t hash = std::hash<const Target*>()(target);
-    Node* node = NodeLookup(
-        hash, [target](const Node* n) { return n->target == target; });
-
-    if (node->is_valid())
-      return false;
-
-    node->target = target;
-    node->src_target = src_target;
-    node->is_public = is_public;
-    UpdateAfterInsert(false);
-    return true;
-  }
-
-  // Returns the ChainLink for the given target, or a null-target ChainLink if
-  // not found.
-  HeaderChecker::ChainLink GetLink(const Target* target) const {
-    size_t hash = std::hash<const Target*>()(target);
-    const Node* node = NodeLookup(
-        hash, [target](const Node* n) { return n->target == target; });
-
-    if (node->is_valid())
-      return HeaderChecker::ChainLink(node->src_target, node->is_public);
-    return HeaderChecker::ChainLink();
-  }
-};
-
 }  // namespace
 
 HeaderChecker::HeaderChecker(const BuildSettings* build_settings,
@@ -352,6 +321,92 @@
   return SourceFile();
 }
 
+void HeaderChecker::ReachabilityCache::PerformDependencyWalk(bool permitted) {
+  // Conduct the actual BFS.
+  BreadcrumbTable& breadcrumbs =
+      permitted ? permitted_breadcrumbs_ : any_breadcrumbs_;
+  bool& complete = permitted ? permitted_complete_ : any_complete_;
+
+  if (complete)
+    return;
+
+  // work_queue maintains a queue of targets which need to be considered as part
+  // of dependency chain, in the order they were first traversed. Each time a
+  // new transitive dependency of source_target_ is discovered for the first
+  // time, it is added to work_queue and a "breadcrumb" is added, indicating
+  // which target it was reached from when first discovered.
+  base::queue<const Target*> work_queue;
+  work_queue.push(source_target_);
+  breadcrumbs.Insert(source_target_, nullptr, true);
+
+  while (!work_queue.empty()) {
+    const Target* target = work_queue.front();
+    work_queue.pop();
+
+    for (const auto& dep : target->public_deps()) {
+      if (breadcrumbs.Insert(dep.ptr, target, true))
+        work_queue.push(dep.ptr);
+    }
+
+    if (!permitted || target == source_target_) {
+      // Consider all dependencies since all target paths are allowed, so add
+      // in private ones. Also do this the first time through the loop, since
+      // a target can include headers from its direct deps regardless of
+      // public/private-ness.
+      for (const auto& dep : target->private_deps()) {
+        if (breadcrumbs.Insert(dep.ptr, target, false))
+          work_queue.push(dep.ptr);
+      }
+    }
+  }
+  complete = true;
+}
+
+bool HeaderChecker::ReachabilityCache::SearchForDependencyTo(
+    const Target* search_for,
+    bool permitted,
+    Chain* chain) {
+  {
+    std::shared_lock<std::shared_mutex> read_lock(lock_);
+    if (permitted ? permitted_complete_ : any_complete_) {
+      return SearchBreadcrumbs(search_for, permitted, chain);
+    }
+  }
+
+  {
+    std::unique_lock<std::shared_mutex> write_lock(lock_);
+    if (!(permitted ? permitted_complete_ : any_complete_)) {
+      PerformDependencyWalk(permitted);
+    }
+  }
+
+  std::shared_lock<std::shared_mutex> read_lock(lock_);
+  return SearchBreadcrumbs(search_for, permitted, chain);
+}
+
+bool HeaderChecker::ReachabilityCache::SearchBreadcrumbs(
+    const Target* search_for,
+    bool permitted,
+    Chain* chain) const {
+  const BreadcrumbTable& breadcrumbs =
+      permitted ? permitted_breadcrumbs_ : any_breadcrumbs_;
+  ChainLink incoming_link = breadcrumbs.GetLink(search_for);
+  if (!incoming_link.target)
+    return false;
+
+  // Found it! Reconstruct the chain.
+  chain->clear();
+  const Target* cur = search_for;
+  while (cur != source_target_) {
+    ChainLink link = breadcrumbs.GetLink(cur);
+    chain->push_back(ChainLink(cur, link.is_public));
+    cur = link.target;
+  }
+  chain->push_back(ChainLink(source_target_, true));
+
+  return true;
+}
+
 bool HeaderChecker::CheckFile(const Target* from_target,
                               const SourceFile& file,
                               std::vector<Err>* errors) const {
@@ -396,7 +451,9 @@
 
   IncludeStringWithLocation include;
 
-  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
+  // Get the cache for the source target once for the whole file.
+  ReachabilityCache& from_target_cache =
+      GetReachabilityCacheForTarget(from_target);
 
   while (iter.GetNextIncludeString(&include)) {
     if (include.system_style_include && !check_system_)
@@ -406,8 +463,8 @@
     SourceFile included_file =
         SourceFileForInclude(include, include_dirs, input_file, &err);
     if (!included_file.is_null()) {
-      CheckInclude(from_target, input_file, included_file, include.location,
-                   &no_dependency_cache, errors);
+      CheckInclude(from_target_cache, input_file, included_file,
+                   include.location, errors);
     }
   }
 
@@ -420,13 +477,11 @@
 //  - The dependency path to the included target must follow only public_deps.
 //  - If there are multiple targets with the header in it, only one need be
 //    valid for the check to pass.
-void HeaderChecker::CheckInclude(
-    const Target* from_target,
-    const InputFile& source_file,
-    const SourceFile& include_file,
-    const LocationRange& range,
-    std::set<std::pair<const Target*, const Target*>>* no_dependency_cache,
-    std::vector<Err>* errors) const {
+void HeaderChecker::CheckInclude(ReachabilityCache& from_target_cache,
+                                 const InputFile& source_file,
+                                 const SourceFile& include_file,
+                                 const LocationRange& range,
+                                 std::vector<Err>* errors) const {
   // Assume if the file isn't declared in our sources that we don't need to
   // check it. It would be nice if we could give an error if this happens, but
   // our include finder is too primitive and returns all includes, even if
@@ -439,6 +494,8 @@
   const TargetVector& targets = found->second;
   Chain chain;  // Prevent reallocating in the loop.
 
+  const Target* from_target = from_target_cache.source_target();
+
   // If the file is unknown in the current toolchain (rather than being private
   // or in a target not visible to the current target), ignore it. This is a
   // bit of a hack to account for the fact that the include finder doesn't
@@ -485,21 +542,11 @@
       return;
 
     bool is_permitted_chain = false;
-
-    bool cached_no_dependency =
-        no_dependency_cache->find(std::make_pair(to_target, from_target)) !=
-        no_dependency_cache->end();
-
-    bool add_to_cache = !cached_no_dependency;
-
-    if (!cached_no_dependency &&
-        IsDependencyOf(to_target, from_target, &chain, &is_permitted_chain)) {
-      add_to_cache = false;
-
+    if (IsDependencyOf(to_target, from_target_cache, &chain,
+                       &is_permitted_chain)) {
       DCHECK(chain.size() >= 2);
       DCHECK(chain[0].target == to_target);
       DCHECK(chain[chain.size() - 1].target == from_target);
-
       found_dependency = true;
 
       bool effectively_public =
@@ -533,10 +580,6 @@
       last_error = Err();
       break;
     }
-
-    if (add_to_cache) {
-      no_dependency_cache->emplace(to_target, from_target);
-    }
   }
 
   if (!found_dependency || last_error.has_error()) {
@@ -570,127 +613,43 @@
   //    have the annoying false positive problem, but is complex to write.
 }
 
+HeaderChecker::ReachabilityCache& HeaderChecker::GetReachabilityCacheForTarget(
+    const Target* target) const {
+  size_t shard_index = target->label().hash() % kNumShards;
+  auto& shard = dependency_cache_[shard_index];
+  std::unique_lock<std::shared_mutex> lock(shard.lock);
+  auto it = shard.cache.find(target);
+  if (it == shard.cache.end()) {
+    it =
+        shard.cache.emplace(target, std::make_unique<ReachabilityCache>(target))
+            .first;
+  }
+  return *it->second;
+}
+
 bool HeaderChecker::IsDependencyOf(const Target* search_for,
-                                   const Target* search_from,
+                                   ReachabilityCache& from_target_cache,
                                    Chain* chain,
                                    bool* is_permitted) const {
+  const Target* search_from = from_target_cache.source_target();
   if (search_for == search_from) {
     // A target is always visible from itself.
     *is_permitted = true;
     return false;
   }
 
-  size_t hash_for = search_for->label().hash();
-  size_t hash_from = search_from->label().hash();
-  size_t shard_index = (hash_for ^ hash_from) % kNumShards;
-  auto& shard = dependency_cache_[shard_index];
-
-  {
-    std::shared_lock<std::shared_mutex> lock(shard.lock);
-    auto it = shard.cache.find(std::make_pair(search_for, search_from));
-    if (it != shard.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)) {
+  // 1. Try permitted dependency.
+  if (from_target_cache.SearchForDependencyTo(search_for, true, chain)) {
     *is_permitted = true;
-    std::unique_lock<std::shared_mutex> lock(shard.lock);
-    shard.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)) {
+  // 2. Try any dependency.
+  if (from_target_cache.SearchForDependencyTo(search_for, false, chain)) {
     *is_permitted = false;
-    std::unique_lock<std::shared_mutex> lock(shard.lock);
-    shard.cache[std::make_pair(search_for, search_from)] =
-        DependencyState::kNonPermittedDependency;
     return true;
   }
 
-  *is_permitted = false;
-  std::unique_lock<std::shared_mutex> lock(shard.lock);
-  shard.cache[std::make_pair(search_for, search_from)] =
-      DependencyState::kNotADependency;
-  return false;
-}
-
-bool HeaderChecker::IsDependencyOf(const Target* search_for,
-                                   const Target* search_from,
-                                   bool require_permitted,
-                                   Chain* chain) const {
-  // This method conducts a breadth-first search through the dependency graph
-  // to find a shortest chain from search_from to search_for.
-  //
-  // work_queue maintains a queue of targets which need to be considered as
-  // part of this chain, in the order they were first traversed.
-  //
-  // Each time a new transitive dependency of search_from is discovered for
-  // the first time, it is added to work_queue and a "breadcrumb" is added,
-  // indicating which target it was reached from when first discovered.
-  //
-  // Once this search finds search_for, the breadcrumbs are used to reconstruct
-  // a shortest dependency chain (in reverse order) from search_from to
-  // search_for.
-
-  BreadcrumbTable breadcrumbs;
-
-  base::queue<ChainLink> work_queue;
-  work_queue.push(ChainLink(search_from, true));
-
-  bool first_time = true;
-  while (!work_queue.empty()) {
-    ChainLink cur_link = work_queue.front();
-    const Target* target = cur_link.target;
-    work_queue.pop();
-
-    if (target == search_for) {
-      // Found it! Reconstruct the chain.
-      chain->clear();
-      while (target != search_from) {
-        chain->push_back(cur_link);
-        ChainLink next_link = breadcrumbs.GetLink(target);
-        cur_link = next_link;
-        target = cur_link.target;
-      }
-      chain->push_back(ChainLink(search_from, true));
-      return true;
-    }
-
-    // Always consider public dependencies as possibilities.
-    for (const auto& dep : target->public_deps()) {
-      if (breadcrumbs.Insert(dep.ptr, target, cur_link.is_public))
-        work_queue.push(ChainLink(dep.ptr, true));
-    }
-
-    if (first_time || !require_permitted) {
-      // Consider all dependencies since all target paths are allowed, so add
-      // in private ones. Also do this the first time through the loop, since
-      // a target can include headers from its direct deps regardless of
-      // public/private-ness.
-      first_time = false;
-      for (const auto& dep : target->private_deps()) {
-        if (breadcrumbs.Insert(dep.ptr, target, cur_link.is_public))
-          work_queue.push(ChainLink(dep.ptr, false));
-      }
-    }
-  }
-
   return false;
 }
 
diff --git a/src/gn/header_checker.h b/src/gn/header_checker.h
index 8f36445..f0e0408 100644
--- a/src/gn/header_checker.h
+++ b/src/gn/header_checker.h
@@ -13,6 +13,7 @@
 #include <set>
 #include <shared_mutex>
 #include <string_view>
+#include <unordered_map>
 #include <vector>
 
 #include "base/atomic_ref_count.h"
@@ -20,6 +21,7 @@
 #include "base/memory/ref_counted.h"
 #include "gn/c_include_iterator.h"
 #include "gn/err.h"
+#include "gn/hash_table_base.h"
 #include "gn/source_dir.h"
 
 class BuildSettings;
@@ -84,6 +86,142 @@
 
   ~HeaderChecker();
 
+  // Header checking structures ------------------------------------------------
+
+  // Data for BreadcrumbNode.
+  //
+  // This class is a trivial type so it can be used in HashTableBase.
+  // To implement IsDependencyOf(from_target, to_target), a BFS starting from an
+  // arbitrary `from_target` is performed, and a BreadCrumbTable is used to
+  // record during the walk, that a given `|target|` is a dependency of
+  // `|src_target|`, with `|is_public|` indicating the type of dependency.
+  //
+  // This table only records the first (src_target->target) dependency during
+  // the BFS, since only the shortest dependency path is interesting. This also
+  // means that if a target is the dependency of two distinct parents at the
+  // same level, only the first parent will be recorded in the table. Consider
+  // the following graph:
+  //
+  // ```
+  //     A
+  //    / \
+  //   B   C
+  //    \ /
+  //     D
+  // ```
+  //
+  // The BFS will visit nodes in order: A, B, C and D, but will record only the
+  // (D, B) edge, not the (D, C) one, even if B->D is private and C->D is
+  // public.
+  //
+  // This information is later used to reconstruct the dependency chain when
+  // `to_target` is found by the walk.
+  struct BreadcrumbNode {
+    const Target* target;
+    const Target* src_target;
+    bool is_public;
+
+    bool is_null() const { return !target; }
+    static bool is_tombstone() { return false; }
+    bool is_valid() const { return !is_null(); }
+    size_t hash_value() const { return std::hash<const Target*>()(target); }
+  };
+
+  struct BreadcrumbTable : public HashTableBase<BreadcrumbNode> {
+    using Base = HashTableBase<BreadcrumbNode>;
+    using Node = Base::Node;
+
+    // Since we only insert, we don't need to return success/failure.
+    // We can also assume that key uniqueness is checked before insertion if
+    // necessary, or that we simply overwrite (though BFS usually checks
+    // existence first).
+    //
+    // In IsDependencyOf, we use the return value checking if it was already
+    // there. So we need an Insert that returns whether it was new.
+    bool Insert(const Target* target,
+                const Target* src_target,
+                bool is_public) {
+      size_t hash = std::hash<const Target*>()(target);
+      Node* node = NodeLookup(
+          hash, [target](const Node* n) { return n->target == target; });
+
+      if (node->is_valid())
+        return false;
+
+      node->target = target;
+      node->src_target = src_target;
+      node->is_public = is_public;
+      UpdateAfterInsert(false);
+      return true;
+    }
+
+    // Returns the ChainLink for the given target, or a null-target ChainLink if
+    // not found. The returned link.target, if not nullptr, is a dependent of
+    // the input target that was found during the BFS walk, with dependency
+    // type link.is_public.
+    ChainLink GetLink(const Target* target) const {
+      size_t hash = std::hash<const Target*>()(target);
+      const Node* node = NodeLookup(
+          hash, [target](const Node* n) { return n->target == target; });
+
+      if (node->is_valid())
+        return ChainLink(node->src_target, node->is_public);
+      return ChainLink();
+    }
+  };
+
+  // Store the shortest-dependency-path information for all BFS walks starting
+  // from a given `search_from` target.
+  //
+  // `permitted_breadcrumbs` corresponds to public dependencies only.
+  // `any_breadcrumbs` corresponds to all dependencies.
+  //
+  // Each walk type needs only to be performed once, which is recorded by the
+  // corresponding completion flag.
+  class ReachabilityCache {
+   public:
+    ReachabilityCache(const Target* source) : source_target_(source) {}
+    ReachabilityCache(const ReachabilityCache&) = delete;
+    ReachabilityCache& operator=(const ReachabilityCache&) = delete;
+
+    // Returns true if the given `search_for` target is reachable from
+    // `source_target_`.
+    //
+    // If found, the vector given in `chain` will be filled with the reverse
+    // dependency chain from the destination target to the source target.
+    //
+    // If `permitted` is true, only permitted (public) dependency paths are
+    // searched.
+    bool SearchForDependencyTo(const Target* search_for,
+                               bool permitted,
+                               Chain* chain);
+
+    const Target* source_target() const { return source_target_; }
+
+   private:
+    // Reconstructs the shortest dependency chain to the given target if it was
+    // found during a previous walk of the given type. Returns true on success.
+    // Assumes the lock is held.
+    bool SearchBreadcrumbs(const Target* search_for,
+                           bool permitted,
+                           Chain* chain) const;
+
+    // Conducts a breadth-first search through the dependency graph to find a
+    // shortest chain from source_target_. Assumes unique lock is held.
+    void PerformDependencyWalk(bool permitted);
+
+    const Target* source_target_;
+
+    mutable std::shared_mutex lock_;
+    // Breadcrumbs for the shortest permitted path.
+    BreadcrumbTable permitted_breadcrumbs_;
+    // Breadcrumbs for the shortest path of any type.
+    BreadcrumbTable any_breadcrumbs_;
+
+    bool permitted_complete_ = false;
+    bool any_complete_ = false;
+  };
+
   struct TargetInfo {
     TargetInfo() : target(nullptr), is_public(false), is_generated(false) {}
     TargetInfo(const Target* t, bool is_pub, bool is_gen)
@@ -124,24 +262,20 @@
   // error messages.
   bool CheckFile(const Target* from_target,
                  const SourceFile& file,
-                 std::vector<Err>* err) const;
+                 std::vector<Err>* errors) const;
 
   // Checks that the given file in the given target can include the
   // given include file. If disallowed, adds the error or errors to
   // the errors array.  The range indicates the location of the
   // include in the file for error reporting.
-  // |no_depeency_cache| is used to cache or check whether there is no
-  // dependency from |from_target| to target having |include_file|.
-  void CheckInclude(
-      const Target* from_target,
-      const InputFile& source_file,
-      const SourceFile& include_file,
-      const LocationRange& range,
-      std::set<std::pair<const Target*, const Target*>>* no_dependency_cache,
-      std::vector<Err>* errors) const;
+  void CheckInclude(ReachabilityCache& from_target_cache,
+                    const InputFile& source_file,
+                    const SourceFile& include_file,
+                    const LocationRange& range,
+                    std::vector<Err>* errors) const;
 
   // Returns true if the given search_for target is a dependency of
-  // search_from.
+  // the target associated with the given cache.
   //
   // If found, the vector given in "chain" will be filled with the reverse
   // dependency chain from the dest target (chain[0] = search_for) to the src
@@ -156,17 +290,10 @@
   // one may be private, since a direct dependency always allows headers to be
   // included.
   bool IsDependencyOf(const Target* search_for,
-                      const Target* search_from,
+                      ReachabilityCache& from_target_cache,
                       Chain* chain,
                       bool* is_permitted) const;
 
-  // For internal use by the previous override of IsDependencyOf.  If
-  // require_public is true, only public dependency chains are searched.
-  bool IsDependencyOf(const Target* search_for,
-                      const Target* search_from,
-                      bool require_permitted,
-                      Chain* chain) const;
-
   // Makes a very descriptive error message for when an include is disallowed
   // from a given from_target, with a missing dependency to one of the given
   // targets.
@@ -193,19 +320,10 @@
   // 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>;
-
   static constexpr size_t kNumShards = 64;
   struct DependencyCacheShard {
     mutable std::shared_mutex lock;
-    DependencyCache cache;
+    std::unordered_map<const Target*, std::unique_ptr<ReachabilityCache>> cache;
   };
 
   // Locked variables ----------------------------------------------------------
@@ -218,6 +336,9 @@
 
   mutable std::array<DependencyCacheShard, kNumShards> dependency_cache_;
 
+  // Returns the cache for the given target, creating it if it doesn't exist.
+  ReachabilityCache& GetReachabilityCacheForTarget(const Target* target) const;
+
   // Separate lock for task count synchronization since std::condition_variable
   // only works with std::unique_lock<std::mutex>.
   std::mutex task_count_lock_;
diff --git a/src/gn/header_checker_unittest.cc b/src/gn/header_checker_unittest.cc
index 00a82d3..ec5a397 100644
--- a/src/gn/header_checker_unittest.cc
+++ b/src/gn/header_checker_unittest.cc
@@ -98,12 +98,13 @@
   // A does not depend on itself.
   bool is_permitted = false;
   HeaderChecker::Chain chain;
-  EXPECT_FALSE(checker->IsDependencyOf(&a_, &a_, &chain, &is_permitted));
+  auto& a_cache = checker->GetReachabilityCacheForTarget(&a_);
+  EXPECT_FALSE(checker->IsDependencyOf(&a_, a_cache, &chain, &is_permitted));
 
   // A depends publicly on B.
   chain.clear();
   is_permitted = false;
-  EXPECT_TRUE(checker->IsDependencyOf(&b_, &a_, &chain, &is_permitted));
+  EXPECT_TRUE(checker->IsDependencyOf(&b_, a_cache, &chain, &is_permitted));
   ASSERT_EQ(2u, chain.size());
   EXPECT_EQ(HeaderChecker::ChainLink(&b_, true), chain[0]);
   EXPECT_EQ(HeaderChecker::ChainLink(&a_, true), chain[1]);
@@ -113,7 +114,7 @@
   // be identified.
   chain.clear();
   is_permitted = false;
-  EXPECT_TRUE(checker->IsDependencyOf(&c_, &a_, &chain, &is_permitted));
+  EXPECT_TRUE(checker->IsDependencyOf(&c_, a_cache, &chain, &is_permitted));
   ASSERT_EQ(3u, chain.size());
   EXPECT_EQ(HeaderChecker::ChainLink(&c_, true), chain[0]);
   EXPECT_EQ(HeaderChecker::ChainLink(&b_, true), chain[1]);
@@ -123,7 +124,8 @@
   // C does not depend on A.
   chain.clear();
   is_permitted = false;
-  EXPECT_FALSE(checker->IsDependencyOf(&a_, &c_, &chain, &is_permitted));
+  auto& c_cache = checker->GetReachabilityCacheForTarget(&c_);
+  EXPECT_FALSE(checker->IsDependencyOf(&a_, c_cache, &chain, &is_permitted));
   EXPECT_TRUE(chain.empty());
   EXPECT_FALSE(is_permitted);
 
@@ -132,7 +134,9 @@
   chain.clear();
   EXPECT_EQ(&c_, b_.public_deps()[0].ptr);  // Validate it's the right one.
   b_.public_deps().erase(b_.public_deps().begin());
-  EXPECT_TRUE(checker->IsDependencyOf(&c_, &a_, &chain, &is_permitted));
+  checker = CreateChecker();
+  auto& a_cache2 = checker->GetReachabilityCacheForTarget(&a_);
+  EXPECT_TRUE(checker->IsDependencyOf(&c_, a_cache2, &chain, &is_permitted));
   EXPECT_EQ(3u, chain.size());
   EXPECT_EQ(HeaderChecker::ChainLink(&c_, false), chain[0]);
   EXPECT_EQ(HeaderChecker::ChainLink(&p, true), chain[1]);
@@ -143,7 +147,8 @@
   // one hop.
   chain.clear();
   is_permitted = false;
-  EXPECT_TRUE(checker->IsDependencyOf(&c_, &p, &chain, &is_permitted));
+  auto& p_cache = checker->GetReachabilityCacheForTarget(&p);
+  EXPECT_TRUE(checker->IsDependencyOf(&c_, p_cache, &chain, &is_permitted));
   ASSERT_EQ(2u, chain.size());
   EXPECT_EQ(HeaderChecker::ChainLink(&c_, false), chain[0]);
   EXPECT_EQ(HeaderChecker::ChainLink(&p, true), chain[1]);
@@ -197,46 +202,36 @@
 
   auto checker = CreateChecker();
 
-  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
   // A file in target A can't include a header from D because A has no
   // dependency on D.
   std::vector<Err> errors;
-  checker->CheckInclude(&a_, input_file, d_header, range, &no_dependency_cache,
-                        &errors);
+  auto& a_cache = checker->GetReachabilityCacheForTarget(&a_);
+  checker->CheckInclude(a_cache, input_file, d_header, range, &errors);
   EXPECT_GT(errors.size(), 0);
 
   // A can include the public header in B.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&a_, input_file, b_public, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(a_cache, input_file, b_public, range, &errors);
   EXPECT_EQ(errors.size(), 0);
 
   // Check A depending on the public and private headers in C.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&a_, input_file, c_public, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(a_cache, input_file, c_public, range, &errors);
   EXPECT_EQ(errors.size(), 0);
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&a_, input_file, c_private, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(a_cache, input_file, c_private, range, &errors);
   EXPECT_GT(errors.size(), 0);
 
   // A can depend on a random file unknown to the build.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&a_, input_file, SourceFile("//random.h"), range,
-                        &no_dependency_cache, &errors);
+  checker->CheckInclude(a_cache, input_file, SourceFile("//random.h"), range,
+                        &errors);
   EXPECT_EQ(errors.size(), 0);
 
   // A can depend on a file present only in another toolchain even with no
   // dependency path.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&a_, input_file, otc_header, range,
-                        &no_dependency_cache, &errors);
+  checker->CheckInclude(a_cache, input_file, otc_header, range, &errors);
   EXPECT_EQ(errors.size(), 0);
 }
 
@@ -255,12 +250,15 @@
 
   a_.private_deps().push_back(LabelTargetPair(&z));
 
+  // Update checker because we modified the target graph.
+  auto checker = CreateChecker();
+  auto& a_cache = checker->GetReachabilityCacheForTarget(&a_);
+
   // Check that D can be found from A, but since it's private, it will be
   // marked as not permitted.
   bool is_permitted = false;
   HeaderChecker::Chain chain;
-  auto checker = CreateChecker();
-  EXPECT_TRUE(checker->IsDependencyOf(&d_, &a_, &chain, &is_permitted));
+  EXPECT_TRUE(checker->IsDependencyOf(&d_, a_cache, &chain, &is_permitted));
 
   EXPECT_FALSE(is_permitted);
   ASSERT_EQ(3u, chain.size());
@@ -272,8 +270,9 @@
   // search for D again.
   c_.public_deps().push_back(LabelTargetPair(&d_));
   checker = CreateChecker();
+  auto& a_cache2 = checker->GetReachabilityCacheForTarget(&a_);
   chain.clear();
-  EXPECT_TRUE(checker->IsDependencyOf(&d_, &a_, &chain, &is_permitted));
+  EXPECT_TRUE(checker->IsDependencyOf(&d_, a_cache2, &chain, &is_permitted));
 
   // This should have found the long public one.
   EXPECT_TRUE(is_permitted);
@@ -295,12 +294,11 @@
   a_.sources().push_back(a_public);
 
   auto checker = CreateChecker();
+  auto& b_cache = checker->GetReachabilityCacheForTarget(&b_);
 
   // A depends on B. So B normally can't include headers from A.
   std::vector<Err> errors;
-  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
-  checker->CheckInclude(&b_, input_file, a_public, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(b_cache, input_file, a_public, range, &errors);
   EXPECT_GT(errors.size(), 0);
 
   // Add an allow_circular_includes_from on A that lists B.
@@ -308,9 +306,7 @@
 
   // Now the include from B to A should be allowed.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&b_, input_file, a_public, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(b_cache, input_file, a_public, range, &errors);
   EXPECT_EQ(errors.size(), 0);
 }
 
@@ -339,26 +335,22 @@
   targets_.push_back(&s);
 
   auto checker = CreateChecker();
+  auto& d_cache = checker->GetReachabilityCacheForTarget(&d_);
 
   InputFile input_file(SourceFile("//some_file.cc"));
   input_file.SetContents(std::string());
   LocationRange range;  // Dummy value.
 
   std::vector<Err> errors;
-  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
 
   // Check that unrelated target D cannot include header generated by S.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&d_, input_file, generated_header, range,
-                        &no_dependency_cache, &errors);
+  checker->CheckInclude(d_cache, input_file, generated_header, range, &errors);
   EXPECT_GT(errors.size(), 0);
 
   // Check that unrelated target D cannot include S's bridge header.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&d_, input_file, bridge_header, range,
-                        &no_dependency_cache, &errors);
+  checker->CheckInclude(d_cache, input_file, bridge_header, range, &errors);
   EXPECT_GT(errors.size(), 0);
 }
 
@@ -458,18 +450,16 @@
 
   // Must be after setting everything up for it to find the files.
   auto checker = CreateChecker();
+  auto& b_cache = checker->GetReachabilityCacheForTarget(&b_);
+  auto& a_cache = checker->GetReachabilityCacheForTarget(&a_);
 
   // B should not be allowed to include C's private header.
   std::vector<Err> errors;
-  std::set<std::pair<const Target*, const Target*>> no_dependency_cache;
-  checker->CheckInclude(&b_, input_file, c_private, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(b_cache, input_file, c_private, range, &errors);
   EXPECT_GT(errors.size(), 0);
 
   // A should be able to because of the friend declaration.
   errors.clear();
-  no_dependency_cache.clear();
-  checker->CheckInclude(&a_, input_file, c_private, range, &no_dependency_cache,
-                        &errors);
+  checker->CheckInclude(a_cache, input_file, c_private, range, &errors);
   EXPECT_EQ(errors.size(), 0);
 }