Thu, 12 Oct 2017 19:50:01 +0800
merge
aoqi@0 | 1 | /* |
aoqi@0 | 2 | * Copyright (c) 1999, 2014, Oracle and/or its affiliates. All rights reserved. |
aoqi@0 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
aoqi@0 | 4 | * |
aoqi@0 | 5 | * This code is free software; you can redistribute it and/or modify it |
aoqi@0 | 6 | * under the terms of the GNU General Public License version 2 only, as |
aoqi@0 | 7 | * published by the Free Software Foundation. Oracle designates this |
aoqi@0 | 8 | * particular file as subject to the "Classpath" exception as provided |
aoqi@0 | 9 | * by Oracle in the LICENSE file that accompanied this code. |
aoqi@0 | 10 | * |
aoqi@0 | 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
aoqi@0 | 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
aoqi@0 | 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
aoqi@0 | 14 | * version 2 for more details (a copy is included in the LICENSE file that |
aoqi@0 | 15 | * accompanied this code). |
aoqi@0 | 16 | * |
aoqi@0 | 17 | * You should have received a copy of the GNU General Public License version |
aoqi@0 | 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
aoqi@0 | 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
aoqi@0 | 20 | * |
aoqi@0 | 21 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
aoqi@0 | 22 | * or visit www.oracle.com if you need additional information or have any |
aoqi@0 | 23 | * questions. |
aoqi@0 | 24 | */ |
aoqi@0 | 25 | |
aoqi@0 | 26 | package com.sun.tools.javac.comp; |
aoqi@0 | 27 | |
aoqi@0 | 28 | import com.sun.tools.javac.tree.JCTree; |
aoqi@0 | 29 | import com.sun.tools.javac.tree.JCTree.JCTypeCast; |
aoqi@0 | 30 | import com.sun.tools.javac.tree.TreeInfo; |
aoqi@0 | 31 | import com.sun.tools.javac.util.*; |
aoqi@0 | 32 | import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition; |
aoqi@0 | 33 | import com.sun.tools.javac.util.List; |
aoqi@0 | 34 | import com.sun.tools.javac.code.*; |
aoqi@0 | 35 | import com.sun.tools.javac.code.Type.*; |
aoqi@0 | 36 | import com.sun.tools.javac.code.Type.UndetVar.InferenceBound; |
aoqi@0 | 37 | import com.sun.tools.javac.code.Symbol.*; |
aoqi@0 | 38 | import com.sun.tools.javac.comp.DeferredAttr.AttrMode; |
aoqi@0 | 39 | import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph; |
aoqi@0 | 40 | import com.sun.tools.javac.comp.Infer.GraphSolver.InferenceGraph.Node; |
aoqi@0 | 41 | import com.sun.tools.javac.comp.Resolve.InapplicableMethodException; |
aoqi@0 | 42 | import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode; |
aoqi@0 | 43 | import com.sun.tools.javac.util.GraphUtils.TarjanNode; |
aoqi@0 | 44 | |
aoqi@0 | 45 | import java.util.ArrayList; |
aoqi@0 | 46 | import java.util.Collections; |
aoqi@0 | 47 | import java.util.EnumMap; |
aoqi@0 | 48 | import java.util.EnumSet; |
aoqi@0 | 49 | import java.util.HashMap; |
aoqi@0 | 50 | import java.util.HashSet; |
aoqi@0 | 51 | import java.util.LinkedHashSet; |
aoqi@0 | 52 | import java.util.Map; |
aoqi@0 | 53 | import java.util.Set; |
aoqi@0 | 54 | |
aoqi@0 | 55 | import static com.sun.tools.javac.code.TypeTag.*; |
aoqi@0 | 56 | |
aoqi@0 | 57 | /** Helper class for type parameter inference, used by the attribution phase. |
aoqi@0 | 58 | * |
aoqi@0 | 59 | * <p><b>This is NOT part of any supported API. |
aoqi@0 | 60 | * If you write code that depends on this, you do so at your own risk. |
aoqi@0 | 61 | * This code and its internal interfaces are subject to change or |
aoqi@0 | 62 | * deletion without notice.</b> |
aoqi@0 | 63 | */ |
aoqi@0 | 64 | public class Infer { |
aoqi@0 | 65 | protected static final Context.Key<Infer> inferKey = |
aoqi@0 | 66 | new Context.Key<Infer>(); |
aoqi@0 | 67 | |
aoqi@0 | 68 | Resolve rs; |
aoqi@0 | 69 | Check chk; |
aoqi@0 | 70 | Symtab syms; |
aoqi@0 | 71 | Types types; |
aoqi@0 | 72 | JCDiagnostic.Factory diags; |
aoqi@0 | 73 | Log log; |
aoqi@0 | 74 | |
aoqi@0 | 75 | /** should the graph solver be used? */ |
aoqi@0 | 76 | boolean allowGraphInference; |
aoqi@0 | 77 | |
aoqi@0 | 78 | public static Infer instance(Context context) { |
aoqi@0 | 79 | Infer instance = context.get(inferKey); |
aoqi@0 | 80 | if (instance == null) |
aoqi@0 | 81 | instance = new Infer(context); |
aoqi@0 | 82 | return instance; |
aoqi@0 | 83 | } |
aoqi@0 | 84 | |
aoqi@0 | 85 | protected Infer(Context context) { |
aoqi@0 | 86 | context.put(inferKey, this); |
aoqi@0 | 87 | |
aoqi@0 | 88 | rs = Resolve.instance(context); |
aoqi@0 | 89 | chk = Check.instance(context); |
aoqi@0 | 90 | syms = Symtab.instance(context); |
aoqi@0 | 91 | types = Types.instance(context); |
aoqi@0 | 92 | diags = JCDiagnostic.Factory.instance(context); |
aoqi@0 | 93 | log = Log.instance(context); |
aoqi@0 | 94 | inferenceException = new InferenceException(diags); |
aoqi@0 | 95 | Options options = Options.instance(context); |
aoqi@0 | 96 | allowGraphInference = Source.instance(context).allowGraphInference() |
aoqi@0 | 97 | && options.isUnset("useLegacyInference"); |
aoqi@0 | 98 | } |
aoqi@0 | 99 | |
aoqi@0 | 100 | /** A value for prototypes that admit any type, including polymorphic ones. */ |
aoqi@0 | 101 | public static final Type anyPoly = new JCNoType(); |
aoqi@0 | 102 | |
aoqi@0 | 103 | /** |
aoqi@0 | 104 | * This exception class is design to store a list of diagnostics corresponding |
aoqi@0 | 105 | * to inference errors that can arise during a method applicability check. |
aoqi@0 | 106 | */ |
aoqi@0 | 107 | public static class InferenceException extends InapplicableMethodException { |
aoqi@0 | 108 | private static final long serialVersionUID = 0; |
aoqi@0 | 109 | |
aoqi@0 | 110 | List<JCDiagnostic> messages = List.nil(); |
aoqi@0 | 111 | |
aoqi@0 | 112 | InferenceException(JCDiagnostic.Factory diags) { |
aoqi@0 | 113 | super(diags); |
aoqi@0 | 114 | } |
aoqi@0 | 115 | |
aoqi@0 | 116 | @Override |
aoqi@0 | 117 | InapplicableMethodException setMessage() { |
aoqi@0 | 118 | //no message to set |
aoqi@0 | 119 | return this; |
aoqi@0 | 120 | } |
aoqi@0 | 121 | |
aoqi@0 | 122 | @Override |
aoqi@0 | 123 | InapplicableMethodException setMessage(JCDiagnostic diag) { |
aoqi@0 | 124 | messages = messages.append(diag); |
aoqi@0 | 125 | return this; |
aoqi@0 | 126 | } |
aoqi@0 | 127 | |
aoqi@0 | 128 | @Override |
aoqi@0 | 129 | public JCDiagnostic getDiagnostic() { |
aoqi@0 | 130 | return messages.head; |
aoqi@0 | 131 | } |
aoqi@0 | 132 | |
aoqi@0 | 133 | void clear() { |
aoqi@0 | 134 | messages = List.nil(); |
aoqi@0 | 135 | } |
aoqi@0 | 136 | } |
aoqi@0 | 137 | |
aoqi@0 | 138 | protected final InferenceException inferenceException; |
aoqi@0 | 139 | |
aoqi@0 | 140 | // <editor-fold defaultstate="collapsed" desc="Inference routines"> |
aoqi@0 | 141 | /** |
aoqi@0 | 142 | * Main inference entry point - instantiate a generic method type |
aoqi@0 | 143 | * using given argument types and (possibly) an expected target-type. |
aoqi@0 | 144 | */ |
aoqi@0 | 145 | Type instantiateMethod( Env<AttrContext> env, |
aoqi@0 | 146 | List<Type> tvars, |
aoqi@0 | 147 | MethodType mt, |
aoqi@0 | 148 | Attr.ResultInfo resultInfo, |
aoqi@0 | 149 | MethodSymbol msym, |
aoqi@0 | 150 | List<Type> argtypes, |
aoqi@0 | 151 | boolean allowBoxing, |
aoqi@0 | 152 | boolean useVarargs, |
aoqi@0 | 153 | Resolve.MethodResolutionContext resolveContext, |
aoqi@0 | 154 | Warner warn) throws InferenceException { |
aoqi@0 | 155 | //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG |
aoqi@0 | 156 | final InferenceContext inferenceContext = new InferenceContext(tvars); //B0 |
aoqi@0 | 157 | inferenceException.clear(); |
aoqi@0 | 158 | try { |
aoqi@0 | 159 | DeferredAttr.DeferredAttrContext deferredAttrContext = |
aoqi@0 | 160 | resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn); |
aoqi@0 | 161 | |
aoqi@0 | 162 | resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext, //B2 |
aoqi@0 | 163 | argtypes, mt.getParameterTypes(), warn); |
aoqi@0 | 164 | |
aoqi@0 | 165 | if (allowGraphInference && |
aoqi@0 | 166 | resultInfo != null && |
aoqi@0 | 167 | !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { |
aoqi@0 | 168 | //inject return constraints earlier |
aoqi@0 | 169 | checkWithinBounds(inferenceContext, warn); //propagation |
aoqi@0 | 170 | Type newRestype = generateReturnConstraints(env.tree, resultInfo, //B3 |
aoqi@0 | 171 | mt, inferenceContext); |
aoqi@0 | 172 | mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype); |
aoqi@0 | 173 | //propagate outwards if needed |
aoqi@0 | 174 | if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) { |
aoqi@0 | 175 | //propagate inference context outwards and exit |
aoqi@0 | 176 | inferenceContext.dupTo(resultInfo.checkContext.inferenceContext()); |
aoqi@0 | 177 | deferredAttrContext.complete(); |
aoqi@0 | 178 | return mt; |
aoqi@0 | 179 | } |
aoqi@0 | 180 | } |
aoqi@0 | 181 | |
aoqi@0 | 182 | deferredAttrContext.complete(); |
aoqi@0 | 183 | |
aoqi@0 | 184 | // minimize as yet undetermined type variables |
aoqi@0 | 185 | if (allowGraphInference) { |
aoqi@0 | 186 | inferenceContext.solve(warn); |
aoqi@0 | 187 | } else { |
aoqi@0 | 188 | inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst |
aoqi@0 | 189 | } |
aoqi@0 | 190 | |
aoqi@0 | 191 | mt = (MethodType)inferenceContext.asInstType(mt); |
aoqi@0 | 192 | |
aoqi@0 | 193 | if (!allowGraphInference && |
aoqi@0 | 194 | inferenceContext.restvars().nonEmpty() && |
aoqi@0 | 195 | resultInfo != null && |
aoqi@0 | 196 | !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) { |
aoqi@0 | 197 | generateReturnConstraints(env.tree, resultInfo, mt, inferenceContext); |
aoqi@0 | 198 | inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst |
aoqi@0 | 199 | mt = (MethodType)inferenceContext.asInstType(mt); |
aoqi@0 | 200 | } |
aoqi@0 | 201 | |
aoqi@0 | 202 | if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) { |
aoqi@0 | 203 | log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt); |
aoqi@0 | 204 | } |
aoqi@0 | 205 | |
aoqi@0 | 206 | // return instantiated version of method type |
aoqi@0 | 207 | return mt; |
aoqi@0 | 208 | } finally { |
aoqi@0 | 209 | if (resultInfo != null || !allowGraphInference) { |
aoqi@0 | 210 | inferenceContext.notifyChange(); |
aoqi@0 | 211 | } else { |
aoqi@0 | 212 | inferenceContext.notifyChange(inferenceContext.boundedVars()); |
aoqi@0 | 213 | } |
aoqi@0 | 214 | if (resultInfo == null) { |
aoqi@0 | 215 | /* if the is no result info then we can clear the capture types |
aoqi@0 | 216 | * cache without affecting any result info check |
aoqi@0 | 217 | */ |
aoqi@0 | 218 | inferenceContext.captureTypeCache.clear(); |
aoqi@0 | 219 | } |
aoqi@0 | 220 | } |
aoqi@0 | 221 | } |
aoqi@0 | 222 | |
aoqi@0 | 223 | /** |
aoqi@0 | 224 | * Generate constraints from the generic method's return type. If the method |
aoqi@0 | 225 | * call occurs in a context where a type T is expected, use the expected |
aoqi@0 | 226 | * type to derive more constraints on the generic method inference variables. |
aoqi@0 | 227 | */ |
aoqi@0 | 228 | Type generateReturnConstraints(JCTree tree, Attr.ResultInfo resultInfo, |
aoqi@0 | 229 | MethodType mt, InferenceContext inferenceContext) { |
aoqi@0 | 230 | InferenceContext rsInfoInfContext = resultInfo.checkContext.inferenceContext(); |
aoqi@0 | 231 | Type from = mt.getReturnType(); |
aoqi@0 | 232 | if (mt.getReturnType().containsAny(inferenceContext.inferencevars) && |
aoqi@0 | 233 | rsInfoInfContext != emptyContext) { |
aoqi@0 | 234 | from = types.capture(from); |
aoqi@0 | 235 | //add synthetic captured ivars |
aoqi@0 | 236 | for (Type t : from.getTypeArguments()) { |
aoqi@0 | 237 | if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) { |
aoqi@0 | 238 | inferenceContext.addVar((TypeVar)t); |
aoqi@0 | 239 | } |
aoqi@0 | 240 | } |
aoqi@0 | 241 | } |
aoqi@0 | 242 | Type qtype = inferenceContext.asUndetVar(from); |
aoqi@0 | 243 | Type to = resultInfo.pt; |
aoqi@0 | 244 | |
aoqi@0 | 245 | if (qtype.hasTag(VOID)) { |
aoqi@0 | 246 | to = syms.voidType; |
aoqi@0 | 247 | } else if (to.hasTag(NONE)) { |
aoqi@0 | 248 | to = from.isPrimitive() ? from : syms.objectType; |
aoqi@0 | 249 | } else if (qtype.hasTag(UNDETVAR)) { |
aoqi@0 | 250 | if (resultInfo.pt.isReference()) { |
aoqi@0 | 251 | to = generateReturnConstraintsUndetVarToReference( |
aoqi@0 | 252 | tree, (UndetVar)qtype, to, resultInfo, inferenceContext); |
aoqi@0 | 253 | } else { |
aoqi@0 | 254 | if (to.isPrimitive()) { |
aoqi@0 | 255 | to = generateReturnConstraintsPrimitive(tree, (UndetVar)qtype, to, |
aoqi@0 | 256 | resultInfo, inferenceContext); |
aoqi@0 | 257 | } |
aoqi@0 | 258 | } |
aoqi@0 | 259 | } |
aoqi@0 | 260 | Assert.check(allowGraphInference || !rsInfoInfContext.free(to), |
aoqi@0 | 261 | "legacy inference engine cannot handle constraints on both sides of a subtyping assertion"); |
aoqi@0 | 262 | //we need to skip capture? |
aoqi@0 | 263 | Warner retWarn = new Warner(); |
aoqi@0 | 264 | if (!resultInfo.checkContext.compatible(qtype, rsInfoInfContext.asUndetVar(to), retWarn) || |
aoqi@0 | 265 | //unchecked conversion is not allowed in source 7 mode |
aoqi@0 | 266 | (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) { |
aoqi@0 | 267 | throw inferenceException |
aoqi@0 | 268 | .setMessage("infer.no.conforming.instance.exists", |
aoqi@0 | 269 | inferenceContext.restvars(), mt.getReturnType(), to); |
aoqi@0 | 270 | } |
aoqi@0 | 271 | return from; |
aoqi@0 | 272 | } |
aoqi@0 | 273 | |
aoqi@0 | 274 | private Type generateReturnConstraintsPrimitive(JCTree tree, UndetVar from, |
aoqi@0 | 275 | Type to, Attr.ResultInfo resultInfo, InferenceContext inferenceContext) { |
aoqi@0 | 276 | if (!allowGraphInference) { |
aoqi@0 | 277 | //if legacy, just return boxed type |
aoqi@0 | 278 | return types.boxedClass(to).type; |
aoqi@0 | 279 | } |
aoqi@0 | 280 | //if graph inference we need to skip conflicting boxed bounds... |
aoqi@0 | 281 | for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.UPPER, |
aoqi@0 | 282 | InferenceBound.LOWER)) { |
aoqi@0 | 283 | Type boundAsPrimitive = types.unboxedType(t); |
aoqi@0 | 284 | if (boundAsPrimitive == null || boundAsPrimitive.hasTag(NONE)) { |
aoqi@0 | 285 | continue; |
aoqi@0 | 286 | } |
aoqi@0 | 287 | return generateReferenceToTargetConstraint(tree, from, to, |
aoqi@0 | 288 | resultInfo, inferenceContext); |
aoqi@0 | 289 | } |
aoqi@0 | 290 | return types.boxedClass(to).type; |
aoqi@0 | 291 | } |
aoqi@0 | 292 | |
aoqi@0 | 293 | private Type generateReturnConstraintsUndetVarToReference(JCTree tree, |
aoqi@0 | 294 | UndetVar from, Type to, Attr.ResultInfo resultInfo, |
aoqi@0 | 295 | InferenceContext inferenceContext) { |
aoqi@0 | 296 | Type captureOfTo = types.capture(to); |
aoqi@0 | 297 | /* T is a reference type, but is not a wildcard-parameterized type, and either |
aoqi@0 | 298 | */ |
aoqi@0 | 299 | if (captureOfTo == to) { //not a wildcard parameterized type |
aoqi@0 | 300 | /* i) B2 contains a bound of one of the forms alpha = S or S <: alpha, |
aoqi@0 | 301 | * where S is a wildcard-parameterized type, or |
aoqi@0 | 302 | */ |
aoqi@0 | 303 | for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { |
aoqi@0 | 304 | Type captureOfBound = types.capture(t); |
aoqi@0 | 305 | if (captureOfBound != t) { |
aoqi@0 | 306 | return generateReferenceToTargetConstraint(tree, from, to, |
aoqi@0 | 307 | resultInfo, inferenceContext); |
aoqi@0 | 308 | } |
aoqi@0 | 309 | } |
aoqi@0 | 310 | |
aoqi@0 | 311 | /* ii) B2 contains two bounds of the forms S1 <: alpha and S2 <: alpha, |
aoqi@0 | 312 | * where S1 and S2 have supertypes that are two different |
aoqi@0 | 313 | * parameterizations of the same generic class or interface. |
aoqi@0 | 314 | */ |
aoqi@0 | 315 | for (Type aLowerBound : from.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 316 | for (Type anotherLowerBound : from.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 317 | if (aLowerBound != anotherLowerBound && |
aoqi@0 | 318 | commonSuperWithDiffParameterization(aLowerBound, anotherLowerBound)) { |
aoqi@0 | 319 | /* self comment check if any lower bound may be and undetVar, |
aoqi@0 | 320 | * in that case the result of this call may be a false positive. |
aoqi@0 | 321 | * Should this be restricted to non free types? |
aoqi@0 | 322 | */ |
aoqi@0 | 323 | return generateReferenceToTargetConstraint(tree, from, to, |
aoqi@0 | 324 | resultInfo, inferenceContext); |
aoqi@0 | 325 | } |
aoqi@0 | 326 | } |
aoqi@0 | 327 | } |
aoqi@0 | 328 | } |
aoqi@0 | 329 | |
aoqi@0 | 330 | /* T is a parameterization of a generic class or interface, G, |
aoqi@0 | 331 | * and B2 contains a bound of one of the forms alpha = S or S <: alpha, |
aoqi@0 | 332 | * where there exists no type of the form G<...> that is a |
aoqi@0 | 333 | * supertype of S, but the raw type G is a supertype of S |
aoqi@0 | 334 | */ |
aoqi@0 | 335 | if (to.isParameterized()) { |
aoqi@0 | 336 | for (Type t : from.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) { |
aoqi@0 | 337 | Type sup = types.asSuper(t, to.tsym); |
aoqi@0 | 338 | if (sup != null && sup.isRaw()) { |
aoqi@0 | 339 | return generateReferenceToTargetConstraint(tree, from, to, |
aoqi@0 | 340 | resultInfo, inferenceContext); |
aoqi@0 | 341 | } |
aoqi@0 | 342 | } |
aoqi@0 | 343 | } |
aoqi@0 | 344 | return to; |
aoqi@0 | 345 | } |
aoqi@0 | 346 | |
aoqi@0 | 347 | private boolean commonSuperWithDiffParameterization(Type t, Type s) { |
aoqi@0 | 348 | Pair<Type, Type> supers = getParameterizedSupers(t, s); |
aoqi@0 | 349 | return (supers != null && !types.isSameType(supers.fst, supers.snd)); |
aoqi@0 | 350 | } |
aoqi@0 | 351 | |
aoqi@0 | 352 | private Type generateReferenceToTargetConstraint(JCTree tree, UndetVar from, |
aoqi@0 | 353 | Type to, Attr.ResultInfo resultInfo, |
aoqi@0 | 354 | InferenceContext inferenceContext) { |
aoqi@0 | 355 | inferenceContext.solve(List.of(from.qtype), new Warner()); |
vromero@2543 | 356 | inferenceContext.notifyChange(); |
aoqi@0 | 357 | Type capturedType = resultInfo.checkContext.inferenceContext() |
aoqi@0 | 358 | .cachedCapture(tree, from.inst, false); |
aoqi@0 | 359 | if (types.isConvertible(capturedType, |
aoqi@0 | 360 | resultInfo.checkContext.inferenceContext().asUndetVar(to))) { |
aoqi@0 | 361 | //effectively skip additional return-type constraint generation (compatibility) |
aoqi@0 | 362 | return syms.objectType; |
aoqi@0 | 363 | } |
aoqi@0 | 364 | return to; |
aoqi@0 | 365 | } |
aoqi@0 | 366 | |
aoqi@0 | 367 | /** |
aoqi@0 | 368 | * Infer cyclic inference variables as described in 15.12.2.8. |
aoqi@0 | 369 | */ |
aoqi@0 | 370 | private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) { |
aoqi@0 | 371 | ListBuffer<Type> todo = new ListBuffer<>(); |
aoqi@0 | 372 | //step 1 - create fresh tvars |
aoqi@0 | 373 | for (Type t : vars) { |
aoqi@0 | 374 | UndetVar uv = (UndetVar)inferenceContext.asUndetVar(t); |
aoqi@0 | 375 | List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER); |
aoqi@0 | 376 | if (Type.containsAny(upperBounds, vars)) { |
aoqi@0 | 377 | TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner); |
aoqi@0 | 378 | fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null); |
aoqi@0 | 379 | todo.append(uv); |
aoqi@0 | 380 | uv.inst = fresh_tvar.type; |
aoqi@0 | 381 | } else if (upperBounds.nonEmpty()) { |
aoqi@0 | 382 | uv.inst = types.glb(upperBounds); |
aoqi@0 | 383 | } else { |
aoqi@0 | 384 | uv.inst = syms.objectType; |
aoqi@0 | 385 | } |
aoqi@0 | 386 | } |
aoqi@0 | 387 | //step 2 - replace fresh tvars in their bounds |
aoqi@0 | 388 | List<Type> formals = vars; |
aoqi@0 | 389 | for (Type t : todo) { |
aoqi@0 | 390 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 391 | TypeVar ct = (TypeVar)uv.inst; |
aoqi@0 | 392 | ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct))); |
aoqi@0 | 393 | if (ct.bound.isErroneous()) { |
aoqi@0 | 394 | //report inference error if glb fails |
aoqi@0 | 395 | reportBoundError(uv, BoundErrorKind.BAD_UPPER); |
aoqi@0 | 396 | } |
aoqi@0 | 397 | formals = formals.tail; |
aoqi@0 | 398 | } |
aoqi@0 | 399 | } |
aoqi@0 | 400 | |
aoqi@0 | 401 | /** |
aoqi@0 | 402 | * Compute a synthetic method type corresponding to the requested polymorphic |
aoqi@0 | 403 | * method signature. The target return type is computed from the immediately |
aoqi@0 | 404 | * enclosing scope surrounding the polymorphic-signature call. |
aoqi@0 | 405 | */ |
aoqi@0 | 406 | Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env, |
aoqi@0 | 407 | MethodSymbol spMethod, // sig. poly. method or null if none |
aoqi@0 | 408 | Resolve.MethodResolutionContext resolveContext, |
aoqi@0 | 409 | List<Type> argtypes) { |
aoqi@0 | 410 | final Type restype; |
aoqi@0 | 411 | |
aoqi@0 | 412 | //The return type for a polymorphic signature call is computed from |
aoqi@0 | 413 | //the enclosing tree E, as follows: if E is a cast, then use the |
aoqi@0 | 414 | //target type of the cast expression as a return type; if E is an |
aoqi@0 | 415 | //expression statement, the return type is 'void' - otherwise the |
aoqi@0 | 416 | //return type is simply 'Object'. A correctness check ensures that |
aoqi@0 | 417 | //env.next refers to the lexically enclosing environment in which |
aoqi@0 | 418 | //the polymorphic signature call environment is nested. |
aoqi@0 | 419 | |
aoqi@0 | 420 | switch (env.next.tree.getTag()) { |
aoqi@0 | 421 | case TYPECAST: |
aoqi@0 | 422 | JCTypeCast castTree = (JCTypeCast)env.next.tree; |
aoqi@0 | 423 | restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ? |
aoqi@0 | 424 | castTree.clazz.type : |
aoqi@0 | 425 | syms.objectType; |
aoqi@0 | 426 | break; |
aoqi@0 | 427 | case EXEC: |
aoqi@0 | 428 | JCTree.JCExpressionStatement execTree = |
aoqi@0 | 429 | (JCTree.JCExpressionStatement)env.next.tree; |
aoqi@0 | 430 | restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ? |
aoqi@0 | 431 | syms.voidType : |
aoqi@0 | 432 | syms.objectType; |
aoqi@0 | 433 | break; |
aoqi@0 | 434 | default: |
aoqi@0 | 435 | restype = syms.objectType; |
aoqi@0 | 436 | } |
aoqi@0 | 437 | |
aoqi@0 | 438 | List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step)); |
aoqi@0 | 439 | List<Type> exType = spMethod != null ? |
aoqi@0 | 440 | spMethod.getThrownTypes() : |
aoqi@0 | 441 | List.of(syms.throwableType); // make it throw all exceptions |
aoqi@0 | 442 | |
aoqi@0 | 443 | MethodType mtype = new MethodType(paramtypes, |
aoqi@0 | 444 | restype, |
aoqi@0 | 445 | exType, |
aoqi@0 | 446 | syms.methodClass); |
aoqi@0 | 447 | return mtype; |
aoqi@0 | 448 | } |
aoqi@0 | 449 | //where |
aoqi@0 | 450 | class ImplicitArgType extends DeferredAttr.DeferredTypeMap { |
aoqi@0 | 451 | |
aoqi@0 | 452 | public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) { |
vromero@2543 | 453 | (rs.deferredAttr).super(AttrMode.SPECULATIVE, msym, phase); |
aoqi@0 | 454 | } |
aoqi@0 | 455 | |
aoqi@0 | 456 | public Type apply(Type t) { |
aoqi@0 | 457 | t = types.erasure(super.apply(t)); |
aoqi@0 | 458 | if (t.hasTag(BOT)) |
aoqi@0 | 459 | // nulls type as the marker type Null (which has no instances) |
aoqi@0 | 460 | // infer as java.lang.Void for now |
aoqi@0 | 461 | t = types.boxedClass(syms.voidType).type; |
aoqi@0 | 462 | return t; |
aoqi@0 | 463 | } |
aoqi@0 | 464 | } |
aoqi@0 | 465 | |
aoqi@0 | 466 | /** |
aoqi@0 | 467 | * This method is used to infer a suitable target SAM in case the original |
aoqi@0 | 468 | * SAM type contains one or more wildcards. An inference process is applied |
aoqi@0 | 469 | * so that wildcard bounds, as well as explicit lambda/method ref parameters |
aoqi@0 | 470 | * (where applicable) are used to constraint the solution. |
aoqi@0 | 471 | */ |
aoqi@0 | 472 | public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface, |
aoqi@0 | 473 | List<Type> paramTypes, Check.CheckContext checkContext) { |
aoqi@0 | 474 | if (types.capture(funcInterface) == funcInterface) { |
aoqi@0 | 475 | //if capture doesn't change the type then return the target unchanged |
aoqi@0 | 476 | //(this means the target contains no wildcards!) |
aoqi@0 | 477 | return funcInterface; |
aoqi@0 | 478 | } else { |
aoqi@0 | 479 | Type formalInterface = funcInterface.tsym.type; |
aoqi@0 | 480 | InferenceContext funcInterfaceContext = |
aoqi@0 | 481 | new InferenceContext(funcInterface.tsym.type.getTypeArguments()); |
aoqi@0 | 482 | |
aoqi@0 | 483 | Assert.check(paramTypes != null); |
aoqi@0 | 484 | //get constraints from explicit params (this is done by |
aoqi@0 | 485 | //checking that explicit param types are equal to the ones |
aoqi@0 | 486 | //in the functional interface descriptors) |
aoqi@0 | 487 | List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes(); |
aoqi@0 | 488 | if (descParameterTypes.size() != paramTypes.size()) { |
aoqi@0 | 489 | checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda")); |
aoqi@0 | 490 | return types.createErrorType(funcInterface); |
aoqi@0 | 491 | } |
aoqi@0 | 492 | for (Type p : descParameterTypes) { |
aoqi@0 | 493 | if (!types.isSameType(funcInterfaceContext.asUndetVar(p), paramTypes.head)) { |
aoqi@0 | 494 | checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); |
aoqi@0 | 495 | return types.createErrorType(funcInterface); |
aoqi@0 | 496 | } |
aoqi@0 | 497 | paramTypes = paramTypes.tail; |
aoqi@0 | 498 | } |
aoqi@0 | 499 | |
aoqi@0 | 500 | try { |
aoqi@0 | 501 | funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings); |
aoqi@0 | 502 | } catch (InferenceException ex) { |
aoqi@0 | 503 | checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); |
aoqi@0 | 504 | } |
aoqi@0 | 505 | |
aoqi@0 | 506 | List<Type> actualTypeargs = funcInterface.getTypeArguments(); |
aoqi@0 | 507 | for (Type t : funcInterfaceContext.undetvars) { |
aoqi@0 | 508 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 509 | if (uv.inst == null) { |
aoqi@0 | 510 | uv.inst = actualTypeargs.head; |
aoqi@0 | 511 | } |
aoqi@0 | 512 | actualTypeargs = actualTypeargs.tail; |
aoqi@0 | 513 | } |
aoqi@0 | 514 | |
aoqi@0 | 515 | Type owntype = funcInterfaceContext.asInstType(formalInterface); |
aoqi@0 | 516 | if (!chk.checkValidGenericType(owntype)) { |
aoqi@0 | 517 | //if the inferred functional interface type is not well-formed, |
aoqi@0 | 518 | //or if it's not a subtype of the original target, issue an error |
aoqi@0 | 519 | checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface)); |
aoqi@0 | 520 | } |
vromero@2543 | 521 | //propagate constraints as per JLS 18.2.1 |
vromero@2543 | 522 | checkContext.compatible(owntype, funcInterface, types.noWarnings); |
aoqi@0 | 523 | return owntype; |
aoqi@0 | 524 | } |
aoqi@0 | 525 | } |
aoqi@0 | 526 | // </editor-fold> |
aoqi@0 | 527 | |
aoqi@0 | 528 | // <editor-fold defaultstate="collapsed" desc="Bound checking"> |
aoqi@0 | 529 | /** |
aoqi@0 | 530 | * Check bounds and perform incorporation |
aoqi@0 | 531 | */ |
aoqi@0 | 532 | void checkWithinBounds(InferenceContext inferenceContext, |
aoqi@0 | 533 | Warner warn) throws InferenceException { |
aoqi@0 | 534 | MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars); |
aoqi@0 | 535 | List<Type> saved_undet = inferenceContext.save(); |
aoqi@0 | 536 | try { |
aoqi@0 | 537 | while (true) { |
aoqi@0 | 538 | mlistener.reset(); |
aoqi@0 | 539 | if (!allowGraphInference) { |
aoqi@0 | 540 | //in legacy mode we lack of transitivity, so bound check |
aoqi@0 | 541 | //cannot be run in parallel with other incoprporation rounds |
aoqi@0 | 542 | for (Type t : inferenceContext.undetvars) { |
aoqi@0 | 543 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 544 | IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn); |
aoqi@0 | 545 | } |
aoqi@0 | 546 | } |
aoqi@0 | 547 | for (Type t : inferenceContext.undetvars) { |
aoqi@0 | 548 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 549 | //bound incorporation |
aoqi@0 | 550 | EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ? |
aoqi@0 | 551 | incorporationStepsGraph : incorporationStepsLegacy; |
aoqi@0 | 552 | for (IncorporationStep is : incorporationSteps) { |
aoqi@0 | 553 | if (is.accepts(uv, inferenceContext)) { |
aoqi@0 | 554 | is.apply(uv, inferenceContext, warn); |
aoqi@0 | 555 | } |
aoqi@0 | 556 | } |
aoqi@0 | 557 | } |
aoqi@0 | 558 | if (!mlistener.changed || !allowGraphInference) break; |
aoqi@0 | 559 | } |
aoqi@0 | 560 | } |
aoqi@0 | 561 | finally { |
aoqi@0 | 562 | mlistener.detach(); |
aoqi@0 | 563 | if (incorporationCache.size() == MAX_INCORPORATION_STEPS) { |
aoqi@0 | 564 | inferenceContext.rollback(saved_undet); |
aoqi@0 | 565 | } |
aoqi@0 | 566 | incorporationCache.clear(); |
aoqi@0 | 567 | } |
aoqi@0 | 568 | } |
aoqi@0 | 569 | //where |
aoqi@0 | 570 | /** |
aoqi@0 | 571 | * This listener keeps track of changes on a group of inference variable |
aoqi@0 | 572 | * bounds. Note: the listener must be detached (calling corresponding |
aoqi@0 | 573 | * method) to make sure that the underlying inference variable is |
aoqi@0 | 574 | * left in a clean state. |
aoqi@0 | 575 | */ |
aoqi@0 | 576 | class MultiUndetVarListener implements UndetVar.UndetVarListener { |
aoqi@0 | 577 | |
aoqi@0 | 578 | boolean changed; |
aoqi@0 | 579 | List<Type> undetvars; |
aoqi@0 | 580 | |
aoqi@0 | 581 | public MultiUndetVarListener(List<Type> undetvars) { |
aoqi@0 | 582 | this.undetvars = undetvars; |
aoqi@0 | 583 | for (Type t : undetvars) { |
aoqi@0 | 584 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 585 | uv.listener = this; |
aoqi@0 | 586 | } |
aoqi@0 | 587 | } |
aoqi@0 | 588 | |
aoqi@0 | 589 | public void varChanged(UndetVar uv, Set<InferenceBound> ibs) { |
aoqi@0 | 590 | //avoid non-termination |
aoqi@0 | 591 | if (incorporationCache.size() < MAX_INCORPORATION_STEPS) { |
aoqi@0 | 592 | changed = true; |
aoqi@0 | 593 | } |
aoqi@0 | 594 | } |
aoqi@0 | 595 | |
aoqi@0 | 596 | void reset() { |
aoqi@0 | 597 | changed = false; |
aoqi@0 | 598 | } |
aoqi@0 | 599 | |
aoqi@0 | 600 | void detach() { |
aoqi@0 | 601 | for (Type t : undetvars) { |
aoqi@0 | 602 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 603 | uv.listener = null; |
aoqi@0 | 604 | } |
aoqi@0 | 605 | } |
aoqi@0 | 606 | }; |
aoqi@0 | 607 | |
aoqi@0 | 608 | /** max number of incorporation rounds */ |
aoqi@0 | 609 | static final int MAX_INCORPORATION_STEPS = 100; |
aoqi@0 | 610 | |
aoqi@0 | 611 | /* If for two types t and s there is a least upper bound that is a |
aoqi@0 | 612 | * parameterized type G, then there exists a supertype of 't' of the form |
aoqi@0 | 613 | * G<T1, ..., Tn> and a supertype of 's' of the form G<S1, ..., Sn> |
aoqi@0 | 614 | * which will be returned by this method. If no such supertypes exists then |
aoqi@0 | 615 | * null is returned. |
aoqi@0 | 616 | * |
aoqi@0 | 617 | * As an example for the following input: |
aoqi@0 | 618 | * |
aoqi@0 | 619 | * t = java.util.ArrayList<java.lang.String> |
aoqi@0 | 620 | * s = java.util.List<T> |
aoqi@0 | 621 | * |
aoqi@0 | 622 | * we get this ouput: |
aoqi@0 | 623 | * |
aoqi@0 | 624 | * Pair[java.util.List<java.lang.String>,java.util.List<T>] |
aoqi@0 | 625 | */ |
aoqi@0 | 626 | private Pair<Type, Type> getParameterizedSupers(Type t, Type s) { |
aoqi@0 | 627 | Type lubResult = types.lub(t, s); |
aoqi@0 | 628 | if (lubResult == syms.errType || lubResult == syms.botType || |
aoqi@0 | 629 | !lubResult.isParameterized()) { |
aoqi@0 | 630 | return null; |
aoqi@0 | 631 | } |
aoqi@0 | 632 | Type asSuperOfT = types.asSuper(t, lubResult.tsym); |
aoqi@0 | 633 | Type asSuperOfS = types.asSuper(s, lubResult.tsym); |
aoqi@0 | 634 | return new Pair<>(asSuperOfT, asSuperOfS); |
aoqi@0 | 635 | } |
aoqi@0 | 636 | |
aoqi@0 | 637 | /** |
aoqi@0 | 638 | * This enumeration defines an entry point for doing inference variable |
aoqi@0 | 639 | * bound incorporation - it can be used to inject custom incorporation |
aoqi@0 | 640 | * logic into the basic bound checking routine |
aoqi@0 | 641 | */ |
aoqi@0 | 642 | enum IncorporationStep { |
aoqi@0 | 643 | /** |
aoqi@0 | 644 | * Performs basic bound checking - i.e. is the instantiated type for a given |
aoqi@0 | 645 | * inference variable compatible with its bounds? |
aoqi@0 | 646 | */ |
aoqi@0 | 647 | CHECK_BOUNDS() { |
aoqi@0 | 648 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 649 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 650 | uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types); |
aoqi@0 | 651 | infer.checkCompatibleUpperBounds(uv, inferenceContext); |
aoqi@0 | 652 | if (uv.inst != null) { |
aoqi@0 | 653 | Type inst = uv.inst; |
aoqi@0 | 654 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 655 | if (!isSubtype(inst, inferenceContext.asUndetVar(u), warn, infer)) { |
aoqi@0 | 656 | infer.reportBoundError(uv, BoundErrorKind.UPPER); |
aoqi@0 | 657 | } |
aoqi@0 | 658 | } |
aoqi@0 | 659 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 660 | if (!isSubtype(inferenceContext.asUndetVar(l), inst, warn, infer)) { |
aoqi@0 | 661 | infer.reportBoundError(uv, BoundErrorKind.LOWER); |
aoqi@0 | 662 | } |
aoqi@0 | 663 | } |
aoqi@0 | 664 | for (Type e : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 665 | if (!isSameType(inst, inferenceContext.asUndetVar(e), infer)) { |
aoqi@0 | 666 | infer.reportBoundError(uv, BoundErrorKind.EQ); |
aoqi@0 | 667 | } |
aoqi@0 | 668 | } |
aoqi@0 | 669 | } |
aoqi@0 | 670 | } |
aoqi@0 | 671 | |
aoqi@0 | 672 | @Override |
aoqi@0 | 673 | boolean accepts(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 674 | //applies to all undetvars |
aoqi@0 | 675 | return true; |
aoqi@0 | 676 | } |
aoqi@0 | 677 | }, |
aoqi@0 | 678 | /** |
aoqi@0 | 679 | * Check consistency of equality constraints. This is a slightly more aggressive |
aoqi@0 | 680 | * inference routine that is designed as to maximize compatibility with JDK 7. |
aoqi@0 | 681 | * Note: this is not used in graph mode. |
aoqi@0 | 682 | */ |
aoqi@0 | 683 | EQ_CHECK_LEGACY() { |
aoqi@0 | 684 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 685 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 686 | Type eq = null; |
aoqi@0 | 687 | for (Type e : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 688 | Assert.check(!inferenceContext.free(e)); |
aoqi@0 | 689 | if (eq != null && !isSameType(e, eq, infer)) { |
aoqi@0 | 690 | infer.reportBoundError(uv, BoundErrorKind.EQ); |
aoqi@0 | 691 | } |
aoqi@0 | 692 | eq = e; |
aoqi@0 | 693 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 694 | Assert.check(!inferenceContext.free(l)); |
aoqi@0 | 695 | if (!isSubtype(l, e, warn, infer)) { |
aoqi@0 | 696 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER); |
aoqi@0 | 697 | } |
aoqi@0 | 698 | } |
aoqi@0 | 699 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 700 | if (inferenceContext.free(u)) continue; |
aoqi@0 | 701 | if (!isSubtype(e, u, warn, infer)) { |
aoqi@0 | 702 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER); |
aoqi@0 | 703 | } |
aoqi@0 | 704 | } |
aoqi@0 | 705 | } |
aoqi@0 | 706 | } |
aoqi@0 | 707 | }, |
aoqi@0 | 708 | /** |
aoqi@0 | 709 | * Check consistency of equality constraints. |
aoqi@0 | 710 | */ |
aoqi@0 | 711 | EQ_CHECK() { |
aoqi@0 | 712 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 713 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 714 | for (Type e : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 715 | if (e.containsAny(inferenceContext.inferenceVars())) continue; |
aoqi@0 | 716 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 717 | if (!isSubtype(e, inferenceContext.asUndetVar(u), warn, infer)) { |
aoqi@0 | 718 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER); |
aoqi@0 | 719 | } |
aoqi@0 | 720 | } |
aoqi@0 | 721 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 722 | if (!isSubtype(inferenceContext.asUndetVar(l), e, warn, infer)) { |
aoqi@0 | 723 | infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER); |
aoqi@0 | 724 | } |
aoqi@0 | 725 | } |
aoqi@0 | 726 | } |
aoqi@0 | 727 | } |
aoqi@0 | 728 | }, |
aoqi@0 | 729 | /** |
aoqi@0 | 730 | * Given a bound set containing {@code alpha <: T} and {@code alpha :> S} |
aoqi@0 | 731 | * perform {@code S <: T} (which could lead to new bounds). |
aoqi@0 | 732 | */ |
aoqi@0 | 733 | CROSS_UPPER_LOWER() { |
aoqi@0 | 734 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 735 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 736 | for (Type b1 : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 737 | for (Type b2 : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 738 | isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn , infer); |
aoqi@0 | 739 | } |
aoqi@0 | 740 | } |
aoqi@0 | 741 | } |
aoqi@0 | 742 | }, |
aoqi@0 | 743 | /** |
aoqi@0 | 744 | * Given a bound set containing {@code alpha <: T} and {@code alpha == S} |
aoqi@0 | 745 | * perform {@code S <: T} (which could lead to new bounds). |
aoqi@0 | 746 | */ |
aoqi@0 | 747 | CROSS_UPPER_EQ() { |
aoqi@0 | 748 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 749 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 750 | for (Type b1 : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 751 | for (Type b2 : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 752 | isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer); |
aoqi@0 | 753 | } |
aoqi@0 | 754 | } |
aoqi@0 | 755 | } |
aoqi@0 | 756 | }, |
aoqi@0 | 757 | /** |
aoqi@0 | 758 | * Given a bound set containing {@code alpha :> S} and {@code alpha == T} |
aoqi@0 | 759 | * perform {@code S <: T} (which could lead to new bounds). |
aoqi@0 | 760 | */ |
aoqi@0 | 761 | CROSS_EQ_LOWER() { |
aoqi@0 | 762 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 763 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 764 | for (Type b1 : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 765 | for (Type b2 : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 766 | isSubtype(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), warn, infer); |
aoqi@0 | 767 | } |
aoqi@0 | 768 | } |
aoqi@0 | 769 | } |
aoqi@0 | 770 | }, |
aoqi@0 | 771 | /** |
aoqi@0 | 772 | * Given a bound set containing {@code alpha <: P<T>} and |
aoqi@0 | 773 | * {@code alpha <: P<S>} where P is a parameterized type, |
aoqi@0 | 774 | * perform {@code T = S} (which could lead to new bounds). |
aoqi@0 | 775 | */ |
aoqi@0 | 776 | CROSS_UPPER_UPPER() { |
aoqi@0 | 777 | @Override |
aoqi@0 | 778 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 779 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 780 | List<Type> boundList = uv.getBounds(InferenceBound.UPPER); |
aoqi@0 | 781 | List<Type> boundListTail = boundList.tail; |
aoqi@0 | 782 | while (boundList.nonEmpty()) { |
aoqi@0 | 783 | List<Type> tmpTail = boundListTail; |
aoqi@0 | 784 | while (tmpTail.nonEmpty()) { |
aoqi@0 | 785 | Type b1 = boundList.head; |
aoqi@0 | 786 | Type b2 = tmpTail.head; |
vromero@2601 | 787 | /* This wildcard check is temporary workaround. This code may need to be |
vromero@2601 | 788 | * revisited once spec bug JDK-7034922 is fixed. |
vromero@2601 | 789 | */ |
vromero@2601 | 790 | if (b1 != b2 && !b1.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) { |
aoqi@0 | 791 | Pair<Type, Type> commonSupers = infer.getParameterizedSupers(b1, b2); |
aoqi@0 | 792 | if (commonSupers != null) { |
aoqi@0 | 793 | List<Type> allParamsSuperBound1 = commonSupers.fst.allparams(); |
aoqi@0 | 794 | List<Type> allParamsSuperBound2 = commonSupers.snd.allparams(); |
aoqi@0 | 795 | while (allParamsSuperBound1.nonEmpty() && allParamsSuperBound2.nonEmpty()) { |
aoqi@0 | 796 | //traverse the list of all params comparing them |
aoqi@0 | 797 | if (!allParamsSuperBound1.head.hasTag(WILDCARD) && |
aoqi@0 | 798 | !allParamsSuperBound2.head.hasTag(WILDCARD)) { |
aoqi@0 | 799 | isSameType(inferenceContext.asUndetVar(allParamsSuperBound1.head), |
aoqi@0 | 800 | inferenceContext.asUndetVar(allParamsSuperBound2.head), infer); |
aoqi@0 | 801 | } |
aoqi@0 | 802 | allParamsSuperBound1 = allParamsSuperBound1.tail; |
aoqi@0 | 803 | allParamsSuperBound2 = allParamsSuperBound2.tail; |
aoqi@0 | 804 | } |
aoqi@0 | 805 | Assert.check(allParamsSuperBound1.isEmpty() && allParamsSuperBound2.isEmpty()); |
aoqi@0 | 806 | } |
aoqi@0 | 807 | } |
aoqi@0 | 808 | tmpTail = tmpTail.tail; |
aoqi@0 | 809 | } |
aoqi@0 | 810 | boundList = boundList.tail; |
aoqi@0 | 811 | boundListTail = boundList.tail; |
aoqi@0 | 812 | } |
aoqi@0 | 813 | } |
aoqi@0 | 814 | |
aoqi@0 | 815 | @Override |
aoqi@0 | 816 | boolean accepts(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 817 | return !uv.isCaptured() && |
aoqi@0 | 818 | uv.getBounds(InferenceBound.UPPER).nonEmpty(); |
aoqi@0 | 819 | } |
aoqi@0 | 820 | }, |
aoqi@0 | 821 | /** |
aoqi@0 | 822 | * Given a bound set containing {@code alpha == S} and {@code alpha == T} |
aoqi@0 | 823 | * perform {@code S == T} (which could lead to new bounds). |
aoqi@0 | 824 | */ |
aoqi@0 | 825 | CROSS_EQ_EQ() { |
aoqi@0 | 826 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 827 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 828 | for (Type b1 : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 829 | for (Type b2 : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 830 | if (b1 != b2) { |
aoqi@0 | 831 | isSameType(inferenceContext.asUndetVar(b2), inferenceContext.asUndetVar(b1), infer); |
aoqi@0 | 832 | } |
aoqi@0 | 833 | } |
aoqi@0 | 834 | } |
aoqi@0 | 835 | } |
aoqi@0 | 836 | }, |
aoqi@0 | 837 | /** |
aoqi@0 | 838 | * Given a bound set containing {@code alpha <: beta} propagate lower bounds |
aoqi@0 | 839 | * from alpha to beta; also propagate upper bounds from beta to alpha. |
aoqi@0 | 840 | */ |
aoqi@0 | 841 | PROP_UPPER() { |
aoqi@0 | 842 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 843 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 844 | for (Type b : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 845 | if (inferenceContext.inferenceVars().contains(b)) { |
aoqi@0 | 846 | UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b); |
aoqi@0 | 847 | if (uv2.isCaptured()) continue; |
aoqi@0 | 848 | //alpha <: beta |
aoqi@0 | 849 | //0. set beta :> alpha |
aoqi@0 | 850 | addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer); |
aoqi@0 | 851 | //1. copy alpha's lower to beta's |
aoqi@0 | 852 | for (Type l : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 853 | addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(l), infer); |
aoqi@0 | 854 | } |
aoqi@0 | 855 | //2. copy beta's upper to alpha's |
aoqi@0 | 856 | for (Type u : uv2.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 857 | addBound(InferenceBound.UPPER, uv, inferenceContext.asInstType(u), infer); |
aoqi@0 | 858 | } |
aoqi@0 | 859 | } |
aoqi@0 | 860 | } |
aoqi@0 | 861 | } |
aoqi@0 | 862 | }, |
aoqi@0 | 863 | /** |
aoqi@0 | 864 | * Given a bound set containing {@code alpha :> beta} propagate lower bounds |
aoqi@0 | 865 | * from beta to alpha; also propagate upper bounds from alpha to beta. |
aoqi@0 | 866 | */ |
aoqi@0 | 867 | PROP_LOWER() { |
aoqi@0 | 868 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 869 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 870 | for (Type b : uv.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 871 | if (inferenceContext.inferenceVars().contains(b)) { |
aoqi@0 | 872 | UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b); |
aoqi@0 | 873 | if (uv2.isCaptured()) continue; |
aoqi@0 | 874 | //alpha :> beta |
aoqi@0 | 875 | //0. set beta <: alpha |
aoqi@0 | 876 | addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer); |
aoqi@0 | 877 | //1. copy alpha's upper to beta's |
aoqi@0 | 878 | for (Type u : uv.getBounds(InferenceBound.UPPER)) { |
aoqi@0 | 879 | addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(u), infer); |
aoqi@0 | 880 | } |
aoqi@0 | 881 | //2. copy beta's lower to alpha's |
aoqi@0 | 882 | for (Type l : uv2.getBounds(InferenceBound.LOWER)) { |
aoqi@0 | 883 | addBound(InferenceBound.LOWER, uv, inferenceContext.asInstType(l), infer); |
aoqi@0 | 884 | } |
aoqi@0 | 885 | } |
aoqi@0 | 886 | } |
aoqi@0 | 887 | } |
aoqi@0 | 888 | }, |
aoqi@0 | 889 | /** |
aoqi@0 | 890 | * Given a bound set containing {@code alpha == beta} propagate lower/upper |
aoqi@0 | 891 | * bounds from alpha to beta and back. |
aoqi@0 | 892 | */ |
aoqi@0 | 893 | PROP_EQ() { |
aoqi@0 | 894 | public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) { |
aoqi@0 | 895 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 896 | for (Type b : uv.getBounds(InferenceBound.EQ)) { |
aoqi@0 | 897 | if (inferenceContext.inferenceVars().contains(b)) { |
aoqi@0 | 898 | UndetVar uv2 = (UndetVar)inferenceContext.asUndetVar(b); |
aoqi@0 | 899 | if (uv2.isCaptured()) continue; |
aoqi@0 | 900 | //alpha == beta |
aoqi@0 | 901 | //0. set beta == alpha |
aoqi@0 | 902 | addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer); |
aoqi@0 | 903 | //1. copy all alpha's bounds to beta's |
aoqi@0 | 904 | for (InferenceBound ib : InferenceBound.values()) { |
aoqi@0 | 905 | for (Type b2 : uv.getBounds(ib)) { |
aoqi@0 | 906 | if (b2 != uv2) { |
aoqi@0 | 907 | addBound(ib, uv2, inferenceContext.asInstType(b2), infer); |
aoqi@0 | 908 | } |
aoqi@0 | 909 | } |
aoqi@0 | 910 | } |
aoqi@0 | 911 | //2. copy all beta's bounds to alpha's |
aoqi@0 | 912 | for (InferenceBound ib : InferenceBound.values()) { |
aoqi@0 | 913 | for (Type b2 : uv2.getBounds(ib)) { |
aoqi@0 | 914 | if (b2 != uv) { |
aoqi@0 | 915 | addBound(ib, uv, inferenceContext.asInstType(b2), infer); |
aoqi@0 | 916 | } |
aoqi@0 | 917 | } |
aoqi@0 | 918 | } |
aoqi@0 | 919 | } |
aoqi@0 | 920 | } |
aoqi@0 | 921 | } |
aoqi@0 | 922 | }; |
aoqi@0 | 923 | |
aoqi@0 | 924 | abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn); |
aoqi@0 | 925 | |
aoqi@0 | 926 | boolean accepts(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 927 | return !uv.isCaptured(); |
aoqi@0 | 928 | } |
aoqi@0 | 929 | |
aoqi@0 | 930 | boolean isSubtype(Type s, Type t, Warner warn, Infer infer) { |
aoqi@0 | 931 | return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer); |
aoqi@0 | 932 | } |
aoqi@0 | 933 | |
aoqi@0 | 934 | boolean isSameType(Type s, Type t, Infer infer) { |
aoqi@0 | 935 | return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer); |
aoqi@0 | 936 | } |
aoqi@0 | 937 | |
aoqi@0 | 938 | void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) { |
aoqi@0 | 939 | doIncorporationOp(opFor(ib), uv, b, null, infer); |
aoqi@0 | 940 | } |
aoqi@0 | 941 | |
aoqi@0 | 942 | IncorporationBinaryOpKind opFor(InferenceBound boundKind) { |
aoqi@0 | 943 | switch (boundKind) { |
aoqi@0 | 944 | case EQ: |
aoqi@0 | 945 | return IncorporationBinaryOpKind.ADD_EQ_BOUND; |
aoqi@0 | 946 | case LOWER: |
aoqi@0 | 947 | return IncorporationBinaryOpKind.ADD_LOWER_BOUND; |
aoqi@0 | 948 | case UPPER: |
aoqi@0 | 949 | return IncorporationBinaryOpKind.ADD_UPPER_BOUND; |
aoqi@0 | 950 | default: |
aoqi@0 | 951 | Assert.error("Can't get here!"); |
aoqi@0 | 952 | return null; |
aoqi@0 | 953 | } |
aoqi@0 | 954 | } |
aoqi@0 | 955 | |
aoqi@0 | 956 | boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) { |
aoqi@0 | 957 | IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2); |
aoqi@0 | 958 | Boolean res = infer.incorporationCache.get(newOp); |
aoqi@0 | 959 | if (res == null) { |
aoqi@0 | 960 | infer.incorporationCache.put(newOp, res = newOp.apply(warn)); |
aoqi@0 | 961 | } |
aoqi@0 | 962 | return res; |
aoqi@0 | 963 | } |
aoqi@0 | 964 | } |
aoqi@0 | 965 | |
aoqi@0 | 966 | /** incorporation steps to be executed when running in legacy mode */ |
aoqi@0 | 967 | EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY); |
aoqi@0 | 968 | |
aoqi@0 | 969 | /** incorporation steps to be executed when running in graph mode */ |
aoqi@0 | 970 | EnumSet<IncorporationStep> incorporationStepsGraph = |
aoqi@0 | 971 | EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY)); |
aoqi@0 | 972 | |
aoqi@0 | 973 | /** |
aoqi@0 | 974 | * Three kinds of basic operation are supported as part of an incorporation step: |
aoqi@0 | 975 | * (i) subtype check, (ii) same type check and (iii) bound addition (either |
aoqi@0 | 976 | * upper/lower/eq bound). |
aoqi@0 | 977 | */ |
aoqi@0 | 978 | enum IncorporationBinaryOpKind { |
aoqi@0 | 979 | IS_SUBTYPE() { |
aoqi@0 | 980 | @Override |
aoqi@0 | 981 | boolean apply(Type op1, Type op2, Warner warn, Types types) { |
aoqi@0 | 982 | return types.isSubtypeUnchecked(op1, op2, warn); |
aoqi@0 | 983 | } |
aoqi@0 | 984 | }, |
aoqi@0 | 985 | IS_SAME_TYPE() { |
aoqi@0 | 986 | @Override |
aoqi@0 | 987 | boolean apply(Type op1, Type op2, Warner warn, Types types) { |
aoqi@0 | 988 | return types.isSameType(op1, op2); |
aoqi@0 | 989 | } |
aoqi@0 | 990 | }, |
aoqi@0 | 991 | ADD_UPPER_BOUND() { |
aoqi@0 | 992 | @Override |
aoqi@0 | 993 | boolean apply(Type op1, Type op2, Warner warn, Types types) { |
aoqi@0 | 994 | UndetVar uv = (UndetVar)op1; |
aoqi@0 | 995 | uv.addBound(InferenceBound.UPPER, op2, types); |
aoqi@0 | 996 | return true; |
aoqi@0 | 997 | } |
aoqi@0 | 998 | }, |
aoqi@0 | 999 | ADD_LOWER_BOUND() { |
aoqi@0 | 1000 | @Override |
aoqi@0 | 1001 | boolean apply(Type op1, Type op2, Warner warn, Types types) { |
aoqi@0 | 1002 | UndetVar uv = (UndetVar)op1; |
aoqi@0 | 1003 | uv.addBound(InferenceBound.LOWER, op2, types); |
aoqi@0 | 1004 | return true; |
aoqi@0 | 1005 | } |
aoqi@0 | 1006 | }, |
aoqi@0 | 1007 | ADD_EQ_BOUND() { |
aoqi@0 | 1008 | @Override |
aoqi@0 | 1009 | boolean apply(Type op1, Type op2, Warner warn, Types types) { |
aoqi@0 | 1010 | UndetVar uv = (UndetVar)op1; |
aoqi@0 | 1011 | uv.addBound(InferenceBound.EQ, op2, types); |
aoqi@0 | 1012 | return true; |
aoqi@0 | 1013 | } |
aoqi@0 | 1014 | }; |
aoqi@0 | 1015 | |
aoqi@0 | 1016 | abstract boolean apply(Type op1, Type op2, Warner warn, Types types); |
aoqi@0 | 1017 | } |
aoqi@0 | 1018 | |
aoqi@0 | 1019 | /** |
aoqi@0 | 1020 | * This class encapsulates a basic incorporation operation; incorporation |
aoqi@0 | 1021 | * operations takes two type operands and a kind. Each operation performed |
aoqi@0 | 1022 | * during an incorporation round is stored in a cache, so that operations |
aoqi@0 | 1023 | * are not executed unnecessarily (which would potentially lead to adding |
aoqi@0 | 1024 | * same bounds over and over). |
aoqi@0 | 1025 | */ |
aoqi@0 | 1026 | class IncorporationBinaryOp { |
aoqi@0 | 1027 | |
aoqi@0 | 1028 | IncorporationBinaryOpKind opKind; |
aoqi@0 | 1029 | Type op1; |
aoqi@0 | 1030 | Type op2; |
aoqi@0 | 1031 | |
aoqi@0 | 1032 | IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) { |
aoqi@0 | 1033 | this.opKind = opKind; |
aoqi@0 | 1034 | this.op1 = op1; |
aoqi@0 | 1035 | this.op2 = op2; |
aoqi@0 | 1036 | } |
aoqi@0 | 1037 | |
aoqi@0 | 1038 | @Override |
aoqi@0 | 1039 | public boolean equals(Object o) { |
aoqi@0 | 1040 | if (!(o instanceof IncorporationBinaryOp)) { |
aoqi@0 | 1041 | return false; |
aoqi@0 | 1042 | } else { |
aoqi@0 | 1043 | IncorporationBinaryOp that = (IncorporationBinaryOp)o; |
aoqi@0 | 1044 | return opKind == that.opKind && |
aoqi@0 | 1045 | types.isSameType(op1, that.op1, true) && |
aoqi@0 | 1046 | types.isSameType(op2, that.op2, true); |
aoqi@0 | 1047 | } |
aoqi@0 | 1048 | } |
aoqi@0 | 1049 | |
aoqi@0 | 1050 | @Override |
aoqi@0 | 1051 | public int hashCode() { |
aoqi@0 | 1052 | int result = opKind.hashCode(); |
aoqi@0 | 1053 | result *= 127; |
aoqi@0 | 1054 | result += types.hashCode(op1); |
aoqi@0 | 1055 | result *= 127; |
aoqi@0 | 1056 | result += types.hashCode(op2); |
aoqi@0 | 1057 | return result; |
aoqi@0 | 1058 | } |
aoqi@0 | 1059 | |
aoqi@0 | 1060 | boolean apply(Warner warn) { |
aoqi@0 | 1061 | return opKind.apply(op1, op2, warn, types); |
aoqi@0 | 1062 | } |
aoqi@0 | 1063 | } |
aoqi@0 | 1064 | |
aoqi@0 | 1065 | /** an incorporation cache keeps track of all executed incorporation-related operations */ |
aoqi@0 | 1066 | Map<IncorporationBinaryOp, Boolean> incorporationCache = |
aoqi@0 | 1067 | new HashMap<IncorporationBinaryOp, Boolean>(); |
aoqi@0 | 1068 | |
aoqi@0 | 1069 | /** |
aoqi@0 | 1070 | * Make sure that the upper bounds we got so far lead to a solvable inference |
aoqi@0 | 1071 | * variable by making sure that a glb exists. |
aoqi@0 | 1072 | */ |
aoqi@0 | 1073 | void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1074 | List<Type> hibounds = |
aoqi@0 | 1075 | Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext)); |
aoqi@0 | 1076 | Type hb = null; |
aoqi@0 | 1077 | if (hibounds.isEmpty()) |
aoqi@0 | 1078 | hb = syms.objectType; |
aoqi@0 | 1079 | else if (hibounds.tail.isEmpty()) |
aoqi@0 | 1080 | hb = hibounds.head; |
aoqi@0 | 1081 | else |
aoqi@0 | 1082 | hb = types.glb(hibounds); |
aoqi@0 | 1083 | if (hb == null || hb.isErroneous()) |
aoqi@0 | 1084 | reportBoundError(uv, BoundErrorKind.BAD_UPPER); |
aoqi@0 | 1085 | } |
aoqi@0 | 1086 | //where |
aoqi@0 | 1087 | protected static class BoundFilter implements Filter<Type> { |
aoqi@0 | 1088 | |
aoqi@0 | 1089 | InferenceContext inferenceContext; |
aoqi@0 | 1090 | |
aoqi@0 | 1091 | public BoundFilter(InferenceContext inferenceContext) { |
aoqi@0 | 1092 | this.inferenceContext = inferenceContext; |
aoqi@0 | 1093 | } |
aoqi@0 | 1094 | |
aoqi@0 | 1095 | @Override |
aoqi@0 | 1096 | public boolean accepts(Type t) { |
aoqi@0 | 1097 | return !t.isErroneous() && !inferenceContext.free(t) && |
aoqi@0 | 1098 | !t.hasTag(BOT); |
aoqi@0 | 1099 | } |
aoqi@0 | 1100 | }; |
aoqi@0 | 1101 | |
aoqi@0 | 1102 | /** |
aoqi@0 | 1103 | * This enumeration defines all possible bound-checking related errors. |
aoqi@0 | 1104 | */ |
aoqi@0 | 1105 | enum BoundErrorKind { |
aoqi@0 | 1106 | /** |
aoqi@0 | 1107 | * The (uninstantiated) inference variable has incompatible upper bounds. |
aoqi@0 | 1108 | */ |
aoqi@0 | 1109 | BAD_UPPER() { |
aoqi@0 | 1110 | @Override |
aoqi@0 | 1111 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
aoqi@0 | 1112 | return ex.setMessage("incompatible.upper.bounds", uv.qtype, |
aoqi@0 | 1113 | uv.getBounds(InferenceBound.UPPER)); |
aoqi@0 | 1114 | } |
aoqi@0 | 1115 | }, |
aoqi@0 | 1116 | /** |
aoqi@0 | 1117 | * An equality constraint is not compatible with an upper bound. |
aoqi@0 | 1118 | */ |
aoqi@0 | 1119 | BAD_EQ_UPPER() { |
aoqi@0 | 1120 | @Override |
aoqi@0 | 1121 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
aoqi@0 | 1122 | return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype, |
aoqi@0 | 1123 | uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER)); |
aoqi@0 | 1124 | } |
aoqi@0 | 1125 | }, |
aoqi@0 | 1126 | /** |
aoqi@0 | 1127 | * An equality constraint is not compatible with a lower bound. |
aoqi@0 | 1128 | */ |
aoqi@0 | 1129 | BAD_EQ_LOWER() { |
aoqi@0 | 1130 | @Override |
aoqi@0 | 1131 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
aoqi@0 | 1132 | return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype, |
aoqi@0 | 1133 | uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER)); |
aoqi@0 | 1134 | } |
aoqi@0 | 1135 | }, |
aoqi@0 | 1136 | /** |
aoqi@0 | 1137 | * Instantiated inference variable is not compatible with an upper bound. |
aoqi@0 | 1138 | */ |
aoqi@0 | 1139 | UPPER() { |
aoqi@0 | 1140 | @Override |
aoqi@0 | 1141 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
aoqi@0 | 1142 | return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst, |
aoqi@0 | 1143 | uv.getBounds(InferenceBound.UPPER)); |
aoqi@0 | 1144 | } |
aoqi@0 | 1145 | }, |
aoqi@0 | 1146 | /** |
aoqi@0 | 1147 | * Instantiated inference variable is not compatible with a lower bound. |
aoqi@0 | 1148 | */ |
aoqi@0 | 1149 | LOWER() { |
aoqi@0 | 1150 | @Override |
aoqi@0 | 1151 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
aoqi@0 | 1152 | return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst, |
aoqi@0 | 1153 | uv.getBounds(InferenceBound.LOWER)); |
aoqi@0 | 1154 | } |
aoqi@0 | 1155 | }, |
aoqi@0 | 1156 | /** |
aoqi@0 | 1157 | * Instantiated inference variable is not compatible with an equality constraint. |
aoqi@0 | 1158 | */ |
aoqi@0 | 1159 | EQ() { |
aoqi@0 | 1160 | @Override |
aoqi@0 | 1161 | InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) { |
aoqi@0 | 1162 | return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst, |
aoqi@0 | 1163 | uv.getBounds(InferenceBound.EQ)); |
aoqi@0 | 1164 | } |
aoqi@0 | 1165 | }; |
aoqi@0 | 1166 | |
aoqi@0 | 1167 | abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv); |
aoqi@0 | 1168 | } |
aoqi@0 | 1169 | |
aoqi@0 | 1170 | /** |
aoqi@0 | 1171 | * Report a bound-checking error of given kind |
aoqi@0 | 1172 | */ |
aoqi@0 | 1173 | void reportBoundError(UndetVar uv, BoundErrorKind bk) { |
aoqi@0 | 1174 | throw bk.setMessage(inferenceException, uv); |
aoqi@0 | 1175 | } |
aoqi@0 | 1176 | // </editor-fold> |
aoqi@0 | 1177 | |
aoqi@0 | 1178 | // <editor-fold defaultstate="collapsed" desc="Inference engine"> |
aoqi@0 | 1179 | /** |
aoqi@0 | 1180 | * Graph inference strategy - act as an input to the inference solver; a strategy is |
aoqi@0 | 1181 | * composed of two ingredients: (i) find a node to solve in the inference graph, |
aoqi@0 | 1182 | * and (ii) tell th engine when we are done fixing inference variables |
aoqi@0 | 1183 | */ |
aoqi@0 | 1184 | interface GraphStrategy { |
aoqi@0 | 1185 | |
aoqi@0 | 1186 | /** |
aoqi@0 | 1187 | * A NodeNotFoundException is thrown whenever an inference strategy fails |
aoqi@0 | 1188 | * to pick the next node to solve in the inference graph. |
aoqi@0 | 1189 | */ |
aoqi@0 | 1190 | public static class NodeNotFoundException extends RuntimeException { |
aoqi@0 | 1191 | private static final long serialVersionUID = 0; |
aoqi@0 | 1192 | |
aoqi@0 | 1193 | InferenceGraph graph; |
aoqi@0 | 1194 | |
aoqi@0 | 1195 | public NodeNotFoundException(InferenceGraph graph) { |
aoqi@0 | 1196 | this.graph = graph; |
aoqi@0 | 1197 | } |
aoqi@0 | 1198 | } |
aoqi@0 | 1199 | /** |
aoqi@0 | 1200 | * Pick the next node (leaf) to solve in the graph |
aoqi@0 | 1201 | */ |
aoqi@0 | 1202 | Node pickNode(InferenceGraph g) throws NodeNotFoundException; |
aoqi@0 | 1203 | /** |
aoqi@0 | 1204 | * Is this the last step? |
aoqi@0 | 1205 | */ |
aoqi@0 | 1206 | boolean done(); |
aoqi@0 | 1207 | } |
aoqi@0 | 1208 | |
aoqi@0 | 1209 | /** |
aoqi@0 | 1210 | * Simple solver strategy class that locates all leaves inside a graph |
aoqi@0 | 1211 | * and picks the first leaf as the next node to solve |
aoqi@0 | 1212 | */ |
aoqi@0 | 1213 | abstract class LeafSolver implements GraphStrategy { |
aoqi@0 | 1214 | public Node pickNode(InferenceGraph g) { |
aoqi@0 | 1215 | if (g.nodes.isEmpty()) { |
aoqi@0 | 1216 | //should not happen |
aoqi@0 | 1217 | throw new NodeNotFoundException(g); |
aoqi@0 | 1218 | }; |
aoqi@0 | 1219 | return g.nodes.get(0); |
aoqi@0 | 1220 | } |
aoqi@0 | 1221 | |
aoqi@0 | 1222 | boolean isSubtype(Type s, Type t, Warner warn, Infer infer) { |
aoqi@0 | 1223 | return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer); |
aoqi@0 | 1224 | } |
aoqi@0 | 1225 | |
aoqi@0 | 1226 | boolean isSameType(Type s, Type t, Infer infer) { |
aoqi@0 | 1227 | return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer); |
aoqi@0 | 1228 | } |
aoqi@0 | 1229 | |
aoqi@0 | 1230 | void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) { |
aoqi@0 | 1231 | doIncorporationOp(opFor(ib), uv, b, null, infer); |
aoqi@0 | 1232 | } |
aoqi@0 | 1233 | |
aoqi@0 | 1234 | IncorporationBinaryOpKind opFor(InferenceBound boundKind) { |
aoqi@0 | 1235 | switch (boundKind) { |
aoqi@0 | 1236 | case EQ: |
aoqi@0 | 1237 | return IncorporationBinaryOpKind.ADD_EQ_BOUND; |
aoqi@0 | 1238 | case LOWER: |
aoqi@0 | 1239 | return IncorporationBinaryOpKind.ADD_LOWER_BOUND; |
aoqi@0 | 1240 | case UPPER: |
aoqi@0 | 1241 | return IncorporationBinaryOpKind.ADD_UPPER_BOUND; |
aoqi@0 | 1242 | default: |
aoqi@0 | 1243 | Assert.error("Can't get here!"); |
aoqi@0 | 1244 | return null; |
aoqi@0 | 1245 | } |
aoqi@0 | 1246 | } |
aoqi@0 | 1247 | |
aoqi@0 | 1248 | boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) { |
aoqi@0 | 1249 | IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2); |
aoqi@0 | 1250 | Boolean res = infer.incorporationCache.get(newOp); |
aoqi@0 | 1251 | if (res == null) { |
aoqi@0 | 1252 | infer.incorporationCache.put(newOp, res = newOp.apply(warn)); |
aoqi@0 | 1253 | } |
aoqi@0 | 1254 | return res; |
aoqi@0 | 1255 | } |
aoqi@0 | 1256 | } |
aoqi@0 | 1257 | |
aoqi@0 | 1258 | /** |
aoqi@0 | 1259 | * This solver uses an heuristic to pick the best leaf - the heuristic |
aoqi@0 | 1260 | * tries to select the node that has maximal probability to contain one |
aoqi@0 | 1261 | * or more inference variables in a given list |
aoqi@0 | 1262 | */ |
aoqi@0 | 1263 | abstract class BestLeafSolver extends LeafSolver { |
aoqi@0 | 1264 | |
aoqi@0 | 1265 | /** list of ivars of which at least one must be solved */ |
aoqi@0 | 1266 | List<Type> varsToSolve; |
aoqi@0 | 1267 | |
aoqi@0 | 1268 | BestLeafSolver(List<Type> varsToSolve) { |
aoqi@0 | 1269 | this.varsToSolve = varsToSolve; |
aoqi@0 | 1270 | } |
aoqi@0 | 1271 | |
aoqi@0 | 1272 | /** |
aoqi@0 | 1273 | * Computes a path that goes from a given node to the leafs in the graph. |
aoqi@0 | 1274 | * Typically this will start from a node containing a variable in |
aoqi@0 | 1275 | * {@code varsToSolve}. For any given path, the cost is computed as the total |
aoqi@0 | 1276 | * number of type-variables that should be eagerly instantiated across that path. |
aoqi@0 | 1277 | */ |
aoqi@0 | 1278 | Pair<List<Node>, Integer> computeTreeToLeafs(Node n) { |
aoqi@0 | 1279 | Pair<List<Node>, Integer> cachedPath = treeCache.get(n); |
aoqi@0 | 1280 | if (cachedPath == null) { |
aoqi@0 | 1281 | //cache miss |
aoqi@0 | 1282 | if (n.isLeaf()) { |
aoqi@0 | 1283 | //if leaf, stop |
aoqi@0 | 1284 | cachedPath = new Pair<List<Node>, Integer>(List.of(n), n.data.length()); |
aoqi@0 | 1285 | } else { |
aoqi@0 | 1286 | //if non-leaf, proceed recursively |
aoqi@0 | 1287 | Pair<List<Node>, Integer> path = new Pair<List<Node>, Integer>(List.of(n), n.data.length()); |
aoqi@0 | 1288 | for (Node n2 : n.getAllDependencies()) { |
aoqi@0 | 1289 | if (n2 == n) continue; |
aoqi@0 | 1290 | Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2); |
aoqi@0 | 1291 | path = new Pair<List<Node>, Integer>( |
aoqi@0 | 1292 | path.fst.prependList(subpath.fst), |
aoqi@0 | 1293 | path.snd + subpath.snd); |
aoqi@0 | 1294 | } |
aoqi@0 | 1295 | cachedPath = path; |
aoqi@0 | 1296 | } |
aoqi@0 | 1297 | //save results in cache |
aoqi@0 | 1298 | treeCache.put(n, cachedPath); |
aoqi@0 | 1299 | } |
aoqi@0 | 1300 | return cachedPath; |
aoqi@0 | 1301 | } |
aoqi@0 | 1302 | |
aoqi@0 | 1303 | /** cache used to avoid redundant computation of tree costs */ |
aoqi@0 | 1304 | final Map<Node, Pair<List<Node>, Integer>> treeCache = |
aoqi@0 | 1305 | new HashMap<Node, Pair<List<Node>, Integer>>(); |
aoqi@0 | 1306 | |
aoqi@0 | 1307 | /** constant value used to mark non-existent paths */ |
aoqi@0 | 1308 | final Pair<List<Node>, Integer> noPath = |
aoqi@0 | 1309 | new Pair<List<Node>, Integer>(null, Integer.MAX_VALUE); |
aoqi@0 | 1310 | |
aoqi@0 | 1311 | /** |
aoqi@0 | 1312 | * Pick the leaf that minimize cost |
aoqi@0 | 1313 | */ |
aoqi@0 | 1314 | @Override |
aoqi@0 | 1315 | public Node pickNode(final InferenceGraph g) { |
aoqi@0 | 1316 | treeCache.clear(); //graph changes at every step - cache must be cleared |
aoqi@0 | 1317 | Pair<List<Node>, Integer> bestPath = noPath; |
aoqi@0 | 1318 | for (Node n : g.nodes) { |
aoqi@0 | 1319 | if (!Collections.disjoint(n.data, varsToSolve)) { |
aoqi@0 | 1320 | Pair<List<Node>, Integer> path = computeTreeToLeafs(n); |
aoqi@0 | 1321 | //discard all paths containing at least a node in the |
aoqi@0 | 1322 | //closure computed above |
aoqi@0 | 1323 | if (path.snd < bestPath.snd) { |
aoqi@0 | 1324 | bestPath = path; |
aoqi@0 | 1325 | } |
aoqi@0 | 1326 | } |
aoqi@0 | 1327 | } |
aoqi@0 | 1328 | if (bestPath == noPath) { |
aoqi@0 | 1329 | //no path leads there |
aoqi@0 | 1330 | throw new NodeNotFoundException(g); |
aoqi@0 | 1331 | } |
aoqi@0 | 1332 | return bestPath.fst.head; |
aoqi@0 | 1333 | } |
aoqi@0 | 1334 | } |
aoqi@0 | 1335 | |
aoqi@0 | 1336 | /** |
aoqi@0 | 1337 | * The inference process can be thought of as a sequence of steps. Each step |
aoqi@0 | 1338 | * instantiates an inference variable using a subset of the inference variable |
aoqi@0 | 1339 | * bounds, if certain condition are met. Decisions such as the sequence in which |
aoqi@0 | 1340 | * steps are applied, or which steps are to be applied are left to the inference engine. |
aoqi@0 | 1341 | */ |
aoqi@0 | 1342 | enum InferenceStep { |
aoqi@0 | 1343 | |
aoqi@0 | 1344 | /** |
aoqi@0 | 1345 | * Instantiate an inference variables using one of its (ground) equality |
aoqi@0 | 1346 | * constraints |
aoqi@0 | 1347 | */ |
aoqi@0 | 1348 | EQ(InferenceBound.EQ) { |
aoqi@0 | 1349 | @Override |
aoqi@0 | 1350 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1351 | return filterBounds(uv, inferenceContext).head; |
aoqi@0 | 1352 | } |
aoqi@0 | 1353 | }, |
aoqi@0 | 1354 | /** |
aoqi@0 | 1355 | * Instantiate an inference variables using its (ground) lower bounds. Such |
aoqi@0 | 1356 | * bounds are merged together using lub(). |
aoqi@0 | 1357 | */ |
aoqi@0 | 1358 | LOWER(InferenceBound.LOWER) { |
aoqi@0 | 1359 | @Override |
aoqi@0 | 1360 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1361 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 1362 | List<Type> lobounds = filterBounds(uv, inferenceContext); |
aoqi@0 | 1363 | //note: lobounds should have at least one element |
aoqi@0 | 1364 | Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds); |
aoqi@0 | 1365 | if (owntype.isPrimitive() || owntype.hasTag(ERROR)) { |
aoqi@0 | 1366 | throw infer.inferenceException |
aoqi@0 | 1367 | .setMessage("no.unique.minimal.instance.exists", |
aoqi@0 | 1368 | uv.qtype, lobounds); |
aoqi@0 | 1369 | } else { |
aoqi@0 | 1370 | return owntype; |
aoqi@0 | 1371 | } |
aoqi@0 | 1372 | } |
aoqi@0 | 1373 | }, |
aoqi@0 | 1374 | /** |
aoqi@0 | 1375 | * Infer uninstantiated/unbound inference variables occurring in 'throws' |
aoqi@0 | 1376 | * clause as RuntimeException |
aoqi@0 | 1377 | */ |
aoqi@0 | 1378 | THROWS(InferenceBound.UPPER) { |
aoqi@0 | 1379 | @Override |
aoqi@0 | 1380 | public boolean accepts(UndetVar t, InferenceContext inferenceContext) { |
aoqi@0 | 1381 | if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) { |
aoqi@0 | 1382 | //not a throws undet var |
aoqi@0 | 1383 | return false; |
aoqi@0 | 1384 | } |
aoqi@0 | 1385 | if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER) |
aoqi@0 | 1386 | .diff(t.getDeclaredBounds()).nonEmpty()) { |
aoqi@0 | 1387 | //not an unbounded undet var |
aoqi@0 | 1388 | return false; |
aoqi@0 | 1389 | } |
aoqi@0 | 1390 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 1391 | for (Type db : t.getDeclaredBounds()) { |
aoqi@0 | 1392 | if (t.isInterface()) continue; |
aoqi@0 | 1393 | if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) { |
aoqi@0 | 1394 | //declared bound is a supertype of RuntimeException |
aoqi@0 | 1395 | return true; |
aoqi@0 | 1396 | } |
aoqi@0 | 1397 | } |
aoqi@0 | 1398 | //declared bound is more specific then RuntimeException - give up |
aoqi@0 | 1399 | return false; |
aoqi@0 | 1400 | } |
aoqi@0 | 1401 | |
aoqi@0 | 1402 | @Override |
aoqi@0 | 1403 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1404 | return inferenceContext.infer().syms.runtimeExceptionType; |
aoqi@0 | 1405 | } |
aoqi@0 | 1406 | }, |
aoqi@0 | 1407 | /** |
aoqi@0 | 1408 | * Instantiate an inference variables using its (ground) upper bounds. Such |
aoqi@0 | 1409 | * bounds are merged together using glb(). |
aoqi@0 | 1410 | */ |
aoqi@0 | 1411 | UPPER(InferenceBound.UPPER) { |
aoqi@0 | 1412 | @Override |
aoqi@0 | 1413 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1414 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 1415 | List<Type> hibounds = filterBounds(uv, inferenceContext); |
aoqi@0 | 1416 | //note: hibounds should have at least one element |
aoqi@0 | 1417 | Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds); |
aoqi@0 | 1418 | if (owntype.isPrimitive() || owntype.hasTag(ERROR)) { |
aoqi@0 | 1419 | throw infer.inferenceException |
aoqi@0 | 1420 | .setMessage("no.unique.maximal.instance.exists", |
aoqi@0 | 1421 | uv.qtype, hibounds); |
aoqi@0 | 1422 | } else { |
aoqi@0 | 1423 | return owntype; |
aoqi@0 | 1424 | } |
aoqi@0 | 1425 | } |
aoqi@0 | 1426 | }, |
aoqi@0 | 1427 | /** |
aoqi@0 | 1428 | * Like the former; the only difference is that this step can only be applied |
aoqi@0 | 1429 | * if all upper bounds are ground. |
aoqi@0 | 1430 | */ |
aoqi@0 | 1431 | UPPER_LEGACY(InferenceBound.UPPER) { |
aoqi@0 | 1432 | @Override |
aoqi@0 | 1433 | public boolean accepts(UndetVar t, InferenceContext inferenceContext) { |
aoqi@0 | 1434 | return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured(); |
aoqi@0 | 1435 | } |
aoqi@0 | 1436 | |
aoqi@0 | 1437 | @Override |
aoqi@0 | 1438 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1439 | return UPPER.solve(uv, inferenceContext); |
aoqi@0 | 1440 | } |
aoqi@0 | 1441 | }, |
aoqi@0 | 1442 | /** |
aoqi@0 | 1443 | * Like the former; the only difference is that this step can only be applied |
aoqi@0 | 1444 | * if all upper/lower bounds are ground. |
aoqi@0 | 1445 | */ |
aoqi@0 | 1446 | CAPTURED(InferenceBound.UPPER) { |
aoqi@0 | 1447 | @Override |
aoqi@0 | 1448 | public boolean accepts(UndetVar t, InferenceContext inferenceContext) { |
aoqi@0 | 1449 | return t.isCaptured() && |
aoqi@0 | 1450 | !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER)); |
aoqi@0 | 1451 | } |
aoqi@0 | 1452 | |
aoqi@0 | 1453 | @Override |
aoqi@0 | 1454 | Type solve(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1455 | Infer infer = inferenceContext.infer(); |
aoqi@0 | 1456 | Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ? |
aoqi@0 | 1457 | UPPER.solve(uv, inferenceContext) : |
aoqi@0 | 1458 | infer.syms.objectType; |
aoqi@0 | 1459 | Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ? |
aoqi@0 | 1460 | LOWER.solve(uv, inferenceContext) : |
aoqi@0 | 1461 | infer.syms.botType; |
aoqi@0 | 1462 | CapturedType prevCaptured = (CapturedType)uv.qtype; |
aoqi@0 | 1463 | return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard); |
aoqi@0 | 1464 | } |
aoqi@0 | 1465 | }; |
aoqi@0 | 1466 | |
aoqi@0 | 1467 | final InferenceBound ib; |
aoqi@0 | 1468 | |
aoqi@0 | 1469 | InferenceStep(InferenceBound ib) { |
aoqi@0 | 1470 | this.ib = ib; |
aoqi@0 | 1471 | } |
aoqi@0 | 1472 | |
aoqi@0 | 1473 | /** |
aoqi@0 | 1474 | * Find an instantiated type for a given inference variable within |
aoqi@0 | 1475 | * a given inference context |
aoqi@0 | 1476 | */ |
aoqi@0 | 1477 | abstract Type solve(UndetVar uv, InferenceContext inferenceContext); |
aoqi@0 | 1478 | |
aoqi@0 | 1479 | /** |
aoqi@0 | 1480 | * Can the inference variable be instantiated using this step? |
aoqi@0 | 1481 | */ |
aoqi@0 | 1482 | public boolean accepts(UndetVar t, InferenceContext inferenceContext) { |
aoqi@0 | 1483 | return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured(); |
aoqi@0 | 1484 | } |
aoqi@0 | 1485 | |
aoqi@0 | 1486 | /** |
aoqi@0 | 1487 | * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper) |
aoqi@0 | 1488 | */ |
aoqi@0 | 1489 | List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) { |
aoqi@0 | 1490 | return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext)); |
aoqi@0 | 1491 | } |
aoqi@0 | 1492 | } |
aoqi@0 | 1493 | |
aoqi@0 | 1494 | /** |
aoqi@0 | 1495 | * This enumeration defines the sequence of steps to be applied when the |
aoqi@0 | 1496 | * solver works in legacy mode. The steps in this enumeration reflect |
aoqi@0 | 1497 | * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). |
aoqi@0 | 1498 | */ |
aoqi@0 | 1499 | enum LegacyInferenceSteps { |
aoqi@0 | 1500 | |
aoqi@0 | 1501 | EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), |
aoqi@0 | 1502 | EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY)); |
aoqi@0 | 1503 | |
aoqi@0 | 1504 | final EnumSet<InferenceStep> steps; |
aoqi@0 | 1505 | |
aoqi@0 | 1506 | LegacyInferenceSteps(EnumSet<InferenceStep> steps) { |
aoqi@0 | 1507 | this.steps = steps; |
aoqi@0 | 1508 | } |
aoqi@0 | 1509 | } |
aoqi@0 | 1510 | |
aoqi@0 | 1511 | /** |
aoqi@0 | 1512 | * This enumeration defines the sequence of steps to be applied when the |
aoqi@0 | 1513 | * graph solver is used. This order is defined so as to maximize compatibility |
aoqi@0 | 1514 | * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8). |
aoqi@0 | 1515 | */ |
aoqi@0 | 1516 | enum GraphInferenceSteps { |
aoqi@0 | 1517 | |
aoqi@0 | 1518 | EQ(EnumSet.of(InferenceStep.EQ)), |
aoqi@0 | 1519 | EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)), |
aoqi@0 | 1520 | EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED)); |
aoqi@0 | 1521 | |
aoqi@0 | 1522 | final EnumSet<InferenceStep> steps; |
aoqi@0 | 1523 | |
aoqi@0 | 1524 | GraphInferenceSteps(EnumSet<InferenceStep> steps) { |
aoqi@0 | 1525 | this.steps = steps; |
aoqi@0 | 1526 | } |
aoqi@0 | 1527 | } |
aoqi@0 | 1528 | |
aoqi@0 | 1529 | /** |
aoqi@0 | 1530 | * There are two kinds of dependencies between inference variables. The basic |
aoqi@0 | 1531 | * kind of dependency (or bound dependency) arises when a variable mention |
aoqi@0 | 1532 | * another variable in one of its bounds. There's also a more subtle kind |
aoqi@0 | 1533 | * of dependency that arises when a variable 'might' lead to better constraints |
aoqi@0 | 1534 | * on another variable (this is typically the case with variables holding up |
aoqi@0 | 1535 | * stuck expressions). |
aoqi@0 | 1536 | */ |
aoqi@0 | 1537 | enum DependencyKind implements GraphUtils.DependencyKind { |
aoqi@0 | 1538 | |
aoqi@0 | 1539 | /** bound dependency */ |
aoqi@0 | 1540 | BOUND("dotted"), |
aoqi@0 | 1541 | /** stuck dependency */ |
aoqi@0 | 1542 | STUCK("dashed"); |
aoqi@0 | 1543 | |
aoqi@0 | 1544 | final String dotSyle; |
aoqi@0 | 1545 | |
aoqi@0 | 1546 | private DependencyKind(String dotSyle) { |
aoqi@0 | 1547 | this.dotSyle = dotSyle; |
aoqi@0 | 1548 | } |
aoqi@0 | 1549 | |
aoqi@0 | 1550 | @Override |
aoqi@0 | 1551 | public String getDotStyle() { |
aoqi@0 | 1552 | return dotSyle; |
aoqi@0 | 1553 | } |
aoqi@0 | 1554 | } |
aoqi@0 | 1555 | |
aoqi@0 | 1556 | /** |
aoqi@0 | 1557 | * This is the graph inference solver - the solver organizes all inference variables in |
aoqi@0 | 1558 | * a given inference context by bound dependencies - in the general case, such dependencies |
aoqi@0 | 1559 | * would lead to a cyclic directed graph (hence the name); the dependency info is used to build |
aoqi@0 | 1560 | * an acyclic graph, where all cyclic variables are bundled together. An inference |
aoqi@0 | 1561 | * step corresponds to solving a node in the acyclic graph - this is done by |
aoqi@0 | 1562 | * relying on a given strategy (see GraphStrategy). |
aoqi@0 | 1563 | */ |
aoqi@0 | 1564 | class GraphSolver { |
aoqi@0 | 1565 | |
aoqi@0 | 1566 | InferenceContext inferenceContext; |
aoqi@0 | 1567 | Map<Type, Set<Type>> stuckDeps; |
aoqi@0 | 1568 | Warner warn; |
aoqi@0 | 1569 | |
aoqi@0 | 1570 | GraphSolver(InferenceContext inferenceContext, Map<Type, Set<Type>> stuckDeps, Warner warn) { |
aoqi@0 | 1571 | this.inferenceContext = inferenceContext; |
aoqi@0 | 1572 | this.stuckDeps = stuckDeps; |
aoqi@0 | 1573 | this.warn = warn; |
aoqi@0 | 1574 | } |
aoqi@0 | 1575 | |
aoqi@0 | 1576 | /** |
aoqi@0 | 1577 | * Solve variables in a given inference context. The amount of variables |
aoqi@0 | 1578 | * to be solved, and the way in which the underlying acyclic graph is explored |
aoqi@0 | 1579 | * depends on the selected solver strategy. |
aoqi@0 | 1580 | */ |
aoqi@0 | 1581 | void solve(GraphStrategy sstrategy) { |
aoqi@0 | 1582 | checkWithinBounds(inferenceContext, warn); //initial propagation of bounds |
aoqi@0 | 1583 | InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps); |
aoqi@0 | 1584 | while (!sstrategy.done()) { |
aoqi@0 | 1585 | InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph); |
aoqi@0 | 1586 | List<Type> varsToSolve = List.from(nodeToSolve.data); |
aoqi@0 | 1587 | List<Type> saved_undet = inferenceContext.save(); |
aoqi@0 | 1588 | try { |
aoqi@0 | 1589 | //repeat until all variables are solved |
aoqi@0 | 1590 | outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) { |
aoqi@0 | 1591 | //for each inference phase |
aoqi@0 | 1592 | for (GraphInferenceSteps step : GraphInferenceSteps.values()) { |
aoqi@0 | 1593 | if (inferenceContext.solveBasic(varsToSolve, step.steps)) { |
aoqi@0 | 1594 | checkWithinBounds(inferenceContext, warn); |
aoqi@0 | 1595 | continue outer; |
aoqi@0 | 1596 | } |
aoqi@0 | 1597 | } |
aoqi@0 | 1598 | //no progress |
aoqi@0 | 1599 | throw inferenceException.setMessage(); |
aoqi@0 | 1600 | } |
aoqi@0 | 1601 | } |
aoqi@0 | 1602 | catch (InferenceException ex) { |
aoqi@0 | 1603 | //did we fail because of interdependent ivars? |
aoqi@0 | 1604 | inferenceContext.rollback(saved_undet); |
aoqi@0 | 1605 | instantiateAsUninferredVars(varsToSolve, inferenceContext); |
aoqi@0 | 1606 | checkWithinBounds(inferenceContext, warn); |
aoqi@0 | 1607 | } |
aoqi@0 | 1608 | inferenceGraph.deleteNode(nodeToSolve); |
aoqi@0 | 1609 | } |
aoqi@0 | 1610 | } |
aoqi@0 | 1611 | |
aoqi@0 | 1612 | /** |
aoqi@0 | 1613 | * The dependencies between the inference variables that need to be solved |
aoqi@0 | 1614 | * form a (possibly cyclic) graph. This class reduces the original dependency graph |
aoqi@0 | 1615 | * to an acyclic version, where cyclic nodes are folded into a single 'super node'. |
aoqi@0 | 1616 | */ |
aoqi@0 | 1617 | class InferenceGraph { |
aoqi@0 | 1618 | |
aoqi@0 | 1619 | /** |
aoqi@0 | 1620 | * This class represents a node in the graph. Each node corresponds |
aoqi@0 | 1621 | * to an inference variable and has edges (dependencies) on other |
aoqi@0 | 1622 | * nodes. The node defines an entry point that can be used to receive |
aoqi@0 | 1623 | * updates on the structure of the graph this node belongs to (used to |
aoqi@0 | 1624 | * keep dependencies in sync). |
aoqi@0 | 1625 | */ |
aoqi@0 | 1626 | class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> { |
aoqi@0 | 1627 | |
aoqi@0 | 1628 | /** map listing all dependencies (grouped by kind) */ |
aoqi@0 | 1629 | EnumMap<DependencyKind, Set<Node>> deps; |
aoqi@0 | 1630 | |
aoqi@0 | 1631 | Node(Type ivar) { |
aoqi@0 | 1632 | super(ListBuffer.of(ivar)); |
aoqi@0 | 1633 | this.deps = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class); |
aoqi@0 | 1634 | } |
aoqi@0 | 1635 | |
aoqi@0 | 1636 | @Override |
aoqi@0 | 1637 | public GraphUtils.DependencyKind[] getSupportedDependencyKinds() { |
aoqi@0 | 1638 | return DependencyKind.values(); |
aoqi@0 | 1639 | } |
aoqi@0 | 1640 | |
aoqi@0 | 1641 | @Override |
aoqi@0 | 1642 | public String getDependencyName(GraphUtils.Node<ListBuffer<Type>> to, GraphUtils.DependencyKind dk) { |
aoqi@0 | 1643 | if (dk == DependencyKind.STUCK) return ""; |
aoqi@0 | 1644 | else { |
aoqi@0 | 1645 | StringBuilder buf = new StringBuilder(); |
aoqi@0 | 1646 | String sep = ""; |
aoqi@0 | 1647 | for (Type from : data) { |
aoqi@0 | 1648 | UndetVar uv = (UndetVar)inferenceContext.asUndetVar(from); |
aoqi@0 | 1649 | for (Type bound : uv.getBounds(InferenceBound.values())) { |
aoqi@0 | 1650 | if (bound.containsAny(List.from(to.data))) { |
aoqi@0 | 1651 | buf.append(sep); |
aoqi@0 | 1652 | buf.append(bound); |
aoqi@0 | 1653 | sep = ","; |
aoqi@0 | 1654 | } |
aoqi@0 | 1655 | } |
aoqi@0 | 1656 | } |
aoqi@0 | 1657 | return buf.toString(); |
aoqi@0 | 1658 | } |
aoqi@0 | 1659 | } |
aoqi@0 | 1660 | |
aoqi@0 | 1661 | @Override |
aoqi@0 | 1662 | public Iterable<? extends Node> getAllDependencies() { |
aoqi@0 | 1663 | return getDependencies(DependencyKind.values()); |
aoqi@0 | 1664 | } |
aoqi@0 | 1665 | |
aoqi@0 | 1666 | @Override |
aoqi@0 | 1667 | public Iterable<? extends TarjanNode<ListBuffer<Type>>> getDependenciesByKind(GraphUtils.DependencyKind dk) { |
aoqi@0 | 1668 | return getDependencies((DependencyKind)dk); |
aoqi@0 | 1669 | } |
aoqi@0 | 1670 | |
aoqi@0 | 1671 | /** |
aoqi@0 | 1672 | * Retrieves all dependencies with given kind(s). |
aoqi@0 | 1673 | */ |
aoqi@0 | 1674 | protected Set<Node> getDependencies(DependencyKind... depKinds) { |
aoqi@0 | 1675 | Set<Node> buf = new LinkedHashSet<Node>(); |
aoqi@0 | 1676 | for (DependencyKind dk : depKinds) { |
aoqi@0 | 1677 | Set<Node> depsByKind = deps.get(dk); |
aoqi@0 | 1678 | if (depsByKind != null) { |
aoqi@0 | 1679 | buf.addAll(depsByKind); |
aoqi@0 | 1680 | } |
aoqi@0 | 1681 | } |
aoqi@0 | 1682 | return buf; |
aoqi@0 | 1683 | } |
aoqi@0 | 1684 | |
aoqi@0 | 1685 | /** |
aoqi@0 | 1686 | * Adds dependency with given kind. |
aoqi@0 | 1687 | */ |
aoqi@0 | 1688 | protected void addDependency(DependencyKind dk, Node depToAdd) { |
aoqi@0 | 1689 | Set<Node> depsByKind = deps.get(dk); |
aoqi@0 | 1690 | if (depsByKind == null) { |
aoqi@0 | 1691 | depsByKind = new LinkedHashSet<Node>(); |
aoqi@0 | 1692 | deps.put(dk, depsByKind); |
aoqi@0 | 1693 | } |
aoqi@0 | 1694 | depsByKind.add(depToAdd); |
aoqi@0 | 1695 | } |
aoqi@0 | 1696 | |
aoqi@0 | 1697 | /** |
aoqi@0 | 1698 | * Add multiple dependencies of same given kind. |
aoqi@0 | 1699 | */ |
aoqi@0 | 1700 | protected void addDependencies(DependencyKind dk, Set<Node> depsToAdd) { |
aoqi@0 | 1701 | for (Node n : depsToAdd) { |
aoqi@0 | 1702 | addDependency(dk, n); |
aoqi@0 | 1703 | } |
aoqi@0 | 1704 | } |
aoqi@0 | 1705 | |
aoqi@0 | 1706 | /** |
aoqi@0 | 1707 | * Remove a dependency, regardless of its kind. |
aoqi@0 | 1708 | */ |
aoqi@0 | 1709 | protected Set<DependencyKind> removeDependency(Node n) { |
aoqi@0 | 1710 | Set<DependencyKind> removedKinds = new HashSet<>(); |
aoqi@0 | 1711 | for (DependencyKind dk : DependencyKind.values()) { |
aoqi@0 | 1712 | Set<Node> depsByKind = deps.get(dk); |
aoqi@0 | 1713 | if (depsByKind == null) continue; |
aoqi@0 | 1714 | if (depsByKind.remove(n)) { |
aoqi@0 | 1715 | removedKinds.add(dk); |
aoqi@0 | 1716 | } |
aoqi@0 | 1717 | } |
aoqi@0 | 1718 | return removedKinds; |
aoqi@0 | 1719 | } |
aoqi@0 | 1720 | |
aoqi@0 | 1721 | /** |
aoqi@0 | 1722 | * Compute closure of a give node, by recursively walking |
aoqi@0 | 1723 | * through all its dependencies (of given kinds) |
aoqi@0 | 1724 | */ |
aoqi@0 | 1725 | protected Set<Node> closure(DependencyKind... depKinds) { |
aoqi@0 | 1726 | boolean progress = true; |
aoqi@0 | 1727 | Set<Node> closure = new HashSet<Node>(); |
aoqi@0 | 1728 | closure.add(this); |
aoqi@0 | 1729 | while (progress) { |
aoqi@0 | 1730 | progress = false; |
aoqi@0 | 1731 | for (Node n1 : new HashSet<Node>(closure)) { |
aoqi@0 | 1732 | progress = closure.addAll(n1.getDependencies(depKinds)); |
aoqi@0 | 1733 | } |
aoqi@0 | 1734 | } |
aoqi@0 | 1735 | return closure; |
aoqi@0 | 1736 | } |
aoqi@0 | 1737 | |
aoqi@0 | 1738 | /** |
aoqi@0 | 1739 | * Is this node a leaf? This means either the node has no dependencies, |
aoqi@0 | 1740 | * or it just has self-dependencies. |
aoqi@0 | 1741 | */ |
aoqi@0 | 1742 | protected boolean isLeaf() { |
aoqi@0 | 1743 | //no deps, or only one self dep |
aoqi@0 | 1744 | Set<Node> allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK); |
aoqi@0 | 1745 | if (allDeps.isEmpty()) return true; |
aoqi@0 | 1746 | for (Node n : allDeps) { |
aoqi@0 | 1747 | if (n != this) { |
aoqi@0 | 1748 | return false; |
aoqi@0 | 1749 | } |
aoqi@0 | 1750 | } |
aoqi@0 | 1751 | return true; |
aoqi@0 | 1752 | } |
aoqi@0 | 1753 | |
aoqi@0 | 1754 | /** |
aoqi@0 | 1755 | * Merge this node with another node, acquiring its dependencies. |
aoqi@0 | 1756 | * This routine is used to merge all cyclic node together and |
aoqi@0 | 1757 | * form an acyclic graph. |
aoqi@0 | 1758 | */ |
aoqi@0 | 1759 | protected void mergeWith(List<? extends Node> nodes) { |
aoqi@0 | 1760 | for (Node n : nodes) { |
aoqi@0 | 1761 | Assert.check(n.data.length() == 1, "Attempt to merge a compound node!"); |
aoqi@0 | 1762 | data.appendList(n.data); |
aoqi@0 | 1763 | for (DependencyKind dk : DependencyKind.values()) { |
aoqi@0 | 1764 | addDependencies(dk, n.getDependencies(dk)); |
aoqi@0 | 1765 | } |
aoqi@0 | 1766 | } |
aoqi@0 | 1767 | //update deps |
aoqi@0 | 1768 | EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class); |
aoqi@0 | 1769 | for (DependencyKind dk : DependencyKind.values()) { |
aoqi@0 | 1770 | for (Node d : getDependencies(dk)) { |
aoqi@0 | 1771 | Set<Node> depsByKind = deps2.get(dk); |
aoqi@0 | 1772 | if (depsByKind == null) { |
aoqi@0 | 1773 | depsByKind = new LinkedHashSet<Node>(); |
aoqi@0 | 1774 | deps2.put(dk, depsByKind); |
aoqi@0 | 1775 | } |
aoqi@0 | 1776 | if (data.contains(d.data.first())) { |
aoqi@0 | 1777 | depsByKind.add(this); |
aoqi@0 | 1778 | } else { |
aoqi@0 | 1779 | depsByKind.add(d); |
aoqi@0 | 1780 | } |
aoqi@0 | 1781 | } |
aoqi@0 | 1782 | } |
aoqi@0 | 1783 | deps = deps2; |
aoqi@0 | 1784 | } |
aoqi@0 | 1785 | |
aoqi@0 | 1786 | /** |
aoqi@0 | 1787 | * Notify all nodes that something has changed in the graph |
aoqi@0 | 1788 | * topology. |
aoqi@0 | 1789 | */ |
aoqi@0 | 1790 | private void graphChanged(Node from, Node to) { |
aoqi@0 | 1791 | for (DependencyKind dk : removeDependency(from)) { |
aoqi@0 | 1792 | if (to != null) { |
aoqi@0 | 1793 | addDependency(dk, to); |
aoqi@0 | 1794 | } |
aoqi@0 | 1795 | } |
aoqi@0 | 1796 | } |
aoqi@0 | 1797 | } |
aoqi@0 | 1798 | |
aoqi@0 | 1799 | /** the nodes in the inference graph */ |
aoqi@0 | 1800 | ArrayList<Node> nodes; |
aoqi@0 | 1801 | |
aoqi@0 | 1802 | InferenceGraph(Map<Type, Set<Type>> optDeps) { |
aoqi@0 | 1803 | initNodes(optDeps); |
aoqi@0 | 1804 | } |
aoqi@0 | 1805 | |
aoqi@0 | 1806 | /** |
aoqi@0 | 1807 | * Basic lookup helper for retrieving a graph node given an inference |
aoqi@0 | 1808 | * variable type. |
aoqi@0 | 1809 | */ |
aoqi@0 | 1810 | public Node findNode(Type t) { |
aoqi@0 | 1811 | for (Node n : nodes) { |
aoqi@0 | 1812 | if (n.data.contains(t)) { |
aoqi@0 | 1813 | return n; |
aoqi@0 | 1814 | } |
aoqi@0 | 1815 | } |
aoqi@0 | 1816 | return null; |
aoqi@0 | 1817 | } |
aoqi@0 | 1818 | |
aoqi@0 | 1819 | /** |
aoqi@0 | 1820 | * Delete a node from the graph. This update the underlying structure |
aoqi@0 | 1821 | * of the graph (including dependencies) via listeners updates. |
aoqi@0 | 1822 | */ |
aoqi@0 | 1823 | public void deleteNode(Node n) { |
aoqi@0 | 1824 | Assert.check(nodes.contains(n)); |
aoqi@0 | 1825 | nodes.remove(n); |
aoqi@0 | 1826 | notifyUpdate(n, null); |
aoqi@0 | 1827 | } |
aoqi@0 | 1828 | |
aoqi@0 | 1829 | /** |
aoqi@0 | 1830 | * Notify all nodes of a change in the graph. If the target node is |
aoqi@0 | 1831 | * {@code null} the source node is assumed to be removed. |
aoqi@0 | 1832 | */ |
aoqi@0 | 1833 | void notifyUpdate(Node from, Node to) { |
aoqi@0 | 1834 | for (Node n : nodes) { |
aoqi@0 | 1835 | n.graphChanged(from, to); |
aoqi@0 | 1836 | } |
aoqi@0 | 1837 | } |
aoqi@0 | 1838 | |
aoqi@0 | 1839 | /** |
aoqi@0 | 1840 | * Create the graph nodes. First a simple node is created for every inference |
aoqi@0 | 1841 | * variables to be solved. Then Tarjan is used to found all connected components |
aoqi@0 | 1842 | * in the graph. For each component containing more than one node, a super node is |
aoqi@0 | 1843 | * created, effectively replacing the original cyclic nodes. |
aoqi@0 | 1844 | */ |
aoqi@0 | 1845 | void initNodes(Map<Type, Set<Type>> stuckDeps) { |
aoqi@0 | 1846 | //add nodes |
aoqi@0 | 1847 | nodes = new ArrayList<Node>(); |
aoqi@0 | 1848 | for (Type t : inferenceContext.restvars()) { |
aoqi@0 | 1849 | nodes.add(new Node(t)); |
aoqi@0 | 1850 | } |
aoqi@0 | 1851 | //add dependencies |
aoqi@0 | 1852 | for (Node n_i : nodes) { |
aoqi@0 | 1853 | Type i = n_i.data.first(); |
aoqi@0 | 1854 | Set<Type> optDepsByNode = stuckDeps.get(i); |
aoqi@0 | 1855 | for (Node n_j : nodes) { |
aoqi@0 | 1856 | Type j = n_j.data.first(); |
aoqi@0 | 1857 | UndetVar uv_i = (UndetVar)inferenceContext.asUndetVar(i); |
aoqi@0 | 1858 | if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) { |
aoqi@0 | 1859 | //update i's bound dependencies |
aoqi@0 | 1860 | n_i.addDependency(DependencyKind.BOUND, n_j); |
aoqi@0 | 1861 | } |
aoqi@0 | 1862 | if (optDepsByNode != null && optDepsByNode.contains(j)) { |
aoqi@0 | 1863 | //update i's stuck dependencies |
aoqi@0 | 1864 | n_i.addDependency(DependencyKind.STUCK, n_j); |
aoqi@0 | 1865 | } |
aoqi@0 | 1866 | } |
aoqi@0 | 1867 | } |
aoqi@0 | 1868 | //merge cyclic nodes |
aoqi@0 | 1869 | ArrayList<Node> acyclicNodes = new ArrayList<Node>(); |
aoqi@0 | 1870 | for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) { |
aoqi@0 | 1871 | if (conSubGraph.length() > 1) { |
aoqi@0 | 1872 | Node root = conSubGraph.head; |
aoqi@0 | 1873 | root.mergeWith(conSubGraph.tail); |
aoqi@0 | 1874 | for (Node n : conSubGraph) { |
aoqi@0 | 1875 | notifyUpdate(n, root); |
aoqi@0 | 1876 | } |
aoqi@0 | 1877 | } |
aoqi@0 | 1878 | acyclicNodes.add(conSubGraph.head); |
aoqi@0 | 1879 | } |
aoqi@0 | 1880 | nodes = acyclicNodes; |
aoqi@0 | 1881 | } |
aoqi@0 | 1882 | |
aoqi@0 | 1883 | /** |
aoqi@0 | 1884 | * Debugging: dot representation of this graph |
aoqi@0 | 1885 | */ |
aoqi@0 | 1886 | String toDot() { |
aoqi@0 | 1887 | StringBuilder buf = new StringBuilder(); |
aoqi@0 | 1888 | for (Type t : inferenceContext.undetvars) { |
aoqi@0 | 1889 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 1890 | buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n", |
aoqi@0 | 1891 | uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER), |
aoqi@0 | 1892 | uv.getBounds(InferenceBound.EQ))); |
aoqi@0 | 1893 | } |
aoqi@0 | 1894 | return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString()); |
aoqi@0 | 1895 | } |
aoqi@0 | 1896 | } |
aoqi@0 | 1897 | } |
aoqi@0 | 1898 | // </editor-fold> |
aoqi@0 | 1899 | |
aoqi@0 | 1900 | // <editor-fold defaultstate="collapsed" desc="Inference context"> |
aoqi@0 | 1901 | /** |
aoqi@0 | 1902 | * Functional interface for defining inference callbacks. Certain actions |
aoqi@0 | 1903 | * (i.e. subtyping checks) might need to be redone after all inference variables |
aoqi@0 | 1904 | * have been fixed. |
aoqi@0 | 1905 | */ |
aoqi@0 | 1906 | interface FreeTypeListener { |
aoqi@0 | 1907 | void typesInferred(InferenceContext inferenceContext); |
aoqi@0 | 1908 | } |
aoqi@0 | 1909 | |
aoqi@0 | 1910 | /** |
aoqi@0 | 1911 | * An inference context keeps track of the set of variables that are free |
aoqi@0 | 1912 | * in the current context. It provides utility methods for opening/closing |
aoqi@0 | 1913 | * types to their corresponding free/closed forms. It also provide hooks for |
aoqi@0 | 1914 | * attaching deferred post-inference action (see PendingCheck). Finally, |
aoqi@0 | 1915 | * it can be used as an entry point for performing upper/lower bound inference |
aoqi@0 | 1916 | * (see InferenceKind). |
aoqi@0 | 1917 | */ |
aoqi@0 | 1918 | class InferenceContext { |
aoqi@0 | 1919 | |
aoqi@0 | 1920 | /** list of inference vars as undet vars */ |
aoqi@0 | 1921 | List<Type> undetvars; |
aoqi@0 | 1922 | |
aoqi@0 | 1923 | /** list of inference vars in this context */ |
aoqi@0 | 1924 | List<Type> inferencevars; |
aoqi@0 | 1925 | |
aoqi@0 | 1926 | java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners = |
aoqi@0 | 1927 | new java.util.HashMap<FreeTypeListener, List<Type>>(); |
aoqi@0 | 1928 | |
aoqi@0 | 1929 | List<FreeTypeListener> freetypeListeners = List.nil(); |
aoqi@0 | 1930 | |
aoqi@0 | 1931 | public InferenceContext(List<Type> inferencevars) { |
aoqi@0 | 1932 | this.undetvars = Type.map(inferencevars, fromTypeVarFun); |
aoqi@0 | 1933 | this.inferencevars = inferencevars; |
aoqi@0 | 1934 | } |
aoqi@0 | 1935 | //where |
aoqi@0 | 1936 | Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") { |
aoqi@0 | 1937 | // mapping that turns inference variables into undet vars |
aoqi@0 | 1938 | public Type apply(Type t) { |
aoqi@0 | 1939 | if (t.hasTag(TYPEVAR)) { |
aoqi@0 | 1940 | TypeVar tv = (TypeVar)t; |
aoqi@0 | 1941 | if (tv.isCaptured()) { |
aoqi@0 | 1942 | return new CapturedUndetVar((CapturedType)tv, types); |
aoqi@0 | 1943 | } else { |
aoqi@0 | 1944 | return new UndetVar(tv, types); |
aoqi@0 | 1945 | } |
aoqi@0 | 1946 | } else { |
aoqi@0 | 1947 | return t.map(this); |
aoqi@0 | 1948 | } |
aoqi@0 | 1949 | } |
aoqi@0 | 1950 | }; |
aoqi@0 | 1951 | |
aoqi@0 | 1952 | /** |
aoqi@0 | 1953 | * add a new inference var to this inference context |
aoqi@0 | 1954 | */ |
aoqi@0 | 1955 | void addVar(TypeVar t) { |
aoqi@0 | 1956 | this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t)); |
aoqi@0 | 1957 | this.inferencevars = this.inferencevars.prepend(t); |
aoqi@0 | 1958 | } |
aoqi@0 | 1959 | |
aoqi@0 | 1960 | /** |
aoqi@0 | 1961 | * returns the list of free variables (as type-variables) in this |
aoqi@0 | 1962 | * inference context |
aoqi@0 | 1963 | */ |
aoqi@0 | 1964 | List<Type> inferenceVars() { |
aoqi@0 | 1965 | return inferencevars; |
aoqi@0 | 1966 | } |
aoqi@0 | 1967 | |
aoqi@0 | 1968 | /** |
aoqi@0 | 1969 | * returns the list of uninstantiated variables (as type-variables) in this |
aoqi@0 | 1970 | * inference context |
aoqi@0 | 1971 | */ |
aoqi@0 | 1972 | List<Type> restvars() { |
aoqi@0 | 1973 | return filterVars(new Filter<UndetVar>() { |
aoqi@0 | 1974 | public boolean accepts(UndetVar uv) { |
aoqi@0 | 1975 | return uv.inst == null; |
aoqi@0 | 1976 | } |
aoqi@0 | 1977 | }); |
aoqi@0 | 1978 | } |
aoqi@0 | 1979 | |
aoqi@0 | 1980 | /** |
aoqi@0 | 1981 | * returns the list of instantiated variables (as type-variables) in this |
aoqi@0 | 1982 | * inference context |
aoqi@0 | 1983 | */ |
aoqi@0 | 1984 | List<Type> instvars() { |
aoqi@0 | 1985 | return filterVars(new Filter<UndetVar>() { |
aoqi@0 | 1986 | public boolean accepts(UndetVar uv) { |
aoqi@0 | 1987 | return uv.inst != null; |
aoqi@0 | 1988 | } |
aoqi@0 | 1989 | }); |
aoqi@0 | 1990 | } |
aoqi@0 | 1991 | |
aoqi@0 | 1992 | /** |
aoqi@0 | 1993 | * Get list of bounded inference variables (where bound is other than |
aoqi@0 | 1994 | * declared bounds). |
aoqi@0 | 1995 | */ |
aoqi@0 | 1996 | final List<Type> boundedVars() { |
aoqi@0 | 1997 | return filterVars(new Filter<UndetVar>() { |
aoqi@0 | 1998 | public boolean accepts(UndetVar uv) { |
aoqi@0 | 1999 | return uv.getBounds(InferenceBound.UPPER) |
aoqi@0 | 2000 | .diff(uv.getDeclaredBounds()) |
aoqi@0 | 2001 | .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty(); |
aoqi@0 | 2002 | } |
aoqi@0 | 2003 | }); |
aoqi@0 | 2004 | } |
aoqi@0 | 2005 | |
aoqi@0 | 2006 | /* Returns the corresponding inference variables. |
aoqi@0 | 2007 | */ |
aoqi@0 | 2008 | private List<Type> filterVars(Filter<UndetVar> fu) { |
aoqi@0 | 2009 | ListBuffer<Type> res = new ListBuffer<>(); |
aoqi@0 | 2010 | for (Type t : undetvars) { |
aoqi@0 | 2011 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 2012 | if (fu.accepts(uv)) { |
aoqi@0 | 2013 | res.append(uv.qtype); |
aoqi@0 | 2014 | } |
aoqi@0 | 2015 | } |
aoqi@0 | 2016 | return res.toList(); |
aoqi@0 | 2017 | } |
aoqi@0 | 2018 | |
aoqi@0 | 2019 | /** |
aoqi@0 | 2020 | * is this type free? |
aoqi@0 | 2021 | */ |
aoqi@0 | 2022 | final boolean free(Type t) { |
aoqi@0 | 2023 | return t.containsAny(inferencevars); |
aoqi@0 | 2024 | } |
aoqi@0 | 2025 | |
aoqi@0 | 2026 | final boolean free(List<Type> ts) { |
aoqi@0 | 2027 | for (Type t : ts) { |
aoqi@0 | 2028 | if (free(t)) return true; |
aoqi@0 | 2029 | } |
aoqi@0 | 2030 | return false; |
aoqi@0 | 2031 | } |
aoqi@0 | 2032 | |
aoqi@0 | 2033 | /** |
aoqi@0 | 2034 | * Returns a list of free variables in a given type |
aoqi@0 | 2035 | */ |
aoqi@0 | 2036 | final List<Type> freeVarsIn(Type t) { |
aoqi@0 | 2037 | ListBuffer<Type> buf = new ListBuffer<>(); |
aoqi@0 | 2038 | for (Type iv : inferenceVars()) { |
aoqi@0 | 2039 | if (t.contains(iv)) { |
aoqi@0 | 2040 | buf.add(iv); |
aoqi@0 | 2041 | } |
aoqi@0 | 2042 | } |
aoqi@0 | 2043 | return buf.toList(); |
aoqi@0 | 2044 | } |
aoqi@0 | 2045 | |
aoqi@0 | 2046 | final List<Type> freeVarsIn(List<Type> ts) { |
aoqi@0 | 2047 | ListBuffer<Type> buf = new ListBuffer<>(); |
aoqi@0 | 2048 | for (Type t : ts) { |
aoqi@0 | 2049 | buf.appendList(freeVarsIn(t)); |
aoqi@0 | 2050 | } |
aoqi@0 | 2051 | ListBuffer<Type> buf2 = new ListBuffer<>(); |
aoqi@0 | 2052 | for (Type t : buf) { |
aoqi@0 | 2053 | if (!buf2.contains(t)) { |
aoqi@0 | 2054 | buf2.add(t); |
aoqi@0 | 2055 | } |
aoqi@0 | 2056 | } |
aoqi@0 | 2057 | return buf2.toList(); |
aoqi@0 | 2058 | } |
aoqi@0 | 2059 | |
aoqi@0 | 2060 | /** |
aoqi@0 | 2061 | * Replace all free variables in a given type with corresponding |
aoqi@0 | 2062 | * undet vars (used ahead of subtyping/compatibility checks to allow propagation |
aoqi@0 | 2063 | * of inference constraints). |
aoqi@0 | 2064 | */ |
aoqi@0 | 2065 | final Type asUndetVar(Type t) { |
aoqi@0 | 2066 | return types.subst(t, inferencevars, undetvars); |
aoqi@0 | 2067 | } |
aoqi@0 | 2068 | |
aoqi@0 | 2069 | final List<Type> asUndetVars(List<Type> ts) { |
aoqi@0 | 2070 | ListBuffer<Type> buf = new ListBuffer<>(); |
aoqi@0 | 2071 | for (Type t : ts) { |
aoqi@0 | 2072 | buf.append(asUndetVar(t)); |
aoqi@0 | 2073 | } |
aoqi@0 | 2074 | return buf.toList(); |
aoqi@0 | 2075 | } |
aoqi@0 | 2076 | |
aoqi@0 | 2077 | List<Type> instTypes() { |
aoqi@0 | 2078 | ListBuffer<Type> buf = new ListBuffer<>(); |
aoqi@0 | 2079 | for (Type t : undetvars) { |
aoqi@0 | 2080 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 2081 | buf.append(uv.inst != null ? uv.inst : uv.qtype); |
aoqi@0 | 2082 | } |
aoqi@0 | 2083 | return buf.toList(); |
aoqi@0 | 2084 | } |
aoqi@0 | 2085 | |
aoqi@0 | 2086 | /** |
aoqi@0 | 2087 | * Replace all free variables in a given type with corresponding |
aoqi@0 | 2088 | * instantiated types - if one or more free variable has not been |
aoqi@0 | 2089 | * fully instantiated, it will still be available in the resulting type. |
aoqi@0 | 2090 | */ |
aoqi@0 | 2091 | Type asInstType(Type t) { |
aoqi@0 | 2092 | return types.subst(t, inferencevars, instTypes()); |
aoqi@0 | 2093 | } |
aoqi@0 | 2094 | |
aoqi@0 | 2095 | List<Type> asInstTypes(List<Type> ts) { |
aoqi@0 | 2096 | ListBuffer<Type> buf = new ListBuffer<>(); |
aoqi@0 | 2097 | for (Type t : ts) { |
aoqi@0 | 2098 | buf.append(asInstType(t)); |
aoqi@0 | 2099 | } |
aoqi@0 | 2100 | return buf.toList(); |
aoqi@0 | 2101 | } |
aoqi@0 | 2102 | |
aoqi@0 | 2103 | /** |
aoqi@0 | 2104 | * Add custom hook for performing post-inference action |
aoqi@0 | 2105 | */ |
aoqi@0 | 2106 | void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) { |
aoqi@0 | 2107 | freeTypeListeners.put(ftl, freeVarsIn(types)); |
aoqi@0 | 2108 | } |
aoqi@0 | 2109 | |
aoqi@0 | 2110 | /** |
aoqi@0 | 2111 | * Mark the inference context as complete and trigger evaluation |
aoqi@0 | 2112 | * of all deferred checks. |
aoqi@0 | 2113 | */ |
aoqi@0 | 2114 | void notifyChange() { |
aoqi@0 | 2115 | notifyChange(inferencevars.diff(restvars())); |
aoqi@0 | 2116 | } |
aoqi@0 | 2117 | |
aoqi@0 | 2118 | void notifyChange(List<Type> inferredVars) { |
aoqi@0 | 2119 | InferenceException thrownEx = null; |
aoqi@0 | 2120 | for (Map.Entry<FreeTypeListener, List<Type>> entry : |
aoqi@0 | 2121 | new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) { |
aoqi@0 | 2122 | if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) { |
aoqi@0 | 2123 | try { |
aoqi@0 | 2124 | entry.getKey().typesInferred(this); |
aoqi@0 | 2125 | freeTypeListeners.remove(entry.getKey()); |
aoqi@0 | 2126 | } catch (InferenceException ex) { |
aoqi@0 | 2127 | if (thrownEx == null) { |
aoqi@0 | 2128 | thrownEx = ex; |
aoqi@0 | 2129 | } |
aoqi@0 | 2130 | } |
aoqi@0 | 2131 | } |
aoqi@0 | 2132 | } |
aoqi@0 | 2133 | //inference exception multiplexing - present any inference exception |
aoqi@0 | 2134 | //thrown when processing listeners as a single one |
aoqi@0 | 2135 | if (thrownEx != null) { |
aoqi@0 | 2136 | throw thrownEx; |
aoqi@0 | 2137 | } |
aoqi@0 | 2138 | } |
aoqi@0 | 2139 | |
aoqi@0 | 2140 | /** |
aoqi@0 | 2141 | * Save the state of this inference context |
aoqi@0 | 2142 | */ |
aoqi@0 | 2143 | List<Type> save() { |
aoqi@0 | 2144 | ListBuffer<Type> buf = new ListBuffer<>(); |
aoqi@0 | 2145 | for (Type t : undetvars) { |
aoqi@0 | 2146 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 2147 | UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types); |
aoqi@0 | 2148 | for (InferenceBound ib : InferenceBound.values()) { |
aoqi@0 | 2149 | for (Type b : uv.getBounds(ib)) { |
aoqi@0 | 2150 | uv2.addBound(ib, b, types); |
aoqi@0 | 2151 | } |
aoqi@0 | 2152 | } |
aoqi@0 | 2153 | uv2.inst = uv.inst; |
aoqi@0 | 2154 | buf.add(uv2); |
aoqi@0 | 2155 | } |
aoqi@0 | 2156 | return buf.toList(); |
aoqi@0 | 2157 | } |
aoqi@0 | 2158 | |
aoqi@0 | 2159 | /** |
aoqi@0 | 2160 | * Restore the state of this inference context to the previous known checkpoint |
aoqi@0 | 2161 | */ |
aoqi@0 | 2162 | void rollback(List<Type> saved_undet) { |
aoqi@0 | 2163 | Assert.check(saved_undet != null && saved_undet.length() == undetvars.length()); |
aoqi@0 | 2164 | //restore bounds (note: we need to preserve the old instances) |
aoqi@0 | 2165 | for (Type t : undetvars) { |
aoqi@0 | 2166 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 2167 | UndetVar uv_saved = (UndetVar)saved_undet.head; |
aoqi@0 | 2168 | for (InferenceBound ib : InferenceBound.values()) { |
aoqi@0 | 2169 | uv.setBounds(ib, uv_saved.getBounds(ib)); |
aoqi@0 | 2170 | } |
aoqi@0 | 2171 | uv.inst = uv_saved.inst; |
aoqi@0 | 2172 | saved_undet = saved_undet.tail; |
aoqi@0 | 2173 | } |
aoqi@0 | 2174 | } |
aoqi@0 | 2175 | |
aoqi@0 | 2176 | /** |
aoqi@0 | 2177 | * Copy variable in this inference context to the given context |
aoqi@0 | 2178 | */ |
aoqi@0 | 2179 | void dupTo(final InferenceContext that) { |
aoqi@0 | 2180 | that.inferencevars = that.inferencevars.appendList( |
aoqi@0 | 2181 | inferencevars.diff(that.inferencevars)); |
aoqi@0 | 2182 | that.undetvars = that.undetvars.appendList( |
aoqi@0 | 2183 | undetvars.diff(that.undetvars)); |
aoqi@0 | 2184 | //set up listeners to notify original inference contexts as |
aoqi@0 | 2185 | //propagated vars are inferred in new context |
aoqi@0 | 2186 | for (Type t : inferencevars) { |
aoqi@0 | 2187 | that.freeTypeListeners.put(new FreeTypeListener() { |
aoqi@0 | 2188 | public void typesInferred(InferenceContext inferenceContext) { |
aoqi@0 | 2189 | InferenceContext.this.notifyChange(); |
aoqi@0 | 2190 | } |
aoqi@0 | 2191 | }, List.of(t)); |
aoqi@0 | 2192 | } |
aoqi@0 | 2193 | } |
aoqi@0 | 2194 | |
aoqi@0 | 2195 | private void solve(GraphStrategy ss, Warner warn) { |
aoqi@0 | 2196 | solve(ss, new HashMap<Type, Set<Type>>(), warn); |
aoqi@0 | 2197 | } |
aoqi@0 | 2198 | |
aoqi@0 | 2199 | /** |
aoqi@0 | 2200 | * Solve with given graph strategy. |
aoqi@0 | 2201 | */ |
aoqi@0 | 2202 | private void solve(GraphStrategy ss, Map<Type, Set<Type>> stuckDeps, Warner warn) { |
aoqi@0 | 2203 | GraphSolver s = new GraphSolver(this, stuckDeps, warn); |
aoqi@0 | 2204 | s.solve(ss); |
aoqi@0 | 2205 | } |
aoqi@0 | 2206 | |
aoqi@0 | 2207 | /** |
aoqi@0 | 2208 | * Solve all variables in this context. |
aoqi@0 | 2209 | */ |
aoqi@0 | 2210 | public void solve(Warner warn) { |
aoqi@0 | 2211 | solve(new LeafSolver() { |
aoqi@0 | 2212 | public boolean done() { |
aoqi@0 | 2213 | return restvars().isEmpty(); |
aoqi@0 | 2214 | } |
aoqi@0 | 2215 | }, warn); |
aoqi@0 | 2216 | } |
aoqi@0 | 2217 | |
aoqi@0 | 2218 | /** |
aoqi@0 | 2219 | * Solve all variables in the given list. |
aoqi@0 | 2220 | */ |
aoqi@0 | 2221 | public void solve(final List<Type> vars, Warner warn) { |
aoqi@0 | 2222 | solve(new BestLeafSolver(vars) { |
aoqi@0 | 2223 | public boolean done() { |
aoqi@0 | 2224 | return !free(asInstTypes(vars)); |
aoqi@0 | 2225 | } |
aoqi@0 | 2226 | }, warn); |
aoqi@0 | 2227 | } |
aoqi@0 | 2228 | |
aoqi@0 | 2229 | /** |
aoqi@0 | 2230 | * Solve at least one variable in given list. |
aoqi@0 | 2231 | */ |
aoqi@0 | 2232 | public void solveAny(List<Type> varsToSolve, Map<Type, Set<Type>> optDeps, Warner warn) { |
aoqi@0 | 2233 | solve(new BestLeafSolver(varsToSolve.intersect(restvars())) { |
aoqi@0 | 2234 | public boolean done() { |
aoqi@0 | 2235 | return instvars().intersect(varsToSolve).nonEmpty(); |
aoqi@0 | 2236 | } |
aoqi@0 | 2237 | }, optDeps, warn); |
aoqi@0 | 2238 | } |
aoqi@0 | 2239 | |
aoqi@0 | 2240 | /** |
aoqi@0 | 2241 | * Apply a set of inference steps |
aoqi@0 | 2242 | */ |
aoqi@0 | 2243 | private boolean solveBasic(EnumSet<InferenceStep> steps) { |
aoqi@0 | 2244 | return solveBasic(inferencevars, steps); |
aoqi@0 | 2245 | } |
aoqi@0 | 2246 | |
aoqi@0 | 2247 | private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) { |
aoqi@0 | 2248 | boolean changed = false; |
aoqi@0 | 2249 | for (Type t : varsToSolve.intersect(restvars())) { |
aoqi@0 | 2250 | UndetVar uv = (UndetVar)asUndetVar(t); |
aoqi@0 | 2251 | for (InferenceStep step : steps) { |
aoqi@0 | 2252 | if (step.accepts(uv, this)) { |
aoqi@0 | 2253 | uv.inst = step.solve(uv, this); |
aoqi@0 | 2254 | changed = true; |
aoqi@0 | 2255 | break; |
aoqi@0 | 2256 | } |
aoqi@0 | 2257 | } |
aoqi@0 | 2258 | } |
aoqi@0 | 2259 | return changed; |
aoqi@0 | 2260 | } |
aoqi@0 | 2261 | |
aoqi@0 | 2262 | /** |
aoqi@0 | 2263 | * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8). |
aoqi@0 | 2264 | * During overload resolution, instantiation is done by doing a partial |
aoqi@0 | 2265 | * inference process using eq/lower bound instantiation. During check, |
aoqi@0 | 2266 | * we also instantiate any remaining vars by repeatedly using eq/upper |
aoqi@0 | 2267 | * instantiation, until all variables are solved. |
aoqi@0 | 2268 | */ |
aoqi@0 | 2269 | public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) { |
aoqi@0 | 2270 | while (true) { |
aoqi@0 | 2271 | boolean stuck = !solveBasic(steps); |
aoqi@0 | 2272 | if (restvars().isEmpty() || partial) { |
aoqi@0 | 2273 | //all variables have been instantiated - exit |
aoqi@0 | 2274 | break; |
aoqi@0 | 2275 | } else if (stuck) { |
aoqi@0 | 2276 | //some variables could not be instantiated because of cycles in |
aoqi@0 | 2277 | //upper bounds - provide a (possibly recursive) default instantiation |
aoqi@0 | 2278 | instantiateAsUninferredVars(restvars(), this); |
aoqi@0 | 2279 | break; |
aoqi@0 | 2280 | } else { |
aoqi@0 | 2281 | //some variables have been instantiated - replace newly instantiated |
aoqi@0 | 2282 | //variables in remaining upper bounds and continue |
aoqi@0 | 2283 | for (Type t : undetvars) { |
aoqi@0 | 2284 | UndetVar uv = (UndetVar)t; |
aoqi@0 | 2285 | uv.substBounds(inferenceVars(), instTypes(), types); |
aoqi@0 | 2286 | } |
aoqi@0 | 2287 | } |
aoqi@0 | 2288 | } |
aoqi@0 | 2289 | checkWithinBounds(this, warn); |
aoqi@0 | 2290 | } |
aoqi@0 | 2291 | |
aoqi@0 | 2292 | private Infer infer() { |
aoqi@0 | 2293 | //back-door to infer |
aoqi@0 | 2294 | return Infer.this; |
aoqi@0 | 2295 | } |
aoqi@0 | 2296 | |
aoqi@0 | 2297 | @Override |
aoqi@0 | 2298 | public String toString() { |
aoqi@0 | 2299 | return "Inference vars: " + inferencevars + '\n' + |
aoqi@0 | 2300 | "Undet vars: " + undetvars; |
aoqi@0 | 2301 | } |
aoqi@0 | 2302 | |
aoqi@0 | 2303 | /* Method Types.capture() generates a new type every time it's applied |
aoqi@0 | 2304 | * to a wildcard parameterized type. This is intended functionality but |
aoqi@0 | 2305 | * there are some cases when what you need is not to generate a new |
aoqi@0 | 2306 | * captured type but to check that a previously generated captured type |
aoqi@0 | 2307 | * is correct. There are cases when caching a captured type for later |
aoqi@0 | 2308 | * reuse is sound. In general two captures from the same AST are equal. |
aoqi@0 | 2309 | * This is why the tree is used as the key of the map below. This map |
aoqi@0 | 2310 | * stores a Type per AST. |
aoqi@0 | 2311 | */ |
aoqi@0 | 2312 | Map<JCTree, Type> captureTypeCache = new HashMap<>(); |
aoqi@0 | 2313 | |
aoqi@0 | 2314 | Type cachedCapture(JCTree tree, Type t, boolean readOnly) { |
aoqi@0 | 2315 | Type captured = captureTypeCache.get(tree); |
aoqi@0 | 2316 | if (captured != null) { |
aoqi@0 | 2317 | return captured; |
aoqi@0 | 2318 | } |
aoqi@0 | 2319 | |
aoqi@0 | 2320 | Type result = types.capture(t); |
aoqi@0 | 2321 | if (result != t && !readOnly) { // then t is a wildcard parameterized type |
aoqi@0 | 2322 | captureTypeCache.put(tree, result); |
aoqi@0 | 2323 | } |
aoqi@0 | 2324 | return result; |
aoqi@0 | 2325 | } |
aoqi@0 | 2326 | } |
aoqi@0 | 2327 | |
aoqi@0 | 2328 | final InferenceContext emptyContext = new InferenceContext(List.<Type>nil()); |
aoqi@0 | 2329 | // </editor-fold> |
aoqi@0 | 2330 | } |