From 3155a888b34d83e56ff5f1711c17c48e2e567e8f Mon Sep 17 00:00:00 2001
From: Andy Fingerhut <andy_fingerhut@alum.wustl.edu>
Date: Sun, 9 Sep 2012 01:01:38 -0700
Subject: [PATCH] CLJ-1065: Only do duplicate map key checks at compile time
 if all keys constant

Also changes several calls to RT.map to RT.mapUniqueKeys, to save a
little bit of unnecessary duplicate key checking there.  Many more
such calls could be modified, but I only did so for those that had
more than a few keys/val pairs.
---
 src/jvm/clojure/lang/Compiler.java |   76 ++++++++++++++++++++++++++++--------
 src/jvm/clojure/lang/RT.java       |   12 +++++-
 2 files changed, 69 insertions(+), 19 deletions(-)

diff --git a/src/jvm/clojure/lang/Compiler.java b/src/jvm/clojure/lang/Compiler.java
index e2146a6..2e094a7 100644
--- a/src/jvm/clojure/lang/Compiler.java
+++ b/src/jvm/clojure/lang/Compiler.java
@@ -2788,6 +2788,7 @@ public static class ListExpr implements Expr{
 public static class MapExpr implements Expr{
 	public final IPersistentVector keyvals;
 	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){
@@ -2802,8 +2803,28 @@ public static class MapExpr implements Expr{
 	}
 
 	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;
+			}
 		MethodExpr.emitArgsAsArray(keyvals, objx, gen);
-		gen.invokeStatic(RT_TYPE, mapMethod);
+		if((allKeysConstant && allConstantKeysUnique) || (keyvals.count() <= 2))
+			gen.invokeStatic(RT_TYPE, mapUniqueKeysMethod);
+		else
+			gen.invokeStatic(RT_TYPE, mapMethod);
 		if(context == C.STATEMENT)
 			gen.pop();
 	}
