isa-based multimethods, a la carte hierarchies

3 files changed, 86 insertions, 28 deletions

diff --git a/src/jvm/clojure/lang/LispReader.java b/src/jvm/clojure/lang/LispReader.java
index 17dd8479..cc11603a 100644
--- a/src/jvm/clojure/lang/LispReader.java
+++ b/src/jvm/clojure/lang/LispReader.java
@@ -40,7 +40,7 @@ static Symbol DEREF = Symbol.create("clojure", "deref");
 static IFn[] macros = new IFn[256];

 static IFn[] dispatchMacros = new IFn[256];

 //static Pattern symbolPat = Pattern.compile("[:]?([\\D&&[^:/]][^:/]*/)?[\\D&&[^:/]][^:/]*");

-static Pattern symbolPat = Pattern.compile("[:]?([\\D&&[^:/]].*/)?([\\D&&[^:/]][^/]*)");

+static Pattern symbolPat = Pattern.compile("[:]?([\\D&&[^/]].*/)?([\\D&&[^/]][^/]*)");

 //static Pattern varPat = Pattern.compile("([\\D&&[^:\\.]][^:\\.]*):([\\D&&[^:\\.]][^:\\.]*)");

 //static Pattern intPat = Pattern.compile("[-+]?[0-9]+\\.?");

 static Pattern intPat =

@@ -275,8 +275,13 @@ private static Object matchSymbol(String s){
 		String name = m.group(2);

 		if(ns != null && ns.endsWith(":/")

 		   || name.endsWith(":")

-		   || s.contains("::"))

+		   || s.indexOf("::", 1) != -1)

 			return null;

+		if(s.startsWith("::"))

+			{

+			//auto-resolving keyword

+			return Keyword.intern(Compiler.resolveSymbol(Symbol.intern(s.substring(2))));

+			}

 		boolean isKeyword = s.charAt(0) == ':';

 		Symbol sym = Symbol.intern(s.substring(isKeyword ? 1 : 0));

 		if(isKeyword)

diff --git a/src/jvm/clojure/lang/MultiFn.java b/src/jvm/clojure/lang/MultiFn.java
index f5c09c12..e956b761 100644
--- a/src/jvm/clojure/lang/MultiFn.java
+++ b/src/jvm/clojure/lang/MultiFn.java
@@ -12,48 +12,93 @@
 
 package clojure.lang;
 
