bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java

   1 package org.simantics.scl.compiler.internal.elaboration.constraints;\r
   2 \r
   3 import java.util.ArrayList;\r
   4 \r
   5 import org.simantics.scl.compiler.types.TApply;\r
   6 import org.simantics.scl.compiler.types.TCon;\r
   7 import org.simantics.scl.compiler.types.Type;\r
   8 import org.simantics.scl.compiler.types.Types;\r
   9 import org.simantics.scl.compiler.types.util.MultiApply;\r
  10 \r
  11 import gnu.trove.map.hash.THashMap;\r
  12 import gnu.trove.procedure.TObjectObjectProcedure;\r
  13 \r
  14 public class InstanceTree<T> {\r
  15 \r
  16     Node<T> root;\r
  17     \r
  18     private static interface Node<T> {\r
  19         T get(ArrayList<Type> types);        \r
  20     }\r
  21     \r
  22     private static class SplitNode<T> implements Node<T> {\r
  23         int pId;\r
  24         THashMap<TCon, Node<T>> map;\r
  25         Node<T> alternative;\r
  26         \r
  27         public SplitNode(int pId, THashMap<TCon, Node<T>> map, Node<T> alternative) {\r
  28             this.pId = pId;\r
  29             this.map = map;\r
  30             this.alternative = alternative;\r
  31         }\r
  32 \r
  33         @Override\r
  34         public T get(ArrayList<Type> types) {\r
  35             MultiApply apply = Types.matchApply(types.get(pId));\r
  36             Node<T> node = map.get(apply.constructor);\r
  37             if(node == null)\r
  38                 return null;\r
  39             for(Type parameter : apply.parameters)\r
  40                 types.add(parameter);\r
  41             return node.get(types);\r
  42         }\r
  43     }\r
  44     \r
  45     private static class Entry<T> {\r
  46         Type[] types;\r
  47         T value;\r
  48     }\r
  49     \r
  50     private static boolean isIndexable(Type type) {\r
  51         type = Types.canonical(type);\r
  52         while(true) {\r
  53             if(type instanceof TCon)\r
  54                 return true;\r
  55             else if(type instanceof TApply)\r
  56                 type = Types.canonical(((TApply)type).function);\r
  57             else\r
  58                 return false;\r
  59         }\r
  60     }\r
  61     \r
  62     private static <T> int choosePId(ArrayList<Entry<T>> entries) {\r
  63         int arity = entries.get(0).types.length;\r
  64         if(arity == 1)\r
  65             return 0;\r
  66         int[] indexableCount = new int[arity];\r
  67         for(Entry<T> entry : entries)\r
  68             for(int i=0;i<arity;++i)\r
  69                 if(isIndexable(entry.types[i]))\r
  70                     ++indexableCount[i];\r
  71         int bestIndexableCount = indexableCount[0];\r
  72         int bestPId = 0;\r
  73         for(int i=1;i<arity;++i)\r
  74             if(indexableCount[i] > bestIndexableCount) {\r
  75                 bestIndexableCount = indexableCount[i];\r
  76                 bestPId = i;\r
  77             }\r
  78         return bestPId;\r
  79     }\r
  80         \r
  81     private static <T> Node<T> create(ArrayList<Entry<T>> entries) {\r
  82         int pId = choosePId(entries);\r
  83         THashMap<TCon, ArrayList<Entry<T>>> map1 = new THashMap<TCon, ArrayList<Entry<T>>>();\r
  84         ArrayList<Entry<T>> otherEntries = new ArrayList<Entry<T>>(); \r
  85         for(Entry<T> entry : entries) {\r
  86             Type[] types = entry.types;\r
  87             Type type = types[pId];\r
  88             MultiApply apply = Types.matchApply(type);\r
  89             if(apply.constructor instanceof TCon) {\r
  90                 ArrayList<Entry<T>> l = map1.get((TCon)apply.constructor);\r
  91                 if(l == null) {\r
  92                     l = new ArrayList<Entry<T>>();\r
  93                     map1.put((TCon)apply.constructor, l);\r
  94                 }\r
  95                 Type[] newTypes = new Type[types.length-1+apply.parameters.length];\r
  96                 int j=0;\r
  97                 for(int i=0;i<pId;++i)\r
  98                     newTypes[j++] = types[i];\r
  99                 for(int i=0;i<apply.parameters.length;++i)\r
 100                     newTypes[j++] = apply.parameters[i];\r
 101                 for(int i=pId+1;i<types.length;++i)\r
 102                     newTypes[j++] = types[i];\r
 103                 entry.types = newTypes;\r
 104                 l.add(entry);\r
 105             }\r
 106             else {\r
 107                 otherEntries.add(entry);\r
 108             }\r
 109         }\r
 110         final THashMap<TCon, Node<T>> map = new THashMap<TCon, Node<T>>();\r
 111         map1.forEachEntry(new TObjectObjectProcedure<TCon, ArrayList<Entry<T>>>() {\r
 112             @Override\r
 113             public boolean execute(TCon a, ArrayList<Entry<T>> b) {\r
 114                 map.put(a, create(b));\r
 115                 return true;\r
 116             }\r
 117         });\r
 118         return new SplitNode<T>(pId, map, create(otherEntries));\r
 119     }\r
 120     \r
 121     public T get(ArrayList<Type> types) {\r
 122         return root.get(types);\r
 123     }\r
 124 }\r