Re: [9front] git/query: improve LCA results

[ori@eigenstate.org]

Quoth ori@eigenstate.org:
> Since bugs here can lead to issues sysupdating, I'd
> like some extra eyeballs, testing, and review on this
> before I commit.

A slightly improved version. The `haskeep()` optimization
to break out early could cause us to leave before we'd
found the best node.

diff e6f0abc25e4e237fff97ef9bdd1dc98ee519def8 uncommitted
--- a/sys/src/cmd/git/ref.c
+++ b/sys/src/cmd/git/ref.c
@@ -22,19 +22,19 @@
 	int	stksz;
 };
 
-struct XObject {
-	Object	*obj;
-	Object	*mark;
-	XObject	*queue;
-	XObject	*next;
-};
-
 struct Objq {
 	Objq	*next;
 	Object	*o;
 	int	color;
+	int	dist;
 };
 
+static char *colors[] = {
+[Keep] "keep",
+[Drop] "drop",
+[Blank] "blank",
+};
+
 static Object zcommit = {
 	.type=GCommit
 };
@@ -128,110 +128,6 @@
 	return 1;
 }
 
-XObject*
-hnode(XObject *ht[], Object *o)
-{
-	XObject *h;
-	int	hh;
-
-	hh = o->hash.h[0] & 0xff;
-	for(h = ht[hh]; h; h = h->next)
-		if(hasheq(&o->hash, &h->obj->hash))
-			return h;
-
-	h = emalloc(sizeof(*h));
-	h->obj = o;
-	h->mark = nil;
-	h->queue = nil;
-	h->next = ht[hh];
-	ht[hh] = h;
-	return h;
-}
-
-Object*
-ancestor(Object *a, Object *b)
-{
-	Object *o, *p, *r;
-	XObject *ht[256];
-	XObject *h, *q, *q1, *q2;
-	int i;
-
-	if(a == b)
-		return a;
-	if(a == nil || b == nil)
-		return nil;
-	r = nil;
-	memset(ht, 0, sizeof(ht));
-	q1 = nil;
-
-	h = hnode(ht, a);
-	h->mark = a;
-	h->queue = q1;
-	q1 = h;
-
-	h = hnode(ht, b);
-	h->mark = b;
-	h->queue = q1;
-	q1 = h;
-
-	while(1){
-		q2 = nil;
-		while(q = q1){
-			q1 = q->queue;
-			q->queue = nil;
-			o = q->obj;
-			for(i = 0; i < o->commit->nparent; i++){
-				p = readobject(o->commit->parent[i]);
-				if(p == nil)
-					goto err;
-				h = hnode(ht, p);
-				if(h->mark != nil){
-					if(h->mark != q->mark){
-						r = h->obj;
-						goto done;
-					}
-				} else {
-					h->mark = q->mark;
-					h->queue = q2;
-					q2 = h;
-				}
-			}
-		}
-		if(q2 == nil){
-err:
-			werrstr("no common ancestor");
-			break;
-		}
-		q1 = q2;
-	}
-done:
-	for(i=0; i<nelem(ht); i++){
-		while(h = ht[i]){
-			ht[i] = h->next;
-			free(h);
-		}
-	}
-	return r;
-}
-
-int
-lca(Eval *ev)
-{
-	Object *a, *b, *o;
-
-	if(ev->nstk < 2){
-		werrstr("ancestor needs 2 objects");
-		return -1;
-	}
-	a = pop(ev);
-	b = pop(ev);
-	o = ancestor(a, b);
-	if(o == nil)
-		return -1;
-	push(ev, o);
-	return 0;
-}
-
 static int
 repaint(Objset *keep, Objset *drop, Object *o)
 {
@@ -249,29 +145,48 @@
 	for(i = 0; i < o->commit->nparent; i++){
 		if((p = readobject(o->commit->parent[i])) == nil)
 			return -1;
+		if(oshas(drop, p->hash))
+			goto next;
 		if(repaint(keep, drop, p) == -1)
 			return -1;
+next:
 		unref(p);
 	}
 	return 0;
 }
 
