bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/matching2/PatternMatchingCompiler2.java

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