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