e84e0500c41bb045547266a9f924ea62b22d9b10
[simantics/platform.git] / 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 collectVars(TObjectIntHashMap<Variable> allVars,
147             TIntHashSet vars) {
148         for(DatalogRule rule : rules) {
149             for(Expression parameter : rule.headParameters)
150                 parameter.collectVars(allVars, vars);
151             rule.body.collectVars(allVars, vars);
152         }
153         in.collectVars(allVars, vars);
154     }
155     
156     @Override
157     public Expression resolve(TranslationContext context) {
158         throw new InternalCompilerError();
159     }
160     
161     static class LocalRelationAux {
162         Variable handleFunc;
163     }
164     
165     public Expression compile(TypingContext context) {
166         // Create a map from relations to their ids
167         TObjectIntHashMap<SCLRelation> relationsToIds = new TObjectIntHashMap<SCLRelation>(relations.length,
168                 Constants.DEFAULT_LOAD_FACTOR, -1);
169         for(int i=0;i<relations.length;++i)
170             relationsToIds.put(relations[i], i);
171         
172         // Create a table from relations to the other relations they depend on
173         TIntHashSet[] refsSets = new TIntHashSet[relations.length];
174         int setCapacity = Math.min(Constants.DEFAULT_CAPACITY, relations.length);
175         for(int i=0;i<relations.length;++i)
176             refsSets[i] = new TIntHashSet(setCapacity);
177         
178         for(DatalogRule rule : rules) {
179             int headRelationId = relationsToIds.get(rule.headRelation);
180             TIntHashSet refsSet = refsSets[headRelationId];
181             rule.body.collectRelationRefs(relationsToIds, refsSet);
182             for(Expression parameter : rule.headParameters)
183                 parameter.collectRelationRefs(relationsToIds, refsSet);
184         }
185         
186         // Convert refsSets to an array
187         final int[][] refs = new int[relations.length][];
188         for(int i=0;i<relations.length;++i)
189             refs[i] = refsSets[i].toArray();
190         
191         // Find strongly connected components of the function refs
192         final ArrayList<int[]> components = new ArrayList<int[]>();
193         
194         new StronglyConnectedComponents(relations.length) {
195             @Override
196             protected void reportComponent(int[] component) {
197                 components.add(component);
198             }
199             
200             @Override
201             protected int[] findDependencies(int u) {
202                 return refs[u];
203             }
204         }.findComponents();
205         
206         // If there is just one component, compile it
207         if(components.size() == 1) {
208             return compileStratified(context);
209         }
210         
211         // Inverse of components array 
212         int[] strataPerRelation = new int[relations.length];
213         for(int i=0;i<components.size();++i)
214             for(int k : components.get(i))
215                 strataPerRelation[k] = i;
216         
217         // Collects rules belonging to each strata
218         @SuppressWarnings("unchecked")
219         ArrayList<DatalogRule>[] rulesPerStrata = new ArrayList[components.size()];
220         for(int i=0;i<components.size();++i)
221             rulesPerStrata[i] = new ArrayList<DatalogRule>();
222         for(DatalogRule rule : rules) {
223             int stratum = strataPerRelation[relationsToIds.get(rule.headRelation)];
224             rulesPerStrata[stratum].add(rule);
225         }
226         
227         // Create stratified system
228         Expression cur = this.in;
229         for(int stratum=components.size()-1;stratum >= 0;--stratum) {
230             int[] cs = components.get(stratum);
231             LocalRelation[] curRelations = new LocalRelation[cs.length];
232             for(int i=0;i<cs.length;++i)
233                 curRelations[i] = relations[cs[i]];
234             ArrayList<DatalogRule> curRules = rulesPerStrata[stratum];
235             cur = new ERuleset(curRelations, curRules.toArray(new DatalogRule[curRules.size()]), cur).compileStratified(context);
236         }
237         return cur;
238     }
239     
240     private Expression compileStratified(TypingContext context) {
241         Expression continuation = Expressions.tuple();
242         
243         // Create stacks
244         Variable[] stacks = new Variable[relations.length];
245         for(int i=0;i<relations.length;++i) {
246             LocalRelation relation = relations[i];
247             Type[] parameterTypes = relation.getParameterTypes();
248             stacks[i] = newVar("stack" + relation.getName(),
249                     Types.apply(Names.MList_T, Types.tuple(parameterTypes))
250                     );
251         }
252
253         // Simplify subexpressions and collect derivatives
254         THashMap<LocalRelation, Diffable> diffables = new THashMap<LocalRelation, Diffable>(relations.length);
255         for(int i=0;i<relations.length;++i) {
256             LocalRelation relation = relations[i];
257             Type[] parameterTypes = relation.getParameterTypes();
258             Variable[] parameters = new Variable[parameterTypes.length];
259             for(int j=0;j<parameterTypes.length;++j)
260                 parameters[j] = new Variable("p" + j, parameterTypes[j]);
261             diffables.put(relations[i], new Diffable(i, relation, parameters));
262         }
263         @SuppressWarnings("unchecked")
264         ArrayList<Expression>[] updateExpressions = (ArrayList<Expression>[])new ArrayList[relations.length];
265         for(int i=0;i<relations.length;++i)
266             updateExpressions[i] = new ArrayList<Expression>(2);
267         ArrayList<Expression> seedExpressions = new ArrayList<Expression>(); 
268         for(DatalogRule rule : rules) {
269             int id = diffables.get(rule.headRelation).id;
270             Expression appendExp = apply(context.getCompilationContext(), Types.PROC, Names.MList_add, Types.tuple(rule.headRelation.getParameterTypes()),
271                     var(stacks[id]),
272                     tuple(rule.headParameters)
273                     );
274             Diff[] diffs;
275             try {
276                 diffs = rule.body.derivate(diffables);
277             } catch(DerivateException e) {
278                 context.getErrorLog().log(e.location, "Recursion must not contain negations or aggragates.");
279                 return new EError();
280             }
281             for(Diff diff : diffs)
282                 updateExpressions[diff.id].add(((EWhen)new EWhen(rule.location, diff.query, appendExp, rule.variables).copy(context)).compile(context));
283             if(diffs.length == 0)
284                 seedExpressions.add(((EWhen)new EWhen(rule.location, rule.body, appendExp, rule.variables).copy(context)).compile(context));
285             else {
286                 Query query = rule.body.removeRelations((Set<SCLRelation>)(Set)diffables.keySet());
287                 if(query != Query.EMPTY_QUERY)
288                     seedExpressions.add(((EWhen)new EWhen(location, query, appendExp, rule.variables).copy(context)).compile(context));
289             }
290         }
291         
292         // Iterative solving of relations
293
294         Variable[] loops = new Variable[relations.length];
295         for(int i=0;i<loops.length;++i)
296             loops[i] = newVar("loop" + relations[i].getName(), Types.functionE(Types.INTEGER, Types.PROC, Types.UNIT));
297         continuation = seq(apply(Types.PROC, var(loops[0]), integer(relations.length-1)), continuation);
298         
299         Expression[] loopDefs = new Expression[relations.length];
300         for(int i=0;i<relations.length;++i) {
301             LocalRelation relation = relations[i];
302             Type[] parameterTypes = relation.getParameterTypes();
303             Variable[] parameters = diffables.get(relation).parameters;
304             
305             Variable counter = newVar("counter", Types.INTEGER);
306             
307             Type rowType = Types.tuple(parameterTypes);
308             Variable row = newVar("row", rowType);
309             
310             Expression handleRow = tuple();
311             for(Expression updateExpression : updateExpressions[i])
312                 handleRow = seq(updateExpression, handleRow);
313             handleRow = if_(
314                     apply(context.getCompilationContext(), Types.PROC, Names.MSet_add, rowType,
315                             var(relation.table), var(row)),
316                     handleRow,
317                     tuple()
318                     );
319             handleRow = seq(handleRow, apply(Types.PROC, var(loops[i]), integer(relations.length-1)));
320             Expression failure =
321                     if_(isZeroInteger(var(counter)),
322                         tuple(),
323                         apply(Types.PROC, var(loops[(i+1)%relations.length]), addInteger(var(counter), integer(-1)))
324                        );
325             Expression body = matchWithDefault(
326                     apply(context.getCompilationContext(), Types.PROC, Names.MList_removeLast, rowType, var(stacks[i])),
327                     Just(as(row, tuple(vars(parameters)))), handleRow,
328                     failure);
329             
330             loopDefs[i] = lambda(Types.PROC, counter, body); 
331         }
332         continuation = letRec(loops, loopDefs, continuation);
333         
334         // Seed relations
335         for(Expression seedExpression : seedExpressions)
336             continuation = seq(seedExpression, continuation);
337         
338         // Create stacks
339         for(int i=0;i<stacks.length;++i)
340             continuation = let(stacks[i],
341                     apply(context.getCompilationContext(), Types.PROC, Names.MList_create, Types.tuple(relations[i].getParameterTypes()), tuple()),
342                     continuation);
343         
344         continuation = ForcedClosure.forceClosure(continuation, SCLCompilerConfiguration.EVERY_DATALOG_STRATUM_IN_SEPARATE_METHOD);
345         
346         // Create relations
347         for(LocalRelation relation : relations)
348             continuation = let(relation.table,
349                     apply(context.getCompilationContext(), Types.PROC, Names.MSet_create, Types.tuple(relation.getParameterTypes()), tuple()),
350                     continuation);
351         
352         return seq(continuation, in);
353     }
354
355     @Override
356     protected void updateType() throws MatchException {
357         setType(in.getType());
358     }
359     
360     @Override
361     public void setLocationDeep(long loc) {
362         if(location == Locations.NO_LOCATION) {
363             location = loc;
364             for(DatalogRule rule : rules)
365                 rule.setLocationDeep(loc);
366         }
367     }
368     
369     @Override
370     public void accept(ExpressionVisitor visitor) {
371         visitor.visit(this);
372     }
373
374     public DatalogRule[] getRules() {
375         return rules;
376     }
377     
378     public Expression getIn() {
379         return in;
380     }
381     
382     @Override
383     public Expression accept(ExpressionTransformer transformer) {
384         return transformer.transform(this);
385     }
386
387 }