1 package org.simantics.scl.compiler.compilation;
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;
9 import java.util.ArrayList;
10 import java.util.Collection;
11 import java.util.Collections;
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;
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;
46 public class TypeChecking {
47 final CompilationContext compilationContext;
48 final Environment environment;
49 final ConcreteModule module;
51 ConstraintEnvironment ce;
52 TypeCheckingScheduler scheduler;
54 public TypeChecking(CompilationContext compilationContext, ConcreteModule module) {
55 this.compilationContext = compilationContext;
56 this.environment = compilationContext.environment;
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;
71 public long getLocation() {
72 return value.getExpression().getLocation();
76 public Collection<Object> getDefinedObjects() {
77 return Collections.<Object>singleton(value);
81 public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
82 value.getExpression().collectRefs(allRefs, refs);
86 public void initializeTypeChecking(TypingContext context) {
87 value.setType(Types.metaVar(Kinds.STAR));
88 context.recursiveValues.add(value);
92 public void checkType(TypingContext context) {
93 context.recursiveReferences =
94 this.recursiveReferences = new ArrayList<EPlaceholder>();
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);
104 ArrayList<EVariable> constraintDemand = context.getConstraintDemand();
105 if(!constraintDemand.isEmpty()) {
106 this.constraintDemand = constraintDemand;
107 context.resetConstraintDemand();
110 expression.getType().addPolarity(Polarity.POSITIVE);
114 public void solveConstraints() {
115 if(constraintDemand != null) {
116 Expression expression = value.getExpression();
118 ReducedConstraints red = ConstraintSolver.solve(
119 ce, new ArrayList<TPred>(0), constraintDemand,
122 expression = ExpressionAugmentation.augmentSolved(
123 red.solvedConstraints,
125 value.setExpression(expression);
126 value.setType(expression.getType());
128 for(Constraint c : red.unsolvedConstraints)
129 if(c.constraint.isGround())
130 compilationContext.errorLog.log(c.getDemandLocation(), "There is no instance for <"+c.constraint+">.");
132 ArrayList<Variable> fe = new ArrayList<Variable>(red.unsolvedConstraints.size());
133 for(Constraint c : red.unsolvedConstraints)
135 unsolvedConstraints = red.unsolvedConstraints;
139 value.setExpression(value.getExpression().decomposeMatching());
140 freeEvidence = new ArrayList<Variable>(0);
145 public void collectFreeTypeVariables(
146 THashSet<TVar> varSet) {
147 Type type = value.getType();
148 type = type.convertMetaVarsToVars();
150 varSet.addAll(Types.freeVars(type));
154 public ArrayList<Variable> getFreeEvidence() {
159 public ArrayList<Constraint> getUnsolvedConstraints() {
160 return unsolvedConstraints;
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);
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");
179 freeEvidence.add(var);
181 freeEvidence.add(var);
184 // Add evidence parameters to the functions
185 value.setExpression(lambda(Types.NO_EFFECTS, freeEvidence, value.getExpression())
187 value.setType(Types.forAll(vars,
188 Types.constrained(constraints, value.getType())));
189 //System.out.println(value.getName() + " :: " + value.getType());
191 // Add evidence parameters to recursive calls
192 for(EPlaceholder ref : recursiveReferences) {
193 ref.expression = loc(ref.expression.location, apply(
195 applyTypes(ref.expression, vars),
196 vars(freeEvidence)));
201 scheduler.addPostTypeCheckingRunnable(new Runnable() {
204 Type type = value.getType();
206 Expression expression = value.getExpression();
208 int errorCountBeforeTypeChecking = compilationContext.errorLog.getErrorCount();
209 int functionArity = expression.getSyntacticFunctionArity();
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);
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());
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.");
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.");
242 if(compilationContext.errorLog.hasNoErrors()) { // To prevent exceptions
243 expression = ExpressionAugmentation.augmentSolved(
244 red.solvedConstraints,
246 expression = ExpressionAugmentation.augmentUnsolved(
247 red.givenConstraints,
252 if(compilationContext.errorLog.hasNoErrors()) // To prevent exceptions
253 expression = expression.decomposeMatching();
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);
266 private void typeCheckRelations() {
267 for(SCLRelation relation_ : module.getRelations()) {
268 if(!(relation_ instanceof ConcreteRelation))
270 final ConcreteRelation relation = (ConcreteRelation)relation_;
271 scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
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);
283 public void solveConstraints() {
287 public void injectEvidence(TVar[] vars, TPred[] constraints) {
288 relation.typeVariables = vars;
292 public ArrayList<Constraint> getUnsolvedConstraints() {
293 return new ArrayList<Constraint>(0); // TODO
297 public long getLocation() {
298 return relation.location;
302 public ArrayList<Variable> getFreeEvidence() {
303 return new ArrayList<Variable>(0); // TODO
307 public Collection<Object> getDefinedObjects() {
308 return Collections.<Object>singleton(relation);
312 public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
313 for(QuerySection section : relation.getSections())
314 section.query.collectRefs(allRefs, refs);
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));
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();
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();
347 public void typeCheck() {
348 ce = new ConstraintEnvironment(compilationContext);
349 scheduler = new TypeCheckingScheduler(compilationContext);
352 typeCheckRelations();
355 scheduler.schedule();
358 private void typeCheckRules() {
359 scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
361 public void solveConstraints() {
362 // TODO Auto-generated method stub
366 public void injectEvidence(TVar[] vars, TPred[] constraints) {
367 // TODO Auto-generated method stub
372 public void initializeTypeChecking(TypingContext context) {
373 // TODO Auto-generated method stub
378 public ArrayList<Constraint> getUnsolvedConstraints() {
379 return new ArrayList<Constraint>(0);
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.");
393 public long getLocation() {
394 // TODO Auto-generated method stub
399 public ArrayList<Variable> getFreeEvidence() {
400 return new ArrayList<Variable>(0);
404 public Collection<Object> getDefinedObjects() {
405 return Collections.singleton(ETransformation.TRANSFORMATION_RULES_TYPECHECKED);
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);
417 public void collectFreeTypeVariables(THashSet<TVar> varSet) {
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()));
430 if(!module.getMappingRelations().isEmpty())
431 scheduler.addPostTypeCheckingRunnable(new Runnable() {
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.");