Inference Bug related to parametric polymorphism unification

[John Napier]

Hey Maurizio,

My apologies; you’re right that the example doesn’t compile against 8 - in
my attempts to shrink the code that I have failing locally to the minimal
test case, I apparently lost something essential in the translation.

In the interest of avoiding further confusion, here is the full,
complicated example that compiles against 1.8 but fails to compile without
explicit type ascriptions in both 11 and 12:

    public static class Example {

        public static <A, B> Iterable<B> map(Function<? super A, ? extends
B> fn, Iterable<A> as) {
            throw new UnsupportedOperationException();
        }

        public static <A> Iterable<A> flatten(Iterable<Iterable<A>> aas) {
            throw new UnsupportedOperationException();
        }

        public static <A, B> B foldLeft(BiFunction<? super B, ? super A, ?
extends B> fn, B b, Iterable<A> as) {
            throw new UnsupportedOperationException();
        }

        public static <A, B, C> C destructure(BiFunction<? super A, ? super
B, ? extends C> fn,
                                              Map.Entry<A, B> entry) {
            throw new UnsupportedOperationException();
        }

        public static <A, B, C> Function<Map.Entry<A, B>, C> destructure(
            BiFunction<? super A, ? super B, ? extends C> fn) {
            throw new UnsupportedOperationException();
        }

        public static <K, V> Function<V, Map.Entry<K, V>> pair(K fn) {
            throw new UnsupportedOperationException();
        }

        public static final class Sink {

            public Sink add(String k, String v) {
                throw new UnsupportedOperationException();
            }
        }

        public static void main(String[] args) {
            Map<String, List<String>> headers = Collections.emptyMap();

            // type-checks in 8, fails in 11/12
            foldLeft((acc, h) -> destructure(acc::add, h),
                     new Sink(),
                     flatten(map(destructure((name, values) ->
map(pair(name), values)), headers.entrySet())));
        }
    }

Again, so sorry for the confusion.

Same question as before: should *that* code continue to compile, or is it
correct that it fails to compile in 11 / 12?

Cheers,
John

On Jun 10, 2019, at 6:33 AM, Maurizio Cimadamore <
maurizio.cimadamore at oracle.com> wrote:

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/104e9484/attachment.html>