changeset 2234:2059cf03d755

8019942: Graph inference: avoid redundant computation during bound incorporation
author mcimadamore
date Thu, 04 Jul 2013 16:39:45 +0100
parents 373e8f198908
children 1b91796976f6
files src/share/classes/com/sun/tools/javac/code/Type.java src/share/classes/com/sun/tools/javac/comp/Infer.java test/tools/javac/generics/inference/8019824/T8019824.out
diffstat 3 files changed, 161 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/com/sun/tools/javac/code/Type.java	Wed Jul 03 17:37:14 2013 +0100
+++ b/src/share/classes/com/sun/tools/javac/code/Type.java	Thu Jul 04 16:39:45 2013 +0100
@@ -1379,7 +1379,7 @@
         }
         
         public void addBound(InferenceBound ib, Type bound, Types types, boolean update) {
-            Type bound2 = boundMap.apply(bound);
+            Type bound2 = toTypeVarMap.apply(bound);
             List<Type> prevBounds = bounds.get(ib);
             for (Type b : prevBounds) {
                 //check for redundancy - use strict version of isSameType on tvars
@@ -1390,12 +1390,12 @@
             notifyChange(EnumSet.of(ib));
         }
         //where
-            Type.Mapping boundMap = new Mapping("toTypeVarMap") {
+            Type.Mapping toTypeVarMap = new Mapping("toTypeVarMap") {
                 @Override
                 public Type apply(Type t) {
                     if (t.hasTag(UNDETVAR)) {
                         UndetVar uv = (UndetVar)t;
-                        return uv.inst != null ? uv.inst : uv.qtype;
+                        return uv.qtype;
                     } else {
                         return t.map(this);
                     }
--- a/src/share/classes/com/sun/tools/javac/comp/Infer.java	Wed Jul 03 17:37:14 2013 +0100
+++ b/src/share/classes/com/sun/tools/javac/comp/Infer.java	Thu Jul 04 16:39:45 2013 +0100
@@ -459,9 +459,10 @@
         }
         finally {
             mlistener.detach();
-            if (mlistener.rounds == MAX_INCORPORATION_STEPS) {
+            if (incorporationCache.size() == MAX_INCORPORATION_STEPS) {
                 inferenceContext.rollback(saved_undet);
             }
+            incorporationCache.clear();
         }
     }
     //where
@@ -472,8 +473,7 @@
          * left in a clean state.
          */
         class MultiUndetVarListener implements UndetVar.UndetVarListener {
-
-            int rounds;
+            
             boolean changed;
             List<Type> undetvars;
 
@@ -487,13 +487,12 @@
 
             public void varChanged(UndetVar uv, Set<InferenceBound> ibs) {
                 //avoid non-termination
-                if (rounds < MAX_INCORPORATION_STEPS) {
+                if (incorporationCache.size() < MAX_INCORPORATION_STEPS) {
                     changed = true;
                 }
             }
 
             void reset() {
-                rounds++;
                 changed = false;
             }
 
@@ -526,17 +525,17 @@
                 if (uv.inst != null) {
                     Type inst = uv.inst;
                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {
-                        if (!infer.types.isSubtypeUnchecked(inst, inferenceContext.asFree(u), warn)) {
+                        if (!isSubtype(inst, inferenceContext.asFree(u), warn, infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.UPPER);
                         }
                     }
                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {
-                        if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), inst, warn)) {
+                        if (!isSubtype(inferenceContext.asFree(l), inst, warn, infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.LOWER);
                         }
                     }
                     for (Type e : uv.getBounds(InferenceBound.EQ)) {
-                        if (!infer.types.isSameType(inst, inferenceContext.asFree(e))) {
+                        if (!isSameType(inst, inferenceContext.asFree(e), infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.EQ);
                         }
                     }
@@ -559,19 +558,19 @@
                 Type eq = null;
                 for (Type e : uv.getBounds(InferenceBound.EQ)) {
                     Assert.check(!inferenceContext.free(e));
-                    if (eq != null && !infer.types.isSameType(e, eq)) {
+                    if (eq != null && !isSameType(e, eq, infer)) {
                         infer.reportBoundError(uv, BoundErrorKind.EQ);
                     }
                     eq = e;
                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {
                         Assert.check(!inferenceContext.free(l));
-                        if (!infer.types.isSubtypeUnchecked(l, e, warn)) {
+                        if (!isSubtype(l, e, warn, infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
                         }
                     }
                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {
                         if (inferenceContext.free(u)) continue;
-                        if (!infer.types.isSubtypeUnchecked(e, u, warn)) {
+                        if (!isSubtype(e, u, warn, infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
                         }
                     }
@@ -587,12 +586,12 @@
                 for (Type e : uv.getBounds(InferenceBound.EQ)) {
                     if (e.containsAny(inferenceContext.inferenceVars())) continue;
                     for (Type u : uv.getBounds(InferenceBound.UPPER)) {
-                        if (!infer.types.isSubtypeUnchecked(e, inferenceContext.asFree(u), warn)) {
+                        if (!isSubtype(e, inferenceContext.asFree(u), warn, infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
                         }
                     }
                     for (Type l : uv.getBounds(InferenceBound.LOWER)) {
-                        if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), e, warn)) {
+                        if (!isSubtype(inferenceContext.asFree(l), e, warn, infer)) {
                             infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
                         }
                     }
@@ -608,7 +607,7 @@
                 Infer infer = inferenceContext.infer();
                 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
                     for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
-                        infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
+                        isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn , infer);
                     }
                 }
             }
@@ -622,7 +621,7 @@
                 Infer infer = inferenceContext.infer();
                 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
                     for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
-                        infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
+                        isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn, infer);
                     }
                 }
             }
@@ -636,7 +635,7 @@
                 Infer infer = inferenceContext.infer();
                 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
                     for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
-                        infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
+                        isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn, infer);
                     }
                 }
             }
@@ -651,7 +650,7 @@
                 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
                     for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
                         if (b1 != b2) {
-                            infer.types.isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
+                            isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1), infer);
                         }
                     }
                 }
