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(); + } }