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