Wed, 17 Jul 2013 14:19:25 +0100
8019340: varargs-related warnings are meaningless on signature-polymorphic methods such as MethodHandle.invokeExact
Summary: Disable certain varargs warnings when compiling polymorphic signature calls
Reviewed-by: jjg
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;
44 import java.util.Comparator;
45 import java.util.HashMap;
46 import java.util.Map;
47 import java.util.Set;
48 import java.util.TreeSet;
50 import java.util.ArrayList;
51 import java.util.Collections;
52 import java.util.EnumSet;
53 import java.util.HashSet;
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(JCDiagnostic diag) {
118 messages = messages.append(diag);
119 return this;
120 }
122 @Override
123 public JCDiagnostic getDiagnostic() {
124 return messages.head;
125 }
127 void clear() {
128 messages = List.nil();
129 }
130 }
132 protected final InferenceException inferenceException;
134 // <editor-fold defaultstate="collapsed" desc="Inference routines">
135 /**
136 * Main inference entry point - instantiate a generic method type
137 * using given argument types and (possibly) an expected target-type.
138 */
139 public Type instantiateMethod(Env<AttrContext> env,
140 List<Type> tvars,
141 MethodType mt,
142 Attr.ResultInfo resultInfo,
143 Symbol msym,
144 List<Type> argtypes,
145 boolean allowBoxing,
146 boolean useVarargs,
147 Resolve.MethodResolutionContext resolveContext,
148 Warner warn) throws InferenceException {
149 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
150 final InferenceContext inferenceContext = new InferenceContext(tvars);
151 inferenceException.clear();
152 try {
153 DeferredAttr.DeferredAttrContext deferredAttrContext =
154 resolveContext.deferredAttrContext(msym, inferenceContext, resultInfo, warn);
156 resolveContext.methodCheck.argumentsAcceptable(env, deferredAttrContext,
157 argtypes, mt.getParameterTypes(), warn);
159 if (allowGraphInference &&
160 resultInfo != null &&
161 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
162 //inject return constraints earlier
163 checkWithinBounds(inferenceContext, warn); //propagation
164 Type newRestype = generateReturnConstraints(resultInfo, mt, inferenceContext);
165 mt = (MethodType)types.createMethodTypeWithReturn(mt, newRestype);
166 //propagate outwards if needed
167 if (resultInfo.checkContext.inferenceContext().free(resultInfo.pt)) {
168 //propagate inference context outwards and exit
169 inferenceContext.dupTo(resultInfo.checkContext.inferenceContext());
170 deferredAttrContext.complete();
171 return mt;
172 }
173 }
175 deferredAttrContext.complete();
177 // minimize as yet undetermined type variables
178 if (allowGraphInference) {
179 inferenceContext.solve(warn);
180 } else {
181 inferenceContext.solveLegacy(true, warn, LegacyInferenceSteps.EQ_LOWER.steps); //minimizeInst
182 }
184 mt = (MethodType)inferenceContext.asInstType(mt);
186 if (!allowGraphInference &&
187 inferenceContext.restvars().nonEmpty() &&
188 resultInfo != null &&
189 !warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED)) {
190 generateReturnConstraints(resultInfo, mt, inferenceContext);
191 inferenceContext.solveLegacy(false, warn, LegacyInferenceSteps.EQ_UPPER.steps); //maximizeInst
192 mt = (MethodType)inferenceContext.asInstType(mt);
193 }
195 if (resultInfo != null && rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
196 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
197 }
199 // return instantiated version of method type
200 return mt;
201 } finally {
202 if (resultInfo != null || !allowGraphInference) {
203 inferenceContext.notifyChange();
204 } else {
205 inferenceContext.notifyChange(inferenceContext.boundedVars());
206 }
207 }
208 }
210 /**
211 * Generate constraints from the generic method's return type. If the method
212 * call occurs in a context where a type T is expected, use the expected
213 * type to derive more constraints on the generic method inference variables.
214 */
215 Type generateReturnConstraints(Attr.ResultInfo resultInfo,
216 MethodType mt, InferenceContext inferenceContext) {
217 Type from = mt.getReturnType();
218 if (mt.getReturnType().containsAny(inferenceContext.inferencevars) &&
219 resultInfo.checkContext.inferenceContext() != emptyContext) {
220 from = types.capture(from);
221 //add synthetic captured ivars
222 for (Type t : from.getTypeArguments()) {
223 if (t.hasTag(TYPEVAR) && ((TypeVar)t).isCaptured()) {
224 inferenceContext.addVar((TypeVar)t);
225 }
226 }
227 }
228 Type qtype1 = inferenceContext.asFree(from);
229 Type to = returnConstraintTarget(qtype1, resultInfo.pt);
230 Assert.check(allowGraphInference || !resultInfo.checkContext.inferenceContext().free(to),
231 "legacy inference engine cannot handle constraints on both sides of a subtyping assertion");
232 //we need to skip capture?
233 Warner retWarn = new Warner();
234 if (!resultInfo.checkContext.compatible(qtype1, resultInfo.checkContext.inferenceContext().asFree(to), retWarn) ||
235 //unchecked conversion is not allowed in source 7 mode
236 (!allowGraphInference && retWarn.hasLint(Lint.LintCategory.UNCHECKED))) {
237 throw inferenceException
238 .setMessage("infer.no.conforming.instance.exists",
239 inferenceContext.restvars(), mt.getReturnType(), to);
240 }
241 return from;
242 }
244 Type returnConstraintTarget(Type from, Type to) {
245 if (from.hasTag(VOID)) {
246 return syms.voidType;
247 } else if (to.hasTag(NONE)) {
248 return from.isPrimitive() ? from : syms.objectType;
249 } else if (from.hasTag(UNDETVAR) && to.isPrimitive()) {
250 if (!allowGraphInference) {
251 //if legacy, just return boxed type
252 return types.boxedClass(to).type;
253 }
254 //if graph inference we need to skip conflicting boxed bounds...
255 UndetVar uv = (UndetVar)from;
256 for (Type t : uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)) {
257 Type boundAsPrimitive = types.unboxedType(t);
258 if (boundAsPrimitive == null) continue;
259 if (types.isConvertible(boundAsPrimitive, to)) {
260 //effectively skip return-type constraint generation (compatibility)
261 return syms.objectType;
262 }
263 }
264 return types.boxedClass(to).type;
265 } else {
266 return to;
267 }
268 }
270 /**
271 * Infer cyclic inference variables as described in 15.12.2.8.
272 */
273 private void instantiateAsUninferredVars(List<Type> vars, InferenceContext inferenceContext) {
274 ListBuffer<Type> todo = ListBuffer.lb();
275 //step 1 - create fresh tvars
276 for (Type t : vars) {
277 UndetVar uv = (UndetVar)inferenceContext.asFree(t);
278 List<Type> upperBounds = uv.getBounds(InferenceBound.UPPER);
279 if (Type.containsAny(upperBounds, vars)) {
280 TypeSymbol fresh_tvar = new TypeVariableSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
281 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.getBounds(InferenceBound.UPPER)), null);
282 todo.append(uv);
283 uv.inst = fresh_tvar.type;
284 } else if (upperBounds.nonEmpty()) {
285 uv.inst = types.glb(upperBounds);
286 } else {
287 uv.inst = syms.objectType;
288 }
289 }
290 //step 2 - replace fresh tvars in their bounds
291 List<Type> formals = vars;
292 for (Type t : todo) {
293 UndetVar uv = (UndetVar)t;
294 TypeVar ct = (TypeVar)uv.inst;
295 ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct)));
296 if (ct.bound.isErroneous()) {
297 //report inference error if glb fails
298 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
299 }
300 formals = formals.tail;
301 }
302 }
304 /**
305 * Compute a synthetic method type corresponding to the requested polymorphic
306 * method signature. The target return type is computed from the immediately
307 * enclosing scope surrounding the polymorphic-signature call.
308 */
309 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
310 MethodSymbol spMethod, // sig. poly. method or null if none
311 Resolve.MethodResolutionContext resolveContext,
312 List<Type> argtypes) {
313 final Type restype;
315 //The return type for a polymorphic signature call is computed from
316 //the enclosing tree E, as follows: if E is a cast, then use the
317 //target type of the cast expression as a return type; if E is an
318 //expression statement, the return type is 'void' - otherwise the
319 //return type is simply 'Object'. A correctness check ensures that
320 //env.next refers to the lexically enclosing environment in which
321 //the polymorphic signature call environment is nested.
323 switch (env.next.tree.getTag()) {
324 case TYPECAST:
325 JCTypeCast castTree = (JCTypeCast)env.next.tree;
326 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
327 castTree.clazz.type :
328 syms.objectType;
329 break;
330 case EXEC:
331 JCTree.JCExpressionStatement execTree =
332 (JCTree.JCExpressionStatement)env.next.tree;
333 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
334 syms.voidType :
335 syms.objectType;
336 break;
337 default:
338 restype = syms.objectType;
339 }
341 List<Type> paramtypes = Type.map(argtypes, new ImplicitArgType(spMethod, resolveContext.step));
342 List<Type> exType = spMethod != null ?
343 spMethod.getThrownTypes() :
344 List.of(syms.throwableType); // make it throw all exceptions
346 MethodType mtype = new MethodType(paramtypes,
347 restype,
348 exType,
349 syms.methodClass);
350 return mtype;
351 }
352 //where
353 class ImplicitArgType extends DeferredAttr.DeferredTypeMap {
355 public ImplicitArgType(Symbol msym, Resolve.MethodResolutionPhase phase) {
356 rs.deferredAttr.super(AttrMode.SPECULATIVE, msym, phase);
357 }
359 public Type apply(Type t) {
360 t = types.erasure(super.apply(t));
361 if (t.hasTag(BOT))
362 // nulls type as the marker type Null (which has no instances)
363 // infer as java.lang.Void for now
364 t = types.boxedClass(syms.voidType).type;
365 return t;
366 }
367 }
369 /**
370 * This method is used to infer a suitable target SAM in case the original
371 * SAM type contains one or more wildcards. An inference process is applied
372 * so that wildcard bounds, as well as explicit lambda/method ref parameters
373 * (where applicable) are used to constraint the solution.
374 */
375 public Type instantiateFunctionalInterface(DiagnosticPosition pos, Type funcInterface,
376 List<Type> paramTypes, Check.CheckContext checkContext) {
377 if (types.capture(funcInterface) == funcInterface) {
378 //if capture doesn't change the type then return the target unchanged
379 //(this means the target contains no wildcards!)
380 return funcInterface;
381 } else {
382 Type formalInterface = funcInterface.tsym.type;
383 InferenceContext funcInterfaceContext =
384 new InferenceContext(funcInterface.tsym.type.getTypeArguments());
386 Assert.check(paramTypes != null);
387 //get constraints from explicit params (this is done by
388 //checking that explicit param types are equal to the ones
389 //in the functional interface descriptors)
390 List<Type> descParameterTypes = types.findDescriptorType(formalInterface).getParameterTypes();
391 if (descParameterTypes.size() != paramTypes.size()) {
392 checkContext.report(pos, diags.fragment("incompatible.arg.types.in.lambda"));
393 return types.createErrorType(funcInterface);
394 }
395 for (Type p : descParameterTypes) {
396 if (!types.isSameType(funcInterfaceContext.asFree(p), paramTypes.head)) {
397 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
398 return types.createErrorType(funcInterface);
399 }
400 paramTypes = paramTypes.tail;
401 }
403 try {
404 funcInterfaceContext.solve(funcInterfaceContext.boundedVars(), types.noWarnings);
405 } catch (InferenceException ex) {
406 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
407 }
409 List<Type> actualTypeargs = funcInterface.getTypeArguments();
410 for (Type t : funcInterfaceContext.undetvars) {
411 UndetVar uv = (UndetVar)t;
412 if (uv.inst == null) {
413 uv.inst = actualTypeargs.head;
414 }
415 actualTypeargs = actualTypeargs.tail;
416 }
418 Type owntype = funcInterfaceContext.asInstType(formalInterface);
419 if (!chk.checkValidGenericType(owntype)) {
420 //if the inferred functional interface type is not well-formed,
421 //or if it's not a subtype of the original target, issue an error
422 checkContext.report(pos, diags.fragment("no.suitable.functional.intf.inst", funcInterface));
423 }
424 return owntype;
425 }
426 }
427 // </editor-fold>
429 // <editor-fold defaultstate="collapsed" desc="Bound checking">
430 /**
431 * Check bounds and perform incorporation
432 */
433 void checkWithinBounds(InferenceContext inferenceContext,
434 Warner warn) throws InferenceException {
435 MultiUndetVarListener mlistener = new MultiUndetVarListener(inferenceContext.undetvars);
436 List<Type> saved_undet = inferenceContext.save();
437 try {
438 while (true) {
439 mlistener.reset();
440 if (!allowGraphInference) {
441 //in legacy mode we lack of transitivity, so bound check
442 //cannot be run in parallel with other incoprporation rounds
443 for (Type t : inferenceContext.undetvars) {
444 UndetVar uv = (UndetVar)t;
445 IncorporationStep.CHECK_BOUNDS.apply(uv, inferenceContext, warn);
446 }
447 }
448 for (Type t : inferenceContext.undetvars) {
449 UndetVar uv = (UndetVar)t;
450 //bound incorporation
451 EnumSet<IncorporationStep> incorporationSteps = allowGraphInference ?
452 incorporationStepsGraph : incorporationStepsLegacy;
453 for (IncorporationStep is : incorporationSteps) {
454 if (is.accepts(uv, inferenceContext)) {
455 is.apply(uv, inferenceContext, warn);
456 }
457 }
458 }
459 if (!mlistener.changed || !allowGraphInference) break;
460 }
461 }
462 finally {
463 mlistener.detach();
464 if (mlistener.rounds == MAX_INCORPORATION_STEPS) {
465 inferenceContext.rollback(saved_undet);
466 }
467 }
468 }
469 //where
470 /**
471 * This listener keeps track of changes on a group of inference variable
472 * bounds. Note: the listener must be detached (calling corresponding
473 * method) to make sure that the underlying inference variable is
474 * left in a clean state.
475 */
476 class MultiUndetVarListener implements UndetVar.UndetVarListener {
478 int rounds;
479 boolean changed;
480 List<Type> undetvars;
482 public MultiUndetVarListener(List<Type> undetvars) {
483 this.undetvars = undetvars;
484 for (Type t : undetvars) {
485 UndetVar uv = (UndetVar)t;
486 uv.listener = this;
487 }
488 }
490 public void varChanged(UndetVar uv, Set<InferenceBound> ibs) {
491 //avoid non-termination
492 if (rounds < MAX_INCORPORATION_STEPS) {
493 changed = true;
494 }
495 }
497 void reset() {
498 rounds++;
499 changed = false;
500 }
502 void detach() {
503 for (Type t : undetvars) {
504 UndetVar uv = (UndetVar)t;
505 uv.listener = null;
506 }
507 }
508 };
510 /** max number of incorporation rounds */
511 static final int MAX_INCORPORATION_STEPS = 100;
513 /**
514 * This enumeration defines an entry point for doing inference variable
515 * bound incorporation - it can be used to inject custom incorporation
516 * logic into the basic bound checking routine
517 */
518 enum IncorporationStep {
519 /**
520 * Performs basic bound checking - i.e. is the instantiated type for a given
521 * inference variable compatible with its bounds?
522 */
523 CHECK_BOUNDS() {
524 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
525 Infer infer = inferenceContext.infer();
526 uv.substBounds(inferenceContext.inferenceVars(), inferenceContext.instTypes(), infer.types);
527 infer.checkCompatibleUpperBounds(uv, inferenceContext);
528 if (uv.inst != null) {
529 Type inst = uv.inst;
530 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
531 if (!infer.types.isSubtypeUnchecked(inst, inferenceContext.asFree(u), warn)) {
532 infer.reportBoundError(uv, BoundErrorKind.UPPER);
533 }
534 }
535 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
536 if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), inst, warn)) {
537 infer.reportBoundError(uv, BoundErrorKind.LOWER);
538 }
539 }
540 for (Type e : uv.getBounds(InferenceBound.EQ)) {
541 if (!infer.types.isSameType(inst, inferenceContext.asFree(e))) {
542 infer.reportBoundError(uv, BoundErrorKind.EQ);
543 }
544 }
545 }
546 }
547 @Override
548 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
549 //applies to all undetvars
550 return true;
551 }
552 },
553 /**
554 * Check consistency of equality constraints. This is a slightly more aggressive
555 * inference routine that is designed as to maximize compatibility with JDK 7.
556 * Note: this is not used in graph mode.
557 */
558 EQ_CHECK_LEGACY() {
559 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
560 Infer infer = inferenceContext.infer();
561 Type eq = null;
562 for (Type e : uv.getBounds(InferenceBound.EQ)) {
563 Assert.check(!inferenceContext.free(e));
564 if (eq != null && !infer.types.isSameType(e, eq)) {
565 infer.reportBoundError(uv, BoundErrorKind.EQ);
566 }
567 eq = e;
568 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
569 Assert.check(!inferenceContext.free(l));
570 if (!infer.types.isSubtypeUnchecked(l, e, warn)) {
571 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
572 }
573 }
574 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
575 if (inferenceContext.free(u)) continue;
576 if (!infer.types.isSubtypeUnchecked(e, u, warn)) {
577 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
578 }
579 }
580 }
581 }
582 },
583 /**
584 * Check consistency of equality constraints.
585 */
586 EQ_CHECK() {
587 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
588 Infer infer = inferenceContext.infer();
589 for (Type e : uv.getBounds(InferenceBound.EQ)) {
590 if (e.containsAny(inferenceContext.inferenceVars())) continue;
591 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
592 if (!infer.types.isSubtypeUnchecked(e, inferenceContext.asFree(u), warn)) {
593 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_UPPER);
594 }
595 }
596 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
597 if (!infer.types.isSubtypeUnchecked(inferenceContext.asFree(l), e, warn)) {
598 infer.reportBoundError(uv, BoundErrorKind.BAD_EQ_LOWER);
599 }
600 }
601 }
602 }
603 },
604 /**
605 * Given a bound set containing {@code alpha <: T} and {@code alpha :> S}
606 * perform {@code S <: T} (which could lead to new bounds).
607 */
608 CROSS_UPPER_LOWER() {
609 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
610 Infer infer = inferenceContext.infer();
611 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
612 for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
613 infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
614 }
615 }
616 }
617 },
618 /**
619 * Given a bound set containing {@code alpha <: T} and {@code alpha == S}
620 * perform {@code S <: T} (which could lead to new bounds).
621 */
622 CROSS_UPPER_EQ() {
623 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
624 Infer infer = inferenceContext.infer();
625 for (Type b1 : uv.getBounds(InferenceBound.UPPER)) {
626 for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
627 infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
628 }
629 }
630 }
631 },
632 /**
633 * Given a bound set containing {@code alpha :> S} and {@code alpha == T}
634 * perform {@code S <: T} (which could lead to new bounds).
635 */
636 CROSS_EQ_LOWER() {
637 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
638 Infer infer = inferenceContext.infer();
639 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
640 for (Type b2 : uv.getBounds(InferenceBound.LOWER)) {
641 infer.types.isSubtypeUnchecked(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
642 }
643 }
644 }
645 },
646 /**
647 * Given a bound set containing {@code alpha == S} and {@code alpha == T}
648 * perform {@code S == T} (which could lead to new bounds).
649 */
650 CROSS_EQ_EQ() {
651 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
652 Infer infer = inferenceContext.infer();
653 for (Type b1 : uv.getBounds(InferenceBound.EQ)) {
654 for (Type b2 : uv.getBounds(InferenceBound.EQ)) {
655 if (b1 != b2) {
656 infer.types.isSameType(inferenceContext.asFree(b2), inferenceContext.asFree(b1));
657 }
658 }
659 }
660 }
661 },
662 /**
663 * Given a bound set containing {@code alpha <: beta} propagate lower bounds
664 * from alpha to beta; also propagate upper bounds from beta to alpha.
665 */
666 PROP_UPPER() {
667 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
668 Infer infer = inferenceContext.infer();
669 for (Type b : uv.getBounds(InferenceBound.UPPER)) {
670 if (inferenceContext.inferenceVars().contains(b)) {
671 UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
672 if (uv2.isCaptured()) continue;
673 //alpha <: beta
674 //0. set beta :> alpha
675 uv2.addBound(InferenceBound.LOWER, uv, infer.types);
676 //1. copy alpha's lower to beta's
677 for (Type l : uv.getBounds(InferenceBound.LOWER)) {
678 uv2.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);
679 }
680 //2. copy beta's upper to alpha's
681 for (Type u : uv2.getBounds(InferenceBound.UPPER)) {
682 uv.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);
683 }
684 }
685 }
686 }
687 },
688 /**
689 * Given a bound set containing {@code alpha :> beta} propagate lower bounds
690 * from beta to alpha; also propagate upper bounds from alpha to beta.
691 */
692 PROP_LOWER() {
693 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
694 Infer infer = inferenceContext.infer();
695 for (Type b : uv.getBounds(InferenceBound.LOWER)) {
696 if (inferenceContext.inferenceVars().contains(b)) {
697 UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
698 if (uv2.isCaptured()) continue;
699 //alpha :> beta
700 //0. set beta <: alpha
701 uv2.addBound(InferenceBound.UPPER, uv, infer.types);
702 //1. copy alpha's upper to beta's
703 for (Type u : uv.getBounds(InferenceBound.UPPER)) {
704 uv2.addBound(InferenceBound.UPPER, inferenceContext.asInstType(u), infer.types);
705 }
706 //2. copy beta's lower to alpha's
707 for (Type l : uv2.getBounds(InferenceBound.LOWER)) {
708 uv.addBound(InferenceBound.LOWER, inferenceContext.asInstType(l), infer.types);
709 }
710 }
711 }
712 }
713 },
714 /**
715 * Given a bound set containing {@code alpha == beta} propagate lower/upper
716 * bounds from alpha to beta and back.
717 */
718 PROP_EQ() {
719 public void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn) {
720 Infer infer = inferenceContext.infer();
721 for (Type b : uv.getBounds(InferenceBound.EQ)) {
722 if (inferenceContext.inferenceVars().contains(b)) {
723 UndetVar uv2 = (UndetVar)inferenceContext.asFree(b);
724 if (uv2.isCaptured()) continue;
725 //alpha == beta
726 //0. set beta == alpha
727 uv2.addBound(InferenceBound.EQ, uv, infer.types);
728 //1. copy all alpha's bounds to beta's
729 for (InferenceBound ib : InferenceBound.values()) {
730 for (Type b2 : uv.getBounds(ib)) {
731 if (b2 != uv2) {
732 uv2.addBound(ib, inferenceContext.asInstType(b2), infer.types);
733 }
734 }
735 }
736 //2. copy all beta's bounds to alpha's
737 for (InferenceBound ib : InferenceBound.values()) {
738 for (Type b2 : uv2.getBounds(ib)) {
739 if (b2 != uv) {
740 uv.addBound(ib, inferenceContext.asInstType(b2), infer.types);
741 }
742 }
743 }
744 }
745 }
746 }
747 };
749 abstract void apply(UndetVar uv, InferenceContext inferenceContext, Warner warn);
751 boolean accepts(UndetVar uv, InferenceContext inferenceContext) {
752 return !uv.isCaptured();
753 }
754 }
756 /** incorporation steps to be executed when running in legacy mode */
757 EnumSet<IncorporationStep> incorporationStepsLegacy = EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY);
759 /** incorporation steps to be executed when running in graph mode */
760 EnumSet<IncorporationStep> incorporationStepsGraph =
761 EnumSet.complementOf(EnumSet.of(IncorporationStep.EQ_CHECK_LEGACY));
763 /**
764 * Make sure that the upper bounds we got so far lead to a solvable inference
765 * variable by making sure that a glb exists.
766 */
767 void checkCompatibleUpperBounds(UndetVar uv, InferenceContext inferenceContext) {
768 List<Type> hibounds =
769 Type.filter(uv.getBounds(InferenceBound.UPPER), new BoundFilter(inferenceContext));
770 Type hb = null;
771 if (hibounds.isEmpty())
772 hb = syms.objectType;
773 else if (hibounds.tail.isEmpty())
774 hb = hibounds.head;
775 else
776 hb = types.glb(hibounds);
777 if (hb == null || hb.isErroneous())
778 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
779 }
780 //where
781 protected static class BoundFilter implements Filter<Type> {
783 InferenceContext inferenceContext;
785 public BoundFilter(InferenceContext inferenceContext) {
786 this.inferenceContext = inferenceContext;
787 }
789 @Override
790 public boolean accepts(Type t) {
791 return !t.isErroneous() && !inferenceContext.free(t) &&
792 !t.hasTag(BOT);
793 }
794 };
796 /**
797 * This enumeration defines all possible bound-checking related errors.
798 */
799 enum BoundErrorKind {
800 /**
801 * The (uninstantiated) inference variable has incompatible upper bounds.
802 */
803 BAD_UPPER() {
804 @Override
805 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
806 return ex.setMessage("incompatible.upper.bounds", uv.qtype,
807 uv.getBounds(InferenceBound.UPPER));
808 }
809 },
810 /**
811 * An equality constraint is not compatible with an upper bound.
812 */
813 BAD_EQ_UPPER() {
814 @Override
815 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
816 return ex.setMessage("incompatible.eq.upper.bounds", uv.qtype,
817 uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.UPPER));
818 }
819 },
820 /**
821 * An equality constraint is not compatible with a lower bound.
822 */
823 BAD_EQ_LOWER() {
824 @Override
825 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
826 return ex.setMessage("incompatible.eq.lower.bounds", uv.qtype,
827 uv.getBounds(InferenceBound.EQ), uv.getBounds(InferenceBound.LOWER));
828 }
829 },
830 /**
831 * Instantiated inference variable is not compatible with an upper bound.
832 */
833 UPPER() {
834 @Override
835 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
836 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst,
837 uv.getBounds(InferenceBound.UPPER));
838 }
839 },
840 /**
841 * Instantiated inference variable is not compatible with a lower bound.
842 */
843 LOWER() {
844 @Override
845 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
846 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst,
847 uv.getBounds(InferenceBound.LOWER));
848 }
849 },
850 /**
851 * Instantiated inference variable is not compatible with an equality constraint.
852 */
853 EQ() {
854 @Override
855 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
856 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst,
857 uv.getBounds(InferenceBound.EQ));
858 }
859 };
861 abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
862 }
864 /**
865 * Report a bound-checking error of given kind
866 */
867 void reportBoundError(UndetVar uv, BoundErrorKind bk) {
868 throw bk.setMessage(inferenceException, uv);
869 }
870 // </editor-fold>
872 // <editor-fold defaultstate="collapsed" desc="Inference engine">
873 /**
874 * Graph inference strategy - act as an input to the inference solver; a strategy is
875 * composed of two ingredients: (i) find a node to solve in the inference graph,
876 * and (ii) tell th engine when we are done fixing inference variables
877 */
878 interface GraphStrategy {
879 /**
880 * Pick the next node (leaf) to solve in the graph
881 */
882 Node pickNode(InferenceGraph g);
883 /**
884 * Is this the last step?
885 */
886 boolean done();
887 }
889 /**
890 * Simple solver strategy class that locates all leaves inside a graph
891 * and picks the first leaf as the next node to solve
892 */
893 abstract class LeafSolver implements GraphStrategy {
894 public Node pickNode(InferenceGraph g) {
895 Assert.check(!g.nodes.isEmpty(), "No nodes to solve!");
896 return g.nodes.get(0);
897 }
898 }
900 /**
901 * This solver uses an heuristic to pick the best leaf - the heuristic
902 * tries to select the node that has maximal probability to contain one
903 * or more inference variables in a given list
904 */
905 abstract class BestLeafSolver extends LeafSolver {
907 List<Type> varsToSolve;
909 BestLeafSolver(List<Type> varsToSolve) {
910 this.varsToSolve = varsToSolve;
911 }
913 /**
914 * Computes the minimum path that goes from a given node to any of the nodes
915 * containing a variable in {@code varsToSolve}. For any given path, the cost
916 * is computed as the total number of type-variables that should be eagerly
917 * instantiated across that path.
918 */
919 int computeMinPath(InferenceGraph g, Node n) {
920 return computeMinPath(g, n, List.<Node>nil(), 0);
921 }
923 int computeMinPath(InferenceGraph g, Node n, List<Node> path, int cost) {
924 if (path.contains(n)) return Integer.MAX_VALUE;
925 List<Node> path2 = path.prepend(n);
926 int cost2 = cost + n.data.size();
927 if (!Collections.disjoint(n.data, varsToSolve)) {
928 return cost2;
929 } else {
930 int bestPath = Integer.MAX_VALUE;
931 for (Node n2 : g.nodes) {
932 if (n2.deps.contains(n)) {
933 int res = computeMinPath(g, n2, path2, cost2);
934 if (res < bestPath) {
935 bestPath = res;
936 }
937 }
938 }
939 return bestPath;
940 }
941 }
943 /**
944 * Pick the leaf that minimize cost
945 */
946 @Override
947 public Node pickNode(final InferenceGraph g) {
948 final Map<Node, Integer> leavesMap = new HashMap<Node, Integer>();
949 for (Node n : g.nodes) {
950 if (n.isLeaf(n)) {
951 leavesMap.put(n, computeMinPath(g, n));
952 }
953 }
954 Assert.check(!leavesMap.isEmpty(), "No nodes to solve!");
955 TreeSet<Node> orderedLeaves = new TreeSet<Node>(new Comparator<Node>() {
956 public int compare(Node n1, Node n2) {
957 return leavesMap.get(n1) - leavesMap.get(n2);
958 }
959 });
960 orderedLeaves.addAll(leavesMap.keySet());
961 return orderedLeaves.first();
962 }
963 }
965 /**
966 * The inference process can be thought of as a sequence of steps. Each step
967 * instantiates an inference variable using a subset of the inference variable
968 * bounds, if certain condition are met. Decisions such as the sequence in which
969 * steps are applied, or which steps are to be applied are left to the inference engine.
970 */
971 enum InferenceStep {
973 /**
974 * Instantiate an inference variables using one of its (ground) equality
975 * constraints
976 */
977 EQ(InferenceBound.EQ) {
978 @Override
979 Type solve(UndetVar uv, InferenceContext inferenceContext) {
980 return filterBounds(uv, inferenceContext).head;
981 }
982 },
983 /**
984 * Instantiate an inference variables using its (ground) lower bounds. Such
985 * bounds are merged together using lub().
986 */
987 LOWER(InferenceBound.LOWER) {
988 @Override
989 Type solve(UndetVar uv, InferenceContext inferenceContext) {
990 Infer infer = inferenceContext.infer();
991 List<Type> lobounds = filterBounds(uv, inferenceContext);
992 //note: lobounds should have at least one element
993 Type owntype = lobounds.tail.tail == null ? lobounds.head : infer.types.lub(lobounds);
994 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
995 throw infer.inferenceException
996 .setMessage("no.unique.minimal.instance.exists",
997 uv.qtype, lobounds);
998 } else {
999 return owntype;
1000 }
1001 }
1002 },
1003 /**
1004 * Infer uninstantiated/unbound inference variables occurring in 'throws'
1005 * clause as RuntimeException
1006 */
1007 THROWS(InferenceBound.UPPER) {
1008 @Override
1009 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1010 if ((t.qtype.tsym.flags() & Flags.THROWS) == 0) {
1011 //not a throws undet var
1012 return false;
1013 }
1014 if (t.getBounds(InferenceBound.EQ, InferenceBound.LOWER, InferenceBound.UPPER)
1015 .diff(t.getDeclaredBounds()).nonEmpty()) {
1016 //not an unbounded undet var
1017 return false;
1018 }
1019 Infer infer = inferenceContext.infer();
1020 for (Type db : t.getDeclaredBounds()) {
1021 if (t.isInterface()) continue;
1022 if (infer.types.asSuper(infer.syms.runtimeExceptionType, db.tsym) != null) {
1023 //declared bound is a supertype of RuntimeException
1024 return true;
1025 }
1026 }
1027 //declared bound is more specific then RuntimeException - give up
1028 return false;
1029 }
1031 @Override
1032 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1033 return inferenceContext.infer().syms.runtimeExceptionType;
1034 }
1035 },
1036 /**
1037 * Instantiate an inference variables using its (ground) upper bounds. Such
1038 * bounds are merged together using glb().
1039 */
1040 UPPER(InferenceBound.UPPER) {
1041 @Override
1042 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1043 Infer infer = inferenceContext.infer();
1044 List<Type> hibounds = filterBounds(uv, inferenceContext);
1045 //note: lobounds should have at least one element
1046 Type owntype = hibounds.tail.tail == null ? hibounds.head : infer.types.glb(hibounds);
1047 if (owntype.isPrimitive() || owntype.hasTag(ERROR)) {
1048 throw infer.inferenceException
1049 .setMessage("no.unique.maximal.instance.exists",
1050 uv.qtype, hibounds);
1051 } else {
1052 return owntype;
1053 }
1054 }
1055 },
1056 /**
1057 * Like the former; the only difference is that this step can only be applied
1058 * if all upper bounds are ground.
1059 */
1060 UPPER_LEGACY(InferenceBound.UPPER) {
1061 @Override
1062 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1063 return !inferenceContext.free(t.getBounds(ib)) && !t.isCaptured();
1064 }
1066 @Override
1067 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1068 return UPPER.solve(uv, inferenceContext);
1069 }
1070 },
1071 /**
1072 * Like the former; the only difference is that this step can only be applied
1073 * if all upper/lower bounds are ground.
1074 */
1075 CAPTURED(InferenceBound.UPPER) {
1076 @Override
1077 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1078 return !inferenceContext.free(t.getBounds(InferenceBound.UPPER, InferenceBound.LOWER));
1079 }
1081 @Override
1082 Type solve(UndetVar uv, InferenceContext inferenceContext) {
1083 Infer infer = inferenceContext.infer();
1084 Type upper = UPPER.filterBounds(uv, inferenceContext).nonEmpty() ?
1085 UPPER.solve(uv, inferenceContext) :
1086 infer.syms.objectType;
1087 Type lower = LOWER.filterBounds(uv, inferenceContext).nonEmpty() ?
1088 LOWER.solve(uv, inferenceContext) :
1089 infer.syms.botType;
1090 CapturedType prevCaptured = (CapturedType)uv.qtype;
1091 return new CapturedType(prevCaptured.tsym.name, prevCaptured.tsym.owner, upper, lower, prevCaptured.wildcard);
1092 }
1093 };
1095 final InferenceBound ib;
1097 InferenceStep(InferenceBound ib) {
1098 this.ib = ib;
1099 }
1101 /**
1102 * Find an instantiated type for a given inference variable within
1103 * a given inference context
1104 */
1105 abstract Type solve(UndetVar uv, InferenceContext inferenceContext);
1107 /**
1108 * Can the inference variable be instantiated using this step?
1109 */
1110 public boolean accepts(UndetVar t, InferenceContext inferenceContext) {
1111 return filterBounds(t, inferenceContext).nonEmpty() && !t.isCaptured();
1112 }
1114 /**
1115 * Return the subset of ground bounds in a given bound set (i.e. eq/lower/upper)
1116 */
1117 List<Type> filterBounds(UndetVar uv, InferenceContext inferenceContext) {
1118 return Type.filter(uv.getBounds(ib), new BoundFilter(inferenceContext));
1119 }
1120 }
1122 /**
1123 * This enumeration defines the sequence of steps to be applied when the
1124 * solver works in legacy mode. The steps in this enumeration reflect
1125 * the behavior of old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
1126 */
1127 enum LegacyInferenceSteps {
1129 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
1130 EQ_UPPER(EnumSet.of(InferenceStep.EQ, InferenceStep.UPPER_LEGACY));
1132 final EnumSet<InferenceStep> steps;
1134 LegacyInferenceSteps(EnumSet<InferenceStep> steps) {
1135 this.steps = steps;
1136 }
1137 }
1139 /**
1140 * This enumeration defines the sequence of steps to be applied when the
1141 * graph solver is used. This order is defined so as to maximize compatibility
1142 * w.r.t. old inference routine (see JLS SE 7 15.12.2.7/15.12.2.8).
1143 */
1144 enum GraphInferenceSteps {
1146 EQ(EnumSet.of(InferenceStep.EQ)),
1147 EQ_LOWER(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER)),
1148 EQ_LOWER_THROWS_UPPER_CAPTURED(EnumSet.of(InferenceStep.EQ, InferenceStep.LOWER, InferenceStep.UPPER, InferenceStep.THROWS, InferenceStep.CAPTURED));
1150 final EnumSet<InferenceStep> steps;
1152 GraphInferenceSteps(EnumSet<InferenceStep> steps) {
1153 this.steps = steps;
1154 }
1155 }
1157 /**
1158 * This is the graph inference solver - the solver organizes all inference variables in
1159 * a given inference context by bound dependencies - in the general case, such dependencies
1160 * would lead to a cyclic directed graph (hence the name); the dependency info is used to build
1161 * an acyclic graph, where all cyclic variables are bundled together. An inference
1162 * step corresponds to solving a node in the acyclic graph - this is done by
1163 * relying on a given strategy (see GraphStrategy).
1164 */
1165 class GraphSolver {
1167 InferenceContext inferenceContext;
1168 Warner warn;
1170 GraphSolver(InferenceContext inferenceContext, Warner warn) {
1171 this.inferenceContext = inferenceContext;
1172 this.warn = warn;
1173 }
1175 /**
1176 * Solve variables in a given inference context. The amount of variables
1177 * to be solved, and the way in which the underlying acyclic graph is explored
1178 * depends on the selected solver strategy.
1179 */
1180 void solve(GraphStrategy sstrategy) {
1181 checkWithinBounds(inferenceContext, warn); //initial propagation of bounds
1182 InferenceGraph inferenceGraph = new InferenceGraph();
1183 while (!sstrategy.done()) {
1184 InferenceGraph.Node nodeToSolve = sstrategy.pickNode(inferenceGraph);
1185 List<Type> varsToSolve = List.from(nodeToSolve.data);
1186 List<Type> saved_undet = inferenceContext.save();
1187 try {
1188 //repeat until all variables are solved
1189 outer: while (Type.containsAny(inferenceContext.restvars(), varsToSolve)) {
1190 //for each inference phase
1191 for (GraphInferenceSteps step : GraphInferenceSteps.values()) {
1192 if (inferenceContext.solveBasic(varsToSolve, step.steps)) {
1193 checkWithinBounds(inferenceContext, warn);
1194 continue outer;
1195 }
1196 }
1197 //no progress
1198 throw inferenceException.setMessage();
1199 }
1200 }
1201 catch (InferenceException ex) {
1202 //did we fail because of interdependent ivars?
1203 inferenceContext.rollback(saved_undet);
1204 instantiateAsUninferredVars(varsToSolve, inferenceContext);
1205 checkWithinBounds(inferenceContext, warn);
1206 }
1207 inferenceGraph.deleteNode(nodeToSolve);
1208 }
1209 }
1211 /**
1212 * The dependencies between the inference variables that need to be solved
1213 * form a (possibly cyclic) graph. This class reduces the original dependency graph
1214 * to an acyclic version, where cyclic nodes are folded into a single 'super node'.
1215 */
1216 class InferenceGraph {
1218 /**
1219 * This class represents a node in the graph. Each node corresponds
1220 * to an inference variable and has edges (dependencies) on other
1221 * nodes. The node defines an entry point that can be used to receive
1222 * updates on the structure of the graph this node belongs to (used to
1223 * keep dependencies in sync).
1224 */
1225 class Node extends GraphUtils.TarjanNode<ListBuffer<Type>> {
1227 Set<Node> deps;
1229 Node(Type ivar) {
1230 super(ListBuffer.of(ivar));
1231 this.deps = new HashSet<Node>();
1232 }
1234 @Override
1235 public Iterable<? extends Node> getDependencies() {
1236 return deps;
1237 }
1239 @Override
1240 public String printDependency(GraphUtils.Node<ListBuffer<Type>> to) {
1241 StringBuilder buf = new StringBuilder();
1242 String sep = "";
1243 for (Type from : data) {
1244 UndetVar uv = (UndetVar)inferenceContext.asFree(from);
1245 for (Type bound : uv.getBounds(InferenceBound.values())) {
1246 if (bound.containsAny(List.from(to.data))) {
1247 buf.append(sep);
1248 buf.append(bound);
1249 sep = ",";
1250 }
1251 }
1252 }
1253 return buf.toString();
1254 }
1256 boolean isLeaf(Node n) {
1257 //no deps, or only one self dep
1258 return (n.deps.isEmpty() ||
1259 n.deps.size() == 1 && n.deps.contains(n));
1260 }
1262 void mergeWith(List<? extends Node> nodes) {
1263 for (Node n : nodes) {
1264 Assert.check(n.data.length() == 1, "Attempt to merge a compound node!");
1265 data.appendList(n.data);
1266 deps.addAll(n.deps);
1267 }
1268 //update deps
1269 Set<Node> deps2 = new HashSet<Node>();
1270 for (Node d : deps) {
1271 if (data.contains(d.data.first())) {
1272 deps2.add(this);
1273 } else {
1274 deps2.add(d);
1275 }
1276 }
1277 deps = deps2;
1278 }
1280 void graphChanged(Node from, Node to) {
1281 if (deps.contains(from)) {
1282 deps.remove(from);
1283 if (to != null) {
1284 deps.add(to);
1285 }
1286 }
1287 }
1288 }
1290 /** the nodes in the inference graph */
1291 ArrayList<Node> nodes;
1293 InferenceGraph() {
1294 initNodes();
1295 }
1297 /**
1298 * Delete a node from the graph. This update the underlying structure
1299 * of the graph (including dependencies) via listeners updates.
1300 */
1301 public void deleteNode(Node n) {
1302 Assert.check(nodes.contains(n));
1303 nodes.remove(n);
1304 notifyUpdate(n, null);
1305 }
1307 /**
1308 * Notify all nodes of a change in the graph. If the target node is
1309 * {@code null} the source node is assumed to be removed.
1310 */
1311 void notifyUpdate(Node from, Node to) {
1312 for (Node n : nodes) {
1313 n.graphChanged(from, to);
1314 }
1315 }
1317 /**
1318 * Create the graph nodes. First a simple node is created for every inference
1319 * variables to be solved. Then Tarjan is used to found all connected components
1320 * in the graph. For each component containing more than one node, a super node is
1321 * created, effectively replacing the original cyclic nodes.
1322 */
1323 void initNodes() {
1324 nodes = new ArrayList<Node>();
1325 for (Type t : inferenceContext.restvars()) {
1326 nodes.add(new Node(t));
1327 }
1328 for (Node n_i : nodes) {
1329 Type i = n_i.data.first();
1330 for (Node n_j : nodes) {
1331 Type j = n_j.data.first();
1332 UndetVar uv_i = (UndetVar)inferenceContext.asFree(i);
1333 if (Type.containsAny(uv_i.getBounds(InferenceBound.values()), List.of(j))) {
1334 //update i's deps
1335 n_i.deps.add(n_j);
1336 }
1337 }
1338 }
1339 ArrayList<Node> acyclicNodes = new ArrayList<Node>();
1340 for (List<? extends Node> conSubGraph : GraphUtils.tarjan(nodes)) {
1341 if (conSubGraph.length() > 1) {
1342 Node root = conSubGraph.head;
1343 root.mergeWith(conSubGraph.tail);
1344 for (Node n : conSubGraph) {
1345 notifyUpdate(n, root);
1346 }
1347 }
1348 acyclicNodes.add(conSubGraph.head);
1349 }
1350 nodes = acyclicNodes;
1351 }
1353 /**
1354 * Debugging: dot representation of this graph
1355 */
1356 String toDot() {
1357 StringBuilder buf = new StringBuilder();
1358 for (Type t : inferenceContext.undetvars) {
1359 UndetVar uv = (UndetVar)t;
1360 buf.append(String.format("var %s - upper bounds = %s, lower bounds = %s, eq bounds = %s\\n",
1361 uv.qtype, uv.getBounds(InferenceBound.UPPER), uv.getBounds(InferenceBound.LOWER),
1362 uv.getBounds(InferenceBound.EQ)));
1363 }
1364 return GraphUtils.toDot(nodes, "inferenceGraph" + hashCode(), buf.toString());
1365 }
1366 }
1367 }
1368 // </editor-fold>
1370 // <editor-fold defaultstate="collapsed" desc="Inference context">
1371 /**
1372 * Functional interface for defining inference callbacks. Certain actions
1373 * (i.e. subtyping checks) might need to be redone after all inference variables
1374 * have been fixed.
1375 */
1376 interface FreeTypeListener {
1377 void typesInferred(InferenceContext inferenceContext);
1378 }
1380 /**
1381 * An inference context keeps track of the set of variables that are free
1382 * in the current context. It provides utility methods for opening/closing
1383 * types to their corresponding free/closed forms. It also provide hooks for
1384 * attaching deferred post-inference action (see PendingCheck). Finally,
1385 * it can be used as an entry point for performing upper/lower bound inference
1386 * (see InferenceKind).
1387 */
1388 class InferenceContext {
1390 /** list of inference vars as undet vars */
1391 List<Type> undetvars;
1393 /** list of inference vars in this context */
1394 List<Type> inferencevars;
1396 java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners =
1397 new java.util.HashMap<FreeTypeListener, List<Type>>();
1399 List<FreeTypeListener> freetypeListeners = List.nil();
1401 public InferenceContext(List<Type> inferencevars) {
1402 this.undetvars = Type.map(inferencevars, fromTypeVarFun);
1403 this.inferencevars = inferencevars;
1404 }
1405 //where
1406 Mapping fromTypeVarFun = new Mapping("fromTypeVarFunWithBounds") {
1407 // mapping that turns inference variables into undet vars
1408 public Type apply(Type t) {
1409 if (t.hasTag(TYPEVAR)) {
1410 TypeVar tv = (TypeVar)t;
1411 return tv.isCaptured() ?
1412 new CapturedUndetVar((CapturedType)tv, types) :
1413 new UndetVar(tv, types);
1414 } else {
1415 return t.map(this);
1416 }
1417 }
1418 };
1420 /**
1421 * add a new inference var to this inference context
1422 */
1423 void addVar(TypeVar t) {
1424 this.undetvars = this.undetvars.prepend(fromTypeVarFun.apply(t));
1425 this.inferencevars = this.inferencevars.prepend(t);
1426 }
1428 /**
1429 * returns the list of free variables (as type-variables) in this
1430 * inference context
1431 */
1432 List<Type> inferenceVars() {
1433 return inferencevars;
1434 }
1436 /**
1437 * returns the list of uninstantiated variables (as type-variables) in this
1438 * inference context
1439 */
1440 List<Type> restvars() {
1441 return filterVars(new Filter<UndetVar>() {
1442 public boolean accepts(UndetVar uv) {
1443 return uv.inst == null;
1444 }
1445 });
1446 }
1448 /**
1449 * returns the list of instantiated variables (as type-variables) in this
1450 * inference context
1451 */
1452 List<Type> instvars() {
1453 return filterVars(new Filter<UndetVar>() {
1454 public boolean accepts(UndetVar uv) {
1455 return uv.inst != null;
1456 }
1457 });
1458 }
1460 /**
1461 * Get list of bounded inference variables (where bound is other than
1462 * declared bounds).
1463 */
1464 final List<Type> boundedVars() {
1465 return filterVars(new Filter<UndetVar>() {
1466 public boolean accepts(UndetVar uv) {
1467 return uv.getBounds(InferenceBound.UPPER)
1468 .diff(uv.getDeclaredBounds())
1469 .appendList(uv.getBounds(InferenceBound.EQ, InferenceBound.LOWER)).nonEmpty();
1470 }
1471 });
1472 }
1474 private List<Type> filterVars(Filter<UndetVar> fu) {
1475 ListBuffer<Type> res = ListBuffer.lb();
1476 for (Type t : undetvars) {
1477 UndetVar uv = (UndetVar)t;
1478 if (fu.accepts(uv)) {
1479 res.append(uv.qtype);
1480 }
1481 }
1482 return res.toList();
1483 }
1485 /**
1486 * is this type free?
1487 */
1488 final boolean free(Type t) {
1489 return t.containsAny(inferencevars);
1490 }
1492 final boolean free(List<Type> ts) {
1493 for (Type t : ts) {
1494 if (free(t)) return true;
1495 }
1496 return false;
1497 }
1499 /**
1500 * Returns a list of free variables in a given type
1501 */
1502 final List<Type> freeVarsIn(Type t) {
1503 ListBuffer<Type> buf = ListBuffer.lb();
1504 for (Type iv : inferenceVars()) {
1505 if (t.contains(iv)) {
1506 buf.add(iv);
1507 }
1508 }
1509 return buf.toList();
1510 }
1512 final List<Type> freeVarsIn(List<Type> ts) {
1513 ListBuffer<Type> buf = ListBuffer.lb();
1514 for (Type t : ts) {
1515 buf.appendList(freeVarsIn(t));
1516 }
1517 ListBuffer<Type> buf2 = ListBuffer.lb();
1518 for (Type t : buf) {
1519 if (!buf2.contains(t)) {
1520 buf2.add(t);
1521 }
1522 }
1523 return buf2.toList();
1524 }
1526 /**
1527 * Replace all free variables in a given type with corresponding
1528 * undet vars (used ahead of subtyping/compatibility checks to allow propagation
1529 * of inference constraints).
1530 */
1531 final Type asFree(Type t) {
1532 return types.subst(t, inferencevars, undetvars);
1533 }
1535 final List<Type> asFree(List<Type> ts) {
1536 ListBuffer<Type> buf = ListBuffer.lb();
1537 for (Type t : ts) {
1538 buf.append(asFree(t));
1539 }
1540 return buf.toList();
1541 }
1543 List<Type> instTypes() {
1544 ListBuffer<Type> buf = ListBuffer.lb();
1545 for (Type t : undetvars) {
1546 UndetVar uv = (UndetVar)t;
1547 buf.append(uv.inst != null ? uv.inst : uv.qtype);
1548 }
1549 return buf.toList();
1550 }
1552 /**
1553 * Replace all free variables in a given type with corresponding
1554 * instantiated types - if one or more free variable has not been
1555 * fully instantiated, it will still be available in the resulting type.
1556 */
1557 Type asInstType(Type t) {
1558 return types.subst(t, inferencevars, instTypes());
1559 }
1561 List<Type> asInstTypes(List<Type> ts) {
1562 ListBuffer<Type> buf = ListBuffer.lb();
1563 for (Type t : ts) {
1564 buf.append(asInstType(t));
1565 }
1566 return buf.toList();
1567 }
1569 /**
1570 * Add custom hook for performing post-inference action
1571 */
1572 void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
1573 freeTypeListeners.put(ftl, freeVarsIn(types));
1574 }
1576 /**
1577 * Mark the inference context as complete and trigger evaluation
1578 * of all deferred checks.
1579 */
1580 void notifyChange() {
1581 notifyChange(inferencevars.diff(restvars()));
1582 }
1584 void notifyChange(List<Type> inferredVars) {
1585 InferenceException thrownEx = null;
1586 for (Map.Entry<FreeTypeListener, List<Type>> entry :
1587 new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) {
1588 if (!Type.containsAny(entry.getValue(), inferencevars.diff(inferredVars))) {
1589 try {
1590 entry.getKey().typesInferred(this);
1591 freeTypeListeners.remove(entry.getKey());
1592 } catch (InferenceException ex) {
1593 if (thrownEx == null) {
1594 thrownEx = ex;
1595 }
1596 }
1597 }
1598 }
1599 //inference exception multiplexing - present any inference exception
1600 //thrown when processing listeners as a single one
1601 if (thrownEx != null) {
1602 throw thrownEx;
1603 }
1604 }
1606 /**
1607 * Save the state of this inference context
1608 */
1609 List<Type> save() {
1610 ListBuffer<Type> buf = ListBuffer.lb();
1611 for (Type t : undetvars) {
1612 UndetVar uv = (UndetVar)t;
1613 UndetVar uv2 = new UndetVar((TypeVar)uv.qtype, types);
1614 for (InferenceBound ib : InferenceBound.values()) {
1615 for (Type b : uv.getBounds(ib)) {
1616 uv2.addBound(ib, b, types);
1617 }
1618 }
1619 uv2.inst = uv.inst;
1620 buf.add(uv2);
1621 }
1622 return buf.toList();
1623 }
1625 /**
1626 * Restore the state of this inference context to the previous known checkpoint
1627 */
1628 void rollback(List<Type> saved_undet) {
1629 Assert.check(saved_undet != null && saved_undet.length() == undetvars.length());
1630 //restore bounds (note: we need to preserve the old instances)
1631 for (Type t : undetvars) {
1632 UndetVar uv = (UndetVar)t;
1633 UndetVar uv_saved = (UndetVar)saved_undet.head;
1634 for (InferenceBound ib : InferenceBound.values()) {
1635 uv.setBounds(ib, uv_saved.getBounds(ib));
1636 }
1637 uv.inst = uv_saved.inst;
1638 saved_undet = saved_undet.tail;
1639 }
1640 }
1642 /**
1643 * Copy variable in this inference context to the given context
1644 */
1645 void dupTo(final InferenceContext that) {
1646 that.inferencevars = that.inferencevars.appendList(inferencevars);
1647 that.undetvars = that.undetvars.appendList(undetvars);
1648 //set up listeners to notify original inference contexts as
1649 //propagated vars are inferred in new context
1650 for (Type t : inferencevars) {
1651 that.freeTypeListeners.put(new FreeTypeListener() {
1652 public void typesInferred(InferenceContext inferenceContext) {
1653 InferenceContext.this.notifyChange();
1654 }
1655 }, List.of(t));
1656 }
1657 }
1659 /**
1660 * Solve with given graph strategy.
1661 */
1662 private void solve(GraphStrategy ss, Warner warn) {
1663 GraphSolver s = new GraphSolver(this, warn);
1664 s.solve(ss);
1665 }
1667 /**
1668 * Solve all variables in this context.
1669 */
1670 public void solve(Warner warn) {
1671 solve(new LeafSolver() {
1672 public boolean done() {
1673 return restvars().isEmpty();
1674 }
1675 }, warn);
1676 }
1678 /**
1679 * Solve all variables in the given list.
1680 */
1681 public void solve(final List<Type> vars, Warner warn) {
1682 solve(new BestLeafSolver(vars) {
1683 public boolean done() {
1684 return !free(asInstTypes(vars));
1685 }
1686 }, warn);
1687 }
1689 /**
1690 * Solve at least one variable in given list.
1691 */
1692 public void solveAny(List<Type> varsToSolve, Warner warn) {
1693 checkWithinBounds(this, warn); //propagate bounds
1694 List<Type> boundedVars = boundedVars().intersect(restvars()).intersect(varsToSolve);
1695 if (boundedVars.isEmpty()) {
1696 throw inferenceException.setMessage("cyclic.inference",
1697 freeVarsIn(varsToSolve));
1698 }
1699 solve(new BestLeafSolver(boundedVars) {
1700 public boolean done() {
1701 return instvars().intersect(varsToSolve).nonEmpty();
1702 }
1703 }, warn);
1704 }
1706 /**
1707 * Apply a set of inference steps
1708 */
1709 private boolean solveBasic(EnumSet<InferenceStep> steps) {
1710 return solveBasic(inferencevars, steps);
1711 }
1713 private boolean solveBasic(List<Type> varsToSolve, EnumSet<InferenceStep> steps) {
1714 boolean changed = false;
1715 for (Type t : varsToSolve.intersect(restvars())) {
1716 UndetVar uv = (UndetVar)asFree(t);
1717 for (InferenceStep step : steps) {
1718 if (step.accepts(uv, this)) {
1719 uv.inst = step.solve(uv, this);
1720 changed = true;
1721 break;
1722 }
1723 }
1724 }
1725 return changed;
1726 }
1728 /**
1729 * Instantiate inference variables in legacy mode (JLS 15.12.2.7, 15.12.2.8).
1730 * During overload resolution, instantiation is done by doing a partial
1731 * inference process using eq/lower bound instantiation. During check,
1732 * we also instantiate any remaining vars by repeatedly using eq/upper
1733 * instantiation, until all variables are solved.
1734 */
1735 public void solveLegacy(boolean partial, Warner warn, EnumSet<InferenceStep> steps) {
1736 while (true) {
1737 boolean stuck = !solveBasic(steps);
1738 if (restvars().isEmpty() || partial) {
1739 //all variables have been instantiated - exit
1740 break;
1741 } else if (stuck) {
1742 //some variables could not be instantiated because of cycles in
1743 //upper bounds - provide a (possibly recursive) default instantiation
1744 instantiateAsUninferredVars(restvars(), this);
1745 break;
1746 } else {
1747 //some variables have been instantiated - replace newly instantiated
1748 //variables in remaining upper bounds and continue
1749 for (Type t : undetvars) {
1750 UndetVar uv = (UndetVar)t;
1751 uv.substBounds(inferenceVars(), instTypes(), types);
1752 }
1753 }
1754 }
1755 checkWithinBounds(this, warn);
1756 }
1758 private Infer infer() {
1759 //back-door to infer
1760 return Infer.this;
1761 }
1762 }
1764 final InferenceContext emptyContext = new InferenceContext(List.<Type>nil());
1765 // </editor-fold>
1766 }