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