bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/subsumption/SubSolver.java

   1 package org.simantics.scl.compiler.internal.elaboration.subsumption;\r
   2 \r
   3 import java.util.ArrayDeque;\r
   4 import java.util.ArrayList;\r
   5 \r
   6 import org.simantics.scl.compiler.errors.ErrorLog;\r
   7 import org.simantics.scl.compiler.errors.Locations;\r
   8 import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;\r
   9 import org.simantics.scl.compiler.types.TMetaVar;\r
  10 import org.simantics.scl.compiler.types.TUnion;\r
  11 import org.simantics.scl.compiler.types.Type;\r
  12 import org.simantics.scl.compiler.types.Types;\r
  13 import org.simantics.scl.compiler.types.util.Polarity;\r
  14 import org.simantics.scl.compiler.types.util.TypeUnparsingContext;\r
  15 \r
  16 import gnu.trove.map.hash.THashMap;\r
  17 import gnu.trove.set.hash.THashSet;\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