[9front] [PATCH] git/query: implement range using paint()

[Michael Forney <mforney@mforney.org>]

The current range algorithm does not work correctly when merge
commits are involved with an ancestor of the base commit.

For example, consider the graph

   b
 ↙   ↖
a      d ← e ← f
 ↖   ↙
   c

where b is d's first parent, and c is d's second parent.

This graph is symmetrical, so we should get the same results for
b..f and c..d (modulo the symmetry), but currently range() returns
[d] for b..f and [d, e, f] for c..f. In the first case, we traverse
to b, our base, then unwind to d and add [d] to our results. Then,
we traverse [c, a], but don't find b this time, so unwind back to
f. In the second case, we traverse all the way to a through b,
unwind to d, then find our base, c, and unwind back to f and add
[d, e, f] to our results.

The problem here is that the determining factor for whether a commit
is pushed during unwinding is whether the *last* parent reached the
base commit, when it should be if *any* parent reached the base
commit.

Also, when a is not an ancestor of b, the current algorithm traverses
the entire graph then returns an empty list, despite git's behavior
and git9's documentation ("Between is defined as the set of all
commits which are reachable from b but not reachable from a"). For
the above example, we'd expect that b..f contain c, since c is not
reachable from b.

Range is almost identical to findtwixt, so to fix this we can reuse
the same paint() algorithm for both operations. The only difference
is that we want results in traversal order (rather than an arbitrary
ordering). Add a third mode to paint() to save 'keep' commits in
an array in the order we reach them, then return the non-dropped
and non-skipped commits, preserving that order.
---
The main motivation for this patch is to make a..b work as expected
when a is not an ancestor of b. This type of query is very useful
to answer questions like "what commits do I have that upstream is
missing?" (origin/front..HEAD) or "what commits does upstream have
that I'm missing?" (HEAD..origin/front) when your branch has diverged
from upstream.

Of course, this is possible using the lca feature of ref syntax
(origin/front HEAD @ .. HEAD), but my investigation revealed that
there are other cases that are broken, even if a is an ancestor of
b.

I have some regress tests ready to commit once this is fixed.

 sys/src/cmd/git/ref.c | 120 ++++++++++++++++--------------------------
 1 file changed, 45 insertions(+), 75 deletions(-)

diff --git a/sys/src/cmd/git/ref.c b/sys/src/cmd/git/ref.c
index 11eea7a077..bf798e2664 100644
--- a/sys/src/cmd/git/ref.c
+++ b/sys/src/cmd/git/ref.c
@@ -13,6 +13,12 @@ enum {
 	Skip,
 };
 
+enum {
+	Lca,
+	Twixt,
+	Range,
+};
+
 struct Eval {
 	char	*str;
 	char	*p;
@@ -102,18 +108,20 @@ take(Eval *ev, char *m)
 }
 
 static int
-paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int ancestor)
+paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int mode)
 {
 	Qelt e;
 	Objq objq;
 	Objset keep, drop, skip;
-	Object *o, *c;
-	int i, nskip;
+	Object *o, *c, **range;
+	int i, nskip, nrange;
 
 	osinit(&keep);
 	osinit(&drop);
 	osinit(&skip);
 	qinit(&objq);
+	range = nil;
+	nrange = 0;
 	nskip = 0;
 
 	for(i = 0; i < nhead; i++){
@@ -158,6 +166,10 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in
 				continue;
 			if(oshas(&drop, e.o->hash))
 				e.color = Skip;
+			else if(mode == Range){
+				range = earealloc(range, nrange+1, sizeof(Object*));
+				range[nrange++] = e.o;
+			}
 			osadd(&keep, e.o);
 			break;
 		case Drop:
@@ -188,7 +200,8 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in
 		}
 		unref(o);
 	}
-	if(ancestor){
+	switch(mode){
+	case Lca:
 		dprint(1, "found ancestor\n");
 		o = nil;
 		for(i = 0; i < keep.sz; i++){
@@ -204,7 +217,8 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in
 			*res = eamalloc(1, sizeof(Object*));
 			(*res)[0] = o;
 		}
-	}else{
+		break;
+	case Twixt:
 		dprint(1, "found twixt\n");
 		*res = eamalloc(keep.nobj, sizeof(Object*));
 		*nres = 0;
@@ -215,21 +229,36 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in
 				(*nres)++;
 			}
 		}
