changeset 51177:ef7c4c77d9fa

8178150: Regression in logic for handling inference stuck constraints Summary: Fix broken logic for input/output inference variable dependency Reviewed-by: vromero, bsrbnd
author mcimadamore
date Thu, 14 Jun 2018 11:13:39 +0100
parents 1372f66e0a17
children 69e82329ad01
files src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java test/langtools/tools/javac/generics/inference/8178150/T8178150.java
diffstat 3 files changed, 127 insertions(+), 14 deletions(-) [+]
line wrap: on
line diff
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java	Thu Jun 14 11:13:30 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java	Thu Jun 14 11:13:39 2018 +0100
@@ -31,6 +31,7 @@
 import com.sun.tools.javac.code.Type.StructuralTypeMapping;
 import com.sun.tools.javac.code.Types.TypeMapping;
 import com.sun.tools.javac.comp.ArgumentAttr.LocalCacheContext;
+import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph;
 import com.sun.tools.javac.comp.Resolve.ResolveError;
 import com.sun.tools.javac.resources.CompilerProperties.Fragments;
 import com.sun.tools.javac.tree.*;
@@ -663,28 +664,57 @@
         }
 
         /**
-         * Pick the deferred node to be unstuck. The chosen node is the first strongly connected
-         * component containing exactly one node found in the dependency graph induced by deferred nodes.
-         * If no such component is found, the first deferred node is returned.
+         * Pick the deferred node to be unstuck. First, deferred nodes are organized into a graph
+         * (see {@code DeferredAttrContext.buildStuckGraph()}, where a node N1 depends on another node N2
+         * if its input variable depends (as per the inference graph) on the output variables of N2
+         * (see {@code DeferredAttrContext.canInfluence()}.
+         *
+         * Then, the chosen deferred node is the first strongly connected component containing exactly
+         * one node found in such a graph. If no such component is found, the first deferred node is chosen.
          */
         DeferredAttrNode pickDeferredNode() {
+            List<StuckNode> stuckGraph = buildStuckGraph();
+            //compute tarjan on the stuck graph
+            List<? extends StuckNode> csn = GraphUtils.tarjan(stuckGraph).get(0);
+            return csn.length() == 1 ? csn.get(0).data : deferredAttrNodes.get(0);
+        }
+
+        List<StuckNode> buildStuckGraph() {
+            //first, build inference graph
+            infer.doIncorporation(inferenceContext, warn);
+            InferenceGraph graph = infer.new GraphSolver(inferenceContext, types.noWarnings)
+                    .new InferenceGraph();
+            //then, build stuck graph
             List<StuckNode> nodes = deferredAttrNodes.stream()
                     .map(StuckNode::new)
                     .collect(List.collector());
             //init stuck expression graph; a deferred node A depends on a deferred node B iff
-            //the intersection between A's input variable and B's output variable is non-empty.
+            //B's output variables can influence A's input variables.
             for (StuckNode sn1 : nodes) {
-                for (Type t : sn1.data.deferredStuckPolicy.stuckVars()) {
-                    for (StuckNode sn2 : nodes) {
-                        if (sn1 != sn2 && sn2.data.deferredStuckPolicy.depVars().contains(t)) {
-                            sn1.deps.add(sn2);
-                        }
+                for (StuckNode sn2 : nodes) {
+                    if (sn1 != sn2 && canInfluence(graph, sn2, sn1)) {
+                        sn1.deps.add(sn2);
                     }
                 }
             }
-            //compute tarjan on the stuck graph
-            List<? extends StuckNode> csn = GraphUtils.tarjan(nodes).get(0);
-            return csn.length() == 1 ? csn.get(0).data : deferredAttrNodes.get(0);
+            return nodes;
+        }
+
+        boolean canInfluence(InferenceGraph graph, StuckNode sn1, StuckNode sn2) {
+            Set<Type> outputVars = sn1.data.deferredStuckPolicy.depVars();
+            for (Type inputVar : sn2.data.deferredStuckPolicy.stuckVars()) {
+                InferenceGraph.Node inputNode = graph.findNode(inputVar);
+                //already solved stuck vars do not appear in the graph
+                if (inputNode != null) {
+                    Set<InferenceGraph.Node> inputClosure = inputNode.closure();
+                    if (outputVars.stream()
+                            .map(graph::findNode)
+                            .anyMatch(inputClosure::contains)) {
+                        return true;
+                    }
+                }
+            }
+            return false;
         }
 
         class StuckNode extends GraphUtils.TarjanNode<DeferredAttrNode, StuckNode> {
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java	Thu Jun 14 11:13:30 2018 +0200
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java	Thu Jun 14 11:13:39 2018 +0100
@@ -61,6 +61,7 @@
 import java.util.EnumSet;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.Map;
 import java.util.Optional;
 import java.util.Properties;
@@ -1706,7 +1707,7 @@
 
                 Node(Type ivar) {
                     super(ListBuffer.of(ivar));
-                    this.deps = new HashSet<>();
+                    this.deps = new LinkedHashSet<>();
                 }
 
                 @Override
@@ -1751,6 +1752,24 @@
                 }
 
                 /**
+                 * Compute closure of a give node, by recursively walking
+                 * through all its dependencies.
+                 */
+                protected Set<Node> closure() {
+                    Set<Node> closure = new HashSet<>();
+                    closureInternal(closure);
+                    return closure;
+                }
+
+                private void closureInternal(Set<Node> closure) {
+                    if (closure.add(this)) {
+                        for (Node n : deps) {
+                            n.closureInternal(closure);
+                        }
+                    }
+                }
+
+                /**
                  * Is this node a leaf? This means either the node has no dependencies,
                  * or it just has self-dependencies.
                  */
@@ -1777,7 +1796,7 @@
                         addDependencies(n.deps);
                     }
                     //update deps
-                    Set<Node> deps2 = new HashSet<>();
+                    Set<Node> deps2 = new LinkedHashSet<>();
                     for (Node d : deps) {
                         if (data.contains(d.data.first())) {
                             deps2.add(this);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/langtools/tools/javac/generics/inference/8178150/T8178150.java	Thu Jun 14 11:13:39 2018 +0100
@@ -0,0 +1,64 @@
+/*
+ * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8178150
+ * @summary Regression in logic for handling inference stuck constraints
+ * @compile T8178150.java
+ */
+
+import java.util.*;
+import java.util.function.*;
+import java.util.logging.*;
+
+class T8178150 {
+
+    public static void test(List<List<String>> testList, Logger LOGGER) {
+        testList.forEach(T8178150.bind(cast(LOGGER::info), iterable -> ""));
+        testList.forEach(T8178150.bind_transitive(cast_transitive(LOGGER::info), iterable -> ""));
+    }
+
+    private static <T1, T2> TestProcedure<T1, T2> bind(Consumer<T2> delegate, Function<? super T1, T2> function) {
+        return null;
+    }
+
+    private static <C> Consumer<C> cast(Consumer<C> consumer) {
+        return consumer;
+    }
+
+    private static <T1, T2, U extends T2> TestProcedure<T1, T2> bind_transitive(Consumer<U> delegate, Function<? super T1, T2> function) {
+        return null;
+    }
+
+    private static <C> C cast_transitive(C consumer) {
+        return consumer;
+    }
+
+    private static final class TestProcedure<X1, X2> implements Consumer<X1> {
+        @Override
+        public void accept(final X1 t1) { }
+    }
+}