Complexity reduction when choosing the best inference leaf to be solved

[Maurizio Cimadamore]

Thanks - as I said I already have a fix for this - I will submit this soon.

Maurizio


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