Choosing the best inference leaf is non-deterministic

[Maurizio Cimadamore]

Sure - we had other issues in this vein - determinism trumps every other 
possible use case in this area; dependencies should be stored in a data 
structure that preserves insertion order.

That said, since the algorithm for creating an inference graph is 
deterministic - and we end up adding same elements in same order - while 
I buy that the iteration order of the dependencies will not reflect the 
insertion order, shouldn't it at least be stable?

But then, I note that InferenceGraph.Node doesn't override 
equals/hashcode, so that's definitively a possible cause for 
non-determinism - if default Object.hash changes, items will be inserted 
in the set in different ways, leading to different iteration orders.

Maurizio


On 09/10/17 22:37, B. Blaser wrote:
> 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);