Inference Bug related to parametric polymorphism unification

[Maurizio Cimadamore]

On 15/06/2019 22:55, John Napier wrote:
> I definitely think that your suggestions (or “musings" if suggestions 
> is too strong a word) for choosing the most deeply nested expression 
> as the unification reference would be an improvement over the current 
> situation from a user's perspective, provided it doesn’t lead to a 
> dramatically slower compilation time.
Hi John,

I think that, in this case performances should not be a problem, as it's 
mostly matter to sort constraints by position/depth, which should be 
doable.

What I'm afraid of, is that for each example such an analysis might help 
in getting 'right', there can possibly another where such an analysis 
would 'block' types from being propagated from the LHS and lead to dual 
inference failure modes.

I'll leave this to Dan - the overall feeling I get on this topic is that 
the dependency analysis we have in JLS is great in terms of deciding 
which variables to solve first when we know we have to solve _all_ 
variables in a dependency graph. The problem is that we try to 'reuse' 
this same dependency info, decorate it with extra info about 
directionality of expressions/constraints (e.g. a lambda that takes a X 
and produces a R, means that there's a new dependency in that R depends 
on X). While this work in most cases, the fact that the underlying 
dependency analysis is brittle (e.g. in X <: List<Y> we only conclude 
that X depends on Y, but not viceversa), means that we can 'miss' 
dependencies between expressions when multiple functional expressions 
are 'stuck'.

This can be summarized with this simple example (if I didn't do any odd 
mistakes):

import java.util.function.*;
import java.util.*;

class Test {
   static <X, Y extends List<R>, R, W>  void m(Function<X, Y> a1, 
Function<R, W> a2) {
   }

   static <X, Y extends List<R>, R, W>  void m_inv(Function<R, W> a2, 
Function<X, Y> a1) {
   }


   static void test() {
      m(x -> (List<String>)null, s -> s.length());
      m_inv(s -> s.length(), x -> (List<String>)null);
   }
}


The two invocations are clearly identical (well, symmetric) - m_inv 
declared formals in opposite order than those of m. Yet, testing on JDK 
13, the first invocation passes, while the second fails, with a similar 
error as the one in your example.

In a way, I think that the fact that Y depends on R (as per JLS 
dependency analysis) should be treated as 'less important' compared to 
the fact that one of the two lambdas affects the input variables of the 
other, indirectly, via Y. But I don't think there's an easy way to tweak 
the spec, w/o coming up with a brand new dependency analysis for 
handling stuck expressions. Which might push the cost. vs. benefit ratio 
out of the acceptable limit.

Cheers
Maurizio