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

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