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

   1 package org.simantics.scl.compiler.internal.elaboration.subsumption;\r
   2 \r
   3 import java.util.ArrayList;\r
   4 \r
   5 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
   6 import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;\r
   7 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;\r
   8 import org.simantics.scl.compiler.types.TMetaVar;\r
   9 import org.simantics.scl.compiler.types.Type;\r
  10 import org.simantics.scl.compiler.types.exceptions.UnificationException;\r
  11 \r
  12 public class Var {\r
  13     String name;\r
  14     \r
  15     int constLowerBound = EffectIdMap.MIN;\r
  16     int constUpperBound = EffectIdMap.MAX;\r
  17     int upperApprox = EffectIdMap.MAX;\r
  18     TMetaVar original;\r
  19     \r
  20     ArrayList<Var> simpleLowerBounds = new ArrayList<Var>();\r
  21     ArrayList<Var> simpleUpperBounds = new ArrayList<Var>();\r
  22     ArrayList<VUnion> complexLowerBounds = new ArrayList<VUnion>();\r
  23     ArrayList<VUnion> complexUpperBounds = new ArrayList<VUnion>();\r
  24     \r
  25     SubSolver solver;\r
  26     boolean dirty;\r
  27     \r
  28     public Var(TMetaVar original, String name, SubSolver solver) {\r
  29         this.original = original;\r
  30         this.name = name;\r
  31         this.solver = solver;        \r
  32         markDirty();\r
  33     }\r
  34 \r
  35     void markDirty() {\r
  36         if(!dirty) {\r
  37             dirty = true;\r
  38             solver.dirtyQueue.add(this);\r
  39         }\r
  40     }\r
  41     \r
  42     /**\r
  43      * Adds a constant constraint\r
  44      */\r
  45     public void addUpperBound(int c) {\r
  46         c &= constUpperBound;\r
  47         if(c != constUpperBound) {\r
  48             if((c & constLowerBound) != constLowerBound) {\r
  49                 solver.errorLog.log(solver.globalLoc, "Subsumption failed: " + \r
  50                         solver.effectIds.toType(constLowerBound) + " is not a subtype of " +\r
  51                         solver.effectIds.toType(c)\r
  52                         );\r
  53                 return;\r
  54             }\r
  55             constUpperBound = c;\r
  56             for(int i=0;i<complexUpperBounds.size();++i) {\r
  57                 VUnion u = complexUpperBounds.get(i); \r
  58                 u.con &= c;\r
  59                 if(u.con == 0 && u.vars.size() == 1) {\r
  60                     removeComplexUpperBound(i);               \r
  61                     --i;\r
  62                     addUpperBound(u.vars.get(0));\r
  63                 }\r
  64             }\r
  65             markDirty();\r
  66         }\r
  67     }\r
  68     \r
  69     public void addLowerBound(int c) {\r
  70         if((c | constUpperBound) != constUpperBound) {\r
  71             solver.errorLog.log(solver.globalLoc, "Subsumption failed: " + \r
  72                     solver.effectIds.toType(c) + " is not a subtype of " +\r
  73                     solver.effectIds.toType(constUpperBound)\r
  74                     );\r
  75             return;\r
  76         }\r
  77         constLowerBound |= c;\r
  78         markDirty();\r
  79     }\r
  80     \r
  81     private void removeComplexUpperBound(int i) {\r
  82         VUnion u = complexUpperBounds.get(i);\r
  83         int lastId = complexUpperBounds.size()-1;        \r
  84         VUnion last = complexUpperBounds.remove(lastId);\r
  85         if(i < lastId)\r
  86             complexUpperBounds.set(i, last);\r
  87         for(Var v : u.vars) {\r
  88             v.complexLowerBounds.remove(u);\r
  89             v.markDirty();\r
  90         }\r
  91     }\r
  92     \r
  93     /**\r
  94      * Adds a simple variable constraint\r
  95      */\r
  96     public void addUpperBound(Var var) {\r
  97         if(var == this)\r
  98             return;\r
  99         if(simpleUpperBounds.size() < var.simpleLowerBounds.size()) {\r
 100             if(simpleUpperBounds.contains(var))\r
 101                 return;\r
 102         }\r
 103         else {\r
 104             if(var.simpleLowerBounds.contains(this))\r
 105                 return;\r
 106         }\r
 107         \r
 108         for(int i=0;i<complexUpperBounds.size();++i)\r
 109             if(complexUpperBounds.get(i).vars.contains(var)) {\r
 110                 removeComplexUpperBound(i);               \r
 111                 --i;\r
 112             }\r
 113         \r
 114         simpleUpperBounds.add(var);\r
 115         var.simpleLowerBounds.add(this);\r
 116         \r
 117         markDirty();\r
 118         var.markDirty();\r
 119     }\r
 120     \r
 121     /**\r
 122      * Adds a complex constraint\r
 123      */\r
 124     public void addUpperBound(VUnion u) {\r
 125         if(u.vars.isEmpty()) {\r
 126             addUpperBound(u.con);\r
 127             return;\r
 128         }        \r
 129         if(u.vars.contains(this))\r
 130             return;        \r
 131         for(Var v : u.vars)\r
 132             if(simpleUpperBounds.contains(v))\r
 133                 return;\r
 134         u.con &= constUpperBound;\r
 135         if(u.con == constUpperBound)\r
 136             return;\r
 137         if(u.con == 0 && u.vars.size() == 1)\r
 138             addUpperBound(u.vars.get(0));\r
 139         else {\r
 140             u.low = this;\r
 141             complexUpperBounds.add(u);\r
 142             markDirty();\r
 143             for(Var v : u.vars)\r
 144                 v.complexLowerBounds.add(u);\r
 145         }\r
 146         // TODO compare complex upper bounds together\r
 147     }\r
 148     \r
 149     public void replaceWith(int con) {\r
 150         // Check that replacement is sound\r
 151         if(SCLCompilerConfiguration.DEBUG) {\r
 152             if((con&constLowerBound) != constLowerBound)\r
 153                 throw new InternalCompilerError();\r
 154             if((con|constUpperBound) != constUpperBound)\r
 155                 throw new InternalCompilerError();\r
 156         }\r
 157         \r
 158         // Remove the variable and unify original TMetaVar\r
 159         solver.vars.remove(original);\r
 160         try {\r
 161             Type type = solver.effectIds.toType(con);\r
 162             if(SubSolver.DEBUG)\r
 163                 System.out.println(original.toString(solver.tuc) + " := " + type.toString(solver.tuc));\r
 164             original.setRef(type);\r
 165         } catch (UnificationException e) {\r
 166             throw new InternalCompilerError();\r
 167         }\r
 168         \r
 169         // Propagate change to lower and upper bounds\r
 170         for(Var v : simpleUpperBounds) {\r
 171             v.simpleLowerBounds.remove(this);\r
 172             v.addLowerBound(con);\r
 173             v.markDirty();\r
 174         }\r
 175         for(Var v : simpleLowerBounds) {\r
 176             v.simpleUpperBounds.remove(this);\r
 177             v.addUpperBound(con);\r
 178             v.markDirty();\r
 179         }\r
 180         for(VUnion u : complexUpperBounds) {\r
 181             u.low = null;\r
 182             u.con |= ~con;\r
 183             if(u.vars.size() == 1) {\r
 184                 Var uv = u.vars.get(0);\r
 185                 uv.constLowerBound |= ~u.con;\r
 186                 uv.complexLowerBounds.remove(u);\r
 187                 uv.markDirty();\r
 188             }\r
 189             else {\r
 190                 for(Var uv : u.vars)\r
 191                     uv.markDirty();\r
 192             }\r
 193         }\r
 194         for(VUnion u : complexLowerBounds) {\r
 195             u.low.markDirty();\r
 196             u.vars.remove(this);\r
 197             u.con |= con;\r
 198             u.con &= u.low.constUpperBound;\r
 199             if(u.vars.isEmpty()) {\r
 200                 u.low.complexUpperBounds.remove(u);\r
 201                 u.low.addUpperBound(u.con);\r
 202             }\r
 203             else if(u.vars.size() == 1 && u.con == 0) {\r
 204                 u.low.complexUpperBounds.remove(u);\r
 205                 u.low.addUpperBound(u.vars.get(0));\r
 206             }\r
 207         }\r
 208     }\r
 209     \r
 210     public void replaceDownwards(Var var) {\r
 211         // Remove the variable and unify original TMetaVar\r
 212         solver.vars.remove(original);\r
 213         try {\r
 214             if(SubSolver.DEBUG)\r
 215                 System.out.println(original.toString(solver.tuc) + " := " + var.original.toString(solver.tuc));\r
 216             original.setRef(var.original);\r
 217         } catch (UnificationException e) {\r
 218             throw new InternalCompilerError();\r
 219         }\r
 220         \r
 221         // Remove downwards dependencies\r
 222         if(constLowerBound != 0)\r
 223             throw new InternalCompilerError();\r
 224         for(Var v : simpleLowerBounds)\r
 225             v.simpleUpperBounds.remove(this);\r
 226         if(!complexLowerBounds.isEmpty())\r
 227             throw new InternalCompilerError();\r
 228         var.markDirty();\r
 229         \r
 230         // Propagate change to upper bounds\r
 231         var.addUpperBound(constUpperBound);\r
 232         for(Var v : simpleUpperBounds) {\r
 233             v.simpleLowerBounds.remove(this);\r
 234             var.addUpperBound(v);\r
 235         }\r
 236         for(VUnion u : complexUpperBounds) {\r
 237             var.addUpperBound(u);\r
 238         }\r
 239     }\r
 240     \r
 241     public void replaceUpwards(Var var) {\r
 242         // Remove the variable and unify original TMetaVar\r
 243         solver.vars.remove(original);\r
 244         try {\r
 245             if(SubSolver.DEBUG)\r
 246                 System.out.println(original.toString(solver.tuc) + " := " + var.original.toString(solver.tuc));\r
 247             original.setRef(var.original);\r
 248         } catch (UnificationException e) {\r
 249             throw new InternalCompilerError();\r
 250         }\r
 251         \r
 252         // Remove upwards dependencies\r
 253         if(constUpperBound != EffectIdMap.MAX)\r
 254             throw new InternalCompilerError();\r
 255         for(Var v : simpleUpperBounds)\r
 256             v.simpleLowerBounds.remove(this);\r
 257         if(!complexUpperBounds.isEmpty())\r
 258             throw new InternalCompilerError();\r
 259         var.markDirty();\r
 260         \r
 261         // Propagate change to lower bounds\r
 262         var.addLowerBound(constLowerBound);\r
 263         for(Var v : simpleLowerBounds) {\r
 264             v.simpleUpperBounds.remove(this);\r
 265             v.markDirty();\r
 266             v.addUpperBound(var);\r
 267         }\r
 268         for(VUnion u : complexLowerBounds) {\r
 269             u.vars.remove(this);\r
 270             if(u.low != null) {\r
 271                 u.low.markDirty();            \r
 272                 if(u.vars.isEmpty() && u.con == 0) {\r
 273                     u.low.complexUpperBounds.remove(u);\r
 274                     u.low.addUpperBound(var);\r
 275                     continue;\r
 276                 }\r
 277             }\r
 278             u.addVar(var);\r
 279         }\r
 280     }\r
 281 \r
 282     public boolean isFree() {\r
 283         return constLowerBound == EffectIdMap.MIN && \r
 284                 constUpperBound == EffectIdMap.MAX &&\r
 285                 simpleLowerBounds.isEmpty() &&\r
 286                 simpleUpperBounds.isEmpty() &&\r
 287                 complexLowerBounds.isEmpty() &&\r
 288                 complexUpperBounds.isEmpty();\r
 289     }\r
 290 }\r