Fix bug in GraphOutputWriter#partitionedFactored which caused queue to grow to O(E), and now upper-bounding it to O(N).
RELNOTES: None.
PiperOrigin-RevId: 605164658
Change-Id: I3f0bb10ebc72d7aa2a8b36a331753db4b396927d
diff --git a/src/main/java/com/google/devtools/build/lib/query2/query/output/GraphOutputWriter.java b/src/main/java/com/google/devtools/build/lib/query2/query/output/GraphOutputWriter.java
index ca6fe2c..b75e67d 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/query/output/GraphOutputWriter.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/query/output/GraphOutputWriter.java
@@ -283,6 +283,7 @@
// already belongs to one.
HashMap<Node<T>, Set<Node<T>>> eqClasses = new HashMap<>();
ArrayDeque<Node<T>> queue = new ArrayDeque<>(graph.getRoots());
+ Set<Node<T>> enqueued = new HashSet<>(graph.getRoots());
// Top-level nodes need to be compared amongst each other because they can form an equivalence
// class amongst themselves too.
@@ -292,7 +293,13 @@
Node<T> node = queue.removeFirst();
List<Node<T>> successors = new ArrayList<>(node.getSuccessors());
processSuccessors(successors, eqClasses, equivalenceRelation);
- queue.addAll(node.getSuccessors());
+ for (Node<T> child : node.getSuccessors()) {
+ // We don't want the queue to grow to O(E); also, there is no need to visit children twice.
+ if (!enqueued.contains(child)) {
+ queue.add(child);
+ enqueued.add(child);
+ }
+ }
}
return eqClasses.values().stream().distinct().collect(toImmutableList());
