Choosing the best inference leaf is non-deterministic

[B. Blaser]

Hi,

While working on [1], I noticed that choosing the best inference leaf
to be solved is non-deterministic because 'computeTreeToLeafs()'
iterates on the node dependencies [2] which are stored in an 'HashSet'
with unpredictable iteration order.

I think this is a bit dangerous and could lead to unreproducible
errors as the leaves' solving order within a subtree is unpredictable.
I suggest to use a 'TreeSet' instead with predictable iteration order
even if the operations are in O(log(n)) vs O(1) for the 'HashSet'.
This shouldn't make too much difference with a low average number of
dependencies per node.

What do you think?

Thanks,
Bernard

[1] http://mail.openjdk.java.net/pipermail/compiler-dev/2017-October/011156.html
[2] http://hg.openjdk.java.net/jdk10/master/file/6cb6ef406e97/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java#l1382


diff --git a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
@@ -59,6 +59,7 @@
 import java.util.EnumSet;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.TreeSet;
 import java.util.Map;
 import java.util.Optional;
 import java.util.Properties;
@@ -1705,11 +1706,11 @@
             class Node extends
GraphUtils.TarjanNode<ListBuffer<Type>, Node> implements
DottableNode<ListBuffer<Type>, Node> {

                 /** node dependencies */
-                Set<Node> deps;
+                TreeSet<Node> deps;

                 Node(Type ivar) {
                     super(ListBuffer.of(ivar));
-                    this.deps = new HashSet<>();
+                    this.deps = new TreeSet<>();
                 }

                 @Override
@@ -1780,7 +1781,7 @@
                         addDependencies(n.deps);
                     }
                     //update deps
-                    Set<Node> deps2 = new HashSet<>();
+                    TreeSet<Node> deps2 = new TreeSet<>();
                     for (Node d : deps) {
                         if (data.contains(d.data.first())) {
                             deps2.add(this);