Cache file path -> target lookup in `gn suggest`. 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: Ia47be0e501d26be321ad2fdc8681750b6a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/26240 Reviewed-by: Takuto Ikuta <tikuta@google.com> Commit-Queue: Matt Stark <msta@google.com>
diff --git a/src/gn/command_check.cc b/src/gn/command_check.cc index 0edfc2f..d28a070 100644 --- a/src/gn/command_check.cc +++ b/src/gn/command_check.cc
@@ -300,6 +300,7 @@ bool remaining_violations = false; bool needs_separator = false; bool has_suggestions = false; + TargetResolutionCache cache; for (auto& violation : violations) { if (needs_separator) { OutputString("___________________\n", DECORATION_YELLOW); @@ -315,7 +316,7 @@ [&](std::string_view str, TextDecoration dec, HtmlEscaping esc) { buf.emplace_back(str, dec, esc); }, - apply, setup); + cache, apply, setup); fixed = apply && (exit_code == SuggestResult::kSuccess); if (!buf.empty()) { has_suggestions = true;
diff --git a/src/gn/command_suggest.cc b/src/gn/command_suggest.cc index 1e0d4e5..aafc719 100644 --- a/src/gn/command_suggest.cc +++ b/src/gn/command_suggest.cc
@@ -7,6 +7,7 @@ #include <algorithm> #include <deque> #include <functional> +#include <mutex> #include <tuple> #include <unordered_map> #include <unordered_set> @@ -101,44 +102,19 @@ kAddedTodos, }; -// Determines whether a source file is in either the public or private API of a -// target. -std::optional<commands::ApiScope> DepKind(const Target* target, - const SourceFile& file) { - for (const auto& source : target->sources()) { - if (source == file) { - return target->all_headers_public() && - file.GetType() == SourceFile::SOURCE_H - ? commands::ApiScope::kPublic - : commands::ApiScope::kPrivate; - } - } - for (const auto& header : target->public_headers()) { - if (header == file) { - return commands::ApiScope::kPublic; - } - } - for (const auto& output : target->computed_outputs()) { - if (output.AsSourceFile(target->settings()->build_settings()) == file) { - return commands::ApiScope::kOutput; - } - } - return std::nullopt; -} - // Finds all targets that use a file as a source from a specific toolchain and // adds them to results. Checks every toolchain if current_toolchain is null. bool AddToolchainSources( const std::vector<const Target*>& all_targets, const Label* current_toolchain, const SourceFile& file, + TargetResolutionCache& cache, std::vector<std::pair<const Target*, commands::ApiScope>>& results) { - for (const Target* target : all_targets) { + for (const auto& [target, scope] : + cache.GetTargetsForFile(file, all_targets)) { if (!current_toolchain || target->label().GetToolchainLabel() == *current_toolchain) { - if (auto dep_kind = DepKind(target, file); dep_kind.has_value()) { - results.emplace_back(target, *dep_kind); - } + results.emplace_back(target, scope); } } return !results.empty(); @@ -146,19 +122,18 @@ bool FileExists(const std::vector<const Target*>& all_targets, const SourceFile& file, - const BuildSettings* build_settings) { + const BuildSettings* build_settings, + TargetResolutionCache& cache) { base::FilePath build_dir_path = build_settings->GetFullPath(build_settings->build_dir()); base::FilePath file_path = build_settings->GetFullPath(file); if (build_dir_path.IsParent(file_path)) { // It's in the output directory, so check if it was generated by a target. - OutputFile target_file(build_settings, file); - for (const Target* target : all_targets) { - for (const OutputFile& output : target->computed_outputs()) { - if (output == target_file) { - return true; - } + for (const auto& [target, scope] : + cache.GetTargetsForFile(file, all_targets)) { + if (scope == commands::ApiScope::kOutput) { + return true; } } return false; @@ -171,10 +146,11 @@ SourceFile ResolveFilePath(const BuildSettings* build_settings, const std::vector<const Target*>& all_targets, std::string_view input, + TargetResolutionCache& cache, const Target* includer = nullptr) { if (input.starts_with("//")) { SourceFile file = SourceFile(input); - if (FileExists(all_targets, file, build_settings)) { + if (FileExists(all_targets, file, build_settings, cache)) { return file; } return SourceFile(); @@ -188,7 +164,8 @@ Err err; SourceFile file = build_settings->build_dir().ResolveRelativeFile(input_value, &err); - if (!err.has_error() && FileExists(all_targets, file, build_settings)) { + if (!err.has_error() && + FileExists(all_targets, file, build_settings, cache)) { return file; } // If we are unable to resolve the file, we should treat it as a #include. @@ -201,7 +178,7 @@ SourceFile resolved_file = dir.ResolveRelativeFile(input_value, &resolve_err); if (!resolve_err.has_error() && - FileExists(all_targets, resolved_file, build_settings)) { + FileExists(all_targets, resolved_file, build_settings, cache)) { return resolved_file; } } @@ -289,6 +266,47 @@ } // namespace +TargetResolutionCache::TargetResolutionCache() = default; +TargetResolutionCache::~TargetResolutionCache() = default; + +const std::vector<std::pair<const Target*, ApiScope>>& +TargetResolutionCache::GetTargetsForFile( + const SourceFile& file, + const std::vector<const Target*>& all_targets) { + std::call_once(file_to_target_initialized_, [&]() { + for (const Target* target : all_targets) { + for (const auto& output : target->computed_outputs()) { + SourceFile source = + output.AsSourceFile(target->settings()->build_settings()); + file_to_targets_[source].emplace_back(target, ApiScope::kOutput); + } + for (const auto& header : target->public_headers()) { + file_to_targets_[header].emplace_back(target, ApiScope::kPublic); + } + for (const auto& source : target->sources()) { + // Some files are mis-declared as both sources and public. + if (std::ranges::find(target->public_headers(), source) != + target->public_headers().end()) { + continue; + } + + if (target->all_headers_public() && + source.GetType() == SourceFile::SOURCE_H) { + file_to_targets_[source].emplace_back(target, ApiScope::kPublic); + } else { + file_to_targets_[source].emplace_back(target, ApiScope::kPrivate); + } + } + } + }); + + auto it = file_to_targets_.find(file); + if (it == file_to_targets_.end()) { + return empty_targets_; + } + 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 @@ -302,6 +320,7 @@ const std::vector<const Target*>& all_targets, const Label& current_toolchain, std::string_view input, + TargetResolutionCache& cache, const Target* includer) { auto sort_results = [](auto& vec) { std::sort(vec.begin(), vec.end(), [](const auto& lhs, const auto& rhs) { @@ -348,15 +367,16 @@ // If that doesn't work, try to resolve as a file path. SourceFile file = - ResolveFilePath(build_settings, all_targets, input, includer); + ResolveFilePath(build_settings, all_targets, input, cache, includer); if (file.is_null()) { return {results, false}; } // If we see //foo(:toolchain) request bar.h, prefer //:bar(:toolchain) // over other toolchains. - if (!AddToolchainSources(all_targets, ¤t_toolchain, file, results)) { - AddToolchainSources(all_targets, nullptr, file, results); + if (!AddToolchainSources(all_targets, ¤t_toolchain, file, cache, + results)) { + AddToolchainSources(all_targets, nullptr, file, cache, results); } // If we have an action that generates "gen/foo.h", we should prefer // depending on the source set that declares it as a header. @@ -381,6 +401,7 @@ std::string_view includer_name, std::string_view included_name, OutputStringFunc output_fn, + TargetResolutionCache& cache, bool apply, Setup* setup) { if (apply) { @@ -526,7 +547,8 @@ auto ResolveSuggestion = [&](std::string_view value, const Target* target_context = nullptr) { const auto& [targets, ok] = ResolveSuggestionToTarget( - build_settings, all_targets, current_toolchain, value, target_context); + build_settings, all_targets, current_toolchain, value, cache, + target_context); if (!ok) { StartError(); if (value.starts_with("//")) { @@ -609,8 +631,8 @@ OutputString(", but not in the toolchain "); OutputString(current_toolchain.GetUserVisibleName(false), kLabelLike); OutputString("\n"); - SourceFile file = - ResolveFilePath(build_settings, all_targets, included_name, includer); + SourceFile file = ResolveFilePath(build_settings, all_targets, + included_name, cache, includer); const Target* target = targets.front().first; std::string path = file.is_null() ? std::string(included_name) @@ -652,8 +674,8 @@ OutputString(" is in the private API of "); OutputTarget(included); OutputString("\n"); - SourceFile file = - ResolveFilePath(build_settings, all_targets, included_name, includer); + SourceFile file = ResolveFilePath(build_settings, all_targets, + included_name, cache, includer); if (file.is_null()) { // We tried to do `gn suggest out //:includer=//:included_Private` std::vector<SourceFile> candidates; @@ -942,6 +964,7 @@ SuggestResult exit_status = SuggestResult::kSuccess; bool has_suggestions = false; + TargetResolutionCache cache; for (size_t i = 1; i < args.size(); i++) { if (i != 1) { OutputString("\n"); @@ -973,7 +996,7 @@ has_suggestions = true; ::OutputString(str, dec, esc); }, - apply, setup); + cache, apply, setup); if (res == SuggestResult::kFailure) { exit_status = SuggestResult::kFailure; } else if (res == SuggestResult::kUnapplied &&
diff --git a/src/gn/command_suggest_unittest.cc b/src/gn/command_suggest_unittest.cc index 7998b0b..68ee9c5 100644 --- a/src/gn/command_suggest_unittest.cc +++ b/src/gn/command_suggest_unittest.cc
@@ -105,11 +105,12 @@ target.set_module_name("my_module"); std::vector<const Target*> all_targets = {&target}; + commands::TargetResolutionCache cache; { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, default_toolchain, - "my_module"); + "my_module", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&target, commands::ApiScope::kPublic}}; EXPECT_EQ(expected, results); @@ -120,7 +121,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, default_toolchain, - "my_module_Private"); + "my_module_Private", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&target, commands::ApiScope::kPrivate}}; EXPECT_EQ(expected, results); @@ -142,11 +143,12 @@ setup_scope.settings(), Label(SourceDir("//"), "hello", SourceDir("//build/toolchain/"), "gcc")); std::vector<const Target*> all_targets = {&target, &target_gcc}; + commands::TargetResolutionCache cache; // Test resolving "//:hello" auto [results_label, ok_label] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, - setup_scope.toolchain()->label(), "//:hello"); + setup_scope.toolchain()->label(), "//:hello", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected_label = { {&target, commands::ApiScope::kPublic}}; @@ -156,7 +158,7 @@ // Test resolving "//:hello(//build/toolchain:gcc)" auto [results_toolchain, ok_toolchain] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, default_toolchain, - "//:hello(//build/toolchain:gcc)"); + "//:hello(//build/toolchain:gcc)", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected_toolchain = {{&target_gcc, commands::ApiScope::kPublic}}; @@ -260,11 +262,12 @@ std::vector<const Target*> all_targets = {&explicit_target, &implicit_target, &simple_default, &simple_secondary, &generated, &included_target}; + commands::TargetResolutionCache cache; { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//public.h"); + "//public.h", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&explicit_target, commands::ApiScope::kPublic}}; EXPECT_TRUE(ok); @@ -274,7 +277,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "../../private.h"); + "../../private.h", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&explicit_target, commands::ApiScope::kPrivate}}; EXPECT_TRUE(ok); @@ -284,7 +287,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//implicit_public.h"); + "//implicit_public.h", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&implicit_target, commands::ApiScope::kPublic}}; EXPECT_TRUE(ok); @@ -294,14 +297,14 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "nonexistent_file.h"); + "nonexistent_file.h", cache); EXPECT_FALSE(ok); } { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//out/Debug/generated_file.h"); + "//out/Debug/generated_file.h", cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&generated, commands::ApiScope::kPublic}}; EXPECT_TRUE(ok); @@ -309,10 +312,11 @@ } all_targets.push_back(&consumer); + commands::TargetResolutionCache consumer_cache; { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//out/Debug/generated_file.h"); + "//out/Debug/generated_file.h", consumer_cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected = { {&consumer, commands::ApiScope::kPublic}}; EXPECT_TRUE(ok); @@ -322,7 +326,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//no_target.h"); + "//no_target.h", consumer_cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected_targets; EXPECT_TRUE(ok); EXPECT_EQ(expected_targets, results); @@ -331,7 +335,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//default_toolchain.h"); + "//default_toolchain.h", consumer_cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected_targets = { {&simple_secondary, commands::ApiScope::kPublic}, @@ -344,7 +348,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "//secondary_toolchain.h"); + "//secondary_toolchain.h", consumer_cache); std::vector<std::pair<const Target*, commands::ApiScope>> expected_targets = {{{&simple_secondary, commands::ApiScope::kPublic}}}; EXPECT_TRUE(ok); @@ -354,7 +358,7 @@ { auto [results, ok] = commands::ResolveSuggestionToTarget( setup_scope.build_settings(), all_targets, current_toolchain, - "my_header.h", &consumer); + "my_header.h", consumer_cache, &consumer); EXPECT_TRUE(ok); std::vector<std::pair<const Target*, commands::ApiScope>> expected_targets = {{{&included_target, commands::ApiScope::kPublic}}}; @@ -410,9 +414,10 @@ auto collect = [&](std::string_view s, TextDecoration, HtmlEscaping) { output.append(s); }; + commands::TargetResolutionCache cache; commands::OutputSuggestions(all_targets, setup_scope.build_settings(), - default_toolchain, "//:includer", want, - collect); + default_toolchain, "//:includer", want, collect, + cache); return output; }; @@ -593,10 +598,11 @@ output.append(s); }; + commands::TargetResolutionCache cache; commands::SuggestResult result = commands::OutputSuggestions( project.targets(), &project.setup.build_settings(), project.default_toolchain(), "//includer.cc", "//included.h", collect, - true, &project.setup); + cache, true, &project.setup); EXPECT_EQ(commands::SuggestResult::kSuccess, result); EXPECT_EQ(
diff --git a/src/gn/commands.h b/src/gn/commands.h index 0cc9c8d..1a362bb 100644 --- a/src/gn/commands.h +++ b/src/gn/commands.h
@@ -7,9 +7,12 @@ #include <functional> #include <map> +#include <mutex> +#include <optional> #include <set> #include <string> #include <string_view> +#include <unordered_map> #include <vector> #include "base/values.h" @@ -119,12 +122,43 @@ kUnapplied = 2, }; +enum class ApiScope { + kPublic, + kPrivate, + kOutput, +}; + +// Caches the mapping of SourceFile -> target(s) to accelerate suggestion +// resolution. +// May potentially be used in the future to cache other properties of the build +// graph. +class TargetResolutionCache { + public: + TargetResolutionCache(); + ~TargetResolutionCache(); + + // Returns reference to vector of (Target*, ApiScope) for the given file. + // If the file is not in any target, returns an empty vector. + const std::vector<std::pair<const Target*, ApiScope>>& GetTargetsForFile( + const SourceFile& file, + const std::vector<const Target*>& all_targets); + + private: + std::once_flag file_to_target_initialized_; + std::unordered_map<SourceFile, + std::vector<std::pair<const Target*, ApiScope>>> + file_to_targets_; + // Never mutated. Used when a file is not in any target. + const std::vector<std::pair<const Target*, ApiScope>> empty_targets_; +}; + SuggestResult OutputSuggestions(const std::vector<const Target*>& all_targets, const BuildSettings* build_settings, const Label& default_toolchain, std::string_view includer_name, std::string_view included_name, OutputStringFunc output_fn, + TargetResolutionCache& cache, bool apply = false, Setup* setup = nullptr); @@ -295,12 +329,6 @@ Setup* setup, const std::string& label_string); -enum class ApiScope { - kPublic, - kPrivate, - kOutput, -}; - // Resolves an input to a list of targets for suggestion. // Specifically also decides whether it resolves to the public or private API // of the target. @@ -309,6 +337,7 @@ const std::vector<const Target*>& all_targets, const Label& current_toolchain, std::string_view input, + TargetResolutionCache& cache, const Target* includer = nullptr); // Resolves a vector of command line inputs and figures out the full set of