+import java.util.Map;
+
 public class MultiFn extends AFn{
 final public IFn dispatchFn;
 final public Object defaultDispatchVal;
-final public IPersistentMap methodTable;
+IPersistentMap methodTable;
+IPersistentMap methodCache;
+Object cachedHierarchy;
+
+static final Var assoc = RT.var("clojure", "assoc");
+static final Var dissoc = RT.var("clojure", "dissoc");
+static final Var isa = RT.var("clojure", "isa?");
+static final Var hierarchy = RT.var("clojure", "global-hierarchy");
 
-public MultiFn(IFn dispatchFn, Object defaultDispatchVal){
+public MultiFn(IFn dispatchFn, Object defaultDispatchVal) throws Exception{
 	this.dispatchFn = dispatchFn;
 	this.defaultDispatchVal = defaultDispatchVal;
 	this.methodTable = PersistentHashMap.EMPTY;
+	this.methodCache = methodTable;
+	cachedHierarchy = null;
 }
 
-public MultiFn assoc(Object dispatchVal, IFn method){
-	return new MultiFn(meta(), dispatchFn, defaultDispatchVal, methodTable.assoc(dispatchVal, method));
-}
-
-
-public MultiFn dissoc(Object dispatchVal) throws Exception{
-	return new MultiFn(meta(), dispatchFn,  defaultDispatchVal, methodTable.without(dispatchVal));
+synchronized public MultiFn addMethod(Object dispatchVal, IFn method) throws Exception{
+	methodTable = methodTable.assoc(dispatchVal, method);
+	resetCache();
+	return this;
 }
 
-public Obj withMeta(IPersistentMap meta){
-	if(meta == meta())
-		return this;
-	return new MultiFn(meta, dispatchFn, defaultDispatchVal, methodTable);
+synchronized public MultiFn removeMethod(Object dispatchVal) throws Exception{
+	methodTable = methodTable.without(dispatchVal);
+	resetCache();
+	return this;
 }
 
-private MultiFn(IPersistentMap meta, IFn dispatchFn, Object defaultDispatchVal, IPersistentMap dispatchTable){
-	super(meta);
-	this.dispatchFn = dispatchFn;
-	this.defaultDispatchVal = defaultDispatchVal;
-	this.methodTable = dispatchTable;
+private IPersistentMap resetCache(){
+	methodCache = methodTable;
+	cachedHierarchy = hierarchy.get();
+	return methodCache;
 }
 
-private IFn getFn(Object dispatchVal) throws Exception{
-	IFn targetFn = (IFn) methodTable.valAt(dispatchVal);
-	if(targetFn == null)
-	    targetFn = (IFn) methodTable.valAt(defaultDispatchVal);
+synchronized private IFn getFn(Object dispatchVal) throws Exception{
+	if(cachedHierarchy != hierarchy.get())
+		resetCache();
+	IFn targetFn = (IFn) methodCache.valAt(dispatchVal);
+	if(targetFn != null)
+		return targetFn;
+	targetFn = findAndCacheBestMethod(dispatchVal);
+	if(targetFn != null)
+		return targetFn;
+	targetFn = (IFn) methodTable.valAt(defaultDispatchVal);
 	if(targetFn == null)
 		throw new IllegalArgumentException(String.format("No method for dispatch value: %s", dispatchVal));
 	return targetFn;
 }
 
+private IFn findAndCacheBestMethod(Object dispatchVal) throws Exception{
+	Map.Entry bestEntry = null;
+	for(Object o : methodTable)
+		{
+		Map.Entry e = (Map.Entry) o;
+		if(RT.booleanCast(isa.invoke(dispatchVal, e.getKey())))
+			{
+			if(bestEntry == null || RT.booleanCast(isa.invoke(e.getKey(), bestEntry.getKey())))
+				bestEntry = e;
+			if(!RT.booleanCast(isa.invoke(bestEntry.getKey(), e.getKey())))
+				throw new IllegalArgumentException(
+						String.format("Multiple methods match dispatch value: %s -> %s and %s",
+						              dispatchVal, e.getKey(), bestEntry.getKey()));
+			}
+		}
+	if(bestEntry == null)
+		throw new IllegalArgumentException(String.format("No method for dispatch value: %s", dispatchVal));
+
+	//ensure basis has stayed stable throughout, else redo
+	if(cachedHierarchy == hierarchy.get())
+		{
+		//place in cache
+		methodCache = methodCache.assoc(dispatchVal, bestEntry.getValue());
+		return (IFn) bestEntry.getValue();
+		}
+	else
+		{
+		resetCache();
+		return findAndCacheBestMethod(dispatchVal);
+		}
+}
+
 public Object invoke() throws Exception{
 	return getFn(dispatchFn.invoke()).invoke();
 }
diff --git a/src/jvm/clojure/lang/Var.java b/src/jvm/clojure/lang/Var.java
index f7d42c22..fe6b8b9d 100644
--- a/src/jvm/clojure/lang/Var.java
+++ b/src/jvm/clojure/lang/Var.java
@@ -131,7 +131,7 @@ final public Object get(){
 
 public void setValidator(IFn vf){
 	if(isBound())
-		validate(vf,getRoot());
+		validate(vf, getRoot());
 	validator = vf;
 }
 
@@ -145,7 +145,8 @@ public Object alter(IFn fn, ISeq args) throws Exception{
 }
 
 void validate(IFn vf, Object val){
-	try{
+	try
+		{
 		if(vf != null)
 			vf.invoke(val);
 		}
@@ -156,7 +157,7 @@ void validate(IFn vf, Object val){
 }
 
 public Object set(Object val){
-	validate(getValidator(),val);
+	validate(getValidator(), val);
 	Box b = getThreadBinding();
 	if(b != null)
 		return (b.val = val);
@@ -227,8 +228,15 @@ synchronized public void unbindRoot(){
 
 synchronized public void commuteRoot(IFn fn) throws Exception{
 	Object newRoot = fn.invoke(root);
-	validate(getValidator(),newRoot);
+	validate(getValidator(), newRoot);
+	this.root = newRoot;
+}
+
+synchronized public Object alterRoot(IFn fn, ISeq args) throws Exception{
+	Object newRoot = fn.applyTo(RT.cons(root, args));
+	validate(getValidator(), newRoot);
 	this.root = newRoot;
+	return newRoot;
 }
 
 public static void pushThreadBindings(Associative bindings){