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.compilation.CompilationContext;
   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.EViewPattern;
  18 import org.simantics.scl.compiler.elaboration.expressions.Expression;
  19 import org.simantics.scl.compiler.elaboration.java.DynamicConstructor;
  20 import org.simantics.scl.compiler.elaboration.modules.SCLValue;
  21 import org.simantics.scl.compiler.elaboration.modules.TypeConstructor;
  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 PatternMatchingCompiler2 {
  33
  34     private static class ExpressionMatrix {
  35         final CodeWriter w;
  36         final IVal[] scrutinee;
  37         final List<Row2> rows = new ArrayList<Row2>();
  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 CompilationContext context, IVal[] scrutinee, ICont failure, List<Row2> 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             Row2 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 = constructor.getValue() == DynamicConstructor.INSTANCE ? null : 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, context, scrutinee, 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(e);
 179             }
 180             TypeConstructor cons = (TypeConstructor)context.environment.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, context, mx.scrutinee, failure, mx.rows);
 189         w.switch_(scrutinee[columnId], branches.toArray(new Branch[branches.size()]));
 190     }
 191
 192     private static void splitByViewPattern(CodeWriter w, CompilationContext context, IVal[] scrutinee, ICont failure, List<Row2> rows, int viewPatternColumn) {
 193         Row2 firstRow = rows.get(0);
 194         EViewPattern firstViewPattern = (EViewPattern)firstRow.patterns[viewPatternColumn];
 195         firstRow.patterns[viewPatternColumn] = firstViewPattern.pattern;
 196         int i;
 197         for(i=1;i<rows.size();++i) {
 198             Row2 row = rows.get(i);
 199             Expression pattern = row.patterns[viewPatternColumn];
 200             while(true) {
 201                 if(pattern instanceof EApplyType)
 202                     pattern = ((EApplyType)pattern).getExpression();
 203                 else if(pattern instanceof EAsPattern) {
 204                     EAsPattern asPattern = (EAsPattern)pattern;
 205                     pattern = asPattern.getPattern();
 206                     asPattern.getVariable().setVal(scrutinee[viewPatternColumn]);
 207                 }
 208                 else
 209                     break;
 210                 row.patterns[viewPatternColumn] = pattern;
 211             }
 212             if(!(pattern instanceof EViewPattern))
 213                 break;
 214             EViewPattern otherViewPattern = (EViewPattern)pattern;
 215             if(!otherViewPattern.expression.equalsExpression(firstViewPattern.expression))
 216                 break;
 217             row.patterns[viewPatternColumn] = otherViewPattern.pattern;
 218         }
 219
 220         IVal[] newScrutinee = Arrays.copyOf(scrutinee, scrutinee.length);
 221         newScrutinee[viewPatternColumn] =
 222                 w.apply(firstViewPattern.location,
 223                         firstViewPattern.expression.toVal(context, w),
 224                         scrutinee[viewPatternColumn]);
 225         if(i == rows.size()) {
 226             split(w, context, newScrutinee, failure, rows);
 227         }
 228         else {
 229             CodeWriter cont = w.createBlock();
 230             split(w, context, newScrutinee, cont.getContinuation(), rows.subList(0, i));
 231             split(cont, context, scrutinee, failure, rows.subList(i, rows.size()));
 232         }
 233     }
 234
 235     public static void split(CodeWriter w, CompilationContext context, IVal[] scrutinee, ICont failure, List<Row2> rows) {
 236         Row2 firstRow = rows.get(0);
 237         Expression[] patterns = firstRow.patterns;
 238         if(scrutinee.length != patterns.length)
 239             throw new InternalCompilerError("Scrutinee and patterns have a different length");
 240
 241         // Find a non-variable pattern and split by it
 242         int viewPatternColumn = -1;
 243         for(int i=0;i<patterns.length;++i) {
 244             Expression pattern = patterns[i];
 245             if(pattern instanceof EViewPattern) {
 246                 if(viewPatternColumn == -1)
 247                     viewPatternColumn = i;
 248             }
 249             else if(!(pattern instanceof EVariable)) {
 250                 splitByConstructors(w, context, scrutinee, failure, rows, i);
 251                 return;
 252             }
 253         }
 254
 255         if(viewPatternColumn >= 0) {
 256             splitByViewPattern(w, context, scrutinee, failure, rows, viewPatternColumn);
 257             return;
 258         }
 259
 260         // The first row has only variable patterns: no matching needed
 261         for(int i=0;i<patterns.length;++i)
 262             ((EVariable)patterns[i]).getVariable().setVal(scrutinee[i]);
 263         w.jump(firstRow.continuation);
 264     }
 265 }