Wed, 11 Apr 2012 10:50:11 +0100
7154127: Inference cleanup: remove bound check analysis from visitors in Types.java
Summary: Remove bound checking rules from recursive subtype visitors in Types.java and replace with centralized bound-checking logic
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.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 Type instantiateExpr(ForAll that,
218 Type to,
219 Warner warn) throws InferenceException {
220 List<Type> undetvars = that.undetvars();
221 Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);
222 if (!types.isSubtype(qtype1,
223 qtype1.tag == UNDETVAR ? types.boxedTypeOrType(to) : to)) {
224 throw unambiguousNoInstanceException
225 .setMessage("infer.no.conforming.instance.exists",
226 that.tvars, that.qtype, to);
227 }
229 List<Type> insttypes;
230 while (true) {
231 boolean stuck = true;
232 insttypes = List.nil();
233 for (Type t : undetvars) {
234 UndetVar uv = (UndetVar)t;
235 if (uv.inst == null && (uv.eq.nonEmpty() || !Type.containsAny(uv.hibounds, that.tvars))) {
236 maximizeInst((UndetVar)t, warn);
237 stuck = false;
238 }
239 insttypes = insttypes.append(uv.inst == null ? uv.qtype : uv.inst);
240 }
241 if (!Type.containsAny(insttypes, that.tvars)) {
242 //all variables have been instantiated - exit
243 break;
244 } else if (stuck) {
245 //some variables could not be instantiated because of cycles in
246 //upper bounds - provide a (possibly recursive) default instantiation
247 insttypes = types.subst(insttypes,
248 that.tvars,
249 instantiateAsUninferredVars(undetvars, that.tvars));
250 break;
251 } else {
252 //some variables have been instantiated - replace newly instantiated
253 //variables in remaining upper bounds and continue
254 for (Type t : undetvars) {
255 UndetVar uv = (UndetVar)t;
256 uv.hibounds = types.subst(uv.hibounds, that.tvars, insttypes);
257 }
258 }
259 }
260 return that.inst(insttypes, types);
261 }
263 /**
264 * Infer cyclic inference variables as described in 15.12.2.8.
265 */
266 private List<Type> instantiateAsUninferredVars(List<Type> undetvars, List<Type> tvars) {
267 Assert.check(undetvars.length() == tvars.length());
268 ListBuffer<Type> insttypes = ListBuffer.lb();
269 ListBuffer<Type> todo = ListBuffer.lb();
270 //step 1 - create fresh tvars
271 for (Type t : undetvars) {
272 UndetVar uv = (UndetVar)t;
273 if (uv.inst == null) {
274 TypeSymbol fresh_tvar = new TypeSymbol(Flags.SYNTHETIC, uv.qtype.tsym.name, null, uv.qtype.tsym.owner);
275 fresh_tvar.type = new TypeVar(fresh_tvar, types.makeCompoundType(uv.hibounds), null);
276 todo.append(uv);
277 uv.inst = fresh_tvar.type;
278 }
279 insttypes.append(uv.inst);
280 }
281 //step 2 - replace fresh tvars in their bounds
282 List<Type> formals = tvars;
283 for (Type t : todo) {
284 UndetVar uv = (UndetVar)t;
285 TypeVar ct = (TypeVar)uv.inst;
286 ct.bound = types.glb(types.subst(types.getBounds(ct), tvars, insttypes.toList()));
287 if (ct.bound.isErroneous()) {
288 //report inference error if glb fails
289 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
290 }
291 formals = formals.tail;
292 }
293 return insttypes.toList();
294 }
296 /** Instantiate method type `mt' by finding instantiations of
297 * `tvars' so that method can be applied to `argtypes'.
298 */
299 public Type instantiateMethod(final Env<AttrContext> env,
300 List<Type> tvars,
301 MethodType mt,
302 final Symbol msym,
303 final List<Type> argtypes,
304 final boolean allowBoxing,
305 final boolean useVarargs,
306 final Warner warn) throws InferenceException {
307 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
308 final List<Type> undetvars = makeUndetvars(tvars);
310 final List<Type> capturedArgs =
311 rs.checkRawArgumentsAcceptable(env, undetvars, argtypes, mt.getParameterTypes(),
312 allowBoxing, useVarargs, warn, new InferenceCheckHandler(undetvars));
314 // minimize as yet undetermined type variables
315 for (Type t : undetvars)
316 minimizeInst((UndetVar) t, warn);
318 /** Type variables instantiated to bottom */
319 ListBuffer<Type> restvars = new ListBuffer<Type>();
321 /** Undet vars instantiated to bottom */
322 final ListBuffer<Type> restundet = new ListBuffer<Type>();
324 /** Instantiated types or TypeVars if under-constrained */
325 ListBuffer<Type> insttypes = new ListBuffer<Type>();
327 /** Instantiated types or UndetVars if under-constrained */
328 ListBuffer<Type> undettypes = new ListBuffer<Type>();
330 for (Type t : undetvars) {
331 UndetVar uv = (UndetVar)t;
332 if (uv.inst.tag == BOT) {
333 restvars.append(uv.qtype);
334 restundet.append(uv);
335 insttypes.append(uv.qtype);
336 undettypes.append(uv);
337 uv.inst = null;
338 } else {
339 insttypes.append(uv.inst);
340 undettypes.append(uv.inst);
341 }
342 }
343 checkWithinBounds(tvars, undetvars, insttypes.toList(), warn);
345 mt = (MethodType)types.subst(mt, tvars, insttypes.toList());
347 if (!restvars.isEmpty()) {
348 // if there are uninstantiated variables,
349 // quantify result type with them
350 final List<Type> inferredTypes = insttypes.toList();
351 final List<Type> all_tvars = tvars; //this is the wrong tvars
352 return new UninferredMethodType(env.tree.pos(), msym, mt, restvars.toList()) {
353 @Override
354 List<Type> undetvars() {
355 return restundet.toList();
356 }
357 @Override
358 void instantiateReturnType(Type restype, List<Type> inferred, Types types) throws NoInstanceException {
359 Type owntype = new MethodType(types.subst(getParameterTypes(), tvars, inferred),
360 restype,
361 types.subst(getThrownTypes(), tvars, inferred),
362 qtype.tsym);
363 // check that actuals conform to inferred formals
364 warn.clear();
365 checkArgumentsAcceptable(env, capturedArgs, owntype.getParameterTypes(), allowBoxing, useVarargs, warn);
366 // check that inferred bounds conform to their bounds
367 checkWithinBounds(all_tvars, undetvars,
368 types.subst(inferredTypes, tvars, inferred), warn);
369 qtype = chk.checkMethod(owntype, msym, env, TreeInfo.args(env.tree), capturedArgs, useVarargs, warn.hasNonSilentLint(Lint.LintCategory.UNCHECKED));
370 }
371 };
372 }
373 else {
374 // check that actuals conform to inferred formals
375 checkArgumentsAcceptable(env, capturedArgs, mt.getParameterTypes(), allowBoxing, useVarargs, warn);
376 // return instantiated version of method type
377 return mt;
378 }
379 }
380 //where
382 /** inference check handler **/
383 class InferenceCheckHandler implements Resolve.MethodCheckHandler {
385 List<Type> undetvars;
387 public InferenceCheckHandler(List<Type> undetvars) {
388 this.undetvars = undetvars;
389 }
391 public InapplicableMethodException arityMismatch() {
392 return unambiguousNoInstanceException.setMessage("infer.arg.length.mismatch");
393 }
394 public InapplicableMethodException argumentMismatch(boolean varargs, Type found, Type expected) {
395 String key = varargs ?
396 "infer.varargs.argument.mismatch" :
397 "infer.no.conforming.assignment.exists";
398 return unambiguousNoInstanceException.setMessage(key,
399 inferenceVars(undetvars), found, expected);
400 }
401 public InapplicableMethodException inaccessibleVarargs(Symbol location, Type expected) {
402 return unambiguousNoInstanceException.setMessage("inaccessible.varargs.type",
403 expected, Kinds.kindName(location), location);
404 }
405 }
407 /**
408 * A delegated type representing a partially uninferred method type.
409 * The return type of a partially uninferred method type is a ForAll
410 * type - when the return type is instantiated (see Infer.instantiateExpr)
411 * the underlying method type is also updated.
412 */
413 abstract class UninferredMethodType extends DelegatedType {
415 final List<Type> tvars;
416 final Symbol msym;
417 final DiagnosticPosition pos;
419 public UninferredMethodType(DiagnosticPosition pos, Symbol msym, MethodType mtype, List<Type> tvars) {
420 super(METHOD, new MethodType(mtype.argtypes, null, mtype.thrown, mtype.tsym));
421 this.tvars = tvars;
422 this.msym = msym;
423 this.pos = pos;
424 asMethodType().restype = new UninferredReturnType(tvars, mtype.restype);
425 }
427 @Override
428 public MethodType asMethodType() {
429 return qtype.asMethodType();
430 }
432 @Override
433 public Type map(Mapping f) {
434 return qtype.map(f);
435 }
437 abstract void instantiateReturnType(Type restype, List<Type> inferred, Types types);
439 abstract List<Type> undetvars();
441 class UninferredReturnType extends ForAll {
442 public UninferredReturnType(List<Type> tvars, Type restype) {
443 super(tvars, restype);
444 }
445 @Override
446 public Type inst(List<Type> actuals, Types types) {
447 Type newRestype = super.inst(actuals, types);
448 instantiateReturnType(newRestype, actuals, types);
449 if (rs.verboseResolutionMode.contains(VerboseResolutionMode.DEFERRED_INST)) {
450 log.note(pos, "deferred.method.inst", msym, UninferredMethodType.this.qtype, newRestype);
451 }
452 return UninferredMethodType.this.qtype.getReturnType();
453 }
454 @Override
455 public List<Type> undetvars() {
456 return UninferredMethodType.this.undetvars();
457 }
458 }
459 }
461 private void checkArgumentsAcceptable(Env<AttrContext> env, List<Type> actuals, List<Type> formals,
462 boolean allowBoxing, boolean useVarargs, Warner warn) {
463 try {
464 rs.checkRawArgumentsAcceptable(env, actuals, formals,
465 allowBoxing, useVarargs, warn);
466 }
467 catch (InapplicableMethodException ex) {
468 // inferred method is not applicable
469 throw invalidInstanceException.setMessage(ex.getDiagnostic());
470 }
471 }
473 /** check that type parameters are within their bounds.
474 */
475 void checkWithinBounds(List<Type> tvars,
476 List<Type> undetvars,
477 List<Type> arguments,
478 Warner warn)
479 throws InvalidInstanceException {
480 List<Type> args = arguments;
481 for (Type t : undetvars) {
482 UndetVar uv = (UndetVar)t;
483 uv.hibounds = types.subst(uv.hibounds, tvars, arguments);
484 uv.lobounds = types.subst(uv.lobounds, tvars, arguments);
485 uv.eq = types.subst(uv.eq, tvars, arguments);
486 checkCompatibleUpperBounds(uv, tvars);
487 if (args.head.tag != TYPEVAR || !args.head.containsAny(tvars)) {
488 Type inst = args.head;
489 for (Type u : uv.hibounds) {
490 if (!types.isSubtypeUnchecked(inst, types.subst(u, tvars, undetvars), warn)) {
491 reportBoundError(uv, BoundErrorKind.UPPER);
492 }
493 }
494 for (Type l : uv.lobounds) {
495 if (!types.isSubtypeUnchecked(types.subst(l, tvars, undetvars), inst, warn)) {
496 reportBoundError(uv, BoundErrorKind.LOWER);
497 }
498 }
499 for (Type e : uv.eq) {
500 if (!types.isSameType(inst, types.subst(e, tvars, undetvars))) {
501 reportBoundError(uv, BoundErrorKind.EQ);
502 }
503 }
504 }
505 args = args.tail;
506 }
507 }
509 void checkCompatibleUpperBounds(UndetVar uv, List<Type> tvars) {
510 // VGJ: sort of inlined maximizeInst() below. Adding
511 // bounds can cause lobounds that are above hibounds.
512 ListBuffer<Type> hiboundsNoVars = ListBuffer.lb();
513 for (Type t : Type.filter(uv.hibounds, errorFilter)) {
514 if (!t.containsAny(tvars)) {
515 hiboundsNoVars.append(t);
516 }
517 }
518 List<Type> hibounds = hiboundsNoVars.toList();
519 Type hb = null;
520 if (hibounds.isEmpty())
521 hb = syms.objectType;
522 else if (hibounds.tail.isEmpty())
523 hb = hibounds.head;
524 else
525 hb = types.glb(hibounds);
526 if (hb == null || hb.isErroneous())
527 reportBoundError(uv, BoundErrorKind.BAD_UPPER);
528 }
530 enum BoundErrorKind {
531 BAD_UPPER() {
532 @Override
533 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
534 return ex.setMessage("incompatible.upper.bounds", uv.qtype, uv.hibounds);
535 }
536 },
537 UPPER() {
538 @Override
539 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
540 return ex.setMessage("inferred.do.not.conform.to.upper.bounds", uv.inst, uv.hibounds);
541 }
542 },
543 LOWER() {
544 @Override
545 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
546 return ex.setMessage("inferred.do.not.conform.to.lower.bounds", uv.inst, uv.lobounds);
547 }
548 },
549 EQ() {
550 @Override
551 InapplicableMethodException setMessage(InferenceException ex, UndetVar uv) {
552 return ex.setMessage("inferred.do.not.conform.to.eq.bounds", uv.inst, uv.eq);
553 }
554 };
556 abstract InapplicableMethodException setMessage(InferenceException ex, UndetVar uv);
557 }
558 //where
559 void reportBoundError(UndetVar uv, BoundErrorKind bk) {
560 throw bk.setMessage(uv.inst == null ? ambiguousNoInstanceException : invalidInstanceException, uv);
561 }
563 /**
564 * Compute a synthetic method type corresponding to the requested polymorphic
565 * method signature. The target return type is computed from the immediately
566 * enclosing scope surrounding the polymorphic-signature call.
567 */
568 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env,
569 MethodSymbol spMethod, // sig. poly. method or null if none
570 List<Type> argtypes) {
571 final Type restype;
573 //The return type for a polymorphic signature call is computed from
574 //the enclosing tree E, as follows: if E is a cast, then use the
575 //target type of the cast expression as a return type; if E is an
576 //expression statement, the return type is 'void' - otherwise the
577 //return type is simply 'Object'. A correctness check ensures that
578 //env.next refers to the lexically enclosing environment in which
579 //the polymorphic signature call environment is nested.
581 switch (env.next.tree.getTag()) {
582 case TYPECAST:
583 JCTypeCast castTree = (JCTypeCast)env.next.tree;
584 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
585 castTree.clazz.type :
586 syms.objectType;
587 break;
588 case EXEC:
589 JCTree.JCExpressionStatement execTree =
590 (JCTree.JCExpressionStatement)env.next.tree;
591 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
592 syms.voidType :
593 syms.objectType;
594 break;
595 default:
596 restype = syms.objectType;
597 }
599 List<Type> paramtypes = Type.map(argtypes, implicitArgType);
600 List<Type> exType = spMethod != null ?
601 spMethod.getThrownTypes() :
602 List.of(syms.throwableType); // make it throw all exceptions
604 MethodType mtype = new MethodType(paramtypes,
605 restype,
606 exType,
607 syms.methodClass);
608 return mtype;
609 }
610 //where
611 Mapping implicitArgType = new Mapping ("implicitArgType") {
612 public Type apply(Type t) {
613 t = types.erasure(t);
614 if (t.tag == BOT)
615 // nulls type as the marker type Null (which has no instances)
616 // infer as java.lang.Void for now
617 t = types.boxedClass(syms.voidType).type;
618 return t;
619 }
620 };
621 }