Implement cycle detection and circular dependency handling in `gn suggest`. When suggesting dependency changes, `gn suggest` now checks if the proposed dependency would introduce a cycle. Specifically: - Added `FindDependencyPath` to trace the shortest path of dependencies between targets. - If adding the dependency from target A to target B would create a loop (because B already transitively depends on A), a warning is printed to trace the cycle. - If any target in the cycle utilizes `allow_circular_includes_from`, warns the user that this is bad style and prints a suggestion template demonstrating how to refactor the target (e.g., by splitting it into a `source_set` for compilation units and a target for dependencies). - Added corresponding unit tests in `command_suggest_unittest.cc` to verify the warning messages and suggestion templates. Bug: 500845363 Change-Id: I2d3bf67372073f1aed9c3b1ae6d5a59b6a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/22780 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 a1e71cb..9b7ca28 100644 --- a/src/gn/command_suggest.cc +++ b/src/gn/command_suggest.cc
@@ -5,8 +5,10 @@ #include <stddef.h> #include <algorithm> +#include <deque> #include <functional> #include <tuple> +#include <unordered_map> #include <unordered_set> #include <vector> @@ -137,6 +139,51 @@ return false; } +// 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 // Resolves an input to a list of targets, and whether each are private. @@ -412,11 +459,87 @@ auto OutputDepSuggestion = [&](const std::vector<const Target*>& candidates) { std::vector<std::string> labels; for (const auto& target : candidates) { - labels.push_back( - target->label().dir() == includer->label().dir() - ? ":" + target->label().name() - : target->label().GetUserVisibleName(current_toolchain)); + Label label = target->label(); + std::vector<const Target*> cycle = FindDependencyPath(target, includer); + if (!cycle.empty()) { + StartWarning(); + OutputTarget(target); + OutputString(" depends on "); + OutputTarget(includer); + OutputString( + ", so adding this dependency will create a dependency loop:\n"); + + OutputString(" "); + OutputTarget(includer); + OutputString(" ->\n"); + + for (size_t i = 0; i < cycle.size(); i++) { + OutputString(" "); + OutputTarget(cycle[i]); + if (i + 1 < cycle.size()) { + OutputString(" ->"); + } + OutputString("\n"); + } + + bool has_allow_circular_includes_from = false; + for (const Target* t : cycle) { + if (!t->allow_circular_includes_from().empty()) { + has_allow_circular_includes_from = true; + StartSuggestion(); + OutputString(":", kLabelLike); + OutputString(t->label().name(), kLabelLike); + OutputString(" (defined at "); + OutputString(t->user_friendly_location().Describe(false), + kLabelLike); + OutputString( + ") declares allow_circular_includes_from, which is bad style. " + "Instead, you should remove allow_circular_includes_from by " + "doing the following:\n"); + + OutputString("source_set(\""); + OutputString(t->label().name()); + OutputString("_sources\") {\n"); + OutputString(" # All attributes from :"); + OutputString(t->label().name()); + OutputString(" except public_deps, and any link options\n"); + OutputString( + " # Note that some public_deps may need to be added back " + "based on #includes of headers.\n"); + OutputString("}\n\n"); + + OutputString(Target::GetStringForOutputType(t->output_type())); + OutputString("(\""); + OutputString(t->label().name()); + OutputString("\") {\n"); + OutputString(" public_deps = [ \":"); + OutputString(t->label().name()); + OutputString("_sources\" ]\n"); + OutputString(" # public_deps, and any link variables from :"); + OutputString(t->label().name()); + OutputString("\n"); + OutputString("}\n"); + + if (t == target) { + label = Label(label.dir(), label.name() + "_sources", + label.toolchain_dir(), label.toolchain_name()); + } + break; + } + } + if (!has_allow_circular_includes_from) { + StartSuggestion(); + OutputString( + "Find the part of the dependency chain where there is no " + "#include " + "and remove that dependency.\n"); + } + } + labels.push_back(label.dir() == includer->label().dir() + ? ":" + label.name() + : label.GetUserVisibleName(current_toolchain)); } + std::sort(labels.begin(), labels.end(), [](std::string_view lhs, std::string_view rhs) { // Ensure relative labels come before absolute labels.
diff --git a/src/gn/command_suggest_unittest.cc b/src/gn/command_suggest_unittest.cc index 5f9e8e1..edf342d 100644 --- a/src/gn/command_suggest_unittest.cc +++ b/src/gn/command_suggest_unittest.cc
@@ -345,4 +345,54 @@ "Suggestion: Add public_deps = [ \":exposer_specific\" ] to :includer " "(defined at //BUILD.gn:1)\n", run_suggest(*invisible)); + + auto cyclic = create_target("cyclic", Target::SOURCE_SET, [&](Target* t) { + t->public_deps().push_back(LabelTargetPair(includer.get())); + t->visibility().SetPublic(); + }); + EXPECT_EQ( + "Warning: //:cyclic depends on //:includer, so adding this dependency " + "will create a dependency loop:\n" + " //:includer ->\n" + " //:cyclic ->\n" + " //:includer\n" + "Suggestion: Find the part of the dependency chain where there is no " + "#include and remove that dependency.\n" + "Suggestion: Add public_deps = [ \":cyclic\" ] to :includer (defined at " + "//BUILD.gn:1)\n", + run_suggest(*cyclic)); + + auto cyclic_circular_includes = create_target( + "cyclic_circular_includes", Target::STATIC_LIBRARY, [&](Target* t) { + t->public_deps().push_back(LabelTargetPair(includer.get())); + t->visibility().SetPublic(); + t->allow_circular_includes_from().insert(includer->label()); + }); + EXPECT_EQ( + "Warning: //:cyclic_circular_includes depends on //:includer, so adding " + "this " + "dependency will create a dependency loop:\n" + " //:includer ->\n" + " //:cyclic_circular_includes ->\n" + " //:includer\n" + "Suggestion: :cyclic_circular_includes (defined at //BUILD.gn:1) " + "declares " + "allow_circular_includes_from, which is bad style. Instead, you should " + "remove allow_circular_includes_from by doing the following:\n" + "source_set(\"cyclic_circular_includes_sources\") {\n" + " # All attributes from :cyclic_circular_includes except public_deps, " + "and any link options\n" + " # Note that some public_deps may need to be added back based on " + "#includes of headers.\n" + "}\n" + "\n" + "static_library(\"cyclic_circular_includes\") {\n" + " public_deps = [ \":cyclic_circular_includes_sources\" ]\n" + " # public_deps, and any link variables from :cyclic_circular_includes\n" + "}\n" + "Suggestion: Add public_deps = [ \":cyclic_circular_includes_sources\" ] " + "to " + ":includer " + "(defined at //BUILD.gn:1)\n", + run_suggest(*cyclic_circular_includes)); }