bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/compilation/TypeCheckingOld.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
  15 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
  16 import org.simantics.scl.compiler.elaboration.expressions.EPlaceholder;
  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.rules.MappingRelation;
  22 import org.simantics.scl.compiler.elaboration.rules.TransformationRule;
  23 import org.simantics.scl.compiler.environment.Environment;
  24 import org.simantics.scl.compiler.errors.ErrorLog;
  25 import org.simantics.scl.compiler.errors.Locations;
  26 import org.simantics.scl.compiler.internal.elaboration.constraints.Constraint;
  27 import org.simantics.scl.compiler.internal.elaboration.constraints.ConstraintEnvironment;
  28 import org.simantics.scl.compiler.internal.elaboration.constraints.ConstraintSolver;
  29 import org.simantics.scl.compiler.internal.elaboration.constraints.ExpressionAugmentation;
  30 import org.simantics.scl.compiler.internal.elaboration.constraints.ReducedConstraints;
  31 import org.simantics.scl.compiler.internal.elaboration.utils.StronglyConnectedComponents;
  32 import org.simantics.scl.compiler.module.ConcreteModule;
  33 import org.simantics.scl.compiler.types.TPred;
  34 import org.simantics.scl.compiler.types.TVar;
  35 import org.simantics.scl.compiler.types.Type;
  36 import org.simantics.scl.compiler.types.Types;
  37 import org.simantics.scl.compiler.types.kinds.Kinds;
  38 import org.simantics.scl.compiler.types.util.Polarity;
  39
  40 public class TypeCheckingOld {
  41     public static final boolean PRINT_VALUES = false;
  42
  43     ErrorLog errorLog;
  44     Environment environment;
  45     ConcreteModule module;
  46
  47     ConstraintEnvironment ce;
  48     ArrayList<SCLValue[]> valuesWithoutTypeAnnotation = new ArrayList<SCLValue[]>();
  49     ArrayList<SCLValue> valuesWithTypeAnnotation = new ArrayList<SCLValue>();
  50
  51     public TypeCheckingOld(ErrorLog errorLog, Environment environment,
  52             ConcreteModule module) {
  53         this.errorLog = errorLog;
  54         this.environment = environment;
  55         this.module = module;
  56     }
  57
  58     public void typeCheck() {
  59         ce = new ConstraintEnvironment(environment);
  60         groupValueDefinitionsByDependency();
  61         typeCheckValuesWithoutTypeAnnotations();
  62         typeCheckValuesWithTypeAnnotations();
  63         typeCheckRules();
  64     }
  65
  66     private void groupValueDefinitionsByDependency() {
  67         // Collect all untyped names
  68         final ArrayList<SCLValue> values = new ArrayList<SCLValue>();
  69         for(SCLValue value : module.getValues()) {
  70             if(value.getExpression() != null) {
  71                 if(value.getType() == null)
  72                     values.add(value);
  73                 else
  74                     valuesWithTypeAnnotation.add(value);
  75             }
  76         }
  77
  78         // Create inverse
  79         final TObjectIntHashMap<Object> allRefs =
  80                 new TObjectIntHashMap<Object>(values.size()*2, 0.5f, -1);
  81         for(int i=0;i<values.size();++i)
  82             allRefs.put(values.get(i), i);
  83
  84         // Create groups
  85         new StronglyConnectedComponents(values.size()) {
  86
  87             TIntHashSet set = new TIntHashSet();
  88
  89             @Override
  90             protected void reportComponent(int[] component) {
  91                 SCLValue[] valueComponent = new SCLValue[component.length];
  92                 for(int i=0;i<component.length;++i)
  93                     valueComponent[i] = values.get(component[i]);
  94                 valuesWithoutTypeAnnotation.add(valueComponent);
  95             }
  96
  97             @Override
  98             protected int[] findDependencies(int u) {
  99                 Expression expression = values.get(u).getExpression();
 100                 expression.collectRefs(allRefs, set);
 101
 102                 int[] result = set.toArray();
 103                 set.clear();
 104
 105                 return result;
 106             }
 107
 108         }.findComponents();
 109     }
 110
 111     private void typeCheckValuesWithoutTypeAnnotations() {
 112         for(SCLValue[] group : valuesWithoutTypeAnnotation) {
 113             if(PRINT_VALUES) {
 114                 System.out.println("---------------------------------------------");
 115                 System.out.print("---");
 116                 for(SCLValue value : group)
 117                     System.out.print(" " + value.getName());
 118                 System.out.println();
 119             }
 120
 121             for(int i=0;i<group.length;++i)
 122                 group[i].setType(Types.metaVar(Kinds.STAR));
 123
 124             TypingContext context = new TypingContext(errorLog, environment);
 125             context.recursiveValues = new THashSet<SCLValue>();
 126             for(SCLValue value : group)
 127                 context.recursiveValues.add(value);
 128
 129             @SuppressWarnings("unchecked")
 130             ArrayList<EVariable>[] constraintDemands = new ArrayList[group.length];
 131
 132             @SuppressWarnings("unchecked")
 133             ArrayList<EPlaceholder>[] recursiveReferences = new ArrayList[group.length];
 134             for(int i=0;i<group.length;++i) {
 135                 context.recursiveReferences = new ArrayList<EPlaceholder>();
 136
 137                 SCLValue value = group[i];
 138                 Expression expression = value.getExpression();
 139                 expression = expression.checkType(context, value.getType());
 140                 value.setExpression(expression);
 141
 142                 ArrayList<EVariable> constraintDemand = context.getConstraintDemand();
 143                 if(!constraintDemand.isEmpty()) {
 144                     constraintDemands[i] = constraintDemand;
 145                     context.resetConstraintDemand();
 146                 }
 147
 148                 recursiveReferences[i] = context.recursiveReferences;
 149             }
 150
 151             for(Type type : Types.getTypes(group))
 152                 type.addPolarity(Polarity.POSITIVE);
 153             context.solveSubsumptions(group[0].getExpression().getLocation());
 154             ArrayList<Constraint> allUnsolvedConstraints = new ArrayList<Constraint>();
 155
 156             @SuppressWarnings("unchecked")
 157             ArrayList<Variable>[] freeEvidence = new ArrayList[group.length];
 158             for(int i=0;i<group.length;++i) {
 159                 if(constraintDemands[i] != null) {
 160                     SCLValue value = group[i];
 161                     Expression expression = value.getExpression();
 162
 163                     ReducedConstraints red = ConstraintSolver.solve(
 164                             ce, new ArrayList<TPred>(0), constraintDemands[i],
 165                             true /*!Types.isFunction(expression.getType())*/);
 166
 167                     expression = ExpressionAugmentation.augmentSolved(
 168                             red.solvedConstraints,
 169                             expression);
 170                     value.setExpression(expression);
 171                     value.setType(expression.getType());
 172
 173                     for(Constraint c : red.unsolvedConstraints)
 174                         if(c.constraint.isGround()) {
 175                             errorLog.log(c.getDemandLocation(), "There is no instance for <"+c.constraint+">.");
 176                         }
 177
 178                     ArrayList<Variable> fe = new ArrayList<Variable>(red.unsolvedConstraints.size());
 179                     for(Constraint c : red.unsolvedConstraints) {
 180                         allUnsolvedConstraints.add(c);
 181                         fe.add(c.evidence);
 182                     }
 183                     freeEvidence[i] = fe;
 184                 }
 185                 else {
 186                     group[i].setExpression(group[i].getExpression().decomposeMatching());
 187                     freeEvidence[i] = new ArrayList<Variable>(0);
 188                 }
 189             }
 190
 191             THashSet<TVar> varSet = new THashSet<TVar>();
 192             for(int i=0;i<group.length;++i) {
 193                 SCLValue value = group[i];
 194                 Type type = value.getType();
 195                 type = type.convertMetaVarsToVars();
 196                 value.setType(type);
 197                 varSet.addAll(Types.freeVars(type));
 198             }
 199
 200             TVar[] vars = varSet.toArray(new TVar[varSet.size()]);
 201
 202             // Collect all constraints needed in the group
 203             THashSet<TPred> constraintSet = new THashSet<TPred>();
 204             for(int i=0;i<group.length;++i) {
 205                 for(Variable evidence : freeEvidence[i]) {
 206                     constraintSet.add((TPred)evidence.getType());
 207                 }
 208             }
 209             TPred[] constraints = constraintSet.toArray(new TPred[constraintSet.size()]);
 210             for(TPred constraint : constraints)
 211                 if(constraint.containsMetaVars()) {
 212                     for(Constraint c : allUnsolvedConstraints) {
 213                         if(Types.equals(c.constraint, constraint)) {
 214                             errorLog.log(c.getDemandLocation(),
 215                                     "Constrain " + constraint +
 216                                     " contains free variables not mentioned in the type of the value.");
 217                             break;
 218                         }
 219                     }
 220                 }
 221
 222
 223             // TODO copy to TypeChecking2 from this onwards
 224             for(int i=0;i<group.length;++i) {
 225                 // Create evidence array of every value in the group that has the variables
 226                 // in the same array as in the shared array
 227                 ArrayList<Variable> fe = freeEvidence[i];
 228                 THashMap<TPred, Variable> indexedEvidence = new THashMap<TPred, Variable>(fe.size());
 229                 for(Variable v : fe)
 230                     indexedEvidence.put((TPred)v.getType(), v);
 231                 fe.clear();
 232                 for(TPred c : constraints) {
 233                     Variable var = indexedEvidence.get(c);
 234                     if(var == null) {
 235                         // These are variables that are not directly needed in
 236                         // this definition but in the definitions that are
 237                         // recursively called
 238                         var = new Variable("evX");
 239                         var.setType(c);
 240                         fe.add(var);
 241                     }
 242                     fe.add(var);
 243                 }
 244
 245                 // Add evidence parameters to the functions
 246                 SCLValue value = group[i];
 247                 value.setExpression(lambda(Types.NO_EFFECTS, fe, value.getExpression())
 248                         .closure(vars));
 249                 value.setType(Types.forAll(vars,
 250                         Types.constrained(constraints, value.getType())));
 251
 252                 // Add evidence parameters to recursive calls
 253                 for(EPlaceholder ref : recursiveReferences[i]) {
 254                     ref.expression = loc(ref.expression.location, apply(
 255                             Types.NO_EFFECTS,
 256                             applyTypes(ref.expression, vars),
 257                             vars(fe)));
 258                 }
 259             }
 260         }
 261     }
 262
 263     private void typeCheckValuesWithTypeAnnotations() {
 264         ArrayList<TPred> givenConstraints = new ArrayList<TPred>();
 265         for(SCLValue value : valuesWithTypeAnnotation) {
 266             Type type = value.getType();
 267             if(type != null) {
 268                 if(PRINT_VALUES) {
 269                     System.out.println("---------------------------------------------");
 270                     System.out.println("--- " + value.getName() + " :: " + type);
 271                 }
 272                 Expression expression = value.getExpression();
 273                 ArrayList<TVar> vars = new ArrayList<TVar>();
 274                 type = Types.removeForAll(type, vars);
 275                 type = Types.removePred(type, givenConstraints);
 276
 277                 /*System.out.println("---------------------------------------------");
 278                 TypeUnparsingContext tuc = new TypeUnparsingContext();
 279                 System.out.println("--- " + value.getName() + " :: " + type.toString(tuc));
 280                 for(TPred t : givenConstraints)
 281                     System.out.println(">>> " + t.toString(tuc));
 282                 */
 283                 TypingContext context = new TypingContext(errorLog, environment);
 284                 //System.out.println(expression);
 285                 expression = expression.checkType(context, type);
 286                 //System.out.println(expression);
 287                 expression.getType().addPolarity(Polarity.POSITIVE);
 288                 context.solveSubsumptions(expression.getLocation());
 289                 ArrayList<EVariable> demands = context.getConstraintDemand();
 290                 if(!demands.isEmpty() || !givenConstraints.isEmpty()) {
 291                     ReducedConstraints red =
 292                             ConstraintSolver.solve(ce, givenConstraints, demands, true);
 293                     givenConstraints.clear();
 294                     for(Constraint c :  red.unsolvedConstraints) {
 295                         errorLog.log(c.getDemandLocation(),
 296                                 "Constraint <"+c.constraint+"> is not given and cannot be derived.");
 297                     }
 298                     if(errorLog.isEmpty()) { // To prevent exceptions
 299                         expression = ExpressionAugmentation.augmentSolved(
 300                                 red.solvedConstraints,
 301                                 expression);
 302                         expression = ExpressionAugmentation.augmentUnsolved(
 303                                 red.givenConstraints,
 304                                 expression);
 305                     }
 306                 }
 307                 else {
 308                     if(errorLog.isEmpty()) // To prevent exceptions
 309                         expression = expression.decomposeMatching();
 310                 }
 311                 expression = expression.closure(vars.toArray(new TVar[vars.size()]));
 312                 value.setExpression(expression);
 313             }
 314         }
 315     }
 316
 317     public void typeCheckRules() {
 318         TypingContext context = new TypingContext(errorLog, environment);
 319         for(TransformationRule rule : module.getRules()) {
 320             context.pushEffectUpperBound(rule.location, Types.metaVar(Kinds.EFFECT));
 321             rule.checkType(context);
 322             rule.setEffect(Types.canonical(context.popEffectUpperBound()));
 323         }
 324         context.solveSubsumptions(Locations.NO_LOCATION);
 325
 326         ArrayList<EVariable> demands = context.getConstraintDemand();
 327         if(!demands.isEmpty()) {
 328             ReducedConstraints red =
 329                     ConstraintSolver.solve(ce, new ArrayList<TPred>(), demands, true);
 330             for(Constraint c :  red.unsolvedConstraints) {
 331                 errorLog.log(c.getDemandLocation(),
 332                         "Constraint <"+c.constraint+"> is not given and cannot be derived.");
 333             }
 334         }
 335
 336         for(MappingRelation mappingRelation : module.getMappingRelations())
 337             for(Type parameterType : mappingRelation.parameterTypes)
 338                 if(!parameterType.isGround()) {
 339                     errorLog.log(mappingRelation.location, "Parameter types of the mapping relation are not completely determined.");
 340                     break;
 341                 }
 342
 343         /*for(Rule rule : module.getRules()) {
 344             System.out.println(rule.name);
 345             for(Variable variable : rule.variables)
 346                 System.out.println("    " + variable.getName() + " :: " + variable.getType());
 347         }*/
 348     }
 349 }