bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/transformations/TransformationBuilder.java

   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 }