001: /**************************************************************************/
002: /* N I C E */
003: /* A high-level object-oriented research language */
004: /* (c) Daniel Bonniot 2004 */
005: /* */
006: /* This program is free software; you can redistribute it and/or modify */
007: /* it under the terms of the GNU General Public License as published by */
008: /* the Free Software Foundation; either version 2 of the License, or */
009: /* (at your option) any later version. */
010: /* */
011: /**************************************************************************/package nice.tools.typing;
012:
013: /**
014: Utilities for Nice types.
015:
016: @author Daniel Bonniot (bonniots@users.sf.net)
017: */
018:
019: import mlsub.typing.*;
020:
021: public final class Types {
022: /****************************************************************
023: * Predicates
024: ****************************************************************/
025:
026: public static boolean isVoid(mlsub.typing.Monotype m) {
027: return equivalent(m).head() == PrimitiveType.voidTC;
028: }
029:
030: public static boolean isVoid(mlsub.typing.Polytype t) {
031: return isVoid(t.getMonotype());
032: }
033:
034: public static boolean isPrimitive(TypeConstructor tc) {
035: return nice.tools.code.Types.javaType(tc) instanceof gnu.bytecode.PrimType;
036: }
037:
038: public static boolean isPrimitive(Monotype t) {
039: return nice.tools.code.Types.javaType(t) instanceof gnu.bytecode.PrimType;
040: }
041:
042: public static boolean isPrimitive(Polytype t) {
043: return nice.tools.code.Types.javaType(t) instanceof gnu.bytecode.PrimType;
044: }
045:
046: public static boolean isMaybe(Monotype m) {
047: // This is prob. laxist, since getTC() might be different but equivalent to maybeTC (?)
048: return (m instanceof MonotypeConstructor)
049: && ((MonotypeConstructor) m).getTC() == PrimitiveType.maybeTC;
050: }
051:
052: public static boolean isSure(Monotype m) {
053: // see comment by isMaybe (e?)
054: return (m instanceof MonotypeConstructor)
055: && ((MonotypeConstructor) m).getTC() == PrimitiveType.sureTC;
056: }
057:
058: public static boolean isDispatchable(Monotype m) {
059: // Functional types are not dispatchable
060: if (parameters(m) != null)
061: return false;
062:
063: return !isPrimitive(m);
064: }
065:
066: /****************************************************************
067: * Handling of option types
068: ****************************************************************/
069:
070: public static Monotype equivalent(Monotype m) {
071: return rawType(m).equivalent();
072: }
073:
074: public static void setMarkedKind(Monotype m) {
075: m.setKind(NullnessKind.instance);
076: }
077:
078: public static void makeMarkedType(MonotypeVar m) {
079: m.setPersistentKind(NullnessKind.instance);
080: }
081:
082: /** return the type with nullness markers removed */
083: public static Monotype rawType(Monotype m) {
084: m = m.equivalent();
085: if (m.getKind() != NullnessKind.instance
086: || m == UnknownMonotype.instance)
087: return m;
088:
089: return ((MonotypeConstructor) m).getTP()[0];
090: }
091:
092: /** return the type with nullness markers removed */
093: public static Monotype rawType(MonotypeConstructor mc) {
094: return mc.getTP()[0];
095: }
096:
097: public static mlsub.typing.Monotype sureMonotype(
098: mlsub.typing.Monotype type) {
099: return new mlsub.typing.MonotypeConstructor(
100: PrimitiveType.sureTC,
101: new mlsub.typing.Monotype[] { type });
102: }
103:
104: public static mlsub.typing.Monotype maybeMonotype(
105: mlsub.typing.Monotype type) {
106: return new mlsub.typing.MonotypeConstructor(
107: PrimitiveType.maybeTC,
108: new mlsub.typing.Monotype[] { type });
109: }
110:
111: /****************************************************************
112: * Functional types
113: ****************************************************************/
114:
115: /** @return the domain of a functional monotype with nullness marker */
116: public static Monotype[] parameters(Monotype type) {
117: return rawType(type).domain();
118: }
119:
120: /** @return the domain of a functional polytype with nullness marker */
121: public static Monotype[] parameters(Polytype type) {
122: return rawType(type.getMonotype()).domain();
123: }
124:
125: /** @return the codomain of a functional polytype with nullness marker */
126: public static Monotype result(Polytype type) {
127: return ((FunType) rawType(type.getMonotype())).codomain();
128: }
129:
130: /** @return the <code>rank</code>th type parameter of this type, or null. */
131: public static Monotype getTypeParameter(Polytype type, int rank) {
132: // This can only help
133: type.simplify();
134:
135: return getTypeParameter(type.getMonotype(), rank);
136: }
137:
138: /**
139: Transforms \forall T:K.U into \forall T:K.sure<U>
140: */
141: public static Polytype addSure(Polytype type) {
142: return new Polytype(type.getConstraint(), Types
143: .sureMonotype(type.getMonotype()));
144: }
145:
146: /****************************************************************
147: * Constructor
148: ****************************************************************/
149:
150: public static TypeConstructor constructor(Monotype type) {
151: return equivalent(type).head();
152: }
153:
154: /**
155: Return a concrete type constructor that represents as closely as
156: possible the given type.
157:
158: The constraint that introduces type variables occuring in the type must be
159: entered in the context before calling this method.
160: */
161: public static TypeConstructor concreteConstructor(Monotype type) {
162: TypeConstructor res = constructor(type);
163:
164: if (res == null || res.isConcrete())
165: return res;
166:
167: return Typing.lowestInstance(res);
168: }
169:
170: public static Monotype zeroArgMonotype(TypeConstructor tc)
171: throws BadSizeEx {
172: // Handle 'Class' as 'Class<?>'
173: if (tc == PrimitiveType.classTC)
174: return new MonotypeConstructor(
175: tc,
176: new mlsub.typing.Monotype[] { UnknownMonotype.instance });
177:
178: return new MonotypeConstructor(tc, null);
179: }
180:
181: public static Monotype unknownArgsMonotype(TypeConstructor tc)
182: throws BadSizeEx {
183: if (tc.variance == null || tc.arity() == 0)
184: return new MonotypeConstructor(tc, null);
185:
186: mlsub.typing.Monotype[] args = new mlsub.typing.Monotype[tc
187: .arity()];
188: for (int i = 0; i < tc.arity(); i++)
189: args[i] = UnknownMonotype.instance;
190:
191: return new MonotypeConstructor(tc, args);
192: }
193:
194: /****************************************************************
195: * Type parameters
196: ****************************************************************/
197:
198: /** @return the <code>rank</code>th type parameter of this type, or null. */
199: public static Monotype getTypeParameter(Monotype type, int rank) {
200: // get rid of the nullness part
201: type = rawType(type);
202:
203: if (!(type instanceof MonotypeConstructor))
204: return null;
205:
206: Monotype[] parameters = ((MonotypeConstructor) type).getTP();
207:
208: if (parameters == null || parameters.length <= rank)
209: return null;
210: else
211: return parameters[rank];
212: }
213:
214: /****************************************************************
215: * Domains
216: ****************************************************************/
217:
218: public static Domain domain(Polytype t) {
219: // remove nullness marker
220: Monotype[] m = parameters(t.getMonotype());
221:
222: return new Domain(t.getConstraint(), m);
223: }
224:
225: /****************************************************************
226: * Covariant specialization
227: ****************************************************************/
228:
229: /**
230: @returns true if the spec type is a covariant specialization of origin,
231: false if the return type is not a subtype of the original subtype
232: */
233: public static boolean covariantSpecialization(Polytype spec,
234: Polytype origin) {
235: boolean entered = false;
236:
237: if (Constraint.hasBinders(spec.getConstraint())
238: || Constraint.hasBinders(origin.getConstraint())) {
239: entered = true;
240: Typing.enter();
241: }
242:
243: try {
244:
245: try {
246: if (entered) {
247: Polytype clonedSpec = spec.cloneType();
248:
249: Constraint.enter(origin.getConstraint());
250: Constraint.enter(clonedSpec.getConstraint());
251:
252: // For all argument types ...
253: Monotype[] args = MonotypeVar
254: .news(parameters(origin).length);
255: Typing.introduce(args);
256:
257: // ... that can be used for both methods ...
258: Typing.leq(args, parameters(origin));
259: Typing.leq(args, parameters(clonedSpec));
260:
261: Typing.implies();
262:
263: // ... apply those args to the 'specialized' method ...
264: Constraint.enter(spec.getConstraint());
265: Typing.leq(args, parameters(spec));
266: }
267:
268: // ... and check that the result is indeed more precise.
269: Typing.leq(result(spec), result(origin));
270: } finally {
271: if (entered)
272: Typing.leave();
273: }
274: } catch (TypingEx ex) {
275: return false;
276: }
277:
278: // OK, spec is a covariant specialization
279: return true;
280: }
281:
282: /**
283: @returns true if functional types t1 and t2 have a partly common domain.
284: that is, there exists some types that belong to both domains.
285: */
286: public static boolean domainsIntersect(Polytype t1, Polytype t2,
287: boolean dispatchable) {
288: Typing.enter();
289:
290: try {
291:
292: try {
293:
294: Constraint.enter(t1.getConstraint());
295: Constraint.enter(t2.getConstraint());
296:
297: // There exists argument types ...
298: Monotype[] args = MonotypeVar
299: .news(parameters(t2).length);
300: Typing.introduce(args);
301:
302: // ... that can be used for both methods ...
303: Typing.leq(args, parameters(t1), dispatchable);
304: Typing.leq(args, parameters(t2), dispatchable);
305: } finally {
306: Typing.leave();
307: }
308: } catch (TypingEx ex) {
309: return false;
310: }
311:
312: // OK, there is an intersection
313: return true;
314: }
315:
316: /**
317: @returns true if the spec type specializes type parameters of the original
318: type (which can not be checked at runtime during dispatch, and therefore
319: should not count as overriding).
320: */
321: public static boolean typeParameterDispatch(Polytype spec,
322: Polytype origin) {
323: Monotype[] originalParams = parameters(origin);
324:
325: if (originalParams.length == 0)
326: return false;
327:
328: Typing.enter();
329: try {
330:
331: try {
332: Polytype clonedSpec = spec.cloneType();
333:
334: Constraint.enter(origin.getConstraint());
335: Constraint.enter(clonedSpec.getConstraint());
336:
337: // For all argument types ...
338: Monotype[] args = MonotypeVar
339: .news(originalParams.length);
340: Typing.introduce(args);
341:
342: // ... that can be used for the first method ...
343: Typing.leq(args, originalParams);
344:
345: // ... and that will be dispatched to the specialized method ...
346: Typing.leqHead(args, parameters(clonedSpec));
347:
348: Typing.implies();
349:
350: // ... check that those args fit in the 'specialized' method ...
351: Constraint.enter(spec.getConstraint());
352: Typing.leq(args, parameters(spec));
353: } finally {
354: Typing.leave();
355: }
356: } catch (TypingEx ex) {
357: return true;
358: }
359:
360: // OK, no covariant dispatch
361: return false;
362: }
363:
364: /****************************************************************
365: * Merging
366: ****************************************************************/
367:
368: // <bonniot> this merge is not optimal since it does not search of a common supertype,
369: // <bonniot> only if one is smaller than the other
370: // <bonniot> but it should be useful already, and enough to test an algo that needs it
371: // <arjanb> yeah it would handle 95% of the cases
372: public static Monotype merge(Monotype m1, Monotype m2) {
373: if (m1 == m2)
374: return m1;
375:
376: Monotype raw = rawMerge(equivalent(m1), equivalent(m2));
377: if (raw == null)
378: return null;
379:
380: TypeConstructor marker;
381: if (isSure(m1) && isSure(m2))
382: marker = PrimitiveType.sureTC;
383: else
384: marker = PrimitiveType.maybeTC;
385:
386: Monotype res = new MonotypeConstructor(marker,
387: new Monotype[] { raw });
388: return res;
389: }
390:
391: private static Monotype rawMerge(Monotype raw1, Monotype raw2) {
392: if (raw1 == raw2)
393: return raw1;
394:
395: if (raw1 == TopMonotype.instance
396: || raw2 == TopMonotype.instance)
397: return TopMonotype.instance;
398:
399: TypeConstructor head1 = raw1.head();
400: TypeConstructor head2 = raw2.head();
401:
402: TypeConstructor head;
403: if (Typing.testRigidLeq(raw1.head(), raw2.head()))
404: head = raw2.head();
405: else if (Typing.testRigidLeq(raw2.head(), raw1.head()))
406: head = raw1.head();
407: else
408: return null;
409:
410: Monotype[] args1 = ((MonotypeConstructor) raw1).getTP();
411: Monotype[] args2 = ((MonotypeConstructor) raw2).getTP();
412: Monotype[] args;
413: if (args1 == null && args2 == null)
414: // no-arg type constructors
415: args = null;
416: else {
417: // Resursively merge the type parameters.
418: args = new Monotype[args1.length];
419: for (int i = 0; i < args.length; i++) {
420: args[i] = merge(args1[i], args2[i]);
421: if (args[i] == null)
422: return null;
423: }
424: }
425:
426: return new MonotypeConstructor(head, args);
427: }
428: }
|