1 package org.simantics.scl.compiler.internal.elaboration.constraints;
\r
3 import gnu.trove.map.hash.THashMap;
\r
4 import gnu.trove.procedure.TObjectObjectProcedure;
\r
6 import java.util.ArrayList;
\r
8 import org.simantics.scl.compiler.types.TApply;
\r
9 import org.simantics.scl.compiler.types.TCon;
\r
10 import org.simantics.scl.compiler.types.Type;
\r
11 import org.simantics.scl.compiler.types.Types;
\r
12 import org.simantics.scl.compiler.types.util.MultiApply;
\r
14 public class InstanceTree<T> {
\r
18 private static interface Node<T> {
\r
19 T get(ArrayList<Type> types);
\r
22 private static class SplitNode<T> implements Node<T> {
\r
24 THashMap<TCon, Node<T>> map;
\r
25 Node<T> alternative;
\r
27 public SplitNode(int pId, THashMap<TCon, Node<T>> map, Node<T> alternative) {
\r
30 this.alternative = alternative;
\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
39 for(Type parameter : apply.parameters)
\r
40 types.add(parameter);
\r
41 return node.get(types);
\r
45 private static class Entry<T> {
\r
50 private static boolean isIndexable(Type type) {
\r
51 type = Types.canonical(type);
\r
53 if(type instanceof TCon)
\r
55 else if(type instanceof TApply)
\r
56 type = Types.canonical(((TApply)type).function);
\r
62 private static <T> int choosePId(ArrayList<Entry<T>> entries) {
\r
63 int arity = entries.get(0).types.length;
\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
73 for(int i=1;i<arity;++i)
\r
74 if(indexableCount[i] > bestIndexableCount) {
\r
75 bestIndexableCount = indexableCount[i];
\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
92 l = new ArrayList<Entry<T>>();
\r
93 map1.put((TCon)apply.constructor, l);
\r
95 Type[] newTypes = new Type[types.length-1+apply.parameters.length];
\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
107 otherEntries.add(entry);
\r
110 final THashMap<TCon, Node<T>> map = new THashMap<TCon, Node<T>>();
\r
111 map1.forEachEntry(new TObjectObjectProcedure<TCon, ArrayList<Entry<T>>>() {
\r
113 public boolean execute(TCon a, ArrayList<Entry<T>> b) {
\r
114 map.put(a, create(b));
\r
118 return new SplitNode<T>(pId, map, create(otherEntries));
\r
121 public T get(ArrayList<Type> types) {
\r
122 return root.get(types);
\r