bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/subsumption2/SubsumptionGraph.java

   1 package org.simantics.scl.compiler.internal.elaboration.subsumption2;
   2
   3 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   4 import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;
   5 import org.simantics.scl.compiler.types.TMetaVar;
   6 import org.simantics.scl.compiler.types.exceptions.UnificationException;
   7 import org.simantics.scl.compiler.types.util.Polarity;
   8
   9 public class SubsumptionGraph {
  10     public static final int REMOVED = Integer.MAX_VALUE-1;
  11
  12     public static class LowerBoundSource {
  13         public final long location;
  14         public final int lower;
  15         public final LowerBoundSource next;
  16         public LowerBoundSource(long location, int lower, LowerBoundSource next) {
  17             this.location = location;
  18             this.lower = lower;
  19             this.next = next;
  20         }
  21     }
  22
  23     public static abstract class Node {
  24         int lowerBound = EffectIdMap.MIN;
  25         int upperBound = EffectIdMap.MAX;
  26         Sub lower;
  27         LowerBoundSource lowerBoundSource;
  28
  29         public void addLowerBoundSource(long location, int lower) {
  30             lowerBoundSource = new LowerBoundSource(location, lower, lowerBoundSource);
  31         }
  32     }
  33
  34     public static class VarNode extends Node {
  35         TMetaVar origin;
  36         Sub upper;
  37         PartOfUnion partOf;
  38         int index;
  39
  40         public VarNode(TMetaVar origin) {
  41             this.origin = origin;
  42         }
  43
  44         public Polarity getPolarity() {
  45             return origin.getPolarity();
  46         }
  47
  48         public void replaceBy(VarNode replacement) {
  49             try {
  50                 origin.setRef(replacement.origin);
  51             } catch(UnificationException e) {
  52                 throw new InternalCompilerError(e);
  53             }
  54             {
  55                 Sub last = null;
  56                 for(Sub cur=upper;cur!=null;cur=cur.aNext) {
  57                     cur.a = replacement;
  58                     last = cur;
  59                 }
  60                 if(last != null) {
  61                     last.aNext = replacement.upper;
  62                     if(last.aNext != null)
  63                         last.aNext.aPrev = last;
  64                     replacement.upper = upper;
  65                 }
  66
  67                 last = null;
  68                 for(Sub cur=lower;cur!=null;cur=cur.bNext) {
  69                     cur.b = replacement;
  70                     last = cur;
  71                 }
  72                 if(last != null) {
  73                     last.bNext = replacement.lower;
  74                     if(last.bNext != null)
  75                         last.bNext.bPrev = last;
  76                     replacement.lower = lower;
  77                 }
  78             }
  79             {
  80                 PartOfUnion last = null;
  81                 for(PartOfUnion cur=partOf;cur!=null;cur=cur.bNext) {
  82                     cur.a = replacement;
  83                     last = cur;
  84                 }
  85                 if(last != null) {
  86                     last.aNext = replacement.partOf;
  87                     if(last.aNext != null)
  88                         last.aNext.bPrev = last;
  89                     replacement.partOf = partOf;
  90                 }
  91             }
  92             index = REMOVED;
  93         }
  94
  95         public void removeConstantNode(EffectIdMap effectIds, int constValue) {
  96             try {
  97                 origin.setRef(effectIds.toType(constValue));
  98             } catch (UnificationException e) {
  99                 throw new InternalCompilerError(e);
 100             }
 101             for(Sub cur=lower;cur!=null;cur=cur.bNext)
 102                 cur.detachA();
 103             for(Sub cur=upper;cur!=null;cur=cur.aNext)
 104                 cur.detachB();
 105             for(PartOfUnion cur=partOf;cur!=null;cur=cur.aNext) {
 106                 cur.detachB();
 107                 cur.b.constPart |= constValue;
 108             }
 109             index = REMOVED;
 110         }
 111     }
 112
 113     public static class UnionNode extends Node {
 114         long location;
 115         PartOfUnion parts;
 116         int constPart;
 117
 118         public UnionNode(long location, int constPart) {
 119             this.location = location;
 120             this.constPart = constPart;
 121             this.lowerBound = constPart;
 122         }
 123
 124         public void remove() {
 125             for(Sub cur=lower;cur!=null;cur=cur.bNext)
 126                 cur.detachA();
 127             for(PartOfUnion cur=parts;cur!=null;cur=cur.bNext)
 128                 cur.detachA();
 129             constPart = REMOVED;
 130         }
 131     }
 132
 133     public static class Sub {
 134         VarNode a;
 135         Node b;
 136         Sub aNext;
 137         Sub aPrev;
 138         Sub bNext;
 139         Sub bPrev;
 140
 141         public Sub(VarNode a, Node b) {
 142             this.a = a;
 143             this.b = b;
 144
 145             aNext = a.upper;
 146             if(aNext != null)
 147                 aNext.aPrev = this;
 148             a.upper = this;
 149
 150             bNext = b.lower;
 151             if(bNext != null)
 152                 bNext.bPrev = this;
 153             b.lower = this;
 154         }
 155
 156         public void detachA() {
 157             if(aNext != null)
 158                 aNext.aPrev = aPrev;
 159             if(aPrev != null)
 160                 aPrev.aNext = aNext;
 161             else
 162                 a.upper = aNext;
 163         }
 164
 165         public void detachB() {
 166             if(bNext != null)
 167                 bNext.bPrev = bPrev;
 168             if(bPrev != null)
 169                 bPrev.bNext = bNext;
 170             else
 171                 b.lower = bNext;
 172         }
 173
 174         public void remove() {
 175             detachA();
 176             detachB();
 177         }
 178     }
 179
 180     public static class PartOfUnion {
 181         VarNode a;
 182         UnionNode b;
 183         PartOfUnion aNext;
 184         PartOfUnion aPrev;
 185         PartOfUnion bNext;
 186         PartOfUnion bPrev;
 187
 188         public PartOfUnion(VarNode a, UnionNode b) {
 189             this.a = a;
 190             this.b = b;
 191
 192             aNext = a.partOf;
 193             if(aNext != null)
 194                 aNext.aPrev = this;
 195             a.partOf = this;
 196
 197             bNext = b.parts;
 198             if(bNext != null)
 199                 bNext.bPrev = this;
 200             b.parts = this;
 201         }
 202
 203         public void detachA() {
 204             if(aNext != null)
 205                 aNext.aPrev = aPrev;
 206             if(aPrev != null)
 207                 aPrev.aNext = aNext;
 208             else
 209                 a.partOf = aNext;
 210         }
 211
 212         public void detachB() {
 213             if(bNext != null)
 214                 bNext.bPrev = bPrev;
 215             if(bPrev != null)
 216                 bPrev.bNext = bNext;
 217             else
 218                 b.parts = bNext;
 219         }
 220
 221         public void remove() {
 222             detachA();
 223             detachB();
 224         }
 225
 226     }
 227 }