001: /**************************************************************************/
002: /* B O S S A */
003: /* A simple imperative object-oriented research language */
004: /* (c) Daniel Bonniot 1999 */
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 mlsub.typing;
012:
013: import java.util.*;
014:
015: import mlsub.typing.lowlevel.*;
016:
017: /**
018: Variance of a type constructor.
019:
020: There is one instance of this class per Variance,
021: so pointer equality can be used on variances.
022:
023: @author Daniel Bonniot
024: */
025: public final class Variance implements AtomicKind /* Variance is the Kind of MonotypeConstructors */
026: {
027: private Variance(int[] signs) {
028: this .size = signs.length;
029: this .signs = signs;
030: }
031:
032: /**
033: Array specifying subtyping properties for each parameter:
034: covariant, contravariant or invariant.
035: */
036: private int[] signs;
037:
038: public static final Variance make(int[] signs) {
039: int encoding = encoding(signs);
040: Variance res = get(encoding);
041:
042: if (res == null)
043: return set(encoding, new Variance(signs));
044: else
045: return res;
046: }
047:
048: /**
049: @return the variance of the rankth element
050: */
051: public int getVariance(int rank) {
052: return signs[rank];
053: }
054:
055: /** Compute a small integer that uniquely identifies a variance. */
056: private static int encoding(int[] signs) {
057: int res = 0;
058:
059: int base = 1;
060: for (int i = 0; i < signs.length; i++) {
061: res = res + (signs[i] + 2) * base;
062: base *= 4;
063: }
064: return res;
065: }
066:
067: /****************************************************************
068: * Repository of created variances
069: ****************************************************************/
070:
071: private static final ArrayList variances = new ArrayList(64);
072:
073: private static Variance get(int index) {
074: if (index >= variances.size())
075: return null;
076: return (Variance) variances.get(index);
077: }
078:
079: private static Variance set(int index, Variance v) {
080: // make the list grow
081: while (index >= variances.size())
082: variances.add(null);
083:
084: variances.set(index, v);
085: return v;
086: }
087:
088: /****************************************************************
089: * Empty Variance
090: ****************************************************************/
091:
092: public static Variance empty() {
093: return empty;
094: }
095:
096: private static Variance empty = Variance.make(new int[0]);
097:
098: public mlsub.typing.lowlevel.Engine.Constraint getConstraint() {
099: return mlsub.typing.lowlevel.Engine.getConstraint(this );
100: }
101:
102: public Monotype freshMonotype(boolean existential) {
103: TypeConstructor tc = new TypeConstructor(this );
104: Typing.introduce(tc);
105:
106: Monotype[] tp = MonotypeVar.news(this .size, existential);
107: Typing.introduce(tp);
108:
109: return new MonotypeConstructor(tc, tp);
110: }
111:
112: public void register(Element e) {
113: // if(!(e instanceof MonotypeConstructor))
114: // return;
115:
116: // MonotypeConstructor mc = (MonotypeConstructor) e;
117: // TypeConstructor tc = mc.getTC();
118: // Engine.Constraint k = Engine.getConstraint(this);
119:
120: // if(tc.getKind()!=k)
121: // if(tc.getKind()==null)
122: // Engine.setKind(tc,k);
123: // else
124: // throw new TypingEx("Bad kinding for "+e);
125: }
126:
127: /****************************************************************
128: * Interfaces
129: ****************************************************************/
130:
131: private Vector interfaces = new Vector(10);
132:
133: int newInterface(Interface i) {
134: int res = getConstraint().newInterface();
135: if (res >= interfaces.size())
136: interfaces.setSize(res + 1);
137: interfaces.set(res, i);
138: return res;
139: }
140:
141: public Interface getInterface(int iid) {
142: return (Interface) interfaces.get(iid);
143: }
144:
145: void subInterface(int i1, int i2) {
146: getConstraint().subInterface(i1, i2);
147: }
148:
149: void initialImplements(int x, int iid) {
150: getConstraint().initialImplements(x, iid);
151: }
152:
153: void initialAbstracts(int x, int iid) {
154: getConstraint().initialAbstracts(x, iid);
155: }
156:
157: void indexImplements(int x, int iid) throws Unsatisfiable {
158: getConstraint().indexImplements(x, iid);
159: }
160:
161: public void leq(Element e1, Element e2, boolean initial)
162: throws Unsatisfiable {
163: if (initial)
164: throw new InternalError("initial leq in Variance");
165: leq(e1, e2);
166: }
167:
168: public void leq(Element e1, Element e2) throws Unsatisfiable {
169: MonotypeConstructor m1 = mc(e1), m2 = mc(e2);
170:
171: mlsub.typing.lowlevel.Engine.leq(m1.getTC(), m2.getTC());
172: assertEq(m1.getTP(), m2.getTP());
173: }
174:
175: private MonotypeConstructor mc(Element e) {
176: try {
177: return (MonotypeConstructor) ((Monotype) e).equivalent();
178: } catch (ClassCastException ex) {
179: throw new InternalError(e
180: + " was expected to be a monotype constructor, "
181: + " it's a " + e.getClass());
182: }
183: }
184:
185: /**
186: * Asserts the inequalities between type parameters
187: * belonging to this variance
188: *
189: * @param tp1 a least Collection of Monotypes
190: * @param tp2 a greatest Collection of Monotypes
191: */
192: public void assertEq(Monotype[] tp1, Monotype[] tp2)
193: throws mlsub.typing.lowlevel.Unsatisfiable {
194: if (size == 0)
195: if (tp1 == null && tp2 == null)
196: //OK
197: return;
198: else
199: throw new InternalError("Incorrect sizes "
200: + (tp1 == null ? "null" : Integer
201: .toString(tp1.length))
202: + " and "
203: + (tp2 == null ? "null" : Integer
204: .toString(tp2.length)));
205:
206: if (tp1 == null || tp1.length != size)
207: throw new BadSizeEx(size, tp1 == null ? 0 : tp1.length);
208: if (tp2 == null || tp2.length != size)
209: throw new BadSizeEx(size, tp2 == null ? 0 : tp2.length);
210:
211: for (int i = 0; i < size; i++)
212: switch (signs[i]) {
213: // TODO: Consider UnknownMonotype in non-invariant cases
214: case COVARIANT:
215: mlsub.typing.lowlevel.Engine.leq(tp1[i], tp2[i]);
216: break;
217: case CONTRAVARIANT:
218: mlsub.typing.lowlevel.Engine.leq(tp2[i], tp1[i]);
219: break;
220:
221: case INVARIANT:
222: if (tp2[i].isUnknown())
223: continue;
224:
225: if (tp1[i].isUnknown()) {
226: tp2[i].setUnknown(true, true);
227: continue;
228: }
229:
230: mlsub.typing.lowlevel.Engine.leq(tp1[i], tp2[i]);
231: mlsub.typing.lowlevel.Engine.leq(tp2[i], tp1[i]);
232: break;
233: }
234: }
235:
236: /****************************************************************
237: * Printing
238: ****************************************************************/
239:
240: public String toString() {
241: StringBuffer sb = new StringBuffer();
242: for (int i = 0; i < size; i++) {
243: if (i > 0)
244: sb.append(", ");
245: switch (signs[i]) {
246: case COVARIANT:
247: sb.append("+");
248: break;
249: case CONTRAVARIANT:
250: sb.append("-");
251: break;
252: case INVARIANT:
253: sb.append("=");
254: break;
255: }
256: }
257:
258: return "Variance (" + sb.toString() + ")";
259: }
260:
261: private int size;
262:
263: public int arity() {
264: return size;
265: }
266:
267: /****************************************************************
268: * Simplification
269: ****************************************************************/
270:
271: static public final int COVARIANT = +1, CONTRAVARIANT = -1,
272: INVARIANT = 0;
273:
274: void tag(Monotype[] monotypes, int variance) {
275: if (monotypes == null)
276: return;
277:
278: for (int i = 0; i < monotypes.length; i++)
279: monotypes[i].tag(variance * signs[i]);
280: }
281: }
|