Complexity reduction when choosing the best inference leaf to be solved

[Vicente Romero]

On 10/18/2017 02:08 PM, Maurizio Cimadamore wrote:
> 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.

right that's one of the reasons I was thinking about a max flow 
algorithm, costs were over the table, but as you mentioned later that's 
probably overkill for this case and a simple graph visit should be enough

>
> Maurizio

Vicente

>
>
> 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
>