Use ReachabilityCache to improve performance of loop detection Together with the previous optimizations, this changes the time complexity of suggestions be no longer proportional to the number of targets in the build graph. To benchmark this, I changed the allowlist for `check_includes_strict` to //*, then ran `gn check`. Before: Outputs a few errors per second. Left it running for a few minutes and I had no way to tell how long it was going to take, but probably hours. After: Outputs 295,000 errors in 22 seconds. Change-Id: I4658aa7f612400eec44870c7dc962f176a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/26242 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 9a0ca03..5009b9a 100644 --- a/src/gn/command_suggest.cc +++ b/src/gn/command_suggest.cc
@@ -5,8 +5,8 @@ #include <stddef.h> #include <algorithm> -#include <deque> #include <functional> +#include <memory> #include <mutex> #include <tuple> #include <unordered_map> @@ -187,51 +187,6 @@ return SourceFile(); } -// 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. -std::vector<const Target*> FindDependencyPath(const Target* from, - const Target* to) { - std::deque<const Target*> queue; - std::unordered_map<const Target*, const Target*> parents; - parents[from] = nullptr; - queue.push_back(from); - - const Target* cur = nullptr; - while (!queue.empty()) { - cur = queue.front(); - queue.pop_front(); - if (cur == to) { - break; - } - - auto add_deps = [&](const LabelTargetVector& deps) { - for (const auto& dep : deps) { - if (dep.ptr) { - if (parents.emplace(dep.ptr, cur).second) { - queue.push_back(dep.ptr); - } - } - } - }; - - add_deps(cur->public_deps()); - add_deps(cur->private_deps()); - } - - if (cur != to) { - return {}; - } - - std::vector<const Target*> path; - while (cur != nullptr) { - path.push_back(cur); - cur = parents[cur]; - } - std::reverse(path.begin(), path.end()); - return path; -} - } // namespace TargetResolutionCache::TargetResolutionCache() = default; @@ -334,6 +289,20 @@ return results; } +HeaderChecker::ReachabilityCache& TargetResolutionCache::GetReachabilityCache( + const Target* target) { + std::lock_guard<std::mutex> lock(reachability_cache_lock_); + auto it = reachability_cache_.find(target); + if (it == reachability_cache_.end()) { + it = + reachability_cache_ + .emplace(target, + std::make_unique<HeaderChecker::ReachabilityCache>(target)) + .first; + } + return *it->second; +} + // Resolves an input to a list of targets, and whether each are private. // The input can be: // * A module name for a target @@ -753,8 +722,10 @@ std::vector<CandidateDep> candidate_deps; for (const auto& target : candidates) { Label label = target->label(); - std::vector<const Target*> cycle = FindDependencyPath(target, includer); - if (!cycle.empty()) { + HeaderChecker::Chain cycle; + if (cache.GetReachabilityCache(target).SearchForDependencyTo( + includer, /*permitted=*/false, &cycle)) { + std::reverse(cycle.begin(), cycle.end()); StartWarning(); OutputTarget(target); OutputString(" depends on "); @@ -768,7 +739,7 @@ for (size_t i = 0; i < cycle.size(); i++) { OutputString(" "); - OutputTarget(cycle[i]); + OutputTarget(cycle[i].target); if (i + 1 < cycle.size()) { OutputString(" ->"); } @@ -776,7 +747,8 @@ } bool has_allow_circular_includes_from = false; - for (const Target* t : cycle) { + for (const auto& link : cycle) { + const Target* t = link.target; if (!t->allow_circular_includes_from().empty()) { has_allow_circular_includes_from = true; SetAmbiguous();
diff --git a/src/gn/commands.h b/src/gn/commands.h index 6325058..98009ee 100644 --- a/src/gn/commands.h +++ b/src/gn/commands.h
@@ -7,6 +7,7 @@ #include <functional> #include <map> +#include <memory> #include <mutex> #include <optional> #include <set> @@ -16,6 +17,7 @@ #include <vector> #include "base/values.h" +#include "gn/header_checker.h" #include "gn/standard_out.h" #include "gn/target.h" #include "gn/unique_vector.h" @@ -149,6 +151,9 @@ const Target& target, const std::vector<const Target*>& all_targets); + // Returns reference to ReachabilityCache for the given target. + HeaderChecker::ReachabilityCache& GetReachabilityCache(const Target* target); + private: std::once_flag file_to_target_initialized_; std::unordered_map<SourceFile, @@ -161,6 +166,12 @@ std::once_flag forwarding_parents_initialized_; std::unordered_map<const Target*, std::vector<const Target*>> forwarding_parents_; + + // Maps a Target to its ReachabilityCache for cycle detection. + std::mutex reachability_cache_lock_; + std::unordered_map<const Target*, + std::unique_ptr<HeaderChecker::ReachabilityCache>> + reachability_cache_; }; SuggestResult OutputSuggestions(const std::vector<const Target*>& all_targets,
diff --git a/src/gn/header_checker.h b/src/gn/header_checker.h index 0fee4b6..17e2afc 100644 --- a/src/gn/header_checker.h +++ b/src/gn/header_checker.h
@@ -67,6 +67,141 @@ SourceFile included_file; }; + // 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; + + const Target* source_target() const { return source_target_; } + + // 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); + + // Conducts a breadth-first search through the dependency graph to find a + // shortest chain from source_target_. + void PerformDependencyWalk(bool permitted); + + private: + // 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(); + } + }; + + // 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. + bool SearchBreadcrumbs(const Target* search_for, + bool permitted, + Chain* chain) const; + + 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_; + + std::atomic<bool> permitted_complete_ = false; + std::atomic<bool> any_complete_ = false; + }; + // check_generated, if true, will also check generated // files. Something that can only be done after running a build that // has generated them. @@ -106,141 +241,6 @@ ~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); - - // Conducts a breadth-first search through the dependency graph to find a - // shortest chain from source_target_. - void PerformDependencyWalk(bool permitted); - - 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. - bool SearchBreadcrumbs(const Target* search_for, - bool permitted, - Chain* chain) const; - - 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_; - - std::atomic<bool> permitted_complete_ = false; - std::atomic<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)