Complexity reduction when choosing the best inference leaf to be solved

[B. Blaser]

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