bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/compilation/TypeChecking.java

   1 package org.simantics.scl.compiler.compilation;
   2
   3 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.apply;
   4 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.applyTypes;
   5 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.lambda;
   6 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.loc;
   7 import static org.simantics.scl.compiler.elaboration.expressions.Expressions.vars;
   8
   9 import java.util.ArrayList;
  10 import java.util.Collection;
  11 import java.util.Collections;
  12
  13 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
  14 import org.simantics.scl.compiler.elaboration.expressions.EAmbiguous;
  15 import org.simantics.scl.compiler.elaboration.expressions.EPlaceholder;
  16 import org.simantics.scl.compiler.elaboration.expressions.ETransformation;
  17 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
  18 import org.simantics.scl.compiler.elaboration.expressions.Expression;
  19 import org.simantics.scl.compiler.elaboration.expressions.Variable;
  20 import org.simantics.scl.compiler.elaboration.modules.SCLValue;
  21 import org.simantics.scl.compiler.elaboration.query.Query;
  22 import org.simantics.scl.compiler.elaboration.relations.ConcreteRelation;
  23 import org.simantics.scl.compiler.elaboration.relations.ConcreteRelation.QuerySection;
  24 import org.simantics.scl.compiler.elaboration.relations.SCLRelation;
  25 import org.simantics.scl.compiler.elaboration.rules.MappingRelation;
  26 import org.simantics.scl.compiler.elaboration.rules.TransformationRule;
  27 import org.simantics.scl.compiler.environment.Environment;
  28 import org.simantics.scl.compiler.internal.elaboration.constraints.Constraint;
  29 import org.simantics.scl.compiler.internal.elaboration.constraints.ConstraintEnvironment;
  30 import org.simantics.scl.compiler.internal.elaboration.constraints.ConstraintSolver;
  31 import org.simantics.scl.compiler.internal.elaboration.constraints.ExpressionAugmentation;
  32 import org.simantics.scl.compiler.internal.elaboration.constraints.ReducedConstraints;
  33 import org.simantics.scl.compiler.module.ConcreteModule;
  34 import org.simantics.scl.compiler.types.TPred;
  35 import org.simantics.scl.compiler.types.TVar;
  36 import org.simantics.scl.compiler.types.Type;
  37 import org.simantics.scl.compiler.types.Types;
  38 import org.simantics.scl.compiler.types.kinds.Kinds;
  39 import org.simantics.scl.compiler.types.util.Polarity;
  40
  41 import gnu.trove.map.hash.THashMap;
  42 import gnu.trove.map.hash.TObjectIntHashMap;
  43 import gnu.trove.set.hash.THashSet;
  44 import gnu.trove.set.hash.TIntHashSet;
  45
  46 public class TypeChecking {
  47     final CompilationContext compilationContext;
  48     final Environment environment;
  49     final ConcreteModule module;
  50
  51     ConstraintEnvironment ce;
  52     TypeCheckingScheduler scheduler;
  53
  54     public TypeChecking(CompilationContext compilationContext, ConcreteModule module) {
  55         this.compilationContext = compilationContext;
  56         this.environment = compilationContext.environment;
  57         this.module = module;
  58     }
  59
  60     private void typeCheckValues() {
  61         for(final SCLValue value : module.getValues()) {
  62             if(value.getExpression() != null) {
  63                 if(value.getType() == null)
  64                     scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
  65                         ArrayList<EPlaceholder> recursiveReferences;
  66                         ArrayList<EVariable> constraintDemand;
  67                         ArrayList<Variable> freeEvidence;
  68                         ArrayList<Constraint> unsolvedConstraints;
  69
  70                         @Override
  71                         public long getLocation() {
  72                             return value.getExpression().getLocation();
  73                         }
  74
  75                         @Override
  76                         public Collection<Object> getDefinedObjects() {
  77                             return Collections.<Object>singleton(value);
  78                         }
  79
  80                         @Override
  81                         public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
  82                             value.getExpression().collectRefs(allRefs, refs);
  83                         }
  84
  85                         @Override
  86                         public void initializeTypeChecking(TypingContext context) {
  87                             value.setType(Types.metaVar(Kinds.STAR));
  88                             context.recursiveValues.add(value);
  89                         }
  90
  91                         @Override
  92                         public void checkType(TypingContext context) {
  93                             context.recursiveReferences =
  94                                     this.recursiveReferences = new ArrayList<EPlaceholder>();
  95
  96                             Expression expression = value.getExpression();
  97                             context.pushEffectUpperBound(expression.location, Types.PROC);
  98                             expression = expression.checkType(context, value.getType());
  99                             context.popEffectUpperBound();
 100                             for(EAmbiguous overloaded : context.overloadedExpressions)
 101                                 overloaded.assertResolved(compilationContext.errorLog);
 102                             value.setExpression(expression);
 103
 104                             ArrayList<EVariable> constraintDemand = context.getConstraintDemand();
 105                             if(!constraintDemand.isEmpty()) {
 106                                 this.constraintDemand = constraintDemand;
 107                                 context.resetConstraintDemand();
 108                             }
 109
 110                             expression.getType().addPolarity(Polarity.POSITIVE);
 111                         }
 112
 113                         @Override
 114                         public void solveConstraints() {
 115                             if(constraintDemand != null) {
 116                                 Expression expression = value.getExpression();
 117
 118                                 ReducedConstraints red = ConstraintSolver.solve(
 119                                         ce, new ArrayList<TPred>(0), constraintDemand,
 120                                         true);
 121
 122                                 expression = ExpressionAugmentation.augmentSolved(
 123                                         red.solvedConstraints,
 124                                         expression);
 125                                 value.setExpression(expression);
 126                                 value.setType(expression.getType());
 127
 128                                 for(Constraint c : red.unsolvedConstraints)
 129                                     if(c.constraint.isGround())
 130                                         compilationContext.errorLog.log(c.getDemandLocation(), "There is no instance for <"+c.constraint+">.");
 131
 132                                 ArrayList<Variable> fe = new ArrayList<Variable>(red.unsolvedConstraints.size());
 133                                 for(Constraint c : red.unsolvedConstraints)
 134                                     fe.add(c.evidence);
 135                                 unsolvedConstraints = red.unsolvedConstraints;
 136                                 freeEvidence = fe;
 137                             }
 138                             else {
 139                                 value.setExpression(value.getExpression().decomposeMatching());
 140                                 freeEvidence = new ArrayList<Variable>(0);
 141                             }
 142                         }
 143
 144                         @Override
 145                         public void collectFreeTypeVariables(
 146                                 THashSet<TVar> varSet) {
 147                             Type type = value.getType();
 148                             type = type.convertMetaVarsToVars();
 149                             value.setType(type);
 150                             varSet.addAll(Types.freeVars(type));
 151                         }
 152
 153                         @Override
 154                         public ArrayList<Variable> getFreeEvidence() {
 155                             return freeEvidence;
 156                         }
 157
 158                         @Override
 159                         public ArrayList<Constraint> getUnsolvedConstraints() {
 160                             return unsolvedConstraints;
 161                         }
 162
 163                         @Override
 164                         public void injectEvidence(TVar[] vars, TPred[] constraints) {
 165                             // Create evidence array of every value in the group that has the variables
 166                             // in the same array as in the shared array
 167                             THashMap<TPred, Variable> indexedEvidence = new THashMap<TPred, Variable>(freeEvidence.size());
 168                             for(Variable v : freeEvidence)
 169                                 indexedEvidence.put((TPred)v.getType(), v);
 170                             freeEvidence.clear();
 171                             for(TPred c : constraints) {
 172                                 Variable var = indexedEvidence.get(c);
 173                                 if(var == null) {
 174                                     // These are variables that are not directly needed in
 175                                     // this definition but in the definitions that are
 176                                     // recursively called
 177                                     var = new Variable("evX");
 178                                     var.setType(c);
 179                                     freeEvidence.add(var);
 180                                 }
 181                                 freeEvidence.add(var);
 182                             }
 183
 184                             // Add evidence parameters to the functions
 185                             value.setExpression(lambda(Types.NO_EFFECTS, freeEvidence, value.getExpression())
 186                                     .closure(vars));
 187                             value.setType(Types.forAll(vars,
 188                                     Types.constrained(constraints, value.getType())));
 189
 190                             // Add evidence parameters to recursive calls
 191                             for(EPlaceholder ref : recursiveReferences) {
 192                                 ref.expression = loc(ref.expression.location, apply(
 193                                         Types.NO_EFFECTS,
 194                                         applyTypes(ref.expression, vars),
 195                                         vars(freeEvidence)));
 196                             }
 197                         }
 198                     });
 199                 else
 200                     scheduler.addPostTypeCheckingRunnable(new Runnable() {
 201                         @Override
 202                         public void run() {
 203                             Type type = value.getType();
 204
 205                             Expression expression = value.getExpression();
 206
 207                             try {
 208                                 ArrayList<TVar> vars = new ArrayList<TVar>();
 209                                 type = Types.removeForAll(type, vars);
 210                                 ArrayList<TPred> givenConstraints = new ArrayList<TPred>();
 211                                 type = Types.removePred(type, givenConstraints);
 212
 213                                 TypingContext context = new TypingContext(compilationContext);
 214                                 context.pushEffectUpperBound(expression.location, Types.PROC);
 215                                 expression = expression.checkType(context, type);
 216                                 context.popEffectUpperBound();
 217                                 for(EAmbiguous overloaded : context.overloadedExpressions)
 218                                     overloaded.assertResolved(compilationContext.errorLog);
 219                                 expression.getType().addPolarity(Polarity.POSITIVE);
 220                                 context.solveSubsumptions(expression.getLocation());
 221                                 ArrayList<EVariable> demands = context.getConstraintDemand();
 222                                 if(!demands.isEmpty() || !givenConstraints.isEmpty()) {
 223                                     ReducedConstraints red =
 224                                             ConstraintSolver.solve(ce, givenConstraints, demands, true);
 225                                     givenConstraints.clear();
 226                                     for(Constraint c :  red.unsolvedConstraints) {
 227                                         compilationContext.errorLog.log(c.getDemandLocation(),
 228                                                 "Constraint <"+c.constraint+"> is not given and cannot be derived.");
 229                                     }
 230                                     if(compilationContext.errorLog.isEmpty()) { // To prevent exceptions
 231                                         expression = ExpressionAugmentation.augmentSolved(
 232                                                 red.solvedConstraints,
 233                                                 expression);
 234                                         expression = ExpressionAugmentation.augmentUnsolved(
 235                                                 red.givenConstraints,
 236                                                 expression);
 237                                     }
 238                                 }
 239                                 else {
 240                                     if(compilationContext.errorLog.isEmpty()) // To prevent exceptions
 241                                         expression = expression.decomposeMatching();
 242                                 }
 243                                 expression = expression.closure(vars.toArray(new TVar[vars.size()]));
 244                                 value.setExpression(expression);
 245                             } catch(Exception e) {
 246                                 compilationContext.errorLog.log(expression.location, e);
 247                             }
 248                         }
 249                     });
 250             }
 251         }
 252     }
 253
 254     private void typeCheckRelations() {
 255         for(SCLRelation relation_ : module.getRelations()) {
 256             if(!(relation_ instanceof ConcreteRelation))
 257                 continue;
 258             final ConcreteRelation relation = (ConcreteRelation)relation_;
 259             scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
 260
 261                 @Override
 262                 public void initializeTypeChecking(TypingContext context) {
 263                     for(Variable parameter : relation.parameters) {
 264                         Type type = Types.metaVar(Kinds.STAR);
 265                         type.addPolarity(Polarity.BIPOLAR);
 266                         parameter.setType(type);
 267                     }
 268                 }
 269
 270                 @Override
 271                 public void solveConstraints() {
 272                 }
 273
 274                 @Override
 275                 public void injectEvidence(TVar[] vars, TPred[] constraints) {
 276                     relation.typeVariables = vars;
 277                 }
 278
 279                 @Override
 280                 public ArrayList<Constraint> getUnsolvedConstraints() {
 281                     return new ArrayList<Constraint>(0); // TODO
 282                 }
 283
 284                 @Override
 285                 public long getLocation() {
 286                     return relation.location;
 287                 }
 288
 289                 @Override
 290                 public ArrayList<Variable> getFreeEvidence() {
 291                     return new ArrayList<Variable>(0); // TODO
 292                 }
 293
 294                 @Override
 295                 public Collection<Object> getDefinedObjects() {
 296                     return Collections.<Object>singleton(relation);
 297                 }
 298
 299                 @Override
 300                 public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
 301                     for(QuerySection section : relation.getSections())
 302                         section.query.collectRefs(allRefs, refs);
 303                 }
 304
 305                 @Override
 306                 public void collectFreeTypeVariables(THashSet<TVar> varSet) {
 307                     for(Variable parameter : relation.parameters) {
 308                         Type parameterType = parameter.getType().convertMetaVarsToVars();
 309                         varSet.addAll(Types.freeVars(parameterType));
 310                     }
 311                 }
 312
 313                 @Override
 314                 public void checkType(TypingContext context) {
 315                     for(QuerySection section : relation.getSections()) {
 316                         section.effect = Types.metaVar(Kinds.EFFECT);
 317                         context.pushEffectUpperBound(relation.location, section.effect);
 318                         for(Variable variable : section.existentials)
 319                             variable.setType(Types.metaVar(Kinds.STAR));
 320                         section.query.checkType(context);
 321                         context.popEffectUpperBound();
 322                     }
 323
 324                     if(relation.enforceSection != null) {
 325                         relation.writingEffect = Types.metaVar(Kinds.EFFECT);
 326                         context.pushEffectUpperBound(relation.location, relation.writingEffect);
 327                         relation.enforceSection.checkType(context);
 328                         context.popEffectUpperBound();
 329                     }
 330                 }
 331             });
 332         }
 333     }
 334
 335     public void typeCheck() {
 336         ce = new ConstraintEnvironment(environment);
 337         scheduler = new TypeCheckingScheduler(compilationContext);
 338
 339         typeCheckValues();
 340         typeCheckRelations();
 341         typeCheckRules();
 342
 343         scheduler.schedule();
 344     }
 345
 346     private void typeCheckRules() {
 347         scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
 348             @Override
 349             public void solveConstraints() {
 350                 // TODO Auto-generated method stub
 351             }
 352
 353             @Override
 354             public void injectEvidence(TVar[] vars, TPred[] constraints) {
 355                 // TODO Auto-generated method stub
 356
 357             }
 358
 359             @Override
 360             public void initializeTypeChecking(TypingContext context) {
 361                 // TODO Auto-generated method stub
 362
 363             }
 364
 365             @Override
 366             public ArrayList<Constraint> getUnsolvedConstraints() {
 367                 return new ArrayList<Constraint>(0);
 368                 /*
 369                 ArrayList<EVariable> demands = context.getConstraintDemand();
 370                 if(!demands.isEmpty()) {
 371                     ReducedConstraints red =
 372                             ConstraintSolver.solve(ce, new ArrayList<TPred>(), demands, true);
 373                     for(Constraint c :  red.unsolvedConstraints) {
 374                         errorLog.log(c.getDemandLocation(),
 375                                 "Constraint <"+c.constraint+"> is not given and cannot be derived.");
 376                     }
 377                 }*/
 378             }
 379
 380             @Override
 381             public long getLocation() {
 382                 // TODO Auto-generated method stub
 383                 return 0;
 384             }
 385
 386             @Override
 387             public ArrayList<Variable> getFreeEvidence() {
 388                 return new ArrayList<Variable>(0);
 389             }
 390
 391             @Override
 392             public Collection<Object> getDefinedObjects() {
 393                 return Collections.singleton(ETransformation.TRANSFORMATION_RULES_TYPECHECKED);
 394             }
 395
 396             @Override
 397             public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
 398                 for(TransformationRule rule : module.getRules())
 399                     for(Query[] queries : rule.sections.values())
 400                         for(Query query : queries)
 401                             query.collectRefs(allRefs, refs);
 402             }
 403
 404             @Override
 405             public void collectFreeTypeVariables(THashSet<TVar> varSet) {
 406             }
 407
 408             @Override
 409             public void checkType(TypingContext context) {
 410                 for(TransformationRule rule : module.getRules()) {
 411                     context.pushEffectUpperBound(rule.location, Types.metaVar(Kinds.EFFECT));
 412                     rule.checkType(context);
 413                     rule.setEffect(Types.canonical(context.popEffectUpperBound()));
 414                 }
 415             }
 416         });
 417
 418         if(!module.getMappingRelations().isEmpty())
 419             scheduler.addPostTypeCheckingRunnable(new Runnable() {
 420                 @Override
 421                 public void run() {
 422                     for(MappingRelation mappingRelation : module.getMappingRelations())
 423                         for(Type parameterType : mappingRelation.parameterTypes)
 424                             if(!parameterType.isGround()) {
 425                                 compilationContext.errorLog.log(mappingRelation.location, "Parameter types of the mapping relation are not completely determined.");
 426                                 break;
 427                             }
 428                 }
 429             });
 430     }
 431 }