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

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