bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/expressions/ERuleset.java

   1 package org.simantics.scl.compiler.elaboration.expressions;
   2
   3 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.Just;
   4 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.addInteger;
   5 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.apply;
   6 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.as;
   7 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.if_;
   8 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.integer;
   9 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.isZeroInteger;
  10 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.lambda;
  11 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.let;
  12 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.letRec;
  13 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.matchWithDefault;
  14 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.newVar;
  15 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.seq;
  16 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.tuple;
  17 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.var;
  18 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.vars;
  19
  20 import java.util.ArrayList;
  21 import java.util.Set;
  22
  23 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
  24 import org.simantics.scl.compiler.common.names.Names;
  25 import org.simantics.scl.compiler.elaboration.contexts.TranslationContext;
  26 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
  27 import org.simantics.scl.compiler.elaboration.expressions.printing.ExpressionToStringVisitor;
  28 import org.simantics.scl.compiler.elaboration.query.Query;
  29 import org.simantics.scl.compiler.elaboration.query.Query.Diff;
  30 import org.simantics.scl.compiler.elaboration.query.Query.Diffable;
  31 import org.simantics.scl.compiler.elaboration.query.compilation.DerivateException;
  32 import org.simantics.scl.compiler.elaboration.relations.LocalRelation;
  33 import org.simantics.scl.compiler.elaboration.relations.SCLRelation;
  34 import org.simantics.scl.compiler.errors.Locations;
  35 import org.simantics.scl.compiler.internal.elaboration.utils.ForcedClosure;
  36 import org.simantics.scl.compiler.internal.elaboration.utils.StronglyConnectedComponents;
  37 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
  38 import org.simantics.scl.compiler.types.Type;
  39 import org.simantics.scl.compiler.types.Types;
  40 import org.simantics.scl.compiler.types.exceptions.MatchException;
  41 import org.simantics.scl.compiler.types.kinds.Kinds;
  42
  43 import gnu.trove.impl.Constants;
  44 import gnu.trove.map.hash.THashMap;
  45 import gnu.trove.map.hash.TObjectIntHashMap;
  46 import gnu.trove.set.hash.THashSet;
  47 import gnu.trove.set.hash.TIntHashSet;
  48
  49 public class ERuleset extends SimplifiableExpression {
  50     LocalRelation[] relations;
  51     DatalogRule[] rules;
  52     Expression in;
  53
  54     public ERuleset(LocalRelation[] relations, DatalogRule[] rules, Expression in) {
  55         this.relations = relations;
  56         this.rules = rules;
  57         this.in = in;
  58     }
  59
  60     public static class DatalogRule {
  61         public long location;
  62         public LocalRelation headRelation;
  63         public Expression[] headParameters;
  64         public Query body;
  65         public Variable[] variables;
  66
  67         public DatalogRule(LocalRelation headRelation, Expression[] headParameters,
  68                 Query body) {
  69             this.headRelation = headRelation;
  70             this.headParameters = headParameters;
  71             this.body = body;
  72         }
  73
  74         public DatalogRule(long location, LocalRelation headRelation, Expression[] headParameters,
  75                 Query body, Variable[] variables) {
  76             this.location = location;
  77             this.headRelation = headRelation;
  78             this.headParameters = headParameters;
  79             this.body = body;
  80             this.variables = variables;
  81         }
  82
  83         public void setLocationDeep(long loc) {
  84             this.location = loc;
  85             for(Expression parameter : headParameters)
  86                 parameter.setLocationDeep(loc);
  87             body.setLocationDeep(loc);
  88         }
  89
  90         @Override
  91         public String toString() {
  92             StringBuilder b = new StringBuilder();
  93             ExpressionToStringVisitor visitor = new ExpressionToStringVisitor(b);
  94             visitor.visit(this);
  95             return b.toString();
  96         }
  97     }
  98
  99     private void checkRuleTypes(TypingContext context) {
 100         // Create relation variables
 101         for(DatalogRule rule : rules) {
 102             Type[] parameterTypes =  rule.headRelation.getParameterTypes();
 103             Expression[] parameters = rule.headParameters;
 104             for(Variable variable : rule.variables)
 105                 variable.setType(Types.metaVar(Kinds.STAR));
 106             for(int i=0;i<parameters.length;++i)
 107                 parameters[i] = parameters[i].checkType(context, parameterTypes[i]);
 108             rule.body.checkType(context);
 109         }
 110     }
 111
 112     @Override
 113     public Expression checkBasicType(TypingContext context, Type requiredType) {
 114         checkRuleTypes(context);
 115         in = in.checkBasicType(context, requiredType);
 116         return compile(context);
 117     }
 118
 119     @Override
 120     public Expression inferType(TypingContext context) {
 121         checkRuleTypes(context);
 122         in = in.inferType(context);
 123         return compile(context);
 124     }
 125
 126     @Override
 127     public Expression checkIgnoredType(TypingContext context) {
 128         checkRuleTypes(context);
 129         in = in.checkIgnoredType(context);
 130         return compile(context);
 131     }
 132
 133     @Override
 134     public void collectFreeVariables(THashSet<Variable> vars) {
 135         for(DatalogRule rule : rules) {
 136             for(Expression parameter : rule.headParameters)
 137                 parameter.collectFreeVariables(vars);
 138             rule.body.collectFreeVariables(vars);
 139             for(Variable var : rule.variables)
 140                 vars.remove(var);
 141         }
 142         in.collectFreeVariables(vars);
 143     }
 144
 145     @Override
 146     public void collectRefs(TObjectIntHashMap<Object> allRefs,
 147             TIntHashSet refs) {
 148         for(DatalogRule rule : rules) {
 149             for(Expression parameter : rule.headParameters)
 150                 parameter.collectRefs(allRefs, refs);
 151             rule.body.collectRefs(allRefs, refs);
 152         }
 153         in.collectRefs(allRefs, refs);
 154     }
 155
 156     @Override
 157     public void collectVars(TObjectIntHashMap<Variable> allVars,
 158             TIntHashSet vars) {
 159         for(DatalogRule rule : rules) {
 160             for(Expression parameter : rule.headParameters)
 161                 parameter.collectVars(allVars, vars);
 162             rule.body.collectVars(allVars, vars);
 163         }
 164         in.collectVars(allVars, vars);
 165     }
 166
 167     @Override
 168     public void collectEffects(THashSet<Type> effects) {
 169         throw new InternalCompilerError(location, getClass().getSimpleName() + " does not support collectEffects.");
 170     }
 171
 172     @Override
 173     public Expression resolve(TranslationContext context) {
 174         throw new InternalCompilerError();
 175     }
 176
 177     static class LocalRelationAux {
 178         Variable handleFunc;
 179     }
 180
 181     public Expression compile(TypingContext context) {
 182         // Create a map from relations to their ids
 183         TObjectIntHashMap<SCLRelation> relationsToIds = new TObjectIntHashMap<SCLRelation>(relations.length,
 184                 Constants.DEFAULT_LOAD_FACTOR, -1);
 185         for(int i=0;i<relations.length;++i)
 186             relationsToIds.put(relations[i], i);
 187
 188         // Create a table from relations to the other relations they depend on
 189         TIntHashSet[] refsSets = new TIntHashSet[relations.length];
 190         int setCapacity = Math.min(Constants.DEFAULT_CAPACITY, relations.length);
 191         for(int i=0;i<relations.length;++i)
 192             refsSets[i] = new TIntHashSet(setCapacity);
 193
 194         for(DatalogRule rule : rules) {
 195             int headRelationId = relationsToIds.get(rule.headRelation);
 196             TIntHashSet refsSet = refsSets[headRelationId];
 197             rule.body.collectRelationRefs(relationsToIds, refsSet);
 198             for(Expression parameter : rule.headParameters)
 199                 parameter.collectRelationRefs(relationsToIds, refsSet);
 200         }
 201
 202         // Convert refsSets to an array
 203         final int[][] refs = new int[relations.length][];
 204         for(int i=0;i<relations.length;++i)
 205             refs[i] = refsSets[i].toArray();
 206
 207         // Find strongly connected components of the function refs
 208         final ArrayList<int[]> components = new ArrayList<int[]>();
 209
 210         new StronglyConnectedComponents(relations.length) {
 211             @Override
 212             protected void reportComponent(int[] component) {
 213                 components.add(component);
 214             }
 215
 216             @Override
 217             protected int[] findDependencies(int u) {
 218                 return refs[u];
 219             }
 220         }.findComponents();
 221
 222         // If there is just one component, compile it
 223         if(components.size() == 1) {
 224             return compileStratified(context);
 225         }
 226
 227         // Inverse of components array
 228         int[] strataPerRelation = new int[relations.length];
 229         for(int i=0;i<components.size();++i)
 230             for(int k : components.get(i))
 231                 strataPerRelation[k] = i;
 232
 233         // Collects rules belonging to each strata
 234         @SuppressWarnings("unchecked")
 235         ArrayList<DatalogRule>[] rulesPerStrata = new ArrayList[components.size()];
 236         for(int i=0;i<components.size();++i)
 237             rulesPerStrata[i] = new ArrayList<DatalogRule>();
 238         for(DatalogRule rule : rules) {
 239             int stratum = strataPerRelation[relationsToIds.get(rule.headRelation)];
 240             rulesPerStrata[stratum].add(rule);
 241         }
 242
 243         // Create stratified system
 244         Expression cur = this.in;
 245         for(int stratum=components.size()-1;stratum >= 0;--stratum) {
 246             int[] cs = components.get(stratum);
 247             LocalRelation[] curRelations = new LocalRelation[cs.length];
 248             for(int i=0;i<cs.length;++i)
 249                 curRelations[i] = relations[cs[i]];
 250             ArrayList<DatalogRule> curRules = rulesPerStrata[stratum];
 251             cur = new ERuleset(curRelations, curRules.toArray(new DatalogRule[curRules.size()]), cur).compileStratified(context);
 252         }
 253         return cur;
 254     }
 255
 256     private Expression compileStratified(TypingContext context) {
 257         Expression continuation = Expressions.tuple();
 258
 259         // Create stacks
 260         Variable[] stacks = new Variable[relations.length];
 261         for(int i=0;i<relations.length;++i) {
 262             LocalRelation relation = relations[i];
 263             Type[] parameterTypes = relation.getParameterTypes();
 264             stacks[i] = newVar("stack" + relation.getName(),
 265                     Types.apply(Names.MList_T, Types.tuple(parameterTypes))
 266                     );
 267         }
 268
 269         // Simplify subexpressions and collect derivatives
 270         THashMap<LocalRelation, Diffable> diffables = new THashMap<LocalRelation, Diffable>(relations.length);
 271         for(int i=0;i<relations.length;++i) {
 272             LocalRelation relation = relations[i];
 273             Type[] parameterTypes = relation.getParameterTypes();
 274             Variable[] parameters = new Variable[parameterTypes.length];
 275             for(int j=0;j<parameterTypes.length;++j)
 276                 parameters[j] = new Variable("p" + j, parameterTypes[j]);
 277             diffables.put(relations[i], new Diffable(i, relation, parameters));
 278         }
 279         @SuppressWarnings("unchecked")
 280         ArrayList<Expression>[] updateExpressions = (ArrayList<Expression>[])new ArrayList[relations.length];
 281         for(int i=0;i<relations.length;++i)
 282             updateExpressions[i] = new ArrayList<Expression>(2);
 283         ArrayList<Expression> seedExpressions = new ArrayList<Expression>();
 284         for(DatalogRule rule : rules) {
 285             int id = diffables.get(rule.headRelation).id;
 286             Expression appendExp = apply(context.getCompilationContext(), Types.PROC, Names.MList_add, Types.tuple(rule.headRelation.getParameterTypes()),
 287                     var(stacks[id]),
 288                     tuple(rule.headParameters)
 289                     );
 290             Diff[] diffs;
 291             try {
 292                 diffs = rule.body.derivate(diffables);
 293             } catch(DerivateException e) {
 294                 context.getErrorLog().log(e.location, "Recursion must not contain negations or aggragates.");
 295                 return new EError();
 296             }
 297             for(Diff diff : diffs)
 298                 updateExpressions[diff.id].add(((EWhen)new EWhen(rule.location, diff.query, appendExp, rule.variables).copy(context)).compile(context));
 299             if(diffs.length == 0)
 300                 seedExpressions.add(((EWhen)new EWhen(rule.location, rule.body, appendExp, rule.variables).copy(context)).compile(context));
 301             else {
 302                 Query query = rule.body.removeRelations((Set<SCLRelation>)(Set)diffables.keySet());
 303                 if(query != Query.EMPTY_QUERY)
 304                     seedExpressions.add(((EWhen)new EWhen(location, query, appendExp, rule.variables).copy(context)).compile(context));
 305             }
 306         }
 307
 308         // Iterative solving of relations
 309
 310         Variable[] loops = new Variable[relations.length];
 311         for(int i=0;i<loops.length;++i)
 312             loops[i] = newVar("loop" + relations[i].getName(), Types.functionE(Types.INTEGER, Types.PROC, Types.UNIT));
 313         continuation = seq(apply(Types.PROC, var(loops[0]), integer(relations.length-1)), continuation);
 314
 315         Expression[] loopDefs = new Expression[relations.length];
 316         for(int i=0;i<relations.length;++i) {
 317             LocalRelation relation = relations[i];
 318             Type[] parameterTypes = relation.getParameterTypes();
 319             Variable[] parameters = diffables.get(relation).parameters;
 320
 321             Variable counter = newVar("counter", Types.INTEGER);
 322
 323             Type rowType = Types.tuple(parameterTypes);
 324             Variable row = newVar("row", rowType);
 325
 326             Expression handleRow = tuple();
 327             for(Expression updateExpression : updateExpressions[i])
 328                 handleRow = seq(updateExpression, handleRow);
 329             handleRow = if_(
 330                     apply(context.getCompilationContext(), Types.PROC, Names.MSet_add, rowType,
 331                             var(relation.table), var(row)),
 332                     handleRow,
 333                     tuple()
 334                     );
 335             handleRow = seq(handleRow, apply(Types.PROC, var(loops[i]), integer(relations.length-1)));
 336             Expression failure =
 337                     if_(isZeroInteger(var(counter)),
 338                         tuple(),
 339                         apply(Types.PROC, var(loops[(i+1)%relations.length]), addInteger(var(counter), integer(-1)))
 340                        );
 341             Expression body = matchWithDefault(
 342                     apply(context.getCompilationContext(), Types.PROC, Names.MList_removeLast, rowType, var(stacks[i])),
 343                     Just(as(row, tuple(vars(parameters)))), handleRow,
 344                     failure);
 345
 346             loopDefs[i] = lambda(Types.PROC, counter, body);
 347         }
 348         continuation = letRec(loops, loopDefs, continuation);
 349
 350         // Seed relations
 351         for(Expression seedExpression : seedExpressions)
 352             continuation = seq(seedExpression, continuation);
 353
 354         // Create stacks
 355         for(int i=0;i<stacks.length;++i)
 356             continuation = let(stacks[i],
 357                     apply(context.getCompilationContext(), Types.PROC, Names.MList_create, Types.tuple(relations[i].getParameterTypes()), tuple()),
 358                     continuation);
 359
 360         continuation = ForcedClosure.forceClosure(continuation, SCLCompilerConfiguration.EVERY_DATALOG_STRATUM_IN_SEPARATE_METHOD);
 361
 362         // Create relations
 363         for(LocalRelation relation : relations)
 364             continuation = let(relation.table,
 365                     apply(context.getCompilationContext(), Types.PROC, Names.MSet_create, Types.tuple(relation.getParameterTypes()), tuple()),
 366                     continuation);
 367
 368         return seq(continuation, in);
 369     }
 370
 371     @Override
 372     protected void updateType() throws MatchException {
 373         setType(in.getType());
 374     }
 375
 376     @Override
 377     public void setLocationDeep(long loc) {
 378         if(location == Locations.NO_LOCATION) {
 379             location = loc;
 380             for(DatalogRule rule : rules)
 381                 rule.setLocationDeep(loc);
 382         }
 383     }
 384
 385     @Override
 386     public void accept(ExpressionVisitor visitor) {
 387         visitor.visit(this);
 388     }
 389
 390     public DatalogRule[] getRules() {
 391         return rules;
 392     }
 393
 394     public Expression getIn() {
 395         return in;
 396     }
 397
 398     @Override
 399     public Expression accept(ExpressionTransformer transformer) {
 400         return transformer.transform(this);
 401     }
 402
 403 }