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