-package org.simantics.scl.compiler.internal.elaboration.subsumption;\r
-\r
-import java.util.ArrayList;\r
-\r
-import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
-import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;\r
-import org.simantics.scl.compiler.top.SCLCompilerConfiguration;\r
-import org.simantics.scl.compiler.types.TMetaVar;\r
-import org.simantics.scl.compiler.types.Type;\r
-import org.simantics.scl.compiler.types.exceptions.UnificationException;\r
-\r
-public class Var {\r
- String name;\r
- \r
- int constLowerBound = EffectIdMap.MIN;\r
- int constUpperBound = EffectIdMap.MAX;\r
- int upperApprox = EffectIdMap.MAX;\r
- TMetaVar original;\r
- \r
- ArrayList<Var> simpleLowerBounds = new ArrayList<Var>();\r
- ArrayList<Var> simpleUpperBounds = new ArrayList<Var>();\r
- ArrayList<VUnion> complexLowerBounds = new ArrayList<VUnion>();\r
- ArrayList<VUnion> complexUpperBounds = new ArrayList<VUnion>();\r
- \r
- SubSolver solver;\r
- boolean dirty;\r
- \r
- public Var(TMetaVar original, String name, SubSolver solver) {\r
- this.original = original;\r
- this.name = name;\r
- this.solver = solver; \r
- markDirty();\r
- }\r
-\r
- void markDirty() {\r
- if(!dirty) {\r
- dirty = true;\r
- solver.dirtyQueue.add(this);\r
- }\r
- }\r
- \r
- /**\r
- * Adds a constant constraint\r
- */\r
- public void addUpperBound(int c) {\r
- c &= constUpperBound;\r
- if(c != constUpperBound) {\r
- if((c & constLowerBound) != constLowerBound) {\r
- solver.errorLog.log(solver.globalLoc, "Subsumption failed: " + \r
- solver.effectIds.toType(constLowerBound) + " is not a subtype of " +\r
- solver.effectIds.toType(c)\r
- );\r
- return;\r
- }\r
- constUpperBound = c;\r
- for(int i=0;i<complexUpperBounds.size();++i) {\r
- VUnion u = complexUpperBounds.get(i); \r
- u.con &= c;\r
- if(u.con == 0 && u.vars.size() == 1) {\r
- removeComplexUpperBound(i); \r
- --i;\r
- addUpperBound(u.vars.get(0));\r
- }\r
- }\r
- markDirty();\r
- }\r
- }\r
- \r
- public void addLowerBound(int c) {\r
- if((c | constUpperBound) != constUpperBound) {\r
- solver.errorLog.log(solver.globalLoc, "Subsumption failed: " + \r
- solver.effectIds.toType(c) + " is not a subtype of " +\r
- solver.effectIds.toType(constUpperBound)\r
- );\r
- return;\r
- }\r
- constLowerBound |= c;\r
- markDirty();\r
- }\r
- \r
- private void removeComplexUpperBound(int i) {\r
- VUnion u = complexUpperBounds.get(i);\r
- int lastId = complexUpperBounds.size()-1; \r
- VUnion last = complexUpperBounds.remove(lastId);\r
- if(i < lastId)\r
- complexUpperBounds.set(i, last);\r
- for(Var v : u.vars) {\r
- v.complexLowerBounds.remove(u);\r
- v.markDirty();\r
- }\r
- }\r
- \r
- /**\r
- * Adds a simple variable constraint\r
- */\r
- public void addUpperBound(Var var) {\r
- if(var == this)\r
- return;\r
- if(simpleUpperBounds.size() < var.simpleLowerBounds.size()) {\r
- if(simpleUpperBounds.contains(var))\r
- return;\r
- }\r
- else {\r
- if(var.simpleLowerBounds.contains(this))\r
- return;\r
- }\r
- \r
- for(int i=0;i<complexUpperBounds.size();++i)\r
- if(complexUpperBounds.get(i).vars.contains(var)) {\r
- removeComplexUpperBound(i); \r
- --i;\r
- }\r
- \r
- simpleUpperBounds.add(var);\r
- var.simpleLowerBounds.add(this);\r
- \r
- markDirty();\r
- var.markDirty();\r
- }\r
- \r
- /**\r
- * Adds a complex constraint\r
- */\r
- public void addUpperBound(VUnion u) {\r
- if(u.vars.isEmpty()) {\r
- addUpperBound(u.con);\r
- return;\r
- } \r
- if(u.vars.contains(this))\r
- return; \r
- for(Var v : u.vars)\r
- if(simpleUpperBounds.contains(v))\r
- return;\r
- u.con &= constUpperBound;\r
- if(u.con == constUpperBound)\r
- return;\r
- if(u.con == 0 && u.vars.size() == 1)\r
- addUpperBound(u.vars.get(0));\r
- else {\r
- u.low = this;\r
- complexUpperBounds.add(u);\r
- markDirty();\r
- for(Var v : u.vars)\r
- v.complexLowerBounds.add(u);\r
- }\r
- // TODO compare complex upper bounds together\r
- }\r
- \r
- public void replaceWith(int con) {\r
- // Check that replacement is sound\r
- if(SCLCompilerConfiguration.DEBUG) {\r
- if((con&constLowerBound) != constLowerBound)\r
- throw new InternalCompilerError();\r
- if((con|constUpperBound) != constUpperBound)\r
- throw new InternalCompilerError();\r
- }\r
- \r
- // Remove the variable and unify original TMetaVar\r
- solver.vars.remove(original);\r
- try {\r
- Type type = solver.effectIds.toType(con);\r
- if(SubSolver.DEBUG)\r
- System.out.println(original.toString(solver.tuc) + " := " + type.toString(solver.tuc));\r
- original.setRef(type);\r
- } catch (UnificationException e) {\r
- throw new InternalCompilerError();\r
- }\r
- \r
- // Propagate change to lower and upper bounds\r
- for(Var v : simpleUpperBounds) {\r
- v.simpleLowerBounds.remove(this);\r
- v.addLowerBound(con);\r
- v.markDirty();\r
- }\r
- for(Var v : simpleLowerBounds) {\r
- v.simpleUpperBounds.remove(this);\r
- v.addUpperBound(con);\r
- v.markDirty();\r
- }\r
- for(VUnion u : complexUpperBounds) {\r
- u.low = null;\r
- u.con |= ~con;\r
- if(u.vars.size() == 1) {\r
- Var uv = u.vars.get(0);\r
- uv.constLowerBound |= ~u.con;\r
- uv.complexLowerBounds.remove(u);\r
- uv.markDirty();\r
- }\r
- else {\r
- for(Var uv : u.vars)\r
- uv.markDirty();\r
- }\r
- }\r
- for(VUnion u : complexLowerBounds) {\r
- u.low.markDirty();\r
- u.vars.remove(this);\r
- u.con |= con;\r
- u.con &= u.low.constUpperBound;\r
- if(u.vars.isEmpty()) {\r
- u.low.complexUpperBounds.remove(u);\r
- u.low.addUpperBound(u.con);\r
- }\r
- else if(u.vars.size() == 1 && u.con == 0) {\r
- u.low.complexUpperBounds.remove(u);\r
- u.low.addUpperBound(u.vars.get(0));\r
- }\r
- }\r
- }\r
- \r
- public void replaceDownwards(Var var) {\r
- // Remove the variable and unify original TMetaVar\r
- solver.vars.remove(original);\r
- try {\r
- if(SubSolver.DEBUG)\r
- System.out.println(original.toString(solver.tuc) + " := " + var.original.toString(solver.tuc));\r
- original.setRef(var.original);\r
- } catch (UnificationException e) {\r
- throw new InternalCompilerError();\r
- }\r
- \r
- // Remove downwards dependencies\r
- if(constLowerBound != 0)\r
- throw new InternalCompilerError();\r
- for(Var v : simpleLowerBounds)\r
- v.simpleUpperBounds.remove(this);\r
- if(!complexLowerBounds.isEmpty())\r
- throw new InternalCompilerError();\r
- var.markDirty();\r
- \r
- // Propagate change to upper bounds\r
- var.addUpperBound(constUpperBound);\r
- for(Var v : simpleUpperBounds) {\r
- v.simpleLowerBounds.remove(this);\r
- var.addUpperBound(v);\r
- }\r
- for(VUnion u : complexUpperBounds) {\r
- var.addUpperBound(u);\r
- }\r
- }\r
- \r
- public void replaceUpwards(Var var) {\r
- // Remove the variable and unify original TMetaVar\r
- solver.vars.remove(original);\r
- try {\r
- if(SubSolver.DEBUG)\r
- System.out.println(original.toString(solver.tuc) + " := " + var.original.toString(solver.tuc));\r
- original.setRef(var.original);\r
- } catch (UnificationException e) {\r
- throw new InternalCompilerError();\r
- }\r
- \r
- // Remove upwards dependencies\r
- if(constUpperBound != EffectIdMap.MAX)\r
- throw new InternalCompilerError();\r
- for(Var v : simpleUpperBounds)\r
- v.simpleLowerBounds.remove(this);\r
- if(!complexUpperBounds.isEmpty())\r
- throw new InternalCompilerError();\r
- var.markDirty();\r
- \r
- // Propagate change to lower bounds\r
- var.addLowerBound(constLowerBound);\r
- for(Var v : simpleLowerBounds) {\r
- v.simpleUpperBounds.remove(this);\r
- v.markDirty();\r
- v.addUpperBound(var);\r
- }\r
- for(VUnion u : complexLowerBounds) {\r
- u.vars.remove(this);\r
- if(u.low != null) {\r
- u.low.markDirty(); \r
- if(u.vars.isEmpty() && u.con == 0) {\r
- u.low.complexUpperBounds.remove(u);\r
- u.low.addUpperBound(var);\r
- continue;\r
- }\r
- }\r
- u.addVar(var);\r
- }\r
- }\r
-\r
- public boolean isFree() {\r
- return constLowerBound == EffectIdMap.MIN && \r
- constUpperBound == EffectIdMap.MAX &&\r
- simpleLowerBounds.isEmpty() &&\r
- simpleUpperBounds.isEmpty() &&\r
- complexLowerBounds.isEmpty() &&\r
- complexUpperBounds.isEmpty();\r
- }\r
-}\r
+package org.simantics.scl.compiler.internal.elaboration.subsumption;
+
+import java.util.ArrayList;
+
+import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
+import org.simantics.scl.compiler.internal.types.effects.EffectIdMap;
+import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
+import org.simantics.scl.compiler.types.TMetaVar;
+import org.simantics.scl.compiler.types.Type;
+import org.simantics.scl.compiler.types.exceptions.UnificationException;
+
+public class Var {
+ String name;
+
+ int constLowerBound = EffectIdMap.MIN;
+ int constUpperBound = EffectIdMap.MAX;
+ int upperApprox = EffectIdMap.MAX;
+ TMetaVar original;
+
+ ArrayList<Var> simpleLowerBounds = new ArrayList<Var>();
+ ArrayList<Var> simpleUpperBounds = new ArrayList<Var>();
+ ArrayList<VUnion> complexLowerBounds = new ArrayList<VUnion>();
+ ArrayList<VUnion> complexUpperBounds = new ArrayList<VUnion>();
+
+ SubSolver solver;
+ boolean dirty;
+
+ public Var(TMetaVar original, String name, SubSolver solver) {
+ this.original = original;
+ this.name = name;
+ this.solver = solver;
+ markDirty();
+ }
+
+ void markDirty() {
+ if(!dirty) {
+ dirty = true;
+ solver.dirtyQueue.add(this);
+ }
+ }
+
+ /**
+ * Adds a constant constraint
+ */
+ public void addUpperBound(int c) {
+ c &= constUpperBound;
+ if(c != constUpperBound) {
+ if((c & constLowerBound) != constLowerBound) {
+ solver.errorLog.log(solver.globalLoc, "Subsumption failed: " +
+ solver.effectIds.toType(constLowerBound) + " is not a subtype of " +
+ solver.effectIds.toType(c)
+ );
+ return;
+ }
+ constUpperBound = c;
+ for(int i=0;i<complexUpperBounds.size();++i) {
+ VUnion u = complexUpperBounds.get(i);
+ u.con &= c;
+ if(u.con == 0 && u.vars.size() == 1) {
+ removeComplexUpperBound(i);
+ --i;
+ addUpperBound(u.vars.get(0));
+ }
+ }
+ markDirty();
+ }
+ }
+
+ public void addLowerBound(int c) {
+ if((c | constUpperBound) != constUpperBound) {
+ solver.errorLog.log(solver.globalLoc, "Subsumption failed: " +
+ solver.effectIds.toType(c) + " is not a subtype of " +
+ solver.effectIds.toType(constUpperBound)
+ );
+ return;
+ }
+ constLowerBound |= c;
+ markDirty();
+ }
+
+ private void removeComplexUpperBound(int i) {
+ VUnion u = complexUpperBounds.get(i);
+ int lastId = complexUpperBounds.size()-1;
+ VUnion last = complexUpperBounds.remove(lastId);
+ if(i < lastId)
+ complexUpperBounds.set(i, last);
+ for(Var v : u.vars) {
+ v.complexLowerBounds.remove(u);
+ v.markDirty();
+ }
+ }
+
+ /**
+ * Adds a simple variable constraint
+ */
+ public void addUpperBound(Var var) {
+ if(var == this)
+ return;
+ if(simpleUpperBounds.size() < var.simpleLowerBounds.size()) {
+ if(simpleUpperBounds.contains(var))
+ return;
+ }
+ else {
+ if(var.simpleLowerBounds.contains(this))
+ return;
+ }
+
+ for(int i=0;i<complexUpperBounds.size();++i)
+ if(complexUpperBounds.get(i).vars.contains(var)) {
+ removeComplexUpperBound(i);
+ --i;
+ }
+
+ simpleUpperBounds.add(var);
+ var.simpleLowerBounds.add(this);
+
+ markDirty();
+ var.markDirty();
+ }
+
+ /**
+ * Adds a complex constraint
+ */
+ public void addUpperBound(VUnion u) {
+ if(u.vars.isEmpty()) {
+ addUpperBound(u.con);
+ return;
+ }
+ if(u.vars.contains(this))
+ return;
+ for(Var v : u.vars)
+ if(simpleUpperBounds.contains(v))
+ return;
+ u.con &= constUpperBound;
+ if(u.con == constUpperBound)
+ return;
+ if(u.con == 0 && u.vars.size() == 1)
+ addUpperBound(u.vars.get(0));
+ else {
+ u.low = this;
+ complexUpperBounds.add(u);
+ markDirty();
+ for(Var v : u.vars)
+ v.complexLowerBounds.add(u);
+ }
+ // TODO compare complex upper bounds together
+ }
+
+ public void replaceWith(int con) {
+ // Check that replacement is sound
+ if(SCLCompilerConfiguration.DEBUG) {
+ if((con&constLowerBound) != constLowerBound)
+ throw new InternalCompilerError();
+ if((con|constUpperBound) != constUpperBound)
+ throw new InternalCompilerError();
+ }
+
+ // Remove the variable and unify original TMetaVar
+ solver.vars.remove(original);
+ try {
+ Type type = solver.effectIds.toType(con);
+ if(SubSolver.DEBUG)
+ System.out.println(original.toString(solver.tuc) + " := " + type.toString(solver.tuc));
+ original.setRef(type);
+ } catch (UnificationException e) {
+ throw new InternalCompilerError();
+ }
+
+ // Propagate change to lower and upper bounds
+ for(Var v : simpleUpperBounds) {
+ v.simpleLowerBounds.remove(this);
+ v.addLowerBound(con);
+ v.markDirty();
+ }
+ for(Var v : simpleLowerBounds) {
+ v.simpleUpperBounds.remove(this);
+ v.addUpperBound(con);
+ v.markDirty();
+ }
+ for(VUnion u : complexUpperBounds) {
+ u.low = null;
+ u.con |= ~con;
+ if(u.vars.size() == 1) {
+ Var uv = u.vars.get(0);
+ uv.constLowerBound |= ~u.con;
+ uv.complexLowerBounds.remove(u);
+ uv.markDirty();
+ }
+ else {
+ for(Var uv : u.vars)
+ uv.markDirty();
+ }
+ }
+ for(VUnion u : complexLowerBounds) {
+ u.low.markDirty();
+ u.vars.remove(this);
+ u.con |= con;
+ u.con &= u.low.constUpperBound;
+ if(u.vars.isEmpty()) {
+ u.low.complexUpperBounds.remove(u);
+ u.low.addUpperBound(u.con);
+ }
+ else if(u.vars.size() == 1 && u.con == 0) {
+ u.low.complexUpperBounds.remove(u);
+ u.low.addUpperBound(u.vars.get(0));
+ }
+ }
+ }
+
+ public void replaceDownwards(Var var) {
+ // Remove the variable and unify original TMetaVar
+ solver.vars.remove(original);
+ try {
+ if(SubSolver.DEBUG)
+ System.out.println(original.toString(solver.tuc) + " := " + var.original.toString(solver.tuc));
+ original.setRef(var.original);
+ } catch (UnificationException e) {
+ throw new InternalCompilerError();
+ }
+
+ // Remove downwards dependencies
+ if(constLowerBound != 0)
+ throw new InternalCompilerError();
+ for(Var v : simpleLowerBounds)
+ v.simpleUpperBounds.remove(this);
+ if(!complexLowerBounds.isEmpty())
+ throw new InternalCompilerError();
+ var.markDirty();
+
+ // Propagate change to upper bounds
+ var.addUpperBound(constUpperBound);
+ for(Var v : simpleUpperBounds) {
+ v.simpleLowerBounds.remove(this);
+ var.addUpperBound(v);
+ }
+ for(VUnion u : complexUpperBounds) {
+ var.addUpperBound(u);
+ }
+ }
+
+ public void replaceUpwards(Var var) {
+ // Remove the variable and unify original TMetaVar
+ solver.vars.remove(original);
+ try {
+ if(SubSolver.DEBUG)
+ System.out.println(original.toString(solver.tuc) + " := " + var.original.toString(solver.tuc));
+ original.setRef(var.original);
+ } catch (UnificationException e) {
+ throw new InternalCompilerError();
+ }
+
+ // Remove upwards dependencies
+ if(constUpperBound != EffectIdMap.MAX)
+ throw new InternalCompilerError();
+ for(Var v : simpleUpperBounds)
+ v.simpleLowerBounds.remove(this);
+ if(!complexUpperBounds.isEmpty())
+ throw new InternalCompilerError();
+ var.markDirty();
+
+ // Propagate change to lower bounds
+ var.addLowerBound(constLowerBound);
+ for(Var v : simpleLowerBounds) {
+ v.simpleUpperBounds.remove(this);
+ v.markDirty();
+ v.addUpperBound(var);
+ }
+ for(VUnion u : complexLowerBounds) {
+ u.vars.remove(this);
+ if(u.low != null) {
+ u.low.markDirty();
+ if(u.vars.isEmpty() && u.con == 0) {
+ u.low.complexUpperBounds.remove(u);
+ u.low.addUpperBound(var);
+ continue;
+ }
+ }
+ u.addVar(var);
+ }
+ }
+
+ public boolean isFree() {
+ return constLowerBound == EffectIdMap.MIN &&
+ constUpperBound == EffectIdMap.MAX &&
+ simpleLowerBounds.isEmpty() &&
+ simpleUpperBounds.isEmpty() &&
+ complexLowerBounds.isEmpty() &&
+ complexUpperBounds.isEmpty();
+ }
+}
Code Review / simantics / platform.git / blobdiff