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