code: plan9front

Info  •  Files  •  Log

git/query: implement range using paint()

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.

--- a/sys/src/cmd/git/ref.c

+++ b/sys/src/cmd/git/ref.c

@@ -13,6 +13,12 @@

 	Skip,

 };

+enum {

+	Lca,

+	Twixt,

+	Range,

+};

+

 struct Eval {

 	char	*str;

 	char	*p;

@@ -102,18 +108,20 @@

 }

 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 @@

 				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 @@

 		}

 		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 @@

 			*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,6 +229,20 @@

 				(*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);

@@ -221,8 +249,9 @@

 	osclear(&skip);

 	return 0;

 error:

-	dprint(1, "twixt error: %r\n");

+	dprint(1, "paint error: %r\n");

 	free(objq.heap);

+	free(range);

 	return -1;

 }

@@ -229,7 +258,7 @@

 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 @@

 	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 @@

 	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);

@@ -285,33 +314,10 @@

 }

 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 @@

 		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