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                             int errorCountBeforeTypeChecking = compilationContext.errorLog.getErrorCount();
 208                             int functionArity = expression.getSyntacticFunctionArity();
 209
 210                             try {
 211                                 ArrayList<TVar> vars = new ArrayList<TVar>();
 212                                 type = Types.removeForAll(type, vars);
 213                                 ArrayList<TPred> givenConstraints = new ArrayList<TPred>();
 214                                 type = Types.removePred(type, givenConstraints);
 215
 216                                 TypingContext context = new TypingContext(compilationContext);
 217                                 context.pushEffectUpperBound(expression.location, Types.PROC);
 218                                 expression = expression.checkType(context, type);
 219                                 context.popEffectUpperBound();
 220                                 for(EAmbiguous overloaded : context.overloadedExpressions)
 221                                     overloaded.assertResolved(compilationContext.errorLog);
 222                                 expression.getType().addPolarity(Polarity.POSITIVE);
 223                                 context.solveSubsumptions(expression.getLocation());
 224
 225                                 if(compilationContext.errorLog.getErrorCount() != errorCountBeforeTypeChecking) {
 226                                     int typeArity = Types.getArity(type);
 227                                     if(typeArity != functionArity)
 228                                         compilationContext.errorLog.log(value.definitionLocation, "Possible problem: type declaration has " + typeArity + " parameter types, but function definition has " + functionArity + " parameters.");
 229                                 }
 230
 231                                 ArrayList<EVariable> demands = context.getConstraintDemand();
 232                                 if(!demands.isEmpty() || !givenConstraints.isEmpty()) {
 233                                     ReducedConstraints red =
 234                                             ConstraintSolver.solve(ce, givenConstraints, demands, true);
 235                                     givenConstraints.clear();
 236                                     for(Constraint c :  red.unsolvedConstraints) {
 237                                         compilationContext.errorLog.log(c.getDemandLocation(),
 238                                                 "Constraint <"+c.constraint+"> is not given and cannot be derived.");
 239                                     }
 240                                     if(compilationContext.errorLog.hasNoErrors()) { // To prevent exceptions
 241                                         expression = ExpressionAugmentation.augmentSolved(
 242                                                 red.solvedConstraints,
 243                                                 expression);
 244                                         expression = ExpressionAugmentation.augmentUnsolved(
 245                                                 red.givenConstraints,
 246                                                 expression);
 247                                     }
 248                                 }
 249                                 else {
 250                                     if(compilationContext.errorLog.hasNoErrors()) // To prevent exceptions
 251                                         expression = expression.decomposeMatching();
 252                                 }
 253                                 expression = expression.closure(vars.toArray(new TVar[vars.size()]));
 254                                 value.setExpression(expression);
 255                             } catch(Exception e) {
 256                                 compilationContext.errorLog.log(expression.location, e);
 257                             }
 258                         }
 259                     });
 260             }
 261         }
 262     }
 263
 264     private void typeCheckRelations() {
 265         for(SCLRelation relation_ : module.getRelations()) {
 266             if(!(relation_ instanceof ConcreteRelation))
 267                 continue;
 268             final ConcreteRelation relation = (ConcreteRelation)relation_;
 269             scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
 270
 271                 @Override
 272                 public void initializeTypeChecking(TypingContext context) {
 273                     for(Variable parameter : relation.parameters) {
 274                         Type type = Types.metaVar(Kinds.STAR);
 275                         type.addPolarity(Polarity.BIPOLAR);
 276                         parameter.setType(type);
 277                     }
 278                 }
 279
 280                 @Override
 281                 public void solveConstraints() {
 282                 }
 283
 284                 @Override
 285                 public void injectEvidence(TVar[] vars, TPred[] constraints) {
 286                     relation.typeVariables = vars;
 287                 }
 288
 289                 @Override
 290                 public ArrayList<Constraint> getUnsolvedConstraints() {
 291                     return new ArrayList<Constraint>(0); // TODO
 292                 }
 293
 294                 @Override
 295                 public long getLocation() {
 296                     return relation.location;
 297                 }
 298
 299                 @Override
 300                 public ArrayList<Variable> getFreeEvidence() {
 301                     return new ArrayList<Variable>(0); // TODO
 302                 }
 303
 304                 @Override
 305                 public Collection<Object> getDefinedObjects() {
 306                     return Collections.<Object>singleton(relation);
 307                 }
 308
 309                 @Override
 310                 public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
 311                     for(QuerySection section : relation.getSections())
 312                         section.query.collectRefs(allRefs, refs);
 313                 }
 314
 315                 @Override
 316                 public void collectFreeTypeVariables(THashSet<TVar> varSet) {
 317                     for(Variable parameter : relation.parameters) {
 318                         Type parameterType = parameter.getType().convertMetaVarsToVars();
 319                         varSet.addAll(Types.freeVars(parameterType));
 320                     }
 321                 }
 322
 323                 @Override
 324                 public void checkType(TypingContext context) {
 325                     for(QuerySection section : relation.getSections()) {
 326                         section.effect = Types.metaVar(Kinds.EFFECT);
 327                         context.pushEffectUpperBound(relation.location, section.effect);
 328                         for(Variable variable : section.existentials)
 329                             variable.setType(Types.metaVar(Kinds.STAR));
 330                         section.query.checkType(context);
 331                         context.popEffectUpperBound();
 332                     }
 333
 334                     if(relation.enforceSection != null) {
 335                         relation.writingEffect = Types.metaVar(Kinds.EFFECT);
 336                         context.pushEffectUpperBound(relation.location, relation.writingEffect);
 337                         relation.enforceSection.checkType(context);
 338                         context.popEffectUpperBound();
 339                     }
 340                 }
 341             });
 342         }
 343     }
 344
 345     public void typeCheck() {
 346         ce = new ConstraintEnvironment(environment);
 347         scheduler = new TypeCheckingScheduler(compilationContext);
 348
 349         typeCheckValues();
 350         typeCheckRelations();
 351         typeCheckRules();
 352
 353         scheduler.schedule();
 354     }
 355
 356     private void typeCheckRules() {
 357         scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
 358             @Override
 359             public void solveConstraints() {
 360                 // TODO Auto-generated method stub
 361             }
 362
 363             @Override
 364             public void injectEvidence(TVar[] vars, TPred[] constraints) {
 365                 // TODO Auto-generated method stub
 366
 367             }
 368
 369             @Override
 370             public void initializeTypeChecking(TypingContext context) {
 371                 // TODO Auto-generated method stub
 372
 373             }
 374
 375             @Override
 376             public ArrayList<Constraint> getUnsolvedConstraints() {
 377                 return new ArrayList<Constraint>(0);
 378                 /*
 379                 ArrayList<EVariable> demands = context.getConstraintDemand();
 380                 if(!demands.isEmpty()) {
 381                     ReducedConstraints red =
 382                             ConstraintSolver.solve(ce, new ArrayList<TPred>(), demands, true);
 383                     for(Constraint c :  red.unsolvedConstraints) {
 384                         errorLog.log(c.getDemandLocation(),
 385                                 "Constraint <"+c.constraint+"> is not given and cannot be derived.");
 386                     }
 387                 }*/
 388             }
 389
 390             @Override
 391             public long getLocation() {
 392                 // TODO Auto-generated method stub
 393                 return 0;
 394             }
 395
 396             @Override
 397             public ArrayList<Variable> getFreeEvidence() {
 398                 return new ArrayList<Variable>(0);
 399             }
 400
 401             @Override
 402             public Collection<Object> getDefinedObjects() {
 403                 return Collections.singleton(ETransformation.TRANSFORMATION_RULES_TYPECHECKED);
 404             }
 405
 406             @Override
 407             public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
 408                 for(TransformationRule rule : module.getRules())
 409                     for(Query[] queries : rule.sections.values())
 410                         for(Query query : queries)
 411                             query.collectRefs(allRefs, refs);
 412             }
 413
 414             @Override
 415             public void collectFreeTypeVariables(THashSet<TVar> varSet) {
 416             }
 417
 418             @Override
 419             public void checkType(TypingContext context) {
 420                 for(TransformationRule rule : module.getRules()) {
 421                     context.pushEffectUpperBound(rule.location, Types.metaVar(Kinds.EFFECT));
 422                     rule.checkType(context);
 423                     rule.setEffect(Types.canonical(context.popEffectUpperBound()));
 424                 }
 425             }
 426         });
 427
 428         if(!module.getMappingRelations().isEmpty())
 429             scheduler.addPostTypeCheckingRunnable(new Runnable() {
 430                 @Override
 431                 public void run() {
 432                     for(MappingRelation mappingRelation : module.getMappingRelations())
 433                         for(Type parameterType : mappingRelation.parameterTypes)
 434                             if(!parameterType.isGround()) {
 435                                 compilationContext.errorLog.log(mappingRelation.location, "Parameter types of the mapping relation are not completely determined.");
 436                                 break;
 437                             }
 438                 }
 439             });
 440     }
 441 }