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

   1 package org.simantics.scl.compiler.types;
   2
   3 import java.util.ArrayList;
   4
   5 import org.simantics.databoard.util.IdentityHashSet;
   6 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   7 import org.simantics.scl.compiler.environment.Environment;
   8 import org.simantics.scl.compiler.internal.types.HashCodeUtils;
   9 import org.simantics.scl.compiler.internal.types.TypeHashCodeContext;
  10 import org.simantics.scl.compiler.internal.types.ast.TVarAst;
  11 import org.simantics.scl.compiler.internal.types.ast.TypeAst;
  12 import org.simantics.scl.compiler.types.exceptions.KindUnificationException;
  13 import org.simantics.scl.compiler.types.exceptions.UnificationException;
  14 import org.simantics.scl.compiler.types.kinds.KMetaVar;
  15 import org.simantics.scl.compiler.types.kinds.Kind;
  16 import org.simantics.scl.compiler.types.kinds.Kinds;
  17 import org.simantics.scl.compiler.types.util.Polarity;
  18 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;
  19
  20 import gnu.trove.map.hash.THashMap;
  21 import gnu.trove.set.hash.THashSet;
  22
  23
  24
  25 /**
  26  * A meta-variable, a type that is currently unknown. This class
  27  * should occur only during type inference. Method removeMetaVars
  28  * can be used to remove all instances of TMetaVar from the type.
  29  *
  30  * @author Hannu Niemist&ouml;
  31  */
  32 public class TMetaVar extends Type {
  33     public static final TMetaVar[] EMPTY_ARRAY = new TMetaVar[0];
  34     public static final boolean DEBUG = false;
  35
  36     Type ref = null;
  37     Type skeletonRef = null;
  38     Polarity polarity = Polarity.NO_POLARITY;
  39     private Kind kind;
  40     private TMetaVarListener listener;
  41
  42     public static abstract class TMetaVarListener {
  43         private Object prev; // TMetaVarListener or TMetaVar
  44         private TMetaVarListener next;
  45
  46         public abstract void notifyAboutChange();
  47
  48         public void remove() {
  49             if(prev == null)
  50                 return; // Not added or not anymore listening TMetaVar
  51             if(prev instanceof TMetaVar)
  52                 ((TMetaVar)prev).listener = next;
  53             else
  54                 ((TMetaVarListener)prev).next = next;
  55             if(next != null) {
  56                 next.prev = prev;
  57                 next = null;
  58             }
  59             prev = null;
  60         }
  61     }
  62
  63     TMetaVar(Kind kind) {
  64         this.kind = kind;
  65     }
  66
  67     TMetaVar(Kind kind, Polarity polarity) {
  68         this.kind = kind;
  69         this.polarity = polarity;
  70     }
  71
  72     public Kind getKind() {
  73         if(kind instanceof KMetaVar)
  74             kind = Kinds.canonical(kind);
  75         return kind;
  76     }
  77
  78     @Override
  79     public Type replace(TVar var, Type replacement) {
  80         if(ref == null)
  81             return this;
  82         else {
  83             Type newRef = ref.replace(var, replacement);
  84             if(newRef != ref)
  85                 return newRef;
  86             else
  87                 // We could also return newRef here, but in this way
  88                 // we don't have to copy so many parent types.
  89                 return this;
  90         }
  91     }
  92
  93     @Override
  94     public TypeAst toTypeAst(TypeUnparsingContext context) {
  95         if(ref == null)
  96             return new TVarAst(/*polarity.getSymbol() +*/ context.getName(this));
  97         else
  98             return ref.toTypeAst(context);
  99     }
 100
 101     @Override
 102     public void updateHashCode(TypeHashCodeContext context) {
 103         if(ref == null)
 104             context.append(System.identityHashCode(this));
 105         else
 106             ref.updateHashCode(context);
 107     }
 108
 109     @Override
 110     public void collectFreeVars(ArrayList<TVar> vars) {
 111         if(ref != null)
 112             ref.collectFreeVars(vars);
 113     }
 114
 115     @Override
 116     public void collectMetaVars(ArrayList<TMetaVar> vars) {
 117         if(ref == null)
 118             vars.add(this);
 119         else
 120             ref.collectMetaVars(vars);
 121     }
 122
 123     @Override
 124     public void collectMetaVars(THashSet<TMetaVar> vars) {
 125         if(ref == null)
 126             vars.add(this);
 127         else
 128             ref.collectMetaVars(vars);
 129     }
 130
 131     @Override
 132     public void collectEffectMetaVars(ArrayList<TMetaVar> vars) {
 133         if(ref != null)
 134             ref.collectEffectMetaVars(vars);
 135     }
 136
 137     public void setRef(Type type) throws UnificationException {
 138         //System.out.println("----");
 139         //System.out.println("this = " + refStructure(this));
 140         //System.out.println("type = " + refStructure(type));
 141         if(type == this)
 142             throw new InternalCompilerError("Illegal setRef");
 143         if(DEBUG)
 144             System.out.println("setRef " + System.identityHashCode(this) + " -> " + type);
 145         if(ref != null)
 146             throw new InternalCompilerError("Method setRef should be called only for unbound meta variables.");
 147         Type thisSkeleton = Skeletons.canonicalSkeleton(this);
 148
 149         if(type instanceof TMetaVar) {
 150             TMetaVar other = (TMetaVar)type;
 151             if(other.ref != null)
 152                 throw new InternalCompilerError("Not canonical!");
 153
 154             Type typeSkeleton = Skeletons.canonicalSkeleton(type);
 155             if(thisSkeleton == typeSkeleton) {
 156                 if(skeletonRef != null)
 157                     setRefBase(type);
 158                 else
 159                     other.setRefBase(this);
 160                 return;
 161             }
 162             else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
 163                 throw new UnificationException(this, type);
 164         }
 165         else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
 166             throw new UnificationException(this, type);
 167
 168         // Common case
 169         if(skeletonRef != null) {
 170             Skeletons.unifySkeletons(thisSkeleton, type);
 171         }
 172         setRefBase(type);
 173     }
 174
 175     private void setRefBase(Type type) throws UnificationException {
 176         skeletonRef = null;
 177         ref = type;
 178         if(polarity != Polarity.NO_POLARITY)
 179             type.addPolarity(polarity);
 180         //System.out.println("result = " + refStructure(this));
 181         //checkRefLoop(this);
 182         fireNotifyAboutChange();
 183     }
 184
 185     private static String refStructure(Type t) {
 186         StringBuilder b = new StringBuilder();
 187         IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
 188         refType(b, t, seenVars);
 189         return b.toString();
 190     }
 191
 192     private void refStructure(StringBuilder b, IdentityHashSet<TMetaVar> seenVars) {
 193         b.append(System.identityHashCode(this));
 194         if(!seenVars.add(this))
 195             b.append(" (loop)");
 196         else if(ref != null) {
 197             b.append(" => ");
 198             refType(b, ref, seenVars);
 199         }
 200         else if(skeletonRef != null) {
 201             b.append(" -> ");
 202             refType(b, skeletonRef, seenVars);
 203         }
 204         else
 205             b.append(" (canonical)");
 206     }
 207
 208     private static void refType(StringBuilder b, Type t, IdentityHashSet<TMetaVar> seenVars) {
 209         if(t instanceof TMetaVar)
 210             ((TMetaVar)t).refStructure(b, seenVars);
 211         else {
 212             b.append('[');
 213             t.toString(new TypeUnparsingContext(), b);
 214             b.append(']');
 215         }
 216     }
 217
 218     private void checkRefLoop(TMetaVar var) {
 219         IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
 220         StringBuilder b = new StringBuilder();
 221         while(true) {
 222             b.append(var);
 223             if(!seenVars.add(var))
 224                 throw new InternalCompilerError("Cyclic meta var references: " + b);
 225             if(var.ref != null) {
 226                 b.append(" => ");
 227                 if(var.ref instanceof TMetaVar)
 228                     var = (TMetaVar)var.ref;
 229                 else
 230                     return;
 231             }
 232             else if(var.skeletonRef != null) {
 233                 b.append(" -> ");
 234                 if(var.skeletonRef instanceof TMetaVar)
 235                     var = (TMetaVar)var.skeletonRef;
 236                 else
 237                     return;
 238             }
 239             else
 240                 return;
 241         }
 242     }
 243
 244     public Type getRef() {
 245         return ref;
 246     }
 247
 248     @Override
 249     public boolean contains(TMetaVar other) {
 250         if(ref != null)
 251             return ref.contains(other);
 252         else if(skeletonRef != null)
 253             return skeletonRef.contains(other);
 254         else
 255             return this == other;
 256     }
 257
 258     @Override
 259     public Type convertMetaVarsToVars() {
 260         if(ref == null) {
 261             if(kind == Kinds.EFFECT && !polarity.isNegative())
 262                 ref = Types.NO_EFFECTS;
 263             else
 264                 ref = Types.var(getKind());
 265             return ref;
 266         }
 267         else
 268             return ref.convertMetaVarsToVars();
 269     }
 270
 271     @Override
 272     public boolean isGround() {
 273         if(ref == null)
 274             return false;
 275         else
 276             return ref.isGround();
 277     }
 278
 279         public Kind inferKind(Environment context) throws KindUnificationException {
 280             return Kinds.metaVar();
 281     }
 282
 283     @Override
 284     public boolean containsMetaVars() {
 285         if(ref == null)
 286             return true;
 287         else
 288             return ref.containsMetaVars();
 289     }
 290
 291     @Override
 292     public void toName(TypeUnparsingContext context, StringBuilder b) {
 293         if(ref != null)
 294             ref.toName(context, b);
 295         else
 296             b.append(context.getName(this));
 297     }
 298
 299     @Override
 300     public int getClassId() {
 301         return METAVAR_ID;
 302     }
 303
 304     @Override
 305     public boolean isMaximal() {
 306         return ref != null && ref.isMaximal();
 307     }
 308
 309     @Override
 310     public boolean isMinimal() {
 311         return ref != null && ref.isMinimal();
 312     }
 313
 314     @Override
 315     public void addPolarity(Polarity polarity) {
 316         if(ref != null)
 317             ref.addPolarity(polarity);
 318         else
 319             this.polarity = this.polarity.add(polarity);
 320     }
 321
 322     public Polarity getPolarity() {
 323         return polarity;
 324     }
 325
 326     @Override
 327     public void collectConcreteEffects(ArrayList<TCon> concreteEffects) {
 328         if(ref != null)
 329             ref.collectConcreteEffects(concreteEffects);
 330     }
 331
 332     @Override
 333     public Type head() {
 334         if(ref != null)
 335             return ref.head();
 336         else
 337             return this;
 338     }
 339
 340     @Override
 341     public Type copySkeleton(THashMap<TMetaVar, TMetaVar> metaVarMap) {
 342         if(ref != null)
 343             return ref.copySkeleton(metaVarMap);
 344         else {
 345             TMetaVar result = metaVarMap.get(this);
 346             if(result == null) {
 347                 result = new TMetaVar(kind, polarity);
 348                 metaVarMap.put(this, result);
 349             }
 350             return result;
 351         }
 352     }
 353
 354     public void setSkeletonRef(Type type) throws UnificationException {
 355         if(DEBUG)
 356             System.out.println("setSkeletonRef " +  System.identityHashCode(this) + " -> " + type);
 357         if(ref != null || skeletonRef != null)
 358             throw new InternalCompilerError("Method setRef should be called only for unbound meta variables.");
 359         if(type.contains(this))
 360             throw new UnificationException(this, type);
 361         this.skeletonRef = type;
 362         //checkRefLoop(this);
 363         fireNotifyAboutChange();
 364     }
 365
 366     @Override
 367     public int hashCode() {
 368         if(ref == null)
 369             return System.identityHashCode(this);
 370         else
 371             return ref.hashCode();
 372     }
 373
 374     @Override
 375     public int hashCode(int hash) {
 376         if(ref == null)
 377             return HashCodeUtils.update(hash, System.identityHashCode(this));
 378         else
 379             return ref.hashCode(hash);
 380     }
 381
 382     @Override
 383     public int hashCode(int hash, TVar[] boundVars) {
 384         if(ref == null)
 385             return HashCodeUtils.update(hash, System.identityHashCode(this));
 386         else
 387             return ref.hashCode(hash, boundVars);
 388     }
 389
 390     @Override
 391     public int skeletonHashCode() {
 392         if(ref != null)
 393             return ref.skeletonHashCode();
 394         else if(skeletonRef != null)
 395             return skeletonRef.skeletonHashCode();
 396         else
 397             return System.identityHashCode(this);
 398     }
 399
 400     @Override
 401     public int skeletonHashCode(int hash) {
 402         if(ref != null)
 403             return ref.skeletonHashCode(hash);
 404         else if(skeletonRef != null)
 405             return skeletonRef.skeletonHashCode(hash);
 406         else
 407             return HashCodeUtils.update(hash, System.identityHashCode(this));
 408     }
 409
 410     @Override
 411     public int skeletonHashCode(int hash, TVar[] boundVars) {
 412         if(ref != null)
 413             return ref.skeletonHashCode(hash, boundVars);
 414         else if(skeletonRef != null)
 415             return skeletonRef.skeletonHashCode(hash, boundVars);
 416         else
 417             return HashCodeUtils.update(hash, System.identityHashCode(this));
 418     }
 419
 420     @Override
 421     public boolean equalsCanonical(Type other) {
 422         return this == other;
 423     }
 424
 425     @Override
 426     public Type canonical() {
 427         if(ref == null)
 428             return this;
 429         else
 430             return ref = ref.canonical();
 431     }
 432
 433     public void addListener(TMetaVarListener newListener) {
 434         if(DEBUG)
 435             System.out.println("addListener " + System.identityHashCode(this));
 436         newListener.next = listener;
 437         newListener.prev = this;
 438         if(listener != null)
 439             listener.prev = newListener;
 440         listener = newListener;
 441     }
 442
 443     private void fireNotifyAboutChange() {
 444         if(DEBUG)
 445             System.out.println("fireNotifyAboutChange " + System.identityHashCode(this) + " " + ref);
 446         TMetaVarListener cur = listener;
 447         listener = null;
 448         while(cur != null) {
 449             if(DEBUG)
 450                 System.out.println("    call listener");
 451             cur.prev = null; // This prevents TMetaVarListener.remove from doing anything
 452             cur.notifyAboutChange();
 453             TMetaVarListener next = cur.next;
 454             cur.next = null;
 455             cur = next;
 456         }
 457     }
 458
 459     public TMetaVarListener getLatestListener() {
 460         return listener;
 461     }
 462
 463     @Override
 464     public Kind getKind(Environment context) {
 465         return kind;
 466     }
 467
 468     @Override
 469     public Type[] skeletonCanonicalChildren() {
 470         // Assumes that this is already canonical skeleton
 471         return EMPTY_ARRAY;
 472     }
 473 }