]> gerrit.simantics Code Review - simantics/platform.git/blob
0beb90f83126543a305f48085c2c1c7cf397095c
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.elaboration.transformations;
2
3 import gnu.trove.map.hash.THashMap;
4 import gnu.trove.map.hash.TIntObjectHashMap;
5 import gnu.trove.map.hash.TObjectIntHashMap;
6 import gnu.trove.set.hash.THashSet;
7
8 import java.util.ArrayList;
9 import java.util.Arrays;
10 import java.util.List;
11
12 import org.simantics.scl.compiler.common.names.Name;
13 import org.simantics.scl.compiler.constants.Constant;
14 import org.simantics.scl.compiler.elaboration.contexts.EnvironmentalContext;
15 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
16 import org.simantics.scl.compiler.elaboration.expressions.EApply;
17 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
18 import org.simantics.scl.compiler.elaboration.expressions.EEnforce;
19 import org.simantics.scl.compiler.elaboration.expressions.ERuleset;
20 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
21 import org.simantics.scl.compiler.elaboration.expressions.EWhen;
22 import org.simantics.scl.compiler.elaboration.expressions.Expression;
23 import org.simantics.scl.compiler.elaboration.expressions.Expressions;
24 import org.simantics.scl.compiler.elaboration.expressions.Variable;
25 import org.simantics.scl.compiler.elaboration.expressions.VariableProcedure;
26 import org.simantics.scl.compiler.elaboration.expressions.block.GuardStatement;
27 import org.simantics.scl.compiler.elaboration.expressions.block.LetStatement;
28 import org.simantics.scl.compiler.elaboration.expressions.block.Statement;
29 import org.simantics.scl.compiler.elaboration.query.QAtom;
30 import org.simantics.scl.compiler.elaboration.query.QConjunction;
31 import org.simantics.scl.compiler.elaboration.query.QMapping;
32 import org.simantics.scl.compiler.elaboration.query.Query;
33 import org.simantics.scl.compiler.elaboration.relations.LocalRelation;
34 import org.simantics.scl.compiler.elaboration.rules.MappingRelation;
35 import org.simantics.scl.compiler.elaboration.rules.TransformationRule;
36 import org.simantics.scl.compiler.errors.ErrorLog;
37 import org.simantics.scl.compiler.errors.Locations;
38 import org.simantics.scl.compiler.internal.codegen.references.IVal;
39 import org.simantics.scl.compiler.internal.elaboration.utils.ForcedClosure;
40 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
41 import org.simantics.scl.compiler.top.SCLExpressionCompilationException;
42 import org.simantics.scl.compiler.types.TCon;
43 import org.simantics.scl.compiler.types.Type;
44 import org.simantics.scl.compiler.types.Types;
45
46 public class TransformationBuilder {
47     private static final TCon UMap = Types.con("Unification", "UMap");
48     private static final Name createUMap = Name.create("Unification", "createUMap");
49     
50     private static final TCon Unifiable = Types.con("Unification", "Unifiable");
51     private static final Name uVar = Name.create("Unification", "uVar");
52
53     private final ErrorLog errorLog;
54     private final TypingContext context;
55     private final UnifiableFactory unifiableFactory;
56     
57     // Auxiliary
58     static class Mapping {
59         LocalRelation relation;
60         Variable umap;
61     }
62     THashMap<MappingRelation, Mapping> mappings = new THashMap<MappingRelation, Mapping>();
63     THashMap<TransformationRule, LocalRelation> ruleSourceMatchRelations = new THashMap<TransformationRule, LocalRelation>();
64     
65     // Output
66     ArrayList<ERuleset.DatalogRule> sourceMatchingRules = new ArrayList<ERuleset.DatalogRule>();
67     ArrayList<Statement> mappingStatements = new ArrayList<Statement>();
68     TIntObjectHashMap<ArrayList<Statement>> enforcingStatements = new TIntObjectHashMap<ArrayList<Statement>>();
69     
70     public TransformationBuilder(ErrorLog errorLog, TypingContext context) {
71         this.errorLog = errorLog;
72         this.context = context;
73         this.unifiableFactory = new UnifiableFactory(context, mappingStatements);
74     }
75     
76     private Mapping getMapping(MappingRelation mappingRelation) {
77         Mapping mapping = mappings.get(mappingRelation);
78         if(mapping == null) {
79             mapping = new Mapping();
80             mapping.relation =  new LocalRelation(mappingRelation.name.name+"_src", new Type[] {
81                     mappingRelation.parameterTypes[0]
82             });
83             mapping.umap = new Variable("map_" + mappingRelation.name.name,
84                     Types.apply(UMap, mappingRelation.parameterTypes)
85                     );
86             mappings.put(mappingRelation, mapping);
87             mappingStatements.add(new LetStatement(new EVariable(mapping.umap),
88                     Expressions.apply(context, Types.PROC, createUMap,
89                             mappingRelation.parameterTypes[0],
90                             mappingRelation.parameterTypes[1],
91                             Expressions.punit())));
92         }
93         return mapping;
94     }
95     
96     private static class PatternAnalyzer implements VariableProcedure {
97         THashSet<Variable> variableSet;
98         TObjectIntHashMap<Variable> mappedVariableUseCount;
99         boolean containsVariables;
100         
101         public PatternAnalyzer(THashSet<Variable> variableSet,
102                 TObjectIntHashMap<Variable> mappedVariableUseCount) {
103             this.variableSet = variableSet;
104             this.mappedVariableUseCount = mappedVariableUseCount;
105         }
106
107         @Override
108         public void execute(long location, Variable variable) {
109             if(!variableSet.contains(variable))
110                 return;
111             
112             mappedVariableUseCount.adjustOrPutValue(variable, 1, 1);
113             
114             containsVariables = true;
115         }
116     }
117     
118     private static Expression statementsToExpression(EnvironmentalContext context, List<Statement> statements, Expression in) {
119         for(int i=statements.size()-1;i>=0;--i)
120             in = statements.get(i).toExpression(context, false, in);
121         return in;
122     }
123     
124     private static Expression statementsToExpression(EnvironmentalContext context, List<Statement> statements) {
125         return statementsToExpression(context, statements, Expressions.tuple());
126     }
127     
128     public void handleSeed(Query query) {
129         if(query instanceof QMapping) {
130             QMapping mapping = (QMapping)query;
131             Mapping m = getMapping(mapping.mappingRelation);
132             sourceMatchingRules.add(new ERuleset.DatalogRule(
133                     query.location,
134                     m.relation,
135                     new Expression[] {mapping.parameters[0]},
136                     new QConjunction(),
137                     Variable.EMPTY_ARRAY
138                     ));
139             mappingStatements.add(new GuardStatement(unifiableFactory.putToUMapConstant(m.umap,
140                     mapping.parameters[0].copy(context),
141                     mapping.parameters[1].copy(context))));
142         }
143         else if(query instanceof QConjunction) {
144             QConjunction conjunction = (QConjunction)query;
145             for(Query childQuery : conjunction.queries)
146                 handleSeed(childQuery);
147         }
148         else {
149             errorLog.log(query.location, "Cannot use the query as a seed for the transformation.");
150         }
151     }
152
153     public void handleRule(TransformationRule rule) {
154         // Collect and classify queries
155         final DecomposedRule decomposed = DecomposedRule.decompose(context, rule, true);
156         for(QMapping mapping : decomposed.sourceMappings) {
157             decomposed.sourceQueries.add(new QAtom(
158                     getMapping(mapping.mappingRelation).relation,
159                     Type.EMPTY_ARRAY,
160                     mapping.parameters[0].copy(context)
161                     ));
162         }
163         
164         // Source variables
165         /* 
166          * Collect the existential variables occurring in the rule so that
167          *     sourceVariables = the variables that can be solved with source patterns 
168          *                       including the sources of the mapping relations in when section
169          *     variableSet = all other existential variables that are solved in mapping/enforcing phases 
170          */
171         final THashSet<Variable> variableSet = new THashSet<Variable>(rule.variables.length);
172         for(Variable variable : rule.variables)
173             variableSet.add(variable);
174
175         Variable[] sourceVariables;
176         {
177             final ArrayList<Variable> sourceVariableList = new ArrayList<Variable>(rule.variables.length);
178             VariableProcedure analyze = new VariableProcedure() {
179                 @Override
180                 public void execute(long location, Variable variable) {
181                     if(variableSet.remove(variable))
182                         sourceVariableList.add(variable);
183                 }
184             };
185             for(Query query : decomposed.sourceQueries)
186                 query.forVariables(analyze);
187             VariableProcedure check = new VariableProcedure() {
188                 @Override
189                 public void execute(long location, Variable variable) {
190                     if(variableSet.contains(variable))
191                         errorLog.log(location, "Cannot resolve the variable " + variable.getName() + " using the source patterns.");
192                 }
193             };
194             for(QMapping mapping : decomposed.targetMappings)
195                 mapping.parameters[0].forVariables(check);
196             sourceVariables = sourceVariableList.toArray(new Variable[sourceVariableList.size()]);
197         }
198         
199         // Matching rules
200         generateMatchingRules(decomposed, sourceVariables);
201         
202         // Mapped variables
203         ArrayList<QMapping> mappings = new ArrayList<QMapping>(
204                 decomposed.sourceMappings.size() + decomposed.targetMappings.size());
205         mappings.addAll(decomposed.sourceMappings);
206         mappings.addAll(decomposed.targetMappings);
207
208         // Analyze mappings
209         int capacity = Math.max(10, mappings.size());
210         ArrayList<QMapping> closedMappings = new ArrayList<QMapping>(capacity);
211         ArrayList<QMapping> openMappings = new ArrayList<QMapping>(capacity);
212         ArrayList<QMapping> semiopenMappings = new ArrayList<QMapping>(capacity);
213
214         TObjectIntHashMap<Variable> mappedVariableUseCount = new TObjectIntHashMap<Variable>();
215         for(QMapping mapping : mappings) {
216             Expression expression = mapping.parameters[1];
217             if(expression instanceof EVariable) {
218                 Variable variable = ((EVariable)expression).getVariable();
219                 if(variableSet.contains(variable)) {
220                     // Single open variable
221                     mappedVariableUseCount.adjustOrPutValue(variable, 1, 1);
222                     openMappings.add(mapping);
223                 }
224                 else {
225                     // Single variable whose value is bound
226                     closedMappings.add(mapping);
227                 }
228             }
229             else {
230                 PatternAnalyzer analyzer = new PatternAnalyzer(variableSet, mappedVariableUseCount); 
231                 expression.forVariables(analyzer);
232
233                 if(analyzer.containsVariables)
234                     semiopenMappings.add(mapping);
235                 else
236                     closedMappings.add(mapping);
237             }
238         }
239
240         // Generate mapping actions
241         ArrayList<Statement> phase2Actions = new ArrayList<Statement>();
242         ArrayList<Statement> phase3Actions = new ArrayList<Statement>();
243         for(QMapping mapping : closedMappings)
244             phase2Actions.add(new GuardStatement(unifiableFactory.putToUMapConstant(
245                     getMapping(mapping.mappingRelation).umap,
246                     mapping.parameters[0].copy(context),
247                     mapping.parameters[1].copy(context))));
248
249         // Choose and initialize shared unification variables
250         THashMap<Variable, Variable> uniVariableMap =
251                 new THashMap<Variable, Variable>();
252         for(Variable variable : mappedVariableUseCount.keySet()) {
253             int count = mappedVariableUseCount.get(variable);
254             if(count > 1) {
255                 Variable uniVariable = new Variable("uvar_" + variable.getName(),
256                         Types.apply(Unifiable, variable.getType()));
257                 phase2Actions.add(new LetStatement(new EVariable(uniVariable), 
258                         Expressions.apply(context, Types.PROC,
259                                 uVar,
260                                 variable.getType(),
261                                 Expressions.tuple())));
262                 uniVariableMap.put(variable, uniVariable);
263             }
264         }
265
266         // Select open mappings that use shared variables
267         THashSet<Variable> undeterminedVariables = new THashSet<Variable>(variableSet); 
268         for(QMapping mapping : openMappings) {
269             Variable variable = ((EVariable)mapping.parameters[1]).getVariable();
270             if(uniVariableMap.containsKey(variable))
271                 semiopenMappings.add(mapping);
272             else {
273                 Mapping m = getMapping(mapping.mappingRelation);
274                 Type resultType = mapping.mappingRelation.parameterTypes[1];
275                 phase3Actions.add(new LetStatement(new EVariable(variable),
276                         unifiableFactory.getFromUMap(Expressions.var(m.umap), mapping.parameters[0].copy(context), resultType)));
277                 undeterminedVariables.remove(variable);
278             }
279         }
280
281         for(QMapping mapping : semiopenMappings) {
282             Mapping m = getMapping(mapping.mappingRelation);
283             Type valueType = mapping.mappingRelation.parameterTypes[1];
284             phase2Actions.add(new GuardStatement(unifiableFactory.putToUMapUnifiable(
285                     variableSet, uniVariableMap,
286                     Expressions.var(m.umap), mapping.parameters[0].copy(context), mapping.parameters[1].copy(context))));
287             
288             Expression pattern = toPattern(undeterminedVariables, mapping.parameters[1]);
289             if(pattern != null) {
290                 Expression value = unifiableFactory.getFromUMap(Expressions.var(m.umap), mapping.parameters[0].copy(context), valueType);
291                 phase3Actions.add(new LetStatement(pattern, value));
292             }
293         }
294         
295         // Mapping statement
296         if(!phase2Actions.isEmpty())
297             mappingStatements.add(new GuardStatement(new EWhen(
298                     rule.location,
299                     new QAtom(decomposed.ruleMatchingRelation,
300                             Type.EMPTY_ARRAY,
301                             Expressions.vars(sourceVariables)),
302                             statementsToExpression(context, phase2Actions),
303                             sourceVariables).compile(context)));
304
305         // Enforcing statement
306         if(!decomposed.targetQueries.isEmpty()) {
307             for(Variable variable : rule.variables)
308                 if(variableSet.contains(variable) && !mappedVariableUseCount.containsKey(variable))
309                     phase3Actions.add(new LetStatement(new EVariable(variable), unifiableFactory.generateDefaultValue(variable.getType())));
310             
311             TIntObjectHashMap<ArrayList<Query>> phases = new TIntObjectHashMap<ArrayList<Query>>();
312             for(Query targetQuery : decomposed.targetQueries)
313                 targetQuery.splitToPhases(phases);
314             
315             for(int phase : phases.keys()) {
316                 ArrayList<Query> targetQuery = phases.get(phase);
317                 Expression enforcing = new EEnforce(new QConjunction(targetQuery.toArray(new Query[targetQuery.size()]))).compile(context);
318                 enforcing = statementsToExpression(context, phase3Actions, enforcing);
319                 enforcing = new EWhen(
320                         rule.location,
321                         new QAtom(decomposed.ruleMatchingRelation,
322                                 Type.EMPTY_ARRAY,
323                                 Expressions.vars(sourceVariables)),
324                                 enforcing,
325                                 sourceVariables).compile(context);
326                 ArrayList<Statement> list = enforcingStatements.get(phase);
327                 if(list == null) {
328                     list = new ArrayList<Statement>();
329                     enforcingStatements.put(phase, list);
330                 }
331                 list.add(new GuardStatement(ForcedClosure.forceClosure(enforcing.copy(context),
332                         SCLCompilerConfiguration.EVERY_RULE_ENFORCEMENT_IN_SEPARATE_METHOD)));
333             }
334         }
335     }
336     
337     public Expression compileRules() {
338         ArrayList<LocalRelation> localRelations = new ArrayList<LocalRelation>();
339         localRelations.addAll(ruleSourceMatchRelations.values());
340         for(Mapping mapping : mappings.values())
341             localRelations.add(mapping.relation);
342         
343         ArrayList<Statement> allEnforcingStatements;
344         if(enforcingStatements.size() == 1)
345             allEnforcingStatements = enforcingStatements.valueCollection().iterator().next();
346         else {
347             int[] phases = enforcingStatements.keys();
348             Arrays.sort(phases);
349             allEnforcingStatements = new ArrayList<Statement>();
350             for(int phase : phases)
351                 allEnforcingStatements.addAll(enforcingStatements.get(phase));
352         }
353         Expression expression = statementsToExpression(context, allEnforcingStatements);
354         expression = statementsToExpression(context, mappingStatements, expression);
355         
356         // Matching
357         Expression result = new ERuleset(
358                 localRelations.toArray(new LocalRelation[localRelations.size()]),
359                 sourceMatchingRules.toArray(new ERuleset.DatalogRule[sourceMatchingRules.size()]),
360                 expression
361                 ).compile(context);
362         return result;
363     }
364         
365     private Expression toPattern(
366             THashSet<Variable> undeterminedVariables,
367             Expression expression) {
368         if(expression instanceof EVariable) {
369             Variable variable = ((EVariable)expression).getVariable();
370             if(undeterminedVariables.remove(variable))
371                 return new EVariable(variable);
372             else
373                 return null;
374         }
375         if(expression instanceof EApply) {
376             EApply apply = (EApply)expression;
377             
378             if(!(apply.getFunction() instanceof EConstant))
379                 return null;
380             EConstant function = (EConstant)apply.getFunction();
381             
382             IVal val = function.getValue().getValue();
383             if(!(val instanceof Constant))
384                 return null;
385             Constant constant = (Constant)val;
386             
387             int constructorTag = constant.constructorTag();
388             if(constructorTag < 0)
389                 return null;
390             
391             int arity = constant.getArity();
392             Expression[] parameters = apply.getParameters(); 
393             if(arity != parameters.length)
394                 return null;
395             
396             Expression[] patterns = new Expression[arity];
397             boolean noUndeterminedVariables = true;
398             for(int i=0;i<arity;++i) {
399                 Expression pattern = toPattern(undeterminedVariables, parameters[i]); 
400                 patterns[i] = pattern;
401                 if(pattern != null)
402                     noUndeterminedVariables = false;
403             }
404             if(noUndeterminedVariables)
405                 return null;
406             
407             for(int i=0;i<arity;++i)
408                 if(patterns[i] == null)
409                     patterns[i] = Expressions.blank(parameters[i].getType());
410             return new EApply(Locations.NO_LOCATION, apply.getEffect(), apply.getFunction().copy(context), patterns);
411         } 
412         
413         return null;
414     }
415
416     private void generateMatchingRules(DecomposedRule decomposed, Variable[] sourceVariables) {
417         // @when/from -sections
418         decomposed.ruleMatchingRelation =
419                 new LocalRelation(decomposed.rule.name.name+"_match", Types.getTypes(sourceVariables));
420         ruleSourceMatchRelations.put(decomposed.rule, decomposed.ruleMatchingRelation);
421         sourceMatchingRules.add(new ERuleset.DatalogRule(decomposed.rule.location,
422                 decomposed.ruleMatchingRelation,
423                 Expressions.vars(sourceVariables), 
424                 new QConjunction(decomposed.sourceQueries.toArray(new Query[decomposed.sourceQueries.size()])),
425                 sourceVariables));
426         
427         // @where -section
428         for(QMapping mapping : decomposed.targetMappings)
429             sourceMatchingRules.add(new ERuleset.DatalogRule(decomposed.rule.location,
430                     getMapping(mapping.mappingRelation).relation,
431                     new Expression[] {mapping.parameters[0].copy(context)},
432                     new QAtom(decomposed.ruleMatchingRelation,
433                             Type.EMPTY_ARRAY,
434                             Expressions.vars(sourceVariables)),
435                             sourceVariables));
436     }
437 }