Mercurial > jdk8-mips64-public > langtools / file revision
src/share/classes/com/sun/tools/javac/comp/Infer.java@5a43b245aed1
src/share/classes/com/sun/tools/javac/comp/Infer.java
Fri, 28 Jan 2011 12:03:49 +0000
- author
- mcimadamore
- date
- Fri, 28 Jan 2011 12:03:49 +0000
- changeset 845
- 5a43b245aed1
- parent 832
- 57e3b9bc7fb8
- child 895
- 9286a5d1fae3
- permissions
- -rw-r--r--
6313164: javac generates code that fails byte code verification for the varargs feature
Summary: method applicability check should fail if formal varargs element type is not accessible
Reviewed-by: jjg
1 /*
2 * Copyright (c) 1999, 2011, 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 //note: if applicability check is triggered by most specific test,
411 //the last argument of a varargs is _not_ an array type (see JLS 15.12.2.5)
412 Type elemType = types.elemtypeOrType(varargsFormal);
413 Type elemUndet = types.subst(elemType, tvars, undetvars);
414 while (actuals.nonEmpty()) {
415 Type actual = actuals.head.baseType();
416 Type actualNoCapture = actualsNoCapture.head.baseType();
417 if (actual.tag == FORALL)
418 actual = instantiateArg((ForAll)actual, elemType, tvars, warn);
419 boolean works = types.isConvertible(actual, elemUndet, warn);
420 if (!works) {
421 throw unambiguousNoInstanceException
422 .setMessage("infer.no.conforming.assignment.exists",
423 tvars, actualNoCapture, elemType);
424 }
425 actuals = actuals.tail;
426 actualsNoCapture = actualsNoCapture.tail;
427 }
428 }
430 // minimize as yet undetermined type variables
431 for (Type t : undetvars)
432 minimizeInst((UndetVar) t, warn);
434 /** Type variables instantiated to bottom */
435 ListBuffer<Type> restvars = new ListBuffer<Type>();
437 /** Undet vars instantiated to bottom */
438 final ListBuffer<Type> restundet = new ListBuffer<Type>();
440 /** Instantiated types or TypeVars if under-constrained */
441 ListBuffer<Type> insttypes = new ListBuffer<Type>();
443 /** Instantiated types or UndetVars if under-constrained */
444 ListBuffer<Type> undettypes = new ListBuffer<Type>();
446 for (Type t : undetvars) {
447 UndetVar uv = (UndetVar)t;
448 if (uv.inst.tag == BOT) {
449 restvars.append(uv.qtype);
450 restundet.append(uv);
451 insttypes.append(uv.qtype);
452 undettypes.append(uv);
453 uv.inst = null;
454 } else {
455 insttypes.append(uv.inst);
456 undettypes.append(uv.inst);
457 }
458 }
459 checkWithinBounds(tvars, undettypes.toList(), warn);
461 mt = (MethodType)types.subst(mt, tvars, insttypes.toList());
463 if (!restvars.isEmpty()) {
464 // if there are uninstantiated variables,
465 // quantify result type with them
466 final List<Type> inferredTypes = insttypes.toList();
467 final List<Type> all_tvars = tvars; //this is the wrong tvars
468 final MethodType mt2 = new MethodType(mt.argtypes, null, mt.thrown, syms.methodClass);
469 mt2.restype = new ForAll(restvars.toList(), mt.restype) {
470 @Override
471 public List<Type> getConstraints(TypeVar tv, ConstraintKind ck) {
472 for (Type t : restundet.toList()) {
473 UndetVar uv = (UndetVar)t;
474 if (uv.qtype == tv) {
475 switch (ck) {
476 case EXTENDS: return uv.hibounds.appendList(types.subst(types.getBounds(tv), all_tvars, inferredTypes));
477 case SUPER: return uv.lobounds;
478 case EQUAL: return uv.inst != null ? List.of(uv.inst) : List.<Type>nil();
479 }
480 }
481 }
482 return List.nil();
483 }
485 @Override
486 public Type inst(List<Type> inferred, Types types) throws NoInstanceException {
487 List<Type> formals = types.subst(mt2.argtypes, tvars, inferred);
488 // check that actuals conform to inferred formals
489 checkArgumentsAcceptable(env, capturedArgs, formals, allowBoxing, useVarargs, warn);
490 // check that inferred bounds conform to their bounds
491 checkWithinBounds(all_tvars,
492 types.subst(inferredTypes, tvars, inferred), warn);
493 if (useVarargs) {
494 chk.checkVararg(env.tree.pos(), formals, msym);
495 }
496 return super.inst(inferred, types);
497 }};
498 return mt2;
499 }
500 else {
501 // check that actuals conform to inferred formals
502 checkArgumentsAcceptable(env, capturedArgs, mt.getParameterTypes(), allowBoxing, useVarargs, warn);
503 // return instantiated version of method type
504 return mt;
505 }
506 }
507 //where
509 private void checkArgumentsAcceptable(Env<AttrContext> env, List<Type> actuals, List<Type> formals,
510 boolean allowBoxing, boolean useVarargs, Warner warn) {
511 try {
512 rs.checkRawArgumentsAcceptable(env, actuals, formals,
513 allowBoxing, useVarargs, warn);
514 }
515 catch (Resolve.InapplicableMethodException ex) {
516 // inferred method is not applicable
517 throw invalidInstanceException.setMessage(ex.getDiagnostic());
518 }
519 }
521 /** Try to instantiate argument type `that' to given type `to'.
522 * If this fails, try to insantiate `that' to `to' where
523 * every occurrence of a type variable in `tvars' is replaced
524 * by an unknown type.
525 */
526 private Type instantiateArg(ForAll that,
527 Type to,
528 List<Type> tvars,
529 Warner warn) throws InferenceException {
530 List<Type> targs;
531 try {
532 return instantiateExpr(that, to, warn);
533 } catch (NoInstanceException ex) {
534 Type to1 = to;
535 for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)
536 to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType));
537 return instantiateExpr(that, to1, warn);
538 }
539 }
541 /** check that type parameters are within their bounds.
542 */
543 void checkWithinBounds(List<Type> tvars,
544 List<Type> arguments,
545 Warner warn)
546 throws InvalidInstanceException {
547 for (List<Type> tvs = tvars, args = arguments;
548 tvs.nonEmpty();
549 tvs = tvs.tail, args = args.tail) {
550 if (args.head instanceof UndetVar ||
551 tvars.head.getUpperBound().isErroneous()) continue;
552 List<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);
553 if (!types.isSubtypeUnchecked(args.head, bounds, warn))
554 throw invalidInstanceException
555 .setMessage("inferred.do.not.conform.to.bounds",
556 args.head, bounds);
557 }
558 }
560 /**
561 * Compute a synthetic method type corresponding to the requested polymorphic
562 * method signature. The target return type is computed from the immediately
563 * enclosing scope surrounding the polymorphic-signature call.
564 */
565 Type instantiatePolymorphicSignatureInstance(Env<AttrContext> env, Type site,
566 Name name,
567 MethodSymbol spMethod, // sig. poly. method or null if none
568 List<Type> argtypes) {
569 final Type restype;
571 //The return type for a polymorphic signature call is computed from
572 //the enclosing tree E, as follows: if E is a cast, then use the
573 //target type of the cast expression as a return type; if E is an
574 //expression statement, the return type is 'void' - otherwise the
575 //return type is simply 'Object'. A correctness check ensures that
576 //env.next refers to the lexically enclosing environment in which
577 //the polymorphic signature call environment is nested.
579 switch (env.next.tree.getTag()) {
580 case JCTree.TYPECAST:
581 JCTypeCast castTree = (JCTypeCast)env.next.tree;
582 restype = (TreeInfo.skipParens(castTree.expr) == env.tree) ?
583 castTree.clazz.type :
584 syms.objectType;
585 break;
586 case JCTree.EXEC:
587 JCTree.JCExpressionStatement execTree =
588 (JCTree.JCExpressionStatement)env.next.tree;
589 restype = (TreeInfo.skipParens(execTree.expr) == env.tree) ?
590 syms.voidType :
591 syms.objectType;
592 break;
593 default:
594 restype = syms.objectType;
595 }
597 List<Type> paramtypes = Type.map(argtypes, implicitArgType);
598 List<Type> exType = spMethod != null ?
599 spMethod.getThrownTypes() :
600 List.of(syms.throwableType); // make it throw all exceptions
602 MethodType mtype = new MethodType(paramtypes,
603 restype,
604 exType,
605 syms.methodClass);
606 return mtype;
607 }
608 //where
609 Mapping implicitArgType = new Mapping ("implicitArgType") {
610 public Type apply(Type t) {
611 t = types.erasure(t);
612 if (t.tag == BOT)
613 // nulls type as the marker type Null (which has no instances)
614 // infer as java.lang.Void for now
615 t = types.boxedClass(syms.voidType).type;
616 return t;
617 }
618 };
619 }