@@ -670,14 +669,14 @@
                         if (uv2.isCaptured()) continue;
                         //alpha <: beta
                         //0. set beta :> alpha
-                        uv2.addBound(InferenceBound.LOWER, uv, infer.types);
+                        addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer);
                         //1. copy alpha's lower to beta's
                         for (Type l : uv.getBounds(InferenceBound.LOWER)) {
-                            uv2.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);
+                            addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(l), infer);
                         }
                         //2. copy beta's upper to alpha's
                         for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
-                            uv.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);
+                            addBound(InferenceBound.UPPER, uv, inferenceContext.asInstType(u), infer);
                         }
                     }
                 }
@@ -696,14 +695,14 @@
                         if (uv2.isCaptured()) continue;
                         //alpha :> beta
                         //0. set beta <: alpha
-                        uv2.addBound(InferenceBound.UPPER, uv, infer.types);
+                        addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer);
                         //1. copy alpha's upper to beta's
                         for (Type u : uv.getBounds(InferenceBound.UPPER)) {
-                            uv2.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);
+                            addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(u), infer);
                         }
                         //2. copy beta's lower to alpha's
                         for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
-                            uv.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);
+                            addBound(InferenceBound.LOWER, uv, inferenceContext.asInstType(l), infer);
                         }
                     }
                 }
@@ -722,12 +721,12 @@
                         if (uv2.isCaptured()) continue;
                         //alpha == beta
                         //0. set beta == alpha
-                        uv2.addBound(InferenceBound.EQ, uv, infer.types);
+                        addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer);
                         //1. copy all alpha's bounds to beta's
                         for (InferenceBound ib : InferenceBound.values()) {
                             for (Type b2 : uv.getBounds(ib)) {
-                                if (b2 != uv2) {
-                                    uv2.addBound(ib, inferenceContext.asInstType(b2), infer.types);
+                                if (b2 != uv2) {                                    
+                                    addBound(ib, uv2, inferenceContext.asInstType(b2), infer);
                                 }
                             }
                         }
@@ -735,7 +734,7 @@
                         for (InferenceBound ib : InferenceBound.values()) {
                             for (Type b2 : uv2.getBounds(ib)) {
                                 if (b2 != uv) {
-                                    uv.addBound(ib, inferenceContext.asInstType(b2), infer.types);
+                                    addBound(ib, uv, inferenceContext.asInstType(b2), infer);
                                 }
                             }
                         }
@@ -749,6 +748,41 @@
         boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
             return !uv.isCaptured();
         }
+        
+        boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
+            return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
+        }
+        
+        boolean isSameType(Type s, Type t, Infer infer) {
+            return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
+        }
+        
+        void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
+            doIncorporationOp(opFor(ib), uv, b, null, infer);
+        }
+        
+        IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
+            switch (boundKind) {
+                case EQ:
+                    return IncorporationBinaryOpKind.ADD_EQ_BOUND;
+                case LOWER:
+                    return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
+                case UPPER:
+                    return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
+                default:
+                    Assert.error("Can't get here!");
+                    return null;
+            }
+        }
+        
+        boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
+            IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
+            Boolean res = infer.incorporationCache.get(newOp);
+            if (res == null) {
+                infer.incorporationCache.put(newOp, res = newOp.apply(warn));
+            }
+            return res;
+        }
     }
 
     /** incorporation steps to be executed when running in legacy mode */
