src/java.base/share/classes/jdk/internal/module/ModuleHashesBuilder.java

8200134: Improve ModuleHashesBuilder
Reviewed-by: mchung, alanb

*** 33,43 ****
  import java.util.ArrayDeque;
  import java.util.Collections;
  import java.util.Deque;
  import java.util.HashMap;
  import java.util.HashSet;
- import java.util.LinkedList;
  import java.util.Map;
  import java.util.Set;
  import java.util.function.Consumer;
  import java.util.function.Function;
  import java.util.stream.Stream;
--- 33,42 ----
*** 74,93 ****
       */
      public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
          // build a graph containing the packaged modules and
          // its transitive dependences matching --hash-modules
          Graph.Builder<String> builder = new Graph.Builder<>();
!         Deque<ResolvedModule> deque = new ArrayDeque<>(configuration.modules());
          Set<ResolvedModule> visited = new HashSet<>();
!         while (!deque.isEmpty()) {
!             ResolvedModule rm = deque.pop();
!             if (!visited.contains(rm)) {
!                 visited.add(rm);
                  builder.addNode(rm.name());
                  for (ResolvedModule dm : rm.reads()) {
                      if (!visited.contains(dm)) {
!                         deque.push(dm);
                      }
                      builder.addEdge(rm.name(), dm.name());
                  }
              }
          }
--- 73,91 ----
       */
      public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
          // build a graph containing the packaged modules and
          // its transitive dependences matching --hash-modules
          Graph.Builder<String> builder = new Graph.Builder<>();
!         Deque<ResolvedModule> todo = new ArrayDeque<>(configuration.modules());
          Set<ResolvedModule> visited = new HashSet<>();
!         ResolvedModule rm;
!         while ((rm = todo.poll()) != null) {
!             if (visited.add(rm)) {
                  builder.addNode(rm.name());
                  for (ResolvedModule dm : rm.reads()) {
                      if (!visited.contains(dm)) {
!                         todo.push(dm);
                      }
                      builder.addEdge(rm.name(), dm.name());
                  }
              }
          }
*** 210,230 ****
  
          /**
           * Returns all nodes reachable from the given set of roots.
           */
          public Set<T> dfs(Set<T> roots) {
!             Deque<T> deque = new LinkedList<>(roots);
              Set<T> visited = new HashSet<>();
!             while (!deque.isEmpty()) {
!                 T u = deque.pop();
!                 if (!visited.contains(u)) {
!                     visited.add(u);
!                     if (contains(u)) {
                          adjacentNodes(u).stream()
                              .filter(v -> !visited.contains(v))
!                             .forEach(deque::push);
!                     }
                  }
              }
              return visited;
          }
  
--- 208,225 ----
  
          /**
           * Returns all nodes reachable from the given set of roots.
           */
          public Set<T> dfs(Set<T> roots) {
!             ArrayDeque<T> todo = new ArrayDeque<>(roots);
              Set<T> visited = new HashSet<>();
!             T u;
!             while ((u = todo.poll()) != null) {
!                 if (visited.add(u) && contains(u)) {
                      adjacentNodes(u).stream()
                          .filter(v -> !visited.contains(v))
!                         .forEach(todo::push);
                  }
              }
              return visited;
          }
  
*** 238,253 ****
          static class Builder<T> {
              final Set<T> nodes = new HashSet<>();
              final Map<T, Set<T>> edges = new HashMap<>();
  
              public void addNode(T node) {
!                 if (nodes.contains(node)) {
!                     return;
!                 }
!                 nodes.add(node);
                  edges.computeIfAbsent(node, _e -> new HashSet<>());
              }
  
              public void addEdge(T u, T v) {
                  addNode(u);
                  addNode(v);
                  edges.get(u).add(v);
--- 233,246 ----
          static class Builder<T> {
              final Set<T> nodes = new HashSet<>();
              final Map<T, Set<T>> edges = new HashMap<>();
  
              public void addNode(T node) {
!                 if (nodes.add(node)) {
                      edges.computeIfAbsent(node, _e -> new HashSet<>());
                  }
+             }
  
              public void addEdge(T u, T v) {
                  addNode(u);
                  addNode(v);
                  edges.get(u).add(v);
*** 261,310 ****
  
      /**
       * Topological sort
       */
      private static class TopoSorter<T> {
!         final Deque<T> result = new LinkedList<>();
!         final Deque<T> nodes;
          final Graph<T> graph;
  
          TopoSorter(Graph<T> graph) {
              this.graph = graph;
-             this.nodes = new LinkedList<>(graph.nodes);
              sort();
          }
  
          public void ordered(Consumer<T> action) {
!             result.iterator().forEachRemaining(action);
          }
  
          public void reverse(Consumer<T> action) {
              result.descendingIterator().forEachRemaining(action);
          }
  
          private void sort() {
!             Deque<T> visited = new LinkedList<>();
!             Deque<T> done = new LinkedList<>();
!             T node;
!             while ((node = nodes.poll()) != null) {
!                 if (!visited.contains(node)) {
!                     visit(node, visited, done);
!                 }
              }
          }
  
!         private void visit(T node, Deque<T> visited, Deque<T> done) {
!             if (visited.contains(node)) {
!                 if (!done.contains(node)) {
!                     throw new IllegalArgumentException("Cyclic detected: " +
!                         node + " " + graph.edges().get(node));
                  }
!                 return;
              }
-             visited.add(node);
-             graph.edges().get(node)
-                 .forEach(x -> visit(x, visited, done));
-             done.add(node);
-             result.addLast(node);
          }
      }
  }
--- 254,298 ----
  
      /**
       * Topological sort
       */
      private static class TopoSorter<T> {
!         final Deque<T> result = new ArrayDeque<>();
          final Graph<T> graph;
  
          TopoSorter(Graph<T> graph) {
              this.graph = graph;
              sort();
          }
  
          public void ordered(Consumer<T> action) {
!             result.forEach(action);
          }
  
          public void reverse(Consumer<T> action) {
              result.descendingIterator().forEachRemaining(action);
          }
  
          private void sort() {
!             Set<T> visited = new HashSet<>();
!             Deque<T> stack = new ArrayDeque<>();
!             graph.nodes.forEach(node -> visit(node, visited, stack));
          }
+ 
+         private Set<T> children(T node) {
+             return graph.edges().get(node);
          }
  
!         private void visit(T node, Set<T> visited, Deque<T> stack) {
!             if (visited.add(node)) {
!                 stack.push(node);
!                 children(node).forEach(child -> visit(child, visited, stack));
!                 stack.pop();
!                 result.addLast(node);
              }
!             else if (stack.contains(node)) {
!                 throw new IllegalArgumentException(
!                     "Cycle detected: " + node + " -> " + children(node));
              }
          }
      }
  }