1 package org.simantics.scl.compiler.types;
3 import java.util.ArrayList;
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;
20 import gnu.trove.map.hash.THashMap;
21 import gnu.trove.set.hash.THashSet;
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.
30 * @author Hannu Niemistö
32 public class TMetaVar extends Type {
33 public static final TMetaVar[] EMPTY_ARRAY = new TMetaVar[0];
34 public static final boolean DEBUG = false;
37 Type skeletonRef = null;
38 Polarity polarity = Polarity.NO_POLARITY;
40 private TMetaVarListener listener;
42 public static abstract class TMetaVarListener {
43 private Object prev; // TMetaVarListener or TMetaVar
44 private TMetaVarListener next;
46 public abstract void notifyAboutChange();
48 public void remove() {
50 return; // Not added or not anymore listening TMetaVar
51 if(prev instanceof TMetaVar)
52 ((TMetaVar)prev).listener = next;
54 ((TMetaVarListener)prev).next = next;
67 TMetaVar(Kind kind, Polarity polarity) {
69 this.polarity = polarity;
72 public Kind getKind() {
73 if(kind instanceof KMetaVar)
74 kind = Kinds.canonical(kind);
79 public Type replace(TVar var, Type replacement) {
83 Type newRef = ref.replace(var, replacement);
87 // We could also return newRef here, but in this way
88 // we don't have to copy so many parent types.
94 public TypeAst toTypeAst(TypeUnparsingContext context) {
96 return ref.toTypeAst(context);
97 else if(context.showSkeletons && skeletonRef != null)
98 return skeletonRef.toTypeAst(context);
100 return new TVarAst(/*polarity.getSymbol() +*/ context.getName(this));
104 public void updateHashCode(TypeHashCodeContext context) {
106 context.append(System.identityHashCode(this));
108 ref.updateHashCode(context);
112 public void collectFreeVars(ArrayList<TVar> vars) {
114 ref.collectFreeVars(vars);
118 public void collectMetaVars(ArrayList<TMetaVar> vars) {
122 ref.collectMetaVars(vars);
126 public void collectMetaVars(THashSet<TMetaVar> vars) {
130 ref.collectMetaVars(vars);
134 public void collectEffectMetaVars(ArrayList<TMetaVar> vars) {
136 ref.collectEffectMetaVars(vars);
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));
144 throw new InternalCompilerError("Illegal setRef");
146 System.out.println("setRef " + System.identityHashCode(this) + " -> " + type);
148 throw new InternalCompilerError("Method setRef should be called only for unbound meta variables.");
149 Type thisSkeleton = Skeletons.canonicalSkeleton(this);
151 if(type instanceof TMetaVar) {
152 TMetaVar other = (TMetaVar)type;
153 if(other.ref != null)
154 throw new InternalCompilerError("Not canonical!");
156 Type typeSkeleton = Skeletons.canonicalSkeleton(type);
157 if(thisSkeleton == typeSkeleton) {
158 if(skeletonRef != null)
161 other.setRefBase(this);
164 else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
165 throw new UnificationException(this, type);
167 else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
168 throw new UnificationException(this, type);
171 if(skeletonRef != null) {
172 Skeletons.unifySkeletons(thisSkeleton, type);
174 Types.unify(this, type);
181 private void setRefBase(Type type) throws UnificationException {
184 if(polarity != Polarity.NO_POLARITY)
185 type.addPolarity(polarity);
186 //System.out.println("result = " + refStructure(this));
187 //checkRefLoop(this);
188 fireNotifyAboutChange();
191 private static String refStructure(Type t) {
192 StringBuilder b = new StringBuilder();
193 IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
194 refType(b, t, seenVars);
198 private void refStructure(StringBuilder b, IdentityHashSet<TMetaVar> seenVars) {
199 b.append(System.identityHashCode(this));
200 if(!seenVars.add(this))
202 else if(ref != null) {
204 refType(b, ref, seenVars);
206 else if(skeletonRef != null) {
208 refType(b, skeletonRef, seenVars);
211 b.append(" (canonical)");
214 private static void refType(StringBuilder b, Type t, IdentityHashSet<TMetaVar> seenVars) {
215 if(t instanceof TMetaVar)
216 ((TMetaVar)t).refStructure(b, seenVars);
219 t.toString(new TypeUnparsingContext(), b);
224 private void checkRefLoop(TMetaVar var) {
225 IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
226 StringBuilder b = new StringBuilder();
229 if(!seenVars.add(var))
230 throw new InternalCompilerError("Cyclic meta var references: " + b);
231 if(var.ref != null) {
233 if(var.ref instanceof TMetaVar)
234 var = (TMetaVar)var.ref;
238 else if(var.skeletonRef != null) {
240 if(var.skeletonRef instanceof TMetaVar)
241 var = (TMetaVar)var.skeletonRef;
250 public Type getRef() {
255 public boolean contains(TMetaVar other) {
257 return ref.contains(other);
258 else if(skeletonRef != null)
259 return skeletonRef.contains(other);
261 return this == other;
265 public Type convertMetaVarsToVars() {
267 if(kind == Kinds.EFFECT && !polarity.isNegative())
268 ref = Types.NO_EFFECTS;
270 ref = Types.var(getKind());
274 return ref.convertMetaVarsToVars();
278 public boolean isGround() {
282 return ref.isGround();
285 public Kind inferKind(Environment context) throws KindUnificationException {
286 return Kinds.metaVar();
290 public boolean containsMetaVars() {
294 return ref.containsMetaVars();
298 public void toName(TypeUnparsingContext context, StringBuilder b) {
300 ref.toName(context, b);
302 b.append(context.getName(this));
306 public int getClassId() {
311 public boolean isMaximal() {
312 return ref != null && ref.isMaximal();
316 public boolean isMinimal() {
317 return ref != null && ref.isMinimal();
321 public void addPolarity(Polarity polarity) {
323 ref.addPolarity(polarity);
325 this.polarity = this.polarity.add(polarity);
328 public Polarity getPolarity() {
333 public void collectConcreteEffects(ArrayList<TCon> concreteEffects) {
335 ref.collectConcreteEffects(concreteEffects);
347 public Type copySkeleton(THashMap<TMetaVar, TMetaVar> metaVarMap) {
349 return ref.copySkeleton(metaVarMap);
351 TMetaVar result = metaVarMap.get(this);
353 result = new TMetaVar(kind, polarity);
354 metaVarMap.put(this, result);
360 public void setSkeletonRef(Type type) throws UnificationException {
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();
373 public int hashCode() {
375 return System.identityHashCode(this);
377 return ref.hashCode();
381 public int hashCode(int hash) {
383 return HashCodeUtils.update(hash, System.identityHashCode(this));
385 return ref.hashCode(hash);
389 public int hashCode(int hash, TVar[] boundVars) {
391 return HashCodeUtils.update(hash, System.identityHashCode(this));
393 return ref.hashCode(hash, boundVars);
397 public int skeletonHashCode() {
399 return ref.skeletonHashCode();
400 else if(skeletonRef != null)
401 return skeletonRef.skeletonHashCode();
403 return System.identityHashCode(this);
407 public int skeletonHashCode(int hash) {
409 return ref.skeletonHashCode(hash);
410 else if(skeletonRef != null)
411 return skeletonRef.skeletonHashCode(hash);
413 return HashCodeUtils.update(hash, System.identityHashCode(this));
417 public int skeletonHashCode(int hash, TVar[] boundVars) {
419 return ref.skeletonHashCode(hash, boundVars);
420 else if(skeletonRef != null)
421 return skeletonRef.skeletonHashCode(hash, boundVars);
423 return HashCodeUtils.update(hash, System.identityHashCode(this));
427 public boolean equalsCanonical(Type other) {
428 return this == other;
432 public Type canonical() {
436 return ref = ref.canonical();
439 public void addListener(TMetaVarListener newListener) {
441 System.out.println("addListener " + System.identityHashCode(this));
442 newListener.next = listener;
443 newListener.prev = this;
445 listener.prev = newListener;
446 listener = newListener;
449 private void fireNotifyAboutChange() {
451 System.out.println("fireNotifyAboutChange " + System.identityHashCode(this) + " " + ref);
452 TMetaVarListener cur = listener;
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;
465 public TMetaVarListener getLatestListener() {
470 public Kind getKind(Environment context) {
475 public Type[] skeletonCanonicalChildren() {
476 // Assumes that this is already canonical skeleton