Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / internal / elaboration / constraints / InstanceTree.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java
new file mode 100644 (file)
index 0000000..3b04473
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/constraints/InstanceTree.java
@@ -0,0 +1,124 @@
+package org.simantics.scl.compiler.internal.elaboration.constraints;\r
+\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.procedure.TObjectObjectProcedure;\r
+\r
+import java.util.ArrayList;\r
+\r
+import org.simantics.scl.compiler.types.TApply;\r
+import org.simantics.scl.compiler.types.TCon;\r
+import org.simantics.scl.compiler.types.Type;\r
+import org.simantics.scl.compiler.types.Types;\r
+import org.simantics.scl.compiler.types.util.MultiApply;\r
+\r
+public class InstanceTree<T> {\r
+\r
+    Node<T> root;\r
+    \r
+    private static interface Node<T> {\r
+        T get(ArrayList<Type> types);        \r
+    }\r
+    \r
+    private static class SplitNode<T> implements Node<T> {\r
+        int pId;\r
+        THashMap<TCon, Node<T>> map;\r
+        Node<T> alternative;\r
+        \r
+        public SplitNode(int pId, THashMap<TCon, Node<T>> map, Node<T> alternative) {\r
+            this.pId = pId;\r
+            this.map = map;\r
+            this.alternative = alternative;\r
+        }\r
+\r
+        @Override\r
+        public T get(ArrayList<Type> types) {\r
+            MultiApply apply = Types.matchApply(types.get(pId));\r
+            Node<T> node = map.get(apply.constructor);\r
+            if(node == null)\r
+                return null;\r
+            for(Type parameter : apply.parameters)\r
+                types.add(parameter);\r
+            return node.get(types);\r
+        }\r
+    }\r
+    \r
+    private static class Entry<T> {\r
+        Type[] types;\r
+        T value;\r
+    }\r
+    \r
+    private static boolean isIndexable(Type type) {\r
+        type = Types.canonical(type);\r
+        while(true) {\r
+            if(type instanceof TCon)\r
+                return true;\r
+            else if(type instanceof TApply)\r
+                type = Types.canonical(((TApply)type).function);\r
+            else\r
+                return false;\r
+        }\r
+    }\r
+    \r
+    private static <T> int choosePId(ArrayList<Entry<T>> entries) {\r
+        int arity = entries.get(0).types.length;\r
+        if(arity == 1)\r
+            return 0;\r
+        int[] indexableCount = new int[arity];\r
+        for(Entry<T> entry : entries)\r
+            for(int i=0;i<arity;++i)\r
+                if(isIndexable(entry.types[i]))\r
+                    ++indexableCount[i];\r
+        int bestIndexableCount = indexableCount[0];\r
+        int bestPId = 0;\r
+        for(int i=1;i<arity;++i)\r
+            if(indexableCount[i] > bestIndexableCount) {\r
+                bestIndexableCount = indexableCount[i];\r
+                bestPId = i;\r
+            }\r
+        return bestPId;\r
+    }\r
+        \r
+    private static <T> Node<T> create(ArrayList<Entry<T>> entries) {\r
+        int pId = choosePId(entries);\r
+        THashMap<TCon, ArrayList<Entry<T>>> map1 = new THashMap<TCon, ArrayList<Entry<T>>>();\r
+        ArrayList<Entry<T>> otherEntries = new ArrayList<Entry<T>>(); \r
+        for(Entry<T> entry : entries) {\r
+            Type[] types = entry.types;\r
+            Type type = types[pId];\r
+            MultiApply apply = Types.matchApply(type);\r
+            if(apply.constructor instanceof TCon) {\r
+                ArrayList<Entry<T>> l = map1.get((TCon)apply.constructor);\r
+                if(l == null) {\r
+                    l = new ArrayList<Entry<T>>();\r
+                    map1.put((TCon)apply.constructor, l);\r
+                }\r
+                Type[] newTypes = new Type[types.length-1+apply.parameters.length];\r
+                int j=0;\r
+                for(int i=0;i<pId;++i)\r
+                    newTypes[j++] = types[i];\r
+                for(int i=0;i<apply.parameters.length;++i)\r
+                    newTypes[j++] = apply.parameters[i];\r
+                for(int i=pId+1;i<types.length;++i)\r
+                    newTypes[j++] = types[i];\r
+                entry.types = newTypes;\r
+                l.add(entry);\r
+            }\r
+            else {\r
+                otherEntries.add(entry);\r
+            }\r
+        }\r
+        final THashMap<TCon, Node<T>> map = new THashMap<TCon, Node<T>>();\r
+        map1.forEachEntry(new TObjectObjectProcedure<TCon, ArrayList<Entry<T>>>() {\r
+            @Override\r
+            public boolean execute(TCon a, ArrayList<Entry<T>> b) {\r
+                map.put(a, create(b));\r
+                return true;\r
+            }\r
+        });\r
+        return new SplitNode<T>(pId, map, create(otherEntries));\r
+    }\r
+    \r
+    public T get(ArrayList<Type> types) {\r
+        return root.get(types);\r
+    }\r
+}\r