]> gerrit.simantics Code Review - simantics/platform.git/blob
34b34eccef4fc24e137634b2d433ce67e887c167
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.elaboration.subsumption;\r
2 \r
3 import gnu.trove.map.hash.THashMap;\r
4 import gnu.trove.set.hash.THashSet;\r
5 \r
6 import java.util.ArrayDeque;\r
7 import java.util.ArrayList;\r
8 \r
9 import org.simantics.scl.compiler.errors.ErrorLog;\r
10 import org.simantics.scl.compiler.errors.Locations;\r
11 import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;\r
12 import org.simantics.scl.compiler.types.TMetaVar;\r
13 import org.simantics.scl.compiler.types.TUnion;\r
14 import org.simantics.scl.compiler.types.Type;\r
15 import org.simantics.scl.compiler.types.Types;\r
16 import org.simantics.scl.compiler.types.util.Polarity;\r
17 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;\r
18 \r
19 public class SubSolver {\r
20 \r
21     public static final boolean DEBUG = false;\r
22     \r
23     long globalLoc;\r
24     ErrorLog errorLog;\r
25     ArrayList<Subsumption> subsumptions;\r
26     ArrayList<Type> potentialSingletonEffects;\r
27     EffectIdMap effectIds = new EffectIdMap();\r
28     THashMap<TMetaVar,Var> vars = new THashMap<TMetaVar,Var>();\r
29     ArrayDeque<Var> dirtyQueue = new ArrayDeque<Var>();\r
30     \r
31     TypeUnparsingContext tuc = new TypeUnparsingContext();\r
32     \r
33     public SubSolver(ErrorLog errorLog, ArrayList<Subsumption> subsumptions,\r
34             ArrayList<Type> potentialSingletonEffects,\r
35             long globalLoc) {\r
36         this.errorLog = errorLog;\r
37         this.subsumptions = subsumptions;\r
38         this.potentialSingletonEffects = potentialSingletonEffects;\r
39         this.globalLoc = globalLoc;\r
40         \r
41         //for(Subsumption sub : subsumptions)\r
42         //    System.out.println("[" + sub.a.toString(tuc) + " < " + sub.b.toString(tuc) + "]");\r
43     }    \r
44     \r
45     public void solve() {\r
46         //printSubsumptions();\r
47         createVar();\r
48         //print();\r
49         reduceChains();\r
50         propagateUpperBounds();\r
51         checkLowerBounds();\r
52         errorFromUnsolvedEquations();\r
53         //System.out.println("--");\r
54         //print();\r
55     }\r
56     \r
57     private void markAllDirty() {\r
58         for(Var v : vars.values())\r
59             v.markDirty();\r
60     }\r
61     \r
62     private Var getOrCreateVar(TMetaVar mv) {\r
63         Var var = vars.get(mv);\r
64         if(var == null) {\r
65             var = new Var(mv, mv.toString(tuc).substring(1), this);\r
66             vars.put(mv, var);\r
67         }\r
68         return var;\r
69     }\r
70 \r
71     private void addVar(Type t) {\r
72         t = Types.canonical(t);\r
73         if(t instanceof TMetaVar)\r
74             getOrCreateVar((TMetaVar)t);\r
75         else if(t instanceof TUnion)\r
76             for(Type c : ((TUnion)t).effects)\r
77                 addVar(c);\r
78     }\r
79 \r
80     ArrayList<TMetaVar> aVars = new ArrayList<TMetaVar>();\r
81     \r
82     private void addSubsumption(long loc, Type a, Type b) {\r
83         int aCons = effectIds.toId(a, aVars);\r
84         if(!aVars.isEmpty()) {\r
85             for(TMetaVar var : aVars)\r
86                 getOrCreateVar((TMetaVar)var).addUpperBound(toVUnion(b));\r
87             aVars.clear();\r
88         }        \r
89         if(aCons != 0) {\r
90             VUnion u = toVUnion(b);\r
91             if(u.vars.isEmpty()) {\r
92                 testSubsumption(loc, aCons, u.con);\r
93             }\r
94             else\r
95                 u.makeLowerBound(aCons);\r
96         }\r
97     }\r
98 \r
99     ArrayList<TMetaVar> bVars = new ArrayList<TMetaVar>();\r
100     \r
101     private VUnion toVUnion(Type a) {\r
102         int cons = effectIds.toId(a, bVars);\r
103         ArrayList<Var> vars = new ArrayList<Var>(bVars.size());\r
104         for(TMetaVar v : bVars)\r
105             vars.add(getOrCreateVar(v));\r
106         bVars.clear();\r
107         return new VUnion(cons, vars);\r
108     }\r
109 \r
110     private void createVar() {\r
111         for(Subsumption sub : subsumptions)\r
112             addSubsumption(sub.loc, sub.a, sub.b);\r
113         for(Type t : potentialSingletonEffects)\r
114             addVar(t);\r
115     }\r
116     \r
117     private void reduceChains() {\r
118         markAllDirty();\r
119         while(true) {\r
120             Var v = dirtyQueue.poll();\r
121             if(v == null)\r
122                 break;\r
123             \r
124             reduceChains(v);\r
125             v.dirty = false;\r
126         }\r
127     }\r
128     \r
129     private void reduceChains(Var v) {\r
130         if(v.constLowerBound == v.constUpperBound) {\r
131             v.replaceWith(v.constLowerBound);\r
132             return;\r
133         }\r
134         Polarity p = v.original.getPolarity();\r
135         if(!p.isNegative() && v.complexLowerBounds.isEmpty()) {\r
136             if(v.simpleLowerBounds.isEmpty()) {\r
137                 if((v.constLowerBound&v.constUpperBound) != v.constLowerBound)\r
138                     errorLog.log(globalLoc, "Subsumption failed.");\r
139                 v.replaceWith(v.constLowerBound);\r
140                 return;\r
141             }\r
142             else if(v.simpleLowerBounds.size() == 1 && v.constLowerBound == 0) {\r
143                 v.replaceDownwards(v.simpleLowerBounds.get(0));\r
144                 return;\r
145             }\r
146         }\r
147         if(p == Polarity.NEGATIVE && v.complexUpperBounds.isEmpty()) {\r
148             if(v.simpleUpperBounds.isEmpty()) {\r
149                 if((v.constLowerBound&v.constUpperBound) != v.constLowerBound)\r
150                     errorLog.log(globalLoc, "Subsumption failed.");\r
151                 v.replaceWith(v.constUpperBound);\r
152                 return;\r
153             }\r
154             else if(v.simpleUpperBounds.size() == 1 && v.constUpperBound == EffectIdMap.MAX) {\r
155                 v.replaceUpwards(v.simpleUpperBounds.get(0));\r
156                 return;\r
157             }\r
158         }\r
159     }\r
160     \r
161     private void propagateUpperBounds() {\r
162         markAllDirty();        \r
163         while(true) {\r
164             Var v = dirtyQueue.poll();\r
165             if(v == null)\r
166                 break;\r
167             \r
168             int upperApprox = v.constUpperBound;\r
169             for(Var u : v.simpleUpperBounds)\r
170                 upperApprox &= u.upperApprox;\r
171             for(VUnion u : v.complexUpperBounds)\r
172                 upperApprox &= u.getUpperApprox();\r
173             \r
174             if(upperApprox != v.upperApprox) {\r
175                 v.upperApprox = upperApprox;\r
176                 for(Var u : v.simpleLowerBounds)\r
177                     u.markDirty();\r
178                 for(VUnion u : v.complexLowerBounds)\r
179                     if(u.low != null)\r
180                         u.low.markDirty();\r
181             }   \r
182             \r
183             v.dirty = false;\r
184         }\r
185     }\r
186     \r
187     private void checkLowerBounds() {\r
188         THashSet<VUnion> lowerBounds = new THashSet<VUnion>(); \r
189         for(Var v : vars.values()) {\r
190             if((v.constLowerBound & v.upperApprox) != v.constLowerBound)\r
191                 testSubsumption(globalLoc, v.constLowerBound, v.upperApprox);\r
192             for(VUnion u : v.complexLowerBounds)\r
193                 if(u.low == null)\r
194                     lowerBounds.add(u);\r
195         }\r
196         for(VUnion u : lowerBounds)\r
197             if(u.getUpperApprox() != EffectIdMap.MAX)\r
198                 errorLog.log(globalLoc, "Subsumption failed.");\r
199     }\r
200 \r
201     private void errorFromUnsolvedEquations() {\r
202         for(Var v : vars.values()) {\r
203             if(!v.isFree()) {\r
204                 errorLog.log(globalLoc, "Couldn't simplify all effect subsumptions away. " +\r
205                                 "The current compiler cannot handle this situation. Try adding more type annotations.");\r
206                 break;\r
207             }\r
208         }\r
209     }\r
210     \r
211     private void print() {\r
212         for(Var v : vars.values()) {\r
213             System.out.println(v.name + \r
214                     ", " + v.original.getPolarity() + \r
215                     (v.simpleLowerBounds.isEmpty() ? "" : ", simpleLowerRefs: " + v.simpleLowerBounds.size()) +  \r
216                     (v.complexLowerBounds.isEmpty() ? "" : ", complexLowerRefs: " + v.complexLowerBounds.size()) +\r
217                     ", " + v.original.getKind());\r
218             if(v.constLowerBound != EffectIdMap.MIN)\r
219                 System.out.println("    > " + v.constLowerBound);\r
220             if(v.constUpperBound != EffectIdMap.MAX)\r
221                 System.out.println("    < " + v.constUpperBound);\r
222             for(Var u : v.simpleUpperBounds)\r
223                 System.out.println("    < " + u.name);\r
224             for(VUnion u : v.complexUpperBounds)\r
225                 System.out.println("    << " + u);\r
226         }\r
227     }\r
228     \r
229     private void printSubsumptions() {\r
230         for(Subsumption sub : subsumptions)\r
231             System.out.println("[" + sub.a.toString(tuc) + " < " + sub.b.toString(tuc) + " : " + \r
232                     Locations.beginOf(sub.loc) + "," + Locations.endOf(sub.loc) + "]");\r
233     }\r
234 \r
235     private void testSubsumption(long location, int a, int b) {\r
236         int extraEffects = a & (~b);\r
237         if(extraEffects != 0)\r
238             subsumptionFailed(location, extraEffects);\r
239     }\r
240     \r
241     private void subsumptionFailed(long location , int effects) {\r
242         errorLog.log(location, "Side-effect " + effectIds.toType(effects) + " is forbidden here.");\r
243     }\r
244 }\r