@@ -757,6 +791,102 @@
     /** incorporation steps to be executed when running in graph mode */
     EnumSet<IncorporationStep> incorporationStepsGraph =
             EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
+    
+    /**
+     * Three kinds of basic operation are supported as part of an incorporation step:
+     * (i) subtype check, (ii) same type check and (iii) bound addition (either
+     * upper/lower/eq bound).
+     */
+    enum IncorporationBinaryOpKind {
+        IS_SUBTYPE() {
+            @Override
+            boolean apply(Type op1, Type op2, Warner warn, Types types) {
+                return types.isSubtypeUnchecked(op1, op2, warn);
+            }
+        },
+        IS_SAME_TYPE() {
+            @Override
+            boolean apply(Type op1, Type op2, Warner warn, Types types) {
+                return types.isSameType(op1, op2);
+            }
+        },
+        ADD_UPPER_BOUND() {
+            @Override
+            boolean apply(Type op1, Type op2, Warner warn, Types types) {
+                UndetVar uv = (UndetVar)op1;
+                uv.addBound(InferenceBound.UPPER, op2, types);
+                return true;
+            }
+        },
+        ADD_LOWER_BOUND() {
+            @Override
+            boolean apply(Type op1, Type op2, Warner warn, Types types) {
+                UndetVar uv = (UndetVar)op1;
+                uv.addBound(InferenceBound.LOWER, op2, types);
+                return true;
+            }
+        },
+        ADD_EQ_BOUND() {
+            @Override
+            boolean apply(Type op1, Type op2, Warner warn, Types types) {
+                UndetVar uv = (UndetVar)op1;
+                uv.addBound(InferenceBound.EQ, op2, types);
+                return true;
+            }
+        };
+
+        abstract boolean apply(Type op1, Type op2, Warner warn, Types types);
+    }
+    
+    /**
+     * This class encapsulates a basic incorporation operation; incorporation
+     * operations takes two type operands and a kind. Each operation performed
+     * during an incorporation round is stored in a cache, so that operations
+     * are not executed unnecessarily (which would potentially lead to adding
+     * same bounds over and over).
+     */
+    class IncorporationBinaryOp {
+        
+        IncorporationBinaryOpKind opKind;
+        Type op1;
+        Type op2;
+
+        IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
+            this.opKind = opKind;
+            this.op1 = op1;
+            this.op2 = op2;            
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (!(o instanceof IncorporationBinaryOp)) {
+                return false;
+            } else {
+                IncorporationBinaryOp that = (IncorporationBinaryOp)o;
+                return opKind == that.opKind &&
+                        types.isSameType(op1, that.op1, true) &&
+                        types.isSameType(op2, that.op2, true);
+            }
+        }
+
+        @Override
+        public int hashCode() {
+            int result = opKind.hashCode();
+            result *= 127;
+            result += types.hashCode(op1);
+            result *= 127;
+            result += types.hashCode(op2);
+            return result;
+        }
+        
+        boolean apply(Warner warn) {
+            return opKind.apply(op1, op2, warn, types);
+        }
+    }
+    
+    /** an incorporation cache keeps track of all executed incorporation-related operations */
+    Map<IncorporationBinaryOp, Boolean> incorporationCache =
+            new HashMap<IncorporationBinaryOp, Boolean>();
 
     /**
      * Make sure that the upper bounds we got so far lead to a solvable inference
--- a/test/tools/javac/generics/inference/8019824/T8019824.out	Wed Jul 03 17:37:14 2013 +0100
+++ b/test/tools/javac/generics/inference/8019824/T8019824.out	Thu Jul 04 16:39:45 2013 +0100
@@ -1,2 +1,2 @@
-T8019824.java:9:25: compiler.err.cant.apply.symbol: kindname.method, make, java.lang.Class<C>, java.lang.Class<compiler.misc.type.captureof: 1, ? extends T8019824.Foo<?,?>>, kindname.class, T8019824, (compiler.misc.incompatible.eq.upper.bounds: C, compiler.misc.type.captureof: 1, ? extends T8019824.Foo<?,?>, T8019824.Foo<java.lang.Object,B>)
+T8019824.java:9:25: compiler.err.cant.apply.symbol: kindname.method, make, java.lang.Class<C>, java.lang.Class<compiler.misc.type.captureof: 1, ? extends T8019824.Foo<?,?>>, kindname.class, T8019824, (compiler.misc.incompatible.eq.upper.bounds: C, compiler.misc.type.captureof: 1, ? extends T8019824.Foo<?,?>, T8019824.Foo<compiler.misc.type.captureof: 2, ?,B>)
 1 error