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