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 java.util.ArrayList;
   4 import java.util.Arrays;
   5 import java.util.List;
   6
   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;
  39
  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;
  44
  45 public class TransformationBuilder {
  46     private static final TCon UMap = Types.con("Unification", "UMap");
  47     private static final Name createUMap = Name.create("Unification", "createUMap");
  48
  49     private static final TCon Unifiable = Types.con("Unification", "Unifiable");
  50     private static final Name uVar = Name.create("Unification", "uVar");
  51
  52     private final ErrorLog errorLog;
  53     private final TypingContext context;
  54     private final UnifiableFactory unifiableFactory;
  55
  56     // Auxiliary
  57     static class Mapping {
  58         LocalRelation relation;
  59         Variable umap;
  60     }
  61     THashMap<MappingRelation, Mapping> mappings = new THashMap<MappingRelation, Mapping>();
  62     THashMap<TransformationRule, LocalRelation> ruleSourceMatchRelations = new THashMap<TransformationRule, LocalRelation>();
  63
  64     // Output
  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>>();
  68
  69     public TransformationBuilder(ErrorLog errorLog, TypingContext context) {
  70         this.errorLog = errorLog;
  71         this.context = context;
  72         this.unifiableFactory = new UnifiableFactory(context, mappingStatements);
  73     }
  74
  75     private Mapping getMapping(MappingRelation mappingRelation) {
  76         Mapping mapping = mappings.get(mappingRelation);
  77         if(mapping == null) {
  78             mapping = new Mapping();
  79             mapping.relation =  new LocalRelation(mappingRelation.name.name+"_src", new Type[] {
  80                     mappingRelation.parameterTypes[0]
  81             });
  82             mapping.umap = new Variable("map_" + mappingRelation.name.name,
  83                     Types.apply(UMap, mappingRelation.parameterTypes)
  84                     );
  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())));
  91         }
  92         return mapping;
  93     }
  94
  95     private static class PatternAnalyzer implements VariableProcedure {
  96         THashSet<Variable> variableSet;
  97         TObjectIntHashMap<Variable> mappedVariableUseCount;
  98         boolean containsVariables;
  99
 100         public PatternAnalyzer(THashSet<Variable> variableSet,
 101                 TObjectIntHashMap<Variable> mappedVariableUseCount) {
 102             this.variableSet = variableSet;
 103             this.mappedVariableUseCount = mappedVariableUseCount;
 104         }
 105
 106         @Override
 107         public void execute(long location, Variable variable) {
 108             if(!variableSet.contains(variable))
 109                 return;
 110
 111             mappedVariableUseCount.adjustOrPutValue(variable, 1, 1);
 112
 113             containsVariables = true;
 114         }
 115     }
 116
 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);
 120         return in;
 121     }
 122
 123     private static Expression statementsToExpression(EnvironmentalContext context, List<Statement> statements) {
 124         return statementsToExpression(context, statements, Expressions.tuple());
 125     }
 126
 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(
 132                     query.location,
 133                     m.relation,
 134                     new Expression[] {mapping.parameters[0]},
 135                     new QConjunction(),
 136                     Variable.EMPTY_ARRAY
 137                     ));
 138             mappingStatements.add(new GuardStatement(unifiableFactory.putToUMapConstant(m.umap,
 139                     mapping.parameters[0].copy(context),
 140                     mapping.parameters[1].copy(context))));
 141         }
 142         else if(query instanceof QConjunction) {
 143             QConjunction conjunction = (QConjunction)query;
 144             for(Query childQuery : conjunction.queries)
 145                 handleSeed(childQuery);
 146         }
 147         else {
 148             errorLog.log(query.location, "Cannot use the query as a seed for the transformation.");
 149         }
 150     }
 151
 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,
 158                     Type.EMPTY_ARRAY,
 159                     mapping.parameters[0].copy(context)
 160                     ));
 161         }
 162
 163         // Source variables
 164         /*
 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
 169          */
 170         final THashSet<Variable> variableSet = new THashSet<Variable>(rule.variables.length);
 171         for(Variable variable : rule.variables)
 172             variableSet.add(variable);
 173
 174         Variable[] sourceVariables;
 175         {
 176             final ArrayList<Variable> sourceVariableList = new ArrayList<Variable>(rule.variables.length);
 177             VariableProcedure analyze = new VariableProcedure() {
 178                 @Override
 179                 public void execute(long location, Variable variable) {
 180                     if(variableSet.remove(variable))
 181                         sourceVariableList.add(variable);
 182                 }
 183             };
 184             for(Query query : decomposed.sourceQueries)
 185                 query.forVariables(analyze);
 186             VariableProcedure check = new VariableProcedure() {
 187                 @Override
 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.");
 191                 }
 192             };
 193             for(QMapping mapping : decomposed.targetMappings)
 194                 mapping.parameters[0].forVariables(check);
 195             sourceVariables = sourceVariableList.toArray(new Variable[sourceVariableList.size()]);
 196         }
 197
 198         // Matching rules
 199         generateMatchingRules(decomposed, sourceVariables);
 200
 201         // Mapped variables
 202         ArrayList<QMapping> mappings = new ArrayList<QMapping>(
 203                 decomposed.sourceMappings.size() + decomposed.targetMappings.size());
 204         mappings.addAll(decomposed.sourceMappings);
 205         mappings.addAll(decomposed.targetMappings);
 206
 207         // Analyze mappings
 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);
 212
 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);
 222                 }
 223                 else {
 224                     // Single variable whose value is bound
 225                     closedMappings.add(mapping);
 226                 }
 227             }
 228             else {
 229                 PatternAnalyzer analyzer = new PatternAnalyzer(variableSet, mappedVariableUseCount);
 230                 expression.forVariables(analyzer);
 231
 232                 if(analyzer.containsVariables)
 233                     semiopenMappings.add(mapping);
 234                 else
 235                     closedMappings.add(mapping);
 236             }
 237         }
 238
 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))));
 247
 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);
 253             if(count > 1) {
 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,
 258                                 uVar,
 259                                 variable.getType(),
 260                                 Expressions.tuple())));
 261                 uniVariableMap.put(variable, uniVariable);
 262             }
 263         }
 264
 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);
 271             else {
 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);
 277             }
 278         }
 279
 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))));
 286
 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));
 291             }
 292         }
 293
 294         // Mapping statement
 295         if(!phase2Actions.isEmpty())
 296             mappingStatements.add(new GuardStatement(new EWhen(
 297                     rule.location,
 298                     new QAtom(decomposed.ruleMatchingRelation,
 299                             Type.EMPTY_ARRAY,
 300                             Expressions.vars(sourceVariables)),
 301                             statementsToExpression(context, phase2Actions),
 302                             sourceVariables).compile(context)));
 303
 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())));
 309
 310             TIntObjectHashMap<ArrayList<Query>> phases = new TIntObjectHashMap<ArrayList<Query>>();
 311             for(Query targetQuery : decomposed.targetQueries)
 312                 targetQuery.splitToPhases(phases);
 313
 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(
 319                         rule.location,
 320                         new QAtom(decomposed.ruleMatchingRelation,
 321                                 Type.EMPTY_ARRAY,
 322                                 Expressions.vars(sourceVariables)),
 323                                 enforcing,
 324                                 sourceVariables).compile(context);
 325                 ArrayList<Statement> list = enforcingStatements.get(phase);
 326                 if(list == null) {
 327                     list = new ArrayList<Statement>();
 328                     enforcingStatements.put(phase, list);
 329                 }
 330                 list.add(new GuardStatement(ForcedClosure.forceClosure(enforcing.copy(context),
 331                         SCLCompilerConfiguration.EVERY_RULE_ENFORCEMENT_IN_SEPARATE_METHOD)));
 332             }
 333         }
 334     }
 335
 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);
 341
 342         ArrayList<Statement> allEnforcingStatements;
 343         if(enforcingStatements.size() == 1)
 344             allEnforcingStatements = enforcingStatements.valueCollection().iterator().next();
 345         else {
 346             int[] phases = enforcingStatements.keys();
 347             Arrays.sort(phases);
 348             allEnforcingStatements = new ArrayList<Statement>();
 349             for(int phase : phases)
 350                 allEnforcingStatements.addAll(enforcingStatements.get(phase));
 351         }
 352         Expression expression = statementsToExpression(context, allEnforcingStatements);
 353         expression = statementsToExpression(context, mappingStatements, expression);
 354
 355         // Matching
 356         Expression result = new ERuleset(
 357                 localRelations.toArray(new LocalRelation[localRelations.size()]),
 358                 sourceMatchingRules.toArray(new ERuleset.DatalogRule[sourceMatchingRules.size()]),
 359                 expression
 360                 ).compile(context);
 361         return result;
 362     }
 363
 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);
 371             else
 372                 return null;
 373         }
 374         if(expression instanceof EApply) {
 375             EApply apply = (EApply)expression;
 376
 377             if(!(apply.getFunction() instanceof EConstant))
 378                 return null;
 379             EConstant function = (EConstant)apply.getFunction();
 380
 381             IVal val = function.getValue().getValue();
 382             if(!(val instanceof Constant))
 383                 return null;
 384             Constant constant = (Constant)val;
 385
 386             int constructorTag = constant.constructorTag();
 387             if(constructorTag < 0)
 388                 return null;
 389
 390             int arity = constant.getArity();
 391             Expression[] parameters = apply.getParameters();
 392             if(arity != parameters.length)
 393                 return null;
 394
 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;
 400                 if(pattern != null)
 401                     noUndeterminedVariables = false;
 402             }
 403             if(noUndeterminedVariables)
 404                 return null;
 405
 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);
 410         }
 411
 412         return null;
 413     }
 414
 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()])),
 424                 sourceVariables));
 425
 426         // @where -section
 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,
 432                             Type.EMPTY_ARRAY,
 433                             Expressions.vars(sourceVariables)),
 434                             sourceVariables));
 435     }
 436 }