1 package org.simantics.scl.compiler.types;
3 import org.simantics.scl.compiler.environment.Environment;
4 import org.simantics.scl.compiler.internal.types.HashCodeUtils;
5 import org.simantics.scl.compiler.types.exceptions.KindUnificationException;
6 import org.simantics.scl.compiler.types.exceptions.UnificationException;
7 import org.simantics.scl.compiler.types.kinds.Kinds;
9 import gnu.trove.map.hash.THashMap;
11 public class Skeletons {
13 public static Type canonicalSkeleton(Type type) {
14 while(type instanceof TMetaVar) {
15 TMetaVar metaVar = (TMetaVar)type;
16 if(metaVar.ref != null)
18 else if(metaVar.skeletonRef != null)
19 type = metaVar.skeletonRef;
26 public static Type canonicalSkeleton(THashMap<TMetaVar,Type> unifications, Type type) {
27 while(type instanceof TMetaVar) {
28 TMetaVar metaVar = (TMetaVar)type;
29 if(metaVar.ref != null)
31 else if(metaVar.skeletonRef != null)
32 type = metaVar.skeletonRef;
34 Type temp = unifications.get(metaVar);
44 public static boolean doesSkeletonContain(THashMap<TMetaVar,Type> unifications, Type type, TMetaVar metaVar) {
45 type = canonicalSkeleton(unifications, type);
48 if(type instanceof TFun) {
49 TFun fun = (TFun)type;
50 return doesSkeletonContain(unifications, fun.domain, metaVar)
51 || doesSkeletonContain(unifications, fun.range, metaVar);
53 if(type instanceof TApply) {
54 TApply apply = (TApply)type;
55 return doesSkeletonContain(unifications, apply.function, metaVar)
56 || doesSkeletonContain(unifications, apply.parameter, metaVar);
58 if(type instanceof TForAll) {
59 TForAll forAll = (TForAll)type;
60 return doesSkeletonContain(unifications, forAll.type, metaVar);
62 if(type instanceof TPred) {
63 TPred pred = (TPred)type;
64 for(Type param : pred.parameters)
65 if(doesSkeletonContain(unifications, param, metaVar))
74 * Returns true, if unification of the skeletons of the types would succeed.
76 public static boolean areSkeletonsCompatible(THashMap<TMetaVar,Type> unifications, Type a, Type b) {
77 a = canonicalSkeleton(unifications, a);
78 b = canonicalSkeleton(unifications, b);
81 Class<?> ca = a.getClass();
82 Class<?> cb = b.getClass();
84 if(ca == TMetaVar.class) {
85 TMetaVar ma = (TMetaVar)a;
86 if(doesSkeletonContain(unifications, b, ma))
88 unifications.put(ma, b);
91 if(cb == TMetaVar.class) {
92 TMetaVar mb = (TMetaVar)b;
93 if(doesSkeletonContain(unifications, a, mb))
95 unifications.put(mb, a);
100 if(ca == TFun.class) {
103 return areSkeletonsCompatible(unifications, funA.domain, funB.domain)
104 && areSkeletonsCompatible(unifications, funA.range, funB.range);
106 if(ca == TApply.class) {
107 TApply applyA = (TApply)a;
108 TApply applyB = (TApply)b;
109 return areSkeletonsCompatible(unifications, applyA.function, applyB.function)
110 && areSkeletonsCompatible(unifications, applyA.parameter, applyB.parameter);
112 if(ca == TPred.class) {
113 TPred predA = (TPred)a;
114 TPred predB = (TPred)b;
115 if(predA.typeClass != predB.typeClass)
117 for(int i=0;i<predA.parameters.length;++i)
118 if(!areSkeletonsCompatible(unifications, predA.parameters[i], predB.parameters[i]))
122 if(ca == TForAll.class) {
123 TForAll forAllA = (TForAll)a;
124 TForAll forAllB = (TForAll)b;
125 TVar temp = Types.var(forAllA.var.getKind());
126 return areSkeletonsCompatible(unifications,
127 forAllA.type.replace(forAllA.var, temp),
128 forAllB.type.replace(forAllB.var, temp));
133 public static void unifySkeletons(Type a, Type b) throws UnificationException {
134 a = canonicalSkeleton(a);
135 b = canonicalSkeleton(b);
139 if(a instanceof TMetaVar) {
140 ((TMetaVar) a).setSkeletonRef(b);
143 if(b instanceof TMetaVar) {
144 ((TMetaVar) b).setSkeletonRef(a);
148 Class<?> ca = a.getClass();
149 Class<?> cb = b.getClass();
151 throw new UnificationException(a, b);
153 if(ca == TApply.class)
154 //unifySkeletons((TApply)a, (TApply)b);
156 else if(ca == TFun.class)
157 unifySkeletons((TFun)a, (TFun)b);
158 else if(ca == TForAll.class)
159 unifySkeletons((TForAll)a, (TForAll)b);
160 else if(ca == TPred.class)
161 //unifySkeletons((TPred)a, (TPred)b);
163 else if(ca == TUnion.class)
164 unifySkeletons((TUnion)a, (TUnion)b);
165 else // ca == TCon.class || ca = TVar.class
166 throw new UnificationException(a, b);
169 public static void unifySkeletons(TFun a, TFun b) throws UnificationException {
170 unifySkeletons(a.domain, b.domain);
171 unifySkeletons(a.range, b.range);
174 public static void unifySkeletons(TApply a, TApply b) throws UnificationException {
175 unifySkeletons(a.function, b.function);
176 unifySkeletons(a.parameter, b.parameter);
179 public static void unifySkeletons(TForAll a, TForAll b) throws UnificationException {
181 Kinds.unify(a.var.getKind(), b.var.getKind());
182 } catch (KindUnificationException e) {
183 throw new UnificationException(a, b);
185 TVar newVar = Types.var(a.var.getKind());
186 unifySkeletons(a.type.replace(a.var, newVar), b.type.replace(b.var, newVar));
189 public static void unifySkeletons(TPred a, TPred b) throws UnificationException {
190 if(a.typeClass != b.typeClass
191 || a.parameters.length != b.parameters.length)
192 throw new UnificationException(a, b);
193 for(int i=0;i<a.parameters.length;++i)
194 unifySkeletons(a.parameters[i], b.parameters[i]);
197 public static void unifySkeletons(TUnion a, TUnion b) throws UnificationException {
201 public static Type commonSkeleton(Environment context, Type[] types) {
202 THashMap<Type[], TMetaVar> metaVarMap = new THashMap<Type[], TMetaVar>() {
204 protected boolean equals(Object a, Object b) {
205 return Types.equals((Type[])a, (Type[])b);
208 protected int hash(Object a) {
209 Type[] types = (Type[])a;
210 int hash = HashCodeUtils.SEED;
211 for(Type type : types)
212 hash = type.hashCode(hash);
216 return commonSkeleton(context, metaVarMap, types);
219 private static TMetaVar metaVarFor(Environment context, THashMap<Type[], TMetaVar> metaVarMap, Type[] types) {
220 TMetaVar result = metaVarMap.get(types);
223 result = Types.metaVar(types[0].inferKind(context));
224 } catch (KindUnificationException e) {
225 result = Types.metaVar(Kinds.STAR);
227 metaVarMap.put(types, result);
233 * Finds the most specific type that can be unified with the all the types
234 * given as a parameter.
236 private static Type commonSkeleton(Environment context, THashMap<Type[], TMetaVar> metaVarMap, Type[] types) {
237 for(int i=0;i<types.length;++i)
238 types[i] = canonicalSkeleton(types[i]);
240 Type first = types[0];
241 Class<?> clazz = first.getClass();
242 for(int i=1;i<types.length;++i)
243 if(types[i].getClass() != clazz)
244 return metaVarFor(context, metaVarMap, types);
246 if(clazz == TCon.class) {
247 for(int i=1;i<types.length;++i)
248 if(types[i] != first)
249 return metaVarFor(context, metaVarMap, types);
252 else if(clazz == TApply.class) {
253 Type[] functions = new Type[types.length];
254 Type[] parameters = new Type[types.length];
255 for(int i=0;i<types.length;++i) {
256 TApply apply = (TApply)types[i];
257 functions[i] = apply.function;
258 parameters[i] = apply.parameter;
261 commonSkeleton(context, metaVarMap, functions),
262 commonSkeleton(context, metaVarMap, parameters));
264 else if(clazz == TFun.class) {
265 Type[] domains = new Type[types.length];
266 Type[] effects = new Type[types.length];
267 Type[] ranges = new Type[types.length];
268 for(int i=0;i<types.length;++i) {
269 TFun fun = (TFun)types[i];
270 if(fun.domain instanceof TPred)
271 return metaVarFor(context, metaVarMap, types);
272 domains[i] = fun.domain;
273 effects[i] = fun.effect;
274 ranges[i] = fun.range;
276 return Types.functionE(
277 commonSkeleton(context, metaVarMap, domains),
278 commonEffect(effects),
279 commonSkeleton(context, metaVarMap, ranges));
282 return metaVarFor(context, metaVarMap, types);
285 private static Type commonEffect(Type[] effects) {
286 Type first = effects[0];
287 for(int i=1;i<effects.length;++i)
288 if(!Types.equals(first, effects[i]))
289 return Types.metaVar(Kinds.EFFECT);