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