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

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