Tue, 16 Jun 2009 10:46:16 +0100
6835428: regression: return-type inference rejects valid code
Summary: Redundant subtyping test during type-inference ends up in rejecting legal code
Reviewed-by: jjg
1 /*
2 * Copyright 1999-2009 Sun Microsystems, Inc. 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. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
26 package com.sun.tools.javac.comp;
28 import com.sun.tools.javac.util.*;
29 import com.sun.tools.javac.util.List;
30 import com.sun.tools.javac.code.*;
31 import com.sun.tools.javac.code.Type.*;
32 import com.sun.tools.javac.util.JCDiagnostic;
34 import static com.sun.tools.javac.code.TypeTags.*;
36 /** Helper class for type parameter inference, used by the attribution phase.
37 *
38 * <p><b>This is NOT part of any API supported by Sun Microsystems. If
39 * you write code that depends on this, you do so at your own risk.
40 * This code and its internal interfaces are subject to change or
41 * deletion without notice.</b>
42 */
43 public class Infer {
44 protected static final Context.Key<Infer> inferKey =
45 new Context.Key<Infer>();
47 /** A value for prototypes that admit any type, including polymorphic ones. */
48 public static final Type anyPoly = new Type(NONE, null);
50 Symtab syms;
51 Types types;
52 JCDiagnostic.Factory diags;
54 public static Infer instance(Context context) {
55 Infer instance = context.get(inferKey);
56 if (instance == null)
57 instance = new Infer(context);
58 return instance;
59 }
61 protected Infer(Context context) {
62 context.put(inferKey, this);
63 syms = Symtab.instance(context);
64 types = Types.instance(context);
65 diags = JCDiagnostic.Factory.instance(context);
66 ambiguousNoInstanceException =
67 new NoInstanceException(true, diags);
68 unambiguousNoInstanceException =
69 new NoInstanceException(false, diags);
70 }
72 public static class NoInstanceException extends RuntimeException {
73 private static final long serialVersionUID = 0;
75 boolean isAmbiguous; // exist several incomparable best instances?
77 JCDiagnostic diagnostic;
78 JCDiagnostic.Factory diags;
80 NoInstanceException(boolean isAmbiguous, JCDiagnostic.Factory diags) {
81 this.diagnostic = null;
82 this.isAmbiguous = isAmbiguous;
83 this.diags = diags;
84 }
85 NoInstanceException setMessage(String key) {
86 this.diagnostic = diags.fragment(key);
87 return this;
88 }
89 NoInstanceException setMessage(String key, Object arg1) {
90 this.diagnostic = diags.fragment(key, arg1);
91 return this;
92 }
93 NoInstanceException setMessage(String key, Object arg1, Object arg2) {
94 this.diagnostic = diags.fragment(key, arg1, arg2);
95 return this;
96 }
97 NoInstanceException setMessage(String key, Object arg1, Object arg2, Object arg3) {
98 this.diagnostic = diags.fragment(key, arg1, arg2, arg3);
99 return this;
100 }
101 public JCDiagnostic getDiagnostic() {
102 return diagnostic;
103 }
104 }
105 private final NoInstanceException ambiguousNoInstanceException;
106 private final NoInstanceException unambiguousNoInstanceException;
108 /***************************************************************************
109 * Auxiliary type values and classes
110 ***************************************************************************/
112 /** A mapping that turns type variables into undetermined type variables.
113 */
114 Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
115 public Type apply(Type t) {
116 if (t.tag == TYPEVAR) return new UndetVar(t);
117 else return t.map(this);
118 }
119 };
121 /** A mapping that returns its type argument with every UndetVar replaced
122 * by its `inst' field. Throws a NoInstanceException
123 * if this not possible because an `inst' field is null.
124 */
125 Mapping getInstFun = new Mapping("getInstFun") {
126 public Type apply(Type t) {
127 switch (t.tag) {
128 case UNKNOWN:
129 throw ambiguousNoInstanceException
130 .setMessage("undetermined.type");
131 case UNDETVAR:
132 UndetVar that = (UndetVar) t;
133 if (that.inst == null)
134 throw ambiguousNoInstanceException
135 .setMessage("type.variable.has.undetermined.type",
136 that.qtype);
137 return apply(that.inst);
138 default:
139 return t.map(this);
140 }
141 }
142 };
144 /***************************************************************************
145 * Mini/Maximization of UndetVars
146 ***************************************************************************/
148 /** Instantiate undetermined type variable to its minimal upper bound.
149 * Throw a NoInstanceException if this not possible.
150 */
151 void maximizeInst(UndetVar that, Warner warn) throws NoInstanceException {
152 if (that.inst == null) {
153 if (that.hibounds.isEmpty())
154 that.inst = syms.objectType;
155 else if (that.hibounds.tail.isEmpty())
156 that.inst = that.hibounds.head;
157 else
158 that.inst = types.glb(that.hibounds);
159 }
160 if (that.inst == null ||
161 that.inst.isErroneous())
162 throw ambiguousNoInstanceException
163 .setMessage("no.unique.maximal.instance.exists",
164 that.qtype, that.hibounds);
165 }
166 //where
167 private boolean isSubClass(Type t, final List<Type> ts) {
168 t = t.baseType();
169 if (t.tag == TYPEVAR) {
170 List<Type> bounds = types.getBounds((TypeVar)t);
171 for (Type s : ts) {
172 if (!types.isSameType(t, s.baseType())) {
173 for (Type bound : bounds) {
174 if (!isSubClass(bound, List.of(s.baseType())))
175 return false;
176 }
177 }
178 }
179 } else {
180 for (Type s : ts) {
181 if (!t.tsym.isSubClass(s.baseType().tsym, types))
182 return false;
183 }
184 }
185 return true;
186 }
188 /** Instantiate undetermined type variable to the lub of all its lower bounds.
189 * Throw a NoInstanceException if this not possible.
190 */
191 void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException {
192 if (that.inst == null) {
193 if (that.lobounds.isEmpty())
194 that.inst = syms.botType;
195 else if (that.lobounds.tail.isEmpty())
196 that.inst = that.lobounds.head.isPrimitive() ? syms.errType : that.lobounds.head;
197 else {
198 that.inst = types.lub(that.lobounds);
199 }
200 if (that.inst == null || that.inst.tag == ERROR)
201 throw ambiguousNoInstanceException
202 .setMessage("no.unique.minimal.instance.exists",
203 that.qtype, that.lobounds);
204 // VGJ: sort of inlined maximizeInst() below. Adding
205 // bounds can cause lobounds that are above hibounds.
206 if (that.hibounds.isEmpty())
207 return;
208 Type hb = null;
209 if (that.hibounds.tail.isEmpty())
210 hb = that.hibounds.head;
211 else for (List<Type> bs = that.hibounds;
212 bs.nonEmpty() && hb == null;
213 bs = bs.tail) {
214 if (isSubClass(bs.head, that.hibounds))
215 hb = types.fromUnknownFun.apply(bs.head);
216 }
217 if (hb == null ||
218 !types.isSubtypeUnchecked(hb, that.hibounds, warn) ||
219 !types.isSubtypeUnchecked(that.inst, hb, warn))
220 throw ambiguousNoInstanceException;
221 }
222 }
224 /***************************************************************************
225 * Exported Methods
226 ***************************************************************************/
228 /** Try to instantiate expression type `that' to given type `to'.
229 * If a maximal instantiation exists which makes this type
230 * a subtype of type `to', return the instantiated type.
231 * If no instantiation exists, or if several incomparable
232 * best instantiations exist throw a NoInstanceException.
233 */
234 public Type instantiateExpr(ForAll that,
235 Type to,
236 Warner warn) throws NoInstanceException {
237 List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);
238 for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {
239 UndetVar v = (UndetVar) l.head;
240 ListBuffer<Type> hibounds = new ListBuffer<Type>();
241 for (List<Type> l1 = types.getBounds((TypeVar) v.qtype); l1.nonEmpty(); l1 = l1.tail) {
242 if (!l1.head.containsSome(that.tvars)) {
243 hibounds.append(l1.head);
244 }
245 }
246 v.hibounds = hibounds.toList();
247 }
248 Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);
249 if (!types.isSubtype(qtype1, to)) {
250 throw unambiguousNoInstanceException
251 .setMessage("no.conforming.instance.exists",
252 that.tvars, that.qtype, to);
253 }
254 for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail)
255 maximizeInst((UndetVar) l.head, warn);
256 // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG
258 // check bounds
259 List<Type> targs = Type.map(undetvars, getInstFun);
260 targs = types.subst(targs, that.tvars, targs);
261 checkWithinBounds(that.tvars, targs, warn);
263 return getInstFun.apply(qtype1);
264 }
266 /** Instantiate method type `mt' by finding instantiations of
267 * `tvars' so that method can be applied to `argtypes'.
268 */
269 public Type instantiateMethod(List<Type> tvars,
270 MethodType mt,
271 List<Type> argtypes,
272 boolean allowBoxing,
273 boolean useVarargs,
274 Warner warn) throws NoInstanceException {
275 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
276 List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
277 List<Type> formals = mt.argtypes;
279 // instantiate all polymorphic argument types and
280 // set up lower bounds constraints for undetvars
281 Type varargsFormal = useVarargs ? formals.last() : null;
282 while (argtypes.nonEmpty() && formals.head != varargsFormal) {
283 Type ft = formals.head;
284 Type at = argtypes.head.baseType();
285 if (at.tag == FORALL)
286 at = instantiateArg((ForAll) at, ft, tvars, warn);
287 Type sft = types.subst(ft, tvars, undetvars);
288 boolean works = allowBoxing
289 ? types.isConvertible(at, sft, warn)
290 : types.isSubtypeUnchecked(at, sft, warn);
291 if (!works) {
292 throw unambiguousNoInstanceException
293 .setMessage("no.conforming.assignment.exists",
294 tvars, at, ft);
295 }
296 formals = formals.tail;
297 argtypes = argtypes.tail;
298 }
299 if (formals.head != varargsFormal || // not enough args
300 !useVarargs && argtypes.nonEmpty()) { // too many args
301 // argument lists differ in length
302 throw unambiguousNoInstanceException
303 .setMessage("arg.length.mismatch");
304 }
306 // for varargs arguments as well
307 if (useVarargs) {
308 Type elt = types.elemtype(varargsFormal);
309 Type sft = types.subst(elt, tvars, undetvars);
310 while (argtypes.nonEmpty()) {
311 Type ft = sft;
312 Type at = argtypes.head.baseType();
313 if (at.tag == FORALL)
314 at = instantiateArg((ForAll) at, ft, tvars, warn);
315 boolean works = types.isConvertible(at, sft, warn);
316 if (!works) {
317 throw unambiguousNoInstanceException
318 .setMessage("no.conforming.assignment.exists",
319 tvars, at, ft);
320 }
321 argtypes = argtypes.tail;
322 }
323 }
325 // minimize as yet undetermined type variables
326 for (Type t : undetvars)
327 minimizeInst((UndetVar) t, warn);
329 /** Type variables instantiated to bottom */
330 ListBuffer<Type> restvars = 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 insttypes.append(uv.qtype);
343 undettypes.append(uv);
344 uv.inst = null;
345 } else {
346 insttypes.append(uv.inst);
347 undettypes.append(uv.inst);
348 }
349 }
350 checkWithinBounds(tvars, undettypes.toList(), warn);
352 if (!restvars.isEmpty()) {
353 // if there are uninstantiated variables,
354 // quantify result type with them
355 mt = new MethodType(mt.argtypes,
356 new ForAll(restvars.toList(), mt.restype),
357 mt.thrown, syms.methodClass);
358 }
360 // return instantiated version of method type
361 return types.subst(mt, tvars, insttypes.toList());
362 }
363 //where
365 /** Try to instantiate argument type `that' to given type `to'.
366 * If this fails, try to insantiate `that' to `to' where
367 * every occurrence of a type variable in `tvars' is replaced
368 * by an unknown type.
369 */
370 private Type instantiateArg(ForAll that,
371 Type to,
372 List<Type> tvars,
373 Warner warn) throws NoInstanceException {
374 List<Type> targs;
375 try {
376 return instantiateExpr(that, to, warn);
377 } catch (NoInstanceException ex) {
378 Type to1 = to;
379 for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)
380 to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType));
381 return instantiateExpr(that, to1, warn);
382 }
383 }
385 /** check that type parameters are within their bounds.
386 */
387 private void checkWithinBounds(List<Type> tvars,
388 List<Type> arguments,
389 Warner warn)
390 throws NoInstanceException {
391 for (List<Type> tvs = tvars, args = arguments;
392 tvs.nonEmpty();
393 tvs = tvs.tail, args = args.tail) {
394 if (args.head instanceof UndetVar) continue;
395 List<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);
396 if (!types.isSubtypeUnchecked(args.head, bounds, warn))
397 throw unambiguousNoInstanceException
398 .setMessage("inferred.do.not.conform.to.bounds",
399 arguments, tvars);
400 }
401 }
402 }