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.List;
   5
   6 import org.simantics.scl.compiler.common.exceptions.InternalCompilerError;
   7 import org.simantics.scl.compiler.constants.Constant;
   8 import org.simantics.scl.compiler.elaboration.expressions.EApply;
   9 import org.simantics.scl.compiler.elaboration.expressions.EApplyType;
  10 import org.simantics.scl.compiler.elaboration.expressions.EAsPattern;
  11 import org.simantics.scl.compiler.elaboration.expressions.EConstant;
  12 import org.simantics.scl.compiler.elaboration.expressions.EExternalConstant;
  13 import org.simantics.scl.compiler.elaboration.expressions.ELiteral;
  14 import org.simantics.scl.compiler.elaboration.expressions.EVariable;
  15 import org.simantics.scl.compiler.elaboration.expressions.Expression;
  16 import org.simantics.scl.compiler.elaboration.expressions.GuardedExpressionGroup;
  17 import org.simantics.scl.compiler.elaboration.modules.SCLValue;
  18 import org.simantics.scl.compiler.elaboration.modules.TypeConstructor;
  19 import org.simantics.scl.compiler.environment.Environment;
  20 import org.simantics.scl.compiler.internal.codegen.continuations.Branch;
  21 import org.simantics.scl.compiler.internal.codegen.continuations.ICont;
  22 import org.simantics.scl.compiler.internal.codegen.references.IVal;
  23 import org.simantics.scl.compiler.internal.codegen.writer.CodeWriter;
  24 import org.simantics.scl.compiler.types.TCon;
  25 import org.simantics.scl.compiler.types.Types;
  26 import org.simantics.scl.compiler.types.exceptions.MatchException;
  27
  28 import gnu.trove.map.hash.THashMap;
  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 }