Mercurial > jdk8-mips64-public > langtools / file revision
src/share/classes/com/sun/tools/javac/comp/Infer.java@963c57175e40
src/share/classes/com/sun/tools/javac/comp/Infer.java
Tue, 22 Oct 2013 13:54:49 +0100
- author
- vromero
- date
- Tue, 22 Oct 2013 13:54:49 +0100
- changeset 2157
- 963c57175e40
- parent 2047
- 5f915a0c9615
- child 2302
- f35effa10297
- permissions
- -rw-r--r--
8025290: javac implicit versus explicit lambda compilation error
Reviewed-by: jjg, dlsmith
1 /*
2 * Copyright (c) 1999, 2013, 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 public Type instantiateMethod(Env<AttrContext> env,
146 List<Type> tvars,
147 MethodType mt,
148 Attr.ResultInfo resultInfo,
149 Symbol 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);
157 inferenceException.clear();
158 try {
159 DeferredAttr.DeferredAttrContext deferredAttrContext =
160 resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
162 resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,
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(resultInfo, mt, inferenceContext);
171 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);
172 //propagate outwards if needed
173 if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {
174 //propagate inference context outwards and exit
175 inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());
176 deferredAttrContext.complete();
177 return mt;
178 }
179 }
181 deferredAttrContext.complete();
183 // minimize as yet undetermined type variables
184 if (allowGraphInference) {
185 inferenceContext.solve(warn);
186 } else {
187 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
188 }
190 mt = (MethodType)inferenceContext.asInstType(mt);
192 if (!allowGraphInference &&
193 inferenceContext.restvars().nonEmpty() &&
194 resultInfo != null &&
195 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
196 generateReturnConstraints(resultInfo, mt, inferenceContext);
197 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
198 mt = (MethodType)inferenceContext.asInstType(mt);
199 }
201 if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
202 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
203 }
205 // return instantiated version of method type
206 return mt;
207 } finally {
208 if (resultInfo != null || !allowGraphInference) {
209 inferenceContext.notifyChange();
210 } else {
211 inferenceContext.notifyChange(inferenceContext.boundedVars());
212 }
213 }
214 }
216 /**
217 * Generate constraints from the generic method's return type. If the method
218 * call occurs in a context where a type T is expected, use the expected
219 * type to derive more constraints on the generic method inference variables.
220 */
221 Type generateReturnConstraints(Attr.ResultInfo resultInfo,
222 MethodType mt, InferenceContext inferenceContext) {
223 Type from = mt.getReturnType();
224 if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
225 resultInfo.checkContext.inferenceContext() != emptyContext) {
226 from = types.capture(from);
227 //add synthetic captured ivars
228 for (Type t : from.getTypeArguments()) {
229 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
230 inferenceContext.addVar((TypeVar)t);
231 }
232 }
233 }
234 Type qtype1 = inferenceContext.asFree(from);
235 Type to = returnConstraintTarget(qtype1, resultInfo.pt);
236 Assert.check(allowGraphInference || !resultInfo.checkContext.inferenceContext().free(to),
237 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
238 //we need to skip capture?
239 Warner retWarn = new Warner();
240 if (!resultInfo.checkContext.compatible(qtype1, resultInfo.checkContext.inferenceContext().asFree(to), retWarn) ||
241 //unchecked conversion is not allowed in source 7 mode
242 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
243 throw inferenceException
244 .setMessage("infer.no.conforming.instance.exists",
245 inferenceContext.restvars(), mt.getReturnType(), to);
246 }
247 return from;
248 }
250 Type returnConstraintTarget(Type from, Type to) {
251 if (from.hasTag(VOID)) {
252 return syms.voidType;
253 } else if (to.hasTag(NONE)) {
254 return from.isPrimitive() ? from : syms.objectType;
255 } else if (from.hasTag(UNDETVAR) && to.isPrimitive()) {
256 if (!allowGraphInference) {
257 //if legacy, just return boxed type
258 return types.boxedClass(to).type;
259 }
260 //if graph inference we need to skip conflicting boxed bounds...
261 UndetVar uv = (UndetVar)from;
262 for (Type t : uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
263 Type boundAsPrimitive = types.unboxedType(t);
264 if (boundAsPrimitive == null) continue;
265 if (types.isConvertible(boundAsPrimitive, to)) {
266 //effectively skip return-type constraint generation (compatibility)
267 return syms.objectType;
268 }
269 }
270 return types.boxedClass(to).type;
271 } else {
272 return to;
273 }
274 }
276 /**
277 * Infer cyclic inference variables as described in 15.12.2.8.
278 */
279 private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {
280 ListBuffer<Type> todo = new ListBuffer<>();
281 //step 1 - create fresh tvars
282 for (Type t : vars) {
283 UndetVar uv = (UndetVar)inferenceContext.asFree(t);
284 List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);
285 if (Type.containsAny(upperBounds, vars)) {
286 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
287 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);
288 todo.append(uv);
289 uv.inst = fresh_tvar.type;
290 } else if (upperBounds.nonEmpty()) {
291 uv.inst = types.glb(upperBounds);
292 } else {
293 uv.inst = syms.objectType;
294 }
295 }
296 //step 2 - replace fresh tvars in their bounds
297 List<Type> formals = vars;
298 for (Type t : todo) {
299 UndetVar uv = (UndetVar)t;
300 TypeVar ct = (TypeVar)uv.inst;
301 ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
302 if (ct.bound.isErroneous()) {
303 //report inference error if glb fails
304 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
305 }
306 formals = formals.tail;
307 }
308 }
310 /**
311 * Compute a synthetic method type corresponding to the requested polymorphic
312 * method signature. The target return type is computed from the immediately
313 * enclosing scope surrounding the polymorphic-signature call.
314 */
315 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
316 MethodSymbol spMethod, // sig. poly. method or null if none
317 Resolve.MethodResolutionContext resolveContext,
318 List<Type> argtypes) {
319 final Type restype;
321 //The return type for a polymorphic signature call is computed from
322 //the enclosing tree E, as follows: if E is a cast, then use the
323 //target type of the cast expression as a return type; if E is an
324 //expression statement, the return type is 'void' - otherwise the
325 //return type is simply 'Object'. A correctness check ensures that
326 //env.next refers to the lexically enclosing environment in which
327 //the polymorphic signature call environment is nested.
329 switch (env.next.tree.getTag()) {
330 case TYPECAST:
331 JCTypeCast castTree = (JCTypeCast)env.next.tree;
332 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
333 castTree.clazz.type :
334 syms.objectType;
335 break;
336 case EXEC:
337 JCTree.JCExpressionStatement execTree =
338 (JCTree.JCExpressionStatement)env.next.tree;
339 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
340 syms.voidType :
341 syms.objectType;
342 break;
343 default:
344 restype = syms.objectType;
345 }
347 List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));
348 List<Type> exType = spMethod != null ?
349 spMethod.getThrownTypes() :
350 List.of(syms.throwableType); // make it throw all exceptions
352 MethodType mtype = new MethodType(paramtypes,
353 restype,
354 exType,
355 syms.methodClass);
356 return mtype;
357 }
358 //where
359 class ImplicitArgType extends DeferredAttr.DeferredTypeMap {
361 public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
362 rs.deferredAttr.super(AttrMode.SPECULATIVE, msym, phase);
363 }
365 public Type apply(Type t) {
366 t = types.erasure(super.apply(t));
367 if (t.hasTag(BOT))
368 // nulls type as the marker type Null (which has no instances)
369 // infer as java.lang.Void for now
370 t = types.boxedClass(syms.voidType).type;
371 return t;
372 }
373 }
375 /**
376 * This method is used to infer a suitable target SAM in case the original
377 * SAM type contains one or more wildcards. An inference process is applied
378 * so that wildcard bounds, as well as explicit lambda/method ref parameters
379 * (where applicable) are used to constraint the solution.
380 */
381 public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
382 List<Type> paramTypes, Check.CheckContext checkContext) {
383 if (types.capture(funcInterface) == funcInterface) {
384 //if capture doesn't change the type then return the target unchanged
385 //(this means the target contains no wildcards!)
386 return funcInterface;
387 } else {
388 Type formalInterface = funcInterface.tsym.type;
389 InferenceContext funcInterfaceContext =
390 new InferenceContext(funcInterface.tsym.type.getTypeArguments());
392 Assert.check(paramTypes != null);
393 //get constraints from explicit params (this is done by
394 //checking that explicit param types are equal to the ones
395 //in the functional interface descriptors)
396 List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
397 if (descParameterTypes.size() != paramTypes.size()) {
398 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
399 return types.createErrorType(funcInterface);
400 }
401 for (Type p : descParameterTypes) {
402 if (!types.isSameType(funcInterfaceContext.asFree(p), paramTypes.head)) {
403 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
404 return types.createErrorType(funcInterface);
405 }
406 paramTypes = paramTypes.tail;
407 }
409 try {
410 funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
411 } catch (InferenceException ex) {
412 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
413 }
415 List<Type> actualTypeargs = funcInterface.getTypeArguments();
416 for (Type t : funcInterfaceContext.undetvars) {
417 UndetVar uv = (UndetVar)t;
418 if (uv.inst == null) {
419 uv.inst = actualTypeargs.head;
420 }
421 actualTypeargs = actualTypeargs.tail;
422 }
424 Type owntype = funcInterfaceContext.asInstType(formalInterface);
425 if (!chk.checkValidGenericType(owntype)) {
426 //if the inferred functional interface type is not well-formed,
427 //or if it's not a subtype of the original target, issue an error
428 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
429 }
430 return owntype;
431 }
432 }
433 // </editor-fold>
435 // <editor-fold defaultstate="collapsed" desc="Bound checking">
436 /**
437 * Check bounds and perform incorporation
438 */
439 void checkWithinBounds(InferenceContext inferenceContext,
440 Warner warn) throws InferenceException {
441 MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);
442 List<Type> saved_undet = inferenceContext.save();
443 try {
444 while (true) {
445 mlistener.reset();
446 if (!allowGraphInference) {
447 //in legacy mode we lack of transitivity, so bound check
448 //cannot be run in parallel with other incoprporation rounds
449 for (Type t : inferenceContext.undetvars) {
450 UndetVar uv = (UndetVar)t;
451 IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);
452 }
453 }
454 for (Type t : inferenceContext.undetvars) {
455 UndetVar uv = (UndetVar)t;
456 //bound incorporation
457 EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?
458 incorporationStepsGraph : incorporationStepsLegacy;
459 for (IncorporationStep is : incorporationSteps) {
460 if (is.accepts(uv, inferenceContext)) {
461 is.apply(uv, inferenceContext, warn);
462 }
463 }
464 }
465 if (!mlistener.changed || !allowGraphInference) break;
466 }
467 }
468 finally {
469 mlistener.detach();
470 if (incorporationCache.size() == MAX_INCORPORATION_STEPS) {
471 inferenceContext.rollback(saved_undet);
472 }
473 incorporationCache.clear();
474 }
475 }
476 //where
477 /**
478 * This listener keeps track of changes on a group of inference variable
479 * bounds. Note: the listener must be detached (calling corresponding
480 * method) to make sure that the underlying inference variable is
481 * left in a clean state.
482 */
483 class MultiUndetVarListener implements UndetVar.UndetVarListener {
485 boolean changed;
486 List<Type> undetvars;
488 public MultiUndetVarListener(List<Type> undetvars) {
489 this.undetvars = undetvars;
490 for (Type t : undetvars) {
491 UndetVar uv = (UndetVar)t;
492 uv.listener = this;
493 }
494 }
496 public void varChanged(UndetVar uv, Set<InferenceBound> ibs) {
497 //avoid non-termination
498 if (incorporationCache.size() < MAX_INCORPORATION_STEPS) {
499 changed = true;
500 }
501 }
503 void reset() {
504 changed = false;
505 }
507 void detach() {
508 for (Type t : undetvars) {
509 UndetVar uv = (UndetVar)t;
510 uv.listener = null;
511 }
512 }
513 };
515 /** max number of incorporation rounds */
516 static final int MAX_INCORPORATION_STEPS = 100;
518 /**
519 * This enumeration defines an entry point for doing inference variable
520 * bound incorporation - it can be used to inject custom incorporation
521 * logic into the basic bound checking routine
522 */
523 enum IncorporationStep {
524 /**
525 * Performs basic bound checking - i.e. is the instantiated type for a given
526 * inference variable compatible with its bounds?
527 */
528 CHECK_BOUNDS() {
529 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
530 Infer infer = inferenceContext.infer();
531 uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);
532 infer.checkCompatibleUpperBounds(uv, inferenceContext);
533 if (uv.inst != null) {
534 Type inst = uv.inst;
535 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
536 if (!isSubtype(inst, inferenceContext.asFree(u), warn, infer)) {
537 infer.reportBoundError(uv, BoundErrorKind.UPPER);
538 }
539 }
540 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
541 if (!isSubtype(inferenceContext.asFree(l), inst, warn, infer)) {
542 infer.reportBoundError(uv, BoundErrorKind.LOWER);
543 }
544 }
545 for (Type e : uv.getBounds(InferenceBound.EQ)) {
546 if (!isSameType(inst, inferenceContext.asFree(e), infer)) {
547 infer.reportBoundError(uv, BoundErrorKind.EQ);
548 }
549 }
550 }
551 }
552 @Override
553 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
554 //applies to all undetvars
555 return true;
556 }
557 },
558 /**
559 * Check consistency of equality constraints. This is a slightly more aggressive
560 * inference routine that is designed as to maximize compatibility with JDK 7.
561 * Note: this is not used in graph mode.
562 */
563 EQ_CHECK_LEGACY() {
564 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
565 Infer infer = inferenceContext.infer();
566 Type eq = null;
567 for (Type e : uv.getBounds(InferenceBound.EQ)) {
568 Assert.check(!inferenceContext.free(e));
569 if (eq != null && !isSameType(e, eq, infer)) {
570 infer.reportBoundError(uv, BoundErrorKind.EQ);
571 }
572 eq = e;
573 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
574 Assert.check(!inferenceContext.free(l));
575 if (!isSubtype(l, e, warn, infer)) {
576 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
577 }
578 }
579 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
580 if (inferenceContext.free(u)) continue;
581 if (!isSubtype(e, u, warn, infer)) {
582 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
583 }
584 }
585 }
586 }
587 },
588 /**
589 * Check consistency of equality constraints.
590 */
591 EQ_CHECK() {
592 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
593 Infer infer = inferenceContext.infer();
594 for (Type e : uv.getBounds(InferenceBound.EQ)) {
595 if (e.containsAny(inferenceContext.inferenceVars())) continue;
596 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
597 if (!isSubtype(e, inferenceContext.asFree(u), warn, infer)) {
598 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
599 }
600 }
601 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
602 if (!isSubtype(inferenceContext.asFree(l), e, warn, infer)) {
603 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
604 }
605 }
606 }
607 }
608 },
609 /**
610 * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}
611 * perform {@code S <: T} (which could lead to new bounds).
612 */
613 CROSS_UPPER_LOWER() {
614 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
615 Infer infer = inferenceContext.infer();
616 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
617 for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
618 isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn , infer);
619 }
620 }
621 }
622 },
623 /**
624 * Given a bound set containing {@code alpha <: T} and {@code alpha == S}
625 * perform {@code S <: T} (which could lead to new bounds).
626 */
627 CROSS_UPPER_EQ() {
628 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
629 Infer infer = inferenceContext.infer();
630 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
631 for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
632 isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn, infer);
633 }
634 }
635 }
636 },
637 /**
638 * Given a bound set containing {@code alpha :> S} and {@code alpha == T}
639 * perform {@code S <: T} (which could lead to new bounds).
640 */
641 CROSS_EQ_LOWER() {
642 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
643 Infer infer = inferenceContext.infer();
644 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
645 for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
646 isSubtype(inferenceContext.asFree(b2), inferenceContext.asFree(b1), warn, infer);
647 }
648 }
649 }
650 },
651 /**
652 * Given a bound set containing {@code alpha == S} and {@code alpha == T}
653 * perform {@code S == T} (which could lead to new bounds).
654 */
655 CROSS_EQ_EQ() {
656 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
657 Infer infer = inferenceContext.infer();
658 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
659 for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
660 if (b1 != b2) {
661 isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1), infer);
662 }
663 }
664 }
665 }
666 },
667 /**
668 * Given a bound set containing {@code alpha <: beta} propagate lower bounds
669 * from alpha to beta; also propagate upper bounds from beta to alpha.
670 */
671 PROP_UPPER() {
672 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
673 Infer infer = inferenceContext.infer();
674 for (Type b : uv.getBounds(InferenceBound.UPPER)) {
675 if (inferenceContext.inferenceVars().contains(b)) {
676 UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
677 if (uv2.isCaptured()) continue;
678 //alpha <: beta
679 //0. set beta :> alpha
680 addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(uv.qtype), infer);
681 //1. copy alpha's lower to beta's
682 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
683 addBound(InferenceBound.LOWER, uv2, inferenceContext.asInstType(l), infer);
684 }
685 //2. copy beta's upper to alpha's
686 for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
687 addBound(InferenceBound.UPPER, uv, inferenceContext.asInstType(u), infer);
688 }
689 }
690 }
691 }
692 },
693 /**
694 * Given a bound set containing {@code alpha :> beta} propagate lower bounds
695 * from beta to alpha; also propagate upper bounds from alpha to beta.
696 */
697 PROP_LOWER() {
698 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
699 Infer infer = inferenceContext.infer();
700 for (Type b : uv.getBounds(InferenceBound.LOWER)) {
701 if (inferenceContext.inferenceVars().contains(b)) {
702 UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
703 if (uv2.isCaptured()) continue;
704 //alpha :> beta
705 //0. set beta <: alpha
706 addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(uv.qtype), infer);
707 //1. copy alpha's upper to beta's
708 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
709 addBound(InferenceBound.UPPER, uv2, inferenceContext.asInstType(u), infer);
710 }
711 //2. copy beta's lower to alpha's
712 for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
713 addBound(InferenceBound.LOWER, uv, inferenceContext.asInstType(l), infer);
714 }
715 }
716 }
717 }
718 },
719 /**
720 * Given a bound set containing {@code alpha == beta} propagate lower/upper
721 * bounds from alpha to beta and back.
722 */
723 PROP_EQ() {
724 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
725 Infer infer = inferenceContext.infer();
726 for (Type b : uv.getBounds(InferenceBound.EQ)) {
727 if (inferenceContext.inferenceVars().contains(b)) {
728 UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
729 if (uv2.isCaptured()) continue;
730 //alpha == beta
731 //0. set beta == alpha
732 addBound(InferenceBound.EQ, uv2, inferenceContext.asInstType(uv.qtype), infer);
733 //1. copy all alpha's bounds to beta's
734 for (InferenceBound ib : InferenceBound.values()) {
735 for (Type b2 : uv.getBounds(ib)) {
736 if (b2 != uv2) {
737 addBound(ib, uv2, inferenceContext.asInstType(b2), infer);
738 }
739 }
740 }
741 //2. copy all beta's bounds to alpha's
742 for (InferenceBound ib : InferenceBound.values()) {
743 for (Type b2 : uv2.getBounds(ib)) {
744 if (b2 != uv) {
745 addBound(ib, uv, inferenceContext.asInstType(b2), infer);
746 }
747 }
748 }
749 }
750 }
751 }
752 };
754 abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);
756 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
757 return !uv.isCaptured();
758 }
760 boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
761 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
762 }
764 boolean isSameType(Type s, Type t, Infer infer) {
765 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
766 }
768 void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
769 doIncorporationOp(opFor(ib), uv, b, null, infer);
770 }
772 IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
773 switch (boundKind) {
774 case EQ:
775 return IncorporationBinaryOpKind.ADD_EQ_BOUND;
776 case LOWER:
777 return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
778 case UPPER:
779 return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
780 default:
781 Assert.error("Can't get here!");
782 return null;
783 }
784 }
786 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
787 IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
788 Boolean res = infer.incorporationCache.get(newOp);
789 if (res == null) {
790 infer.incorporationCache.put(newOp, res = newOp.apply(warn));
791 }
792 return res;
793 }
794 }
796 /** incorporation steps to be executed when running in legacy mode */
797 EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);
799 /** incorporation steps to be executed when running in graph mode */
800 EnumSet<IncorporationStep> incorporationStepsGraph =
801 EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
803 /**
804 * Three kinds of basic operation are supported as part of an incorporation step:
805 * (i) subtype check, (ii) same type check and (iii) bound addition (either
806 * upper/lower/eq bound).
807 */
808 enum IncorporationBinaryOpKind {
809 IS_SUBTYPE() {
810 @Override
811 boolean apply(Type op1, Type op2, Warner warn, Types types) {
812 return types.isSubtypeUnchecked(op1, op2, warn);
813 }
814 },
815 IS_SAME_TYPE() {
816 @Override
817 boolean apply(Type op1, Type op2, Warner warn, Types types) {
818 return types.isSameType(op1, op2);
819 }
820 },
821 ADD_UPPER_BOUND() {
822 @Override
823 boolean apply(Type op1, Type op2, Warner warn, Types types) {
824 UndetVar uv = (UndetVar)op1;
825 uv.addBound(InferenceBound.UPPER, op2, types);
826 return true;
827 }
828 },
829 ADD_LOWER_BOUND() {
830 @Override
831 boolean apply(Type op1, Type op2, Warner warn, Types types) {
832 UndetVar uv = (UndetVar)op1;
833 uv.addBound(InferenceBound.LOWER, op2, types);
834 return true;
835 }
836 },
837 ADD_EQ_BOUND() {
838 @Override
839 boolean apply(Type op1, Type op2, Warner warn, Types types) {
840 UndetVar uv = (UndetVar)op1;
841 uv.addBound(InferenceBound.EQ, op2, types);
842 return true;
843 }
844 };
846 abstract boolean apply(Type op1, Type op2, Warner warn, Types types);
847 }
849 /**
850 * This class encapsulates a basic incorporation operation; incorporation
851 * operations takes two type operands and a kind. Each operation performed
852 * during an incorporation round is stored in a cache, so that operations
853 * are not executed unnecessarily (which would potentially lead to adding
854 * same bounds over and over).
855 */
856 class IncorporationBinaryOp {
858 IncorporationBinaryOpKind opKind;
859 Type op1;
860 Type op2;
862 IncorporationBinaryOp(IncorporationBinaryOpKind opKind, Type op1, Type op2) {
863 this.opKind = opKind;
864 this.op1 = op1;
865 this.op2 = op2;
866 }
868 @Override
869 public boolean equals(Object o) {
870 if (!(o instanceof IncorporationBinaryOp)) {
871 return false;
872 } else {
873 IncorporationBinaryOp that = (IncorporationBinaryOp)o;
874 return opKind == that.opKind &&
875 types.isSameType(op1, that.op1, true) &&
876 types.isSameType(op2, that.op2, true);
877 }
878 }
880 @Override
881 public int hashCode() {
882 int result = opKind.hashCode();
883 result *= 127;
884 result += types.hashCode(op1);
885 result *= 127;
886 result += types.hashCode(op2);
887 return result;
888 }
890 boolean apply(Warner warn) {
891 return opKind.apply(op1, op2, warn, types);
892 }
893 }
895 /** an incorporation cache keeps track of all executed incorporation-related operations */
896 Map<IncorporationBinaryOp, Boolean> incorporationCache =
897 new HashMap<IncorporationBinaryOp, Boolean>();
899 /**
900 * Make sure that the upper bounds we got so far lead to a solvable inference
901 * variable by making sure that a glb exists.
902 */
903 void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
904 List<Type> hibounds =
905 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
906 Type hb = null;
907 if (hibounds.isEmpty())
908 hb = syms.objectType;
909 else if (hibounds.tail.isEmpty())
910 hb = hibounds.head;
911 else
912 hb = types.glb(hibounds);
913 if (hb == null || hb.isErroneous())
914 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
915 }
916 //where
917 protected static class BoundFilter implements Filter<Type> {
919 InferenceContext inferenceContext;
921 public BoundFilter(InferenceContext inferenceContext) {
922 this.inferenceContext = inferenceContext;
923 }
925 @Override
926 public boolean accepts(Type t) {
927 return !t.isErroneous() && !inferenceContext.free(t) &&
928 !t.hasTag(BOT);
929 }
930 };
932 /**
933 * This enumeration defines all possible bound-checking related errors.
934 */
935 enum BoundErrorKind {
936 /**
937 * The (uninstantiated) inference variable has incompatible upper bounds.
938 */
939 BAD_UPPER() {
940 @Override
941 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
942 return ex.setMessage("incompatible.upper.bounds", uv.qtype,
943 uv.getBounds(InferenceBound.UPPER));
944 }
945 },
946 /**
947 * An equality constraint is not compatible with an upper bound.
948 */
949 BAD_EQ_UPPER() {
950 @Override
951 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
952 return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,
953 uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));
954 }
955 },
956 /**
957 * An equality constraint is not compatible with a lower bound.
958 */
959 BAD_EQ_LOWER() {
960 @Override
961 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
962 return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,
963 uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));
964 }
965 },
966 /**
967 * Instantiated inference variable is not compatible with an upper bound.
968 */
969 UPPER() {
970 @Override
971 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
972 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,
973 uv.getBounds(InferenceBound.UPPER));
974 }
975 },
976 /**
977 * Instantiated inference variable is not compatible with a lower bound.
978 */
979 LOWER() {
980 @Override
981 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
982 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,
983 uv.getBounds(InferenceBound.LOWER));
984 }
985 },
986 /**
987 * Instantiated inference variable is not compatible with an equality constraint.
988 */
989 EQ() {
990 @Override
991 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
992 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,
993 uv.getBounds(InferenceBound.EQ));
994 }
995 };
997 abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
998 }
1000 /**
1001 * Report a bound-checking error of given kind
1002 */
1003 void reportBoundError(UndetVar uv, BoundErrorKind bk) {
1004 throw bk.setMessage(inferenceException, uv);
1005 }
1006 // </editor-fold>
1008 // <editor-fold defaultstate="collapsed" desc="Inference engine">
1009 /**
1010 * Graph inference strategy - act as an input to the inference solver; a strategy is
1011 * composed of two ingredients: (i) find a node to solve in the inference graph,
1012 * and (ii) tell th engine when we are done fixing inference variables
1013 */
1014 interface GraphStrategy {
1016 /**
1017 * A NodeNotFoundException is thrown whenever an inference strategy fails
1018 * to pick the next node to solve in the inference graph.
1019 */
1020 public static class NodeNotFoundException extends RuntimeException {
1021 private static final long serialVersionUID = 0;
1023 InferenceGraph graph;
1025 public NodeNotFoundException(InferenceGraph graph) {
1026 this.graph = graph;
1027 }
1028 }
1029 /**
1030 * Pick the next node (leaf) to solve in the graph
1031 */
1032 Node pickNode(InferenceGraph g) throws NodeNotFoundException;
1033 /**
1034 * Is this the last step?
1035 */
1036 boolean done();
1037 }
1039 /**
1040 * Simple solver strategy class that locates all leaves inside a graph
1041 * and picks the first leaf as the next node to solve
1042 */
1043 abstract class LeafSolver implements GraphStrategy {
1044 public Node pickNode(InferenceGraph g) {
1045 if (g.nodes.isEmpty()) {
1046 //should not happen
1047 throw new NodeNotFoundException(g);
1048 };
1049 return g.nodes.get(0);
1050 }
1052 boolean isSubtype(Type s, Type t, Warner warn, Infer infer) {
1053 return doIncorporationOp(IncorporationBinaryOpKind.IS_SUBTYPE, s, t, warn, infer);
1054 }
1056 boolean isSameType(Type s, Type t, Infer infer) {
1057 return doIncorporationOp(IncorporationBinaryOpKind.IS_SAME_TYPE, s, t, null, infer);
1058 }
1060 void addBound(InferenceBound ib, UndetVar uv, Type b, Infer infer) {
1061 doIncorporationOp(opFor(ib), uv, b, null, infer);
1062 }
1064 IncorporationBinaryOpKind opFor(InferenceBound boundKind) {
1065 switch (boundKind) {
1066 case EQ:
1067 return IncorporationBinaryOpKind.ADD_EQ_BOUND;
1068 case LOWER:
1069 return IncorporationBinaryOpKind.ADD_LOWER_BOUND;
1070 case UPPER:
1071 return IncorporationBinaryOpKind.ADD_UPPER_BOUND;
1072 default:
1073 Assert.error("Can't get here!");
1074 return null;
1075 }
1076 }
1078 boolean doIncorporationOp(IncorporationBinaryOpKind opKind, Type op1, Type op2, Warner warn, Infer infer) {
1079 IncorporationBinaryOp newOp = infer.new IncorporationBinaryOp(opKind, op1, op2);
1080 Boolean res = infer.incorporationCache.get(newOp);
1081 if (res == null) {
1082 infer.incorporationCache.put(newOp, res = newOp.apply(warn));
1083 }
1084 return res;
1085 }
1086 }
1088 /**
1089 * This solver uses an heuristic to pick the best leaf - the heuristic
1090 * tries to select the node that has maximal probability to contain one
1091 * or more inference variables in a given list
1092 */
1093 abstract class BestLeafSolver extends LeafSolver {
1095 /** list of ivars of which at least one must be solved */
1096 List<Type> varsToSolve;
1098 BestLeafSolver(List<Type> varsToSolve) {
1099 this.varsToSolve = varsToSolve;
1100 }
1102 /**
1103 * Computes a path that goes from a given node to the leafs in the graph.
1104 * Typically this will start from a node containing a variable in
1105 * {@code varsToSolve}. For any given path, the cost is computed as the total
1106 * number of type-variables that should be eagerly instantiated across that path.
1107 */
1108 Pair<List<Node>, Integer> computeTreeToLeafs(Node n) {
1109 Pair<List<Node>, Integer> cachedPath = treeCache.get(n);
1110 if (cachedPath == null) {
1111 //cache miss
1112 if (n.isLeaf()) {
1113 //if leaf, stop
1114 cachedPath = new Pair<List<Node>, Integer>(List.of(n), n.data.length());
1115 } else {
1116 //if non-leaf, proceed recursively
1117 Pair<List<Node>, Integer> path = new Pair<List<Node>, Integer>(List.of(n), n.data.length());
1118 for (Node n2 : n.getAllDependencies()) {
1119 if (n2 == n) continue;
1120 Pair<List<Node>, Integer> subpath = computeTreeToLeafs(n2);
1121 path = new Pair<List<Node>, Integer>(
1122 path.fst.prependList(subpath.fst),
1123 path.snd + subpath.snd);
1124 }
1125 cachedPath = path;
1126 }
1127 //save results in cache
1128 treeCache.put(n, cachedPath);
1129 }
1130 return cachedPath;
1131 }
1133 /** cache used to avoid redundant computation of tree costs */
1134 final Map<Node, Pair<List<Node>, Integer>> treeCache =
1135 new HashMap<Node, Pair<List<Node>, Integer>>();
1137 /** constant value used to mark non-existent paths */
1138 final Pair<List<Node>, Integer> noPath =
1139 new Pair<List<Node>, Integer>(null, Integer.MAX_VALUE);
1141 /**
1142 * Pick the leaf that minimize cost
1143 */
1144 @Override
1145 public Node pickNode(final InferenceGraph g) {
1146 treeCache.clear(); //graph changes at every step - cache must be cleared
1147 Pair<List<Node>, Integer> bestPath = noPath;
1148 for (Node n : g.nodes) {
1149 if (!Collections.disjoint(n.data, varsToSolve)) {
1150 Pair<List<Node>, Integer> path = computeTreeToLeafs(n);
1151 //discard all paths containing at least a node in the
1152 //closure computed above
1153 if (path.snd < bestPath.snd) {
1154 bestPath = path;
1155 }
1156 }
1157 }
1158 if (bestPath == noPath) {
1159 //no path leads there
1160 throw new NodeNotFoundException(g);
1161 }
1162 return bestPath.fst.head;
1163 }
1164 }
1166 /**
1167 * The inference process can be thought of as a sequence of steps. Each step
1168 * instantiates an inference variable using a subset of the inference variable
1169 * bounds, if certain condition are met. Decisions such as the sequence in which
1170 * steps are applied, or which steps are to be applied are left to the inference engine.
1171 */
1172 enum InferenceStep {
1174 /**
1175 * Instantiate an inference variables using one of its (ground) equality
1176 * constraints
1177 */
1178 EQ(InferenceBound.EQ) {
1179 @Override
1180 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1181 return filterBounds(uv, inferenceContext).head;
1182 }
1183 },
1184 /**
1185 * Instantiate an inference variables using its (ground) lower bounds. Such
1186 * bounds are merged together using lub().
1187 */
1188 LOWER(InferenceBound.LOWER) {
1189 @Override
1190 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1191 Infer infer = inferenceContext.infer();
1192 List<Type> lobounds = filterBounds(uv, inferenceContext);
1193 //note: lobounds should have at least one element
1194 Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds);
1195 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
1196 throw infer.inferenceException
1197 .setMessage("no.unique.minimal.instance.exists",
1198 uv.qtype, lobounds);
1199 } else {
1200 return owntype;
1201 }
1202 }
1203 },
1204 /**
1205 * Infer uninstantiated/unbound inference variables occurring in 'throws'
1206 * clause as RuntimeException
1207 */
1208 THROWS(InferenceBound.UPPER) {
1209 @Override
1210 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1211 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {
1212 //not a throws undet var
1213 return false;
1214 }
1215 if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)
1216 .diff(t.getDeclaredBounds()).nonEmpty()) {
1217 //not an unbounded undet var
1218 return false;
1219 }
1220 Infer infer = inferenceContext.infer();
1221 for (Type db : t.getDeclaredBounds()) {
1222 if (t.isInterface()) continue;
1223 if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {
1224 //declared bound is a supertype of RuntimeException
1225 return true;
1226 }
1227 }
1228 //declared bound is more specific then RuntimeException - give up
1229 return false;
1230 }
1232 @Override
1233 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1234 return inferenceContext.infer().syms.runtimeExceptionType;
1235 }
1236 },
1237 /**
1238 * Instantiate an inference variables using its (ground) upper bounds. Such
1239 * bounds are merged together using glb().
1240 */
1241 UPPER(InferenceBound.UPPER) {
1242 @Override
1243 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1244 Infer infer = inferenceContext.infer();
1245 List<Type> hibounds = filterBounds(uv, inferenceContext);
1246 //note: lobounds should have at least one element
1247 Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds);
1248 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
1249 throw infer.inferenceException
1250 .setMessage("no.unique.maximal.instance.exists",
1251 uv.qtype, hibounds);
1252 } else {
1253 return owntype;
1254 }
1255 }
1256 },
1257 /**
1258 * Like the former; the only difference is that this step can only be applied
1259 * if all upper bounds are ground.
1260 */
1261 UPPER_LEGACY(InferenceBound.UPPER) {
1262 @Override
1263 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1264 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
1265 }
1267 @Override
1268 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1269 return UPPER.solve(uv, inferenceContext);
1270 }
1271 },
1272 /**
1273 * Like the former; the only difference is that this step can only be applied
1274 * if all upper/lower bounds are ground.
1275 */
1276 CAPTURED(InferenceBound.UPPER) {
1277 @Override
1278 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1279 return t.isCaptured() &&
1280 !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
1281 }
1283 @Override
1284 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1285 Infer infer = inferenceContext.infer();
1286 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
1287 UPPER.solve(uv, inferenceContext) :
1288 infer.syms.objectType;
1289 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
1290 LOWER.solve(uv, inferenceContext) :
1291 infer.syms.botType;
1292 CapturedType prevCaptured = (CapturedType)uv.qtype;
1293 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard);
1294 }
1295 };
1297 final InferenceBound ib;
1299 InferenceStep(InferenceBound ib) {
1300 this.ib = ib;
1301 }
1303 /**
1304 * Find an instantiated type for a given inference variable within
1305 * a given inference context
1306 */
1307 abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
1309 /**
1310 * Can the inference variable be instantiated using this step?
1311 */
1312 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1313 return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
1314 }
1316 /**
1317 * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
1318 */
1319 List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {
1320 return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
1321 }
1322 }
1324 /**
1325 * This enumeration defines the sequence of steps to be applied when the
1326 * solver works in legacy mode. The steps in this enumeration reflect
1327 * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
1328 */
1329 enum LegacyInferenceSteps {
1331 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
1332 EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
1334 final EnumSet<InferenceStep> steps;
1336 LegacyInferenceSteps(EnumSet<InferenceStep> steps) {
1337 this.steps = steps;
1338 }
1339 }
1341 /**
1342 * This enumeration defines the sequence of steps to be applied when the
1343 * graph solver is used. This order is defined so as to maximize compatibility
1344 * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
1345 */
1346 enum GraphInferenceSteps {
1348 EQ(EnumSet.of(InferenceStep.EQ)),
1349 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
1350 EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));
1352 final EnumSet<InferenceStep> steps;
1354 GraphInferenceSteps(EnumSet<InferenceStep> steps) {
1355 this.steps = steps;
1356 }
1357 }
1359 /**
1360 * There are two kinds of dependencies between inference variables. The basic
1361 * kind of dependency (or bound dependency) arises when a variable mention
1362 * another variable in one of its bounds. There's also a more subtle kind
1363 * of dependency that arises when a variable 'might' lead to better constraints
1364 * on another variable (this is typically the case with variables holding up
1365 * stuck expressions).
1366 */
1367 enum DependencyKind implements GraphUtils.DependencyKind {
1369 /** bound dependency */
1370 BOUND("dotted"),
1371 /** stuck dependency */
1372 STUCK("dashed");
1374 final String dotSyle;
1376 private DependencyKind(String dotSyle) {
1377 this.dotSyle = dotSyle;
1378 }
1380 @Override
1381 public String getDotStyle() {
1382 return dotSyle;
1383 }
1384 }
1386 /**
1387 * This is the graph inference solver - the solver organizes all inference variables in
1388 * a given inference context by bound dependencies - in the general case, such dependencies
1389 * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
1390 * an acyclic graph, where all cyclic variables are bundled together. An inference
1391 * step corresponds to solving a node in the acyclic graph - this is done by
1392 * relying on a given strategy (see GraphStrategy).
1393 */
1394 class GraphSolver {
1396 InferenceContext inferenceContext;
1397 Map<Type, Set<Type>> stuckDeps;
1398 Warner warn;
1400 GraphSolver(InferenceContext inferenceContext, Map<Type, Set<Type>> stuckDeps, Warner warn) {
1401 this.inferenceContext = inferenceContext;
1402 this.stuckDeps = stuckDeps;
1403 this.warn = warn;
1404 }
1406 /**
1407 * Solve variables in a given inference context. The amount of variables
1408 * to be solved, and the way in which the underlying acyclic graph is explored
1409 * depends on the selected solver strategy.
1410 */
1411 void solve(GraphStrategy sstrategy) {
1412 checkWithinBounds(inferenceContext, warn); //initial propagation of bounds
1413 InferenceGraph inferenceGraph = new InferenceGraph(stuckDeps);
1414 while (!sstrategy.done()) {
1415 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
1416 List<Type> varsToSolve = List.from(nodeToSolve.data);
1417 List<Type> saved_undet = inferenceContext.save();
1418 try {
1419 //repeat until all variables are solved
1420 outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
1421 //for each inference phase
1422 for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
1423 if (inferenceContext.solveBasic(varsToSolve, step.steps)) {
1424 checkWithinBounds(inferenceContext, warn);
1425 continue outer;
1426 }
1427 }
1428 //no progress
1429 throw inferenceException.setMessage();
1430 }
1431 }
1432 catch (InferenceException ex) {
1433 //did we fail because of interdependent ivars?
1434 inferenceContext.rollback(saved_undet);
1435 instantiateAsUninferredVars(varsToSolve, inferenceContext);
1436 checkWithinBounds(inferenceContext, warn);
1437 }
1438 inferenceGraph.deleteNode(nodeToSolve);
1439 }
1440 }
1442 /**
1443 * The dependencies between the inference variables that need to be solved
1444 * form a (possibly cyclic) graph. This class reduces the original dependency graph
1445 * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
1446 */
1447 class InferenceGraph {
1449 /**
1450 * This class represents a node in the graph. Each node corresponds
1451 * to an inference variable and has edges (dependencies) on other
1452 * nodes. The node defines an entry point that can be used to receive
1453 * updates on the structure of the graph this node belongs to (used to
1454 * keep dependencies in sync).
1455 */
1456 class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> {
1458 /** map listing all dependencies (grouped by kind) */
1459 EnumMap<DependencyKind, Set<Node>> deps;
1461 Node(Type ivar) {
1462 super(ListBuffer.of(ivar));
1463 this.deps = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class);
1464 }
1466 @Override
1467 public GraphUtils.DependencyKind[] getSupportedDependencyKinds() {
1468 return DependencyKind.values();
1469 }
1471 @Override
1472 public String getDependencyName(GraphUtils.Node<ListBuffer<Type>> to, GraphUtils.DependencyKind dk) {
1473 if (dk == DependencyKind.STUCK) return "";
1474 else {
1475 StringBuilder buf = new StringBuilder();
1476 String sep = "";
1477 for (Type from : data) {
1478 UndetVar uv = (UndetVar)inferenceContext.asFree(from);
1479 for (Type bound : uv.getBounds(InferenceBound.values())) {
1480 if (bound.containsAny(List.from(to.data))) {
1481 buf.append(sep);
1482 buf.append(bound);
1483 sep = ",";
1484 }
1485 }
1486 }
1487 return buf.toString();
1488 }
1489 }
1491 @Override
1492 public Iterable<? extends Node> getAllDependencies() {
1493 return getDependencies(DependencyKind.values());
1494 }
1496 @Override
1497 public Iterable<? extends TarjanNode<ListBuffer<Type>>> getDependenciesByKind(GraphUtils.DependencyKind dk) {
1498 return getDependencies((DependencyKind)dk);
1499 }
1501 /**
1502 * Retrieves all dependencies with given kind(s).
1503 */
1504 protected Set<Node> getDependencies(DependencyKind... depKinds) {
1505 Set<Node> buf = new LinkedHashSet<Node>();
1506 for (DependencyKind dk : depKinds) {
1507 Set<Node> depsByKind = deps.get(dk);
1508 if (depsByKind != null) {
1509 buf.addAll(depsByKind);
1510 }
1511 }
1512 return buf;
1513 }
1515 /**
1516 * Adds dependency with given kind.
1517 */
1518 protected void addDependency(DependencyKind dk, Node depToAdd) {
1519 Set<Node> depsByKind = deps.get(dk);
1520 if (depsByKind == null) {
1521 depsByKind = new LinkedHashSet<Node>();
1522 deps.put(dk, depsByKind);
1523 }
1524 depsByKind.add(depToAdd);
1525 }
1527 /**
1528 * Add multiple dependencies of same given kind.
1529 */
1530 protected void addDependencies(DependencyKind dk, Set<Node> depsToAdd) {
1531 for (Node n : depsToAdd) {
1532 addDependency(dk, n);
1533 }
1534 }
1536 /**
1537 * Remove a dependency, regardless of its kind.
1538 */
1539 protected Set<DependencyKind> removeDependency(Node n) {
1540 Set<DependencyKind> removedKinds = new HashSet<>();
1541 for (DependencyKind dk : DependencyKind.values()) {
1542 Set<Node> depsByKind = deps.get(dk);
1543 if (depsByKind == null) continue;
1544 if (depsByKind.remove(n)) {
1545 removedKinds.add(dk);
1546 }
1547 }
1548 return removedKinds;
1549 }
1551 /**
1552 * Compute closure of a give node, by recursively walking
1553 * through all its dependencies (of given kinds)
1554 */
1555 protected Set<Node> closure(DependencyKind... depKinds) {
1556 boolean progress = true;
1557 Set<Node> closure = new HashSet<Node>();
1558 closure.add(this);
1559 while (progress) {
1560 progress = false;
1561 for (Node n1 : new HashSet<Node>(closure)) {
1562 progress = closure.addAll(n1.getDependencies(depKinds));
1563 }
1564 }
1565 return closure;
1566 }
1568 /**
1569 * Is this node a leaf? This means either the node has no dependencies,
1570 * or it just has self-dependencies.
1571 */
1572 protected boolean isLeaf() {
1573 //no deps, or only one self dep
1574 Set<Node> allDeps = getDependencies(DependencyKind.BOUND, DependencyKind.STUCK);
1575 if (allDeps.isEmpty()) return true;
1576 for (Node n : allDeps) {
1577 if (n != this) {
1578 return false;
1579 }
1580 }
1581 return true;
1582 }
1584 /**
1585 * Merge this node with another node, acquiring its dependencies.
1586 * This routine is used to merge all cyclic node together and
1587 * form an acyclic graph.
1588 */
1589 protected void mergeWith(List<? extends Node> nodes) {
1590 for (Node n : nodes) {
1591 Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
1592 data.appendList(n.data);
1593 for (DependencyKind dk : DependencyKind.values()) {
1594 addDependencies(dk, n.getDependencies(dk));
1595 }
1596 }
1597 //update deps
1598 EnumMap<DependencyKind, Set<Node>> deps2 = new EnumMap<DependencyKind, Set<Node>>(DependencyKind.class);
1599 for (DependencyKind dk : DependencyKind.values()) {
1600 for (Node d : getDependencies(dk)) {
1601 Set<Node> depsByKind = deps2.get(dk);
1602 if (depsByKind == null) {
1603 depsByKind = new LinkedHashSet<Node>();
1604 deps2.put(dk, depsByKind);
1605 }
1606 if (data.contains(d.data.first())) {
1607 depsByKind.add(this);
1608 } else {
1609 depsByKind.add(d);
1610 }
1611 }
1612 }
1613 deps = deps2;
1614 }
1616 /**
1617 * Notify all nodes that something has changed in the graph
1618 * topology.
1619 */
1620 private void graphChanged(Node from, Node to) {
1621 for (DependencyKind dk : removeDependency(from)) {
1622 if (to != null) {
1623 addDependency(dk, to);
1624 }
1625 }
1626 }
1627 }
1629 /** the nodes in the inference graph */
1630 ArrayList<Node> nodes;
1632 InferenceGraph(Map<Type, Set<Type>> optDeps) {
1633 initNodes(optDeps);
1634 }
1636 /**
1637 * Basic lookup helper for retrieving a graph node given an inference
1638 * variable type.
1639 */
1640 public Node findNode(Type t) {
1641 for (Node n : nodes) {
1642 if (n.data.contains(t)) {
1643 return n;
1644 }
1645 }
1646 return null;
1647 }
1649 /**
1650 * Delete a node from the graph. This update the underlying structure
1651 * of the graph (including dependencies) via listeners updates.
1652 */
1653 public void deleteNode(Node n) {
1654 Assert.check(nodes.contains(n));
1655 nodes.remove(n);
1656 notifyUpdate(n, null);
1657 }
1659 /**
1660 * Notify all nodes of a change in the graph. If the target node is
1661 * {@code null} the source node is assumed to be removed.
1662 */
1663 void notifyUpdate(Node from, Node to) {
1664 for (Node n : nodes) {
1665 n.graphChanged(from, to);
1666 }
1667 }
1669 /**
1670 * Create the graph nodes. First a simple node is created for every inference
1671 * variables to be solved. Then Tarjan is used to found all connected components
1672 * in the graph. For each component containing more than one node, a super node is
1673 * created, effectively replacing the original cyclic nodes.
1674 */
1675 void initNodes(Map<Type, Set<Type>> stuckDeps) {
1676 //add nodes
1677 nodes = new ArrayList<Node>();
1678 for (Type t : inferenceContext.restvars()) {
1679 nodes.add(new Node(t));
1680 }
1681 //add dependencies
1682 for (Node n_i : nodes) {
1683 Type i = n_i.data.first();
1684 Set<Type> optDepsByNode = stuckDeps.get(i);
1685 for (Node n_j : nodes) {
1686 Type j = n_j.data.first();
1687 UndetVar uv_i = (UndetVar)inferenceContext.asFree(i);
1688 if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
1689 //update i's bound dependencies
1690 n_i.addDependency(DependencyKind.BOUND, n_j);
1691 }
1692 if (optDepsByNode != null && optDepsByNode.contains(j)) {
1693 //update i's stuck dependencies
1694 n_i.addDependency(DependencyKind.STUCK, n_j);
1695 }
1696 }
1697 }
1698 //merge cyclic nodes
1699 ArrayList<Node> acyclicNodes = new ArrayList<Node>();
1700 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
1701 if (conSubGraph.length() > 1) {
1702 Node root = conSubGraph.head;
1703 root.mergeWith(conSubGraph.tail);
1704 for (Node n : conSubGraph) {
1705 notifyUpdate(n, root);
1706 }
1707 }
1708 acyclicNodes.add(conSubGraph.head);
1709 }
1710 nodes = acyclicNodes;
1711 }
1713 /**
1714 * Debugging: dot representation of this graph
1715 */
1716 String toDot() {
1717 StringBuilder buf = new StringBuilder();
1718 for (Type t : inferenceContext.undetvars) {
1719 UndetVar uv = (UndetVar)t;
1720 buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
1721 uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
1722 uv.getBounds(InferenceBound.EQ)));
1723 }
1724 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
1725 }
1726 }
1727 }
1728 // </editor-fold>
1730 // <editor-fold defaultstate="collapsed" desc="Inference context">
1731 /**
1732 * Functional interface for defining inference callbacks. Certain actions
1733 * (i.e. subtyping checks) might need to be redone after all inference variables
1734 * have been fixed.
1735 */
1736 interface FreeTypeListener {
1737 void typesInferred(InferenceContext inferenceContext);
1738 }
1740 /**
1741 * An inference context keeps track of the set of variables that are free
1742 * in the current context. It provides utility methods for opening/closing
1743 * types to their corresponding free/closed forms. It also provide hooks for
1744 * attaching deferred post-inference action (see PendingCheck). Finally,
1745 * it can be used as an entry point for performing upper/lower bound inference
1746 * (see InferenceKind).
1747 */
1748 class InferenceContext {
1750 /** list of inference vars as undet vars */
1751 List<Type> undetvars;
1753 /** list of inference vars in this context */
1754 List<Type> inferencevars;
1756 java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners =
1757 new java.util.HashMap<FreeTypeListener, List<Type>>();
1759 List<FreeTypeListener> freetypeListeners = List.nil();
1761 public InferenceContext(List<Type> inferencevars) {
1762 this.undetvars = Type.map(inferencevars, fromTypeVarFun);
1763 this.inferencevars = inferencevars;
1764 }
1765 //where
1766 Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {
1767 // mapping that turns inference variables into undet vars
1768 public Type apply(Type t) {
1769 if (t.hasTag(TYPEVAR)) {
1770 TypeVar tv = (TypeVar)t;
1771 if (tv.isCaptured()) {
1772 return new CapturedUndetVar((CapturedType)tv, types);
1773 } else {
1774 return new UndetVar(tv, types);
1775 }
1776 } else {
1777 return t.map(this);
1778 }
1779 }
1780 };
1782 /**
1783 * add a new inference var to this inference context
1784 */
1785 void addVar(TypeVar t) {
1786 this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));
1787 this.inferencevars = this.inferencevars.prepend(t);
1788 }
1790 /**
1791 * returns the list of free variables (as type-variables) in this
1792 * inference context
1793 */
1794 List<Type> inferenceVars() {
1795 return inferencevars;
1796 }
1798 /**
1799 * returns the list of uninstantiated variables (as type-variables) in this
1800 * inference context
1801 */
1802 List<Type> restvars() {
1803 return filterVars(new Filter<UndetVar>() {
1804 public boolean accepts(UndetVar uv) {
1805 return uv.inst == null;
1806 }
1807 });
1808 }
1810 /**
1811 * returns the list of instantiated variables (as type-variables) in this
1812 * inference context
1813 */
1814 List<Type> instvars() {
1815 return filterVars(new Filter<UndetVar>() {
1816 public boolean accepts(UndetVar uv) {
1817 return uv.inst != null;
1818 }
1819 });
1820 }
1822 /**
1823 * Get list of bounded inference variables (where bound is other than
1824 * declared bounds).
1825 */
1826 final List<Type> boundedVars() {
1827 return filterVars(new Filter<UndetVar>() {
1828 public boolean accepts(UndetVar uv) {
1829 return uv.getBounds(InferenceBound.UPPER)
1830 .diff(uv.getDeclaredBounds())
1831 .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();
1832 }
1833 });
1834 }
1836 private List<Type> filterVars(Filter<UndetVar> fu) {
1837 ListBuffer<Type> res = new ListBuffer<>();
1838 for (Type t : undetvars) {
1839 UndetVar uv = (UndetVar)t;
1840 if (fu.accepts(uv)) {
1841 res.append(uv.qtype);
1842 }
1843 }
1844 return res.toList();
1845 }
1847 /**
1848 * is this type free?
1849 */
1850 final boolean free(Type t) {
1851 return t.containsAny(inferencevars);
1852 }
1854 final boolean free(List<Type> ts) {
1855 for (Type t : ts) {
1856 if (free(t)) return true;
1857 }
1858 return false;
1859 }
1861 /**
1862 * Returns a list of free variables in a given type
1863 */
1864 final List<Type> freeVarsIn(Type t) {
1865 ListBuffer<Type> buf = new ListBuffer<>();
1866 for (Type iv : inferenceVars()) {
1867 if (t.contains(iv)) {
1868 buf.add(iv);
1869 }
1870 }
1871 return buf.toList();
1872 }
1874 final List<Type> freeVarsIn(List<Type> ts) {
1875 ListBuffer<Type> buf = new ListBuffer<>();
1876 for (Type t : ts) {
1877 buf.appendList(freeVarsIn(t));
1878 }
1879 ListBuffer<Type> buf2 = new ListBuffer<>();
1880 for (Type t : buf) {
1881 if (!buf2.contains(t)) {
1882 buf2.add(t);
1883 }
1884 }
1885 return buf2.toList();
1886 }
1888 /**
1889 * Replace all free variables in a given type with corresponding
1890 * undet vars (used ahead of subtyping/compatibility checks to allow propagation
1891 * of inference constraints).
1892 */
1893 final Type asFree(Type t) {
1894 return types.subst(t, inferencevars, undetvars);
1895 }
1897 final List<Type> asFree(List<Type> ts) {
1898 ListBuffer<Type> buf = new ListBuffer<>();
1899 for (Type t : ts) {
1900 buf.append(asFree(t));
1901 }
1902 return buf.toList();
1903 }
1905 List<Type> instTypes() {
1906 ListBuffer<Type> buf = new ListBuffer<>();
1907 for (Type t : undetvars) {
1908 UndetVar uv = (UndetVar)t;
1909 buf.append(uv.inst != null ? uv.inst : uv.qtype);
1910 }
1911 return buf.toList();
1912 }
1914 /**
1915 * Replace all free variables in a given type with corresponding
1916 * instantiated types - if one or more free variable has not been
1917 * fully instantiated, it will still be available in the resulting type.
1918 */
1919 Type asInstType(Type t) {
1920 return types.subst(t, inferencevars, instTypes());
1921 }
1923 List<Type> asInstTypes(List<Type> ts) {
1924 ListBuffer<Type> buf = new ListBuffer<>();
1925 for (Type t : ts) {
1926 buf.append(asInstType(t));
1927 }
1928 return buf.toList();
1929 }
1931 /**
1932 * Add custom hook for performing post-inference action
1933 */
1934 void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
1935 freeTypeListeners.put(ftl, freeVarsIn(types));
1936 }
1938 /**
1939 * Mark the inference context as complete and trigger evaluation
1940 * of all deferred checks.
1941 */
1942 void notifyChange() {
1943 notifyChange(inferencevars.diff(restvars()));
1944 }
1946 void notifyChange(List<Type> inferredVars) {
1947 InferenceException thrownEx = null;
1948 for (Map.Entry<FreeTypeListener, List<Type>> entry :
1949 new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) {
1950 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
1951 try {
1952 entry.getKey().typesInferred(this);
1953 freeTypeListeners.remove(entry.getKey());
1954 } catch (InferenceException ex) {
1955 if (thrownEx == null) {
1956 thrownEx = ex;
1957 }
1958 }
1959 }
1960 }
1961 //inference exception multiplexing - present any inference exception
1962 //thrown when processing listeners as a single one
1963 if (thrownEx != null) {
1964 throw thrownEx;
1965 }
1966 }
1968 /**
1969 * Save the state of this inference context
1970 */
1971 List<Type> save() {
1972 ListBuffer<Type> buf = new ListBuffer<>();
1973 for (Type t : undetvars) {
1974 UndetVar uv = (UndetVar)t;
1975 UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);
1976 for (InferenceBound ib : InferenceBound.values()) {
1977 for (Type b : uv.getBounds(ib)) {
1978 uv2.addBound(ib, b, types);
1979 }
1980 }
1981 uv2.inst = uv.inst;
1982 buf.add(uv2);
1983 }
1984 return buf.toList();
1985 }
1987 /**
1988 * Restore the state of this inference context to the previous known checkpoint
1989 */
1990 void rollback(List<Type> saved_undet) {
1991 Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());
1992 //restore bounds (note: we need to preserve the old instances)
1993 for (Type t : undetvars) {
1994 UndetVar uv = (UndetVar)t;
1995 UndetVar uv_saved = (UndetVar)saved_undet.head;
1996 for (InferenceBound ib : InferenceBound.values()) {
1997 uv.setBounds(ib, uv_saved.getBounds(ib));
1998 }
1999 uv.inst = uv_saved.inst;
2000 saved_undet = saved_undet.tail;
2001 }
2002 }
2004 /**
2005 * Copy variable in this inference context to the given context
2006 */
2007 void dupTo(final InferenceContext that) {
2008 that.inferencevars = that.inferencevars.appendList(inferencevars);
2009 that.undetvars = that.undetvars.appendList(undetvars);
2010 //set up listeners to notify original inference contexts as
2011 //propagated vars are inferred in new context
2012 for (Type t : inferencevars) {
2013 that.freeTypeListeners.put(new FreeTypeListener() {
2014 public void typesInferred(InferenceContext inferenceContext) {
2015 InferenceContext.this.notifyChange();
2016 }
2017 }, List.of(t));
2018 }
2019 }
2021 private void solve(GraphStrategy ss, Warner warn) {
2022 solve(ss, new HashMap<Type, Set<Type>>(), warn);
2023 }
2025 /**
2026 * Solve with given graph strategy.
2027 */
2028 private void solve(GraphStrategy ss, Map<Type, Set<Type>> stuckDeps, Warner warn) {
2029 GraphSolver s = new GraphSolver(this, stuckDeps, warn);
2030 s.solve(ss);
2031 }
2033 /**
2034 * Solve all variables in this context.
2035 */
2036 public void solve(Warner warn) {
2037 solve(new LeafSolver() {
2038 public boolean done() {
2039 return restvars().isEmpty();
2040 }
2041 }, warn);
2042 }
2044 /**
2045 * Solve all variables in the given list.
2046 */
2047 public void solve(final List<Type> vars, Warner warn) {
2048 solve(new BestLeafSolver(vars) {
2049 public boolean done() {
2050 return !free(asInstTypes(vars));
2051 }
2052 }, warn);
2053 }
2055 /**
2056 * Solve at least one variable in given list.
2057 */
2058 public void solveAny(List<Type> varsToSolve, Map<Type, Set<Type>> optDeps, Warner warn) {
2059 solve(new BestLeafSolver(varsToSolve.intersect(restvars())) {
2060 public boolean done() {
2061 return instvars().intersect(varsToSolve).nonEmpty();
2062 }
2063 }, optDeps, warn);
2064 }
2066 /**
2067 * Apply a set of inference steps
2068 */
2069 private boolean solveBasic(EnumSet<InferenceStep> steps) {
2070 return solveBasic(inferencevars, steps);
2071 }
2073 private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {
2074 boolean changed = false;
2075 for (Type t : varsToSolve.intersect(restvars())) {
2076 UndetVar uv = (UndetVar)asFree(t);
2077 for (InferenceStep step : steps) {
2078 if (step.accepts(uv, this)) {
2079 uv.inst = step.solve(uv, this);
2080 changed = true;
2081 break;
2082 }
2083 }
2084 }
2085 return changed;
2086 }
2088 /**
2089 * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
2090 * During overload resolution, instantiation is done by doing a partial
2091 * inference process using eq/lower bound instantiation. During check,
2092 * we also instantiate any remaining vars by repeatedly using eq/upper
2093 * instantiation, until all variables are solved.
2094 */
2095 public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {
2096 while (true) {
2097 boolean stuck = !solveBasic(steps);
2098 if (restvars().isEmpty() || partial) {
2099 //all variables have been instantiated - exit
2100 break;
2101 } else if (stuck) {
2102 //some variables could not be instantiated because of cycles in
2103 //upper bounds - provide a (possibly recursive) default instantiation
2104 instantiateAsUninferredVars(restvars(), this);
2105 break;
2106 } else {
2107 //some variables have been instantiated - replace newly instantiated
2108 //variables in remaining upper bounds and continue
2109 for (Type t : undetvars) {
2110 UndetVar uv = (UndetVar)t;
2111 uv.substBounds(inferenceVars(), instTypes(), types);
2112 }
2113 }
2114 }
2115 checkWithinBounds(this, warn);
2116 }
2118 private Infer infer() {
2119 //back-door to infer
2120 return Infer.this;
2121 }
2122 }
2124 final InferenceContext emptyContext = new InferenceContext(List.<Type>nil());
2125 // </editor-fold>
2126 }
