1 package org.simantics.scl.compiler.internal.elaboration.subsumption;
3 import java.util.ArrayDeque;
4 import java.util.ArrayList;
6 import org.simantics.scl.compiler.errors.ErrorLog;
7 import org.simantics.scl.compiler.errors.Locations;
8 import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;
9 import org.simantics.scl.compiler.types.TMetaVar;
10 import org.simantics.scl.compiler.types.TUnion;
11 import org.simantics.scl.compiler.types.Type;
12 import org.simantics.scl.compiler.types.Types;
13 import org.simantics.scl.compiler.types.util.Polarity;
14 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;
16 import gnu.trove.map.hash.THashMap;
17 import gnu.trove.set.hash.THashSet;
19 public class SubSolver {
21 public static final boolean DEBUG = false;
25 ArrayList<Subsumption> subsumptions;
26 ArrayList<Type> potentialSingletonEffects;
27 EffectIdMap effectIds = new EffectIdMap();
28 THashMap<TMetaVar,Var> vars = new THashMap<TMetaVar,Var>();
29 ArrayDeque<Var> dirtyQueue = new ArrayDeque<Var>();
31 TypeUnparsingContext tuc = new TypeUnparsingContext();
33 public SubSolver(ErrorLog errorLog, ArrayList<Subsumption> subsumptions,
34 ArrayList<Type> potentialSingletonEffects,
36 this.errorLog = errorLog;
37 this.subsumptions = subsumptions;
38 this.potentialSingletonEffects = potentialSingletonEffects;
39 this.globalLoc = globalLoc;
41 //for(Subsumption sub : subsumptions)
42 // System.out.println("[" + sub.a.toString(tuc) + " < " + sub.b.toString(tuc) + "]");
46 //printSubsumptions();
50 propagateUpperBounds();
52 //errorFromUnsolvedEquations();
53 //System.out.println("--");
57 private void markAllDirty() {
58 for(Var v : vars.values())
62 private Var getOrCreateVar(TMetaVar mv) {
63 Var var = vars.get(mv);
65 var = new Var(mv, mv.toString(tuc).substring(1), this);
71 private void addVar(Type t) {
72 t = Types.canonical(t);
73 if(t instanceof TMetaVar)
74 getOrCreateVar((TMetaVar)t);
75 else if(t instanceof TUnion)
76 for(Type c : ((TUnion)t).effects)
80 ArrayList<TMetaVar> aVars = new ArrayList<TMetaVar>();
82 private void addSubsumption(long loc, Type a, Type b) {
83 int aCons = effectIds.toId(a, aVars);
84 if(!aVars.isEmpty()) {
85 for(TMetaVar var : aVars)
86 getOrCreateVar((TMetaVar)var).addUpperBound(toVUnion(b));
90 VUnion u = toVUnion(b);
91 if(u.vars.isEmpty()) {
92 testSubsumption(loc, aCons, u.con);
95 u.makeLowerBound(aCons);
99 ArrayList<TMetaVar> bVars = new ArrayList<TMetaVar>();
101 private VUnion toVUnion(Type a) {
102 int cons = effectIds.toId(a, bVars);
103 ArrayList<Var> vars = new ArrayList<Var>(bVars.size());
104 for(TMetaVar v : bVars)
105 vars.add(getOrCreateVar(v));
107 return new VUnion(cons, vars);
110 private void createVar() {
111 for(Subsumption sub : subsumptions)
112 addSubsumption(sub.loc, sub.a, sub.b);
113 for(Type t : potentialSingletonEffects)
117 private void reduceChains() {
120 Var v = dirtyQueue.poll();
129 private void reduceChains(Var v) {
130 if(v.constLowerBound == v.constUpperBound) {
131 v.replaceWith(v.constLowerBound);
134 Polarity p = v.original.getPolarity();
135 if(!p.isNegative() && v.complexLowerBounds.isEmpty()) {
136 if(v.simpleLowerBounds.isEmpty()) {
137 if((v.constLowerBound&v.constUpperBound) != v.constLowerBound)
138 errorLog.log(globalLoc, "Subsumption failed.");
139 v.replaceWith(v.constLowerBound);
142 else if(v.simpleLowerBounds.size() == 1 && v.constLowerBound == 0) {
143 v.replaceDownwards(v.simpleLowerBounds.get(0));
147 if(p == Polarity.NEGATIVE && v.complexUpperBounds.isEmpty()) {
148 if(v.simpleUpperBounds.isEmpty()) {
149 if((v.constLowerBound&v.constUpperBound) != v.constLowerBound)
150 errorLog.log(globalLoc, "Subsumption failed.");
151 v.replaceWith(v.constUpperBound);
154 else if(v.simpleUpperBounds.size() == 1 && v.constUpperBound == EffectIdMap.MAX) {
155 v.replaceUpwards(v.simpleUpperBounds.get(0));
161 private void propagateUpperBounds() {
164 Var v = dirtyQueue.poll();
168 int upperApprox = v.constUpperBound;
169 for(Var u : v.simpleUpperBounds)
170 upperApprox &= u.upperApprox;
171 for(VUnion u : v.complexUpperBounds)
172 upperApprox &= u.getUpperApprox();
174 if(upperApprox != v.upperApprox) {
175 v.upperApprox = upperApprox;
176 for(Var u : v.simpleLowerBounds)
178 for(VUnion u : v.complexLowerBounds)
187 private void checkLowerBounds() {
188 THashSet<VUnion> lowerBounds = new THashSet<VUnion>();
189 for(Var v : vars.values()) {
190 if((v.constLowerBound & v.upperApprox) != v.constLowerBound)
191 testSubsumption(globalLoc, v.constLowerBound, v.upperApprox);
192 for(VUnion u : v.complexLowerBounds)
196 for(VUnion u : lowerBounds)
197 if(u.getUpperApprox() != EffectIdMap.MAX)
198 errorLog.log(globalLoc, "Subsumption failed.");
201 private void errorFromUnsolvedEquations() {
202 for(Var v : vars.values()) {
204 errorLog.log(globalLoc, "Couldn't simplify all effect subsumptions away. " +
205 "The current compiler cannot handle this situation. Try adding more type annotations.");
211 private void print() {
212 for(Var v : vars.values()) {
213 System.out.println(v.name +
214 ", " + v.original.getPolarity() +
215 (v.simpleLowerBounds.isEmpty() ? "" : ", simpleLowerRefs: " + v.simpleLowerBounds.size()) +
216 (v.complexLowerBounds.isEmpty() ? "" : ", complexLowerRefs: " + v.complexLowerBounds.size()) +
217 ", " + v.original.getKind());
218 if(v.constLowerBound != EffectIdMap.MIN)
219 System.out.println(" > " + v.constLowerBound);
220 if(v.constUpperBound != EffectIdMap.MAX)
221 System.out.println(" < " + v.constUpperBound);
222 for(Var u : v.simpleUpperBounds)
223 System.out.println(" < " + u.name);
224 for(VUnion u : v.complexUpperBounds)
225 System.out.println(" << " + u);
229 private void printSubsumptions() {
230 for(Subsumption sub : subsumptions)
231 System.out.println("[" + sub.a.toString(tuc) + " < " + sub.b.toString(tuc) + " : " +
232 Locations.beginOf(sub.loc) + "," + Locations.endOf(sub.loc) + "]");
235 private void testSubsumption(long location, int a, int b) {
236 int extraEffects = a & (~b);
237 if(extraEffects != 0)
238 subsumptionFailed(location, extraEffects);
241 private void subsumptionFailed(long location , int effects) {
242 errorLog.log(location, "Side-effect " + effectIds.toType(effects) + " is forbidden here.");