-int
-findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)
+static int
+bestpick(Hash *head, int nhead, Hash *tail, int ntail, Objq *q, int dist)
 {
+	int i;
+
+	if(q->dist < dist)
+		return 1;
+	for(i = 0; i < nhead; i++)
+		if(hasheq(&head[i], &q->o->hash))
+			return 1;
+	for(i = 0; i < ntail; i++)
+		if(hasheq(&tail[i], &q->o->hash))
+			return 1;
+	return 0;
+}
+
+static int
+paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int ancestor)
+{
 	Objq *q, *e, *n, **p;
 	Objset keep, drop;
-	Object *o, *c;
-	int i, ncolor;
+	Object *o, *c, *best;
+	int i, dist, ncolor;
 
 	e = nil;
 	q = nil;
 	p = &q;
+	best = nil;
+	dist = 1<<30;
 	osinit(&keep);
 	osinit(&drop);
 	for(i = 0; i < nhead; i++){
-		if(hasheq(&head[i], &Zhash))
-			continue;
 		if((o = readobject(head[i])) == nil){
 			fprint(2, "warning: %H does not point at commit\n", o->hash);
 			werrstr("read head %H: %r", head[i]);
@@ -282,17 +197,16 @@
 			unref(o);
 			continue;
 		}
-		dprint(1, "twixt init: keep %H\n", o->hash);
+		dprint(1, "init: keep %H\n", o->hash);
 		e = emalloc(sizeof(Objq));
 		e->o = o;
 		e->color = Keep;
+		e->dist = 0;
 		*p = e;
 		p = &e->next;
 		unref(o);
 	}		
 	for(i = 0; i < ntail; i++){
-		if(hasheq(&tail[i], &Zhash))
-			continue;
 		if((o = readobject(tail[i])) == nil){
 			werrstr("read tail %H: %r", tail[i]);
 			return -1;
@@ -306,6 +220,7 @@
 		e = emalloc(sizeof(Objq));
 		e->o = o;
 		e->color = Drop;
+		e->dist = 0;
 		*p = e;
 		p = &e->next;
 		unref(o);
@@ -319,18 +234,37 @@
 			ncolor = Keep;
 		else
 			ncolor = Blank;
-		if(ncolor == Drop || ncolor == Keep && q->color == Keep)
+		dprint(2, "visit: ncolor=%s, qcolor=%s %H\n",
+			colors[ncolor], colors[q->color], q->o->hash);
+		if(ncolor == Keep && q->color == Keep){
 			goto next;
-		if(ncolor == Keep && q->color == Drop){
+		}else if(ncolor == Drop){
+			dprint(2, "consider: best %H => %H (dist: %d => %d)\n",
+				best ? best->hash : Zhash, q->o->hash,
+				dist, q->dist);
+			if(q->color == Keep && bestpick(head, nhead, tail, ntail, q, dist)){
+				dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n",
+					best ? best->hash : Zhash, q->o->hash,
+					dist, q->dist);
+				best = q->o;
+				dist = q->dist;
+			}
+		}else if(ncolor == Keep && q->color == Drop){
+			dprint(2, "consider: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+			if(bestpick(head, nhead, tail, ntail, q, dist)){
+				dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist);
+				best = q->o;
+				dist = q->dist;
+			}
 			if(repaint(&keep, &drop, q->o) == -1)
 				goto error;
 		}else if (ncolor == Blank) {
-			dprint(2, "visit: %s %H\n", q->color == Keep ? "keep" : "drop", q->o->hash);
 			if(q->color == Keep)
 				osadd(&keep, q->o);
 			else
 				osadd(&drop, q->o);
-			for(i = 0; i < q->o->commit->nparent; i++){
+			o = readobject(q->o->hash);
+			for(i = 0; i < o->commit->nparent; i++){
 				if((c = readobject(q->o->commit->parent[i])) == nil)
 					goto error;
 				if(c->type != GCommit){
@@ -338,9 +272,10 @@
 					unref(c);
 					continue;
 				}
-				dprint(2, "enqueue: %s %H\n", q->color == Keep ? "keep" : "drop", c->hash);
+				dprint(2, "enqueue: %s %H\n", colors[q->color], c->hash);
 				n = emalloc(sizeof(Objq));
 				n->color = q->color;
+				n->dist = q->dist + 1;
 				n->next = nil;
 				n->o = c;
 				e->next = n;
@@ -347,8 +282,9 @@
 				e = n;
 				unref(c);
 			}
+			unref(o);
 		}else{
-			sysfatal("oops");
+			sysfatal("oops: ncolor==%d && qcolor==%d", ncolor, q->color);
 		}
 next:
 		n = q->next;
@@ -355,13 +291,24 @@
 		free(q);
 		q = n;
 	}
-	*res = eamalloc(keep.nobj, sizeof(Object*));
-	*nres = 0;
-	for(i = 0; i < keep.sz; i++){
-		if(keep.obj[i] != nil && !oshas(&drop, keep.obj[i]->hash)){
-			(*res)[*nres] = keep.obj[i];
-			(*nres)++;
+	if(ancestor){
+		if(best == nil){
+			*nres = 0;
+			*res = nil;
+		}else{
+			*nres = 1;
+			*res = eamalloc(1, sizeof(Object*));
+			(*res)[0] = best;
 		}
+	}else{
+		*res = eamalloc(keep.nobj, sizeof(Object*));
+		*nres = 0;
+		for(i = 0; i < keep.sz; i++){
+			if(keep.obj[i] != nil && !oshas(&drop, keep.obj[i]->hash)){
+				(*res)[*nres] = keep.obj[i];
+				(*nres)++;
+			}
+		}
 	}
 	osclear(&keep);
 	osclear(&drop);
@@ -372,6 +319,46 @@
 		free(q);
 	}
 	return -1;
+}
+
+int
+findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)
+{
+	return paint(head, nhead, tail, ntail, res, nres, 0);
+}
+
+Object*
+ancestor(Object *a, Object *b)
+{
+	Object **o, *r;
+	int n;
+
+	if(paint(&a->hash, 1, &b->hash, 1, &o, &n, 1) == -1 || n == 0)
+		return nil;
+	r = o[0];
+	free(o);
+	return r;
+}
+
+int
+lca(Eval *ev)
+{
+	Object *a, *b, **o;
+	int n;
+
+	if(ev->nstk < 2){
+		werrstr("ancestor needs 2 objects");
+		return -1;
+	}
+	n = 0;
+	a = pop(ev);
+	b = pop(ev);
+	paint(&a->hash, 1, &b->hash, 1, &o, &n, 1);
+	if(n == 0)
+		return -1;
+	push(ev, *o);
+	free(o);
+	return 0;
 }
 
 static int