001 /*
002 * Copyright 1999-2008 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package com.sun.tools.javac.comp;
027
028 import com.sun.tools.javac.util.*;
029 import com.sun.tools.javac.util.List;
030 import com.sun.tools.javac.code.*;
031 import com.sun.tools.javac.code.Type.*;
032 import com.sun.tools.javac.util.JCDiagnostic;
033
034 import static com.sun.tools.javac.code.TypeTags.*;
035
036 /** Helper class for type parameter inference, used by the attribution phase.
037 *
038 * <p><b>This is NOT part of any API supported by Sun Microsystems. If
039 * you write code that depends on this, you do so at your own risk.
040 * This code and its internal interfaces are subject to change or
041 * deletion without notice.</b>
042 */
043 public class Infer {
044 protected static final Context.Key<Infer> inferKey =
045 new Context.Key<Infer>();
046
047 /** A value for prototypes that admit any type, including polymorphic ones. */
048 public static final Type anyPoly = new Type(NONE, null);
049
050 Symtab syms;
051 Types types;
052 JCDiagnostic.Factory diags;
053
054 public static Infer instance(Context context) {
055 Infer instance = context.get(inferKey);
056 if (instance == null)
057 instance = new Infer(context);
058 return instance;
059 }
060
061 protected Infer(Context context) {
062 context.put(inferKey, this);
063 syms = Symtab.instance(context);
064 types = Types.instance(context);
065 diags = JCDiagnostic.Factory.instance(context);
066 ambiguousNoInstanceException =
067 new NoInstanceException(true, diags);
068 unambiguousNoInstanceException =
069 new NoInstanceException(false, diags);
070 }
071
072 public static class NoInstanceException extends RuntimeException {
073 private static final long serialVersionUID = 0;
074
075 boolean isAmbiguous; // exist several incomparable best instances?
076
077 JCDiagnostic diagnostic;
078 JCDiagnostic.Factory diags;
079
080 NoInstanceException(boolean isAmbiguous, JCDiagnostic.Factory diags) {
081 this.diagnostic = null;
082 this.isAmbiguous = isAmbiguous;
083 this.diags = diags;
084 }
085 NoInstanceException setMessage(String key) {
086 this.diagnostic = diags.fragment(key);
087 return this;
088 }
089 NoInstanceException setMessage(String key, Object arg1) {
090 this.diagnostic = diags.fragment(key, arg1);
091 return this;
092 }
093 NoInstanceException setMessage(String key, Object arg1, Object arg2) {
094 this.diagnostic = diags.fragment(key, arg1, arg2);
095 return this;
096 }
097 NoInstanceException setMessage(String key, Object arg1, Object arg2, Object arg3) {
098 this.diagnostic = diags.fragment(key, arg1, arg2, arg3);
099 return this;
100 }
101 public JCDiagnostic getDiagnostic() {
102 return diagnostic;
103 }
104 }
105 private final NoInstanceException ambiguousNoInstanceException;
106 private final NoInstanceException unambiguousNoInstanceException;
107
108 /***************************************************************************
109 * Auxiliary type values and classes
110 ***************************************************************************/
111
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 };
120
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 };
143
144 /***************************************************************************
145 * Mini/Maximization of UndetVars
146 ***************************************************************************/
147
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 for (List<Type> bs = that.hibounds;
159 bs.nonEmpty() && that.inst == null;
160 bs = bs.tail) {
161 // System.out.println("hibounds = " + that.hibounds);//DEBUG
162 if (isSubClass(bs.head, that.hibounds))
163 that.inst = types.fromUnknownFun.apply(bs.head);
164 }
165 if (that.inst == null) {
166 int classCount = 0, interfaceCount = 0;
167 for (Type t : that.hibounds) {
168 if (t.tag == CLASS) {
169 if (t.isInterface())
170 interfaceCount++;
171 else
172 classCount++;
173 }
174 }
175 if ((that.hibounds.size() == classCount + interfaceCount) && classCount == 1)
176 that.inst = types.makeCompoundType(that.hibounds);
177 }
178 if (that.inst == null || !types.isSubtypeUnchecked(that.inst, that.hibounds, warn))
179 throw ambiguousNoInstanceException
180 .setMessage("no.unique.maximal.instance.exists",
181 that.qtype, that.hibounds);
182 }
183 }
184 }
185 //where
186 private boolean isSubClass(Type t, final List<Type> ts) {
187 t = t.baseType();
188 if (t.tag == TYPEVAR) {
189 List<Type> bounds = types.getBounds((TypeVar)t);
190 for (Type s : ts) {
191 if (!types.isSameType(t, s.baseType())) {
192 for (Type bound : bounds) {
193 if (!isSubClass(bound, List.of(s.baseType())))
194 return false;
195 }
196 }
197 }
198 } else {
199 for (Type s : ts) {
200 if (!t.tsym.isSubClass(s.baseType().tsym, types))
201 return false;
202 }
203 }
204 return true;
205 }
206
207 /** Instantiate undetermined type variable to the lub of all its lower bounds.
208 * Throw a NoInstanceException if this not possible.
209 */
210 void minimizeInst(UndetVar that, Warner warn) throws NoInstanceException {
211 if (that.inst == null) {
212 if (that.lobounds.isEmpty())
213 that.inst = syms.botType;
214 else if (that.lobounds.tail.isEmpty())
215 that.inst = that.lobounds.head.isPrimitive() ? syms.errType : that.lobounds.head;
216 else {
217 that.inst = types.lub(that.lobounds);
218 }
219 if (that.inst == null || that.inst.tag == ERROR)
220 throw ambiguousNoInstanceException
221 .setMessage("no.unique.minimal.instance.exists",
222 that.qtype, that.lobounds);
223 // VGJ: sort of inlined maximizeInst() below. Adding
224 // bounds can cause lobounds that are above hibounds.
225 if (that.hibounds.isEmpty())
226 return;
227 Type hb = null;
228 if (that.hibounds.tail.isEmpty())
229 hb = that.hibounds.head;
230 else for (List<Type> bs = that.hibounds;
231 bs.nonEmpty() && hb == null;
232 bs = bs.tail) {
233 if (isSubClass(bs.head, that.hibounds))
234 hb = types.fromUnknownFun.apply(bs.head);
235 }
236 if (hb == null ||
237 !types.isSubtypeUnchecked(hb, that.hibounds, warn) ||
238 !types.isSubtypeUnchecked(that.inst, hb, warn))
239 throw ambiguousNoInstanceException;
240 }
241 }
242
243 /***************************************************************************
244 * Exported Methods
245 ***************************************************************************/
246
247 /** Try to instantiate expression type `that' to given type `to'.
248 * If a maximal instantiation exists which makes this type
249 * a subtype of type `to', return the instantiated type.
250 * If no instantiation exists, or if several incomparable
251 * best instantiations exist throw a NoInstanceException.
252 */
253 public Type instantiateExpr(ForAll that,
254 Type to,
255 Warner warn) throws NoInstanceException {
256 List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);
257 for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {
258 UndetVar v = (UndetVar) l.head;
259 ListBuffer<Type> hibounds = new ListBuffer<Type>();
260 for (List<Type> l1 = types.getBounds((TypeVar) v.qtype); l1.nonEmpty(); l1 = l1.tail) {
261 if (!l1.head.containsSome(that.tvars)) {
262 hibounds.append(l1.head);
263 }
264 }
265 v.hibounds = hibounds.toList();
266 }
267 Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);
268 if (!types.isSubtype(qtype1, to)) {
269 throw unambiguousNoInstanceException
270 .setMessage("no.conforming.instance.exists",
271 that.tvars, that.qtype, to);
272 }
273 for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail)
274 maximizeInst((UndetVar) l.head, warn);
275 // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG
276
277 // check bounds
278 List<Type> targs = Type.map(undetvars, getInstFun);
279 targs = types.subst(targs, that.tvars, targs);
280 checkWithinBounds(that.tvars, targs, warn);
281
282 return getInstFun.apply(qtype1);
283 }
284
285 /** Instantiate method type `mt' by finding instantiations of
286 * `tvars' so that method can be applied to `argtypes'.
287 */
288 public Type instantiateMethod(List<Type> tvars,
289 MethodType mt,
290 List<Type> argtypes,
291 boolean allowBoxing,
292 boolean useVarargs,
293 Warner warn) throws NoInstanceException {
294 //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
295 List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
296 List<Type> formals = mt.argtypes;
297
298 // instantiate all polymorphic argument types and
299 // set up lower bounds constraints for undetvars
300 Type varargsFormal = useVarargs ? formals.last() : null;
301 while (argtypes.nonEmpty() && formals.head != varargsFormal) {
302 Type ft = formals.head;
303 Type at = argtypes.head.baseType();
304 if (at.tag == FORALL)
305 at = instantiateArg((ForAll) at, ft, tvars, warn);
306 Type sft = types.subst(ft, tvars, undetvars);
307 boolean works = allowBoxing
308 ? types.isConvertible(at, sft, warn)
309 : types.isSubtypeUnchecked(at, sft, warn);
310 if (!works) {
311 throw unambiguousNoInstanceException
312 .setMessage("no.conforming.assignment.exists",
313 tvars, at, ft);
314 }
315 formals = formals.tail;
316 argtypes = argtypes.tail;
317 }
318 if (formals.head != varargsFormal || // not enough args
319 !useVarargs && argtypes.nonEmpty()) { // too many args
320 // argument lists differ in length
321 throw unambiguousNoInstanceException
322 .setMessage("arg.length.mismatch");
323 }
324
325 // for varargs arguments as well
326 if (useVarargs) {
327 Type elt = types.elemtype(varargsFormal);
328 Type sft = types.subst(elt, tvars, undetvars);
329 while (argtypes.nonEmpty()) {
330 Type ft = sft;
331 Type at = argtypes.head.baseType();
332 if (at.tag == FORALL)
333 at = instantiateArg((ForAll) at, ft, tvars, warn);
334 boolean works = types.isConvertible(at, sft, warn);
335 if (!works) {
336 throw unambiguousNoInstanceException
337 .setMessage("no.conforming.assignment.exists",
338 tvars, at, ft);
339 }
340 argtypes = argtypes.tail;
341 }
342 }
343
344 // minimize as yet undetermined type variables
345 for (Type t : undetvars)
346 minimizeInst((UndetVar) t, warn);
347
348 /** Type variables instantiated to bottom */
349 ListBuffer<Type> restvars = new ListBuffer<Type>();
350
351 /** Instantiated types or TypeVars if under-constrained */
352 ListBuffer<Type> insttypes = new ListBuffer<Type>();
353
354 /** Instantiated types or UndetVars if under-constrained */
355 ListBuffer<Type> undettypes = new ListBuffer<Type>();
356
357 for (Type t : undetvars) {
358 UndetVar uv = (UndetVar)t;
359 if (uv.inst.tag == BOT) {
360 restvars.append(uv.qtype);
361 insttypes.append(uv.qtype);
362 undettypes.append(uv);
363 uv.inst = null;
364 } else {
365 insttypes.append(uv.inst);
366 undettypes.append(uv.inst);
367 }
368 }
369 checkWithinBounds(tvars, undettypes.toList(), warn);
370
371 if (!restvars.isEmpty()) {
372 // if there are uninstantiated variables,
373 // quantify result type with them
374 mt = new MethodType(mt.argtypes,
375 new ForAll(restvars.toList(), mt.restype),
376 mt.thrown, syms.methodClass);
377 }
378
379 // return instantiated version of method type
380 return types.subst(mt, tvars, insttypes.toList());
381 }
382 //where
383
384 /** Try to instantiate argument type `that' to given type `to'.
385 * If this fails, try to insantiate `that' to `to' where
386 * every occurrence of a type variable in `tvars' is replaced
387 * by an unknown type.
388 */
389 private Type instantiateArg(ForAll that,
390 Type to,
391 List<Type> tvars,
392 Warner warn) throws NoInstanceException {
393 List<Type> targs;
394 try {
395 return instantiateExpr(that, to, warn);
396 } catch (NoInstanceException ex) {
397 Type to1 = to;
398 for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)
399 to1 = types.subst(to1, List.of(l.head), List.of(syms.unknownType));
400 return instantiateExpr(that, to1, warn);
401 }
402 }
403
404 /** check that type parameters are within their bounds.
405 */
406 private void checkWithinBounds(List<Type> tvars,
407 List<Type> arguments,
408 Warner warn)
409 throws NoInstanceException {
410 for (List<Type> tvs = tvars, args = arguments;
411 tvs.nonEmpty();
412 tvs = tvs.tail, args = args.tail) {
413 if (args.head instanceof UndetVar) continue;
414 List<Type> bounds = types.subst(types.getBounds((TypeVar)tvs.head), tvars, arguments);
415 if (!types.isSubtypeUnchecked(args.head, bounds, warn))
416 throw unambiguousNoInstanceException
417 .setMessage("inferred.do.not.conform.to.bounds",
418 arguments, tvars);
419 }
420 }
421 }