Mercurial > jdk8-mips64-public > langtools / file revision
src/share/classes/com/sun/tools/javac/comp/Infer.java@19c900c703c6
src/share/classes/com/sun/tools/javac/comp/Infer.java
Mon, 24 Jan 2011 15:44:15 +0000
- author
- mcimadamore
- date
- Mon, 24 Jan 2011 15:44:15 +0000
- changeset 828
- 19c900c703c6
- parent 820
- 2d5aff89aaa3
- child 832
- 57e3b9bc7fb8
- permissions
- -rw-r--r--
6943278: spurious error message for inference and type-variable with erroneous bound
Summary: type-inference should ignore erroneous bounds
Reviewed-by: jjg
1 /*
2 * Copyright (c) 1999, 2010, 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.Type.ForAll.ConstraintKind;
36 import com.sun.tools.javac.code.Symbol.*;
37 import com.sun.tools.javac.util.JCDiagnostic;
39 import static com.sun.tools.javac.code.TypeTags.*;
41 /** Helper class for type parameter inference, used by the attribution phase.
42 *
43 * <p><b>This is NOT part of any supported API.
44 * If you write code that depends on this, you do so at your own risk.
45 * This code and its internal interfaces are subject to change or
46 * deletion without notice.</b>
47 */
48 public class Infer {
49 protected static final Context.Key<Infer> inferKey =
50 new Context.Key<Infer>();
52 /** A value for prototypes that admit any type, including polymorphic ones. */
53 public static final Type anyPoly = new Type(NONE, null);
55 Symtab syms;
56 Types types;
57 Check chk;
58 Resolve rs;
59 JCDiagnostic.Factory diags;
61 public static Infer instance(Context context) {
62 Infer instance = context.get(inferKey);
63 if (instance == null)
64 instance = new Infer(context);
65 return instance;
66 }
68 protected Infer(Context context) {
69 context.put(inferKey, this);
70 syms = Symtab.instance(context);
71 types = Types.instance(context);
72 rs = Resolve.instance(context);
73 chk = Check.instance(context);
74 diags = JCDiagnostic.Factory.instance(context);
75 ambiguousNoInstanceException =
76 new NoInstanceException(true, diags);
77 unambiguousNoInstanceException =
78 new NoInstanceException(false, diags);
79 invalidInstanceException =
80 new InvalidInstanceException(diags);
82 }
84 public static class InferenceException extends Resolve.InapplicableMethodException {
85 private static final long serialVersionUID = 0;
87 InferenceException(JCDiagnostic.Factory diags) {
88 super(diags);
89 }
90 }
92 public static class NoInstanceException extends InferenceException {
93 private static final long serialVersionUID = 1;
95 boolean isAmbiguous; // exist several incomparable best instances?
97 NoInstanceException(boolean isAmbiguous, JCDiagnostic.Factory diags) {
98 super(diags);
99 this.isAmbiguous = isAmbiguous;
100 }
101 }
103 public static class InvalidInstanceException extends InferenceException {
104 private static final long serialVersionUID = 2;
106 InvalidInstanceException(JCDiagnostic.Factory diags) {
107 super(diags);
108 }
109 }
111 private final NoInstanceException ambiguousNoInstanceException;
112 private final NoInstanceException unambiguousNoInstanceException;
113 private final InvalidInstanceException invalidInstanceException;
115 /***************************************************************************
116 * Auxiliary type values and classes
117 ***************************************************************************/
119 /** A mapping that turns type variables into undetermined type variables.
120 */
121 Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
122 public Type apply(Type t) {
123 if (t.tag == TYPEVAR) return new UndetVar(t);
124 else return t.map(this);
125 }
126 };
128 /** A mapping that returns its type argument with every UndetVar replaced
129 * by its `inst' field. Throws a NoInstanceException
130 * if this not possible because an `inst' field is null.
131 * Note: mutually referring undertvars will be left uninstantiated
132 * (that is, they will be replaced by the underlying type-variable).
133 */
135 Mapping getInstFun = new Mapping("getInstFun") {
136 public Type apply(Type t) {
137 switch (t.tag) {
138 case UNKNOWN:
139 throw ambiguousNoInstanceException
140 .setMessage("undetermined.type");
141 case UNDETVAR:
142 UndetVar that = (UndetVar) t;
143 if (that.inst == null)
144 throw ambiguousNoInstanceException
145 .setMessage("type.variable.has.undetermined.type",
146 that.qtype);
147 return isConstraintCyclic(that) ?
148 that.qtype :
149 apply(that.inst);
150 default:
151 return t.map(this);
152 }
153 }
155 private boolean isConstraintCyclic(UndetVar uv) {
156 Types.UnaryVisitor<Boolean> constraintScanner =
157 new Types.UnaryVisitor<Boolean>() {
159 List<Type> seen = List.nil();
161 Boolean visit(List<Type> ts) {
162 for (Type t : ts) {
163 if (visit(t)) return true;
164 }
165 return false;
166 }
168 public Boolean visitType(Type t, Void ignored) {
169 return false;
170 }
172 @Override
173 public Boolean visitClassType(ClassType t, Void ignored) {
174 if (t.isCompound()) {
175 return visit(types.supertype(t)) ||
176 visit(types.interfaces(t));
177 } else {
178 return visit(t.getTypeArguments());
179 }
180 }
181 @Override
182 public Boolean visitWildcardType(WildcardType t, Void ignored) {
183 return visit(t.type);
184 }
186 @Override
187 public Boolean visitUndetVar(UndetVar t, Void ignored) {
188 if (seen.contains(t)) {
189 return true;
190 } else {
191 seen = seen.prepend(t);
192 return visit(t.inst);
193 }
194 }
195 };
196 return constraintScanner.visit(uv);
197 }
198 };
200 /***************************************************************************
201 * Mini/Maximization of UndetVars
202 ***************************************************************************/
204 /** Instantiate undetermined type variable to its minimal upper bound.
205 * Throw a NoInstanceException if this not possible.
206 */
207 void maximizeInst(UndetVar that, Warner warn) throws NoInstanceException {
208 List<Type> hibounds = Type.filter(that.hibounds, errorFilter);
209 if (that.inst == null) {
210 if (hibounds.isEmpty())
211 that.inst = syms.objectType;
212 else if (hibounds.tail.isEmpty())
213 that.inst = hibounds.head;
214 else
215 that.inst = types.glb(hibounds);
216 }
217 if (that.inst == null ||
218 that.inst.isErroneous())
219 throw ambiguousNoInstanceException
220 .setMessage("no.unique.maximal.instance.exists",
221 that.qtype, hibounds);
222 }
223 //where
224 private boolean isSubClass(Type t, final List<Type> ts) {
225 t = t.baseType();
226 if (t.tag == TYPEVAR) {
227 List<Type> bounds = types.getBounds((TypeVar)t);
228 for (Type s : ts) {
229 if (!types.isSameType(t, s.baseType())) {
230 for (Type bound : bounds) {
231 if (!isSubClass(bound, List.of(s.baseType())))
232 return false;
233 }
234 }
235 }
236 } else {
237 for (Type s : ts) {
238 if (!t.tsym.isSubClass(s.baseType().tsym, types))
239 return false;
240 }
241 }
242 return true;
243 }
245 private Filter<Type> errorFilter = new Filter<Type>() {
246 @Override
247 public boolean accepts(Type t) {
248 return !t.isErroneous();
249 }
250 };
252 /** Instantiate undetermined type variable to the lub of all its lower bounds.
253 * Throw a NoInstanceException if this not possible.
254 */
255 void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException {
256 List<Type> lobounds = Type.filter(that.lobounds, errorFilter);
257 if (that.inst == null) {
258 if (lobounds.isEmpty())
259 that.inst = syms.botType;
260 else if (lobounds.tail.isEmpty())
261 that.inst = lobounds.head.isPrimitive() ? syms.errType : lobounds.head;
262 else {
263 that.inst = types.lub(lobounds);
264 }
265 if (that.inst == null || that.inst.tag == ERROR)
266 throw ambiguousNoInstanceException
267 .setMessage("no.unique.minimal.instance.exists",
268 that.qtype, lobounds);
269 // VGJ: sort of inlined maximizeInst() below. Adding
270 // bounds can cause lobounds that are above hibounds.
271 List<Type> hibounds = Type.filter(that.hibounds, errorFilter);
272 if (hibounds.isEmpty())
273 return;
274 Type hb = null;
275 if (hibounds.tail.isEmpty())
276 hb = hibounds.head;
277 else for (List<Type> bs = hibounds;
278 bs.nonEmpty() && hb == null;
279 bs = bs.tail) {
280 if (isSubClass(bs.head, hibounds))
281 hb = types.fromUnknownFun.apply(bs.head);
282 }
283 if (hb == null ||
284 !types.isSubtypeUnchecked(hb, hibounds, warn) ||
285 !types.isSubtypeUnchecked(that.inst, hb, warn))
286 throw ambiguousNoInstanceException;
287 }
288 }
290 /***************************************************************************
291 * Exported Methods
292 ***************************************************************************/
294 /** Try to instantiate expression type `that' to given type `to'.
295 * If a maximal instantiation exists which makes this type
296 * a subtype of type `to', return the instantiated type.
297 * If no instantiation exists, or if several incomparable
298 * best instantiations exist throw a NoInstanceException.
299 */
300 public Type instantiateExpr(ForAll that,
301 Type to,
302 Warner warn) throws InferenceException {
303 List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);
304 for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {
305 UndetVar uv = (UndetVar) l.head;
306 TypeVar tv = (TypeVar)uv.qtype;
307 ListBuffer<Type> hibounds = new ListBuffer<Type>();
308 for (Type t : that.getConstraints(tv, ConstraintKind.EXTENDS)) {
309 hibounds.append(types.subst(t, that.tvars, undetvars));
310 }
312 List<Type> inst = that.getConstraints(tv, ConstraintKind.EQUAL);
313 if (inst.nonEmpty() && inst.head.tag != BOT) {
314 uv.inst = inst.head;
315 }
316 uv.hibounds = hibounds.toList();
317 }
318 Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);
319 if (!types.isSubtype(qtype1,
320 qtype1.tag == UNDETVAR ? types.boxedTypeOrType(to) : to)) {
321 throw unambiguousNoInstanceException
322 .setMessage("infer.no.conforming.instance.exists",
323 that.tvars, that.qtype, to);
324 }
325 for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail)
326 maximizeInst((UndetVar) l.head, warn);
327 // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG
329 // check bounds
330 List<Type> targs = Type.map(undetvars, getInstFun);
331 if (Type.containsAny(targs, that.tvars)) {
332 //replace uninferred type-vars
333 targs = types.subst(targs,
334 that.tvars,
335 instaniateAsUninferredVars(undetvars, that.tvars));
336 }
337 return chk.checkType(warn.pos(), that.inst(targs, types), to);
338 }
339 //where
340 private List<Type> instaniateAsUninferredVars(List<Type> undetvars, List<Type> tvars) {
341 ListBuffer<Type> new_targs = ListBuffer.lb();
342 //step 1 - create syntethic captured vars
343 for (Type t : undetvars) {
344 UndetVar uv = (UndetVar)t;
345 Type newArg = new CapturedType(t.tsym.name, t.tsym, uv.inst, syms.botType, null);
346 new_targs = new_targs.append(newArg);
347 }
348 //step 2 - replace synthetic vars in their bounds
349 for (Type t : new_targs.toList()) {
350 CapturedType ct = (CapturedType)t;
351 ct.bound = types.subst(ct.bound, tvars, new_targs.toList());
352 WildcardType wt = new WildcardType(ct.bound, BoundKind.EXTENDS, syms.boundClass);
353 ct.wildcard = wt;
354 }
355 return new_targs.toList();
356 }
358 /** Instantiate method type `mt' by finding instantiations of
359 * `tvars' so that method can be applied to `argtypes'.
360 */
361 public Type instantiateMethod(final Env<AttrContext> env,
362 List<Type> tvars,
363 MethodType mt,
364 final Symbol msym,
365 final List<Type> argtypes,
366 final boolean allowBoxing,
367 final boolean useVarargs,
368 final Warner warn) throws InferenceException {
369 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
370 List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
371 List<Type> formals = mt.argtypes;
372 //need to capture exactly once - otherwise subsequent
373 //applicability checks might fail
374 final List<Type> capturedArgs = types.capture(argtypes);
375 List<Type> actuals = capturedArgs;
376 List<Type> actualsNoCapture = argtypes;
377 // instantiate all polymorphic argument types and
378 // set up lower bounds constraints for undetvars
379 Type varargsFormal = useVarargs ? formals.last() : null;
380 if (varargsFormal == null &&
381 actuals.size() != formals.size()) {
382 throw unambiguousNoInstanceException
383 .setMessage("infer.arg.length.mismatch");
384 }
385 while (actuals.nonEmpty() && formals.head != varargsFormal) {
386 Type formal = formals.head;
387 Type actual = actuals.head.baseType();
388 Type actualNoCapture = actualsNoCapture.head.baseType();
389 if (actual.tag == FORALL)
390 actual = instantiateArg((ForAll)actual, formal, tvars, warn);
391 Type undetFormal = types.subst(formal, tvars, undetvars);
392 boolean works = allowBoxing
393 ? types.isConvertible(actual, undetFormal, warn)
394 : types.isSubtypeUnchecked(actual, undetFormal, warn);
395 if (!works) {
396 throw unambiguousNoInstanceException
397 .setMessage("infer.no.conforming.assignment.exists",
398 tvars, actualNoCapture, formal);
399 }
400 formals = formals.tail;
401 actuals = actuals.tail;
402 actualsNoCapture = actualsNoCapture.tail;
403 }
405 if (formals.head != varargsFormal) // not enough args
406 throw unambiguousNoInstanceException.setMessage("infer.arg.length.mismatch");
408 // for varargs arguments as well
409 if (useVarargs) {
410 Type elemType = types.elemtype(varargsFormal);
411 Type elemUndet = types.subst(elemType, tvars, undetvars);
412 while (actuals.nonEmpty()) {
413 Type actual = actuals.head.baseType();
414 Type actualNoCapture = actualsNoCapture.head.baseType();
415 if (actual.tag == FORALL)
416 actual = instantiateArg((ForAll)actual, elemType, tvars, warn);
417 boolean works = types.isConvertible(actual, elemUndet, warn);
418 if (!works) {
419 throw unambiguousNoInstanceException
420 .setMessage("infer.no.conforming.assignment.exists",
421 tvars, actualNoCapture, elemType);
422 }
423 actuals = actuals.tail;
424 actualsNoCapture = actualsNoCapture.tail;
425 }
426 }
428 // minimize as yet undetermined type variables
429 for (Type t : undetvars)
430 minimizeInst((UndetVar) t, warn);
432 /** Type variables instantiated to bottom */
433 ListBuffer<Type> restvars = new ListBuffer<Type>();
435 /** Undet vars instantiated to bottom */
436 final ListBuffer<Type> restundet = new ListBuffer<Type>();
438 /** Instantiated types or TypeVars if under-constrained */
439 ListBuffer<Type> insttypes = new ListBuffer<Type>();
441 /** Instantiated types or UndetVars if under-constrained */
442 ListBuffer<Type> undettypes = new ListBuffer<Type>();
444 for (Type t : undetvars) {
445 UndetVar uv = (UndetVar)t;
446 if (uv.inst.tag == BOT) {
447 restvars.append(uv.qtype);
448 restundet.append(uv);
449 insttypes.append(uv.qtype);
450 undettypes.append(uv);
451 uv.inst = null;
452 } else {
453 insttypes.append(uv.inst);
454 undettypes.append(uv.inst);
455 }
456 }
457 checkWithinBounds(tvars, undettypes.toList(), warn);
459 mt = (MethodType)types.subst(mt, tvars, insttypes.toList());
461 if (!restvars.isEmpty()) {
462 // if there are uninstantiated variables,
463 // quantify result type with them
464 final List<Type> inferredTypes = insttypes.toList();
465 final List<Type> all_tvars = tvars; //this is the wrong tvars
466 final MethodType mt2 = new MethodType(mt.argtypes, null, mt.thrown, syms.methodClass);
467 mt2.restype = new ForAll(restvars.toList(), mt.restype) {
468 @Override
469 public List<Type> getConstraints(TypeVar tv, ConstraintKind ck) {
470 for (Type t : restundet.toList()) {
471 UndetVar uv = (UndetVar)t;
472 if (uv.qtype == tv) {
473 switch (ck) {
474 case EXTENDS: return uv.hibounds.appendList(types.subst(types.getBounds(tv), all_tvars, inferredTypes));
475 case SUPER: return uv.lobounds;
476 case EQUAL: return uv.inst != null ? List.of(uv.inst) : List.<Type>nil();
477 }
478 }
479 }
480 return List.nil();
481 }
483 @Override
484 public Type inst(List<Type> inferred, Types types) throws NoInstanceException {
485 List<Type> formals = types.subst(mt2.argtypes, tvars, inferred);
486 if (!rs.argumentsAcceptable(capturedArgs, formals,
487 allowBoxing, useVarargs, warn)) {
488 // inferred method is not applicable
489 throw invalidInstanceException.setMessage("inferred.do.not.conform.to.params", formals, argtypes);
490 }
491 // check that inferred bounds conform to their bounds
492 checkWithinBounds(all_tvars,
493 types.subst(inferredTypes, tvars, inferred), warn);
494 if (useVarargs) {
495 chk.checkVararg(env.tree.pos(), formals, msym);
496 }
497 return super.inst(inferred, types);
498 }};
499 return mt2;
500 }
501 else if (!rs.argumentsAcceptable(capturedArgs, mt.getParameterTypes(), allowBoxing, useVarargs, warn)) {
502 // inferred method is not applicable
503 throw invalidInstanceException.setMessage("inferred.do.not.conform.to.params", mt.getParameterTypes(), argtypes);
504 }
505 else {
506 // return instantiated version of method type
507 return mt;
508 }
509 }
510 //where
512 /** Try to instantiate argument type `that' to given type `to'.
513 * If this fails, try to insantiate `that' to `to' where
514 * every occurrence of a type variable in `tvars' is replaced
515 * by an unknown type.
516 */
517 private Type instantiateArg(ForAll that,
518 Type to,
519 List<Type> tvars,
520 Warner warn) throws InferenceException {
521 List<Type> targs;
522 try {
523 return instantiateExpr(that, to, warn);
524 } catch (NoInstanceException ex) {
525 Type to1 = to;
526 for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)
527 to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType));
528 return instantiateExpr(that, to1, warn);
529 }
530 }
532 /** check that type parameters are within their bounds.
533 */
534 void checkWithinBounds(List<Type> tvars,
535 List<Type> arguments,
536 Warner warn)
537 throws InvalidInstanceException {
538 for (List<Type> tvs = tvars, args = arguments;
539 tvs.nonEmpty();
540 tvs = tvs.tail, args = args.tail) {
541 if (args.head instanceof UndetVar ||
542 tvars.head.getUpperBound().isErroneous()) continue;
543 List<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);
544 if (!types.isSubtypeUnchecked(args.head, bounds, warn))
545 throw invalidInstanceException
546 .setMessage("inferred.do.not.conform.to.bounds",
547 args.head, bounds);
548 }
549 }
551 /**
552 * Compute a synthetic method type corresponding to the requested polymorphic
553 * method signature. The target return type is computed from the immediately
554 * enclosing scope surrounding the polymorphic-signature call.
555 */
556 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env, Type site,
557 Name name,
558 MethodSymbol spMethod, // sig. poly. method or null if none
559 List<Type> argtypes) {
560 final Type restype;
562 //The return type for a polymorphic signature call is computed from
563 //the enclosing tree E, as follows: if E is a cast, then use the
564 //target type of the cast expression as a return type; if E is an
565 //expression statement, the return type is 'void' - otherwise the
566 //return type is simply 'Object'. A correctness check ensures that
567 //env.next refers to the lexically enclosing environment in which
568 //the polymorphic signature call environment is nested.
570 switch (env.next.tree.getTag()) {
571 case JCTree.TYPECAST:
572 JCTypeCast castTree = (JCTypeCast)env.next.tree;
573 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
574 castTree.clazz.type :
575 syms.objectType;
576 break;
577 case JCTree.EXEC:
578 JCTree.JCExpressionStatement execTree =
579 (JCTree.JCExpressionStatement)env.next.tree;
580 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
581 syms.voidType :
582 syms.objectType;
583 break;
584 default:
585 restype = syms.objectType;
586 }
588 List<Type> paramtypes = Type.map(argtypes, implicitArgType);
589 List<Type> exType = spMethod != null ?
590 spMethod.getThrownTypes() :
591 List.of(syms.throwableType); // make it throw all exceptions
593 MethodType mtype = new MethodType(paramtypes,
594 restype,
595 exType,
596 syms.methodClass);
597 return mtype;
598 }
599 //where
600 Mapping implicitArgType = new Mapping ("implicitArgType") {
601 public Type apply(Type t) {
602 t = types.erasure(t);
603 if (t.tag == BOT)
604 // nulls type as the marker type Null (which has no instances)
605 // infer as java.lang.Void for now
606 t = types.boxedClass(syms.voidType).type;
607 return t;
608 }
609 };
610 }
