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