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