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