@@ -2819,7 +2840,10 @@ public static class MapExpr implements Expr{
 
 	static public Expr parse(C context, IPersistentMap form) {
 		IPersistentVector keyvals = PersistentVector.EMPTY;
-		boolean constant = true;
+		boolean keysConstant = true;
+		boolean valsConstant = true;
+		boolean allConstantKeysUnique = true;
+		IPersistentSet constantKeys = PersistentHashSet.EMPTY;
 		for(ISeq s = RT.seq(form); s != null; s = s.next())
 			{
 			IMapEntry e = (IMapEntry) s.first();
@@ -2827,23 +2851,41 @@ public static class MapExpr implements Expr{
 			Expr v = analyze(context == C.EVAL ? context : C.EXPRESSION, e.val());
 			keyvals = (IPersistentVector) keyvals.cons(k);
 			keyvals = (IPersistentVector) keyvals.cons(v);
-			if(!(k instanceof LiteralExpr && v instanceof LiteralExpr))
-				constant = false;
+			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
 					.parse(context == C.EVAL ? context : C.EXPRESSION, ((IObj) form).meta()));
-		else if(constant)
+		else if(keysConstant)
 			{
-			IPersistentMap m = PersistentHashMap.EMPTY;
-			for(int i=0;i<keyvals.length();i+= 2)
+			// TBD: Add more detail to exception thrown below.
+			if(!allConstantKeysUnique)
+				throw new IllegalArgumentException("Duplicate constant keys in map");
+			if(valsConstant)
 				{
-				m = m.assoc(((LiteralExpr)keyvals.nth(i)).val(), ((LiteralExpr)keyvals.nth(i+1)).val());
+				IPersistentMap m = PersistentHashMap.EMPTY;
+				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);
 				}
-//			System.err.println("Constant: " + m);
-			return new ConstantExpr(m);
+			else
+				return ret;
 			}
 		else
 			return ret;
@@ -3643,7 +3685,7 @@ static public class FnExpr extends ObjExpr{
 		try
 			{
 			Var.pushThreadBindings(
-					RT.map(CONSTANTS, PersistentVector.EMPTY,
+					RT.mapUniqueKeys(CONSTANTS, PersistentVector.EMPTY,
 					       CONSTANT_IDS, new IdentityHashMap(),
 					       KEYWORDS, PersistentHashMap.EMPTY,
 					       VARS, PersistentHashMap.EMPTY,
@@ -4948,7 +4990,7 @@ public static class FnMethod extends ObjMethod{
 			if(pnode == null)
 				pnode = new PathNode(PATHTYPE.PATH,null);
 			Var.pushThreadBindings(
-					RT.map(
+					RT.mapUniqueKeys(
 							METHOD, method,
 							LOCAL_ENV, LOCAL_ENV.deref(),
 							LOOP_LOCALS, null,
@@ -6929,7 +6971,7 @@ public static Object load(Reader rdr, String sourcePath, String sourceName) {
 			(rdr instanceof LineNumberingPushbackReader) ? (LineNumberingPushbackReader) rdr :
 			new LineNumberingPushbackReader(rdr);
 	Var.pushThreadBindings(
-			RT.map(LOADER, RT.makeClassLoader(),
+			RT.mapUniqueKeys(LOADER, RT.makeClassLoader(),
 			       SOURCE_PATH, sourcePath,
 			       SOURCE, sourceName,
 			       METHOD, null,
@@ -7052,7 +7094,7 @@ public static Object compile(Reader rdr, String sourcePath, String sourceName) t
 			(rdr instanceof LineNumberingPushbackReader) ? (LineNumberingPushbackReader) rdr :
 			new LineNumberingPushbackReader(rdr);
 	Var.pushThreadBindings(
-			RT.map(SOURCE_PATH, sourcePath,
+			RT.mapUniqueKeys(SOURCE_PATH, sourcePath,
 			       SOURCE, sourceName,
 			       METHOD, null,
 			       LOCAL_ENV, null,
@@ -7322,7 +7364,7 @@ static public class NewInstanceExpr extends ObjExpr{
 		try
 			{
 			Var.pushThreadBindings(
-					RT.map(CONSTANTS, PersistentVector.EMPTY,
+					RT.mapUniqueKeys(CONSTANTS, PersistentVector.EMPTY,
 					       CONSTANT_IDS, new IdentityHashMap(),
 					       KEYWORDS, PersistentHashMap.EMPTY,
 					       VARS, PersistentHashMap.EMPTY,
@@ -7332,7 +7374,7 @@ static public class NewInstanceExpr extends ObjExpr{
                                                NO_RECUR, null));
 			if(ret.isDeftype())
 				{
-				Var.pushThreadBindings(RT.map(METHOD, null,
+				Var.pushThreadBindings(RT.mapUniqueKeys(METHOD, null,
 				                              LOCAL_ENV, ret.fields
 						, COMPILE_STUB_SYM, Symbol.intern(null, tagName)
 						, COMPILE_STUB_CLASS, stub));
@@ -7705,7 +7747,7 @@ public static class NewInstanceMethod extends ObjMethod{
 			//register as the current method and set up a new env frame
             PathNode pnode =  new PathNode(PATHTYPE.PATH, (PathNode) CLEAR_PATH.get());
 			Var.pushThreadBindings(
-					RT.map(
+					RT.mapUniqueKeys(
 							METHOD, method,
 							LOCAL_ENV, LOCAL_ENV.deref(),
 							LOOP_LOCALS, null,
diff --git a/src/jvm/clojure/lang/RT.java b/src/jvm/clojure/lang/RT.java
index 9769acb..79caeff 100644
--- a/src/jvm/clojure/lang/RT.java
+++ b/src/jvm/clojure/lang/RT.java
@@ -413,7 +413,7 @@ static public void load(String scriptbase, boolean failIfNotFound) throws IOExce
 	   || classURL == null) {
 		try {
 			Var.pushThreadBindings(
-					RT.map(CURRENT_NS, CURRENT_NS.deref(),
+					RT.mapUniqueKeys(CURRENT_NS, CURRENT_NS.deref(),
 					       WARN_ON_REFLECTION, WARN_ON_REFLECTION.deref()
 							,RT.UNCHECKED_MATH, RT.UNCHECKED_MATH.deref()));
 			loaded = (loadClassForName(scriptbase.replace('/', '.') + LOADER_SUFFIX) != null);
@@ -436,7 +436,7 @@ static void doInit() throws ClassNotFoundException, IOException{
 	load("clojure/core");
 
 	Var.pushThreadBindings(
-			RT.map(CURRENT_NS, CURRENT_NS.deref(),
+			RT.mapUniqueKeys(CURRENT_NS, CURRENT_NS.deref(),
 			       WARN_ON_REFLECTION, WARN_ON_REFLECTION.deref()
 					,RT.UNCHECKED_MATH, RT.UNCHECKED_MATH.deref()));
 	try {
@@ -1451,6 +1451,14 @@ static public IPersistentMap map(Object... init){
 	return PersistentHashMap.createWithCheck(init);
 }
 
+static public IPersistentMap mapUniqueKeys(Object... init){
+	if(init == null)
+		return PersistentArrayMap.EMPTY;
+	else if(init.length <= PersistentArrayMap.HASHTABLE_THRESHOLD)
+		return new PersistentArrayMap(init);
+	return PersistentHashMap.create(init);
+}
+
 static public IPersistentSet set(Object... init){
 	return PersistentHashSet.createWithCheck(init);
 }
-- 
1.7.10