(refs #7375) Replaced collectFreeVariables method by a visitor
[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / elaboration / expressions / Expression.java
1 package org.simantics.scl.compiler.elaboration.expressions;
2
3 import java.util.ArrayList;
4 import java.util.Set;
5
6 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
7 import org.simantics.scl.compiler.common.precedence.Precedence;
8 import org.simantics.scl.compiler.compilation.CompilationContext;
9 import org.simantics.scl.compiler.constants.NoRepConstant;
10 import org.simantics.scl.compiler.elaboration.contexts.ReplaceContext;
11 import org.simantics.scl.compiler.elaboration.contexts.SimplificationContext;
12 import org.simantics.scl.compiler.elaboration.contexts.TranslationContext;
13 import org.simantics.scl.compiler.elaboration.contexts.TypingContext;
14 import org.simantics.scl.compiler.elaboration.errors.NotPatternException;
15 import org.simantics.scl.compiler.elaboration.expressions.lhstype.LhsType;
16 import org.simantics.scl.compiler.elaboration.expressions.lhstype.PatternMatchingLhs;
17 import org.simantics.scl.compiler.elaboration.expressions.printing.ExpressionToStringVisitor;
18 import org.simantics.scl.compiler.elaboration.expressions.visitors.CollectEffectsVisitor;
19 import org.simantics.scl.compiler.elaboration.expressions.visitors.CollectFreeVariablesVisitor;
20 import org.simantics.scl.compiler.elaboration.expressions.visitors.CollectRefsVisitor;
21 import org.simantics.scl.compiler.elaboration.expressions.visitors.ForVariablesUsesVisitor;
22 import org.simantics.scl.compiler.elaboration.expressions.visitors.StandardExpressionVisitor;
23 import org.simantics.scl.compiler.elaboration.query.QAtom;
24 import org.simantics.scl.compiler.elaboration.relations.SCLRelation;
25 import org.simantics.scl.compiler.internal.codegen.references.IVal;
26 import org.simantics.scl.compiler.internal.codegen.writer.CodeWriter;
27 import org.simantics.scl.compiler.internal.elaboration.decomposed.DecomposedExpression;
28 import org.simantics.scl.compiler.internal.interpreted.IExpression;
29 import org.simantics.scl.compiler.internal.parsing.Symbol;
30 import org.simantics.scl.compiler.top.ExpressionInterpretationContext;
31 import org.simantics.scl.compiler.types.TForAll;
32 import org.simantics.scl.compiler.types.TFun;
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.exceptions.MatchException;
38 import org.simantics.scl.compiler.types.kinds.Kinds;
39 import org.simantics.scl.compiler.types.util.Typed;
40
41 import gnu.trove.map.hash.TObjectIntHashMap;
42 import gnu.trove.set.hash.TIntHashSet;
43
44 public abstract class Expression extends Symbol implements Typed {
45     public static final Expression[] EMPTY_ARRAY = new Expression[0];
46     
47     transient
48     private Type type;
49     
50     public Expression() {
51     }
52     
53     public Expression(long loc) {
54         this.location = loc;
55     }
56         
57     @Override
58     public Type getType() {
59         if(type == null) {
60             try {
61                 updateType();
62             } catch (MatchException e) {
63                 throw new InternalCompilerError(e);
64             }
65             if(type == null)
66                 throw new InternalCompilerError(getClass().getSimpleName() + 
67                         ".updateType couldn't compute its type.");
68         }
69         return type;
70     }
71
72     public void setType(Type type) {
73         if(type == null)
74             throw new NullPointerException();
75         this.type = type;
76     }
77         
78         /**
79          * Infers the type of the expression without any context. Adds type
80      * applications and lambdas if needed.       
81          */
82     public Expression inferType(TypingContext context) {
83         return checkBasicType(context, Types.metaVar(Kinds.STAR));
84     }
85
86     public Expression checkBasicType(TypingContext context, Type requiredType) {
87         return context.subsume(inferType(context), requiredType);
88     }
89     
90     protected Expression applyPUnit(TypingContext context) {
91         Type type = Types.canonical(getType());
92         if(type instanceof TFun) {
93             TFun fun = (TFun)type;
94             if(fun.getCanonicalDomain() == Types.PUNIT) {
95                 EApply result = new EApply(location, this, new ELiteral(NoRepConstant.PUNIT));
96                 result.effect = fun.getCanonicalEffect();
97                 context.declareEffect(this.location, result.effect);
98                 return result;
99             }
100         }
101         return this;
102     }
103
104     public Expression checkIgnoredType(TypingContext context) {
105         Expression expression = inferType(context);
106         if(Types.canonical(expression.getType()) != Types.UNIT)
107             expression = new ESimpleLet(location, null, expression, new ELiteral(NoRepConstant.PUNIT));
108         return expression;
109     }
110
111     /**
112      * Checks the type of the expression against the given type. Adds type
113      * applications and lambdas if needed.
114      */
115     public final Expression checkType(TypingContext context, Type requiredType) {
116         //System.out.println("checkType: " + this + " :: " + requiredType);
117         if(!context.isInPattern()) {
118             requiredType = Types.canonical(requiredType);
119             if(requiredType instanceof TForAll) {
120                 TForAll forAll = (TForAll)requiredType;
121                 TVar var = forAll.var;
122                 TVar newVar = Types.var(var.getKind());
123                 requiredType = Types.canonical(forAll.type).replace(var, newVar);
124                 return new ELambdaType(new TVar[] {newVar}, checkType(context, requiredType));
125             }
126             while(requiredType instanceof TFun) {
127                 TFun fun = (TFun)requiredType;
128                 if(fun.domain instanceof TPred) { // No need to canonicalize
129                     ArrayList<Variable> constraints = new ArrayList<Variable>(2);
130                     while(true) {
131                         constraints.add(new Variable("constraint", fun.domain));
132                         requiredType = Types.canonical(fun.range);
133                         if(!(requiredType instanceof TFun))
134                             break;
135                         fun = (TFun)requiredType;
136                         if(!(fun.domain instanceof TPred))
137                             break;
138                     }
139                     context.pushConstraintFrame(constraints.toArray(new Variable[constraints.size()]));
140                     Expression expression = checkType(context, requiredType);
141                     context.popConstraintFrame();
142                     for(int i=constraints.size()-1;i>=0;--i)
143                         expression = new ESimpleLambda(constraints.get(i), expression);
144                     return expression;
145                 }
146                 else if(fun.domain == Types.PUNIT) {
147                     context.pushEffectUpperBound(location, fun.effect);
148                     Expression expr = checkType(context, fun.range);
149                     context.popEffectUpperBound();       
150
151                     // Wrap
152                     Variable var = new Variable("punit", Types.PUNIT);
153                     return new ESimpleLambda(location, var, fun.effect, expr);
154                 }
155                 else
156                     break;
157             }
158         }
159         return checkBasicType(context, requiredType); 
160     }
161
162     public final void collectRefs(TObjectIntHashMap<Object> allRefs, TIntHashSet refs) {
163         accept(new CollectRefsVisitor(allRefs, refs));
164     }
165
166     public abstract void collectVars(TObjectIntHashMap<Variable> allVars, TIntHashSet vars);
167
168     public final void forVariableUses(VariableProcedure procedure) {
169         accept(new ForVariablesUsesVisitor(procedure));
170     }
171
172     public Expression decomposeMatching() {
173         return this;
174     }
175
176         public String toString() {
177             StringBuilder b = new StringBuilder();
178             ExpressionToStringVisitor visitor = new ExpressionToStringVisitor(b);
179             accept(visitor);
180             return b.toString();
181     }
182
183         protected abstract void updateType() throws MatchException;
184         
185         public static class TypeValidationException extends Exception {
186         private static final long serialVersionUID = 3181298127162041248L;  
187         
188         long loc;
189
190         public TypeValidationException(long loc) {
191             this.loc = loc;
192         }
193         
194         public long getLoc() {
195             return loc;
196         }
197
198         public TypeValidationException(long loc, Throwable cause) {
199             super(cause);
200             this.loc = loc;
201         }
202     }
203     
204     public static void assertEquals(long loc, Type a, Type b) throws TypeValidationException {
205         if(!Types.equals(a, b))
206             throw new TypeValidationException(loc);
207     }
208
209         public abstract IVal toVal(CompilationContext context, CodeWriter w);
210                 
211         public Expression closure(TVar ... vars) {
212             if(vars.length == 0)
213             return this;
214         return new ELambdaType(vars, this);
215         }
216     
217     public Expression simplify(SimplificationContext context) {
218         System.out.println("#############################");
219         System.out.println(this);
220         throw new InternalCompilerError(location, getClass().getSimpleName() + " does not support simplify method.");
221     }
222
223     public abstract Expression resolve(TranslationContext context);
224     
225     /**
226      * Returns head of the pattern.
227      */
228     public EVar getPatternHead() throws NotPatternException {
229         throw new NotPatternException(this);
230     }
231     
232     public LhsType getLhsType() throws NotPatternException {
233         throw new NotPatternException(this);
234     }
235
236     protected void collectVariableNames(PatternMatchingLhs lhsType) throws NotPatternException {
237         throw new NotPatternException(this);
238     }
239
240     public void getParameters(TranslationContext translationContext,
241             ArrayList<Expression> parameters) {
242         throw new InternalCompilerError("Class " + getClass().getSimpleName() + " does not support getParameters.");        
243     }
244
245     public Expression resolveAsPattern(TranslationContext context) {
246         context.getErrorLog().log(location, "Pattern was expected here.");
247         return new EError();
248     }
249     
250     public Expression checkTypeAsPattern(TypingContext context, Type requiredType) {
251         if(context.isInPattern())
252             throw new InternalCompilerError("Already in a pattern.");
253         context.setInPattern(true);
254         Expression expression = checkType(context, requiredType);
255         context.setInPattern(false);
256         return expression;
257     }
258
259     /**
260      * Used during simplification and in toIExpression
261      */
262     public Set<Variable> getFreeVariables() {
263         CollectFreeVariablesVisitor visitor = new CollectFreeVariablesVisitor(); 
264         accept(visitor);
265         return visitor.getFreeVariables();
266     }
267
268     public static Expression[] concat(Expression[] a, Expression[] b) {
269         if(a.length == 0)
270             return b;
271         if(b.length == 0)
272             return a;
273         Expression[] result = new Expression[a.length + b.length];
274         for(int i=0;i<a.length;++i)
275             result[i] = a[i];
276         for(int i=0;i<b.length;++i)
277             result[i+a.length] = b[i];
278         return result;
279     }
280
281     public Expression replace(ReplaceContext context) {
282         throw new InternalCompilerError(getClass().getSimpleName() + " does not support replace.");
283     }
284     
285     public static Expression[] replace(ReplaceContext context, Expression[] expressions) {
286         Expression[] result = new Expression[expressions.length];
287         for(int i=0;i<expressions.length;++i)
288             result[i] = expressions[i].replace(context);
289         return result;
290     }
291     
292     public Expression copy() {
293         return replace(new ReplaceContext(null));
294     }
295     
296     public Expression copy(TypingContext typingContext) {
297         return replace(new ReplaceContext(typingContext));
298     }
299
300     public abstract void setLocationDeep(long loc);
301
302     public Expression replaceInPattern(ReplaceContext context) {
303         context.inPattern = true;
304         Expression result = replace(context);
305         context.inPattern = false;
306         return result;
307     }
308
309     public int getFunctionDefinitionPatternArity() throws NotPatternException {
310         throw new NotPatternException(this);
311     }
312     
313     public IVal lambdaToVal(CompilationContext context, CodeWriter w) {
314         DecomposedExpression decomposed = DecomposedExpression.decompose(context.errorLog, this);
315         CodeWriter newW = w.createFunction(decomposed.typeParameters, decomposed.effect, decomposed.returnType, decomposed.parameterTypes);
316         IVal[] parameters = newW.getParameters();
317         IVal functionVal = newW.getFunction().getTarget();
318         for(int i=0;i<parameters.length;++i)
319             decomposed.parameters[i].setVal(parameters[i]);
320         newW.return_(decomposed.body.toVal(context, newW));
321         return functionVal;
322     }
323     
324     public IExpression toIExpression(ExpressionInterpretationContext context) {
325         throw new UnsupportedOperationException();
326     }
327     
328     public static IExpression[] toIExpressions(ExpressionInterpretationContext target, Expression[] expressions) {
329         IExpression[] result = new IExpression[expressions.length];
330         for(int i=0;i<expressions.length;++i)
331             result[i] = expressions[i].toIExpression(target);
332         return result;
333     }
334     
335     public Expression applyType(Type type) {
336         return new EApplyType(location, this, type);
337     }
338
339         public boolean isEffectful() {
340                 return true;
341         }
342
343     public boolean isFunctionPattern() {
344         return false;
345     }
346
347     public boolean isConstructorApplication() {
348         return false;
349     }
350     
351     public Type getEffect() {
352         CollectEffectsVisitor visitor = new CollectEffectsVisitor();
353         accept(visitor);
354         return visitor.getCombinedEffect();
355     }
356     
357     public abstract void accept(ExpressionVisitor visitor);
358     
359     public void collectRelationRefs(
360             final TObjectIntHashMap<SCLRelation> allRefs, final TIntHashSet refs) {
361         accept(new StandardExpressionVisitor() {
362             @Override
363             public void visit(QAtom query) {
364                 int id = allRefs.get(query.relation);
365                 if(id >= 0)
366                     refs.add(id);
367             }
368         });
369     }
370
371     public boolean isFunctionDefinitionLhs() {
372         return false;
373     }
374
375     public Precedence getPrecedence() {
376         return Precedence.DEFAULT;
377     }
378
379     public boolean isPattern(int arity) {
380         return false;
381     }
382     
383     public abstract Expression accept(ExpressionTransformer transformer);
384
385     // TODO implement for all expressions
386     public boolean equalsExpression(Expression expression) {
387         return false;
388     }
389
390     /**
391      * This method returns a lower bound for the function arity of the value this expression defines.
392      * The lower bound is calculated purely looking the syntax of the expression, not the
393      * types of the constants and variables the expression refers to.
394      */
395     public int getSyntacticFunctionArity() {
396         return 0;
397     }
398 }