Tue, 25 Sep 2012 11:55:34 +0100
7175433: Inference cleanup: add helper class to handle inference variables
Summary: Add class to handle inference variables instantiation and associated info
Reviewed-by: jjg, dlsmith
1 /*
2 * Copyright (c) 1999, 2012, 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.code.*;
29 import com.sun.tools.javac.code.Symbol.*;
30 import com.sun.tools.javac.code.Type.*;
31 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
32 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
33 import com.sun.tools.javac.tree.JCTree;
34 import com.sun.tools.javac.tree.JCTree.JCTypeCast;
35 import com.sun.tools.javac.tree.TreeInfo;
36 import com.sun.tools.javac.util.*;
37 import com.sun.tools.javac.util.List;
38 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
40 import java.util.HashMap;
41 import java.util.Map;
43 import static com.sun.tools.javac.code.TypeTags.*;
45 /** Helper class for type parameter inference, used by the attribution phase.
46 *
47 * <p><b>This is NOT part of any supported API.
48 * If you write code that depends on this, you do so at your own risk.
49 * This code and its internal interfaces are subject to change or
50 * deletion without notice.</b>
51 */
52 public class Infer {
53 protected static final Context.Key<Infer> inferKey =
54 new Context.Key<Infer>();
56 /** A value for prototypes that admit any type, including polymorphic ones. */
57 public static final Type anyPoly = new Type(NONE, null);
59 Symtab syms;
60 Types types;
61 Check chk;
62 Resolve rs;
63 Log log;
64 JCDiagnostic.Factory diags;
66 public static Infer instance(Context context) {
67 Infer instance = context.get(inferKey);
68 if (instance == null)
69 instance = new Infer(context);
70 return instance;
71 }
73 protected Infer(Context context) {
74 context.put(inferKey, this);
75 syms = Symtab.instance(context);
76 types = Types.instance(context);
77 rs = Resolve.instance(context);
78 log = Log.instance(context);
79 chk = Check.instance(context);
80 diags = JCDiagnostic.Factory.instance(context);
81 inferenceException = new InferenceException(diags);
82 }
84 /**
85 * This exception class is design to store a list of diagnostics corresponding
86 * to inference errors that can arise during a method applicability check.
87 */
88 public static class InferenceException extends InapplicableMethodException {
89 private static final long serialVersionUID = 0;
91 List<JCDiagnostic> messages = List.nil();
93 InferenceException(JCDiagnostic.Factory diags) {
94 super(diags);
95 }
97 @Override
98 InapplicableMethodException setMessage(JCDiagnostic diag) {
99 messages = messages.append(diag);
100 return this;
101 }
103 @Override
104 public JCDiagnostic getDiagnostic() {
105 return messages.head;
106 }
108 void clear() {
109 messages = List.nil();
110 }
111 }
113 private final InferenceException inferenceException;
115 /***************************************************************************
116 * Mini/Maximization of UndetVars
117 ***************************************************************************/
119 /** Instantiate undetermined type variable to its minimal upper bound.
120 * Throw a NoInstanceException if this not possible.
121 */
122 void maximizeInst(UndetVar that, Warner warn) throws InferenceException {
123 List<Type> hibounds = Type.filter(that.hibounds, boundFilter);
124 if (that.eq.isEmpty()) {
125 if (hibounds.isEmpty())
126 that.inst = syms.objectType;
127 else if (hibounds.tail.isEmpty())
128 that.inst = hibounds.head;
129 else
130 that.inst = types.glb(hibounds);
131 } else {
132 that.inst = that.eq.head;
133 }
134 if (that.inst == null ||
135 that.inst.isErroneous())
136 throw inferenceException
137 .setMessage("no.unique.maximal.instance.exists",
138 that.qtype, hibounds);
139 }
141 private Filter<Type> boundFilter = new Filter<Type>() {
142 @Override
143 public boolean accepts(Type t) {
144 return !t.isErroneous() && t.tag != BOT;
145 }
146 };
148 /** Instantiate undetermined type variable to the lub of all its lower bounds.
149 * Throw a NoInstanceException if this not possible.
150 */
151 void minimizeInst(UndetVar that, Warner warn) throws InferenceException {
152 List<Type> lobounds = Type.filter(that.lobounds, boundFilter);
153 if (that.eq.isEmpty()) {
154 if (lobounds.isEmpty()) {
155 //do nothing - the inference variable is under-constrained
156 return;
157 } else if (lobounds.tail.isEmpty())
158 that.inst = lobounds.head.isPrimitive() ? syms.errType : lobounds.head;
159 else {
160 that.inst = types.lub(lobounds);
161 }
162 if (that.inst == null || that.inst.tag == ERROR)
163 throw inferenceException
164 .setMessage("no.unique.minimal.instance.exists",
165 that.qtype, lobounds);
166 } else {
167 that.inst = that.eq.head;
168 }
169 }
171 /***************************************************************************
172 * Exported Methods
173 ***************************************************************************/
175 /**
176 * Instantiate uninferred inference variables (JLS 15.12.2.8). First
177 * if the method return type is non-void, we derive constraints from the
178 * expected type - then we use declared bound well-formedness to derive additional
179 * constraints. If no instantiation exists, or if several incomparable
180 * best instantiations exist throw a NoInstanceException.
181 */
182 public void instantiateUninferred(DiagnosticPosition pos,
183 InferenceContext inferenceContext,
184 MethodType mtype,
185 Attr.ResultInfo resultInfo,
186 Warner warn) throws InferenceException {
187 Type to = resultInfo.pt;
188 if (to.tag == NONE) {
189 to = mtype.getReturnType().tag <= VOID ?
190 mtype.getReturnType() : syms.objectType;
191 }
192 Type qtype1 = inferenceContext.asFree(mtype.getReturnType(), types);
193 if (!types.isSubtype(qtype1,
194 qtype1.tag == UNDETVAR ? types.boxedTypeOrType(to) : to)) {
195 throw inferenceException
196 .setMessage("infer.no.conforming.instance.exists",
197 inferenceContext.restvars(), mtype.getReturnType(), to);
198 }
200 while (true) {
201 boolean stuck = true;
202 for (Type t : inferenceContext.undetvars) {
203 UndetVar uv = (UndetVar)t;
204 if (uv.inst == null && (uv.eq.nonEmpty() || !inferenceContext.free(uv.hibounds))) {
205 maximizeInst((UndetVar)t, warn);
206 stuck = false;
207 }
208 }
209 if (inferenceContext.restvars().isEmpty()) {
210 //all variables have been instantiated - exit
211 break;
212 } else if (stuck) {
213 //some variables could not be instantiated because of cycles in
214 //upper bounds - provide a (possibly recursive) default instantiation
215 instantiateAsUninferredVars(inferenceContext);
216 break;
217 } else {
218 //some variables have been instantiated - replace newly instantiated
219 //variables in remaining upper bounds and continue
220 for (Type t : inferenceContext.undetvars) {
221 UndetVar uv = (UndetVar)t;
222 uv.hibounds = inferenceContext.asInstTypes(uv.hibounds, types);
223 }
224 }
225 }
226 }
228 /**
229 * Infer cyclic inference variables as described in 15.12.2.8.
230 */
231 private void instantiateAsUninferredVars(InferenceContext inferenceContext) {
232 ListBuffer<Type> todo = ListBuffer.lb();
233 //step 1 - create fresh tvars
234 for (Type t : inferenceContext.undetvars) {
235 UndetVar uv = (UndetVar)t;
236 if (uv.inst == null) {
237 TypeSymbol fresh_tvar = new TypeSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
238 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.hibounds), null);
239 todo.append(uv);
240 uv.inst = fresh_tvar.type;
241 }
242 }
243 //step 2 - replace fresh tvars in their bounds
244 List<Type> formals = inferenceContext.inferenceVars();
245 for (Type t : todo) {
246 UndetVar uv = (UndetVar)t;
247 TypeVar ct = (TypeVar)uv.inst;
248 ct.bound = types.glb(inferenceContext.asInstTypes(types.getBounds(ct), types));
249 if (ct.bound.isErroneous()) {
250 //report inference error if glb fails
251 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
252 }
253 formals = formals.tail;
254 }
255 }
257 /** Instantiate a generic method type by finding instantiations for all its
258 * inference variables so that it can be applied to a given argument type list.
259 */
260 public Type instantiateMethod(Env<AttrContext> env,
261 List<Type> tvars,
262 MethodType mt,
263 Attr.ResultInfo resultInfo,
264 Symbol msym,
265 List<Type> argtypes,
266 boolean allowBoxing,
267 boolean useVarargs,
268 Warner warn) throws InferenceException {
269 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
270 final InferenceContext inferenceContext = new InferenceContext(tvars, types);
271 inferenceException.clear();
273 try {
274 rs.checkRawArgumentsAcceptable(env, inferenceContext, argtypes, mt.getParameterTypes(),
275 allowBoxing, useVarargs, warn, new InferenceCheckHandler(inferenceContext));
277 // minimize as yet undetermined type variables
278 for (Type t : inferenceContext.undetvars) {
279 minimizeInst((UndetVar)t, warn);
280 }
282 checkWithinBounds(inferenceContext, warn);
284 mt = (MethodType)inferenceContext.asInstType(mt, types);
286 List<Type> restvars = inferenceContext.restvars();
288 if (!restvars.isEmpty()) {
289 if (resultInfo != null) {
290 instantiateUninferred(env.tree.pos(), inferenceContext, mt, resultInfo, warn);
291 checkWithinBounds(inferenceContext, warn);
292 mt = (MethodType)inferenceContext.asInstType(mt, types);
293 if (rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
294 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
295 }
296 }
297 }
299 // return instantiated version of method type
300 return mt;
301 } finally {
302 inferenceContext.notifyChange(types);
303 }
304 }
305 //where
307 /** inference check handler **/
308 class InferenceCheckHandler implements Resolve.MethodCheckHandler {
310 InferenceContext inferenceContext;
312 public InferenceCheckHandler(InferenceContext inferenceContext) {
313 this.inferenceContext = inferenceContext;
314 }
316 public InapplicableMethodException arityMismatch() {
317 return inferenceException.setMessage("infer.arg.length.mismatch", inferenceContext.inferenceVars());
318 }
319 public InapplicableMethodException argumentMismatch(boolean varargs, JCDiagnostic details) {
320 String key = varargs ?
321 "infer.varargs.argument.mismatch" :
322 "infer.no.conforming.assignment.exists";
323 return inferenceException.setMessage(key,
324 inferenceContext.inferenceVars(), details);
325 }
326 public InapplicableMethodException inaccessibleVarargs(Symbol location, Type expected) {
327 return inferenceException.setMessage("inaccessible.varargs.type",
328 expected, Kinds.kindName(location), location);
329 }
330 }
332 /** check that type parameters are within their bounds.
333 */
334 void checkWithinBounds(InferenceContext inferenceContext,
335 Warner warn)
336 throws InferenceException {
337 List<Type> tvars = inferenceContext.inferenceVars();
338 for (Type t : inferenceContext.undetvars) {
339 UndetVar uv = (UndetVar)t;
340 uv.hibounds = inferenceContext.asInstTypes(uv.hibounds, types);
341 uv.lobounds = inferenceContext.asInstTypes(uv.lobounds, types);
342 uv.eq = inferenceContext.asInstTypes(uv.eq, types);
343 checkCompatibleUpperBounds(uv, inferenceContext.inferenceVars());
344 if (!inferenceContext.restvars().contains(tvars.head)) {
345 Type inst = inferenceContext.asInstType(t, types);
346 for (Type u : uv.hibounds) {
347 if (!types.isSubtypeUnchecked(inst, inferenceContext.asFree(u, types), warn)) {
348 reportBoundError(uv, BoundErrorKind.UPPER);
349 }
350 }
351 for (Type l : uv.lobounds) {
352 if (!types.isSubtypeUnchecked(inferenceContext.asFree(l, types), inst, warn)) {
353 reportBoundError(uv, BoundErrorKind.LOWER);
354 }
355 }
356 for (Type e : uv.eq) {
357 if (!types.isSameType(inst, inferenceContext.asFree(e, types))) {
358 reportBoundError(uv, BoundErrorKind.EQ);
359 }
360 }
361 }
362 tvars = tvars.tail;
363 }
364 }
366 void checkCompatibleUpperBounds(UndetVar uv, List<Type> tvars) {
367 // VGJ: sort of inlined maximizeInst() below. Adding
368 // bounds can cause lobounds that are above hibounds.
369 ListBuffer<Type> hiboundsNoVars = ListBuffer.lb();
370 for (Type t : Type.filter(uv.hibounds, boundFilter)) {
371 if (!t.containsAny(tvars)) {
372 hiboundsNoVars.append(t);
373 }
374 }
375 List<Type> hibounds = hiboundsNoVars.toList();
376 Type hb = null;
377 if (hibounds.isEmpty())
378 hb = syms.objectType;
379 else if (hibounds.tail.isEmpty())
380 hb = hibounds.head;
381 else
382 hb = types.glb(hibounds);
383 if (hb == null || hb.isErroneous())
384 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
385 }
387 enum BoundErrorKind {
388 BAD_UPPER() {
389 @Override
390 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
391 return ex.setMessage("incompatible.upper.bounds", uv.qtype, uv.hibounds);
392 }
393 },
394 UPPER() {
395 @Override
396 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
397 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst, uv.hibounds);
398 }
399 },
400 LOWER() {
401 @Override
402 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
403 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst, uv.lobounds);
404 }
405 },
406 EQ() {
407 @Override
408 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
409 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst, uv.eq);
410 }
411 };
413 abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
414 }
415 //where
416 void reportBoundError(UndetVar uv, BoundErrorKind bk) {
417 throw bk.setMessage(inferenceException, uv);
418 }
420 /**
421 * Compute a synthetic method type corresponding to the requested polymorphic
422 * method signature. The target return type is computed from the immediately
423 * enclosing scope surrounding the polymorphic-signature call.
424 */
425 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
426 MethodSymbol spMethod, // sig. poly. method or null if none
427 List<Type> argtypes) {
428 final Type restype;
430 //The return type for a polymorphic signature call is computed from
431 //the enclosing tree E, as follows: if E is a cast, then use the
432 //target type of the cast expression as a return type; if E is an
433 //expression statement, the return type is 'void' - otherwise the
434 //return type is simply 'Object'. A correctness check ensures that
435 //env.next refers to the lexically enclosing environment in which
436 //the polymorphic signature call environment is nested.
438 switch (env.next.tree.getTag()) {
439 case TYPECAST:
440 JCTypeCast castTree = (JCTypeCast)env.next.tree;
441 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
442 castTree.clazz.type :
443 syms.objectType;
444 break;
445 case EXEC:
446 JCTree.JCExpressionStatement execTree =
447 (JCTree.JCExpressionStatement)env.next.tree;
448 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
449 syms.voidType :
450 syms.objectType;
451 break;
452 default:
453 restype = syms.objectType;
454 }
456 List<Type> paramtypes = Type.map(argtypes, implicitArgType);
457 List<Type> exType = spMethod != null ?
458 spMethod.getThrownTypes() :
459 List.of(syms.throwableType); // make it throw all exceptions
461 MethodType mtype = new MethodType(paramtypes,
462 restype,
463 exType,
464 syms.methodClass);
465 return mtype;
466 }
467 //where
468 Mapping implicitArgType = new Mapping ("implicitArgType") {
469 public Type apply(Type t) {
470 t = types.erasure(t);
471 if (t.tag == BOT)
472 // nulls type as the marker type Null (which has no instances)
473 // infer as java.lang.Void for now
474 t = types.boxedClass(syms.voidType).type;
475 return t;
476 }
477 };
479 /**
480 * Mapping that turns inference variables into undet vars
481 * (used by inference context)
482 */
483 static Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
484 public Type apply(Type t) {
485 if (t.tag == TYPEVAR) return new UndetVar(t);
486 else return t.map(this);
487 }
488 };
490 /**
491 * An inference context keeps track of the set of variables that are free
492 * in the current context. It provides utility methods for opening/closing
493 * types to their corresponding free/closed forms. It also provide hooks for
494 * attaching deferred post-inference action (see PendingCheck). Finally,
495 * it can be used as an entry point for performing upper/lower bound inference
496 * (see InferenceKind).
497 */
498 static class InferenceContext {
500 /**
501 * Single-method-interface for defining inference callbacks. Certain actions
502 * (i.e. subtyping checks) might need to be redone after all inference variables
503 * have been fixed.
504 */
505 interface FreeTypeListener {
506 void typesInferred(InferenceContext inferenceContext);
507 }
509 /** list of inference vars as undet vars */
510 List<Type> undetvars;
512 /** list of inference vars in this context */
513 List<Type> inferencevars;
515 java.util.Map<FreeTypeListener, List<Type>> freeTypeListeners =
516 new java.util.HashMap<FreeTypeListener, List<Type>>();
518 List<FreeTypeListener> freetypeListeners = List.nil();
520 public InferenceContext(List<Type> inferencevars, Types types) {
521 this.undetvars = Type.map(inferencevars, fromTypeVarFun);
522 this.inferencevars = inferencevars;
523 for (Type t : this.undetvars) {
524 UndetVar uv = (UndetVar)t;
525 uv.hibounds = types.getBounds((TypeVar)uv.qtype);
526 }
527 }
529 /**
530 * returns the list of free variables (as type-variables) in this
531 * inference context
532 */
533 List<Type> inferenceVars() {
534 return inferencevars;
535 }
537 /**
538 * returns the list of uninstantiated variables (as type-variables) in this
539 * inference context (usually called after instantiate())
540 */
541 List<Type> restvars() {
542 List<Type> undetvars = this.undetvars;
543 ListBuffer<Type> restvars = ListBuffer.lb();
544 for (Type t : instTypes()) {
545 UndetVar uv = (UndetVar)undetvars.head;
546 if (uv.qtype == t) {
547 restvars.append(t);
548 }
549 undetvars = undetvars.tail;
550 }
551 return restvars.toList();
552 }
554 /**
555 * is this type free?
556 */
557 final boolean free(Type t) {
558 return t.containsAny(inferencevars);
559 }
561 final boolean free(List<Type> ts) {
562 for (Type t : ts) {
563 if (free(t)) return true;
564 }
565 return false;
566 }
568 /**
569 * Returns a list of free variables in a given type
570 */
571 final List<Type> freeVarsIn(Type t) {
572 ListBuffer<Type> buf = ListBuffer.lb();
573 for (Type iv : inferenceVars()) {
574 if (t.contains(iv)) {
575 buf.add(iv);
576 }
577 }
578 return buf.toList();
579 }
581 final List<Type> freeVarsIn(List<Type> ts) {
582 ListBuffer<Type> buf = ListBuffer.lb();
583 for (Type t : ts) {
584 buf.appendList(freeVarsIn(t));
585 }
586 ListBuffer<Type> buf2 = ListBuffer.lb();
587 for (Type t : buf) {
588 if (!buf2.contains(t)) {
589 buf2.add(t);
590 }
591 }
592 return buf2.toList();
593 }
595 /**
596 * Replace all free variables in a given type with corresponding
597 * undet vars (used ahead of subtyping/compatibility checks to allow propagation
598 * of inference constraints).
599 */
600 final Type asFree(Type t, Types types) {
601 return types.subst(t, inferencevars, undetvars);
602 }
604 final List<Type> asFree(List<Type> ts, Types types) {
605 ListBuffer<Type> buf = ListBuffer.lb();
606 for (Type t : ts) {
607 buf.append(asFree(t, types));
608 }
609 return buf.toList();
610 }
612 List<Type> instTypes() {
613 ListBuffer<Type> buf = ListBuffer.lb();
614 for (Type t : undetvars) {
615 UndetVar uv = (UndetVar)t;
616 buf.append(uv.inst != null ? uv.inst : uv.qtype);
617 }
618 return buf.toList();
619 }
621 /**
622 * Replace all free variables in a given type with corresponding
623 * instantiated types - if one or more free variable has not been
624 * fully instantiated, it will still be available in the resulting type.
625 */
626 Type asInstType(Type t, Types types) {
627 return types.subst(t, inferencevars, instTypes());
628 }
630 List<Type> asInstTypes(List<Type> ts, Types types) {
631 ListBuffer<Type> buf = ListBuffer.lb();
632 for (Type t : ts) {
633 buf.append(asInstType(t, types));
634 }
635 return buf.toList();
636 }
638 /**
639 * Add custom hook for performing post-inference action
640 */
641 void addFreeTypeListener(List<Type> types, FreeTypeListener ftl) {
642 freeTypeListeners.put(ftl, freeVarsIn(types));
643 }
645 /**
646 * Mark the inference context as complete and trigger evaluation
647 * of all deferred checks.
648 */
649 void notifyChange(Types types) {
650 InferenceException thrownEx = null;
651 for (Map.Entry<FreeTypeListener, List<Type>> entry :
652 new HashMap<FreeTypeListener, List<Type>>(freeTypeListeners).entrySet()) {
653 if (!Type.containsAny(entry.getValue(), restvars())) {
654 try {
655 entry.getKey().typesInferred(this);
656 freeTypeListeners.remove(entry.getKey());
657 } catch (InferenceException ex) {
658 if (thrownEx == null) {
659 thrownEx = ex;
660 }
661 }
662 }
663 }
664 //inference exception multiplexing - present any inference exception
665 //thrown when processing listeners as a single one
666 if (thrownEx != null) {
667 throw thrownEx;
668 }
669 }
670 }
672 final InferenceContext emptyContext = new InferenceContext(List.<Type>nil(), types);
673 }