Optimize reachability cache to drastically reduce BFS executions The most significant part of this optimization is caching the reachability search results starting from a 'from_target'. By sharing this cache across all files and includes within the same target, we avoid redundant, expensive BFS traverses, which was the primary bottleneck. Benchmark results on macOS (hyperfine): Benchmark 1: gn_main gen out/no_clang_modules/ --check Time (mean ± σ): 15.978 s ± 0.107 s [User: 139.317 s, System: 20.336 s] Range (min … max): 15.845 s … 16.141 s 10 runs Benchmark 2: gn_bfs_cache gen out/no_clang_modules/ --check Time (mean ± σ): 7.578 s ± 0.048 s [User: 23.380 s, System: 38.648 s] Range (min … max): 7.481 s … 7.656 s 10 runs Summary gn_bfs_cache ran 2.11 ± 0.02 times faster than gn_main Additionally, this change: - Shards the cache into 64 shards using std::unordered_map and fine-grained locking (std::shared_mutex) to reduce lock contention during concurrent checks. - Uses std::unique_ptr for ReachabilityCache to safely manage non-copyable objects (due to the included mutex). Bug: 484862257 Change-Id: I9a85e813ba942384eb1237fa965e447b1224659d Reviewed-on: https://gn-review.googlesource.com/c/gn/+/21160 Reviewed-by: David Turner <digit@google.com> Commit-Queue: Takuto Ikuta <tikuta@google.com>
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); }