map template code

map-templates.diff

diff --git a/src/jvm/clojure/lang/BootstrapMethods.java b/src/jvm/clojure/lang/BootstrapMethods.java
index 6eb04ee8..7b163bf3 100644
--- a/src/jvm/clojure/lang/BootstrapMethods.java
+++ b/src/jvm/clojure/lang/BootstrapMethods.java
@@ -1,56 +1,113 @@
 package clojure.lang;
 
 import java.util.Arrays;
 import java.lang.invoke.CallSite;
 import java.lang.invoke.ConstantCallSite;
 import java.lang.invoke.MethodHandles;
 import java.lang.invoke.MethodHandle;
 import java.lang.invoke.MethodType;
 
 public class BootstrapMethods {
 
         private static final MethodHandle MAP;
         private static final MethodHandle MAP_UNIQUE;
         private static final MethodHandle ARRAY_MAP;
         private static final MethodHandle ARRAY_MAP_UNIQUE;
+        private static final MethodHandle MAP_FROM_TEMPLATE;
 
         public static final MethodHandle RT_MAP;
         public static final MethodHandle VECTOR;
 
         private static final MethodType IPERSISTENT_MAP_TYPE = MethodType.methodType(IPersistentMap.class, Object[].class);
 
         private static MethodHandle mapCreator(MethodHandle src) {
         	return src.asType(IPERSISTENT_MAP_TYPE).asVarargsCollector(Object[].class); 
         }
 
+        public static int[] slotsFromBitmap(int count, int bitmap) {
+
+            final int mask = (1 << (count & 31)) - 1;
+            bitmap = bitmap & mask;
+            int[] ret = new int[Integer.bitCount(bitmap)];
+
+            int slotIdx = 0;
+            for (int i = 0; i < count; i++) {
+                if ((bitmap & 1) == 1) {
+                    ret[slotIdx] = i;
+                    slotIdx++;
+                }
+                bitmap = bitmap >>> 1;
+            }
+            return ret;
+        }
+
+        public static IPersistentMap createMapFromTemplate(int[] slots, Object[] template, Object... dynArgs) {
+            final int n = template.length;
+
+            Object[] arr = new Object[n];
+            System.arraycopy(template, 0, arr, 0, n);
+
+            for (int i = 0; i < slots.length; i++) {
+                arr[slots[i]] = dynArgs[i];
+            }
+
+            if (n < 16) {
+                return new PersistentArrayMap(arr);
+            } else {
+                return PersistentHashMap.create(arr);
+            }
+        }
+
+        // this *must* be varargs for proper bsm linkage
+        public static CallSite kwMap(MethodHandles.Lookup lk, String methodName, MethodType t, Object... data) {
+            int n               = (int) data[0];
+            int constantsBitmap = (int) data[1];
+            Object[] template = new Object[n];
+            int i = 2;
+
+            for (int slot : slotsFromBitmap(n, constantsBitmap)) {
+                template[slot] = Keyword.intern((String) data[i]);
+                i++;
+            }
+
+            // bit-invert the constant markers to get the dynamic markers
+            MethodHandle mh = MethodHandles.insertArguments(MAP_FROM_TEMPLATE, 0,
+                    slotsFromBitmap(n, ~constantsBitmap), template);
+
+            return new ConstantCallSite(mh.asCollector(Object[].class, t.parameterCount()));
+        }
+
     static {
         try {
                 MethodHandles.Lookup lk = MethodHandles.lookup();
 
                 MethodType vectype = MethodType.methodType(IPersistentVector.class, Object[].class);
                 VECTOR = lk.findStatic(RT.class, "vector", vectype);
 
                 MethodType amaptype = MethodType.methodType(PersistentArrayMap.class, Object[].class);
                 MethodType pmaptype = MethodType.methodType(PersistentHashMap.class, Object[].class);
 
                 MAP              = mapCreator(lk.findStatic(PersistentHashMap.class, "createWithCheck", pmaptype));
                 MAP_UNIQUE       = mapCreator(lk.findStatic(PersistentHashMap.class, "create", pmaptype));
 
                 ARRAY_MAP        = mapCreator(lk.findStatic(PersistentArrayMap.class, "createWithCheck", amaptype));
                 ARRAY_MAP_UNIQUE = mapCreator(lk.findConstructor(PersistentArrayMap.class, MethodType.methodType(void.class, Object[].class)));
 
+                MAP_FROM_TEMPLATE = lk.findStatic(BootstrapMethods.class, "createMapFromTemplate",
+                        MethodType.methodType(IPersistentMap.class, int[].class, Object[].class, Object[].class));
+
                 RT_MAP = lk.findStatic(RT.class, "map", IPERSISTENT_MAP_TYPE);
         } catch (Exception e) {
                 System.err.println(e);
                 throw new RuntimeException("Couldn't init bootstrapmethods");
         }
         }
 
 	public static CallSite varExpr(MethodHandles.Lookup lk, String methodName, MethodType t, String varNs, String varName) {
 		Var v = RT.var(varNs, varName);
                 MethodHandle mh = Var.ROOT.bindTo(v);
 		return new ConstantCallSite(mh);
 	}
 
         public static CallSite keywordExpr(MethodHandles.Lookup lk, String methodName, MethodType t, String sym) {
                 Keyword k = Keyword.intern(sym);
diff --git a/src/jvm/clojure/lang/Compiler.java b/src/jvm/clojure/lang/Compiler.java
index b2748190..b6dc08cc 100644
--- a/src/jvm/clojure/lang/Compiler.java
+++ b/src/jvm/clojure/lang/Compiler.java
@@ -2996,132 +2996,171 @@ public static class ListExpr implements Expr{
 			gen.pop();
 	}
 
 	public boolean hasJavaClass() {
 		return true;
 	}
 
 	public Class getJavaClass() {
 		return IPersistentList.class;
 	}
 
 }
 
 public static class MapExpr implements Expr{
 	public final IPersistentVector keyvals;
+	final boolean uniqueKeys;
+	final boolean templateable;
 	final static Method mapMethod = Method.getMethod("clojure.lang.IPersistentMap map(Object[])");
 	final static Method mapUniqueKeysMethod = Method.getMethod("clojure.lang.IPersistentMap mapUniqueKeys(Object[])");
 
 
-	public MapExpr(IPersistentVector keyvals){
+	public MapExpr(IPersistentVector keyvals, boolean uniqueKeys){
 		this.keyvals = keyvals;
+		this.uniqueKeys = uniqueKeys;
+		this.templateable = false;
 	}
 
+
+	public MapExpr(IPersistentVector keyvals, boolean uniqueKeys, boolean templateable){
+		this.keyvals = keyvals;
+		this.uniqueKeys = uniqueKeys;
+		this.templateable = templateable;
+	}
+
+    void emitPartial(ObjExpr objx, GeneratorAdapter gen) {
+
+        Object[] staticArgs = new Object[keyvals.count()];
+
+		int constantsBitmap = 0;
+        int ndyn = 0;
+        int nstatic = 0;
+		for(int i = 0; i < keyvals.count(); i++) {
+            Expr e = (Expr) keyvals.nth(i);
+            if (e instanceof KeywordExpr) {
+                Keyword k = ((KeywordExpr) e).k;
+                staticArgs[nstatic] = k.sym.toString();
+				constantsBitmap = constantsBitmap | (1 << i);
+                nstatic++;
+            } else {
+            	ndyn++;
+			}
+        }
+
+		Object[] bsmArgs = new Object[(2 + nstatic)];
+		bsmArgs[0] = keyvals.count();
+		bsmArgs[1] = constantsBitmap;
+		System.arraycopy(staticArgs, 0, bsmArgs, 2, nstatic);
+
+		MethodType mt = MethodType.genericMethodType(ndyn).changeReturnType(IPersistentMap.class);
+
+		// emit dynamic arguments
+		for(int i = 0; i < keyvals.count(); i++) {
+			Expr e = (Expr) keyvals.nth(i);
+			if (!(e instanceof KeywordExpr)) {
+				e.emit(C.EXPRESSION, objx, gen);
+			}
+		}
+
+        gen.invokeDynamic("kwMap",
+				mt.toMethodDescriptorString(),
+				getIndyBsm("kwMap", Object[].class),
+				bsmArgs);
+
+    }
+
 	public Object eval() {
 		Object[] ret = new Object[keyvals.count()];
 		for(int i = 0; i < keyvals.count(); i++)
 			ret[i] = ((Expr) keyvals.nth(i)).eval();
 		return RT.map(ret);
 	}
 
 	public void emit(C context, ObjExpr objx, GeneratorAdapter gen){
-		boolean allKeysConstant = true;
-		boolean allConstantKeysUnique = true;
-		IPersistentSet constantKeys = PersistentHashSet.EMPTY;
-		for(int i = 0; i < keyvals.count(); i+=2)
-			{
-			Expr k = (Expr) keyvals.nth(i);
-			if(k instanceof LiteralExpr)
-				{
-				Object kval = k.eval();
-				if (constantKeys.contains(kval))
-					allConstantKeysUnique = false;
-				else
-					constantKeys = (IPersistentSet)constantKeys.cons(kval);
-				}
-			else
-				allKeysConstant = false;
+		if(uniqueKeys) {
+			if (templateable && keyvals.count() <= 32) {
+				emitPartial(objx, gen);
+			} else {
+				MethodExpr.emitArgsAsArray(keyvals, objx, gen);
+				gen.invokeStatic(RT_TYPE, mapUniqueKeysMethod);
 			}
-		MethodExpr.emitArgsAsArray(keyvals, objx, gen);
-		if((allKeysConstant && allConstantKeysUnique) || (keyvals.count() <= 2))
-			gen.invokeStatic(RT_TYPE, mapUniqueKeysMethod);
-		else
+		}
+		else {
+			MethodExpr.emitArgsAsArray(keyvals, objx, gen);
 			gen.invokeStatic(RT_TYPE, mapMethod);
+		}
 		if(context == C.STATEMENT)
 			gen.pop();
 	}
 
 	public boolean hasJavaClass() {
 		return true;
 	}
 
 	public Class getJavaClass() {
 		return IPersistentMap.class;
 	}
 
 
 	static public Expr parse(C context, IPersistentMap form) {
 		IPersistentVector keyvals = PersistentVector.EMPTY;
 		boolean keysConstant = true;
 		boolean valsConstant = true;
 		boolean allConstantKeysUnique = true;
+		boolean templateable = false;
 		IPersistentSet constantKeys = PersistentHashSet.EMPTY;
 		for(ISeq s = RT.seq(form); s != null; s = s.next())
 			{
 			IMapEntry e = (IMapEntry) s.first();
 			Expr k = analyze(context == C.EVAL ? context : C.EXPRESSION, e.key());
 			Expr v = analyze(context == C.EVAL ? context : C.EXPRESSION, e.val());
 			keyvals = (IPersistentVector) keyvals.cons(k);
 			keyvals = (IPersistentVector) keyvals.cons(v);
+			if (k instanceof KeywordExpr || v instanceof KeywordExpr)
+				templateable = true;
 			if(k instanceof LiteralExpr)
 				{
 				Object kval = k.eval();
 				if (constantKeys.contains(kval))
 					allConstantKeysUnique = false;
 				else
 					constantKeys = (IPersistentSet)constantKeys.cons(kval);
 				}
 			else
 				keysConstant = false;
 			if(!(v instanceof LiteralExpr))
 				valsConstant = false;
 			}
 
-		Expr ret = new MapExpr(keyvals);
 		if(form instanceof IObj && ((IObj) form).meta() != null)
-			return new MetaExpr(ret, MapExpr
+			return new MetaExpr(new MapExpr(keyvals, false), MapExpr
 					.parse(context == C.EVAL ? context : C.EXPRESSION, ((IObj) form).meta()));
-		else if(keysConstant)
-			{
+		else if(keysConstant) {
 			// TBD: Add more detail to exception thrown below.
-			if(!allConstantKeysUnique)
+			if (!allConstantKeysUnique)
 				throw new IllegalArgumentException("Duplicate constant keys in map");
-			if(valsConstant)
-				{
+			if (valsConstant) {
 				IPersistentMap m = PersistentArrayMap.EMPTY;
-				for(int i=0;i<keyvals.length();i+= 2)
-					{
-					m = m.assoc(((LiteralExpr)keyvals.nth(i)).val(), ((LiteralExpr)keyvals.nth(i+1)).val());
-					}
+				for (int i = 0; i < keyvals.length(); i += 2) {
+					m = m.assoc(((LiteralExpr) keyvals.nth(i)).val(), ((LiteralExpr) keyvals.nth(i + 1)).val());
+				}
 //				System.err.println("Constant: " + m);
 				return new ConstantExpr(m);
-				}
-			else
-				return ret;
 			}
-		else
-			return ret;
+
+		}
+		return new MapExpr(keyvals, keysConstant, templateable);
 	}
 }
 
 public static class SetExpr implements Expr{
 	public final IPersistentVector keys;
 	final static Method setMethod = Method.getMethod("clojure.lang.IPersistentSet set(Object[])");
 
 
 	public SetExpr(IPersistentVector keys){
 		this.keys = keys;
 	}
 
 	public Object eval() {
 		Object[] ret = new Object[keys.count()];
 		for(int i = 0; i < keys.count(); i++)