1 package org.simantics.scl.compiler.internal.elaboration.transformations;
3 import java.util.ArrayList;
4 import java.util.Arrays;
7 import org.simantics.scl.compiler.common.names.Name;
8 import org.simantics.scl.compiler.constants.Constant;
9 import org.simantics.scl.compiler.elaboration.contexts.EnvironmentalContext;
10 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
11 import org.simantics.scl.compiler.elaboration.expressions.EApply;
12 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
13 import org.simantics.scl.compiler.elaboration.expressions.EEnforce;
14 import org.simantics.scl.compiler.elaboration.expressions.ERuleset;
15 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
16 import org.simantics.scl.compiler.elaboration.expressions.EWhen;
17 import org.simantics.scl.compiler.elaboration.expressions.Expression;
18 import org.simantics.scl.compiler.elaboration.expressions.Expressions;
19 import org.simantics.scl.compiler.elaboration.expressions.Variable;
20 import org.simantics.scl.compiler.elaboration.expressions.VariableProcedure;
21 import org.simantics.scl.compiler.elaboration.expressions.block.GuardStatement;
22 import org.simantics.scl.compiler.elaboration.expressions.block.LetStatement;
23 import org.simantics.scl.compiler.elaboration.expressions.block.Statement;
24 import org.simantics.scl.compiler.elaboration.query.QAtom;
25 import org.simantics.scl.compiler.elaboration.query.QConjunction;
26 import org.simantics.scl.compiler.elaboration.query.QMapping;
27 import org.simantics.scl.compiler.elaboration.query.Query;
28 import org.simantics.scl.compiler.elaboration.relations.LocalRelation;
29 import org.simantics.scl.compiler.elaboration.rules.MappingRelation;
30 import org.simantics.scl.compiler.elaboration.rules.TransformationRule;
31 import org.simantics.scl.compiler.errors.ErrorLog;
32 import org.simantics.scl.compiler.errors.Locations;
33 import org.simantics.scl.compiler.internal.codegen.references.IVal;
34 import org.simantics.scl.compiler.internal.elaboration.utils.ForcedClosure;
35 import org.simantics.scl.compiler.top.SCLCompilerConfiguration;
36 import org.simantics.scl.compiler.types.TCon;
37 import org.simantics.scl.compiler.types.Type;
38 import org.simantics.scl.compiler.types.Types;
40 import gnu.trove.map.hash.THashMap;
41 import gnu.trove.map.hash.TIntObjectHashMap;
42 import gnu.trove.map.hash.TObjectIntHashMap;
43 import gnu.trove.set.hash.THashSet;
45 public class TransformationBuilder {
46 private static final TCon UMap = Types.con("Unification", "UMap");
47 private static final Name createUMap = Name.create("Unification", "createUMap");
49 private static final TCon Unifiable = Types.con("Unification", "Unifiable");
50 private static final Name uVar = Name.create("Unification", "uVar");
52 private final ErrorLog errorLog;
53 private final TypingContext context;
54 private final UnifiableFactory unifiableFactory;
57 static class Mapping {
58 LocalRelation relation;
61 THashMap<MappingRelation, Mapping> mappings = new THashMap<MappingRelation, Mapping>();
62 THashMap<TransformationRule, LocalRelation> ruleSourceMatchRelations = new THashMap<TransformationRule, LocalRelation>();
65 ArrayList<ERuleset.DatalogRule> sourceMatchingRules = new ArrayList<ERuleset.DatalogRule>();
66 ArrayList<Statement> mappingStatements = new ArrayList<Statement>();
67 TIntObjectHashMap<ArrayList<Statement>> enforcingStatements = new TIntObjectHashMap<ArrayList<Statement>>();
69 public TransformationBuilder(ErrorLog errorLog, TypingContext context) {
70 this.errorLog = errorLog;
71 this.context = context;
72 this.unifiableFactory = new UnifiableFactory(context, mappingStatements);
75 private Mapping getMapping(MappingRelation mappingRelation) {
76 Mapping mapping = mappings.get(mappingRelation);
78 mapping = new Mapping();
79 mapping.relation = new LocalRelation(mappingRelation.name.name+"_src", new Type[] {
80 mappingRelation.parameterTypes[0]
82 mapping.umap = new Variable("map_" + mappingRelation.name.name,
83 Types.apply(UMap, mappingRelation.parameterTypes)
85 mappings.put(mappingRelation, mapping);
86 mappingStatements.add(new LetStatement(new EVariable(mapping.umap),
87 Expressions.apply(context, Types.PROC, createUMap,
88 mappingRelation.parameterTypes[0],
89 mappingRelation.parameterTypes[1],
90 Expressions.punit())));
95 private static class PatternAnalyzer implements VariableProcedure {
96 THashSet<Variable> variableSet;
97 TObjectIntHashMap<Variable> mappedVariableUseCount;
98 boolean containsVariables;
100 public PatternAnalyzer(THashSet<Variable> variableSet,
101 TObjectIntHashMap<Variable> mappedVariableUseCount) {
102 this.variableSet = variableSet;
103 this.mappedVariableUseCount = mappedVariableUseCount;
107 public void execute(long location, Variable variable) {
108 if(!variableSet.contains(variable))
111 mappedVariableUseCount.adjustOrPutValue(variable, 1, 1);
113 containsVariables = true;
117 private static Expression statementsToExpression(EnvironmentalContext context, List<Statement> statements, Expression in) {
118 for(int i=statements.size()-1;i>=0;--i)
119 in = statements.get(i).toExpression(context, false, in);
123 private static Expression statementsToExpression(EnvironmentalContext context, List<Statement> statements) {
124 return statementsToExpression(context, statements, Expressions.tuple());
127 public void handleSeed(Query query) {
128 if(query instanceof QMapping) {
129 QMapping mapping = (QMapping)query;
130 Mapping m = getMapping(mapping.mappingRelation);
131 sourceMatchingRules.add(new ERuleset.DatalogRule(
134 new Expression[] {mapping.parameters[0]},
138 mappingStatements.add(new GuardStatement(unifiableFactory.putToUMapConstant(m.umap,
139 mapping.parameters[0].copy(context),
140 mapping.parameters[1].copy(context))));
142 else if(query instanceof QConjunction) {
143 QConjunction conjunction = (QConjunction)query;
144 for(Query childQuery : conjunction.queries)
145 handleSeed(childQuery);
148 errorLog.log(query.location, "Cannot use the query as a seed for the transformation.");
152 public void handleRule(TransformationRule rule) {
153 // Collect and classify queries
154 final DecomposedRule decomposed = DecomposedRule.decompose(context, rule, true);
155 for(QMapping mapping : decomposed.sourceMappings) {
156 decomposed.sourceQueries.add(new QAtom(
157 getMapping(mapping.mappingRelation).relation,
159 mapping.parameters[0].copy(context)
165 * Collect the existential variables occurring in the rule so that
166 * sourceVariables = the variables that can be solved with source patterns
167 * including the sources of the mapping relations in when section
168 * variableSet = all other existential variables that are solved in mapping/enforcing phases
170 final THashSet<Variable> variableSet = new THashSet<Variable>(rule.variables.length);
171 for(Variable variable : rule.variables)
172 variableSet.add(variable);
174 Variable[] sourceVariables;
176 final ArrayList<Variable> sourceVariableList = new ArrayList<Variable>(rule.variables.length);
177 VariableProcedure analyze = new VariableProcedure() {
179 public void execute(long location, Variable variable) {
180 if(variableSet.remove(variable))
181 sourceVariableList.add(variable);
184 for(Query query : decomposed.sourceQueries)
185 query.forVariables(analyze);
186 VariableProcedure check = new VariableProcedure() {
188 public void execute(long location, Variable variable) {
189 if(variableSet.contains(variable))
190 errorLog.log(location, "Cannot resolve the variable " + variable.getName() + " using the source patterns.");
193 for(QMapping mapping : decomposed.targetMappings)
194 mapping.parameters[0].forVariables(check);
195 sourceVariables = sourceVariableList.toArray(new Variable[sourceVariableList.size()]);
199 generateMatchingRules(decomposed, sourceVariables);
202 ArrayList<QMapping> mappings = new ArrayList<QMapping>(
203 decomposed.sourceMappings.size() + decomposed.targetMappings.size());
204 mappings.addAll(decomposed.sourceMappings);
205 mappings.addAll(decomposed.targetMappings);
208 int capacity = Math.max(10, mappings.size());
209 ArrayList<QMapping> closedMappings = new ArrayList<QMapping>(capacity);
210 ArrayList<QMapping> openMappings = new ArrayList<QMapping>(capacity);
211 ArrayList<QMapping> semiopenMappings = new ArrayList<QMapping>(capacity);
213 TObjectIntHashMap<Variable> mappedVariableUseCount = new TObjectIntHashMap<Variable>();
214 for(QMapping mapping : mappings) {
215 Expression expression = mapping.parameters[1];
216 if(expression instanceof EVariable) {
217 Variable variable = ((EVariable)expression).getVariable();
218 if(variableSet.contains(variable)) {
219 // Single open variable
220 mappedVariableUseCount.adjustOrPutValue(variable, 1, 1);
221 openMappings.add(mapping);
224 // Single variable whose value is bound
225 closedMappings.add(mapping);
229 PatternAnalyzer analyzer = new PatternAnalyzer(variableSet, mappedVariableUseCount);
230 expression.forVariables(analyzer);
232 if(analyzer.containsVariables)
233 semiopenMappings.add(mapping);
235 closedMappings.add(mapping);
239 // Generate mapping actions
240 ArrayList<Statement> phase2Actions = new ArrayList<Statement>();
241 ArrayList<Statement> phase3Actions = new ArrayList<Statement>();
242 for(QMapping mapping : closedMappings)
243 phase2Actions.add(new GuardStatement(unifiableFactory.putToUMapConstant(
244 getMapping(mapping.mappingRelation).umap,
245 mapping.parameters[0].copy(context),
246 mapping.parameters[1].copy(context))));
248 // Choose and initialize shared unification variables
249 THashMap<Variable, Variable> uniVariableMap =
250 new THashMap<Variable, Variable>();
251 for(Variable variable : mappedVariableUseCount.keySet()) {
252 int count = mappedVariableUseCount.get(variable);
254 Variable uniVariable = new Variable("uvar_" + variable.getName(),
255 Types.apply(Unifiable, variable.getType()));
256 phase2Actions.add(new LetStatement(new EVariable(uniVariable),
257 Expressions.apply(context, Types.PROC,
260 Expressions.tuple())));
261 uniVariableMap.put(variable, uniVariable);
265 // Select open mappings that use shared variables
266 THashSet<Variable> undeterminedVariables = new THashSet<Variable>(variableSet);
267 for(QMapping mapping : openMappings) {
268 Variable variable = ((EVariable)mapping.parameters[1]).getVariable();
269 if(uniVariableMap.containsKey(variable))
270 semiopenMappings.add(mapping);
272 Mapping m = getMapping(mapping.mappingRelation);
273 Type resultType = mapping.mappingRelation.parameterTypes[1];
274 phase3Actions.add(new LetStatement(new EVariable(variable),
275 unifiableFactory.getFromUMap(Expressions.var(m.umap), mapping.parameters[0].copy(context), resultType)));
276 undeterminedVariables.remove(variable);
280 for(QMapping mapping : semiopenMappings) {
281 Mapping m = getMapping(mapping.mappingRelation);
282 Type valueType = mapping.mappingRelation.parameterTypes[1];
283 phase2Actions.add(new GuardStatement(unifiableFactory.putToUMapUnifiable(
284 variableSet, uniVariableMap,
285 Expressions.var(m.umap), mapping.parameters[0].copy(context), mapping.parameters[1].copy(context))));
287 Expression pattern = toPattern(undeterminedVariables, mapping.parameters[1]);
288 if(pattern != null) {
289 Expression value = unifiableFactory.getFromUMap(Expressions.var(m.umap), mapping.parameters[0].copy(context), valueType);
290 phase3Actions.add(new LetStatement(pattern, value));
295 if(!phase2Actions.isEmpty())
296 mappingStatements.add(new GuardStatement(new EWhen(
298 new QAtom(decomposed.ruleMatchingRelation,
300 Expressions.vars(sourceVariables)),
301 statementsToExpression(context, phase2Actions),
302 sourceVariables).compile(context)));
304 // Enforcing statement
305 if(!decomposed.targetQueries.isEmpty()) {
306 for(Variable variable : rule.variables)
307 if(variableSet.contains(variable) && !mappedVariableUseCount.containsKey(variable))
308 phase3Actions.add(new LetStatement(new EVariable(variable), unifiableFactory.generateDefaultValue(variable.getType())));
310 TIntObjectHashMap<ArrayList<Query>> phases = new TIntObjectHashMap<ArrayList<Query>>();
311 for(Query targetQuery : decomposed.targetQueries)
312 targetQuery.splitToPhases(phases);
314 for(int phase : phases.keys()) {
315 ArrayList<Query> targetQuery = phases.get(phase);
316 Expression enforcing = new EEnforce(new QConjunction(targetQuery.toArray(new Query[targetQuery.size()]))).compile(context);
317 enforcing = statementsToExpression(context, phase3Actions, enforcing);
318 enforcing = new EWhen(
320 new QAtom(decomposed.ruleMatchingRelation,
322 Expressions.vars(sourceVariables)),
324 sourceVariables).compile(context);
325 ArrayList<Statement> list = enforcingStatements.get(phase);
327 list = new ArrayList<Statement>();
328 enforcingStatements.put(phase, list);
330 list.add(new GuardStatement(ForcedClosure.forceClosure(enforcing.copy(context),
331 SCLCompilerConfiguration.EVERY_RULE_ENFORCEMENT_IN_SEPARATE_METHOD)));
336 public Expression compileRules() {
337 ArrayList<LocalRelation> localRelations = new ArrayList<LocalRelation>();
338 localRelations.addAll(ruleSourceMatchRelations.values());
339 for(Mapping mapping : mappings.values())
340 localRelations.add(mapping.relation);
342 ArrayList<Statement> allEnforcingStatements;
343 if(enforcingStatements.size() == 1)
344 allEnforcingStatements = enforcingStatements.valueCollection().iterator().next();
346 int[] phases = enforcingStatements.keys();
348 allEnforcingStatements = new ArrayList<Statement>();
349 for(int phase : phases)
350 allEnforcingStatements.addAll(enforcingStatements.get(phase));
352 Expression expression = statementsToExpression(context, allEnforcingStatements);
353 expression = statementsToExpression(context, mappingStatements, expression);
356 Expression result = new ERuleset(
357 localRelations.toArray(new LocalRelation[localRelations.size()]),
358 sourceMatchingRules.toArray(new ERuleset.DatalogRule[sourceMatchingRules.size()]),
364 private Expression toPattern(
365 THashSet<Variable> undeterminedVariables,
366 Expression expression) {
367 if(expression instanceof EVariable) {
368 Variable variable = ((EVariable)expression).getVariable();
369 if(undeterminedVariables.remove(variable))
370 return new EVariable(variable);
374 if(expression instanceof EApply) {
375 EApply apply = (EApply)expression;
377 if(!(apply.getFunction() instanceof EConstant))
379 EConstant function = (EConstant)apply.getFunction();
381 IVal val = function.getValue().getValue();
382 if(!(val instanceof Constant))
384 Constant constant = (Constant)val;
386 int constructorTag = constant.constructorTag();
387 if(constructorTag < 0)
390 int arity = constant.getArity();
391 Expression[] parameters = apply.getParameters();
392 if(arity != parameters.length)
395 Expression[] patterns = new Expression[arity];
396 boolean noUndeterminedVariables = true;
397 for(int i=0;i<arity;++i) {
398 Expression pattern = toPattern(undeterminedVariables, parameters[i]);
399 patterns[i] = pattern;
401 noUndeterminedVariables = false;
403 if(noUndeterminedVariables)
406 for(int i=0;i<arity;++i)
407 if(patterns[i] == null)
408 patterns[i] = Expressions.blank(parameters[i].getType());
409 return new EApply(Locations.NO_LOCATION, apply.getEffect(), apply.getFunction().copy(context), patterns);
415 private void generateMatchingRules(DecomposedRule decomposed, Variable[] sourceVariables) {
416 // @when/from -sections
417 decomposed.ruleMatchingRelation =
418 new LocalRelation(decomposed.rule.name.name+"_match", Types.getTypes(sourceVariables));
419 ruleSourceMatchRelations.put(decomposed.rule, decomposed.ruleMatchingRelation);
420 sourceMatchingRules.add(new ERuleset.DatalogRule(decomposed.rule.location,
421 decomposed.ruleMatchingRelation,
422 Expressions.vars(sourceVariables),
423 new QConjunction(decomposed.sourceQueries.toArray(new Query[decomposed.sourceQueries.size()])),
427 for(QMapping mapping : decomposed.targetMappings)
428 sourceMatchingRules.add(new ERuleset.DatalogRule(decomposed.rule.location,
429 getMapping(mapping.mappingRelation).relation,
430 new Expression[] {mapping.parameters[0].copy(context)},
431 new QAtom(decomposed.ruleMatchingRelation,
433 Expressions.vars(sourceVariables)),