]> gerrit.simantics Code Review - simantics/platform.git/blob
1ca1e7c3071707e09061cda747da59a6211ccbbe
[simantics/platform.git] /
1 package org.simantics.scl.compiler.internal.elaboration.matching;
2
3 import gnu.trove.map.hash.THashMap;
4
5 import java.util.ArrayList;
6 import java.util.List;
7
8 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
9 import org.simantics.scl.compiler.constants.Constant;
10 import org.simantics.scl.compiler.elaboration.expressions.EApply;
11 import org.simantics.scl.compiler.elaboration.expressions.EApplyType;
12 import org.simantics.scl.compiler.elaboration.expressions.EAsPattern;
13 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
14 import org.simantics.scl.compiler.elaboration.expressions.EExternalConstant;
15 import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
16 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
17 import org.simantics.scl.compiler.elaboration.expressions.Expression;
18 import org.simantics.scl.compiler.elaboration.expressions.GuardedExpressionGroup;
19 import org.simantics.scl.compiler.elaboration.modules.SCLValue;
20 import org.simantics.scl.compiler.elaboration.modules.TypeConstructor;
21 import org.simantics.scl.compiler.environment.Environment;
22 import org.simantics.scl.compiler.internal.codegen.continuations.Branch;
23 import org.simantics.scl.compiler.internal.codegen.continuations.ICont;
24 import org.simantics.scl.compiler.internal.codegen.references.IVal;
25 import org.simantics.scl.compiler.internal.codegen.writer.CodeWriter;
26 import org.simantics.scl.compiler.types.TCon;
27 import org.simantics.scl.compiler.types.Types;
28 import org.simantics.scl.compiler.types.exceptions.MatchException;
29
30 public class PatternMatchingCompiler {
31
32     private static class ExpressionMatrix {
33         final CodeWriter w;
34         final IVal[] scrutinee;
35         final List<Row> rows = new ArrayList<Row>();
36
37         public ExpressionMatrix(CodeWriter w, IVal[] scrutinee) {
38             this.w = w;
39             this.scrutinee = scrutinee;
40         }
41     }
42
43     public static IVal[] replace(IVal[] vals, int columnToReplace, IVal ... substitution) {
44         IVal[] newVals = new IVal[vals.length-1+substitution.length];
45         int j=0;
46         for(int i=0;i<columnToReplace;++i)
47             newVals[j++] = vals[i];
48         for(int i=0;i<substitution.length;++i)
49             newVals[j++] = substitution[i];
50         for(int i=columnToReplace+1;i<vals.length;++i)
51             newVals[j++] = vals[i];
52         return newVals;
53     }
54
55     private static void split(CodeWriter w, final Environment env, IVal[] scrutinee, final ICont success, ICont failure, List<Row> rows, int columnId) {
56         THashMap<Object, ExpressionMatrix> matrixMap = new THashMap<Object, ExpressionMatrix>();
57         ArrayList<Branch> branches = new ArrayList<Branch>();
58         ArrayList<ExpressionMatrix> matrices = new ArrayList<ExpressionMatrix>();
59         
60         /*System.out.println("---");
61         for(Row row : rows) {
62             for(Expression e : row.patterns)
63                 System.out.print(e + " ");
64             System.out.println();
65         }*/
66
67         int i;
68         for(i=0;i<rows.size();++i) {
69             Row row = rows.get(i);
70             Expression pattern = row.patterns[columnId];
71             while(true) {
72                 if(pattern instanceof EApplyType)
73                     pattern = ((EApplyType)pattern).getExpression();
74                 else if(pattern instanceof EAsPattern) {
75                     EAsPattern asPattern = (EAsPattern)pattern;
76                     pattern = asPattern.getPattern();
77                     asPattern.getVariable().setVal(scrutinee[columnId]);
78                 }
79                 else
80                     break;
81                 row.patterns[columnId] = pattern;
82             }
83             if(pattern instanceof EVariable)
84                 break;
85             else if(pattern instanceof EApply) {
86                 EApply applyConstructor = (EApply)pattern;
87                 Expression constructor_ = applyConstructor.getFunction();
88                 while(constructor_ instanceof EApplyType)
89                     constructor_ = ((EApplyType)constructor_).getExpression();
90                 SCLValue constructor = ((EConstant)constructor_).getValue();
91                 // TODO How type parameters are handled???
92                 Expression[] parameters = applyConstructor.getParameters();
93
94                 ExpressionMatrix matrix = matrixMap.get(constructor.getName());
95                 if(matrix == null) {
96                     CodeWriter newW = w.createBlock(Types.getTypes(parameters));
97                     branches.add(new Branch((Constant)constructor.getValue(), newW.getContinuation()));
98                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
99                     matrices.add(matrix);
100                     matrixMap.put(constructor.getName(), matrix);
101                 }
102                 matrix.rows.add(row.replace(columnId, parameters));
103             }
104             else if(pattern instanceof EConstant) {
105                 EConstant applyConstructor = (EConstant)pattern;
106                 SCLValue constructor = applyConstructor.getValue();
107
108                 ExpressionMatrix matrix = matrixMap.get(constructor.getName());
109                 if(matrix == null) {
110                     CodeWriter newW = w.createBlock();
111                     branches.add(new Branch((Constant)constructor.getValue(), newW.getContinuation()));
112                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
113                     matrices.add(matrix);
114                     matrixMap.put(constructor.getName(), matrix);
115                 }
116                 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
117             }
118             else if(pattern instanceof ELiteral) {
119                 ELiteral literal = (ELiteral)pattern;
120                 Constant constructor = literal.getValue();
121
122                 ExpressionMatrix matrix = matrixMap.get(constructor);
123                 if(matrix == null) {
124                     CodeWriter newW = w.createBlock();
125                     branches.add(new Branch(constructor, newW.getContinuation()));
126                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
127                     matrices.add(matrix);
128                     matrixMap.put(constructor, matrix);
129                 }
130                 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
131             }
132             else if(pattern instanceof EExternalConstant) {
133                 EExternalConstant constant = (EExternalConstant)pattern;
134                 Constant constructor = w.getModuleWriter().getExternalConstant(constant.getValue(), constant.getType());
135
136                 ExpressionMatrix matrix = matrixMap.get(constructor);
137                 if(matrix == null) {
138                     CodeWriter newW = w.createBlock();
139                     branches.add(new Branch(constructor, newW.getContinuation()));
140                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
141                     matrices.add(matrix);
142                     matrixMap.put(constructor, matrix);
143                 }
144                 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
145             }
146             else
147                 throw new InternalCompilerError("Cannot handle an instance of " + pattern.getClass().getSimpleName() + " in a pattern.");
148         }
149         if(i < rows.size()) {
150             CodeWriter newW = w.createBlock();
151             ICont cont = newW.getContinuation();
152             branches.add(new Branch(null, cont));
153             split(newW, env, scrutinee, success, failure, rows.subList(i, rows.size()));
154             failure = cont;
155         }
156         else {
157             TCon con;
158             try {
159                 con = Types.getConstructor(scrutinee[columnId].getType());
160             } catch (MatchException e) {
161                 throw new InternalCompilerError();
162             }
163             TypeConstructor cons = env.getTypeConstructor(con);
164             int maxBranchCount = cons.isOpen ? Integer.MAX_VALUE 
165                     : cons.constructors.length;
166             if(branches.size() < maxBranchCount)
167                 branches.add(new Branch(null, failure));
168         }
169
170         for(ExpressionMatrix mx : matrices)
171             split(mx.w, env, mx.scrutinee, success, failure, mx.rows);
172         w.switch_(scrutinee[columnId], branches.toArray(new Branch[branches.size()]));
173     }
174
175     public static void split(CodeWriter w, Environment env, IVal[] scrutinee, ICont success, ICont failure, List<Row> rows) {
176         Row firstRow = rows.get(0);
177         Expression[] patterns = firstRow.patterns;
178         if(scrutinee.length != patterns.length)
179             throw new InternalCompilerError();
180         
181         // Find a non-variable pattern and split by it
182         for(int i=0;i<patterns.length;++i) {
183             if(!(patterns[i] instanceof EVariable)) {
184                 split(w, env, scrutinee, success, failure, rows, i);
185                 return;
186             }
187         }
188
189         // No matching needed
190         for(int i=0;i<patterns.length;++i)
191             ((EVariable)patterns[i]).getVariable().setVal(scrutinee[i]);
192         if(firstRow.value instanceof GuardedExpressionGroup) {
193             GuardedExpressionGroup group = (GuardedExpressionGroup)firstRow.value;
194             if(rows.size() == 1) {
195                 group.compile(env, w, success, failure);
196             }
197             else {
198                 CodeWriter newW = w.createBlock();            
199                 ICont cont = newW.getContinuation();
200                 group.compile(env, w, success, cont);
201                 split(newW, env, scrutinee, success, failure, rows.subList(1, rows.size()));
202             }
203         }
204         else
205             w.jump(success, firstRow.value.toVal(env, w));
206     }
207 }