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.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;
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;
47 public class TypeChecking {
48 final ErrorLog errorLog;
49 final Environment environment;
50 final ConcreteModule module;
52 ConstraintEnvironment ce;
53 TypeCheckingScheduler scheduler;
55 public TypeChecking(ErrorLog errorLog, Environment environment,
56 ConcreteModule module) {
57 this.errorLog = errorLog;
58 this.environment = environment;
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;
73 public long getLocation() {
74 return value.getExpression().getLocation();
78 public Collection<Object> getDefinedObjects() {
79 return Collections.<Object>singleton(value);
83 public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
84 value.getExpression().collectRefs(allRefs, refs);
88 public void initializeTypeChecking(TypingContext context) {
89 value.setType(Types.metaVar(Kinds.STAR));
90 context.recursiveValues.add(value);
94 public void checkType(TypingContext context) {
95 context.recursiveReferences =
96 this.recursiveReferences = new ArrayList<EPlaceholder>();
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);
106 ArrayList<EVariable> constraintDemand = context.getConstraintDemand();
107 if(!constraintDemand.isEmpty()) {
108 this.constraintDemand = constraintDemand;
109 context.resetConstraintDemand();
112 expression.getType().addPolarity(Polarity.POSITIVE);
116 public void solveConstraints() {
117 if(constraintDemand != null) {
118 Expression expression = value.getExpression();
120 ReducedConstraints red = ConstraintSolver.solve(
121 ce, new ArrayList<TPred>(0), constraintDemand,
124 expression = ExpressionAugmentation.augmentSolved(
125 red.solvedConstraints,
127 value.setExpression(expression);
128 value.setType(expression.getType());
130 for(Constraint c : red.unsolvedConstraints)
131 if(c.constraint.isGround())
132 errorLog.log(c.getDemandLocation(), "There is no instance for <"+c.constraint+">.");
134 ArrayList<Variable> fe = new ArrayList<Variable>(red.unsolvedConstraints.size());
135 for(Constraint c : red.unsolvedConstraints)
137 unsolvedConstraints = red.unsolvedConstraints;
141 value.setExpression(value.getExpression().decomposeMatching());
142 freeEvidence = new ArrayList<Variable>(0);
147 public void collectFreeTypeVariables(
148 THashSet<TVar> varSet) {
149 Type type = value.getType();
150 type = type.convertMetaVarsToVars();
152 varSet.addAll(Types.freeVars(type));
156 public ArrayList<Variable> getFreeEvidence() {
161 public ArrayList<Constraint> getUnsolvedConstraints() {
162 return unsolvedConstraints;
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);
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");
181 freeEvidence.add(var);
183 freeEvidence.add(var);
186 // Add evidence parameters to the functions
187 value.setExpression(lambda(Types.NO_EFFECTS, freeEvidence, value.getExpression())
189 value.setType(Types.forAll(vars,
190 Types.constrained(constraints, value.getType())));
192 // Add evidence parameters to recursive calls
193 for(EPlaceholder ref : recursiveReferences) {
194 ref.expression = loc(ref.expression.location, apply(
196 applyTypes(ref.expression, vars),
197 vars(freeEvidence)));
202 scheduler.addPostTypeCheckingRunnable(new Runnable() {
205 Type type = value.getType();
207 Expression expression = value.getExpression();
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);
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.");
232 if(errorLog.isEmpty()) { // To prevent exceptions
233 expression = ExpressionAugmentation.augmentSolved(
234 red.solvedConstraints,
236 expression = ExpressionAugmentation.augmentUnsolved(
237 red.givenConstraints,
242 if(errorLog.isEmpty()) // To prevent exceptions
243 expression = expression.decomposeMatching();
245 expression = expression.closure(vars.toArray(new TVar[vars.size()]));
246 value.setExpression(expression);
247 } catch(Exception e) {
248 errorLog.log(expression.location, e);
256 private void typeCheckRelations() {
257 for(SCLRelation relation_ : module.getRelations()) {
258 if(!(relation_ instanceof ConcreteRelation))
260 final ConcreteRelation relation = (ConcreteRelation)relation_;
261 scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
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);
273 public void solveConstraints() {
277 public void injectEvidence(TVar[] vars, TPred[] constraints) {
278 relation.typeVariables = vars;
282 public ArrayList<Constraint> getUnsolvedConstraints() {
283 return new ArrayList<Constraint>(0); // TODO
287 public long getLocation() {
288 return relation.location;
292 public ArrayList<Variable> getFreeEvidence() {
293 return new ArrayList<Variable>(0); // TODO
297 public Collection<Object> getDefinedObjects() {
298 return Collections.<Object>singleton(relation);
302 public void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
303 for(QuerySection section : relation.getSections())
304 section.query.collectRefs(allRefs, refs);
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));
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();
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();
337 public void typeCheck() {
338 ce = new ConstraintEnvironment(environment);
339 scheduler = new TypeCheckingScheduler(errorLog, environment);
342 typeCheckRelations();
345 scheduler.schedule();
348 private void typeCheckRules() {
349 scheduler.addTypeInferableDefinition(new TypeInferableDefinition() {
351 public void solveConstraints() {
352 // TODO Auto-generated method stub
356 public void injectEvidence(TVar[] vars, TPred[] constraints) {
357 // TODO Auto-generated method stub
362 public void initializeTypeChecking(TypingContext context) {
363 // TODO Auto-generated method stub
368 public ArrayList<Constraint> getUnsolvedConstraints() {
369 return new ArrayList<Constraint>(0);
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.");
383 public long getLocation() {
384 // TODO Auto-generated method stub
389 public ArrayList<Variable> getFreeEvidence() {
390 return new ArrayList<Variable>(0);
394 public Collection<Object> getDefinedObjects() {
395 return Collections.singleton(ETransformation.TRANSFORMATION_RULES_TYPECHECKED);
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);
407 public void collectFreeTypeVariables(THashSet<TVar> varSet) {
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()));
420 if(!module.getMappingRelations().isEmpty())
421 scheduler.addPostTypeCheckingRunnable(new Runnable() {
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.");