Fix StackOverflowError in bazel mod graph output
This change fixes an infinite recursion issue in TextOutputFormatter when the dependency graph contains cycles formed by merging different paths. It adds a parentStack to track visited nodes and detect cycles dynamically.
Fixes https://github.com/bazelbuild/bazel/issues/27839
Closes #27876.
PiperOrigin-RevId: 842137415
Change-Id: I131d3310b1fa939164379a50419f16ebb071ec55
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/TextOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/TextOutputFormatter.java
index a371b38..426a025 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/TextOutputFormatter.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/TextOutputFormatter.java
@@ -46,6 +46,7 @@
private DrawCharset drawCharset;
private Set<ModuleExtensionId> seenExtensions;
private StringBuilder str;
+ private Set<ModuleKey> visted;
@Override
public void output() {
@@ -56,6 +57,7 @@
}
isLastChildStack = new ArrayDeque<>();
seenExtensions = new HashSet<>();
+ visted = new HashSet<>();
str = new StringBuilder();
printModule(ModuleKey.ROOT, null, IsExpanded.TRUE, IsIndirect.FALSE, IsCycle.FALSE, 0);
this.printer.println(str);
@@ -147,74 +149,85 @@
int depth) {
printTreeDrawing(indirect, depth);
- ResultNode node = Objects.requireNonNull(result.get(key));
- if (key.equals(ModuleKey.ROOT)) {
- AugmentedModule rootModule = depGraph.get(ModuleKey.ROOT);
- Preconditions.checkNotNull(rootModule);
- str.append(
- String.format(
- "<root> (%s@%s)",
- rootModule.name(),
- rootModule.version().equals(Version.EMPTY) ? "_" : rootModule.version()));
- } else {
- str.append(key).append(" ");
- }
-
- int totalChildrenNum = node.getChildren().size();
-
- ImmutableSortedSet<ModuleExtensionId> extensionsUsed =
- extensionRepoImports.keySet().stream()
- .filter(e -> extensionRepoImports.get(e).inverse().containsKey(key))
- .collect(toImmutableSortedSet(ModuleExtensionId.LEXICOGRAPHIC_COMPARATOR));
- if (options.extensionInfo != ExtensionShow.HIDDEN) {
- totalChildrenNum += extensionsUsed.size();
- }
-
- if (cycle == IsCycle.TRUE) {
- str.append("(cycle) ");
- } else if (expanded == IsExpanded.FALSE) {
- str.append("(*) ");
- } else {
- if (node.isTarget()) {
- str.append("# ");
+ boolean added = visted.add(key);
+ try {
+ ResultNode node = Objects.requireNonNull(result.get(key));
+ if (key.equals(ModuleKey.ROOT)) {
+ AugmentedModule rootModule = depGraph.get(ModuleKey.ROOT);
+ Preconditions.checkNotNull(rootModule);
+ str.append(
+ String.format(
+ "<root> (%s@%s)",
+ rootModule.name(),
+ rootModule.version().equals(Version.EMPTY) ? "_" : rootModule.version()));
+ } else {
+ str.append(key).append(" ");
}
- }
- AugmentedModule module = Objects.requireNonNull(depGraph.get(key));
- if (!options.verbose && !module.isUsed()) {
- str.append("(unused) ");
- }
- // If the edge is indirect, the parent is not only unknown, but the node could have come
- // from multiple paths merged in the process, so we skip the resolution explanation.
- if (indirect == IsIndirect.FALSE && options.verbose && parent != null) {
- Explanation explanation = getExtraResolutionExplanation(key, parent);
- if (explanation != null) {
- str.append(explanation.toExplanationString(!module.isUsed()));
+
+ int totalChildrenNum = node.getChildren().size();
+
+ ImmutableSortedSet<ModuleExtensionId> extensionsUsed =
+ extensionRepoImports.keySet().stream()
+ .filter(e -> extensionRepoImports.get(e).inverse().containsKey(key))
+ .collect(toImmutableSortedSet(ModuleExtensionId.LEXICOGRAPHIC_COMPARATOR));
+ if (options.extensionInfo != ExtensionShow.HIDDEN) {
+ totalChildrenNum += extensionsUsed.size();
}
- }
- str.append("\n");
+ // If we've already seen this node in the current traversal path, treat it as a cycle
+ // even if the graph structure says otherwise (which can happen due to merged paths).
+ boolean isCycle = cycle == IsCycle.TRUE || !added;
- if (expanded == IsExpanded.FALSE) {
- return;
- }
+ if (isCycle) {
+ str.append("(cycle) ");
+ } else if (expanded == IsExpanded.FALSE) {
+ str.append("(*) ");
+ } else {
+ if (node.isTarget()) {
+ str.append("# ");
+ }
+ }
+ AugmentedModule module = Objects.requireNonNull(depGraph.get(key));
+ if (!options.verbose && !module.isUsed()) {
+ str.append("(unused) ");
+ }
+ // If the edge is indirect, the parent is not only unknown, but the node could have come
+ // from multiple paths merged in the process, so we skip the resolution explanation.
+ if (indirect == IsIndirect.FALSE && options.verbose && parent != null) {
+ Explanation explanation = getExtraResolutionExplanation(key, parent);
+ if (explanation != null) {
+ str.append(explanation.toExplanationString(!module.isUsed()));
+ }
+ }
- int currChild = 1;
- if (options.extensionInfo != ExtensionShow.HIDDEN) {
- for (ModuleExtensionId extensionId : extensionsUsed) {
- boolean unexpandedExtension = !seenExtensions.add(extensionId);
+ str.append("\n");
+
+ if (expanded == IsExpanded.FALSE || isCycle) {
+ return;
+ }
+
+ int currChild = 1;
+ if (options.extensionInfo != ExtensionShow.HIDDEN) {
+ for (ModuleExtensionId extensionId : extensionsUsed) {
+ boolean unexpandedExtension = !seenExtensions.add(extensionId);
+ isLastChildStack.push(currChild++ == totalChildrenNum);
+ printExtension(key, extensionId, unexpandedExtension, depth + 1);
+ isLastChildStack.pop();
+ }
+ }
+ for (Entry<ModuleKey, NodeMetadata> e : node.getChildrenSortedByEdgeType()) {
+ ModuleKey childKey = e.getKey();
+ IsExpanded childExpanded = e.getValue().isExpanded();
+ IsIndirect childIndirect = e.getValue().isIndirect();
+ IsCycle childCycles = e.getValue().isCycle();
isLastChildStack.push(currChild++ == totalChildrenNum);
- printExtension(key, extensionId, unexpandedExtension, depth + 1);
+ printModule(childKey, key, childExpanded, childIndirect, childCycles, depth + 1);
isLastChildStack.pop();
}
- }
- for (Entry<ModuleKey, NodeMetadata> e : node.getChildrenSortedByEdgeType()) {
- ModuleKey childKey = e.getKey();
- IsExpanded childExpanded = e.getValue().isExpanded();
- IsIndirect childIndirect = e.getValue().isIndirect();
- IsCycle childCycles = e.getValue().isCycle();
- isLastChildStack.push(currChild++ == totalChildrenNum);
- printModule(childKey, key, childExpanded, childIndirect, childCycles, depth + 1);
- isLastChildStack.pop();
+ } finally {
+ if (added) {
+ visted.remove(key);
+ }
}
}
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/ModExecutorTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/ModExecutorTest.java
index da8c175..5a7d16d 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/ModExecutorTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/modcommand/ModExecutorTest.java
@@ -811,6 +811,15 @@
Optional.empty());
}
+ private ModuleExtensionId createExtensionId(
+ String moduleName, String version, String path, String extensionName)
+ throws LabelSyntaxException {
+ return ModuleExtensionId.create(
+ Label.parseCanonical("@@" + moduleName + "+" + version + "//" + path + ":" + path),
+ extensionName,
+ Optional.empty());
+ }
+
@Test
public void testModCommandPath_complexGraphFiltersCorrectly() throws ParseException, IOException {
// <root> -> A -> B -> C -> D
@@ -1077,4 +1086,114 @@
"<root> (main@1.0)", "└───$@@//extensions:extensions%maven ", " └───repo1", "")
.inOrder();
}
+
+ @Test
+ public void testGraphWithExtensionFilterAndCycle() throws Exception {
+ // <root> -> A -> B -> A (cycle)
+ // A and B both use extension defined in A.
+ ImmutableMap<ModuleKey, AugmentedModule> depGraph =
+ new ImmutableMap.Builder<ModuleKey, AugmentedModule>()
+ .put(
+ buildAugmentedModule(ModuleKey.ROOT, "main", Version.parse("1.0"), true)
+ .addDep("A", "1.0")
+ .addDep("B", "1.0")
+ .buildEntry())
+ .put(
+ buildAugmentedModule("A", "1.0")
+ .addStillDependant(ModuleKey.ROOT)
+ .addStillDependant("B", "1.0")
+ .addDep("B", "1.0")
+ .buildEntry())
+ .put(
+ buildAugmentedModule("B", "1.0")
+ .addStillDependant(ModuleKey.ROOT)
+ .addStillDependant("A", "1.0")
+ .addDep("A", "1.0")
+ .buildEntry())
+ .buildOrThrow();
+
+ ModuleExtensionId extensionId = createExtensionId("A", "1.0", "extensions", "ext");
+ ImmutableTable<ModuleExtensionId, ModuleKey, ModuleExtensionUsage> extensionUsages =
+ new ImmutableTable.Builder<ModuleExtensionId, ModuleKey, ModuleExtensionUsage>()
+ .put(
+ extensionId,
+ createModuleKey("A", "1.0"),
+ ModuleExtensionUsage.builder()
+ .setExtensionBzlFile("//extensions:extensions.bzl")
+ .setExtensionName("ext")
+ .setRepoOverrides(ImmutableMap.of())
+ .addProxy(
+ ModuleExtensionUsage.Proxy.builder()
+ .setLocation(Location.fromFileLineColumn("MODULE.bazel", 1, 1))
+ .setImports(ImmutableBiMap.of("repo1", "repo1"))
+ .setDevDependency(false)
+ .setContainingModuleFilePath(LabelConstants.MODULE_DOT_BAZEL_FILE_NAME)
+ .build())
+ .build())
+ .put(
+ extensionId,
+ createModuleKey("B", "1.0"),
+ ModuleExtensionUsage.builder()
+ .setExtensionBzlFile("//extensions:extensions.bzl")
+ .setExtensionName("ext")
+ .setRepoOverrides(ImmutableMap.of())
+ .addProxy(
+ ModuleExtensionUsage.Proxy.builder()
+ .setLocation(Location.fromFileLineColumn("MODULE.bazel", 1, 1))
+ .setImports(ImmutableBiMap.of("repo2", "repo2"))
+ .setDevDependency(false)
+ .setContainingModuleFilePath(LabelConstants.MODULE_DOT_BAZEL_FILE_NAME)
+ .build())
+ .build())
+ .buildOrThrow();
+
+ ImmutableSetMultimap<ModuleExtensionId, String> extensionRepos =
+ new ImmutableSetMultimap.Builder<ModuleExtensionId, String>()
+ .putAll(extensionId, ImmutableSet.of("repo1", "repo2"))
+ .build();
+
+ ModOptions options = ModOptions.getDefaultOptions();
+ options.outputFormat = OutputFormat.TEXT;
+ options.extensionInfo = ExtensionShow.ALL;
+ options.cycles = true;
+
+ File file = File.createTempFile("output_text_cycle_ext", "txt");
+ file.deleteOnExit();
+ try (Writer writer = new OutputStreamWriter(new FileOutputStream(file), UTF_8)) {
+ ModExecutor executor =
+ new ModExecutor(
+ depGraph,
+ extensionUsages,
+ extensionRepos,
+ Optional.of(MaybeCompleteSet.copyOf(ImmutableSet.of(extensionId))),
+ options,
+ writer);
+ executor.graph(ImmutableSet.of(ModuleKey.ROOT));
+ }
+
+ List<String> textOutput = Files.readAllLines(file.toPath());
+ assertThat(textOutput)
+ .containsExactly(
+ "<root> (main@1.0)",
+ "├───A@1.0 # ",
+ "│ ├───$@@A+1.0//extensions:extensions%ext ",
+ "│ │ └───repo1",
+ "│ ├───B@1.0 (cycle) ",
+ "│ └───B@1.0 # ",
+ "│ ├───$@@A+1.0//extensions:extensions%ext ... ",
+ "│ │ └───repo2",
+ "│ ├───A@1.0 (cycle) ",
+ "│ └───A@1.0 (cycle) ",
+ "└───B@1.0 # ",
+ " ├───$@@A+1.0//extensions:extensions%ext ... ",
+ " │ └───repo2",
+ " ├───A@1.0 (cycle) ",
+ " └───A@1.0 # ",
+ " ├───$@@A+1.0//extensions:extensions%ext ... ",
+ " │ └───repo1",
+ " ├───B@1.0 (cycle) ",
+ " └───B@1.0 (cycle) ",
+ "")
+ .inOrder();
+ }
}
