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