18.4: resolution order

[Rafkind, Jon]

Given these bounds, where lower case letters are inference variables:

=Problem=

a <: Object
b <: Object
ArrayList<b> <: a

section 18.4 does not seem to suggest that 'b' should be instantiated
before 'a', but that is the only possible way to come up with an
instantiation for 'a' with a lower bound of ArrayList<Object>, which is
needed later on in the process (not shown).

The dependencies are
b -> b
a -> a, b

Assuming we originally wanted to resolve 'a', we define V as

V = a + dependencies(a)
V = a, b

The subset of V, {a1..an}, seems to be a bit superflous because it is
simply the variables in V that are uninstantiated. But in any case we
can check that the stated property holds for each variable.

Let {a1..an} = V = {a, b}

a:
  depends on 'a', there is no instantiation of 'a' but the first element
of {a1..an} is 'a' so the property holds
  depends on 'b', there is no instantiation of 'b' but the second
element of {a1..an} is 'b' so the property holds
b:
  depends on 'b', there is no instantiation of 'b' but the second
element of {a1..an} is 'b' so the property holds

Now we try to instantiate {a, b}:

Ta = glb(Object) = Object
Tb = glb(Object) = Object

so we incorporate 'a = Object' and 'b = Object'. At this point we are
done because both 'a' and 'b' have instantiations.

=Solution=

If we choose the subset of V in a different way we can choose to
incorporate 'b' first, then 'a' in a proceeding step.

{a1..an} should be chosen such that for each ai, the following property
must hold for all dependencies of ai {B1..Bn}:
  either 1. Bi has an instantiation
  or       2. The dependencies of Bi contains ai

This works for variables that mutually depend on each other. Back to the
example, now we can build {a1..an} constructively using the above property:

Should 'a' be added to the set?

a:
  depends on 'a', property holds by 2
  depends on 'b', property does not hold by either 1 or 2

no, by virtue of the 'b' dependency not matching the required property.
Should 'b' be added to the set?

b:
  depends on 'b', property holds by 2

{a1..an} = {b}

=Test code=

Just to be complete this is the Java code I was testing with:

import java.util.Collection;
import java.util.List;
import java.util.ArrayList;
import java.util.function.Supplier;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;

public class Generics7{
    private static class Inner<T, A, R>{
        Inner(Supplier<A> supplier,
              BiConsumer<A, T> accumulator,
              BinaryOperator<A> combiner){

        }
    }

    public static <T> Inner<T, ?, List<T>> toList() {
        return new Inner<>(
                (Supplier<List<T>>) ArrayList::new,
                List::add,
                (left, right) -> { left.addAll(right); return left; });
    }
}