Choosing the best inference leaf is non-deterministic

[B. Blaser]

On 10 October 2017 at 11:45, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
>
>
> On 10/10/17 10:26, B. Blaser wrote:
>>
>> This is stable enough until we find a failing example;-)
>>
>> If you run twice the second example given in [1], you'll see that the
>> nodes aren't always solved in the same order...
>>
>> While there isn't any problem in this case, this non-deterministic
>> behavior is definitively unsafe, which is probably due to the fact
>> that the default 'hashCode()' might depend on the reference (memory
>> location), see [3].
>>
>> The 'TreeSet' I suggested yesterday isn't probably a good solution
>> neither as it uses the comparison method defined to compute the
>> acyclic graph.
>>
>> So, something derived from 'LinkedHashMap' would be better to preserve
>> the insertion order and to access the elements in O(1). Or, at least,
>> overriding 'hashCode()' with something more stable while not
>> preserving the insertion order (a sequential index assigned to each
>> node when the inference graph is created, for example).
>>
>> What do you think?
>
> I think we need to understand the source of non-determinism. If that is
> simply caused by nodes not having stable equals and hashcode, we might as
> well add those methods, and make the problem go away w/o any extra memory
> cost. Iteration order could still be non-deterministic in multi-threaded
> scenario, but that's not a concern with this part of javac.
>
> Or, we could look into a more robust data structure - typically
> LinkedHashSet is used in such cases, which is probably more robust longer
> term.

I think 'LinkedHashSet' is exactly what we need here, as next.

Thanks!
Bernard

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.LinkedHashSet;
 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;
+                LinkedHashSet<Node> deps;

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

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


> Or we could do both :-)
>
> Maurizio
>
>>
>> Bernard
>>
>> [3]
>> https://docs.oracle.com/javase/9/docs/api/java/lang/Object.html#hashCode--