-package org.simantics.scl.compiler.elaboration.expressions;\r
-\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.Just;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.addInteger;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.apply;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.as;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.if_;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.integer;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.isZeroInteger;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.lambda;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.let;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.letRec;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.matchWithDefault;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.newVar;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.seq;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.tuple;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.var;\r
-import static org.simantics.scl.compiler.elaboration.expressions.Expressions.vars;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Set;\r
-\r
-import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;\r
-import org.simantics.scl.compiler.common.names.Names;\r
-import org.simantics.scl.compiler.elaboration.contexts.TranslationContext;\r
-import org.simantics.scl.compiler.elaboration.contexts.TypingContext;\r
-import org.simantics.scl.compiler.elaboration.expressions.printing.ExpressionToStringVisitor;\r
-import org.simantics.scl.compiler.elaboration.query.Query;\r
-import org.simantics.scl.compiler.elaboration.query.Query.Diff;\r
-import org.simantics.scl.compiler.elaboration.query.Query.Diffable;\r
-import org.simantics.scl.compiler.elaboration.query.compilation.DerivateException;\r
-import org.simantics.scl.compiler.elaboration.relations.LocalRelation;\r
-import org.simantics.scl.compiler.elaboration.relations.SCLRelation;\r
-import org.simantics.scl.compiler.errors.Locations;\r
-import org.simantics.scl.compiler.internal.elaboration.utils.ExpressionDecorator;\r
-import org.simantics.scl.compiler.internal.elaboration.utils.ForcedClosure;\r
-import org.simantics.scl.compiler.internal.elaboration.utils.StronglyConnectedComponents;\r
-import org.simantics.scl.compiler.top.SCLCompilerConfiguration;\r
-import org.simantics.scl.compiler.types.Type;\r
-import org.simantics.scl.compiler.types.Types;\r
-import org.simantics.scl.compiler.types.exceptions.MatchException;\r
-import org.simantics.scl.compiler.types.kinds.Kinds;\r
-\r
-import gnu.trove.impl.Constants;\r
-import gnu.trove.map.hash.THashMap;\r
-import gnu.trove.map.hash.TObjectIntHashMap;\r
-import gnu.trove.set.hash.THashSet;\r
-import gnu.trove.set.hash.TIntHashSet;\r
-\r
-public class ERuleset extends SimplifiableExpression {\r
- LocalRelation[] relations;\r
- DatalogRule[] rules;\r
- Expression in;\r
- \r
- public ERuleset(LocalRelation[] relations, DatalogRule[] rules, Expression in) {\r
- this.relations = relations;\r
- this.rules = rules;\r
- this.in = in;\r
- }\r
-\r
- public static class DatalogRule {\r
- public long location;\r
- public LocalRelation headRelation;\r
- public Expression[] headParameters;\r
- public Query body;\r
- public Variable[] variables;\r
- \r
- public DatalogRule(LocalRelation headRelation, Expression[] headParameters,\r
- Query body) {\r
- this.headRelation = headRelation;\r
- this.headParameters = headParameters;\r
- this.body = body;\r
- }\r
- \r
- public DatalogRule(long location, LocalRelation headRelation, Expression[] headParameters,\r
- Query body, Variable[] variables) {\r
- this.location = location;\r
- this.headRelation = headRelation;\r
- this.headParameters = headParameters;\r
- this.body = body;\r
- this.variables = variables;\r
- }\r
-\r
- public void setLocationDeep(long loc) {\r
- this.location = loc;\r
- for(Expression parameter : headParameters)\r
- parameter.setLocationDeep(loc);\r
- body.setLocationDeep(loc);\r
- }\r
- \r
- @Override\r
- public String toString() {\r
- StringBuilder b = new StringBuilder();\r
- ExpressionToStringVisitor visitor = new ExpressionToStringVisitor(b);\r
- visitor.visit(this);\r
- return b.toString();\r
- }\r
-\r
- public void forVariables(VariableProcedure procedure) {\r
- for(Expression headParameter : headParameters)\r
- headParameter.forVariables(procedure);\r
- body.forVariables(procedure);\r
- }\r
- }\r
- \r
- private void checkRuleTypes(TypingContext context) {\r
- // Create relation variables\r
- for(DatalogRule rule : rules) {\r
- Type[] parameterTypes = rule.headRelation.getParameterTypes();\r
- Expression[] parameters = rule.headParameters;\r
- for(Variable variable : rule.variables)\r
- variable.setType(Types.metaVar(Kinds.STAR));\r
- for(int i=0;i<parameters.length;++i)\r
- parameters[i] = parameters[i].checkType(context, parameterTypes[i]);\r
- rule.body.checkType(context);\r
- }\r
- }\r
- \r
- @Override\r
- public Expression checkBasicType(TypingContext context, Type requiredType) {\r
- checkRuleTypes(context);\r
- in = in.checkBasicType(context, requiredType);\r
- return compile(context);\r
- }\r
- \r
- @Override\r
- public Expression inferType(TypingContext context) {\r
- checkRuleTypes(context);\r
- in = in.inferType(context);\r
- return compile(context);\r
- }\r
- \r
- @Override\r
- public Expression checkIgnoredType(TypingContext context) {\r
- checkRuleTypes(context);\r
- in = in.checkIgnoredType(context);\r
- return compile(context);\r
- }\r
- \r
- @Override\r
- public void collectFreeVariables(THashSet<Variable> vars) {\r
- for(DatalogRule rule : rules) {\r
- for(Expression parameter : rule.headParameters)\r
- parameter.collectFreeVariables(vars);\r
- rule.body.collectFreeVariables(vars);\r
- for(Variable var : rule.variables)\r
- vars.remove(var);\r
- }\r
- in.collectFreeVariables(vars);\r
- }\r
- \r
- @Override\r
- public void collectRefs(TObjectIntHashMap<Object> allRefs,\r
- TIntHashSet refs) {\r
- for(DatalogRule rule : rules) {\r
- for(Expression parameter : rule.headParameters)\r
- parameter.collectRefs(allRefs, refs);\r
- rule.body.collectRefs(allRefs, refs);\r
- }\r
- in.collectRefs(allRefs, refs);\r
- }\r
- \r
- @Override\r
- public void collectVars(TObjectIntHashMap<Variable> allVars,\r
- TIntHashSet vars) {\r
- for(DatalogRule rule : rules) {\r
- for(Expression parameter : rule.headParameters)\r
- parameter.collectVars(allVars, vars);\r
- rule.body.collectVars(allVars, vars);\r
- }\r
- in.collectVars(allVars, vars);\r
- }\r
- \r
- @Override\r
- public void collectEffects(THashSet<Type> effects) {\r
- throw new InternalCompilerError(location, getClass().getSimpleName() + " does not support collectEffects.");\r
- }\r
- \r
- @Override\r
- public Expression decorate(ExpressionDecorator decorator) {\r
- return decorator.decorate(this);\r
- }\r
- \r
- @Override\r
- public Expression resolve(TranslationContext context) {\r
- throw new InternalCompilerError();\r
- }\r
- \r
- static class LocalRelationAux {\r
- Variable handleFunc;\r
- }\r
- \r
- public Expression compile(TypingContext context) {\r
- // Create a map from relations to their ids\r
- TObjectIntHashMap<SCLRelation> relationsToIds = new TObjectIntHashMap<SCLRelation>(relations.length,\r
- Constants.DEFAULT_LOAD_FACTOR, -1);\r
- for(int i=0;i<relations.length;++i)\r
- relationsToIds.put(relations[i], i);\r
- \r
- // Create a table from relations to the other relations they depend on\r
- TIntHashSet[] refsSets = new TIntHashSet[relations.length];\r
- int setCapacity = Math.min(Constants.DEFAULT_CAPACITY, relations.length);\r
- for(int i=0;i<relations.length;++i)\r
- refsSets[i] = new TIntHashSet(setCapacity);\r
- \r
- for(DatalogRule rule : rules) {\r
- int headRelationId = relationsToIds.get(rule.headRelation);\r
- TIntHashSet refsSet = refsSets[headRelationId];\r
- rule.body.collectRelationRefs(relationsToIds, refsSet);\r
- for(Expression parameter : rule.headParameters)\r
- parameter.collectRelationRefs(relationsToIds, refsSet);\r
- }\r
- \r
- // Convert refsSets to an array\r
- final int[][] refs = new int[relations.length][];\r
- for(int i=0;i<relations.length;++i)\r
- refs[i] = refsSets[i].toArray();\r
- \r
- // Find strongly connected components of the function refs\r
- final ArrayList<int[]> components = new ArrayList<int[]>();\r
- \r
- new StronglyConnectedComponents(relations.length) {\r
- @Override\r
- protected void reportComponent(int[] component) {\r
- components.add(component);\r
- }\r
- \r
- @Override\r
- protected int[] findDependencies(int u) {\r
- return refs[u];\r
- }\r
- }.findComponents();\r
- \r
- // If there is just one component, compile it\r
- if(components.size() == 1) {\r
- return compileStratified(context);\r
- }\r
- \r
- // Inverse of components array \r
- int[] strataPerRelation = new int[relations.length];\r
- for(int i=0;i<components.size();++i)\r
- for(int k : components.get(i))\r
- strataPerRelation[k] = i;\r
- \r
- // Collects rules belonging to each strata\r
- @SuppressWarnings("unchecked")\r
- ArrayList<DatalogRule>[] rulesPerStrata = new ArrayList[components.size()];\r
- for(int i=0;i<components.size();++i)\r
- rulesPerStrata[i] = new ArrayList<DatalogRule>();\r
- for(DatalogRule rule : rules) {\r
- int stratum = strataPerRelation[relationsToIds.get(rule.headRelation)];\r
- rulesPerStrata[stratum].add(rule);\r
- }\r
- \r
- // Create stratified system\r
- Expression cur = this.in;\r
- for(int stratum=components.size()-1;stratum >= 0;--stratum) {\r
- int[] cs = components.get(stratum);\r
- LocalRelation[] curRelations = new LocalRelation[cs.length];\r
- for(int i=0;i<cs.length;++i)\r
- curRelations[i] = relations[cs[i]];\r
- ArrayList<DatalogRule> curRules = rulesPerStrata[stratum];\r
- cur = new ERuleset(curRelations, curRules.toArray(new DatalogRule[curRules.size()]), cur).compileStratified(context);\r
- }\r
- return cur;\r
- }\r
- \r
- private Expression compileStratified(TypingContext context) {\r
- Expression continuation = Expressions.tuple();\r
- \r
- // Create stacks\r
- Variable[] stacks = new Variable[relations.length];\r
- for(int i=0;i<relations.length;++i) {\r
- LocalRelation relation = relations[i];\r
- Type[] parameterTypes = relation.getParameterTypes();\r
- stacks[i] = newVar("stack" + relation.getName(),\r
- Types.apply(Names.MList_T, Types.tuple(parameterTypes))\r
- );\r
- }\r
-\r
- // Simplify subexpressions and collect derivatives\r
- THashMap<LocalRelation, Diffable> diffables = new THashMap<LocalRelation, Diffable>(relations.length);\r
- for(int i=0;i<relations.length;++i) {\r
- LocalRelation relation = relations[i];\r
- Type[] parameterTypes = relation.getParameterTypes();\r
- Variable[] parameters = new Variable[parameterTypes.length];\r
- for(int j=0;j<parameterTypes.length;++j)\r
- parameters[j] = new Variable("p" + j, parameterTypes[j]);\r
- diffables.put(relations[i], new Diffable(i, relation, parameters));\r
- }\r
- @SuppressWarnings("unchecked")\r
- ArrayList<Expression>[] updateExpressions = (ArrayList<Expression>[])new ArrayList[relations.length];\r
- for(int i=0;i<relations.length;++i)\r
- updateExpressions[i] = new ArrayList<Expression>(2);\r
- ArrayList<Expression> seedExpressions = new ArrayList<Expression>(); \r
- for(DatalogRule rule : rules) {\r
- int id = diffables.get(rule.headRelation).id;\r
- Expression appendExp = apply(context.getCompilationContext(), Types.PROC, Names.MList_add, Types.tuple(rule.headRelation.getParameterTypes()),\r
- var(stacks[id]),\r
- tuple(rule.headParameters)\r
- );\r
- Diff[] diffs;\r
- try {\r
- diffs = rule.body.derivate(diffables);\r
- } catch(DerivateException e) {\r
- context.getErrorLog().log(e.location, "Recursion must not contain negations or aggragates.");\r
- return new EError();\r
- }\r
- for(Diff diff : diffs)\r
- updateExpressions[diff.id].add(((EWhen)new EWhen(rule.location, diff.query, appendExp, rule.variables).copy(context)).compile(context));\r
- if(diffs.length == 0)\r
- seedExpressions.add(((EWhen)new EWhen(rule.location, rule.body, appendExp, rule.variables).copy(context)).compile(context));\r
- else {\r
- Query query = rule.body.removeRelations((Set<SCLRelation>)(Set)diffables.keySet());\r
- if(query != Query.EMPTY_QUERY)\r
- seedExpressions.add(((EWhen)new EWhen(location, query, appendExp, rule.variables).copy(context)).compile(context));\r
- }\r
- }\r
- \r
- // Iterative solving of relations\r
-\r
- Variable[] loops = new Variable[relations.length];\r
- for(int i=0;i<loops.length;++i)\r
- loops[i] = newVar("loop" + relations[i].getName(), Types.functionE(Types.INTEGER, Types.PROC, Types.UNIT));\r
- continuation = seq(apply(Types.PROC, var(loops[0]), integer(relations.length-1)), continuation);\r
- \r
- Expression[] loopDefs = new Expression[relations.length];\r
- for(int i=0;i<relations.length;++i) {\r
- LocalRelation relation = relations[i];\r
- Type[] parameterTypes = relation.getParameterTypes();\r
- Variable[] parameters = diffables.get(relation).parameters;\r
- \r
- Variable counter = newVar("counter", Types.INTEGER);\r
- \r
- Type rowType = Types.tuple(parameterTypes);\r
- Variable row = newVar("row", rowType);\r
- \r
- Expression handleRow = tuple();\r
- for(Expression updateExpression : updateExpressions[i])\r
- handleRow = seq(updateExpression, handleRow);\r
- handleRow = if_(\r
- apply(context.getCompilationContext(), Types.PROC, Names.MSet_add, rowType,\r
- var(relation.table), var(row)),\r
- handleRow,\r
- tuple()\r
- );\r
- handleRow = seq(handleRow, apply(Types.PROC, var(loops[i]), integer(relations.length-1)));\r
- Expression failure =\r
- if_(isZeroInteger(var(counter)),\r
- tuple(),\r
- apply(Types.PROC, var(loops[(i+1)%relations.length]), addInteger(var(counter), integer(-1)))\r
- );\r
- Expression body = matchWithDefault(\r
- apply(context.getCompilationContext(), Types.PROC, Names.MList_removeLast, rowType, var(stacks[i])),\r
- Just(as(row, tuple(vars(parameters)))), handleRow,\r
- failure);\r
- \r
- loopDefs[i] = lambda(Types.PROC, counter, body); \r
- }\r
- continuation = letRec(loops, loopDefs, continuation);\r
- \r
- // Seed relations\r
- for(Expression seedExpression : seedExpressions)\r
- continuation = seq(seedExpression, continuation);\r
- \r
- // Create stacks\r
- for(int i=0;i<stacks.length;++i)\r
- continuation = let(stacks[i],\r
- apply(context.getCompilationContext(), Types.PROC, Names.MList_create, Types.tuple(relations[i].getParameterTypes()), tuple()),\r
- continuation);\r
- \r
- continuation = ForcedClosure.forceClosure(continuation, SCLCompilerConfiguration.EVERY_DATALOG_STRATUM_IN_SEPARATE_METHOD);\r
- \r
- // Create relations\r
- for(LocalRelation relation : relations)\r
- continuation = let(relation.table,\r
- apply(context.getCompilationContext(), Types.PROC, Names.MSet_create, Types.tuple(relation.getParameterTypes()), tuple()),\r
- continuation);\r
- \r
- return seq(continuation, in);\r
- }\r
-\r
- @Override\r
- protected void updateType() throws MatchException {\r
- setType(in.getType());\r
- }\r
- \r
- @Override\r
- public void setLocationDeep(long loc) {\r
- if(location == Locations.NO_LOCATION) {\r
- location = loc;\r
- for(DatalogRule rule : rules)\r
- rule.setLocationDeep(loc);\r
- }\r
- }\r
- \r
- @Override\r
- public void accept(ExpressionVisitor visitor) {\r
- visitor.visit(this);\r
- }\r
-\r
- public DatalogRule[] getRules() {\r
- return rules;\r
- }\r
- \r
- public Expression getIn() {\r
- return in;\r
- }\r
-\r
- @Override\r
- public void forVariables(VariableProcedure procedure) {\r
- for(DatalogRule rule : rules)\r
- rule.forVariables(procedure);\r
- in.forVariables(procedure);\r
- }\r
- \r
- @Override\r
- public Expression accept(ExpressionTransformer transformer) {\r
- return transformer.transform(this);\r
- }\r
-\r
-}\r
+package org.simantics.scl.compiler.elaboration.expressions;
+
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.Just;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.addInteger;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.apply;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.as;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.if_;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.integer;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.isZeroInteger;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.lambda;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.let;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.letRec;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.matchWithDefault;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.newVar;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.seq;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.tuple;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.var;
+import static org.simantics.scl.compiler.elaboration.expressions.Expressions.vars;
+
+import java.util.ArrayList;
+import java.util.Set;
+
+import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
+import org.simantics.scl.compiler.common.names.Names;
+import org.simantics.scl.compiler.elaboration.contexts.TranslationContext;
+import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
+import org.simantics.scl.compiler.elaboration.expressions.printing.ExpressionToStringVisitor;
+import org.simantics.scl.compiler.elaboration.query.Query;
+import org.simantics.scl.compiler.elaboration.query.Query.Diff;
+import org.simantics.scl.compiler.elaboration.query.Query.Diffable;
+import org.simantics.scl.compiler.elaboration.query.compilation.DerivateException;
+import org.simantics.scl.compiler.elaboration.relations.LocalRelation;
+import org.simantics.scl.compiler.elaboration.relations.SCLRelation;
+import org.simantics.scl.compiler.errors.Locations;
+import org.simantics.scl.compiler.internal.elaboration.utils.ForcedClosure;
+import org.simantics.scl.compiler.internal.elaboration.utils.StronglyConnectedComponents;
+import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
+import org.simantics.scl.compiler.types.Type;
+import org.simantics.scl.compiler.types.Types;
+import org.simantics.scl.compiler.types.exceptions.MatchException;
+import org.simantics.scl.compiler.types.kinds.Kinds;
+
+import gnu.trove.impl.Constants;
+import gnu.trove.map.hash.THashMap;
+import gnu.trove.map.hash.TObjectIntHashMap;
+import gnu.trove.set.hash.TIntHashSet;
+
+public class ERuleset extends SimplifiableExpression {
+ LocalRelation[] relations;
+ public DatalogRule[] rules;
+ public Expression in;
+
+ public ERuleset(LocalRelation[] relations, DatalogRule[] rules, Expression in) {
+ this.relations = relations;
+ this.rules = rules;
+ this.in = in;
+ }
+
+ public static class DatalogRule {
+ public long location;
+ public LocalRelation headRelation;
+ public Expression[] headParameters;
+ public Query body;
+ public Variable[] variables;
+
+ public DatalogRule(LocalRelation headRelation, Expression[] headParameters,
+ Query body) {
+ this.headRelation = headRelation;
+ this.headParameters = headParameters;
+ this.body = body;
+ }
+
+ public DatalogRule(long location, LocalRelation headRelation, Expression[] headParameters,
+ Query body, Variable[] variables) {
+ this.location = location;
+ this.headRelation = headRelation;
+ this.headParameters = headParameters;
+ this.body = body;
+ this.variables = variables;
+ }
+
+ public void setLocationDeep(long loc) {
+ this.location = loc;
+ for(Expression parameter : headParameters)
+ parameter.setLocationDeep(loc);
+ body.setLocationDeep(loc);
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder b = new StringBuilder();
+ ExpressionToStringVisitor visitor = new ExpressionToStringVisitor(b);
+ visitor.visit(this);
+ return b.toString();
+ }
+ }
+
+ private void checkRuleTypes(TypingContext context) {
+ // Create relation variables
+ for(DatalogRule rule : rules) {
+ Type[] parameterTypes = rule.headRelation.getParameterTypes();
+ Expression[] parameters = rule.headParameters;
+ for(Variable variable : rule.variables)
+ variable.setType(Types.metaVar(Kinds.STAR));
+ for(int i=0;i<parameters.length;++i)
+ parameters[i] = parameters[i].checkType(context, parameterTypes[i]);
+ rule.body.checkType(context);
+ }
+ }
+
+ @Override
+ public Expression checkBasicType(TypingContext context, Type requiredType) {
+ checkRuleTypes(context);
+ in = in.checkBasicType(context, requiredType);
+ return compile(context);
+ }
+
+ @Override
+ public Expression inferType(TypingContext context) {
+ checkRuleTypes(context);
+ in = in.inferType(context);
+ return compile(context);
+ }
+
+ @Override
+ public Expression checkIgnoredType(TypingContext context) {
+ checkRuleTypes(context);
+ in = in.checkIgnoredType(context);
+ return compile(context);
+ }
+
+ @Override
+ public void collectVars(TObjectIntHashMap<Variable> allVars,
+ TIntHashSet vars) {
+ for(DatalogRule rule : rules) {
+ for(Expression parameter : rule.headParameters)
+ parameter.collectVars(allVars, vars);
+ rule.body.collectVars(allVars, vars);
+ }
+ in.collectVars(allVars, vars);
+ }
+
+ @Override
+ public Expression resolve(TranslationContext context) {
+ throw new InternalCompilerError();
+ }
+
+ static class LocalRelationAux {
+ Variable handleFunc;
+ }
+
+ public Expression compile(TypingContext context) {
+ // Create a map from relations to their ids
+ TObjectIntHashMap<SCLRelation> relationsToIds = new TObjectIntHashMap<SCLRelation>(relations.length,
+ Constants.DEFAULT_LOAD_FACTOR, -1);
+ for(int i=0;i<relations.length;++i)
+ relationsToIds.put(relations[i], i);
+
+ // Create a table from relations to the other relations they depend on
+ TIntHashSet[] refsSets = new TIntHashSet[relations.length];
+ int setCapacity = Math.min(Constants.DEFAULT_CAPACITY, relations.length);
+ for(int i=0;i<relations.length;++i)
+ refsSets[i] = new TIntHashSet(setCapacity);
+
+ for(DatalogRule rule : rules) {
+ int headRelationId = relationsToIds.get(rule.headRelation);
+ TIntHashSet refsSet = refsSets[headRelationId];
+ rule.body.collectRelationRefs(relationsToIds, refsSet);
+ for(Expression parameter : rule.headParameters)
+ parameter.collectRelationRefs(relationsToIds, refsSet);
+ }
+
+ // Convert refsSets to an array
+ final int[][] refs = new int[relations.length][];
+ for(int i=0;i<relations.length;++i)
+ refs[i] = refsSets[i].toArray();
+
+ // Find strongly connected components of the function refs
+ final ArrayList<int[]> components = new ArrayList<int[]>();
+
+ new StronglyConnectedComponents(relations.length) {
+ @Override
+ protected void reportComponent(int[] component) {
+ components.add(component);
+ }
+
+ @Override
+ protected int[] findDependencies(int u) {
+ return refs[u];
+ }
+ }.findComponents();
+
+ // If there is just one component, compile it
+ if(components.size() == 1) {
+ return compileStratified(context);
+ }
+
+ // Inverse of components array
+ int[] strataPerRelation = new int[relations.length];
+ for(int i=0;i<components.size();++i)
+ for(int k : components.get(i))
+ strataPerRelation[k] = i;
+
+ // Collects rules belonging to each strata
+ @SuppressWarnings("unchecked")
+ ArrayList<DatalogRule>[] rulesPerStrata = new ArrayList[components.size()];
+ for(int i=0;i<components.size();++i)
+ rulesPerStrata[i] = new ArrayList<DatalogRule>();
+ for(DatalogRule rule : rules) {
+ int stratum = strataPerRelation[relationsToIds.get(rule.headRelation)];
+ rulesPerStrata[stratum].add(rule);
+ }
+
+ // Create stratified system
+ Expression cur = this.in;
+ for(int stratum=components.size()-1;stratum >= 0;--stratum) {
+ int[] cs = components.get(stratum);
+ LocalRelation[] curRelations = new LocalRelation[cs.length];
+ for(int i=0;i<cs.length;++i)
+ curRelations[i] = relations[cs[i]];
+ ArrayList<DatalogRule> curRules = rulesPerStrata[stratum];
+ cur = new ERuleset(curRelations, curRules.toArray(new DatalogRule[curRules.size()]), cur).compileStratified(context);
+ }
+ return cur;
+ }
+
+ private Expression compileStratified(TypingContext context) {
+ Expression continuation = Expressions.tuple();
+
+ // Create stacks
+ Variable[] stacks = new Variable[relations.length];
+ for(int i=0;i<relations.length;++i) {
+ LocalRelation relation = relations[i];
+ Type[] parameterTypes = relation.getParameterTypes();
+ stacks[i] = newVar("stack" + relation.getName(),
+ Types.apply(Names.MList_T, Types.tuple(parameterTypes))
+ );
+ }
+
+ // Simplify subexpressions and collect derivatives
+ THashMap<LocalRelation, Diffable> diffables = new THashMap<LocalRelation, Diffable>(relations.length);
+ for(int i=0;i<relations.length;++i) {
+ LocalRelation relation = relations[i];
+ Type[] parameterTypes = relation.getParameterTypes();
+ Variable[] parameters = new Variable[parameterTypes.length];
+ for(int j=0;j<parameterTypes.length;++j)
+ parameters[j] = new Variable("p" + j, parameterTypes[j]);
+ diffables.put(relations[i], new Diffable(i, relation, parameters));
+ }
+ @SuppressWarnings("unchecked")
+ ArrayList<Expression>[] updateExpressions = (ArrayList<Expression>[])new ArrayList[relations.length];
+ for(int i=0;i<relations.length;++i)
+ updateExpressions[i] = new ArrayList<Expression>(2);
+ ArrayList<Expression> seedExpressions = new ArrayList<Expression>();
+ for(DatalogRule rule : rules) {
+ int id = diffables.get(rule.headRelation).id;
+ Expression appendExp = apply(context.getCompilationContext(), Types.PROC, Names.MList_add, Types.tuple(rule.headRelation.getParameterTypes()),
+ var(stacks[id]),
+ tuple(rule.headParameters)
+ );
+ Diff[] diffs;
+ try {
+ diffs = rule.body.derivate(diffables);
+ } catch(DerivateException e) {
+ context.getErrorLog().log(e.location, "Recursion must not contain negations or aggragates.");
+ return new EError();
+ }
+ for(Diff diff : diffs)
+ updateExpressions[diff.id].add(((EWhen)new EWhen(rule.location, diff.query, appendExp, rule.variables).copy(context)).compile(context));
+ if(diffs.length == 0)
+ seedExpressions.add(((EWhen)new EWhen(rule.location, rule.body, appendExp, rule.variables).copy(context)).compile(context));
+ else {
+ Query query = rule.body.removeRelations((Set<SCLRelation>)(Set)diffables.keySet());
+ if(query != Query.EMPTY_QUERY)
+ seedExpressions.add(((EWhen)new EWhen(location, query, appendExp, rule.variables).copy(context)).compile(context));
+ }
+ }
+
+ // Iterative solving of relations
+
+ Variable[] loops = new Variable[relations.length];
+ for(int i=0;i<loops.length;++i)
+ loops[i] = newVar("loop" + relations[i].getName(), Types.functionE(Types.INTEGER, Types.PROC, Types.UNIT));
+ continuation = seq(apply(Types.PROC, var(loops[0]), integer(relations.length-1)), continuation);
+
+ Expression[] loopDefs = new Expression[relations.length];
+ for(int i=0;i<relations.length;++i) {
+ LocalRelation relation = relations[i];
+ Type[] parameterTypes = relation.getParameterTypes();
+ Variable[] parameters = diffables.get(relation).parameters;
+
+ Variable counter = newVar("counter", Types.INTEGER);
+
+ Type rowType = Types.tuple(parameterTypes);
+ Variable row = newVar("row", rowType);
+
+ Expression handleRow = tuple();
+ for(Expression updateExpression : updateExpressions[i])
+ handleRow = seq(updateExpression, handleRow);
+ handleRow = if_(
+ apply(context.getCompilationContext(), Types.PROC, Names.MSet_add, rowType,
+ var(relation.table), var(row)),
+ handleRow,
+ tuple()
+ );
+ handleRow = seq(handleRow, apply(Types.PROC, var(loops[i]), integer(relations.length-1)));
+ Expression failure =
+ if_(isZeroInteger(var(counter)),
+ tuple(),
+ apply(Types.PROC, var(loops[(i+1)%relations.length]), addInteger(var(counter), integer(-1)))
+ );
+ Expression body = matchWithDefault(
+ apply(context.getCompilationContext(), Types.PROC, Names.MList_removeLast, rowType, var(stacks[i])),
+ Just(as(row, tuple(vars(parameters)))), handleRow,
+ failure);
+
+ loopDefs[i] = lambda(Types.PROC, counter, body);
+ }
+ continuation = letRec(loops, loopDefs, continuation);
+
+ // Seed relations
+ for(Expression seedExpression : seedExpressions)
+ continuation = seq(seedExpression, continuation);
+
+ // Create stacks
+ for(int i=0;i<stacks.length;++i)
+ continuation = let(stacks[i],
+ apply(context.getCompilationContext(), Types.PROC, Names.MList_create, Types.tuple(relations[i].getParameterTypes()), tuple()),
+ continuation);
+
+ continuation = ForcedClosure.forceClosure(continuation, SCLCompilerConfiguration.EVERY_DATALOG_STRATUM_IN_SEPARATE_METHOD);
+
+ // Create relations
+ for(LocalRelation relation : relations)
+ continuation = let(relation.table,
+ apply(context.getCompilationContext(), Types.PROC, Names.MSet_create, Types.tuple(relation.getParameterTypes()), tuple()),
+ continuation);
+
+ return seq(continuation, in);
+ }
+
+ @Override
+ protected void updateType() throws MatchException {
+ setType(in.getType());
+ }
+
+ @Override
+ public void setLocationDeep(long loc) {
+ if(location == Locations.NO_LOCATION) {
+ location = loc;
+ for(DatalogRule rule : rules)
+ rule.setLocationDeep(loc);
+ }
+ }
+
+ @Override
+ public void accept(ExpressionVisitor visitor) {
+ visitor.visit(this);
+ }
+
+ public DatalogRule[] getRules() {
+ return rules;
+ }
+
+ public Expression getIn() {
+ return in;
+ }
+
+ @Override
+ public Expression accept(ExpressionTransformer transformer) {
+ return transformer.transform(this);
+ }
+
+}
Code Review / simantics / platform.git / blobdiff