001: /*
002: * Copyright 1999-2006 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:
033: import static com.sun.tools.javac.code.Flags.*;
034: import static com.sun.tools.javac.code.Kinds.*;
035: import static com.sun.tools.javac.code.TypeTags.*;
036:
037: /** Helper class for type parameter inference, used by the attribution phase.
038: *
039: * <p><b>This is NOT part of any API supported by Sun Microsystems. If
040: * you write code that depends on this, you do so at your own risk.
041: * This code and its internal interfaces are subject to change or
042: * deletion without notice.</b>
043: */
044: @Version("@(#)Infer.java 1.62 07/05/05")
045: public class Infer {
046: protected static final Context.Key<Infer> inferKey = new Context.Key<Infer>();
047:
048: /** A value for prototypes that admit any type, including polymorphic ones. */
049: public static final Type anyPoly = new Type(NONE, null);
050:
051: Symtab syms;
052: Types types;
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: }
066:
067: public static class NoInstanceException extends RuntimeException {
068: private static final long serialVersionUID = 0;
069:
070: boolean isAmbiguous; // exist several incomparable best instances?
071:
072: JCDiagnostic diagnostic;
073:
074: NoInstanceException(boolean isAmbiguous) {
075: this .diagnostic = null;
076: this .isAmbiguous = isAmbiguous;
077: }
078:
079: NoInstanceException setMessage(String key) {
080: this .diagnostic = JCDiagnostic.fragment(key);
081: return this ;
082: }
083:
084: NoInstanceException setMessage(String key, Object arg1) {
085: this .diagnostic = JCDiagnostic.fragment(key, arg1);
086: return this ;
087: }
088:
089: NoInstanceException setMessage(String key, Object arg1,
090: Object arg2) {
091: this .diagnostic = JCDiagnostic.fragment(key, arg1, arg2);
092: return this ;
093: }
094:
095: NoInstanceException setMessage(String key, Object arg1,
096: Object arg2, Object arg3) {
097: this .diagnostic = JCDiagnostic.fragment(key, arg1, arg2,
098: arg3);
099: return this ;
100: }
101:
102: public JCDiagnostic getDiagnostic() {
103: return diagnostic;
104: }
105: }
106:
107: private final NoInstanceException ambiguousNoInstanceException = new NoInstanceException(
108: true);
109: private final NoInstanceException unambiguousNoInstanceException = new NoInstanceException(
110: false);
111:
112: /***************************************************************************
113: * Auxiliary type values and classes
114: ***************************************************************************/
115:
116: /** A mapping that turns type variables into undetermined type variables.
117: */
118: Mapping fromTypeVarFun = new Mapping("fromTypeVarFun") {
119: public Type apply(Type t) {
120: if (t.tag == TYPEVAR)
121: return new UndetVar(t);
122: else
123: return t.map(this );
124: }
125: };
126:
127: /** A mapping that returns its type argument with every UndetVar replaced
128: * by its `inst' field. Throws a NoInstanceException
129: * if this not possible because an `inst' field is null.
130: */
131: Mapping getInstFun = new Mapping("getInstFun") {
132: public Type apply(Type t) {
133: switch (t.tag) {
134: case UNKNOWN:
135: throw ambiguousNoInstanceException
136: .setMessage("undetermined.type");
137: case UNDETVAR:
138: UndetVar that = (UndetVar) t;
139: if (that.inst == null)
140: throw ambiguousNoInstanceException.setMessage(
141: "type.variable.has.undetermined.type",
142: that.qtype);
143: return apply(that.inst);
144: default:
145: return t.map(this );
146: }
147: }
148: };
149:
150: /***************************************************************************
151: * Mini/Maximization of UndetVars
152: ***************************************************************************/
153:
154: /** Instantiate undetermined type variable to its minimal upper bound.
155: * Throw a NoInstanceException if this not possible.
156: */
157: void maximizeInst(UndetVar that, Warner warn)
158: throws NoInstanceException {
159: if (that.inst == null) {
160: if (that.hibounds.isEmpty())
161: that.inst = syms.objectType;
162: else if (that.hibounds.tail.isEmpty())
163: that.inst = that.hibounds.head;
164: else {
165: for (List<Type> bs = that.hibounds; bs.nonEmpty()
166: && that.inst == null; bs = bs.tail) {
167: // System.out.println("hibounds = " + that.hibounds);//DEBUG
168: if (isSubClass(bs.head, that.hibounds))
169: that.inst = types.fromUnknownFun.apply(bs.head);
170: }
171: if (that.inst == null
172: || !types.isSubtypeUnchecked(that.inst,
173: that.hibounds, warn))
174: throw ambiguousNoInstanceException.setMessage(
175: "no.unique.maximal.instance.exists",
176: that.qtype, that.hibounds);
177: }
178: }
179: }
180:
181: //where
182: private boolean isSubClass(Type t, final List<Type> ts) {
183: t = t.baseType();
184: if (t.tag == TYPEVAR) {
185: List<Type> bounds = types.getBounds((TypeVar) t);
186: for (Type s : ts) {
187: if (!types.isSameType(t, s.baseType())) {
188: for (Type bound : bounds) {
189: if (!isSubClass(bound, List.of(s.baseType())))
190: return false;
191: }
192: }
193: }
194: } else {
195: for (Type s : ts) {
196: if (!t.tsym.isSubClass(s.baseType().tsym, types))
197: return false;
198: }
199: }
200: return true;
201: }
202:
203: /** Instaniate undetermined type variable to the lub of all its lower bounds.
204: * Throw a NoInstanceException if this not possible.
205: */
206: void minimizeInst(UndetVar that, Warner warn)
207: throws NoInstanceException {
208: if (that.inst == null) {
209: if (that.lobounds.isEmpty())
210: that.inst = syms.botType;
211: else if (that.lobounds.tail.isEmpty())
212: that.inst = that.lobounds.head;
213: else {
214: that.inst = types.lub(that.lobounds);
215: if (that.inst == null)
216: throw ambiguousNoInstanceException.setMessage(
217: "no.unique.minimal.instance.exists",
218: that.qtype, that.lobounds);
219: }
220: // VGJ: sort of inlined maximizeInst() below. Adding
221: // bounds can cause lobounds that are above hibounds.
222: if (that.hibounds.isEmpty())
223: return;
224: Type hb = null;
225: if (that.hibounds.tail.isEmpty())
226: hb = that.hibounds.head;
227: else
228: for (List<Type> bs = that.hibounds; bs.nonEmpty()
229: && hb == null; bs = bs.tail) {
230: if (isSubClass(bs.head, that.hibounds))
231: hb = types.fromUnknownFun.apply(bs.head);
232: }
233: if (hb == null
234: || !types.isSubtypeUnchecked(hb, that.hibounds,
235: warn)
236: || !types.isSubtypeUnchecked(that.inst, hb, warn))
237: throw ambiguousNoInstanceException;
238: }
239: }
240:
241: /***************************************************************************
242: * Exported Methods
243: ***************************************************************************/
244:
245: /** Try to instantiate expression type `that' to given type `to'.
246: * If a maximal instantiation exists which makes this type
247: * a subtype of type `to', return the instantiated type.
248: * If no instantiation exists, or if several incomparable
249: * best instantiations exist throw a NoInstanceException.
250: */
251: public Type instantiateExpr(ForAll that, Type to, Warner warn)
252: throws NoInstanceException {
253: List<Type> undetvars = Type.map(that.tvars, fromTypeVarFun);
254: for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail) {
255: UndetVar v = (UndetVar) l.head;
256: ListBuffer<Type> hibounds = new ListBuffer<Type>();
257: for (List<Type> l1 = types.getBounds((TypeVar) v.qtype); l1
258: .nonEmpty(); l1 = l1.tail) {
259: if (!l1.head.containsSome(that.tvars)) {
260: hibounds.append(l1.head);
261: }
262: }
263: v.hibounds = hibounds.toList();
264: }
265: Type qtype1 = types.subst(that.qtype, that.tvars, undetvars);
266: if (!types.isSubtype(qtype1, to)) {
267: throw unambiguousNoInstanceException.setMessage(
268: "no.conforming.instance.exists", that.tvars,
269: that.qtype, to);
270: }
271: for (List<Type> l = undetvars; l.nonEmpty(); l = l.tail)
272: maximizeInst((UndetVar) l.head, warn);
273: // System.out.println(" = " + qtype1.map(getInstFun));//DEBUG
274:
275: // check bounds
276: List<Type> targs = Type.map(undetvars, getInstFun);
277: targs = types.subst(targs, that.tvars, targs);
278: checkWithinBounds(that.tvars, targs, warn);
279:
280: return getInstFun.apply(qtype1);
281: }
282:
283: /** Instantiate method type `mt' by finding instantiations of
284: * `tvars' so that method can be applied to `argtypes'.
285: */
286: public Type instantiateMethod(List<Type> tvars, MethodType mt,
287: List<Type> argtypes, boolean allowBoxing,
288: boolean useVarargs, Warner warn) throws NoInstanceException {
289: //-System.err.println("instantiateMethod(" + tvars + ", " + mt + ", " + argtypes + ")"); //DEBUG
290: List<Type> undetvars = Type.map(tvars, fromTypeVarFun);
291: List<Type> formals = mt.argtypes;
292:
293: // instantiate all polymorphic argument types and
294: // set up lower bounds constraints for undetvars
295: Type varargsFormal = useVarargs ? formals.last() : null;
296: while (argtypes.nonEmpty() && formals.head != varargsFormal) {
297: Type ft = formals.head;
298: Type at = argtypes.head.baseType();
299: if (at.tag == FORALL)
300: at = instantiateArg((ForAll) at, ft, tvars, warn);
301: Type sft = types.subst(ft, tvars, undetvars);
302: boolean works = allowBoxing ? types.isConvertible(at, sft,
303: warn) : types.isSubtypeUnchecked(at, sft, warn);
304: if (!works) {
305: throw unambiguousNoInstanceException.setMessage(
306: "no.conforming.assignment.exists", tvars, at,
307: ft);
308: }
309: formals = formals.tail;
310: argtypes = argtypes.tail;
311: }
312: if (formals.head != varargsFormal || // not enough args
313: !useVarargs && argtypes.nonEmpty()) { // too many args
314: // argument lists differ in length
315: throw unambiguousNoInstanceException
316: .setMessage("arg.length.mismatch");
317: }
318:
319: // for varargs arguments as well
320: if (useVarargs) {
321: Type elt = types.elemtype(varargsFormal);
322: Type sft = types.subst(elt, tvars, undetvars);
323: while (argtypes.nonEmpty()) {
324: Type ft = sft;
325: Type at = argtypes.head.baseType();
326: if (at.tag == FORALL)
327: at = instantiateArg((ForAll) at, ft, tvars, warn);
328: boolean works = types.isConvertible(at, sft, warn);
329: if (!works) {
330: throw unambiguousNoInstanceException.setMessage(
331: "no.conforming.assignment.exists", tvars,
332: at, ft);
333: }
334: argtypes = argtypes.tail;
335: }
336: }
337:
338: // minimize as yet undetermined type variables
339: for (Type t : undetvars)
340: minimizeInst((UndetVar) t, warn);
341:
342: /** Type variables instantiated to bottom */
343: ListBuffer<Type> restvars = new ListBuffer<Type>();
344:
345: /** Instantiated types or TypeVars if under-constrained */
346: ListBuffer<Type> insttypes = new ListBuffer<Type>();
347:
348: /** Instantiated types or UndetVars if under-constrained */
349: ListBuffer<Type> undettypes = new ListBuffer<Type>();
350:
351: for (Type t : undetvars) {
352: UndetVar uv = (UndetVar) t;
353: if (uv.inst.tag == BOT) {
354: restvars.append(uv.qtype);
355: insttypes.append(uv.qtype);
356: undettypes.append(uv);
357: uv.inst = null;
358: } else {
359: insttypes.append(uv.inst);
360: undettypes.append(uv.inst);
361: }
362: }
363: checkWithinBounds(tvars, undettypes.toList(), warn);
364:
365: if (!restvars.isEmpty()) {
366: // if there are uninstantiated variables,
367: // quantify result type with them
368: mt = new MethodType(mt.argtypes, new ForAll(restvars
369: .toList(), mt.restype), mt.thrown, syms.methodClass);
370: }
371:
372: // return instantiated version of method type
373: return types.subst(mt, tvars, insttypes.toList());
374: }
375:
376: //where
377:
378: /** Try to instantiate argument type `that' to given type `to'.
379: * If this fails, try to insantiate `that' to `to' where
380: * every occurrence of a type variable in `tvars' is replaced
381: * by an unknown type.
382: */
383: private Type instantiateArg(ForAll that, Type to, List<Type> tvars,
384: Warner warn) throws NoInstanceException {
385: List<Type> targs;
386: try {
387: return instantiateExpr(that, to, warn);
388: } catch (NoInstanceException ex) {
389: Type to1 = to;
390: for (List<Type> l = tvars; l.nonEmpty(); l = l.tail)
391: to1 = types.subst(to1, List.of(l.head), List
392: .of(syms.unknownType));
393: return instantiateExpr(that, to1, warn);
394: }
395: }
396:
397: /** check that type parameters are within their bounds.
398: */
399: private void checkWithinBounds(List<Type> tvars,
400: List<Type> arguments, Warner warn)
401: throws NoInstanceException {
402: for (List<Type> tvs = tvars, args = arguments; tvs.nonEmpty(); tvs = tvs.tail, args = args.tail) {
403: if (args.head instanceof UndetVar)
404: continue;
405: List<Type> bounds = types.subst(types
406: .getBounds((TypeVar) tvs.head), tvars, arguments);
407: if (!types.isSubtypeUnchecked(args.head, bounds, warn))
408: throw unambiguousNoInstanceException.setMessage(
409: "inferred.do.not.conform.to.bounds", arguments,
410: tvars);
411: }
412: }
413: }
|