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

   1 package org.simantics.scl.compiler.internal.elaboration.subsumption;
   2
   3 import java.util.ArrayDeque;
   4 import java.util.ArrayList;
   5
   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;
  15
  16 import gnu.trove.map.hash.THashMap;
  17 import gnu.trove.set.hash.THashSet;
  18
  19 public class SubSolver {
  20
  21     public static final boolean DEBUG = false;
  22
  23     long globalLoc;
  24     ErrorLog errorLog;
  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>();
  30
  31     TypeUnparsingContext tuc = new TypeUnparsingContext();
  32
  33     public SubSolver(ErrorLog errorLog, ArrayList<Subsumption> subsumptions,
  34             ArrayList<Type> potentialSingletonEffects,
  35             long globalLoc) {
  36         this.errorLog = errorLog;
  37         this.subsumptions = subsumptions;
  38         this.potentialSingletonEffects = potentialSingletonEffects;
  39         this.globalLoc = globalLoc;
  40
  41         //for(Subsumption sub : subsumptions)
  42         //    System.out.println("[" + sub.a.toString(tuc) + " < " + sub.b.toString(tuc) + "]");
  43     }
  44
  45     public void solve() {
  46         //printSubsumptions();
  47         createVar();
  48         //print();
  49         reduceChains();
  50         propagateUpperBounds();
  51         checkLowerBounds();
  52         //errorFromUnsolvedEquations();
  53         //System.out.println("--");
  54         //print();
  55     }
  56
  57     private void markAllDirty() {
  58         for(Var v : vars.values())
  59             v.markDirty();
  60     }
  61
  62     private Var getOrCreateVar(TMetaVar mv) {
  63         Var var = vars.get(mv);
  64         if(var == null) {
  65             var = new Var(mv, mv.toString(tuc).substring(1), this);
  66             vars.put(mv, var);
  67         }
  68         return var;
  69     }
  70
  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)
  77                 addVar(c);
  78     }
  79
  80     ArrayList<TMetaVar> aVars = new ArrayList<TMetaVar>();
  81
  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));
  87             aVars.clear();
  88         }
  89         if(aCons != 0) {
  90             VUnion u = toVUnion(b);
  91             if(u.vars.isEmpty()) {
  92                 testSubsumption(loc, aCons, u.con);
  93             }
  94             else
  95                 u.makeLowerBound(aCons);
  96         }
  97     }
  98
  99     ArrayList<TMetaVar> bVars = new ArrayList<TMetaVar>();
 100
 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));
 106         bVars.clear();
 107         return new VUnion(cons, vars);
 108     }
 109
 110     private void createVar() {
 111         for(Subsumption sub : subsumptions)
 112             addSubsumption(sub.loc, sub.a, sub.b);
 113         for(Type t : potentialSingletonEffects)
 114             addVar(t);
 115     }
 116
 117     private void reduceChains() {
 118         markAllDirty();
 119         while(true) {
 120             Var v = dirtyQueue.poll();
 121             if(v == null)
 122                 break;
 123
 124             reduceChains(v);
 125             v.dirty = false;
 126         }
 127     }
 128
 129     private void reduceChains(Var v) {
 130         if(v.constLowerBound == v.constUpperBound) {
 131             v.replaceWith(v.constLowerBound);
 132             return;
 133         }
 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);
 140                 return;
 141             }
 142             else if(v.simpleLowerBounds.size() == 1 && v.constLowerBound == 0) {
 143                 v.replaceDownwards(v.simpleLowerBounds.get(0));
 144                 return;
 145             }
 146         }
 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);
 152                 return;
 153             }
 154             else if(v.simpleUpperBounds.size() == 1 && v.constUpperBound == EffectIdMap.MAX) {
 155                 v.replaceUpwards(v.simpleUpperBounds.get(0));
 156                 return;
 157             }
 158         }
 159     }
 160
 161     private void propagateUpperBounds() {
 162         markAllDirty();
 163         while(true) {
 164             Var v = dirtyQueue.poll();
 165             if(v == null)
 166                 break;
 167
 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();
 173
 174             if(upperApprox != v.upperApprox) {
 175                 v.upperApprox = upperApprox;
 176                 for(Var u : v.simpleLowerBounds)
 177                     u.markDirty();
 178                 for(VUnion u : v.complexLowerBounds)
 179                     if(u.low != null)
 180                         u.low.markDirty();
 181             }
 182
 183             v.dirty = false;
 184         }
 185     }
 186
 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)
 193                 if(u.low == null)
 194                     lowerBounds.add(u);
 195         }
 196         for(VUnion u : lowerBounds)
 197             if(u.getUpperApprox() != EffectIdMap.MAX)
 198                 errorLog.log(globalLoc, "Subsumption failed.");
 199     }
 200
 201     private void errorFromUnsolvedEquations() {
 202         for(Var v : vars.values()) {
 203             if(!v.isFree()) {
 204                 errorLog.log(globalLoc, "Couldn't simplify all effect subsumptions away. " +
 205                                 "The current compiler cannot handle this situation. Try adding more type annotations.");
 206                 break;
 207             }
 208         }
 209     }
 210
 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);
 226         }
 227     }
 228
 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) + "]");
 233     }
 234
 235     private void testSubsumption(long location, int a, int b) {
 236         int extraEffects = a & (~b);
 237         if(extraEffects != 0)
 238             subsumptionFailed(location, extraEffects);
 239     }
 240
 241     private void subsumptionFailed(long location , int effects) {
 242         errorLog.log(location, "Side-effect " + effectIds.toType(effects) + " is forbidden here.");
 243     }
 244 }