+		break;
+	case Range:
+		dprint(1, "found range\n");
+		*res = eamalloc(nrange, sizeof(Object*));
+		*nres = 0;
+		for(i = nrange - 1; i >= 0; i--){
+			o = range[i];
+			if(!oshas(&drop, o->hash) && !oshas(&skip, o->hash)){
+				(*res)[*nres] = o;
+				(*nres)++;
+			}
+		}
+		free(range);
+		break;
 	}
 	osclear(&keep);
 	osclear(&drop);
 	osclear(&skip);
 	return 0;
 error:
-	dprint(1, "twixt error: %r\n");
+	dprint(1, "paint error: %r\n");
 	free(objq.heap);
+	free(range);
 	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);
+	return paint(head, nhead, tail, ntail, res, nres, Twixt);
 }
 
 Object*
@@ -238,7 +267,7 @@ ancestor(Object *a, Object *b)
 	Object **o, *r;
 	int n;
 
-	if(paint(&a->hash, 1, &b->hash, 1, &o, &n, 1) == -1 || n == 0)
+	if(paint(&a->hash, 1, &b->hash, 1, &o, &n, Lca) == -1 || n == 0)
 		return nil;
 	r = ref(o[0]);
 	free(o);
@@ -258,7 +287,7 @@ lca(Eval *ev)
 	n = 0;
 	b = pop(ev);
 	a = pop(ev);
-	paint(&a->hash, 1, &b->hash, 1, &o, &n, 1);
+	paint(&a->hash, 1, &b->hash, 1, &o, &n, Lca);
 	if(n == 0)
 		return -1;
 	push(ev, *o);
@@ -284,34 +313,11 @@ parent(Eval *ev)
 	return 0;
 }
 
-static int
-unwind(Eval *ev, Object **obj, int *idx, int nobj, Object **p, Objset *set, int keep)
-{
-	int i;
-
-	for(i = nobj; i >= 0; i--){
-		idx[i]++;
-		if(keep && !oshas(set, obj[i]->hash)){
-			push(ev, obj[i]);
-			osadd(set, obj[i]);
-		}else{
-			osadd(set, obj[i]);
-		}
-		if(idx[i] < obj[i]->commit->nparent){
-			*p = obj[i];
-			return i;
-		}
-		unref(obj[i]);
-	}
-	return -1;
-}
-
 static int
 range(Eval *ev)
 {
-	Object *a, *b, *p, *q, **all;
-	int nall, *idx;
-	Objset keep, skip;
+	Object *a, *b, **o;
+	int i, n;
 
 	b = pop(ev);
 	a = pop(ev);
@@ -324,48 +330,12 @@ range(Eval *ev)
 		return -1;
 	}
 
-	p = b;
-	all = nil;
-	idx = nil;
-	nall = 0;
-	osinit(&keep);
-	osinit(&skip);
-	osadd(&keep, a);
-	while(1){
-		all = earealloc(all, (nall + 1), sizeof(Object*));
-		idx = earealloc(idx, (nall + 1), sizeof(int));
-		all[nall] = p;
-		idx[nall] = 0;
-		if(p == a || p->commit->nparent == 0 && a == &zcommit){
-			if((nall = unwind(ev, all, idx, nall, &p, &keep, 1)) == -1)
-				break;
-		}else if(p->commit->nparent == 0){
-			if((nall = unwind(ev, all, idx, nall, &p, &skip, 0)) == -1)
-				break;
-		}else if(oshas(&keep, p->hash)){
-			if((nall = unwind(ev, all, idx, nall, &p, &keep, 1)) == -1)
-				break;
-		}else if(oshas(&skip, p->hash))
-			if((nall = unwind(ev, all, idx, nall, &p, &skip, 0)) == -1)
-				break;
-		if(p->commit->nparent == 0)
-			break;
-		if((q = readobject(p->commit->parent[idx[nall]])) == nil){
-			werrstr("bad commit %H", p->commit->parent[idx[nall]]);
-			goto error;
-		}
-		if(q->type != GCommit){
-			werrstr("not commit: %H", q->hash);
-			goto error;
-		}
-		p = q;
-		nall++;
-	}
-	free(all);
+	if(paint(&b->hash, 1, &a->hash, 1, &o, &n, Range) == -1)
+		return -1;
+	for(i = 0; i < n; i++)
+		push(ev, o[i]);
+	free(o);
 	return 0;
-error:
-	free(all);
-	return -1;
 }
 
 int
-- 
2.34.1