Thu, 31 May 2012 17:42:14 +0100
7166552: Inference: cleanup usage of Type.ForAll
Summary: Remove hack to callback into type-inference from assignment context
Reviewed-by: dlsmith, jjg
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.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.List;
33 import com.sun.tools.javac.code.*;
34 import com.sun.tools.javac.code.Type.*;
35 import com.sun.tools.javac.code.Symbol.*;
36 import com.sun.tools.javac.comp.Resolve.InapplicableMethodException;
37 import com.sun.tools.javac.comp.Resolve.VerboseResolutionMode;
38 import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;
40 import static com.sun.tools.javac.code.TypeTags.*;
42 /** Helper class for type parameter inference, used by the attribution phase.
43 *
44 * <p><b>This is NOT part of any supported API.
45 * If you write code that depends on this, you do so at your own risk.
46 * This code and its internal interfaces are subject to change or
47 * deletion without notice.</b>
48 */
49 public class Infer {
50 protected static final Context.Key<Infer> inferKey =
51 new Context.Key<Infer>();
53 /** A value for prototypes that admit any type, including polymorphic ones. */
54 public static final Type anyPoly = new Type(NONE, null);
56 Symtab syms;
57 Types types;
58 Check chk;
59 Resolve rs;
60 Log log;
61 JCDiagnostic.Factory diags;
63 public static Infer instance(Context context) {
64 Infer instance = context.get(inferKey);
65 if (instance == null)
66 instance = new Infer(context);
67 return instance;
68 }
70 protected Infer(Context context) {
71 context.put(inferKey, this);
72 syms = Symtab.instance(context);
73 types = Types.instance(context);
74 rs = Resolve.instance(context);
75 log = Log.instance(context);
76 chk = Check.instance(context);
77 diags = JCDiagnostic.Factory.instance(context);
78 ambiguousNoInstanceException =
79 new NoInstanceException(true, diags);
80 unambiguousNoInstanceException =
81 new NoInstanceException(false, diags);
82 invalidInstanceException =
83 new InvalidInstanceException(diags);
85 }
87 public static class InferenceException extends InapplicableMethodException {
88 private static final long serialVersionUID = 0;
90 InferenceException(JCDiagnostic.Factory diags) {
91 super(diags);
92 }
93 }
95 public static class NoInstanceException extends InferenceException {
96 private static final long serialVersionUID = 1;
98 boolean isAmbiguous; // exist several incomparable best instances?
100 NoInstanceException(boolean isAmbiguous, JCDiagnostic.Factory diags) {
101 super(diags);
102 this.isAmbiguous = isAmbiguous;
103 }
104 }
106 public static class InvalidInstanceException extends InferenceException {
107 private static final long serialVersionUID = 2;
109 InvalidInstanceException(JCDiagnostic.Factory diags) {
110 super(diags);
111 }
112 }
114 private final NoInstanceException ambiguousNoInstanceException;
115 private final NoInstanceException unambiguousNoInstanceException;
116 private final InvalidInstanceException invalidInstanceException;
118 /***************************************************************************
119 * Auxiliary type values and classes
120 ***************************************************************************/
122 /** A mapping that turns type variables into undetermined type variables.
123 */
124 List<Type> makeUndetvars(List<Type> tvars) {
125 List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
126 for (Type t : undetvars) {
127 UndetVar uv = (UndetVar)t;
128 uv.hibounds = types.getBounds((TypeVar)uv.qtype);
129 }
130 return undetvars;
131 }
132 //where
133 Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
134 public Type apply(Type t) {
135 if (t.tag == TYPEVAR) return new UndetVar(t);
136 else return t.map(this);
137 }
138 };
140 /***************************************************************************
141 * Mini/Maximization of UndetVars
142 ***************************************************************************/
144 /** Instantiate undetermined type variable to its minimal upper bound.
145 * Throw a NoInstanceException if this not possible.
146 */
147 void maximizeInst(UndetVar that, Warner warn) throws NoInstanceException {
148 List<Type> hibounds = Type.filter(that.hibounds, errorFilter);
149 if (that.eq.isEmpty()) {
150 if (hibounds.isEmpty())
151 that.inst = syms.objectType;
152 else if (hibounds.tail.isEmpty())
153 that.inst = hibounds.head;
154 else
155 that.inst = types.glb(hibounds);
156 } else {
157 that.inst = that.eq.head;
158 }
159 if (that.inst == null ||
160 that.inst.isErroneous())
161 throw ambiguousNoInstanceException
162 .setMessage("no.unique.maximal.instance.exists",
163 that.qtype, hibounds);
164 }
166 private Filter<Type> errorFilter = new Filter<Type>() {
167 @Override
168 public boolean accepts(Type t) {
169 return !t.isErroneous();
170 }
171 };
173 /** Instantiate undetermined type variable to the lub of all its lower bounds.
174 * Throw a NoInstanceException if this not possible.
175 */
176 void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException {
177 List<Type> lobounds = Type.filter(that.lobounds, errorFilter);
178 if (that.eq.isEmpty()) {
179 if (lobounds.isEmpty())
180 that.inst = syms.botType;
181 else if (lobounds.tail.isEmpty())
182 that.inst = lobounds.head.isPrimitive() ? syms.errType : lobounds.head;
183 else {
184 that.inst = types.lub(lobounds);
185 }
186 if (that.inst == null || that.inst.tag == ERROR)
187 throw ambiguousNoInstanceException
188 .setMessage("no.unique.minimal.instance.exists",
189 that.qtype, lobounds);
190 } else {
191 that.inst = that.eq.head;
192 }
193 }
195 Type asUndetType(Type t, List<Type> undetvars) {
196 return types.subst(t, inferenceVars(undetvars), undetvars);
197 }
199 List<Type> inferenceVars(List<Type> undetvars) {
200 ListBuffer<Type> tvars = ListBuffer.lb();
201 for (Type uv : undetvars) {
202 tvars.append(((UndetVar)uv).qtype);
203 }
204 return tvars.toList();
205 }
207 /***************************************************************************
208 * Exported Methods
209 ***************************************************************************/
211 /** Try to instantiate expression type `that' to given type `to'.
212 * If a maximal instantiation exists which makes this type
213 * a subtype of type `to', return the instantiated type.
214 * If no instantiation exists, or if several incomparable
215 * best instantiations exist throw a NoInstanceException.
216 */
217 public List<Type> instantiateUninferred(DiagnosticPosition pos,
218 List<Type> undetvars,
219 List<Type> tvars,
220 MethodType mtype,
221 Attr.ResultInfo resultInfo,
222 Warner warn) throws InferenceException {
223 Type to = resultInfo.pt;
224 if (to.tag == NONE) {
225 to = mtype.getReturnType().tag <= VOID ?
226 mtype.getReturnType() : syms.objectType;
227 }
228 Type qtype1 = types.subst(mtype.getReturnType(), tvars, undetvars);
229 if (!types.isSubtype(qtype1,
230 qtype1.tag == UNDETVAR ? types.boxedTypeOrType(to) : to)) {
231 throw unambiguousNoInstanceException
232 .setMessage("infer.no.conforming.instance.exists",
233 tvars, mtype.getReturnType(), to);
234 }
236 List<Type> insttypes;
237 while (true) {
238 boolean stuck = true;
239 insttypes = List.nil();
240 for (Type t : undetvars) {
241 UndetVar uv = (UndetVar)t;
242 if (uv.inst == null && (uv.eq.nonEmpty() || !Type.containsAny(uv.hibounds, tvars))) {
243 maximizeInst((UndetVar)t, warn);
244 stuck = false;
245 }
246 insttypes = insttypes.append(uv.inst == null ? uv.qtype : uv.inst);
247 }
248 if (!Type.containsAny(insttypes, tvars)) {
249 //all variables have been instantiated - exit
250 break;
251 } else if (stuck) {
252 //some variables could not be instantiated because of cycles in
253 //upper bounds - provide a (possibly recursive) default instantiation
254 insttypes = types.subst(insttypes,
255 tvars,
256 instantiateAsUninferredVars(undetvars, tvars));
257 break;
258 } else {
259 //some variables have been instantiated - replace newly instantiated
260 //variables in remaining upper bounds and continue
261 for (Type t : undetvars) {
262 UndetVar uv = (UndetVar)t;
263 uv.hibounds = types.subst(uv.hibounds, tvars, insttypes);
264 }
265 }
266 }
267 return insttypes;
268 }
270 /**
271 * Infer cyclic inference variables as described in 15.12.2.8.
272 */
273 private List<Type> instantiateAsUninferredVars(List<Type> undetvars, List<Type> tvars) {
274 Assert.check(undetvars.length() == tvars.length());
275 ListBuffer<Type> insttypes = ListBuffer.lb();
276 ListBuffer<Type> todo = ListBuffer.lb();
277 //step 1 - create fresh tvars
278 for (Type t : undetvars) {
279 UndetVar uv = (UndetVar)t;
280 if (uv.inst == null) {
281 TypeSymbol fresh_tvar = new TypeSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
282 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.hibounds), null);
283 todo.append(uv);
284 uv.inst = fresh_tvar.type;
285 }
286 insttypes.append(uv.inst);
287 }
288 //step 2 - replace fresh tvars in their bounds
289 List<Type> formals = tvars;
290 for (Type t : todo) {
291 UndetVar uv = (UndetVar)t;
292 TypeVar ct = (TypeVar)uv.inst;
293 ct.bound = types.glb(types.subst(types.getBounds(ct), tvars, insttypes.toList()));
294 if (ct.bound.isErroneous()) {
295 //report inference error if glb fails
296 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
297 }
298 formals = formals.tail;
299 }
300 return insttypes.toList();
301 }
303 /** Instantiate method type `mt' by finding instantiations of
304 * `tvars' so that method can be applied to `argtypes'.
305 */
306 public Type instantiateMethod(Env<AttrContext> env,
307 List<Type> tvars,
308 MethodType mt,
309 Attr.ResultInfo resultInfo,
310 Symbol msym,
311 List<Type> argtypes,
312 boolean allowBoxing,
313 boolean useVarargs,
314 Warner warn) throws InferenceException {
315 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
316 List<Type> undetvars = makeUndetvars(tvars);
318 List<Type> capturedArgs =
319 rs.checkRawArgumentsAcceptable(env, undetvars, argtypes, mt.getParameterTypes(),
320 allowBoxing, useVarargs, warn, new InferenceCheckHandler(undetvars));
322 // minimize as yet undetermined type variables
323 for (Type t : undetvars)
324 minimizeInst((UndetVar) t, warn);
326 /** Type variables instantiated to bottom */
327 ListBuffer<Type> restvars = new ListBuffer<Type>();
329 /** Undet vars instantiated to bottom */
330 final ListBuffer<Type> restundet = new ListBuffer<Type>();
332 /** Instantiated types or TypeVars if under-constrained */
333 ListBuffer<Type> insttypes = new ListBuffer<Type>();
335 /** Instantiated types or UndetVars if under-constrained */
336 ListBuffer<Type> undettypes = new ListBuffer<Type>();
338 for (Type t : undetvars) {
339 UndetVar uv = (UndetVar)t;
340 if (uv.inst.tag == BOT) {
341 restvars.append(uv.qtype);
342 restundet.append(uv);
343 insttypes.append(uv.qtype);
344 undettypes.append(uv);
345 uv.inst = null;
346 } else {
347 insttypes.append(uv.inst);
348 undettypes.append(uv.inst);
349 }
350 }
351 checkWithinBounds(tvars, undetvars, insttypes.toList(), warn);
353 mt = (MethodType)types.subst(mt, tvars, insttypes.toList());
355 if (!restvars.isEmpty() && resultInfo != null) {
356 List<Type> restInferred =
357 instantiateUninferred(env.tree.pos(), restundet.toList(), restvars.toList(), mt, resultInfo, warn);
358 checkWithinBounds(tvars, undetvars,
359 types.subst(insttypes.toList(), restvars.toList(), restInferred), warn);
360 mt = (MethodType)types.subst(mt, restvars.toList(), restInferred);
361 if (rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
362 log.note(env.tree.pos, "deferred.method.inst", msym, mt, resultInfo.pt);
363 }
364 }
366 if (restvars.isEmpty() || resultInfo != null) {
367 // check that actuals conform to inferred formals
368 checkArgumentsAcceptable(env, capturedArgs, mt.getParameterTypes(), allowBoxing, useVarargs, warn);
369 }
370 // return instantiated version of method type
371 return mt;
372 }
373 //where
375 /** inference check handler **/
376 class InferenceCheckHandler implements Resolve.MethodCheckHandler {
378 List<Type> undetvars;
380 public InferenceCheckHandler(List<Type> undetvars) {
381 this.undetvars = undetvars;
382 }
384 public InapplicableMethodException arityMismatch() {
385 return unambiguousNoInstanceException.setMessage("infer.arg.length.mismatch");
386 }
387 public InapplicableMethodException argumentMismatch(boolean varargs, Type found, Type expected) {
388 String key = varargs ?
389 "infer.varargs.argument.mismatch" :
390 "infer.no.conforming.assignment.exists";
391 return unambiguousNoInstanceException.setMessage(key,
392 inferenceVars(undetvars), found, expected);
393 }
394 public InapplicableMethodException inaccessibleVarargs(Symbol location, Type expected) {
395 return unambiguousNoInstanceException.setMessage("inaccessible.varargs.type",
396 expected, Kinds.kindName(location), location);
397 }
398 }
400 private void checkArgumentsAcceptable(Env<AttrContext> env, List<Type> actuals, List<Type> formals,
401 boolean allowBoxing, boolean useVarargs, Warner warn) {
402 try {
403 rs.checkRawArgumentsAcceptable(env, actuals, formals,
404 allowBoxing, useVarargs, warn);
405 }
406 catch (InapplicableMethodException ex) {
407 // inferred method is not applicable
408 throw invalidInstanceException.setMessage(ex.getDiagnostic());
409 }
410 }
412 /** check that type parameters are within their bounds.
413 */
414 void checkWithinBounds(List<Type> tvars,
415 List<Type> undetvars,
416 List<Type> arguments,
417 Warner warn)
418 throws InvalidInstanceException {
419 List<Type> args = arguments;
420 for (Type t : undetvars) {
421 UndetVar uv = (UndetVar)t;
422 uv.hibounds = types.subst(uv.hibounds, tvars, arguments);
423 uv.lobounds = types.subst(uv.lobounds, tvars, arguments);
424 uv.eq = types.subst(uv.eq, tvars, arguments);
425 checkCompatibleUpperBounds(uv, tvars);
426 if (args.head.tag != TYPEVAR || !args.head.containsAny(tvars)) {
427 Type inst = args.head;
428 for (Type u : uv.hibounds) {
429 if (!types.isSubtypeUnchecked(inst, types.subst(u, tvars, undetvars), warn)) {
430 reportBoundError(uv, BoundErrorKind.UPPER);
431 }
432 }
433 for (Type l : uv.lobounds) {
434 if (!types.isSubtypeUnchecked(types.subst(l, tvars, undetvars), inst, warn)) {
435 reportBoundError(uv, BoundErrorKind.LOWER);
436 }
437 }
438 for (Type e : uv.eq) {
439 if (!types.isSameType(inst, types.subst(e, tvars, undetvars))) {
440 reportBoundError(uv, BoundErrorKind.EQ);
441 }
442 }
443 }
444 args = args.tail;
445 }
446 }
448 void checkCompatibleUpperBounds(UndetVar uv, List<Type> tvars) {
449 // VGJ: sort of inlined maximizeInst() below. Adding
450 // bounds can cause lobounds that are above hibounds.
451 ListBuffer<Type> hiboundsNoVars = ListBuffer.lb();
452 for (Type t : Type.filter(uv.hibounds, errorFilter)) {
453 if (!t.containsAny(tvars)) {
454 hiboundsNoVars.append(t);
455 }
456 }
457 List<Type> hibounds = hiboundsNoVars.toList();
458 Type hb = null;
459 if (hibounds.isEmpty())
460 hb = syms.objectType;
461 else if (hibounds.tail.isEmpty())
462 hb = hibounds.head;
463 else
464 hb = types.glb(hibounds);
465 if (hb == null || hb.isErroneous())
466 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
467 }
469 enum BoundErrorKind {
470 BAD_UPPER() {
471 @Override
472 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
473 return ex.setMessage("incompatible.upper.bounds", uv.qtype, uv.hibounds);
474 }
475 },
476 UPPER() {
477 @Override
478 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
479 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst, uv.hibounds);
480 }
481 },
482 LOWER() {
483 @Override
484 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
485 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst, uv.lobounds);
486 }
487 },
488 EQ() {
489 @Override
490 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
491 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst, uv.eq);
492 }
493 };
495 abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
496 }
497 //where
498 void reportBoundError(UndetVar uv, BoundErrorKind bk) {
499 throw bk.setMessage(uv.inst == null ? ambiguousNoInstanceException : invalidInstanceException, uv);
500 }
502 /**
503 * Compute a synthetic method type corresponding to the requested polymorphic
504 * method signature. The target return type is computed from the immediately
505 * enclosing scope surrounding the polymorphic-signature call.
506 */
507 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
508 MethodSymbol spMethod, // sig. poly. method or null if none
509 List<Type> argtypes) {
510 final Type restype;
512 //The return type for a polymorphic signature call is computed from
513 //the enclosing tree E, as follows: if E is a cast, then use the
514 //target type of the cast expression as a return type; if E is an
515 //expression statement, the return type is 'void' - otherwise the
516 //return type is simply 'Object'. A correctness check ensures that
517 //env.next refers to the lexically enclosing environment in which
518 //the polymorphic signature call environment is nested.
520 switch (env.next.tree.getTag()) {
521 case TYPECAST:
522 JCTypeCast castTree = (JCTypeCast)env.next.tree;
523 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
524 castTree.clazz.type :
525 syms.objectType;
526 break;
527 case EXEC:
528 JCTree.JCExpressionStatement execTree =
529 (JCTree.JCExpressionStatement)env.next.tree;
530 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
531 syms.voidType :
532 syms.objectType;
533 break;
534 default:
535 restype = syms.objectType;
536 }
538 List<Type> paramtypes = Type.map(argtypes, implicitArgType);
539 List<Type> exType = spMethod != null ?
540 spMethod.getThrownTypes() :
541 List.of(syms.throwableType); // make it throw all exceptions
543 MethodType mtype = new MethodType(paramtypes,
544 restype,
545 exType,
546 syms.methodClass);
547 return mtype;
548 }
549 //where
550 Mapping implicitArgType = new Mapping ("implicitArgType") {
551 public Type apply(Type t) {
552 t = types.erasure(t);
553 if (t.tag == BOT)
554 // nulls type as the marker type Null (which has no instances)
555 // infer as java.lang.Void for now
556 t = types.boxedClass(syms.voidType).type;
557 return t;
558 }
559 };
560 }