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