1 package org.simantics.scl.compiler.internal.elaboration.matching2;
\r
3 import java.util.ArrayList;
\r
4 import java.util.Arrays;
\r
5 import java.util.List;
\r
7 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
\r
8 import org.simantics.scl.compiler.constants.Constant;
\r
9 import org.simantics.scl.compiler.elaboration.expressions.EApply;
\r
10 import org.simantics.scl.compiler.elaboration.expressions.EApplyType;
\r
11 import org.simantics.scl.compiler.elaboration.expressions.EAsPattern;
\r
12 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
\r
13 import org.simantics.scl.compiler.elaboration.expressions.EExternalConstant;
\r
14 import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
\r
15 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
\r
16 import org.simantics.scl.compiler.elaboration.expressions.EViewPattern;
\r
17 import org.simantics.scl.compiler.elaboration.expressions.Expression;
\r
18 import org.simantics.scl.compiler.elaboration.modules.SCLValue;
\r
19 import org.simantics.scl.compiler.elaboration.modules.TypeConstructor;
\r
20 import org.simantics.scl.compiler.environment.Environment;
\r
21 import org.simantics.scl.compiler.internal.codegen.continuations.Branch;
\r
22 import org.simantics.scl.compiler.internal.codegen.continuations.ICont;
\r
23 import org.simantics.scl.compiler.internal.codegen.references.IVal;
\r
24 import org.simantics.scl.compiler.internal.codegen.writer.CodeWriter;
\r
25 import org.simantics.scl.compiler.types.TCon;
\r
26 import org.simantics.scl.compiler.types.Types;
\r
27 import org.simantics.scl.compiler.types.exceptions.MatchException;
\r
29 import gnu.trove.map.hash.THashMap;
\r
31 public class PatternMatchingCompiler2 {
\r
33 private static class ExpressionMatrix {
\r
35 final IVal[] scrutinee;
\r
36 final List<Row2> rows = new ArrayList<Row2>();
\r
38 public ExpressionMatrix(CodeWriter w, IVal[] scrutinee) {
\r
40 this.scrutinee = scrutinee;
\r
44 public static IVal[] replace(IVal[] vals, int columnToReplace, IVal ... substitution) {
\r
45 IVal[] newVals = new IVal[vals.length-1+substitution.length];
\r
47 for(int i=0;i<columnToReplace;++i)
\r
48 newVals[j++] = vals[i];
\r
49 for(int i=0;i<substitution.length;++i)
\r
50 newVals[j++] = substitution[i];
\r
51 for(int i=columnToReplace+1;i<vals.length;++i)
\r
52 newVals[j++] = vals[i];
\r
56 private static void splitByConstructors(CodeWriter w, final Environment env, IVal[] scrutinee, ICont failure, List<Row2> rows, int columnId) {
\r
57 THashMap<Object, ExpressionMatrix> matrixMap = new THashMap<Object, ExpressionMatrix>();
\r
58 ArrayList<Branch> branches = new ArrayList<Branch>();
\r
59 ArrayList<ExpressionMatrix> matrices = new ArrayList<ExpressionMatrix>();
\r
61 /*System.out.println("---");
\r
62 for(Row row : rows) {
\r
63 for(Expression e : row.patterns)
\r
64 System.out.print(e + " ");
\r
65 System.out.println();
\r
69 for(i=0;i<rows.size();++i) {
\r
70 Row2 row = rows.get(i);
\r
71 Expression pattern = row.patterns[columnId];
\r
73 if(pattern instanceof EApplyType)
\r
74 pattern = ((EApplyType)pattern).getExpression();
\r
75 else if(pattern instanceof EAsPattern) {
\r
76 EAsPattern asPattern = (EAsPattern)pattern;
\r
77 pattern = asPattern.getPattern();
\r
78 asPattern.getVariable().setVal(scrutinee[columnId]);
\r
82 row.patterns[columnId] = pattern;
\r
84 if(pattern instanceof EVariable)
\r
86 else if(pattern instanceof EApply) {
\r
87 EApply applyConstructor = (EApply)pattern;
\r
88 Expression constructor_ = applyConstructor.getFunction();
\r
89 while(constructor_ instanceof EApplyType)
\r
90 constructor_ = ((EApplyType)constructor_).getExpression();
\r
91 Expression[] parameters = applyConstructor.getParameters();
\r
92 // TODO How type parameters are handled???
\r
93 if(constructor_ instanceof EConstant) {
\r
94 SCLValue constructor = ((EConstant)constructor_).getValue();
\r
96 ExpressionMatrix matrix = matrixMap.get(constructor.getName());
\r
97 if(matrix == null) {
\r
98 CodeWriter newW = w.createBlock(Types.getTypes(parameters));
\r
99 branches.add(new Branch((Constant)constructor.getValue(), newW.getContinuation()));
\r
100 matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
\r
101 matrices.add(matrix);
\r
102 matrixMap.put(constructor.getName(), matrix);
\r
104 matrix.rows.add(row.replace(columnId, parameters));
\r
106 else if(constructor_ instanceof ELiteral) {
\r
107 Constant constructor = ((ELiteral)constructor_).getValue();
\r
109 ExpressionMatrix matrix = matrixMap.get(constructor);
\r
110 if(matrix == null) {
\r
111 CodeWriter newW = w.createBlock(Types.getTypes(parameters));
\r
112 branches.add(new Branch(constructor, newW.getContinuation()));
\r
113 matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
\r
114 matrices.add(matrix);
\r
115 matrixMap.put(constructor, matrix);
\r
117 matrix.rows.add(row.replace(columnId, parameters));
\r
120 else if(pattern instanceof EConstant) {
\r
121 EConstant applyConstructor = (EConstant)pattern;
\r
122 SCLValue constructor = applyConstructor.getValue();
\r
124 ExpressionMatrix matrix = matrixMap.get(constructor.getName());
\r
125 if(matrix == null) {
\r
126 CodeWriter newW = w.createBlock();
\r
127 branches.add(new Branch((Constant)constructor.getValue(), newW.getContinuation()));
\r
128 matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
\r
129 matrices.add(matrix);
\r
130 matrixMap.put(constructor.getName(), matrix);
\r
132 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
\r
134 else if(pattern instanceof ELiteral) {
\r
135 ELiteral literal = (ELiteral)pattern;
\r
136 Constant constructor = literal.getValue();
\r
138 ExpressionMatrix matrix = matrixMap.get(constructor);
\r
139 if(matrix == null) {
\r
140 CodeWriter newW = w.createBlock();
\r
141 branches.add(new Branch(constructor, newW.getContinuation()));
\r
142 matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
\r
143 matrices.add(matrix);
\r
144 matrixMap.put(constructor, matrix);
\r
146 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
\r
148 else if(pattern instanceof EExternalConstant) {
\r
149 EExternalConstant constant = (EExternalConstant)pattern;
\r
150 Constant constructor = w.getModuleWriter().getExternalConstant(constant.getValue(), constant.getType());
\r
152 ExpressionMatrix matrix = matrixMap.get(constructor);
\r
153 if(matrix == null) {
\r
154 CodeWriter newW = w.createBlock();
\r
155 branches.add(new Branch(constructor, newW.getContinuation()));
\r
156 matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
\r
157 matrices.add(matrix);
\r
158 matrixMap.put(constructor, matrix);
\r
160 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
\r
163 throw new InternalCompilerError("Cannot handle an instance of " + pattern.getClass().getSimpleName() + " in a pattern.");
\r
165 if(i < rows.size()) {
\r
166 CodeWriter newW = w.createBlock();
\r
167 ICont cont = newW.getContinuation();
\r
168 branches.add(new Branch(null, cont));
\r
169 split(newW, env, scrutinee, failure, rows.subList(i, rows.size()));
\r
175 con = Types.getConstructor(scrutinee[columnId].getType());
\r
176 } catch (MatchException e) {
\r
177 throw new InternalCompilerError(e);
\r
179 TypeConstructor cons = (TypeConstructor)env.getTypeDescriptor(con);
\r
180 int maxBranchCount = cons.isOpen ? Integer.MAX_VALUE
\r
181 : cons.constructors.length;
\r
182 if(branches.size() < maxBranchCount)
\r
183 branches.add(new Branch(null, failure));
\r
186 for(ExpressionMatrix mx : matrices)
\r
187 split(mx.w, env, mx.scrutinee, failure, mx.rows);
\r
188 w.switch_(scrutinee[columnId], branches.toArray(new Branch[branches.size()]));
\r
191 private static void splitByViewPattern(CodeWriter w, Environment env, IVal[] scrutinee, ICont failure, List<Row2> rows, int viewPatternColumn) {
\r
192 Row2 firstRow = rows.get(0);
\r
193 EViewPattern firstViewPattern = (EViewPattern)firstRow.patterns[viewPatternColumn];
\r
194 firstRow.patterns[viewPatternColumn] = firstViewPattern.pattern;
\r
196 for(i=1;i<rows.size();++i) {
\r
197 Row2 row = rows.get(i);
\r
198 Expression pattern = row.patterns[viewPatternColumn];
\r
200 if(pattern instanceof EApplyType)
\r
201 pattern = ((EApplyType)pattern).getExpression();
\r
202 else if(pattern instanceof EAsPattern) {
\r
203 EAsPattern asPattern = (EAsPattern)pattern;
\r
204 pattern = asPattern.getPattern();
\r
205 asPattern.getVariable().setVal(scrutinee[viewPatternColumn]);
\r
209 row.patterns[viewPatternColumn] = pattern;
\r
211 if(!(pattern instanceof EViewPattern))
\r
213 EViewPattern otherViewPattern = (EViewPattern)pattern;
\r
214 if(!otherViewPattern.expression.equalsExpression(firstViewPattern.expression))
\r
216 row.patterns[viewPatternColumn] = otherViewPattern.pattern;
\r
219 IVal[] newScrutinee = Arrays.copyOf(scrutinee, scrutinee.length);
\r
220 newScrutinee[viewPatternColumn] =
\r
221 w.apply(firstViewPattern.location,
\r
222 firstViewPattern.expression.toVal(env, w),
\r
223 scrutinee[viewPatternColumn]);
\r
224 if(i == rows.size()) {
\r
225 split(w, env, newScrutinee, failure, rows);
\r
228 CodeWriter cont = w.createBlock();
\r
229 split(w, env, newScrutinee, cont.getContinuation(), rows.subList(0, i));
\r
230 split(cont, env, scrutinee, failure, rows.subList(i, rows.size()));
\r
234 public static void split(CodeWriter w, Environment env, IVal[] scrutinee, ICont failure, List<Row2> rows) {
\r
235 Row2 firstRow = rows.get(0);
\r
236 Expression[] patterns = firstRow.patterns;
\r
237 if(scrutinee.length != patterns.length)
\r
238 throw new InternalCompilerError("Scrutinee and patterns have a different length");
\r
240 // Find a non-variable pattern and split by it
\r
241 int viewPatternColumn = -1;
\r
242 for(int i=0;i<patterns.length;++i) {
\r
243 Expression pattern = patterns[i];
\r
244 if(pattern instanceof EViewPattern) {
\r
245 if(viewPatternColumn == -1)
\r
246 viewPatternColumn = i;
\r
248 else if(!(pattern instanceof EVariable)) {
\r
249 splitByConstructors(w, env, scrutinee, failure, rows, i);
\r
254 if(viewPatternColumn >= 0) {
\r
255 splitByViewPattern(w, env, scrutinee, failure, rows, viewPatternColumn);
\r
259 // The first row has only variable patterns: no matching needed
\r
260 for(int i=0;i<patterns.length;++i)
\r
261 ((EVariable)patterns[i]).getVariable().setVal(scrutinee[i]);
\r
262 w.jump(firstRow.continuation);
\r