bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/matching/PatternMatchingCompiler.java

   1 package org.simantics.scl.compiler.internal.elaboration.matching;
   2
   3 import java.util.ArrayList;
   4 import java.util.Arrays;
   5 import java.util.List;
   6
   7 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   8 import org.simantics.scl.compiler.constants.Constant;
   9 import org.simantics.scl.compiler.elaboration.expressions.EApply;
  10 import org.simantics.scl.compiler.elaboration.expressions.EApplyType;
  11 import org.simantics.scl.compiler.elaboration.expressions.EAsPattern;
  12 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
  13 import org.simantics.scl.compiler.elaboration.expressions.EExternalConstant;
  14 import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
  15 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
  16 import org.simantics.scl.compiler.elaboration.expressions.EViewPattern;
  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 import gnu.trove.map.hash.THashMap;
  31
  32 public class PatternMatchingCompiler {
  33
  34     private static class ExpressionMatrix {
  35         final CodeWriter w;
  36         final IVal[] scrutinee;
  37         final List<Row> rows = new ArrayList<Row>();
  38
  39         public ExpressionMatrix(CodeWriter w, IVal[] scrutinee) {
  40             this.w = w;
  41             this.scrutinee = scrutinee;
  42         }
  43     }
  44
  45     public static IVal[] replace(IVal[] vals, int columnToReplace, IVal ... substitution) {
  46         IVal[] newVals = new IVal[vals.length-1+substitution.length];
  47         int j=0;
  48         for(int i=0;i<columnToReplace;++i)
  49             newVals[j++] = vals[i];
  50         for(int i=0;i<substitution.length;++i)
  51             newVals[j++] = substitution[i];
  52         for(int i=columnToReplace+1;i<vals.length;++i)
  53             newVals[j++] = vals[i];
  54         return newVals;
  55     }
  56
  57     private static void splitByConstructors(CodeWriter w, final Environment env, IVal[] scrutinee, final ICont success, ICont failure, List<Row> rows, int columnId) {
  58         THashMap<Object, ExpressionMatrix> matrixMap = new THashMap<Object, ExpressionMatrix>();
  59         ArrayList<Branch> branches = new ArrayList<Branch>();
  60         ArrayList<ExpressionMatrix> matrices = new ArrayList<ExpressionMatrix>();
  61
  62         /*System.out.println("---");
  63         for(Row row : rows) {
  64             for(Expression e : row.patterns)
  65                 System.out.print(e + " ");
  66             System.out.println();
  67         }*/
  68
  69         int i;
  70         for(i=0;i<rows.size();++i) {
  71             Row row = rows.get(i);
  72             Expression pattern = row.patterns[columnId];
  73             while(true) {
  74                 if(pattern instanceof EApplyType)
  75                     pattern = ((EApplyType)pattern).getExpression();
  76                 else if(pattern instanceof EAsPattern) {
  77                     EAsPattern asPattern = (EAsPattern)pattern;
  78                     pattern = asPattern.getPattern();
  79                     asPattern.getVariable().setVal(scrutinee[columnId]);
  80                 }
  81                 else
  82                     break;
  83                 row.patterns[columnId] = pattern;
  84             }
  85             if(pattern instanceof EVariable)
  86                 break;
  87             else if(pattern instanceof EApply) {
  88                 EApply applyConstructor = (EApply)pattern;
  89                 Expression constructor_ = applyConstructor.getFunction();
  90                 while(constructor_ instanceof EApplyType)
  91                     constructor_ = ((EApplyType)constructor_).getExpression();
  92                 Expression[] parameters = applyConstructor.getParameters();
  93                 // TODO How type parameters are handled???
  94                 if(constructor_ instanceof EConstant) {
  95                     SCLValue constructor = ((EConstant)constructor_).getValue();
  96
  97                     ExpressionMatrix matrix = matrixMap.get(constructor.getName());
  98                     if(matrix == null) {
  99                         CodeWriter newW = w.createBlock(Types.getTypes(parameters));
 100                         branches.add(new Branch((Constant)constructor.getValue(), newW.getContinuation()));
 101                         matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
 102                         matrices.add(matrix);
 103                         matrixMap.put(constructor.getName(), matrix);
 104                     }
 105                     matrix.rows.add(row.replace(columnId, parameters));
 106                 }
 107                 else if(constructor_ instanceof ELiteral) {
 108                     Constant constructor = ((ELiteral)constructor_).getValue();
 109
 110                     ExpressionMatrix matrix = matrixMap.get(constructor);
 111                     if(matrix == null) {
 112                         CodeWriter newW = w.createBlock(Types.getTypes(parameters));
 113                         branches.add(new Branch(constructor, newW.getContinuation()));
 114                         matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
 115                         matrices.add(matrix);
 116                         matrixMap.put(constructor, matrix);
 117                     }
 118                     matrix.rows.add(row.replace(columnId, parameters));
 119                 }
 120             }
 121             else if(pattern instanceof EConstant) {
 122                 EConstant applyConstructor = (EConstant)pattern;
 123                 SCLValue constructor = applyConstructor.getValue();
 124
 125                 ExpressionMatrix matrix = matrixMap.get(constructor.getName());
 126                 if(matrix == null) {
 127                     CodeWriter newW = w.createBlock();
 128                     branches.add(new Branch((Constant)constructor.getValue(), newW.getContinuation()));
 129                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
 130                     matrices.add(matrix);
 131                     matrixMap.put(constructor.getName(), matrix);
 132                 }
 133                 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
 134             }
 135             else if(pattern instanceof ELiteral) {
 136                 ELiteral literal = (ELiteral)pattern;
 137                 Constant constructor = literal.getValue();
 138
 139                 ExpressionMatrix matrix = matrixMap.get(constructor);
 140                 if(matrix == null) {
 141                     CodeWriter newW = w.createBlock();
 142                     branches.add(new Branch(constructor, newW.getContinuation()));
 143                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
 144                     matrices.add(matrix);
 145                     matrixMap.put(constructor, matrix);
 146                 }
 147                 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
 148             }
 149             else if(pattern instanceof EExternalConstant) {
 150                 EExternalConstant constant = (EExternalConstant)pattern;
 151                 Constant constructor = w.getModuleWriter().getExternalConstant(constant.getValue(), constant.getType());
 152
 153                 ExpressionMatrix matrix = matrixMap.get(constructor);
 154                 if(matrix == null) {
 155                     CodeWriter newW = w.createBlock();
 156                     branches.add(new Branch(constructor, newW.getContinuation()));
 157                     matrix = new ExpressionMatrix(newW, replace(scrutinee, columnId, newW.getParameters()));
 158                     matrices.add(matrix);
 159                     matrixMap.put(constructor, matrix);
 160                 }
 161                 matrix.rows.add(row.replace(columnId, Expression.EMPTY_ARRAY));
 162             }
 163             else
 164                 throw new InternalCompilerError("Cannot handle an instance of " + pattern.getClass().getSimpleName() + " in a pattern.");
 165         }
 166         if(i < rows.size()) {
 167             CodeWriter newW = w.createBlock();
 168             ICont cont = newW.getContinuation();
 169             branches.add(new Branch(null, cont));
 170             split(newW, env, scrutinee, success, failure, rows.subList(i, rows.size()));
 171             failure = cont;
 172         }
 173         else {
 174             TCon con;
 175             try {
 176                 con = Types.getConstructor(scrutinee[columnId].getType());
 177             } catch (MatchException e) {
 178                 throw new InternalCompilerError();
 179             }
 180             TypeConstructor cons = (TypeConstructor)env.getTypeDescriptor(con);
 181             int maxBranchCount = cons.isOpen ? Integer.MAX_VALUE
 182                     : cons.constructors.length;
 183             if(branches.size() < maxBranchCount)
 184                 branches.add(new Branch(null, failure));
 185         }
 186
 187         for(ExpressionMatrix mx : matrices)
 188             split(mx.w, env, mx.scrutinee, success, failure, mx.rows);
 189         w.switch_(scrutinee[columnId], branches.toArray(new Branch[branches.size()]));
 190     }
 191
 192     private static void splitByViewPattern(CodeWriter w, Environment env, IVal[] scrutinee, ICont success,
 193             ICont failure, List<Row> rows, int viewPatternColumn) {
 194         Row firstRow = rows.get(0);
 195         EViewPattern firstViewPattern = (EViewPattern)firstRow.patterns[viewPatternColumn];
 196         firstRow.patterns[viewPatternColumn] = firstViewPattern.pattern;
 197         int i;
 198         for(i=1;i<rows.size();++i) {
 199             Row row = rows.get(i);
 200             Expression pattern = row.patterns[viewPatternColumn];
 201             while(true) {
 202                 if(pattern instanceof EApplyType)
 203                     pattern = ((EApplyType)pattern).getExpression();
 204                 else if(pattern instanceof EAsPattern) {
 205                     EAsPattern asPattern = (EAsPattern)pattern;
 206                     pattern = asPattern.getPattern();
 207                     asPattern.getVariable().setVal(scrutinee[viewPatternColumn]);
 208                 }
 209                 else
 210                     break;
 211                 row.patterns[viewPatternColumn] = pattern;
 212             }
 213             if(!(pattern instanceof EViewPattern))
 214                 break;
 215             EViewPattern otherViewPattern = (EViewPattern)pattern;
 216             if(!otherViewPattern.expression.equalsExpression(firstViewPattern.expression))
 217                 break;
 218             row.patterns[viewPatternColumn] = otherViewPattern.pattern;
 219         }
 220
 221         IVal[] newScrutinee = Arrays.copyOf(scrutinee, scrutinee.length);
 222         newScrutinee[viewPatternColumn] =
 223                 w.apply(firstViewPattern.location,
 224                         firstViewPattern.expression.toVal(env, w),
 225                         scrutinee[viewPatternColumn]);
 226         if(i == rows.size()) {
 227             split(w, env, newScrutinee, success, failure, rows);
 228         }
 229         else {
 230             CodeWriter cont = w.createBlock();
 231             split(w, env, newScrutinee, success, cont.getContinuation(), rows.subList(0, i));
 232             split(cont, env, scrutinee, success, failure, rows.subList(i, rows.size()));
 233         }
 234     }
 235
 236     public static void split(CodeWriter w, Environment env, IVal[] scrutinee, ICont success, ICont failure, List<Row> rows) {
 237         Row firstRow = rows.get(0);
 238         Expression[] patterns = firstRow.patterns;
 239         if(scrutinee.length != patterns.length)
 240             throw new InternalCompilerError("Scrutinee and patterns have a different length");
 241
 242         // Find a non-variable pattern and split by it
 243         int viewPatternColumn = -1;
 244         for(int i=0;i<patterns.length;++i) {
 245             Expression pattern = patterns[i];
 246             if(pattern instanceof EViewPattern) {
 247                 if(viewPatternColumn == -1)
 248                     viewPatternColumn = i;
 249             }
 250             else if(!(pattern instanceof EVariable)) {
 251                 splitByConstructors(w, env, scrutinee, success, failure, rows, i);
 252                 return;
 253             }
 254         }
 255
 256         if(viewPatternColumn >= 0) {
 257             splitByViewPattern(w, env, scrutinee, success, failure, rows, viewPatternColumn);
 258             return;
 259         }
 260
 261         // The first row has only variable patterns: no matching needed
 262         for(int i=0;i<patterns.length;++i)
 263             ((EVariable)patterns[i]).getVariable().setVal(scrutinee[i]);
 264         if(firstRow.value instanceof GuardedExpressionGroup) {
 265             GuardedExpressionGroup group = (GuardedExpressionGroup)firstRow.value;
 266             if(rows.size() == 1) {
 267                 group.compile(env, w, success, failure);
 268             }
 269             else {
 270                 CodeWriter newW = w.createBlock();
 271                 ICont cont = newW.getContinuation();
 272                 group.compile(env, w, success, cont);
 273                 split(newW, env, scrutinee, success, failure, rows.subList(1, rows.size()));
 274             }
 275         }
 276         else
 277             w.jump(success, firstRow.value.toVal(env, w));
 278     }
 279 }