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 new TVarAst(/*polarity.getSymbol() +*/ context.getName(this));
98 return ref.toTypeAst(context);
102 public void updateHashCode(TypeHashCodeContext context) {
104 context.append(System.identityHashCode(this));
106 ref.updateHashCode(context);
110 public void collectFreeVars(ArrayList<TVar> vars) {
112 ref.collectFreeVars(vars);
116 public void collectMetaVars(ArrayList<TMetaVar> vars) {
120 ref.collectMetaVars(vars);
124 public void collectMetaVars(THashSet<TMetaVar> vars) {
128 ref.collectMetaVars(vars);
132 public void collectEffectMetaVars(ArrayList<TMetaVar> vars) {
134 ref.collectEffectMetaVars(vars);
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));
142 throw new InternalCompilerError("Illegal setRef");
144 System.out.println("setRef " + System.identityHashCode(this) + " -> " + type);
146 throw new InternalCompilerError("Method setRef should be called only for unbound meta variables.");
147 Type thisSkeleton = Skeletons.canonicalSkeleton(this);
149 if(type instanceof TMetaVar) {
150 TMetaVar other = (TMetaVar)type;
151 if(other.ref != null)
152 throw new InternalCompilerError("Not canonical!");
154 Type typeSkeleton = Skeletons.canonicalSkeleton(type);
155 if(thisSkeleton == typeSkeleton) {
156 if(skeletonRef != null)
159 other.setRefBase(this);
162 else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
163 throw new UnificationException(this, type);
165 else if(thisSkeleton instanceof TMetaVar && type.contains((TMetaVar)thisSkeleton))
166 throw new UnificationException(this, type);
169 if(skeletonRef != null) {
170 Skeletons.unifySkeletons(thisSkeleton, type);
175 private void setRefBase(Type type) throws UnificationException {
178 if(polarity != Polarity.NO_POLARITY)
179 type.addPolarity(polarity);
180 //System.out.println("result = " + refStructure(this));
181 //checkRefLoop(this);
182 fireNotifyAboutChange();
185 private static String refStructure(Type t) {
186 StringBuilder b = new StringBuilder();
187 IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
188 refType(b, t, seenVars);
192 private void refStructure(StringBuilder b, IdentityHashSet<TMetaVar> seenVars) {
193 b.append(System.identityHashCode(this));
194 if(!seenVars.add(this))
196 else if(ref != null) {
198 refType(b, ref, seenVars);
200 else if(skeletonRef != null) {
202 refType(b, skeletonRef, seenVars);
205 b.append(" (canonical)");
208 private static void refType(StringBuilder b, Type t, IdentityHashSet<TMetaVar> seenVars) {
209 if(t instanceof TMetaVar)
210 ((TMetaVar)t).refStructure(b, seenVars);
213 t.toString(new TypeUnparsingContext(), b);
218 private void checkRefLoop(TMetaVar var) {
219 IdentityHashSet<TMetaVar> seenVars = new IdentityHashSet<TMetaVar>();
220 StringBuilder b = new StringBuilder();
223 if(!seenVars.add(var))
224 throw new InternalCompilerError("Cyclic meta var references: " + b);
225 if(var.ref != null) {
227 if(var.ref instanceof TMetaVar)
228 var = (TMetaVar)var.ref;
232 else if(var.skeletonRef != null) {
234 if(var.skeletonRef instanceof TMetaVar)
235 var = (TMetaVar)var.skeletonRef;
244 public Type getRef() {
249 public boolean contains(TMetaVar other) {
251 return ref.contains(other);
252 else if(skeletonRef != null)
253 return skeletonRef.contains(other);
255 return this == other;
259 public Type convertMetaVarsToVars() {
261 if(kind == Kinds.EFFECT && !polarity.isNegative())
262 ref = Types.NO_EFFECTS;
264 ref = Types.var(getKind());
268 return ref.convertMetaVarsToVars();
272 public boolean isGround() {
276 return ref.isGround();
279 public Kind inferKind(Environment context) throws KindUnificationException {
280 return Kinds.metaVar();
284 public boolean containsMetaVars() {
288 return ref.containsMetaVars();
292 public void toName(TypeUnparsingContext context, StringBuilder b) {
294 ref.toName(context, b);
296 b.append(context.getName(this));
300 public int getClassId() {
305 public boolean isMaximal() {
306 return ref != null && ref.isMaximal();
310 public boolean isMinimal() {
311 return ref != null && ref.isMinimal();
315 public void addPolarity(Polarity polarity) {
317 ref.addPolarity(polarity);
319 this.polarity = this.polarity.add(polarity);
322 public Polarity getPolarity() {
327 public void collectConcreteEffects(ArrayList<TCon> concreteEffects) {
329 ref.collectConcreteEffects(concreteEffects);
341 public Type copySkeleton(THashMap<TMetaVar, TMetaVar> metaVarMap) {
343 return ref.copySkeleton(metaVarMap);
345 TMetaVar result = metaVarMap.get(this);
347 result = new TMetaVar(kind, polarity);
348 metaVarMap.put(this, result);
354 public void setSkeletonRef(Type type) throws UnificationException {
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();
367 public int hashCode() {
369 return System.identityHashCode(this);
371 return ref.hashCode();
375 public int hashCode(int hash) {
377 return HashCodeUtils.update(hash, System.identityHashCode(this));
379 return ref.hashCode(hash);
383 public int hashCode(int hash, TVar[] boundVars) {
385 return HashCodeUtils.update(hash, System.identityHashCode(this));
387 return ref.hashCode(hash, boundVars);
391 public int skeletonHashCode() {
393 return ref.skeletonHashCode();
394 else if(skeletonRef != null)
395 return skeletonRef.skeletonHashCode();
397 return System.identityHashCode(this);
401 public int skeletonHashCode(int hash) {
403 return ref.skeletonHashCode(hash);
404 else if(skeletonRef != null)
405 return skeletonRef.skeletonHashCode(hash);
407 return HashCodeUtils.update(hash, System.identityHashCode(this));
411 public int skeletonHashCode(int hash, TVar[] boundVars) {
413 return ref.skeletonHashCode(hash, boundVars);
414 else if(skeletonRef != null)
415 return skeletonRef.skeletonHashCode(hash, boundVars);
417 return HashCodeUtils.update(hash, System.identityHashCode(this));
421 public boolean equalsCanonical(Type other) {
422 return this == other;
426 public Type canonical() {
430 return ref = ref.canonical();
433 public void addListener(TMetaVarListener newListener) {
435 System.out.println("addListener " + System.identityHashCode(this));
436 newListener.next = listener;
437 newListener.prev = this;
439 listener.prev = newListener;
440 listener = newListener;
443 private void fireNotifyAboutChange() {
445 System.out.println("fireNotifyAboutChange " + System.identityHashCode(this) + " " + ref);
446 TMetaVarListener cur = listener;
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;
459 public TMetaVarListener getLatestListener() {
464 public Kind getKind(Environment context) {
469 public Type[] skeletonCanonicalChildren() {
470 // Assumes that this is already canonical skeleton