Complexity reduction when choosing the best inference leaf to be solved

[Maurizio Cimadamore]

For the records, the fix I'm working on is slightly more general than 
the one provided here - I think we have to take transitivity into 
account, it's not enough to look at the bounds of a given input variable 
and see if it contains any of the output vars. Consider this case:

alpha <: List<beta>
beta <: List<gamma>
gamma <: String

In this case you get three inference nodes, one for each inference var - 
and you have

Node(alpha) depends on Node(beta) depends on Node(gamma)

so, technically speaking, gamma can influence alpha, but gamma does not 
appear among alpha's bounds, even after incorporation.

I think in certain cases (like in the one described in the bug) 
incorporation copies some of the bounds from one var to another and that 
gives you the illusion of transitivity, but that doesn't always happen. 
See slightly tweaked example at the end of this email

So, unless I'm missing something, I think that for the can-influence 
relation we should piggy back to the inference graph dependencies.

Maurizio


class T8178150_transitive {

     public static void test(List<List<String>> testList, Logger LOGGER) {
         testList.forEach(T8178150.bind(cast(LOGGER::info), iterable -> 
""));
     }

     private static <T1, T2, U extends T2> TestProcedure<T1, T2> 
bind(Consumer<U> delegate, Function<? super T1, T2> function) {
         return null;
     }

     private static <C> C cast(C consumer) {
         return consumer;
     }

     private static final class TestProcedure<X1, X2> implements 
Consumer<X1> {
         @Override
         public void accept(final X1 t1) { }
     }
}


On 15/10/17 12:48, B. Blaser wrote:
> On 13 October 2017 at 21:59, Maurizio Cimadamore
> <maurizio.cimadamore at oracle.com> wrote:
>> Hi,
>> I think the affected area is close to this:
>>
>> https://bugs.openjdk.java.net/browse/JDK-8178150
> Quoting from your JBS comment, here are the two stuck expressions:
>
> * LOGGER::info - input vars = { C }, output vars = { }
> * iterable -> "" - input vars = { T1 }, output vars = { T2 }
>
> The problem here is that the input var 'C' is influenced by the output
> var 'T2' via the bound set of 'C' which doesn't seem to be currently
> implemented in javac.
>
> I wrote a fix, here under, that adds the corresponding dependencies
> before computing the acyclic stuck graph in
> 'DeferredAttr.pickDeferredNode()'.
>
> I tried this fix using the "lazy" leaf heuristic (the last one I
> suggested) that picks a node to be solved in O(log(n)).
>
> Note that this fix shouldn't interfere with any leaf solving heuristic
> so that it should be possible to choose the best one between:
> * the current one (with optimization?) that chooses the smallest subtree
> * the "lazy" one that minimizes the effort to choose a leaf in O(log(n))
> * the "conservative" one (from Vicente) that picks the nearest leaf
> * or any other heuristic like the "aggressive" one
>
> Does this fix look reasonable to you?
>
> Cheers,
> Bernard
>
>
> diff --git a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java
> b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java
> --- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java
> +++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java
> @@ -29,6 +29,8 @@
>   import com.sun.source.tree.NewClassTree;
>   import com.sun.tools.javac.code.*;
>   import com.sun.tools.javac.code.Type.StructuralTypeMapping;
> +import com.sun.tools.javac.code.Type.UndetVar;
> +import com.sun.tools.javac.code.Type.UndetVar.InferenceBound;
>   import com.sun.tools.javac.code.Types.TypeMapping;
>   import com.sun.tools.javac.comp.ArgumentAttr.LocalCacheContext;
>   import com.sun.tools.javac.comp.Resolve.ResolveError;
> @@ -668,10 +670,15 @@
>               //the intersection between A's input variable and B's
> output variable is non-empty.
>               for (StuckNode sn1 : nodes) {
>                   for (Type t : sn1.data.deferredStuckPolicy.stuckVars()) {
> +                    UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t);
>                       for (StuckNode sn2 : nodes) {
> -                        if (sn1 != sn2 &&
> sn2.data.deferredStuckPolicy.depVars().contains(t)) {
> +                        if (sn1 == sn2) continue;
> +
> +                        Set<Type> depVars =
> sn2.data.deferredStuckPolicy.depVars();
> +
> +                        if (depVars.contains(t) || Type.containsAny(
> +
> uv.getBounds(InferenceBound.values()), List.from(depVars)))
>                               sn1.deps.add(sn2);
> -                        }
>                       }
>                   }
>               }
>
>
>> for which I have a fix in the work which I will submit for review soon.
>>
>> After that fix is in, we can consider deeper refactorings in the area.
>>
>> Cheers
>> Maurizio