--- /dev/null
+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.Name;\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.TCon;\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 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 static final TCon MSet = Types.con("MSet", "T");\r
+ private static final Name MSet_add = Name.create("MSet", "add");\r
+ private static final Name MSet_create = Name.create("MSet", "create");\r
+\r
+ private static final TCon MList = Types.con("MList", "T");\r
+ private static final Name MList_add = Name.create("MList", "add");\r
+ private static final Name MList_create = Name.create("MList", "create");\r
+ private static final Name MList_removeLast = Name.create("MList", "removeLast");\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(MList, 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, Types.PROC, 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, Types.PROC, 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, Types.PROC, 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, Types.PROC, 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, Types.PROC, 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
Code Review / simantics / platform.git / blobdiff