]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java
Minor SCL enhancements and fixes for logging and test executing
[simantics/platform.git] / 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 }