Inference Bug related to parametric polymorphism unification

[Maurizio Cimadamore]

Hi John
I've been trying to reproduce, but for me the example fails even in 8...

That said, I agree that there could be something fishy here; I did some 
experiments with variations of your example, and it looks like javac can 
undrestand what the typing of `destructure(Pair::new, entry)` is, in 
isolation - you can see that by adding this statement:

Object o = (String)destructure(Pair::new, entry);

This will trigger this error:

error: incompatible types: Pair<String,String> cannot be converted to String
Object o = (String)destructure(Pair::new, entry);

Which seems to confirm that javac is indeed capable of inferring A and B 
to String and take it from there.

My suspicion is that when you nest these expressions inside each other, 
you create a 'bigger' inference context, where two expressions cannot be 
evaluated (we call them 'stuck'):

* Pair::new (indirect method reference)
* (x, y) -> x + y (implicit lambda)

To break this tie, the compiler has to choose which inference variable 
to instantiate first: the outer { A, B }, or the innermost ones? This 
choice is, at its core, driven by the spec 18.5.2 (see [1]). In your 
example we have these inference variables:

* A#inner, B#inner and C#inner (from innermost invocation of 'destructure')
* A#outer, B#outer and C#outer (from outermost invocation of 'destructure')

This analysis is based on the concept of input/output inference variable 
- in this case:

* A#inner,B#inner influence C#inner
* A#outer,B#outer influence C#outer

So far, if we had to choose between these two constraints, the choice 
would be non-deterministic (as the two input/output constraints are 
mirroring each other). But there's another dependency here:

* C#inner <: Entry<A#outer, B#outer>

Now, from a programmer perspective, looking at the way the code is 
written, it's clear we'd like solution of C#inner to influence A#outer, 
B#outer. But I don't think that's the way the spec works. In this case 
the spec says that C#inner 'depends' on A#outer, C#outer.

So we really have no way

That's because the result of the innermost call to 'destructure' is 
passed to the outermost call, so the inferred type for C#inner can 
affect the inferred Entry<A#outer, B#outer>.

So, we are basically left with what I think is an non-deterministic 
choice between eagerly resolving { A#inner, B#inner } or { A#outer, 
B#outer }. Unfortunately, picking the former makes the code pass, 
whereas picking the latter makes compilation fail (because at that time 
we don't know any better than just instantiating A#outer and B#outer to 
Object).

If this is the issue, inference could to a better job, by either looking 
at presence of other 'more meaningful' bounds on {A#inner, B#inner} 
(although defining 'more meaningful might be problematic). Or it could 
just give precedence to innermost variables in case of a tie, which is a 
rule that I think programmers will find natural. Currently though, these 
'extensions' are not part of the JLS - so the behavior here is, 
essentially, unspecified.

At the same time, there's also an argument to be had as to whether the 
code here isn't inherently buggy - essentially, { A, B, C } in the 
'destructure' method are all independent variables so, in a way, the 
problem is *underconstrained* (e.g. there's no real objective choice for 
which variable to solve first, other than resorting to heuristics, whose 
mileage can vary).

Note that your second call works simply because, by adding the explicit 
type param on the method reference receiver, you make the method 
reference 'direct' meaning its type is evaluated *ahead* of the lambda. 
Basically you told the compiler which of the two 'stuck' expression 
should be solved first.

@Dan - is this something that has been discussed before in spec-land?

Cheers
Maurizio

[1] - 
https://docs.oracle.com/javase/specs/jls/se12/html/jls-18.html#jls-18.5.2.2

On 06/06/2019 20:31, John Napier wrote:
> Hi all,
>
> The following code compiles against oracle64-1.8.0.162 but fails on 
> both openjdk64-11.0.2 and oracle64-12.0.1:
>
> public static class Example {
>
>         public static class Pair<A, B> implements Map.Entry<A, B> {
>             private final A a;
>             private final B b;
>
>             public Pair(A a, B b) {
>                 this.a = a;
>                 this.b = b;
>             }
>
>             @Override
>             public A getKey() {
>                 return a;
>             }
>
>             @Override
>             public B getValue() {
>                 return b;
>             }
>
>             @Override
>             public B setValue(B value) {
>                 throw new UnsupportedOperationException();
>             }
>         }
>
>         public static <A, B, C> C destructure(BiFunction<A, B, C> fn, 
> Map.Entry<A, B> entry) {
>             return fn.apply(entry.getKey(), entry.getValue());
>         }
>
>         public static void main(String[] args) {
>             Map.Entry<String, String> entry = new Pair<>("foo", "bar");
>
>             // ill-typed
>             String inferred = destructure((x, y) -> x + y, 
> destructure(Pair::new, entry));
>
>             // well-typed
>             String ascribed = destructure((x, y) -> x + y, 
> destructure(Pair<String, String>::new, entry));
>         }
>     }
>
> Before submitting more bugs of this same ilk, albeit with slight 
> variations in occurrence, I must ask: this is not the intentional 
> modern behavior, correct? Inference should still work as illustrated 
> above, right?
>
> Cheers,
>
> -John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20190610/b6c598e7/attachment.html>