Mon, 03 Jun 2013 17:09:26 -0700
8006615: [doclint] move remaining messages into resource bundle
Reviewed-by: mcimadamore, vromero
duke@1 | 1 | /* |
mcimadamore@1562 | 2 | * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved. |
duke@1 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@1 | 4 | * |
duke@1 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@1 | 6 | * under the terms of the GNU General Public License version 2 only, as |
ohair@554 | 7 | * published by the Free Software Foundation. Oracle designates this |
duke@1 | 8 | * particular file as subject to the "Classpath" exception as provided |
ohair@554 | 9 | * by Oracle in the LICENSE file that accompanied this code. |
duke@1 | 10 | * |
duke@1 | 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@1 | 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@1 | 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@1 | 14 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@1 | 15 | * accompanied this code). |
duke@1 | 16 | * |
duke@1 | 17 | * You should have received a copy of the GNU General Public License version |
duke@1 | 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@1 | 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@1 | 20 | * |
ohair@554 | 21 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
ohair@554 | 22 | * or visit www.oracle.com if you need additional information or have any |
ohair@554 | 23 | * questions. |
duke@1 | 24 | */ |
duke@1 | 25 | |
duke@1 | 26 | package com.sun.tools.javac.comp; |
duke@1 | 27 | |
mcimadamore@674 | 28 | import com.sun.tools.javac.tree.JCTree; |
mcimadamore@674 | 29 | import com.sun.tools.javac.tree.JCTree.JCTypeCast; |
mcimadamore@820 | 30 | import com.sun.tools.javac.tree.TreeInfo; |
duke@1 | 31 | import com.sun.tools.javac.util.*; |
mcimadamore@1562 | 32 | import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition; |
duke@1 | 33 | import com.sun.tools.javac.util.List; |
mcimadamore@1562 | 34 | import com.sun.tools.javac.code.*; |
mcimadamore@1562 | 35 | import com.sun.tools.javac.code.Type.*; |
mcimadamore@1562 | 36 | import com.sun.tools.javac.code.Type.UndetVar.InferenceBound; |
mcimadamore@1562 | 37 | import com.sun.tools.javac.code.Symbol.*; |
mcimadamore@1562 | 38 | import com.sun.tools.javac.comp.DeferredAttr.AttrMode; |
mcimadamore@1562 | 39 | import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph; |
mcimadamore@1562 | 40 | import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node; |
mcimadamore@1562 | 41 | import com.sun.tools.javac.comp.Resolve.InapplicableMethodException; |
mcimadamore@1562 | 42 | import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode; |
duke@1 | 43 | |
mcimadamore@1337 | 44 | import java.util.HashMap; |
mcimadamore@1337 | 45 | import java.util.Map; |
mcimadamore@1562 | 46 | import java.util.Set; |
mcimadamore@1562 | 47 | |
mcimadamore@1562 | 48 | import java.util.ArrayList; |
mcimadamore@1562 | 49 | import java.util.Collections; |
mcimadamore@1562 | 50 | import java.util.EnumSet; |
mcimadamore@1562 | 51 | import java.util.HashSet; |
mcimadamore@1337 | 52 | |
jjg@1374 | 53 | import static com.sun.tools.javac.code.TypeTag.*; |
duke@1 | 54 | |
duke@1 | 55 | /** Helper class for type parameter inference, used by the attribution phase. |
duke@1 | 56 | * |
jjg@581 | 57 | * <p><b>This is NOT part of any supported API. |
jjg@581 | 58 | * If you write code that depends on this, you do so at your own risk. |
duke@1 | 59 | * This code and its internal interfaces are subject to change or |
duke@1 | 60 | * deletion without notice.</b> |
duke@1 | 61 | */ |
duke@1 | 62 | public class Infer { |
duke@1 | 63 | protected static final Context.Key<Infer> inferKey = |
duke@1 | 64 | new Context.Key<Infer>(); |
duke@1 | 65 | |
mcimadamore@1562 | 66 | Resolve rs; |
mcimadamore@1562 | 67 | Check chk; |
duke@1 | 68 | Symtab syms; |
duke@1 | 69 | Types types; |
mcimadamore@1562 | 70 | JCDiagnostic.Factory diags; |
mcimadamore@1114 | 71 | Log log; |
duke@1 | 72 | |
mcimadamore@1562 | 73 | /** should the graph solver be used? */ |
mcimadamore@1562 | 74 | boolean allowGraphInference; |
mcimadamore@1510 | 75 | |
duke@1 | 76 | public static Infer instance(Context context) { |
duke@1 | 77 | Infer instance = context.get(inferKey); |
duke@1 | 78 | if (instance == null) |
duke@1 | 79 | instance = new Infer(context); |
duke@1 | 80 | return instance; |
duke@1 | 81 | } |
duke@1 | 82 | |
duke@1 | 83 | protected Infer(Context context) { |
duke@1 | 84 | context.put(inferKey, this); |
mcimadamore@1562 | 85 | |
mcimadamore@1562 | 86 | rs = Resolve.instance(context); |
mcimadamore@1562 | 87 | chk = Check.instance(context); |
duke@1 | 88 | syms = Symtab.instance(context); |
duke@1 | 89 | types = Types.instance(context); |
mcimadamore@1562 | 90 | diags = JCDiagnostic.Factory.instance(context); |
mcimadamore@1114 | 91 | log = Log.instance(context); |
mcimadamore@1298 | 92 | inferenceException = new InferenceException(diags); |
mcimadamore@1562 | 93 | Options options = Options.instance(context); |
mcimadamore@1562 | 94 | allowGraphInference = Source.instance(context).allowGraphInference() |
mcimadamore@1562 | 95 | && options.isUnset("useLegacyInference"); |
duke@1 | 96 | } |
duke@1 | 97 | |
mcimadamore@1562 | 98 | /** A value for prototypes that admit any type, including polymorphic ones. */ |
mcimadamore@1562 | 99 | public static final Type anyPoly = new Type(NONE, null); |
mcimadamore@1562 | 100 | |
mcimadamore@1337 | 101 | /** |
mcimadamore@1337 | 102 | * This exception class is design to store a list of diagnostics corresponding |
mcimadamore@1337 | 103 | * to inference errors that can arise during a method applicability check. |
mcimadamore@1337 | 104 | */ |
mcimadamore@1186 | 105 | public static class InferenceException extends InapplicableMethodException { |
duke@1 | 106 | private static final long serialVersionUID = 0; |
duke@1 | 107 | |
mcimadamore@1337 | 108 | List<JCDiagnostic> messages = List.nil(); |
mcimadamore@1337 | 109 | |
mcimadamore@299 | 110 | InferenceException(JCDiagnostic.Factory diags) { |
mcimadamore@689 | 111 | super(diags); |
duke@1 | 112 | } |
mcimadamore@1337 | 113 | |
mcimadamore@1337 | 114 | @Override |
mcimadamore@1337 | 115 | InapplicableMethodException setMessage(JCDiagnostic diag) { |
mcimadamore@1337 | 116 | messages = messages.append(diag); |
mcimadamore@1337 | 117 | return this; |
mcimadamore@1337 | 118 | } |
mcimadamore@1337 | 119 | |
mcimadamore@1337 | 120 | @Override |
mcimadamore@1337 | 121 | public JCDiagnostic getDiagnostic() { |
mcimadamore@1337 | 122 | return messages.head; |
mcimadamore@1337 | 123 | } |
mcimadamore@1337 | 124 | |
mcimadamore@1337 | 125 | void clear() { |
mcimadamore@1337 | 126 | messages = List.nil(); |
mcimadamore@1337 | 127 | } |
mcimadamore@299 | 128 | } |
mcimadamore@299 | 129 | |
mcimadamore@1562 | 130 | protected final InferenceException inferenceException; |
duke@1 | 131 | |
mcimadamore@1562 | 132 | // <editor-fold defaultstate="collapsed" desc="Inference routines"> |
mcimadamore@1337 | 133 | /** |
mcimadamore@1562 | 134 | * Main inference entry point - instantiate a generic method type |
mcimadamore@1562 | 135 | * using given argument types and (possibly) an expected target-type. |
duke@1 | 136 | */ |
mcimadamore@1268 | 137 | public Type instantiateMethod(Env<AttrContext> env, |
mcimadamore@547 | 138 | List<Type> tvars, |
duke@1 | 139 | MethodType mt, |
mcimadamore@1268 | 140 | Attr.ResultInfo resultInfo, |
mcimadamore@1268 | 141 | Symbol msym, |
mcimadamore@1268 | 142 | List<Type> argtypes, |
mcimadamore@1268 | 143 | boolean allowBoxing, |
mcimadamore@1268 | 144 | boolean useVarargs, |
mcimadamore@1347 | 145 | Resolve.MethodResolutionContext resolveContext, |
mcimadamore@1268 | 146 | Warner warn) throws InferenceException { |
duke@1 | 147 | //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG |
mcimadamore@1550 | 148 | final InferenceContext inferenceContext = new InferenceContext(tvars); |
mcimadamore@1337 | 149 | inferenceException.clear(); |
mcimadamore@1562 | 150 | try { |
mcimadamore@1562 | 151 | DeferredAttr.DeferredAttrContext deferredAttrContext = |
mcimadamore@1562 | 152 | resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn); |
mcimadamore@689 | 153 | |
mcimadamore@1674 | 154 | resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, |
mcimadamore@1562 | 155 | argtypes, mt.getParameterTypes(), warn); |
mcimadamore@1479 | 156 | |
mcimadamore@1562 | 157 | if (allowGraphInference && |
mcimadamore@1562 | 158 | resultInfo != null && |
mcimadamore@1510 | 159 | !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { |
mcimadamore@1562 | 160 | //inject return constraints earlier |
mcimadamore@1562 | 161 | checkWithinBounds(inferenceContext, warn); //propagation |
mcimadamore@1562 | 162 | generateReturnConstraints(resultInfo, mt, inferenceContext); |
mcimadamore@1562 | 163 | //propagate outwards if needed |
mcimadamore@1562 | 164 | if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) { |
mcimadamore@1562 | 165 | //propagate inference context outwards and exit |
mcimadamore@1562 | 166 | inferenceContext.dupTo(resultInfo.checkContext.inferenceContext()); |
mcimadamore@1562 | 167 | deferredAttrContext.complete(); |
mcimadamore@1562 | 168 | return mt; |
mcimadamore@1562 | 169 | } |
mcimadamore@1510 | 170 | } |
mcimadamore@1510 | 171 | |
mcimadamore@1479 | 172 | deferredAttrContext.complete(); |
duke@1 | 173 | |
mcimadamore@1337 | 174 | // minimize as yet undetermined type variables |
mcimadamore@1562 | 175 | if (allowGraphInference) { |
mcimadamore@1562 | 176 | inferenceContext.solve(warn); |
mcimadamore@1562 | 177 | } else { |
mcimadamore@1562 | 178 | inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst |
mcimadamore@1337 | 179 | } |
duke@1 | 180 | |
mcimadamore@1550 | 181 | mt = (MethodType)inferenceContext.asInstType(mt); |
mcimadamore@396 | 182 | |
mcimadamore@1562 | 183 | if (!allowGraphInference && |
mcimadamore@1562 | 184 | inferenceContext.restvars().nonEmpty() && |
mcimadamore@1562 | 185 | resultInfo != null && |
mcimadamore@1562 | 186 | !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { |
mcimadamore@1562 | 187 | generateReturnConstraints(resultInfo, mt, inferenceContext); |
mcimadamore@1562 | 188 | inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst |
mcimadamore@1562 | 189 | mt = (MethodType)inferenceContext.asInstType(mt); |
mcimadamore@1562 | 190 | } |
duke@1 | 191 | |
mcimadamore@1562 | 192 | if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) { |
mcimadamore@1562 | 193 | log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt); |
mcimadamore@1337 | 194 | } |
duke@1 | 195 | |
mcimadamore@1337 | 196 | // return instantiated version of method type |
mcimadamore@1337 | 197 | return mt; |
mcimadamore@1337 | 198 | } finally { |
mcimadamore@1562 | 199 | if (resultInfo != null || !allowGraphInference) { |
mcimadamore@1562 | 200 | inferenceContext.notifyChange(); |
mcimadamore@1562 | 201 | } else { |
mcimadamore@1562 | 202 | inferenceContext.notifyChange(inferenceContext.boundedVars()); |
mcimadamore@1338 | 203 | } |
duke@1 | 204 | } |
mcimadamore@895 | 205 | } |
duke@1 | 206 | |
mcimadamore@1562 | 207 | /** |
mcimadamore@1562 | 208 | * Generate constraints from the generic method's return type. If the method |
mcimadamore@1562 | 209 | * call occurs in a context where a type T is expected, use the expected |
mcimadamore@1562 | 210 | * type to derive more constraints on the generic method inference variables. |
mcimadamore@1562 | 211 | */ |
mcimadamore@1562 | 212 | void generateReturnConstraints(Attr.ResultInfo resultInfo, |
mcimadamore@1562 | 213 | MethodType mt, InferenceContext inferenceContext) { |
mcimadamore@1562 | 214 | Type qtype1 = inferenceContext.asFree(mt.getReturnType()); |
mcimadamore@1562 | 215 | Type to = returnConstraintTarget(qtype1, resultInfo.pt); |
mcimadamore@1562 | 216 | Assert.check(allowGraphInference || !resultInfo.checkContext.inferenceContext().free(to), |
mcimadamore@1562 | 217 | "legacy inference engine cannot handle constraints on both sides of a subtyping assertion"); |
mcimadamore@1562 | 218 | //we need to skip capture? |
mcimadamore@1562 | 219 | Warner retWarn = new Warner(); |
mcimadamore@1562 | 220 | if (!resultInfo.checkContext.compatible(qtype1, resultInfo.checkContext.inferenceContext().asFree(to), retWarn) || |
mcimadamore@1562 | 221 | //unchecked conversion is not allowed |
mcimadamore@1562 | 222 | retWarn.hasLint(Lint.LintCategory.UNCHECKED)) { |
mcimadamore@1562 | 223 | throw inferenceException |
mcimadamore@1562 | 224 | .setMessage("infer.no.conforming.instance.exists", |
mcimadamore@1562 | 225 | inferenceContext.restvars(), mt.getReturnType(), to); |
mcimadamore@1562 | 226 | } |
mcimadamore@1562 | 227 | } |
mcimadamore@1562 | 228 | //where |
mcimadamore@1562 | 229 | private Type returnConstraintTarget(Type from, Type to) { |
mcimadamore@1562 | 230 | if (from.hasTag(VOID)) { |
mcimadamore@1562 | 231 | return syms.voidType; |
mcimadamore@1562 | 232 | } else if (to.hasTag(NONE)) { |
mcimadamore@1562 | 233 | return from.isPrimitive() ? from : syms.objectType; |
mcimadamore@1562 | 234 | } else if (from.hasTag(UNDETVAR) && to.isPrimitive()) { |
mcimadamore@1562 | 235 | if (!allowGraphInference) { |
mcimadamore@1562 | 236 | //if legacy, just return boxed type |
mcimadamore@1562 | 237 | return types.boxedClass(to).type; |
mcimadamore@1562 | 238 | } |
mcimadamore@1562 | 239 | //if graph inference we need to skip conflicting boxed bounds... |
mcimadamore@1562 | 240 | UndetVar uv = (UndetVar)from; |
mcimadamore@1562 | 241 | for (Type t : uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { |
mcimadamore@1562 | 242 | Type boundAsPrimitive = types.unboxedType(t); |
mcimadamore@1562 | 243 | if (boundAsPrimitive == null) continue; |
mcimadamore@1562 | 244 | if (types.isConvertible(boundAsPrimitive, to)) { |
mcimadamore@1562 | 245 | //effectively skip return-type constraint generation (compatibility) |
mcimadamore@1562 | 246 | return syms.objectType; |
mcimadamore@1562 | 247 | } |
mcimadamore@1562 | 248 | } |
mcimadamore@1562 | 249 | return types.boxedClass(to).type; |
mcimadamore@1562 | 250 | } else { |
mcimadamore@1562 | 251 | return to; |
mcimadamore@1251 | 252 | } |
duke@1 | 253 | } |
mcimadamore@1251 | 254 | |
mcimadamore@1562 | 255 | /** |
mcimadamore@1562 | 256 | * Infer cyclic inference variables as described in 15.12.2.8. |
mcimadamore@1562 | 257 | */ |
mcimadamore@1562 | 258 | private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) { |
mcimadamore@1562 | 259 | ListBuffer<Type> todo = ListBuffer.lb(); |
mcimadamore@1562 | 260 | //step 1 - create fresh tvars |
mcimadamore@1562 | 261 | for (Type t : vars) { |
mcimadamore@1562 | 262 | UndetVar uv = (UndetVar)inferenceContext.asFree(t); |
mcimadamore@1562 | 263 | List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER); |
mcimadamore@1562 | 264 | if (Type.containsAny(upperBounds, vars)) { |
jfranck@1689 | 265 | TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner); |
mcimadamore@1562 | 266 | fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null); |
mcimadamore@1562 | 267 | todo.append(uv); |
mcimadamore@1562 | 268 | uv.inst = fresh_tvar.type; |
mcimadamore@1562 | 269 | } else if (upperBounds.nonEmpty()) { |
mcimadamore@1562 | 270 | uv.inst = types.glb(upperBounds); |
mcimadamore@1562 | 271 | } else { |
mcimadamore@1562 | 272 | uv.inst = syms.objectType; |
mcimadamore@1338 | 273 | } |
mcimadamore@1562 | 274 | } |
mcimadamore@1562 | 275 | //step 2 - replace fresh tvars in their bounds |
mcimadamore@1562 | 276 | List<Type> formals = vars; |
mcimadamore@1562 | 277 | for (Type t : todo) { |
mcimadamore@1562 | 278 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 279 | TypeVar ct = (TypeVar)uv.inst; |
mcimadamore@1562 | 280 | ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct))); |
mcimadamore@1562 | 281 | if (ct.bound.isErroneous()) { |
mcimadamore@1562 | 282 | //report inference error if glb fails |
mcimadamore@1562 | 283 | reportBoundError(uv, BoundErrorKind.BAD_UPPER); |
mcimadamore@1338 | 284 | } |
mcimadamore@1562 | 285 | formals = formals.tail; |
mcimadamore@1348 | 286 | } |
mcimadamore@1348 | 287 | } |
mcimadamore@1348 | 288 | |
mcimadamore@674 | 289 | /** |
mcimadamore@674 | 290 | * Compute a synthetic method type corresponding to the requested polymorphic |
mcimadamore@820 | 291 | * method signature. The target return type is computed from the immediately |
mcimadamore@820 | 292 | * enclosing scope surrounding the polymorphic-signature call. |
mcimadamore@674 | 293 | */ |
mcimadamore@1239 | 294 | Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env, |
mcimadamore@674 | 295 | MethodSymbol spMethod, // sig. poly. method or null if none |
mcimadamore@1347 | 296 | Resolve.MethodResolutionContext resolveContext, |
mcimadamore@820 | 297 | List<Type> argtypes) { |
mcimadamore@674 | 298 | final Type restype; |
mcimadamore@716 | 299 | |
mcimadamore@820 | 300 | //The return type for a polymorphic signature call is computed from |
mcimadamore@820 | 301 | //the enclosing tree E, as follows: if E is a cast, then use the |
mcimadamore@820 | 302 | //target type of the cast expression as a return type; if E is an |
mcimadamore@820 | 303 | //expression statement, the return type is 'void' - otherwise the |
mcimadamore@820 | 304 | //return type is simply 'Object'. A correctness check ensures that |
mcimadamore@820 | 305 | //env.next refers to the lexically enclosing environment in which |
mcimadamore@820 | 306 | //the polymorphic signature call environment is nested. |
mcimadamore@820 | 307 | |
mcimadamore@820 | 308 | switch (env.next.tree.getTag()) { |
jjg@1127 | 309 | case TYPECAST: |
mcimadamore@820 | 310 | JCTypeCast castTree = (JCTypeCast)env.next.tree; |
mcimadamore@820 | 311 | restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ? |
mcimadamore@820 | 312 | castTree.clazz.type : |
mcimadamore@820 | 313 | syms.objectType; |
mcimadamore@820 | 314 | break; |
jjg@1127 | 315 | case EXEC: |
mcimadamore@820 | 316 | JCTree.JCExpressionStatement execTree = |
mcimadamore@820 | 317 | (JCTree.JCExpressionStatement)env.next.tree; |
mcimadamore@820 | 318 | restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ? |
mcimadamore@820 | 319 | syms.voidType : |
mcimadamore@820 | 320 | syms.objectType; |
mcimadamore@820 | 321 | break; |
mcimadamore@820 | 322 | default: |
mcimadamore@820 | 323 | restype = syms.objectType; |
mcimadamore@674 | 324 | } |
mcimadamore@674 | 325 | |
mcimadamore@1347 | 326 | List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step)); |
mcimadamore@674 | 327 | List<Type> exType = spMethod != null ? |
mcimadamore@674 | 328 | spMethod.getThrownTypes() : |
mcimadamore@674 | 329 | List.of(syms.throwableType); // make it throw all exceptions |
mcimadamore@674 | 330 | |
mcimadamore@674 | 331 | MethodType mtype = new MethodType(paramtypes, |
mcimadamore@674 | 332 | restype, |
mcimadamore@674 | 333 | exType, |
mcimadamore@674 | 334 | syms.methodClass); |
mcimadamore@674 | 335 | return mtype; |
mcimadamore@674 | 336 | } |
mcimadamore@674 | 337 | //where |
mcimadamore@1347 | 338 | class ImplicitArgType extends DeferredAttr.DeferredTypeMap { |
mcimadamore@1347 | 339 | |
mcimadamore@1347 | 340 | public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) { |
mcimadamore@1562 | 341 | rs.deferredAttr.super(AttrMode.SPECULATIVE, msym, phase); |
mcimadamore@1347 | 342 | } |
mcimadamore@1347 | 343 | |
mcimadamore@1347 | 344 | public Type apply(Type t) { |
mcimadamore@1347 | 345 | t = types.erasure(super.apply(t)); |
jjg@1374 | 346 | if (t.hasTag(BOT)) |
mcimadamore@1347 | 347 | // nulls type as the marker type Null (which has no instances) |
mcimadamore@1347 | 348 | // infer as java.lang.Void for now |
mcimadamore@1347 | 349 | t = types.boxedClass(syms.voidType).type; |
mcimadamore@1347 | 350 | return t; |
mcimadamore@1347 | 351 | } |
mcimadamore@1347 | 352 | } |
mcimadamore@1337 | 353 | |
mcimadamore@1337 | 354 | /** |
mcimadamore@1562 | 355 | * This method is used to infer a suitable target SAM in case the original |
mcimadamore@1562 | 356 | * SAM type contains one or more wildcards. An inference process is applied |
mcimadamore@1562 | 357 | * so that wildcard bounds, as well as explicit lambda/method ref parameters |
mcimadamore@1562 | 358 | * (where applicable) are used to constraint the solution. |
mcimadamore@1562 | 359 | */ |
mcimadamore@1562 | 360 | public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface, |
mcimadamore@1562 | 361 | List<Type> paramTypes, Check.CheckContext checkContext) { |
mcimadamore@1562 | 362 | if (types.capture(funcInterface) == funcInterface) { |
mcimadamore@1562 | 363 | //if capture doesn't change the type then return the target unchanged |
mcimadamore@1562 | 364 | //(this means the target contains no wildcards!) |
mcimadamore@1562 | 365 | return funcInterface; |
mcimadamore@1562 | 366 | } else { |
mcimadamore@1562 | 367 | Type formalInterface = funcInterface.tsym.type; |
mcimadamore@1562 | 368 | InferenceContext funcInterfaceContext = |
mcimadamore@1562 | 369 | new InferenceContext(funcInterface.tsym.type.getTypeArguments()); |
mcimadamore@1562 | 370 | |
mcimadamore@1562 | 371 | Assert.check(paramTypes != null); |
mcimadamore@1562 | 372 | //get constraints from explicit params (this is done by |
mcimadamore@1562 | 373 | //checking that explicit param types are equal to the ones |
mcimadamore@1562 | 374 | //in the functional interface descriptors) |
mcimadamore@1562 | 375 | List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes(); |
mcimadamore@1562 | 376 | if (descParameterTypes.size() != paramTypes.size()) { |
mcimadamore@1562 | 377 | checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda")); |
mcimadamore@1562 | 378 | return types.createErrorType(funcInterface); |
mcimadamore@1562 | 379 | } |
mcimadamore@1562 | 380 | for (Type p : descParameterTypes) { |
mcimadamore@1562 | 381 | if (!types.isSameType(funcInterfaceContext.asFree(p), paramTypes.head)) { |
mcimadamore@1562 | 382 | checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); |
mcimadamore@1562 | 383 | return types.createErrorType(funcInterface); |
mcimadamore@1562 | 384 | } |
mcimadamore@1562 | 385 | paramTypes = paramTypes.tail; |
mcimadamore@1562 | 386 | } |
mcimadamore@1562 | 387 | |
mcimadamore@1562 | 388 | try { |
mcimadamore@1562 | 389 | funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings); |
mcimadamore@1562 | 390 | } catch (InferenceException ex) { |
mcimadamore@1562 | 391 | checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); |
mcimadamore@1562 | 392 | } |
mcimadamore@1562 | 393 | |
mcimadamore@1562 | 394 | List<Type> actualTypeargs = funcInterface.getTypeArguments(); |
mcimadamore@1562 | 395 | for (Type t : funcInterfaceContext.undetvars) { |
mcimadamore@1562 | 396 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 397 | if (uv.inst == null) { |
mcimadamore@1562 | 398 | uv.inst = actualTypeargs.head; |
mcimadamore@1562 | 399 | } |
mcimadamore@1562 | 400 | actualTypeargs = actualTypeargs.tail; |
mcimadamore@1562 | 401 | } |
mcimadamore@1562 | 402 | |
mcimadamore@1562 | 403 | Type owntype = funcInterfaceContext.asInstType(formalInterface); |
mcimadamore@1562 | 404 | if (!chk.checkValidGenericType(owntype)) { |
mcimadamore@1562 | 405 | //if the inferred functional interface type is not well-formed, |
mcimadamore@1562 | 406 | //or if it's not a subtype of the original target, issue an error |
mcimadamore@1562 | 407 | checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); |
mcimadamore@1562 | 408 | } |
mcimadamore@1562 | 409 | return owntype; |
mcimadamore@1562 | 410 | } |
mcimadamore@1562 | 411 | } |
mcimadamore@1562 | 412 | // </editor-fold> |
mcimadamore@1562 | 413 | |
mcimadamore@1562 | 414 | // <editor-fold defaultstate="collapsed" desc="Bound checking"> |
mcimadamore@1562 | 415 | /** |
mcimadamore@1562 | 416 | * Check bounds and perform incorporation |
mcimadamore@1562 | 417 | */ |
mcimadamore@1562 | 418 | void checkWithinBounds(InferenceContext inferenceContext, |
mcimadamore@1562 | 419 | Warner warn) throws InferenceException { |
mcimadamore@1562 | 420 | MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars); |
mcimadamore@1562 | 421 | try { |
mcimadamore@1562 | 422 | while (true) { |
mcimadamore@1562 | 423 | mlistener.reset(); |
mcimadamore@1562 | 424 | if (!allowGraphInference) { |
mcimadamore@1562 | 425 | //in legacy mode we lack of transitivity, so bound check |
mcimadamore@1562 | 426 | //cannot be run in parallel with other incoprporation rounds |
mcimadamore@1562 | 427 | for (Type t : inferenceContext.undetvars) { |
mcimadamore@1562 | 428 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 429 | IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn); |
mcimadamore@1562 | 430 | } |
mcimadamore@1562 | 431 | } |
mcimadamore@1562 | 432 | for (Type t : inferenceContext.undetvars) { |
mcimadamore@1562 | 433 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 434 | //bound incorporation |
mcimadamore@1562 | 435 | EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ? |
mcimadamore@1562 | 436 | incorporationStepsGraph : incorporationStepsLegacy; |
mcimadamore@1562 | 437 | for (IncorporationStep is : incorporationSteps) { |
mcimadamore@1562 | 438 | is.apply(uv, inferenceContext, warn); |
mcimadamore@1562 | 439 | } |
mcimadamore@1562 | 440 | } |
mcimadamore@1562 | 441 | if (!mlistener.changed || !allowGraphInference) break; |
mcimadamore@1562 | 442 | } |
mcimadamore@1562 | 443 | } |
mcimadamore@1562 | 444 | finally { |
mcimadamore@1562 | 445 | mlistener.detach(); |
mcimadamore@1562 | 446 | } |
mcimadamore@1562 | 447 | } |
mcimadamore@1562 | 448 | //where |
mcimadamore@1562 | 449 | /** |
mcimadamore@1562 | 450 | * This listener keeps track of changes on a group of inference variable |
mcimadamore@1562 | 451 | * bounds. Note: the listener must be detached (calling corresponding |
mcimadamore@1562 | 452 | * method) to make sure that the underlying inference variable is |
mcimadamore@1562 | 453 | * left in a clean state. |
mcimadamore@1562 | 454 | */ |
mcimadamore@1562 | 455 | class MultiUndetVarListener implements UndetVar.UndetVarListener { |
mcimadamore@1562 | 456 | |
mcimadamore@1562 | 457 | int rounds; |
mcimadamore@1562 | 458 | boolean changed; |
mcimadamore@1562 | 459 | List<Type> undetvars; |
mcimadamore@1562 | 460 | |
mcimadamore@1562 | 461 | public MultiUndetVarListener(List<Type> undetvars) { |
mcimadamore@1562 | 462 | this.undetvars = undetvars; |
mcimadamore@1562 | 463 | for (Type t : undetvars) { |
mcimadamore@1562 | 464 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 465 | uv.listener = this; |
mcimadamore@1562 | 466 | } |
mcimadamore@1562 | 467 | } |
mcimadamore@1562 | 468 | |
mcimadamore@1562 | 469 | public void varChanged(UndetVar uv, Set<InferenceBound> ibs) { |
mcimadamore@1562 | 470 | //avoid non-termination |
mcimadamore@1562 | 471 | if (rounds < MAX_INCORPORATION_STEPS) { |
mcimadamore@1562 | 472 | changed = true; |
mcimadamore@1562 | 473 | } |
mcimadamore@1562 | 474 | } |
mcimadamore@1562 | 475 | |
mcimadamore@1562 | 476 | void reset() { |
mcimadamore@1562 | 477 | rounds++; |
mcimadamore@1562 | 478 | changed = false; |
mcimadamore@1562 | 479 | } |
mcimadamore@1562 | 480 | |
mcimadamore@1562 | 481 | void detach() { |
mcimadamore@1562 | 482 | for (Type t : undetvars) { |
mcimadamore@1562 | 483 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 484 | uv.listener = null; |
mcimadamore@1562 | 485 | } |
mcimadamore@1562 | 486 | } |
mcimadamore@1562 | 487 | }; |
mcimadamore@1562 | 488 | |
mcimadamore@1562 | 489 | /** max number of incorporation rounds */ |
mcimadamore@1562 | 490 | static final int MAX_INCORPORATION_STEPS = 100; |
mcimadamore@1562 | 491 | |
mcimadamore@1562 | 492 | /** |
mcimadamore@1562 | 493 | * This enumeration defines an entry point for doing inference variable |
mcimadamore@1562 | 494 | * bound incorporation - it can be used to inject custom incorporation |
mcimadamore@1562 | 495 | * logic into the basic bound checking routine |
mcimadamore@1562 | 496 | */ |
mcimadamore@1562 | 497 | enum IncorporationStep { |
mcimadamore@1562 | 498 | /** |
mcimadamore@1562 | 499 | * Performs basic bound checking - i.e. is the instantiated type for a given |
mcimadamore@1562 | 500 | * inference variable compatible with its bounds? |
mcimadamore@1562 | 501 | */ |
mcimadamore@1562 | 502 | CHECK_BOUNDS() { |
mcimadamore@1562 | 503 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 504 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 505 | uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types); |
mcimadamore@1562 | 506 | infer.checkCompatibleUpperBounds(uv, inferenceContext); |
mcimadamore@1562 | 507 | if (uv.inst != null) { |
mcimadamore@1562 | 508 | Type inst = uv.inst; |
mcimadamore@1562 | 509 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 510 | if (!infer.types.isSubtypeUnchecked(inst, inferenceContext.asFree(u), warn)) { |
mcimadamore@1562 | 511 | infer.reportBoundError(uv, BoundErrorKind.UPPER); |
mcimadamore@1562 | 512 | } |
mcimadamore@1562 | 513 | } |
mcimadamore@1562 | 514 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1562 | 515 | if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), inst, warn)) { |
mcimadamore@1562 | 516 | infer.reportBoundError(uv, BoundErrorKind.LOWER); |
mcimadamore@1562 | 517 | } |
mcimadamore@1562 | 518 | } |
mcimadamore@1562 | 519 | for (Type e : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1562 | 520 | if (!infer.types.isSameType(inst, inferenceContext.asFree(e))) { |
mcimadamore@1562 | 521 | infer.reportBoundError(uv, BoundErrorKind.EQ); |
mcimadamore@1562 | 522 | } |
mcimadamore@1562 | 523 | } |
mcimadamore@1562 | 524 | } |
mcimadamore@1562 | 525 | } |
mcimadamore@1562 | 526 | }, |
mcimadamore@1562 | 527 | /** |
mcimadamore@1562 | 528 | * Check consistency of equality constraints. This is a slightly more aggressive |
mcimadamore@1562 | 529 | * inference routine that is designed as to maximize compatibility with JDK 7. |
mcimadamore@1562 | 530 | * Note: this is not used in graph mode. |
mcimadamore@1562 | 531 | */ |
mcimadamore@1562 | 532 | EQ_CHECK_LEGACY() { |
mcimadamore@1562 | 533 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 534 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 535 | Type eq = null; |
mcimadamore@1562 | 536 | for (Type e : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1562 | 537 | Assert.check(!inferenceContext.free(e)); |
mcimadamore@1562 | 538 | if (eq != null && !infer.types.isSameType(e, eq)) { |
mcimadamore@1562 | 539 | infer.reportBoundError(uv, BoundErrorKind.EQ); |
mcimadamore@1562 | 540 | } |
mcimadamore@1562 | 541 | eq = e; |
mcimadamore@1562 | 542 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1562 | 543 | Assert.check(!inferenceContext.free(l)); |
mcimadamore@1562 | 544 | if (!infer.types.isSubtypeUnchecked(l, e, warn)) { |
mcimadamore@1562 | 545 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER); |
mcimadamore@1562 | 546 | } |
mcimadamore@1562 | 547 | } |
mcimadamore@1562 | 548 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 549 | if (inferenceContext.free(u)) continue; |
mcimadamore@1562 | 550 | if (!infer.types.isSubtypeUnchecked(e, u, warn)) { |
mcimadamore@1562 | 551 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER); |
mcimadamore@1562 | 552 | } |
mcimadamore@1562 | 553 | } |
mcimadamore@1562 | 554 | } |
mcimadamore@1562 | 555 | } |
mcimadamore@1562 | 556 | }, |
mcimadamore@1562 | 557 | /** |
mcimadamore@1562 | 558 | * Check consistency of equality constraints. |
mcimadamore@1562 | 559 | */ |
mcimadamore@1562 | 560 | EQ_CHECK() { |
mcimadamore@1562 | 561 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 562 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 563 | for (Type e : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1562 | 564 | if (e.containsAny(inferenceContext.inferenceVars())) continue; |
mcimadamore@1562 | 565 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 566 | if (!infer.types.isSubtypeUnchecked(e, inferenceContext.asFree(u), warn)) { |
mcimadamore@1562 | 567 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER); |
mcimadamore@1562 | 568 | } |
mcimadamore@1562 | 569 | } |
mcimadamore@1562 | 570 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1562 | 571 | if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), e, warn)) { |
mcimadamore@1562 | 572 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER); |
mcimadamore@1562 | 573 | } |
mcimadamore@1562 | 574 | } |
mcimadamore@1562 | 575 | } |
mcimadamore@1562 | 576 | } |
mcimadamore@1562 | 577 | }, |
mcimadamore@1562 | 578 | /** |
mcimadamore@1562 | 579 | * Given a bound set containing {@code alpha <: T} and {@code alpha :> S} |
mcimadamore@1562 | 580 | * perform {@code S <: T} (which could lead to new bounds). |
mcimadamore@1562 | 581 | */ |
mcimadamore@1562 | 582 | CROSS_UPPER_LOWER() { |
mcimadamore@1562 | 583 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 584 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 585 | for (Type b1 : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 586 | for (Type b2 : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1655 | 587 | infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1)); |
mcimadamore@1562 | 588 | } |
mcimadamore@1562 | 589 | } |
mcimadamore@1562 | 590 | } |
mcimadamore@1562 | 591 | }, |
mcimadamore@1562 | 592 | /** |
mcimadamore@1562 | 593 | * Given a bound set containing {@code alpha <: T} and {@code alpha == S} |
mcimadamore@1562 | 594 | * perform {@code S <: T} (which could lead to new bounds). |
mcimadamore@1562 | 595 | */ |
mcimadamore@1562 | 596 | CROSS_UPPER_EQ() { |
mcimadamore@1562 | 597 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 598 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 599 | for (Type b1 : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 600 | for (Type b2 : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1655 | 601 | infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1)); |
mcimadamore@1562 | 602 | } |
mcimadamore@1562 | 603 | } |
mcimadamore@1562 | 604 | } |
mcimadamore@1562 | 605 | }, |
mcimadamore@1562 | 606 | /** |
mcimadamore@1562 | 607 | * Given a bound set containing {@code alpha :> S} and {@code alpha == T} |
mcimadamore@1562 | 608 | * perform {@code S <: T} (which could lead to new bounds). |
mcimadamore@1562 | 609 | */ |
mcimadamore@1562 | 610 | CROSS_EQ_LOWER() { |
mcimadamore@1562 | 611 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 612 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 613 | for (Type b1 : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1562 | 614 | for (Type b2 : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1655 | 615 | infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1)); |
mcimadamore@1655 | 616 | } |
mcimadamore@1655 | 617 | } |
mcimadamore@1655 | 618 | } |
mcimadamore@1655 | 619 | }, |
mcimadamore@1655 | 620 | /** |
mcimadamore@1655 | 621 | * Given a bound set containing {@code alpha == S} and {@code alpha == T} |
mcimadamore@1655 | 622 | * perform {@code S == T} (which could lead to new bounds). |
mcimadamore@1655 | 623 | */ |
mcimadamore@1655 | 624 | CROSS_EQ_EQ() { |
mcimadamore@1655 | 625 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1655 | 626 | Infer infer = inferenceContext.infer(); |
mcimadamore@1655 | 627 | for (Type b1 : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1655 | 628 | for (Type b2 : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1655 | 629 | if (b1 != b2) { |
mcimadamore@1655 | 630 | infer.types.isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1)); |
mcimadamore@1562 | 631 | } |
mcimadamore@1562 | 632 | } |
mcimadamore@1562 | 633 | } |
mcimadamore@1562 | 634 | } |
mcimadamore@1562 | 635 | }, |
mcimadamore@1562 | 636 | /** |
mcimadamore@1562 | 637 | * Given a bound set containing {@code alpha <: beta} propagate lower bounds |
mcimadamore@1562 | 638 | * from alpha to beta; also propagate upper bounds from beta to alpha. |
mcimadamore@1562 | 639 | */ |
mcimadamore@1562 | 640 | PROP_UPPER() { |
mcimadamore@1562 | 641 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 642 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 643 | for (Type b : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 644 | if (inferenceContext.inferenceVars().contains(b)) { |
mcimadamore@1562 | 645 | UndetVar uv2 = (UndetVar)inferenceContext.asFree(b); |
mcimadamore@1562 | 646 | //alpha <: beta |
mcimadamore@1628 | 647 | //0. set beta :> alpha |
mcimadamore@1628 | 648 | uv2.addBound(InferenceBound.LOWER, uv.qtype, infer.types); |
mcimadamore@1562 | 649 | //1. copy alpha's lower to beta's |
mcimadamore@1562 | 650 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1562 | 651 | uv2.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types); |
mcimadamore@1562 | 652 | } |
mcimadamore@1562 | 653 | //2. copy beta's upper to alpha's |
mcimadamore@1562 | 654 | for (Type u : uv2.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 655 | uv.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types); |
mcimadamore@1562 | 656 | } |
mcimadamore@1562 | 657 | } |
mcimadamore@1562 | 658 | } |
mcimadamore@1562 | 659 | } |
mcimadamore@1562 | 660 | }, |
mcimadamore@1562 | 661 | /** |
mcimadamore@1562 | 662 | * Given a bound set containing {@code alpha :> beta} propagate lower bounds |
mcimadamore@1562 | 663 | * from beta to alpha; also propagate upper bounds from alpha to beta. |
mcimadamore@1562 | 664 | */ |
mcimadamore@1562 | 665 | PROP_LOWER() { |
mcimadamore@1562 | 666 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 667 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 668 | for (Type b : uv.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1562 | 669 | if (inferenceContext.inferenceVars().contains(b)) { |
mcimadamore@1562 | 670 | UndetVar uv2 = (UndetVar)inferenceContext.asFree(b); |
mcimadamore@1562 | 671 | //alpha :> beta |
mcimadamore@1628 | 672 | //0. set beta <: alpha |
mcimadamore@1628 | 673 | uv2.addBound(InferenceBound.UPPER, uv.qtype, infer.types); |
mcimadamore@1562 | 674 | //1. copy alpha's upper to beta's |
mcimadamore@1562 | 675 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
mcimadamore@1562 | 676 | uv2.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types); |
mcimadamore@1562 | 677 | } |
mcimadamore@1562 | 678 | //2. copy beta's lower to alpha's |
mcimadamore@1562 | 679 | for (Type l : uv2.getBounds(InferenceBound.LOWER)) { |
mcimadamore@1562 | 680 | uv.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types); |
mcimadamore@1562 | 681 | } |
mcimadamore@1562 | 682 | } |
mcimadamore@1562 | 683 | } |
mcimadamore@1562 | 684 | } |
mcimadamore@1562 | 685 | }, |
mcimadamore@1562 | 686 | /** |
mcimadamore@1562 | 687 | * Given a bound set containing {@code alpha == beta} propagate lower/upper |
mcimadamore@1562 | 688 | * bounds from alpha to beta and back. |
mcimadamore@1562 | 689 | */ |
mcimadamore@1562 | 690 | PROP_EQ() { |
mcimadamore@1562 | 691 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 692 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 693 | for (Type b : uv.getBounds(InferenceBound.EQ)) { |
mcimadamore@1562 | 694 | if (inferenceContext.inferenceVars().contains(b)) { |
mcimadamore@1562 | 695 | UndetVar uv2 = (UndetVar)inferenceContext.asFree(b); |
mcimadamore@1562 | 696 | //alpha == beta |
mcimadamore@1628 | 697 | //0. set beta == alpha |
mcimadamore@1628 | 698 | uv2.addBound(InferenceBound.EQ, uv.qtype, infer.types); |
mcimadamore@1562 | 699 | //1. copy all alpha's bounds to beta's |
mcimadamore@1562 | 700 | for (InferenceBound ib : InferenceBound.values()) { |
mcimadamore@1562 | 701 | for (Type b2 : uv.getBounds(ib)) { |
mcimadamore@1562 | 702 | if (b2 != uv2) { |
mcimadamore@1562 | 703 | uv2.addBound(ib, inferenceContext.asInstType(b2), infer.types); |
mcimadamore@1562 | 704 | } |
mcimadamore@1562 | 705 | } |
mcimadamore@1562 | 706 | } |
mcimadamore@1562 | 707 | //2. copy all beta's bounds to alpha's |
mcimadamore@1562 | 708 | for (InferenceBound ib : InferenceBound.values()) { |
mcimadamore@1562 | 709 | for (Type b2 : uv2.getBounds(ib)) { |
mcimadamore@1562 | 710 | if (b2 != uv) { |
mcimadamore@1562 | 711 | uv.addBound(ib, inferenceContext.asInstType(b2), infer.types); |
mcimadamore@1562 | 712 | } |
mcimadamore@1562 | 713 | } |
mcimadamore@1562 | 714 | } |
mcimadamore@1562 | 715 | } |
mcimadamore@1562 | 716 | } |
mcimadamore@1562 | 717 | } |
mcimadamore@1562 | 718 | }; |
mcimadamore@1562 | 719 | |
mcimadamore@1562 | 720 | abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn); |
mcimadamore@1562 | 721 | } |
mcimadamore@1562 | 722 | |
mcimadamore@1562 | 723 | /** incorporation steps to be executed when running in legacy mode */ |
mcimadamore@1562 | 724 | EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY); |
mcimadamore@1562 | 725 | |
mcimadamore@1562 | 726 | /** incorporation steps to be executed when running in graph mode */ |
mcimadamore@1562 | 727 | EnumSet<IncorporationStep> incorporationStepsGraph = |
mcimadamore@1562 | 728 | EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY)); |
mcimadamore@1562 | 729 | |
mcimadamore@1562 | 730 | /** |
mcimadamore@1562 | 731 | * Make sure that the upper bounds we got so far lead to a solvable inference |
mcimadamore@1562 | 732 | * variable by making sure that a glb exists. |
mcimadamore@1562 | 733 | */ |
mcimadamore@1562 | 734 | void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) { |
mcimadamore@1562 | 735 | List<Type> hibounds = |
mcimadamore@1562 | 736 | Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext)); |
mcimadamore@1562 | 737 | Type hb = null; |
mcimadamore@1562 | 738 | if (hibounds.isEmpty()) |
mcimadamore@1562 | 739 | hb = syms.objectType; |
mcimadamore@1562 | 740 | else if (hibounds.tail.isEmpty()) |
mcimadamore@1562 | 741 | hb = hibounds.head; |
mcimadamore@1562 | 742 | else |
mcimadamore@1562 | 743 | hb = types.glb(hibounds); |
mcimadamore@1562 | 744 | if (hb == null || hb.isErroneous()) |
mcimadamore@1562 | 745 | reportBoundError(uv, BoundErrorKind.BAD_UPPER); |
mcimadamore@1562 | 746 | } |
mcimadamore@1562 | 747 | //where |
mcimadamore@1562 | 748 | protected static class BoundFilter implements Filter<Type> { |
mcimadamore@1562 | 749 | |
mcimadamore@1562 | 750 | InferenceContext inferenceContext; |
mcimadamore@1562 | 751 | |
mcimadamore@1562 | 752 | public BoundFilter(InferenceContext inferenceContext) { |
mcimadamore@1562 | 753 | this.inferenceContext = inferenceContext; |
mcimadamore@1562 | 754 | } |
mcimadamore@1562 | 755 | |
mcimadamore@1562 | 756 | @Override |
mcimadamore@1562 | 757 | public boolean accepts(Type t) { |
mcimadamore@1562 | 758 | return !t.isErroneous() && !inferenceContext.free(t) && |
mcimadamore@1562 | 759 | !t.hasTag(BOT); |
mcimadamore@1562 | 760 | } |
mcimadamore@1562 | 761 | }; |
mcimadamore@1562 | 762 | |
mcimadamore@1562 | 763 | /** |
mcimadamore@1562 | 764 | * This enumeration defines all possible bound-checking related errors. |
mcimadamore@1562 | 765 | */ |
mcimadamore@1562 | 766 | enum BoundErrorKind { |
mcimadamore@1562 | 767 | /** |
mcimadamore@1562 | 768 | * The (uninstantiated) inference variable has incompatible upper bounds. |
mcimadamore@1562 | 769 | */ |
mcimadamore@1562 | 770 | BAD_UPPER() { |
mcimadamore@1562 | 771 | @Override |
mcimadamore@1562 | 772 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
mcimadamore@1562 | 773 | return ex.setMessage("incompatible.upper.bounds", uv.qtype, |
mcimadamore@1562 | 774 | uv.getBounds(InferenceBound.UPPER)); |
mcimadamore@1562 | 775 | } |
mcimadamore@1562 | 776 | }, |
mcimadamore@1562 | 777 | /** |
mcimadamore@1562 | 778 | * An equality constraint is not compatible with an upper bound. |
mcimadamore@1562 | 779 | */ |
mcimadamore@1562 | 780 | BAD_EQ_UPPER() { |
mcimadamore@1562 | 781 | @Override |
mcimadamore@1562 | 782 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
mcimadamore@1562 | 783 | return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype, |
mcimadamore@1562 | 784 | uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER)); |
mcimadamore@1562 | 785 | } |
mcimadamore@1562 | 786 | }, |
mcimadamore@1562 | 787 | /** |
mcimadamore@1562 | 788 | * An equality constraint is not compatible with a lower bound. |
mcimadamore@1562 | 789 | */ |
mcimadamore@1562 | 790 | BAD_EQ_LOWER() { |
mcimadamore@1562 | 791 | @Override |
mcimadamore@1562 | 792 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
mcimadamore@1562 | 793 | return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype, |
mcimadamore@1562 | 794 | uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER)); |
mcimadamore@1562 | 795 | } |
mcimadamore@1562 | 796 | }, |
mcimadamore@1562 | 797 | /** |
mcimadamore@1562 | 798 | * Instantiated inference variable is not compatible with an upper bound. |
mcimadamore@1562 | 799 | */ |
mcimadamore@1562 | 800 | UPPER() { |
mcimadamore@1562 | 801 | @Override |
mcimadamore@1562 | 802 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
mcimadamore@1562 | 803 | return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst, |
mcimadamore@1562 | 804 | uv.getBounds(InferenceBound.UPPER)); |
mcimadamore@1562 | 805 | } |
mcimadamore@1562 | 806 | }, |
mcimadamore@1562 | 807 | /** |
mcimadamore@1562 | 808 | * Instantiated inference variable is not compatible with a lower bound. |
mcimadamore@1562 | 809 | */ |
mcimadamore@1562 | 810 | LOWER() { |
mcimadamore@1562 | 811 | @Override |
mcimadamore@1562 | 812 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
mcimadamore@1562 | 813 | return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst, |
mcimadamore@1562 | 814 | uv.getBounds(InferenceBound.LOWER)); |
mcimadamore@1562 | 815 | } |
mcimadamore@1562 | 816 | }, |
mcimadamore@1562 | 817 | /** |
mcimadamore@1562 | 818 | * Instantiated inference variable is not compatible with an equality constraint. |
mcimadamore@1562 | 819 | */ |
mcimadamore@1562 | 820 | EQ() { |
mcimadamore@1562 | 821 | @Override |
mcimadamore@1562 | 822 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
mcimadamore@1562 | 823 | return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst, |
mcimadamore@1562 | 824 | uv.getBounds(InferenceBound.EQ)); |
mcimadamore@1562 | 825 | } |
mcimadamore@1562 | 826 | }; |
mcimadamore@1562 | 827 | |
mcimadamore@1562 | 828 | abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv); |
mcimadamore@1562 | 829 | } |
mcimadamore@1562 | 830 | |
mcimadamore@1562 | 831 | /** |
mcimadamore@1562 | 832 | * Report a bound-checking error of given kind |
mcimadamore@1562 | 833 | */ |
mcimadamore@1562 | 834 | void reportBoundError(UndetVar uv, BoundErrorKind bk) { |
mcimadamore@1562 | 835 | throw bk.setMessage(inferenceException, uv); |
mcimadamore@1562 | 836 | } |
mcimadamore@1562 | 837 | // </editor-fold> |
mcimadamore@1562 | 838 | |
mcimadamore@1562 | 839 | // <editor-fold defaultstate="collapsed" desc="Inference engine"> |
mcimadamore@1562 | 840 | /** |
mcimadamore@1562 | 841 | * Graph inference strategy - act as an input to the inference solver; a strategy is |
mcimadamore@1562 | 842 | * composed of two ingredients: (i) find a node to solve in the inference graph, |
mcimadamore@1562 | 843 | * and (ii) tell th engine when we are done fixing inference variables |
mcimadamore@1562 | 844 | */ |
mcimadamore@1562 | 845 | interface GraphStrategy { |
mcimadamore@1562 | 846 | /** |
mcimadamore@1562 | 847 | * Pick the next node (leaf) to solve in the graph |
mcimadamore@1562 | 848 | */ |
mcimadamore@1562 | 849 | Node pickNode(InferenceGraph g); |
mcimadamore@1562 | 850 | /** |
mcimadamore@1562 | 851 | * Is this the last step? |
mcimadamore@1562 | 852 | */ |
mcimadamore@1562 | 853 | boolean done(); |
mcimadamore@1562 | 854 | } |
mcimadamore@1562 | 855 | |
mcimadamore@1562 | 856 | /** |
mcimadamore@1562 | 857 | * Simple solver strategy class that locates all leaves inside a graph |
mcimadamore@1562 | 858 | * and picks the first leaf as the next node to solve |
mcimadamore@1562 | 859 | */ |
mcimadamore@1562 | 860 | abstract class LeafSolver implements GraphStrategy { |
mcimadamore@1562 | 861 | public Node pickNode(InferenceGraph g) { |
mcimadamore@1562 | 862 | Assert.check(!g.nodes.isEmpty(), "No nodes to solve!"); |
mcimadamore@1562 | 863 | return g.nodes.get(0); |
mcimadamore@1562 | 864 | } |
mcimadamore@1562 | 865 | } |
mcimadamore@1562 | 866 | |
mcimadamore@1562 | 867 | /** |
mcimadamore@1562 | 868 | * This solver uses an heuristic to pick the best leaf - the heuristic |
mcimadamore@1562 | 869 | * tries to select the node that has maximal probability to contain one |
mcimadamore@1562 | 870 | * or more inference variables in a given list |
mcimadamore@1562 | 871 | */ |
mcimadamore@1562 | 872 | abstract class BestLeafSolver extends LeafSolver { |
mcimadamore@1562 | 873 | |
mcimadamore@1562 | 874 | List<Type> varsToSolve; |
mcimadamore@1562 | 875 | |
mcimadamore@1562 | 876 | BestLeafSolver(List<Type> varsToSolve) { |
mcimadamore@1562 | 877 | this.varsToSolve = varsToSolve; |
mcimadamore@1562 | 878 | } |
mcimadamore@1562 | 879 | |
mcimadamore@1562 | 880 | /** |
mcimadamore@1562 | 881 | * Computes the cost associated with a given node; the cost is computed |
mcimadamore@1562 | 882 | * as the total number of type-variables that should be eagerly instantiated |
mcimadamore@1562 | 883 | * in order to get to some of the variables in {@code varsToSolve} from |
mcimadamore@1562 | 884 | * a given node |
mcimadamore@1562 | 885 | */ |
mcimadamore@1562 | 886 | void computeCostIfNeeded(Node n, Map<Node, Integer> costMap) { |
mcimadamore@1562 | 887 | if (costMap.containsKey(n)) { |
mcimadamore@1562 | 888 | return; |
mcimadamore@1562 | 889 | } else if (!Collections.disjoint(n.data, varsToSolve)) { |
mcimadamore@1562 | 890 | costMap.put(n, n.data.size()); |
mcimadamore@1562 | 891 | } else { |
mcimadamore@1562 | 892 | int subcost = Integer.MAX_VALUE; |
mcimadamore@1562 | 893 | costMap.put(n, subcost); //avoid loops |
mcimadamore@1562 | 894 | for (Node n2 : n.getDependencies()) { |
mcimadamore@1562 | 895 | computeCostIfNeeded(n2, costMap); |
mcimadamore@1562 | 896 | subcost = Math.min(costMap.get(n2), subcost); |
mcimadamore@1562 | 897 | } |
mcimadamore@1562 | 898 | //update cost map to reflect real cost |
mcimadamore@1562 | 899 | costMap.put(n, subcost == Integer.MAX_VALUE ? |
mcimadamore@1562 | 900 | Integer.MAX_VALUE : |
mcimadamore@1562 | 901 | n.data.size() + subcost); |
mcimadamore@1562 | 902 | } |
mcimadamore@1562 | 903 | } |
mcimadamore@1562 | 904 | |
mcimadamore@1562 | 905 | /** |
mcimadamore@1562 | 906 | * Pick the leaf that minimize cost |
mcimadamore@1562 | 907 | */ |
mcimadamore@1562 | 908 | @Override |
mcimadamore@1562 | 909 | public Node pickNode(final InferenceGraph g) { |
mcimadamore@1562 | 910 | final Map<Node, Integer> costMap = new HashMap<Node, Integer>(); |
mcimadamore@1562 | 911 | ArrayList<Node> leaves = new ArrayList<Node>(); |
mcimadamore@1562 | 912 | for (Node n : g.nodes) { |
mcimadamore@1562 | 913 | computeCostIfNeeded(n, costMap); |
mcimadamore@1562 | 914 | if (n.isLeaf(n)) { |
mcimadamore@1562 | 915 | leaves.add(n); |
mcimadamore@1562 | 916 | } |
mcimadamore@1562 | 917 | } |
mcimadamore@1562 | 918 | Assert.check(!leaves.isEmpty(), "No nodes to solve!"); |
mcimadamore@1562 | 919 | Collections.sort(leaves, new java.util.Comparator<Node>() { |
mcimadamore@1562 | 920 | public int compare(Node n1, Node n2) { |
mcimadamore@1562 | 921 | return costMap.get(n1) - costMap.get(n2); |
mcimadamore@1562 | 922 | } |
mcimadamore@1562 | 923 | }); |
mcimadamore@1562 | 924 | return leaves.get(0); |
mcimadamore@1562 | 925 | } |
mcimadamore@1562 | 926 | } |
mcimadamore@1562 | 927 | |
mcimadamore@1562 | 928 | /** |
mcimadamore@1562 | 929 | * The inference process can be thought of as a sequence of steps. Each step |
mcimadamore@1562 | 930 | * instantiates an inference variable using a subset of the inference variable |
mcimadamore@1562 | 931 | * bounds, if certain condition are met. Decisions such as the sequence in which |
mcimadamore@1562 | 932 | * steps are applied, or which steps are to be applied are left to the inference engine. |
mcimadamore@1562 | 933 | */ |
mcimadamore@1562 | 934 | enum InferenceStep { |
mcimadamore@1562 | 935 | |
mcimadamore@1562 | 936 | /** |
mcimadamore@1562 | 937 | * Instantiate an inference variables using one of its (ground) equality |
mcimadamore@1562 | 938 | * constraints |
mcimadamore@1562 | 939 | */ |
mcimadamore@1562 | 940 | EQ(InferenceBound.EQ) { |
mcimadamore@1562 | 941 | @Override |
mcimadamore@1562 | 942 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
mcimadamore@1562 | 943 | return filterBounds(uv, inferenceContext).head; |
mcimadamore@1562 | 944 | } |
mcimadamore@1562 | 945 | }, |
mcimadamore@1562 | 946 | /** |
mcimadamore@1562 | 947 | * Instantiate an inference variables using its (ground) lower bounds. Such |
mcimadamore@1562 | 948 | * bounds are merged together using lub(). |
mcimadamore@1562 | 949 | */ |
mcimadamore@1562 | 950 | LOWER(InferenceBound.LOWER) { |
mcimadamore@1562 | 951 | @Override |
mcimadamore@1562 | 952 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
mcimadamore@1562 | 953 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 954 | List<Type> lobounds = filterBounds(uv, inferenceContext); |
mcimadamore@1562 | 955 | Type owntype = infer.types.lub(lobounds); |
mcimadamore@1562 | 956 | if (owntype.hasTag(ERROR)) { |
mcimadamore@1562 | 957 | throw infer.inferenceException |
mcimadamore@1562 | 958 | .setMessage("no.unique.minimal.instance.exists", |
mcimadamore@1562 | 959 | uv.qtype, lobounds); |
mcimadamore@1562 | 960 | } else { |
mcimadamore@1562 | 961 | return owntype; |
mcimadamore@1562 | 962 | } |
mcimadamore@1562 | 963 | } |
mcimadamore@1562 | 964 | }, |
mcimadamore@1562 | 965 | /** |
mcimadamore@1562 | 966 | * Instantiate an inference variables using its (ground) upper bounds. Such |
mcimadamore@1562 | 967 | * bounds are merged together using glb(). |
mcimadamore@1562 | 968 | */ |
mcimadamore@1562 | 969 | UPPER(InferenceBound.UPPER) { |
mcimadamore@1562 | 970 | @Override |
mcimadamore@1562 | 971 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
mcimadamore@1562 | 972 | Infer infer = inferenceContext.infer(); |
mcimadamore@1562 | 973 | List<Type> hibounds = filterBounds(uv, inferenceContext); |
mcimadamore@1562 | 974 | Type owntype = infer.types.glb(hibounds); |
mcimadamore@1562 | 975 | if (owntype.isErroneous()) { |
mcimadamore@1562 | 976 | throw infer.inferenceException |
mcimadamore@1562 | 977 | .setMessage("no.unique.maximal.instance.exists", |
mcimadamore@1562 | 978 | uv.qtype, hibounds); |
mcimadamore@1562 | 979 | } else { |
mcimadamore@1562 | 980 | return owntype; |
mcimadamore@1562 | 981 | } |
mcimadamore@1562 | 982 | } |
mcimadamore@1562 | 983 | }, |
mcimadamore@1562 | 984 | /** |
mcimadamore@1562 | 985 | * Like the former; the only difference is that this step can only be applied |
mcimadamore@1562 | 986 | * if all upper bounds are ground. |
mcimadamore@1562 | 987 | */ |
mcimadamore@1562 | 988 | UPPER_LEGACY(InferenceBound.UPPER) { |
mcimadamore@1562 | 989 | @Override |
mcimadamore@1562 | 990 | public boolean accepts(UndetVar t, InferenceContext inferenceContext) { |
mcimadamore@1562 | 991 | return !inferenceContext.free(t.getBounds(ib)); |
mcimadamore@1562 | 992 | } |
mcimadamore@1562 | 993 | |
mcimadamore@1562 | 994 | @Override |
mcimadamore@1562 | 995 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
mcimadamore@1562 | 996 | return UPPER.solve(uv, inferenceContext); |
mcimadamore@1562 | 997 | } |
mcimadamore@1562 | 998 | }; |
mcimadamore@1562 | 999 | |
mcimadamore@1562 | 1000 | final InferenceBound ib; |
mcimadamore@1562 | 1001 | |
mcimadamore@1562 | 1002 | InferenceStep(InferenceBound ib) { |
mcimadamore@1562 | 1003 | this.ib = ib; |
mcimadamore@1562 | 1004 | } |
mcimadamore@1562 | 1005 | |
mcimadamore@1562 | 1006 | /** |
mcimadamore@1562 | 1007 | * Find an instantiated type for a given inference variable within |
mcimadamore@1562 | 1008 | * a given inference context |
mcimadamore@1562 | 1009 | */ |
mcimadamore@1562 | 1010 | abstract Type solve(UndetVar uv, InferenceContext inferenceContext); |
mcimadamore@1562 | 1011 | |
mcimadamore@1562 | 1012 | /** |
mcimadamore@1562 | 1013 | * Can the inference variable be instantiated using this step? |
mcimadamore@1562 | 1014 | */ |
mcimadamore@1562 | 1015 | public boolean accepts(UndetVar t, InferenceContext inferenceContext) { |
mcimadamore@1562 | 1016 | return filterBounds(t, inferenceContext).nonEmpty(); |
mcimadamore@1562 | 1017 | } |
mcimadamore@1562 | 1018 | |
mcimadamore@1562 | 1019 | /** |
mcimadamore@1562 | 1020 | * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper) |
mcimadamore@1562 | 1021 | */ |
mcimadamore@1562 | 1022 | List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) { |
mcimadamore@1562 | 1023 | return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext)); |
mcimadamore@1562 | 1024 | } |
mcimadamore@1562 | 1025 | } |
mcimadamore@1562 | 1026 | |
mcimadamore@1562 | 1027 | /** |
mcimadamore@1562 | 1028 | * This enumeration defines the sequence of steps to be applied when the |
mcimadamore@1562 | 1029 | * solver works in legacy mode. The steps in this enumeration reflect |
mcimadamore@1562 | 1030 | * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). |
mcimadamore@1562 | 1031 | */ |
mcimadamore@1562 | 1032 | enum LegacyInferenceSteps { |
mcimadamore@1562 | 1033 | |
mcimadamore@1562 | 1034 | EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), |
mcimadamore@1562 | 1035 | EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY)); |
mcimadamore@1562 | 1036 | |
mcimadamore@1562 | 1037 | final EnumSet<InferenceStep> steps; |
mcimadamore@1562 | 1038 | |
mcimadamore@1562 | 1039 | LegacyInferenceSteps(EnumSet<InferenceStep> steps) { |
mcimadamore@1562 | 1040 | this.steps = steps; |
mcimadamore@1562 | 1041 | } |
mcimadamore@1562 | 1042 | } |
mcimadamore@1562 | 1043 | |
mcimadamore@1562 | 1044 | /** |
mcimadamore@1562 | 1045 | * This enumeration defines the sequence of steps to be applied when the |
mcimadamore@1562 | 1046 | * graph solver is used. This order is defined so as to maximize compatibility |
mcimadamore@1562 | 1047 | * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). |
mcimadamore@1562 | 1048 | */ |
mcimadamore@1562 | 1049 | enum GraphInferenceSteps { |
mcimadamore@1562 | 1050 | |
mcimadamore@1562 | 1051 | EQ(EnumSet.of(InferenceStep.EQ)), |
mcimadamore@1562 | 1052 | EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), |
mcimadamore@1562 | 1053 | EQ_LOWER_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER)); |
mcimadamore@1562 | 1054 | |
mcimadamore@1562 | 1055 | final EnumSet<InferenceStep> steps; |
mcimadamore@1562 | 1056 | |
mcimadamore@1562 | 1057 | GraphInferenceSteps(EnumSet<InferenceStep> steps) { |
mcimadamore@1562 | 1058 | this.steps = steps; |
mcimadamore@1562 | 1059 | } |
mcimadamore@1562 | 1060 | } |
mcimadamore@1562 | 1061 | |
mcimadamore@1562 | 1062 | /** |
mcimadamore@1562 | 1063 | * This is the graph inference solver - the solver organizes all inference variables in |
mcimadamore@1562 | 1064 | * a given inference context by bound dependencies - in the general case, such dependencies |
mcimadamore@1562 | 1065 | * would lead to a cyclic directed graph (hence the name); the dependency info is used to build |
mcimadamore@1562 | 1066 | * an acyclic graph, where all cyclic variables are bundled together. An inference |
mcimadamore@1562 | 1067 | * step corresponds to solving a node in the acyclic graph - this is done by |
mcimadamore@1562 | 1068 | * relying on a given strategy (see GraphStrategy). |
mcimadamore@1562 | 1069 | */ |
mcimadamore@1562 | 1070 | class GraphSolver { |
mcimadamore@1562 | 1071 | |
mcimadamore@1562 | 1072 | InferenceContext inferenceContext; |
mcimadamore@1562 | 1073 | Warner warn; |
mcimadamore@1562 | 1074 | |
mcimadamore@1562 | 1075 | GraphSolver(InferenceContext inferenceContext, Warner warn) { |
mcimadamore@1562 | 1076 | this.inferenceContext = inferenceContext; |
mcimadamore@1562 | 1077 | this.warn = warn; |
mcimadamore@1562 | 1078 | } |
mcimadamore@1562 | 1079 | |
mcimadamore@1562 | 1080 | /** |
mcimadamore@1562 | 1081 | * Solve variables in a given inference context. The amount of variables |
mcimadamore@1562 | 1082 | * to be solved, and the way in which the underlying acyclic graph is explored |
mcimadamore@1562 | 1083 | * depends on the selected solver strategy. |
mcimadamore@1562 | 1084 | */ |
mcimadamore@1562 | 1085 | void solve(GraphStrategy sstrategy) { |
mcimadamore@1562 | 1086 | checkWithinBounds(inferenceContext, warn); //initial propagation of bounds |
mcimadamore@1562 | 1087 | InferenceGraph inferenceGraph = new InferenceGraph(); |
mcimadamore@1562 | 1088 | while (!sstrategy.done()) { |
mcimadamore@1562 | 1089 | InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph); |
mcimadamore@1562 | 1090 | List<Type> varsToSolve = List.from(nodeToSolve.data); |
mcimadamore@1562 | 1091 | inferenceContext.save(); |
mcimadamore@1562 | 1092 | try { |
mcimadamore@1562 | 1093 | //repeat until all variables are solved |
mcimadamore@1562 | 1094 | outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) { |
mcimadamore@1562 | 1095 | //for each inference phase |
mcimadamore@1562 | 1096 | for (GraphInferenceSteps step : GraphInferenceSteps.values()) { |
mcimadamore@1562 | 1097 | if (inferenceContext.solveBasic(varsToSolve, step.steps)) { |
mcimadamore@1562 | 1098 | checkWithinBounds(inferenceContext, warn); |
mcimadamore@1562 | 1099 | continue outer; |
mcimadamore@1562 | 1100 | } |
mcimadamore@1562 | 1101 | } |
mcimadamore@1562 | 1102 | //no progress |
mcimadamore@1562 | 1103 | throw inferenceException; |
mcimadamore@1562 | 1104 | } |
mcimadamore@1562 | 1105 | } |
mcimadamore@1562 | 1106 | catch (InferenceException ex) { |
mcimadamore@1562 | 1107 | inferenceContext.rollback(); |
mcimadamore@1562 | 1108 | instantiateAsUninferredVars(varsToSolve, inferenceContext); |
mcimadamore@1562 | 1109 | checkWithinBounds(inferenceContext, warn); |
mcimadamore@1562 | 1110 | } |
mcimadamore@1562 | 1111 | inferenceGraph.deleteNode(nodeToSolve); |
mcimadamore@1562 | 1112 | } |
mcimadamore@1562 | 1113 | } |
mcimadamore@1562 | 1114 | |
mcimadamore@1562 | 1115 | /** |
mcimadamore@1562 | 1116 | * The dependencies between the inference variables that need to be solved |
mcimadamore@1562 | 1117 | * form a (possibly cyclic) graph. This class reduces the original dependency graph |
mcimadamore@1562 | 1118 | * to an acyclic version, where cyclic nodes are folded into a single 'super node'. |
mcimadamore@1562 | 1119 | */ |
mcimadamore@1562 | 1120 | class InferenceGraph { |
mcimadamore@1562 | 1121 | |
mcimadamore@1562 | 1122 | /** |
mcimadamore@1562 | 1123 | * This class represents a node in the graph. Each node corresponds |
mcimadamore@1562 | 1124 | * to an inference variable and has edges (dependencies) on other |
mcimadamore@1562 | 1125 | * nodes. The node defines an entry point that can be used to receive |
mcimadamore@1562 | 1126 | * updates on the structure of the graph this node belongs to (used to |
mcimadamore@1562 | 1127 | * keep dependencies in sync). |
mcimadamore@1562 | 1128 | */ |
mcimadamore@1562 | 1129 | class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> { |
mcimadamore@1562 | 1130 | |
mcimadamore@1562 | 1131 | Set<Node> deps; |
mcimadamore@1562 | 1132 | |
mcimadamore@1562 | 1133 | Node(Type ivar) { |
mcimadamore@1562 | 1134 | super(ListBuffer.of(ivar)); |
mcimadamore@1562 | 1135 | this.deps = new HashSet<Node>(); |
mcimadamore@1562 | 1136 | } |
mcimadamore@1562 | 1137 | |
mcimadamore@1562 | 1138 | @Override |
mcimadamore@1562 | 1139 | public Iterable<? extends Node> getDependencies() { |
mcimadamore@1562 | 1140 | return deps; |
mcimadamore@1562 | 1141 | } |
mcimadamore@1562 | 1142 | |
mcimadamore@1562 | 1143 | @Override |
mcimadamore@1562 | 1144 | public String printDependency(GraphUtils.Node<ListBuffer<Type>> to) { |
mcimadamore@1562 | 1145 | StringBuilder buf = new StringBuilder(); |
mcimadamore@1562 | 1146 | String sep = ""; |
mcimadamore@1562 | 1147 | for (Type from : data) { |
mcimadamore@1562 | 1148 | UndetVar uv = (UndetVar)inferenceContext.asFree(from); |
mcimadamore@1562 | 1149 | for (Type bound : uv.getBounds(InferenceBound.values())) { |
mcimadamore@1562 | 1150 | if (bound.containsAny(List.from(to.data))) { |
mcimadamore@1562 | 1151 | buf.append(sep); |
mcimadamore@1562 | 1152 | buf.append(bound); |
mcimadamore@1562 | 1153 | sep = ","; |
mcimadamore@1562 | 1154 | } |
mcimadamore@1562 | 1155 | } |
mcimadamore@1562 | 1156 | } |
mcimadamore@1562 | 1157 | return buf.toString(); |
mcimadamore@1562 | 1158 | } |
mcimadamore@1562 | 1159 | |
mcimadamore@1562 | 1160 | boolean isLeaf(Node n) { |
mcimadamore@1562 | 1161 | //no deps, or only one self dep |
mcimadamore@1562 | 1162 | return (n.deps.isEmpty() || |
mcimadamore@1562 | 1163 | n.deps.size() == 1 && n.deps.contains(n)); |
mcimadamore@1562 | 1164 | } |
mcimadamore@1562 | 1165 | |
mcimadamore@1562 | 1166 | void mergeWith(List<? extends Node> nodes) { |
mcimadamore@1562 | 1167 | for (Node n : nodes) { |
mcimadamore@1562 | 1168 | Assert.check(n.data.length() == 1, "Attempt to merge a compound node!"); |
mcimadamore@1562 | 1169 | data.appendList(n.data); |
mcimadamore@1562 | 1170 | deps.addAll(n.deps); |
mcimadamore@1562 | 1171 | } |
mcimadamore@1562 | 1172 | //update deps |
mcimadamore@1562 | 1173 | Set<Node> deps2 = new HashSet<Node>(); |
mcimadamore@1562 | 1174 | for (Node d : deps) { |
mcimadamore@1562 | 1175 | if (data.contains(d.data.first())) { |
mcimadamore@1562 | 1176 | deps2.add(this); |
mcimadamore@1562 | 1177 | } else { |
mcimadamore@1562 | 1178 | deps2.add(d); |
mcimadamore@1562 | 1179 | } |
mcimadamore@1562 | 1180 | } |
mcimadamore@1562 | 1181 | deps = deps2; |
mcimadamore@1562 | 1182 | } |
mcimadamore@1562 | 1183 | |
mcimadamore@1562 | 1184 | void graphChanged(Node from, Node to) { |
mcimadamore@1562 | 1185 | if (deps.contains(from)) { |
mcimadamore@1562 | 1186 | deps.remove(from); |
mcimadamore@1562 | 1187 | if (to != null) { |
mcimadamore@1562 | 1188 | deps.add(to); |
mcimadamore@1562 | 1189 | } |
mcimadamore@1562 | 1190 | } |
mcimadamore@1562 | 1191 | } |
mcimadamore@1562 | 1192 | } |
mcimadamore@1562 | 1193 | |
mcimadamore@1562 | 1194 | /** the nodes in the inference graph */ |
mcimadamore@1562 | 1195 | ArrayList<Node> nodes; |
mcimadamore@1562 | 1196 | |
mcimadamore@1562 | 1197 | InferenceGraph() { |
mcimadamore@1562 | 1198 | initNodes(); |
mcimadamore@1562 | 1199 | } |
mcimadamore@1562 | 1200 | |
mcimadamore@1562 | 1201 | /** |
mcimadamore@1562 | 1202 | * Delete a node from the graph. This update the underlying structure |
mcimadamore@1562 | 1203 | * of the graph (including dependencies) via listeners updates. |
mcimadamore@1562 | 1204 | */ |
mcimadamore@1562 | 1205 | public void deleteNode(Node n) { |
mcimadamore@1562 | 1206 | Assert.check(nodes.contains(n)); |
mcimadamore@1562 | 1207 | nodes.remove(n); |
mcimadamore@1562 | 1208 | notifyUpdate(n, null); |
mcimadamore@1562 | 1209 | } |
mcimadamore@1562 | 1210 | |
mcimadamore@1562 | 1211 | /** |
mcimadamore@1562 | 1212 | * Notify all nodes of a change in the graph. If the target node is |
mcimadamore@1562 | 1213 | * {@code null} the source node is assumed to be removed. |
mcimadamore@1562 | 1214 | */ |
mcimadamore@1562 | 1215 | void notifyUpdate(Node from, Node to) { |
mcimadamore@1562 | 1216 | for (Node n : nodes) { |
mcimadamore@1562 | 1217 | n.graphChanged(from, to); |
mcimadamore@1562 | 1218 | } |
mcimadamore@1562 | 1219 | } |
mcimadamore@1562 | 1220 | |
mcimadamore@1562 | 1221 | /** |
mcimadamore@1562 | 1222 | * Create the graph nodes. First a simple node is created for every inference |
mcimadamore@1562 | 1223 | * variables to be solved. Then Tarjan is used to found all connected components |
mcimadamore@1562 | 1224 | * in the graph. For each component containing more than one node, a super node is |
mcimadamore@1562 | 1225 | * created, effectively replacing the original cyclic nodes. |
mcimadamore@1562 | 1226 | */ |
mcimadamore@1562 | 1227 | void initNodes() { |
mcimadamore@1608 | 1228 | nodes = new ArrayList<Node>(); |
mcimadamore@1562 | 1229 | for (Type t : inferenceContext.restvars()) { |
mcimadamore@1562 | 1230 | nodes.add(new Node(t)); |
mcimadamore@1562 | 1231 | } |
mcimadamore@1562 | 1232 | for (Node n_i : nodes) { |
mcimadamore@1562 | 1233 | Type i = n_i.data.first(); |
mcimadamore@1562 | 1234 | for (Node n_j : nodes) { |
mcimadamore@1562 | 1235 | Type j = n_j.data.first(); |
mcimadamore@1562 | 1236 | UndetVar uv_i = (UndetVar)inferenceContext.asFree(i); |
mcimadamore@1562 | 1237 | if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) { |
mcimadamore@1562 | 1238 | //update i's deps |
mcimadamore@1562 | 1239 | n_i.deps.add(n_j); |
mcimadamore@1562 | 1240 | } |
mcimadamore@1562 | 1241 | } |
mcimadamore@1562 | 1242 | } |
mcimadamore@1608 | 1243 | ArrayList<Node> acyclicNodes = new ArrayList<Node>(); |
mcimadamore@1562 | 1244 | for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) { |
mcimadamore@1562 | 1245 | if (conSubGraph.length() > 1) { |
mcimadamore@1562 | 1246 | Node root = conSubGraph.head; |
mcimadamore@1562 | 1247 | root.mergeWith(conSubGraph.tail); |
mcimadamore@1562 | 1248 | for (Node n : conSubGraph) { |
mcimadamore@1562 | 1249 | notifyUpdate(n, root); |
mcimadamore@1562 | 1250 | } |
mcimadamore@1562 | 1251 | } |
mcimadamore@1608 | 1252 | acyclicNodes.add(conSubGraph.head); |
mcimadamore@1562 | 1253 | } |
mcimadamore@1608 | 1254 | nodes = acyclicNodes; |
mcimadamore@1562 | 1255 | } |
mcimadamore@1562 | 1256 | |
mcimadamore@1562 | 1257 | /** |
mcimadamore@1562 | 1258 | * Debugging: dot representation of this graph |
mcimadamore@1562 | 1259 | */ |
mcimadamore@1562 | 1260 | String toDot() { |
mcimadamore@1562 | 1261 | StringBuilder buf = new StringBuilder(); |
mcimadamore@1562 | 1262 | for (Type t : inferenceContext.undetvars) { |
mcimadamore@1562 | 1263 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 1264 | buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n", |
mcimadamore@1562 | 1265 | uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER), |
mcimadamore@1562 | 1266 | uv.getBounds(InferenceBound.EQ))); |
mcimadamore@1562 | 1267 | } |
mcimadamore@1562 | 1268 | return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString()); |
mcimadamore@1562 | 1269 | } |
mcimadamore@1562 | 1270 | } |
mcimadamore@1562 | 1271 | } |
mcimadamore@1562 | 1272 | // </editor-fold> |
mcimadamore@1562 | 1273 | |
mcimadamore@1562 | 1274 | // <editor-fold defaultstate="collapsed" desc="Inference context"> |
mcimadamore@1562 | 1275 | /** |
mcimadamore@1550 | 1276 | * Functional interface for defining inference callbacks. Certain actions |
mcimadamore@1550 | 1277 | * (i.e. subtyping checks) might need to be redone after all inference variables |
mcimadamore@1550 | 1278 | * have been fixed. |
mcimadamore@1337 | 1279 | */ |
mcimadamore@1550 | 1280 | interface FreeTypeListener { |
mcimadamore@1550 | 1281 | void typesInferred(InferenceContext inferenceContext); |
mcimadamore@1550 | 1282 | } |
mcimadamore@1337 | 1283 | |
mcimadamore@1337 | 1284 | /** |
mcimadamore@1337 | 1285 | * An inference context keeps track of the set of variables that are free |
mcimadamore@1337 | 1286 | * in the current context. It provides utility methods for opening/closing |
mcimadamore@1337 | 1287 | * types to their corresponding free/closed forms. It also provide hooks for |
mcimadamore@1337 | 1288 | * attaching deferred post-inference action (see PendingCheck). Finally, |
mcimadamore@1337 | 1289 | * it can be used as an entry point for performing upper/lower bound inference |
mcimadamore@1337 | 1290 | * (see InferenceKind). |
mcimadamore@1337 | 1291 | */ |
mcimadamore@1562 | 1292 | class InferenceContext { |
mcimadamore@1337 | 1293 | |
mcimadamore@1337 | 1294 | /** list of inference vars as undet vars */ |
mcimadamore@1337 | 1295 | List<Type> undetvars; |
mcimadamore@1337 | 1296 | |
mcimadamore@1337 | 1297 | /** list of inference vars in this context */ |
mcimadamore@1337 | 1298 | List<Type> inferencevars; |
mcimadamore@1337 | 1299 | |
mcimadamore@1562 | 1300 | /** backed up inference variables */ |
mcimadamore@1562 | 1301 | List<Type> saved_undet; |
mcimadamore@1562 | 1302 | |
mcimadamore@1337 | 1303 | java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners = |
mcimadamore@1337 | 1304 | new java.util.HashMap<FreeTypeListener, List<Type>>(); |
mcimadamore@1337 | 1305 | |
mcimadamore@1337 | 1306 | List<FreeTypeListener> freetypeListeners = List.nil(); |
mcimadamore@1337 | 1307 | |
mcimadamore@1550 | 1308 | public InferenceContext(List<Type> inferencevars) { |
mcimadamore@1550 | 1309 | this.undetvars = Type.map(inferencevars, fromTypeVarFun); |
mcimadamore@1337 | 1310 | this.inferencevars = inferencevars; |
mcimadamore@1337 | 1311 | } |
mcimadamore@1550 | 1312 | //where |
mcimadamore@1550 | 1313 | Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") { |
mcimadamore@1550 | 1314 | // mapping that turns inference variables into undet vars |
mcimadamore@1550 | 1315 | public Type apply(Type t) { |
mcimadamore@1550 | 1316 | if (t.hasTag(TYPEVAR)) return new UndetVar((TypeVar)t, types); |
mcimadamore@1550 | 1317 | else return t.map(this); |
mcimadamore@1550 | 1318 | } |
mcimadamore@1550 | 1319 | }; |
mcimadamore@1337 | 1320 | |
mcimadamore@1337 | 1321 | /** |
mcimadamore@1337 | 1322 | * returns the list of free variables (as type-variables) in this |
mcimadamore@1337 | 1323 | * inference context |
mcimadamore@1337 | 1324 | */ |
mcimadamore@1337 | 1325 | List<Type> inferenceVars() { |
mcimadamore@1337 | 1326 | return inferencevars; |
mcimadamore@1337 | 1327 | } |
mcimadamore@1337 | 1328 | |
mcimadamore@1337 | 1329 | /** |
mcimadamore@1337 | 1330 | * returns the list of uninstantiated variables (as type-variables) in this |
mcimadamore@1550 | 1331 | * inference context |
mcimadamore@1337 | 1332 | */ |
mcimadamore@1337 | 1333 | List<Type> restvars() { |
mcimadamore@1550 | 1334 | return filterVars(new Filter<UndetVar>() { |
mcimadamore@1550 | 1335 | public boolean accepts(UndetVar uv) { |
mcimadamore@1550 | 1336 | return uv.inst == null; |
mcimadamore@1337 | 1337 | } |
mcimadamore@1550 | 1338 | }); |
mcimadamore@1550 | 1339 | } |
mcimadamore@1550 | 1340 | |
mcimadamore@1550 | 1341 | /** |
mcimadamore@1550 | 1342 | * returns the list of instantiated variables (as type-variables) in this |
mcimadamore@1550 | 1343 | * inference context |
mcimadamore@1550 | 1344 | */ |
mcimadamore@1550 | 1345 | List<Type> instvars() { |
mcimadamore@1550 | 1346 | return filterVars(new Filter<UndetVar>() { |
mcimadamore@1550 | 1347 | public boolean accepts(UndetVar uv) { |
mcimadamore@1550 | 1348 | return uv.inst != null; |
mcimadamore@1550 | 1349 | } |
mcimadamore@1550 | 1350 | }); |
mcimadamore@1550 | 1351 | } |
mcimadamore@1550 | 1352 | |
mcimadamore@1550 | 1353 | /** |
mcimadamore@1550 | 1354 | * Get list of bounded inference variables (where bound is other than |
mcimadamore@1550 | 1355 | * declared bounds). |
mcimadamore@1550 | 1356 | */ |
mcimadamore@1550 | 1357 | final List<Type> boundedVars() { |
mcimadamore@1550 | 1358 | return filterVars(new Filter<UndetVar>() { |
mcimadamore@1550 | 1359 | public boolean accepts(UndetVar uv) { |
mcimadamore@1550 | 1360 | return uv.getBounds(InferenceBound.UPPER) |
mcimadamore@1550 | 1361 | .diff(uv.getDeclaredBounds()) |
mcimadamore@1550 | 1362 | .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty(); |
mcimadamore@1550 | 1363 | } |
mcimadamore@1550 | 1364 | }); |
mcimadamore@1550 | 1365 | } |
mcimadamore@1550 | 1366 | |
mcimadamore@1550 | 1367 | private List<Type> filterVars(Filter<UndetVar> fu) { |
mcimadamore@1550 | 1368 | ListBuffer<Type> res = ListBuffer.lb(); |
mcimadamore@1550 | 1369 | for (Type t : undetvars) { |
mcimadamore@1550 | 1370 | UndetVar uv = (UndetVar)t; |
mcimadamore@1550 | 1371 | if (fu.accepts(uv)) { |
mcimadamore@1550 | 1372 | res.append(uv.qtype); |
mcimadamore@1550 | 1373 | } |
mcimadamore@1337 | 1374 | } |
mcimadamore@1550 | 1375 | return res.toList(); |
mcimadamore@1337 | 1376 | } |
mcimadamore@1337 | 1377 | |
mcimadamore@1337 | 1378 | /** |
mcimadamore@1337 | 1379 | * is this type free? |
mcimadamore@1337 | 1380 | */ |
mcimadamore@1337 | 1381 | final boolean free(Type t) { |
mcimadamore@1337 | 1382 | return t.containsAny(inferencevars); |
mcimadamore@1337 | 1383 | } |
mcimadamore@1337 | 1384 | |
mcimadamore@1337 | 1385 | final boolean free(List<Type> ts) { |
mcimadamore@1337 | 1386 | for (Type t : ts) { |
mcimadamore@1337 | 1387 | if (free(t)) return true; |
mcimadamore@1337 | 1388 | } |
mcimadamore@1337 | 1389 | return false; |
mcimadamore@1337 | 1390 | } |
mcimadamore@1337 | 1391 | |
mcimadamore@1337 | 1392 | /** |
mcimadamore@1337 | 1393 | * Returns a list of free variables in a given type |
mcimadamore@1337 | 1394 | */ |
mcimadamore@1337 | 1395 | final List<Type> freeVarsIn(Type t) { |
mcimadamore@1337 | 1396 | ListBuffer<Type> buf = ListBuffer.lb(); |
mcimadamore@1337 | 1397 | for (Type iv : inferenceVars()) { |
mcimadamore@1337 | 1398 | if (t.contains(iv)) { |
mcimadamore@1337 | 1399 | buf.add(iv); |
mcimadamore@1337 | 1400 | } |
mcimadamore@1337 | 1401 | } |
mcimadamore@1337 | 1402 | return buf.toList(); |
mcimadamore@1337 | 1403 | } |
mcimadamore@1337 | 1404 | |
mcimadamore@1337 | 1405 | final List<Type> freeVarsIn(List<Type> ts) { |
mcimadamore@1337 | 1406 | ListBuffer<Type> buf = ListBuffer.lb(); |
mcimadamore@1337 | 1407 | for (Type t : ts) { |
mcimadamore@1337 | 1408 | buf.appendList(freeVarsIn(t)); |
mcimadamore@1337 | 1409 | } |
mcimadamore@1337 | 1410 | ListBuffer<Type> buf2 = ListBuffer.lb(); |
mcimadamore@1337 | 1411 | for (Type t : buf) { |
mcimadamore@1337 | 1412 | if (!buf2.contains(t)) { |
mcimadamore@1337 | 1413 | buf2.add(t); |
mcimadamore@1337 | 1414 | } |
mcimadamore@1337 | 1415 | } |
mcimadamore@1337 | 1416 | return buf2.toList(); |
mcimadamore@1337 | 1417 | } |
mcimadamore@1337 | 1418 | |
mcimadamore@1337 | 1419 | /** |
mcimadamore@1337 | 1420 | * Replace all free variables in a given type with corresponding |
mcimadamore@1337 | 1421 | * undet vars (used ahead of subtyping/compatibility checks to allow propagation |
mcimadamore@1337 | 1422 | * of inference constraints). |
mcimadamore@1337 | 1423 | */ |
mcimadamore@1550 | 1424 | final Type asFree(Type t) { |
mcimadamore@1337 | 1425 | return types.subst(t, inferencevars, undetvars); |
mcimadamore@1337 | 1426 | } |
mcimadamore@1337 | 1427 | |
mcimadamore@1550 | 1428 | final List<Type> asFree(List<Type> ts) { |
mcimadamore@1337 | 1429 | ListBuffer<Type> buf = ListBuffer.lb(); |
mcimadamore@1337 | 1430 | for (Type t : ts) { |
mcimadamore@1550 | 1431 | buf.append(asFree(t)); |
mcimadamore@1337 | 1432 | } |
mcimadamore@1337 | 1433 | return buf.toList(); |
mcimadamore@1337 | 1434 | } |
mcimadamore@1337 | 1435 | |
mcimadamore@1337 | 1436 | List<Type> instTypes() { |
mcimadamore@1337 | 1437 | ListBuffer<Type> buf = ListBuffer.lb(); |
mcimadamore@1337 | 1438 | for (Type t : undetvars) { |
mcimadamore@1337 | 1439 | UndetVar uv = (UndetVar)t; |
mcimadamore@1337 | 1440 | buf.append(uv.inst != null ? uv.inst : uv.qtype); |
mcimadamore@1337 | 1441 | } |
mcimadamore@1337 | 1442 | return buf.toList(); |
mcimadamore@1337 | 1443 | } |
mcimadamore@1337 | 1444 | |
mcimadamore@1337 | 1445 | /** |
mcimadamore@1337 | 1446 | * Replace all free variables in a given type with corresponding |
mcimadamore@1337 | 1447 | * instantiated types - if one or more free variable has not been |
mcimadamore@1337 | 1448 | * fully instantiated, it will still be available in the resulting type. |
mcimadamore@1337 | 1449 | */ |
mcimadamore@1550 | 1450 | Type asInstType(Type t) { |
mcimadamore@1337 | 1451 | return types.subst(t, inferencevars, instTypes()); |
mcimadamore@1337 | 1452 | } |
mcimadamore@1337 | 1453 | |
mcimadamore@1550 | 1454 | List<Type> asInstTypes(List<Type> ts) { |
mcimadamore@1337 | 1455 | ListBuffer<Type> buf = ListBuffer.lb(); |
mcimadamore@1337 | 1456 | for (Type t : ts) { |
mcimadamore@1550 | 1457 | buf.append(asInstType(t)); |
mcimadamore@1337 | 1458 | } |
mcimadamore@1337 | 1459 | return buf.toList(); |
mcimadamore@1337 | 1460 | } |
mcimadamore@1337 | 1461 | |
mcimadamore@1337 | 1462 | /** |
mcimadamore@1337 | 1463 | * Add custom hook for performing post-inference action |
mcimadamore@1337 | 1464 | */ |
mcimadamore@1337 | 1465 | void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) { |
mcimadamore@1337 | 1466 | freeTypeListeners.put(ftl, freeVarsIn(types)); |
mcimadamore@1337 | 1467 | } |
mcimadamore@1337 | 1468 | |
mcimadamore@1337 | 1469 | /** |
mcimadamore@1337 | 1470 | * Mark the inference context as complete and trigger evaluation |
mcimadamore@1337 | 1471 | * of all deferred checks. |
mcimadamore@1337 | 1472 | */ |
mcimadamore@1550 | 1473 | void notifyChange() { |
mcimadamore@1562 | 1474 | notifyChange(inferencevars.diff(restvars())); |
mcimadamore@1562 | 1475 | } |
mcimadamore@1562 | 1476 | |
mcimadamore@1562 | 1477 | void notifyChange(List<Type> inferredVars) { |
mcimadamore@1337 | 1478 | InferenceException thrownEx = null; |
mcimadamore@1337 | 1479 | for (Map.Entry<FreeTypeListener, List<Type>> entry : |
mcimadamore@1337 | 1480 | new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) { |
mcimadamore@1562 | 1481 | if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) { |
mcimadamore@1337 | 1482 | try { |
mcimadamore@1337 | 1483 | entry.getKey().typesInferred(this); |
mcimadamore@1337 | 1484 | freeTypeListeners.remove(entry.getKey()); |
mcimadamore@1337 | 1485 | } catch (InferenceException ex) { |
mcimadamore@1337 | 1486 | if (thrownEx == null) { |
mcimadamore@1337 | 1487 | thrownEx = ex; |
mcimadamore@1337 | 1488 | } |
mcimadamore@1337 | 1489 | } |
mcimadamore@1337 | 1490 | } |
mcimadamore@1337 | 1491 | } |
mcimadamore@1337 | 1492 | //inference exception multiplexing - present any inference exception |
mcimadamore@1337 | 1493 | //thrown when processing listeners as a single one |
mcimadamore@1337 | 1494 | if (thrownEx != null) { |
mcimadamore@1337 | 1495 | throw thrownEx; |
mcimadamore@1337 | 1496 | } |
mcimadamore@1337 | 1497 | } |
mcimadamore@1347 | 1498 | |
mcimadamore@1562 | 1499 | /** |
mcimadamore@1562 | 1500 | * Save the state of this inference context |
mcimadamore@1562 | 1501 | */ |
mcimadamore@1562 | 1502 | void save() { |
mcimadamore@1562 | 1503 | ListBuffer<Type> buf = ListBuffer.lb(); |
mcimadamore@1562 | 1504 | for (Type t : undetvars) { |
mcimadamore@1562 | 1505 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 1506 | UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types); |
mcimadamore@1562 | 1507 | for (InferenceBound ib : InferenceBound.values()) { |
mcimadamore@1562 | 1508 | for (Type b : uv.getBounds(ib)) { |
mcimadamore@1562 | 1509 | uv2.addBound(ib, b, types); |
mcimadamore@1562 | 1510 | } |
mcimadamore@1562 | 1511 | } |
mcimadamore@1562 | 1512 | uv2.inst = uv.inst; |
mcimadamore@1562 | 1513 | buf.add(uv2); |
mcimadamore@1562 | 1514 | } |
mcimadamore@1562 | 1515 | saved_undet = buf.toList(); |
mcimadamore@1562 | 1516 | } |
mcimadamore@1562 | 1517 | |
mcimadamore@1562 | 1518 | /** |
mcimadamore@1562 | 1519 | * Restore the state of this inference context to the previous known checkpoint |
mcimadamore@1562 | 1520 | */ |
mcimadamore@1562 | 1521 | void rollback() { |
mcimadamore@1562 | 1522 | Assert.check(saved_undet != null && saved_undet.length() == undetvars.length()); |
mcimadamore@1562 | 1523 | undetvars = saved_undet; |
mcimadamore@1562 | 1524 | saved_undet = null; |
mcimadamore@1562 | 1525 | } |
mcimadamore@1562 | 1526 | |
mcimadamore@1562 | 1527 | /** |
mcimadamore@1562 | 1528 | * Copy variable in this inference context to the given context |
mcimadamore@1562 | 1529 | */ |
mcimadamore@1562 | 1530 | void dupTo(final InferenceContext that) { |
mcimadamore@1562 | 1531 | that.inferencevars = that.inferencevars.appendList(inferencevars); |
mcimadamore@1562 | 1532 | that.undetvars = that.undetvars.appendList(undetvars); |
mcimadamore@1562 | 1533 | //set up listeners to notify original inference contexts as |
mcimadamore@1562 | 1534 | //propagated vars are inferred in new context |
mcimadamore@1562 | 1535 | for (Type t : inferencevars) { |
mcimadamore@1562 | 1536 | that.freeTypeListeners.put(new FreeTypeListener() { |
mcimadamore@1562 | 1537 | public void typesInferred(InferenceContext inferenceContext) { |
mcimadamore@1562 | 1538 | InferenceContext.this.notifyChange(); |
mcimadamore@1562 | 1539 | } |
mcimadamore@1562 | 1540 | }, List.of(t)); |
mcimadamore@1562 | 1541 | } |
mcimadamore@1562 | 1542 | } |
mcimadamore@1562 | 1543 | |
mcimadamore@1562 | 1544 | /** |
mcimadamore@1562 | 1545 | * Solve with given graph strategy. |
mcimadamore@1562 | 1546 | */ |
mcimadamore@1562 | 1547 | private void solve(GraphStrategy ss, Warner warn) { |
mcimadamore@1562 | 1548 | GraphSolver s = new GraphSolver(this, warn); |
mcimadamore@1562 | 1549 | s.solve(ss); |
mcimadamore@1562 | 1550 | } |
mcimadamore@1562 | 1551 | |
mcimadamore@1562 | 1552 | /** |
mcimadamore@1562 | 1553 | * Solve all variables in this context. |
mcimadamore@1562 | 1554 | */ |
mcimadamore@1562 | 1555 | public void solve(Warner warn) { |
mcimadamore@1562 | 1556 | solve(new LeafSolver() { |
mcimadamore@1562 | 1557 | public boolean done() { |
mcimadamore@1562 | 1558 | return restvars().isEmpty(); |
mcimadamore@1562 | 1559 | } |
mcimadamore@1562 | 1560 | }, warn); |
mcimadamore@1562 | 1561 | } |
mcimadamore@1562 | 1562 | |
mcimadamore@1562 | 1563 | /** |
mcimadamore@1562 | 1564 | * Solve all variables in the given list. |
mcimadamore@1562 | 1565 | */ |
mcimadamore@1562 | 1566 | public void solve(final List<Type> vars, Warner warn) { |
mcimadamore@1562 | 1567 | solve(new BestLeafSolver(vars) { |
mcimadamore@1562 | 1568 | public boolean done() { |
mcimadamore@1562 | 1569 | return !free(asInstTypes(vars)); |
mcimadamore@1562 | 1570 | } |
mcimadamore@1562 | 1571 | }, warn); |
mcimadamore@1562 | 1572 | } |
mcimadamore@1562 | 1573 | |
mcimadamore@1562 | 1574 | /** |
mcimadamore@1562 | 1575 | * Solve at least one variable in given list. |
mcimadamore@1562 | 1576 | */ |
mcimadamore@1562 | 1577 | public void solveAny(List<Type> varsToSolve, Warner warn) { |
mcimadamore@1562 | 1578 | checkWithinBounds(this, warn); //propagate bounds |
mcimadamore@1562 | 1579 | List<Type> boundedVars = boundedVars().intersect(restvars()).intersect(varsToSolve); |
mcimadamore@1562 | 1580 | if (boundedVars.isEmpty()) { |
mcimadamore@1562 | 1581 | throw inferenceException.setMessage("cyclic.inference", |
mcimadamore@1562 | 1582 | freeVarsIn(varsToSolve)); |
mcimadamore@1562 | 1583 | } |
mcimadamore@1562 | 1584 | solve(new BestLeafSolver(boundedVars) { |
mcimadamore@1562 | 1585 | public boolean done() { |
mcimadamore@1562 | 1586 | return instvars().intersect(varsToSolve).nonEmpty(); |
mcimadamore@1562 | 1587 | } |
mcimadamore@1562 | 1588 | }, warn); |
mcimadamore@1562 | 1589 | } |
mcimadamore@1562 | 1590 | |
mcimadamore@1562 | 1591 | /** |
mcimadamore@1562 | 1592 | * Apply a set of inference steps |
mcimadamore@1562 | 1593 | */ |
mcimadamore@1562 | 1594 | private boolean solveBasic(EnumSet<InferenceStep> steps) { |
mcimadamore@1562 | 1595 | return solveBasic(inferencevars, steps); |
mcimadamore@1562 | 1596 | } |
mcimadamore@1562 | 1597 | |
mcimadamore@1562 | 1598 | private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) { |
mcimadamore@1562 | 1599 | boolean changed = false; |
mcimadamore@1562 | 1600 | for (Type t : varsToSolve.intersect(restvars())) { |
mcimadamore@1550 | 1601 | UndetVar uv = (UndetVar)asFree(t); |
mcimadamore@1562 | 1602 | for (InferenceStep step : steps) { |
mcimadamore@1562 | 1603 | if (step.accepts(uv, this)) { |
mcimadamore@1562 | 1604 | uv.inst = step.solve(uv, this); |
mcimadamore@1562 | 1605 | changed = true; |
mcimadamore@1562 | 1606 | break; |
mcimadamore@1347 | 1607 | } |
mcimadamore@1347 | 1608 | } |
mcimadamore@1347 | 1609 | } |
mcimadamore@1562 | 1610 | return changed; |
mcimadamore@1562 | 1611 | } |
mcimadamore@1562 | 1612 | |
mcimadamore@1562 | 1613 | /** |
mcimadamore@1562 | 1614 | * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8). |
mcimadamore@1562 | 1615 | * During overload resolution, instantiation is done by doing a partial |
mcimadamore@1562 | 1616 | * inference process using eq/lower bound instantiation. During check, |
mcimadamore@1562 | 1617 | * we also instantiate any remaining vars by repeatedly using eq/upper |
mcimadamore@1562 | 1618 | * instantiation, until all variables are solved. |
mcimadamore@1562 | 1619 | */ |
mcimadamore@1562 | 1620 | public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) { |
mcimadamore@1562 | 1621 | while (true) { |
mcimadamore@1562 | 1622 | boolean stuck = !solveBasic(steps); |
mcimadamore@1562 | 1623 | if (restvars().isEmpty() || partial) { |
mcimadamore@1562 | 1624 | //all variables have been instantiated - exit |
mcimadamore@1562 | 1625 | break; |
mcimadamore@1562 | 1626 | } else if (stuck) { |
mcimadamore@1562 | 1627 | //some variables could not be instantiated because of cycles in |
mcimadamore@1562 | 1628 | //upper bounds - provide a (possibly recursive) default instantiation |
mcimadamore@1562 | 1629 | instantiateAsUninferredVars(restvars(), this); |
mcimadamore@1562 | 1630 | break; |
mcimadamore@1562 | 1631 | } else { |
mcimadamore@1562 | 1632 | //some variables have been instantiated - replace newly instantiated |
mcimadamore@1562 | 1633 | //variables in remaining upper bounds and continue |
mcimadamore@1562 | 1634 | for (Type t : undetvars) { |
mcimadamore@1562 | 1635 | UndetVar uv = (UndetVar)t; |
mcimadamore@1562 | 1636 | uv.substBounds(inferenceVars(), instTypes(), types); |
mcimadamore@1562 | 1637 | } |
mcimadamore@1562 | 1638 | } |
mcimadamore@1347 | 1639 | } |
mcimadamore@1562 | 1640 | checkWithinBounds(this, warn); |
mcimadamore@1562 | 1641 | } |
mcimadamore@1562 | 1642 | |
mcimadamore@1562 | 1643 | private Infer infer() { |
mcimadamore@1562 | 1644 | //back-door to infer |
mcimadamore@1562 | 1645 | return Infer.this; |
mcimadamore@1347 | 1646 | } |
mcimadamore@895 | 1647 | } |
mcimadamore@1337 | 1648 | |
mcimadamore@1550 | 1649 | final InferenceContext emptyContext = new InferenceContext(List.<Type>nil()); |
mcimadamore@1550 | 1650 | // </editor-fold> |
mcimadamore@1337 | 1651 | } |