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 ref.toTypeAst(context);
  97         else if(context.showSkeletons && skeletonRef != null)
  98             return skeletonRef.toTypeAst(context);
  99         else
 100             return new TVarAst(/*polarity.getSymbol() +*/ context.getName(this));
 101     }
 102
 103     @Override
 104     public void updateHashCode(TypeHashCodeContext context) {
 105         if(ref == null)
 106             context.append(System.identityHashCode(this));
 107         else
 108             ref.updateHashCode(context);
 109     }
 110
 111     @Override
 112     public void collectFreeVars(ArrayList<TVar> vars) {
 113         if(ref != null)
 114             ref.collectFreeVars(vars);
 115     }
 116
 117     @Override
 118     public void collectMetaVars(ArrayList<TMetaVar> vars) {
 119         if(ref == null)
 120             vars.add(this);
 121         else
 122             ref.collectMetaVars(vars);
 123     }
 124
 125     @Override
 126     public void collectMetaVars(THashSet<TMetaVar> vars) {
 127         if(ref == null)
 128             vars.add(this);
 129         else
 130             ref.collectMetaVars(vars);
 131     }
 132
 133     @Override
 134     public void collectEffectMetaVars(ArrayList<TMetaVar> vars) {
 135         if(ref != null)
 136             ref.collectEffectMetaVars(vars);
 137     }
 138
 139     public void setRef(Type type) throws UnificationException {
 140         //System.out.println("----");
 141         //System.out.println("this = " + refStructure(this));
 142         //System.out.println("type = " + refStructure(type));
 143         if(type == this)
 144             throw new InternalCompilerError("Illegal setRef");
 145         if(DEBUG)
 146             System.out.println("setRef " + System.identityHashCode(this) + " -> " + type);
 147         if(ref != null)
 148             throw new InternalCompilerError("Method setRef should be called only for unbound meta variables.");
 149         Type thisSkeleton = Skeletons.canonicalSkeleton(this);
 150
 151         if(type instanceof TMetaVar) {
 152             TMetaVar other = (TMetaVar)type;
 153             if(other.ref != null)
 154                 throw new InternalCompilerError("Not canonical!");
 155
 156             Type typeSkeleton = Skeletons.canonicalSkeleton(type);
 157             if(thisSkeleton == typeSkeleton) {
 158                 if(skeletonRef != null)
 159                     setRefBase(type);
 160                 else
 161                     other.setRefBase(this);
 162                 return;
 163             }
 164             else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
 165                 throw new UnificationException(this, type);
 166         }
 167         else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
 168             throw new UnificationException(this, type);
 169
 170         // Common case
 171         if(skeletonRef != null) {
 172             Skeletons.unifySkeletons(thisSkeleton, type);
 173             if(ref != null) {
 174                 Types.unify(this, type);
 175                 return;
 176             }
 177         }
 178         setRefBase(type);
 179     }
 180
 181     private void setRefBase(Type type) throws UnificationException {
 182         skeletonRef = null;
 183         ref = type;
 184         if(polarity != Polarity.NO_POLARITY)
 185             type.addPolarity(polarity);
 186         //System.out.println("result = " + refStructure(this));
 187         //checkRefLoop(this);
 188         fireNotifyAboutChange();
 189     }
 190
 191     private static String refStructure(Type t) {
 192         StringBuilder b = new StringBuilder();
 193         IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
 194         refType(b, t, seenVars);
 195         return b.toString();
 196     }
 197
 198     private void refStructure(StringBuilder b, IdentityHashSet<TMetaVar> seenVars) {
 199         b.append(System.identityHashCode(this));
 200         if(!seenVars.add(this))
 201             b.append(" (loop)");
 202         else if(ref != null) {
 203             b.append(" => ");
 204             refType(b, ref, seenVars);
 205         }
 206         else if(skeletonRef != null) {
 207             b.append(" -> ");
 208             refType(b, skeletonRef, seenVars);
 209         }
 210         else
 211             b.append(" (canonical)");
 212     }
 213
 214     private static void refType(StringBuilder b, Type t, IdentityHashSet<TMetaVar> seenVars) {
 215         if(t instanceof TMetaVar)
 216             ((TMetaVar)t).refStructure(b, seenVars);
 217         else {
 218             b.append('[');
 219             t.toString(new TypeUnparsingContext(), b);
 220             b.append(']');
 221         }
 222     }
 223
 224     private void checkRefLoop(TMetaVar var) {
 225         IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
 226         StringBuilder b = new StringBuilder();
 227         while(true) {
 228             b.append(var);
 229             if(!seenVars.add(var))
 230                 throw new InternalCompilerError("Cyclic meta var references: " + b);
 231             if(var.ref != null) {
 232                 b.append(" => ");
 233                 if(var.ref instanceof TMetaVar)
 234                     var = (TMetaVar)var.ref;
 235                 else
 236                     return;
 237             }
 238             else if(var.skeletonRef != null) {
 239                 b.append(" -> ");
 240                 if(var.skeletonRef instanceof TMetaVar)
 241                     var = (TMetaVar)var.skeletonRef;
 242                 else
 243                     return;
 244             }
 245             else
 246                 return;
 247         }
 248     }
 249
 250     public Type getRef() {
 251         return ref;
 252     }
 253
 254     @Override
 255     public boolean contains(TMetaVar other) {
 256         if(ref != null)
 257             return ref.contains(other);
 258         else if(skeletonRef != null)
 259             return skeletonRef.contains(other);
 260         else
 261             return this == other;
 262     }
 263
 264     @Override
 265     public Type convertMetaVarsToVars() {
 266         if(ref == null) {
 267             if(kind == Kinds.EFFECT && !polarity.isNegative())
 268                 ref = Types.NO_EFFECTS;
 269             else
 270                 ref = Types.var(getKind());
 271             return ref;
 272         }
 273         else
 274             return ref.convertMetaVarsToVars();
 275     }
 276
 277     @Override
 278     public boolean isGround() {
 279         if(ref == null)
 280             return false;
 281         else
 282             return ref.isGround();
 283     }
 284
 285         public Kind inferKind(Environment context) throws KindUnificationException {
 286             return Kinds.metaVar();
 287     }
 288
 289     @Override
 290     public boolean containsMetaVars() {
 291         if(ref == null)
 292             return true;
 293         else
 294             return ref.containsMetaVars();
 295     }
 296
 297     @Override
 298     public void toName(TypeUnparsingContext context, StringBuilder b) {
 299         if(ref != null)
 300             ref.toName(context, b);
 301         else
 302             b.append(context.getName(this));
 303     }
 304
 305     @Override
 306     public int getClassId() {
 307         return METAVAR_ID;
 308     }
 309
 310     @Override
 311     public boolean isMaximal() {
 312         return ref != null && ref.isMaximal();
 313     }
 314
 315     @Override
 316     public boolean isMinimal() {
 317         return ref != null && ref.isMinimal();
 318     }
 319
 320     @Override
 321     public void addPolarity(Polarity polarity) {
 322         if(ref != null)
 323             ref.addPolarity(polarity);
 324         else
 325             this.polarity = this.polarity.add(polarity);
 326     }
 327
 328     public Polarity getPolarity() {
 329         return polarity;
 330     }
 331
 332     @Override
 333     public void collectConcreteEffects(ArrayList<TCon> concreteEffects) {
 334         if(ref != null)
 335             ref.collectConcreteEffects(concreteEffects);
 336     }
 337
 338     @Override
 339     public Type head() {
 340         if(ref != null)
 341             return ref.head();
 342         else
 343             return this;
 344     }
 345
 346     @Override
 347     public Type copySkeleton(THashMap<TMetaVar, TMetaVar> metaVarMap) {
 348         if(ref != null)
 349             return ref.copySkeleton(metaVarMap);
 350         else {
 351             TMetaVar result = metaVarMap.get(this);
 352             if(result == null) {
 353                 result = new TMetaVar(kind, polarity);
 354                 metaVarMap.put(this, result);
 355             }
 356             return result;
 357         }
 358     }
 359
 360     public void setSkeletonRef(Type type) throws UnificationException {
 361         if(DEBUG)
 362             System.out.println("setSkeletonRef " +  System.identityHashCode(this) + " -> " + type);
 363         if(ref != null || skeletonRef != null)
 364             throw new InternalCompilerError("Method setRef should be called only for unbound meta variables.");
 365         if(type.contains(this))
 366             throw new UnificationException(this, type);
 367         this.skeletonRef = type;
 368         //checkRefLoop(this);
 369         fireNotifyAboutChange();
 370     }
 371
 372     @Override
 373     public int hashCode() {
 374         if(ref == null)
 375             return System.identityHashCode(this);
 376         else
 377             return ref.hashCode();
 378     }
 379
 380     @Override
 381     public int hashCode(int hash) {
 382         if(ref == null)
 383             return HashCodeUtils.update(hash, System.identityHashCode(this));
 384         else
 385             return ref.hashCode(hash);
 386     }
 387
 388     @Override
 389     public int hashCode(int hash, TVar[] boundVars) {
 390         if(ref == null)
 391             return HashCodeUtils.update(hash, System.identityHashCode(this));
 392         else
 393             return ref.hashCode(hash, boundVars);
 394     }
 395
 396     @Override
 397     public int skeletonHashCode() {
 398         if(ref != null)
 399             return ref.skeletonHashCode();
 400         else if(skeletonRef != null)
 401             return skeletonRef.skeletonHashCode();
 402         else
 403             return System.identityHashCode(this);
 404     }
 405
 406     @Override
 407     public int skeletonHashCode(int hash) {
 408         if(ref != null)
 409             return ref.skeletonHashCode(hash);
 410         else if(skeletonRef != null)
 411             return skeletonRef.skeletonHashCode(hash);
 412         else
 413             return HashCodeUtils.update(hash, System.identityHashCode(this));
 414     }
 415
 416     @Override
 417     public int skeletonHashCode(int hash, TVar[] boundVars) {
 418         if(ref != null)
 419             return ref.skeletonHashCode(hash, boundVars);
 420         else if(skeletonRef != null)
 421             return skeletonRef.skeletonHashCode(hash, boundVars);
 422         else
 423             return HashCodeUtils.update(hash, System.identityHashCode(this));
 424     }
 425
 426     @Override
 427     public boolean equalsCanonical(Type other) {
 428         return this == other;
 429     }
 430
 431     @Override
 432     public Type canonical() {
 433         if(ref == null)
 434             return this;
 435         else
 436             return ref = ref.canonical();
 437     }
 438
 439     public void addListener(TMetaVarListener newListener) {
 440         if(DEBUG)
 441             System.out.println("addListener " + System.identityHashCode(this));
 442         newListener.next = listener;
 443         newListener.prev = this;
 444         if(listener != null)
 445             listener.prev = newListener;
 446         listener = newListener;
 447     }
 448
 449     private void fireNotifyAboutChange() {
 450         if(DEBUG)
 451             System.out.println("fireNotifyAboutChange " + System.identityHashCode(this) + " " + ref);
 452         TMetaVarListener cur = listener;
 453         listener = null;
 454         while(cur != null) {
 455             if(DEBUG)
 456                 System.out.println("    call listener");
 457             cur.prev = null; // This prevents TMetaVarListener.remove from doing anything
 458             cur.notifyAboutChange();
 459             TMetaVarListener next = cur.next;
 460             cur.next = null;
 461             cur = next;
 462         }
 463     }
 464
 465     public TMetaVarListener getLatestListener() {
 466         return listener;
 467     }
 468
 469     @Override
 470     public Kind getKind(Environment context) {
 471         return kind;
 472     }
 473
 474     @Override
 475     public Type[] skeletonCanonicalChildren() {
 476         // Assumes that this is already canonical skeleton
 477         return EMPTY_ARRAY;
 478     }
 479 }