bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/types/Skeletons.java

   1 package org.simantics.scl.compiler.types;
   2
   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;
   8
   9 import gnu.trove.map.hash.THashMap;
  10
  11 public class Skeletons {
  12
  13     public static Type canonicalSkeleton(Type type) {
  14         while(type instanceof TMetaVar) {
  15             TMetaVar metaVar = (TMetaVar)type;
  16             if(metaVar.ref != null)
  17                 type = metaVar.ref;
  18             else if(metaVar.skeletonRef != null)
  19                 type = metaVar.skeletonRef;
  20             else
  21                 return metaVar;
  22         }
  23         return type;
  24     }
  25
  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)
  30                 type = metaVar.ref;
  31             else if(metaVar.skeletonRef != null)
  32                 type = metaVar.skeletonRef;
  33             else {
  34                 Type temp = unifications.get(metaVar);
  35                 if(temp == null)
  36                     return metaVar;
  37                 else
  38                     type = temp;
  39             }
  40         }
  41         return type;
  42     }
  43
  44     public static boolean doesSkeletonContain(THashMap<TMetaVar,Type> unifications, Type type, TMetaVar metaVar) {
  45         type = canonicalSkeleton(unifications, type);
  46         if(type == metaVar)
  47             return true;
  48         if(type instanceof TFun) {
  49             TFun fun = (TFun)type;
  50             return doesSkeletonContain(unifications, fun.domain, metaVar)
  51                     || doesSkeletonContain(unifications, fun.range, metaVar);
  52         }
  53         if(type instanceof TApply) {
  54             TApply apply = (TApply)type;
  55             return doesSkeletonContain(unifications, apply.function, metaVar)
  56                     || doesSkeletonContain(unifications, apply.parameter, metaVar);
  57         }
  58         if(type instanceof TForAll) {
  59             TForAll forAll = (TForAll)type;
  60             return doesSkeletonContain(unifications, forAll.type, metaVar);
  61         }
  62         if(type instanceof TPred) {
  63             TPred pred = (TPred)type;
  64             for(Type param : pred.parameters)
  65                 if(doesSkeletonContain(unifications, param, metaVar))
  66                     return true;
  67             return false;
  68         }
  69         else
  70             return false;
  71     }
  72
  73     /**
  74      * Returns true, if unification of the skeletons of the types would succeed.
  75      */
  76     public static boolean areSkeletonsCompatible(THashMap<TMetaVar,Type> unifications, Type a, Type b) {
  77         a = canonicalSkeleton(unifications, a);
  78         b = canonicalSkeleton(unifications, b);
  79         if(a == b)
  80             return true;
  81         Class<?> ca = a.getClass();
  82         Class<?> cb = b.getClass();
  83
  84         if(ca == TMetaVar.class) {
  85             TMetaVar ma = (TMetaVar)a;
  86             if(doesSkeletonContain(unifications, b, ma))
  87                 return false;
  88             unifications.put(ma, b);
  89             return true;
  90         }
  91         if(cb == TMetaVar.class) {
  92             TMetaVar mb = (TMetaVar)b;
  93             if(doesSkeletonContain(unifications, a, mb))
  94                 return false;
  95             unifications.put(mb, a);
  96             return true;
  97         }
  98         if(ca != cb)
  99             return false;
 100         if(ca == TFun.class) {
 101             TFun funA = (TFun)a;
 102             TFun funB = (TFun)b;
 103             return areSkeletonsCompatible(unifications, funA.domain, funB.domain)
 104                     && areSkeletonsCompatible(unifications, funA.range, funB.range);
 105         }
 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);
 111         }
 112         if(ca == TPred.class) {
 113             TPred predA = (TPred)a;
 114             TPred predB = (TPred)b;
 115             if(predA.typeClass != predB.typeClass)
 116                 return false;
 117             for(int i=0;i<predA.parameters.length;++i)
 118                 if(!areSkeletonsCompatible(unifications, predA.parameters[i], predB.parameters[i]))
 119                     return false;
 120             return true;
 121         }
 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));
 129         }
 130         return false;
 131     }
 132
 133     public static void unifySkeletons(Type a, Type b) throws UnificationException {
 134         a = canonicalSkeleton(a);
 135         b = canonicalSkeleton(b);
 136
 137         if(a == b)
 138             return;
 139         if(a instanceof TMetaVar) {
 140             ((TMetaVar) a).setSkeletonRef(b);
 141             return;
 142         }
 143         if(b instanceof TMetaVar) {
 144             ((TMetaVar) b).setSkeletonRef(a);
 145             return;
 146         }
 147
 148         Class<?> ca = a.getClass();
 149         Class<?> cb = b.getClass();
 150         if(ca != cb) {
 151             throw new UnificationException(a, b);
 152         }
 153         if(ca == TApply.class)
 154             //unifySkeletons((TApply)a, (TApply)b);
 155             Types.unify(a, 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);
 162             Types.unify(a, 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);
 167     }
 168
 169     public static void unifySkeletons(TFun a, TFun b) throws UnificationException {
 170         unifySkeletons(a.domain, b.domain);
 171         unifySkeletons(a.range, b.range);
 172     }
 173
 174     public static void unifySkeletons(TApply a, TApply b) throws UnificationException {
 175         unifySkeletons(a.function, b.function);
 176         unifySkeletons(a.parameter, b.parameter);
 177     }
 178
 179     public static void unifySkeletons(TForAll a, TForAll b) throws UnificationException {
 180         try {
 181             Kinds.unify(a.var.getKind(), b.var.getKind());
 182         } catch (KindUnificationException e) {
 183             throw new UnificationException(a, b);
 184         }
 185         TVar newVar = Types.var(a.var.getKind());
 186         unifySkeletons(a.type.replace(a.var, newVar), b.type.replace(b.var, newVar));
 187     }
 188
 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]);
 195     }
 196
 197     public static void unifySkeletons(TUnion a, TUnion b) throws UnificationException {
 198         // Nothing to do
 199     }
 200
 201     public static Type commonSkeleton(Environment context, Type[] types) {
 202         THashMap<Type[], TMetaVar> metaVarMap = new THashMap<Type[], TMetaVar>() {
 203             @Override
 204             protected boolean equals(Object a, Object b) {
 205                 return Types.equals((Type[])a, (Type[])b);
 206             }
 207             @Override
 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);
 213                 return hash;
 214             }
 215         };
 216         return commonSkeleton(context, metaVarMap, types);
 217     }
 218
 219     private static TMetaVar metaVarFor(Environment context, THashMap<Type[], TMetaVar> metaVarMap, Type[] types) {
 220         TMetaVar result = metaVarMap.get(types);
 221         if(result == null) {
 222             try {
 223                 result = Types.metaVar(types[0].inferKind(context));
 224             } catch (KindUnificationException e) {
 225                 result = Types.metaVar(Kinds.STAR);
 226             }
 227             metaVarMap.put(types, result);
 228         }
 229         return result;
 230     }
 231
 232     /**
 233      * Finds the most specific type that can be unified with the all the types
 234      * given as a parameter.
 235      */
 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]);
 239
 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);
 245
 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);
 250             return first;
 251         }
 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;
 259             }
 260             return Types.apply(
 261                     commonSkeleton(context, metaVarMap, functions),
 262                     commonSkeleton(context, metaVarMap, parameters));
 263         }
 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;
 275             }
 276             return Types.functionE(
 277                     commonSkeleton(context, metaVarMap, domains),
 278                     commonEffect(effects),
 279                     commonSkeleton(context, metaVarMap, ranges));
 280         }
 281         else
 282             return metaVarFor(context, metaVarMap, types);
 283     }
 284
 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);
 290         return first;
 291     }
 292 }