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