Choosing the best inference leaf is non-deterministic

[B. Blaser]

I created the following JBS issue for that:

https://bugs.openjdk.java.net/browse/JDK-8189683

Cheers,
Bernard


On 10 October 2017 at 22:43, B. Blaser <bsrbnd at gmail.com> wrote:
> 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--