shithub: plan9front

Info  •  Files  •  Log

git/query: fix spurious merge requests

Due to the way LCA is defined, a using a strict LCA
on a graph like this:

 <--a--b--c--d--e--f--g
     \               /
       +-----h-------

can lead to spurious requests to merge. This happens
because 'lca(b, g)' would return 'a', since it can be
reached in one step from 'b', and 2 steps from 'g', while
reaching 'b' from 'a' would be a longer path.

As a result, we need to implement an lca variant that
returns the starting node if one is reachable from the
other, even if it's already found the technically correct
least common ancestor.

This replaces our LCA algorithm with one based on the
painting we do while finding a twixt, making it give
the resutls we want.
git/query: fix spurious merge requests

Due to the way LCA is defined, a using a strict LCA
on a graph like this:

 <--a--b--c--d--e--f--g
     \               /
       +-----h-------

can lead to spurious requests to merge. This happens
because 'lca(b, g)' would return 'a', since it can be
reached in one step from 'b', and 2 steps from 'g', while
reaching 'b' from 'a' would be a longer path.

As a result, we need to implement an lca variant that
returns the starting node if one is reachable from the
other, even if it's already found the technically correct
least common ancestor.

This replaces our LCA algorithm with one based on the
painting we do while finding a twixt.

--- a/sys/src/cmd/git/git.h	Sat Sep 11 08:26:35 2021

+++ b/sys/src/cmd/git/git.h	Sat Sep 11 13:46:26 2021

@@ -18,6 +18,8 @@

 typedef struct Objlist	Objlist;

 typedef struct Dtab	Dtab;

 typedef struct Dblock	Dblock;

+typedef struct Objq	Objq;

+typedef struct Qelt	Qelt;

 enum {

 	Pathmax		= 512,

@@ -151,6 +153,20 @@

 	int	sz;

 };

+struct Qelt {

+	Object	*o;

+	vlong	mtime;

+	int	color;

+	int	dist;

+};

+

+struct Objq {

+	Qelt	*heap;

+	int	nheap;

+	int	heapsz;

+	int	nkeep;

+};

+

 struct Dtab {

 	Object	*o;

 	uchar	*base;

@@ -301,3 +317,9 @@

 int	readphase(Conn *);

 int	writephase(Conn *);

 void	closeconn(Conn *);

+

+/* queues */

+void	qinit(Objq*);

+void	qclear(Objq*);

+void	qput(Objq*, Object*, int, int);

+int	qpop(Objq*, Qelt*);

--- a/sys/src/cmd/git/log.c	Sat Sep 11 08:26:35 2021

+++ b/sys/src/cmd/git/log.c	Sat Sep 11 13:46:26 2021

@@ -15,10 +15,8 @@

 char	*commitid;

 int	shortlog;

-Object	**heap;

-int	nheap;

-int	heapsz;

 Objset	done;

+Objq	objq;

 Pfilt	*pathfilt;

 void

@@ -192,64 +190,10 @@

 }

 static void

-qput(Object *o)

-{

-	Object *p;

-	int i;

-

-	if(oshas(&done, o->hash))

-		return;

-	osadd(&done, o);

-	if(nheap == heapsz){

-		heapsz *= 2;

-		heap = earealloc(heap, heapsz, sizeof(Object*));

-	}

-	heap[nheap++] = o;

-	for(i = nheap - 1; i > 0; i = (i-1)/2){

-		o = heap[i];

-		p = heap[(i-1)/2];

-		if(o->commit->mtime < p->commit->mtime)

-			break;

-		heap[i] = p;

-		heap[(i-1)/2] = o;

-	}

-}

-

-static Object*

-qpop(void)

-{

-	Object *o, *t;

-	int i, l, r, m;

-

-	if(nheap == 0)

-		return nil;

-

-	i = 0;

-	o = heap[0];

-	t = heap[--nheap];

-	heap[0] = t;

-	while(1){

-		m = i;

-		l = 2*i+1;

-		r = 2*i+2;

-		if(l < nheap && heap[m]->commit->mtime < heap[l]->commit->mtime)

-			m = l;

-		if(r < nheap && heap[m]->commit->mtime < heap[r]->commit->mtime)

-			m = r;

-		else

-			break;

-		t = heap[m];

-		heap[m] = heap[i];

-		heap[i] = t;

-		i = m;

-	}

-	return o;

-}

-

-static void

 showcommits(char *c)

 {

 	Object *o, *p;

+	Qelt e;

 	int i;

 	Hash h;

@@ -259,18 +203,20 @@

 		sysfatal("resolve %s: %r", c);

 	if((o = readobject(h)) == nil)

 		sysfatal("load %H: %r", h);

-	heapsz = 8;

-	heap = eamalloc(heapsz, sizeof(Object*));

+	qinit(&objq);

 	osinit(&done);

-	qput(o);

-	while((o = qpop()) != nil){

-		show(o);

-		for(i = 0; i < o->commit->nparent; i++){

-			if((p = readobject(o->commit->parent[i])) == nil)

+	qput(&objq, o, 0, 0);

+	while(qpop(&objq, &e)){

+		show(e.o);

+		for(i = 0; i < e.o->commit->nparent; i++){

+			if(oshas(&done, e.o->commit->parent[i]))

+				continue;

+			if((p = readobject(e.o->commit->parent[i])) == nil)

 				sysfatal("load %H: %r", o->commit->parent[i]);

-			qput(p);

+			osadd(&done, p);

+			qput(&objq, p, 0, 0);

 		}

-		unref(o);

+		unref(e.o);

 	}

 }

--- a/sys/src/cmd/git/query.c	Sat Sep 11 08:26:35 2021

+++ b/sys/src/cmd/git/query.c	Sat Sep 11 13:46:26 2021

@@ -158,6 +158,7 @@

 	char query[2048], repo[512];

 	ARGBEGIN{

+	case 'd':	chattygit++;	break;

 	case 'p':	fullpath++;	break;

 	case 'c':	changes++;	break;

 	case 'r':	reverse ^= 1;	break;

--- a/sys/src/cmd/git/ref.c	Sat Sep 11 08:26:35 2021

+++ b/sys/src/cmd/git/ref.c	Sat Sep 11 13:46:26 2021

@@ -5,8 +5,20 @@

 #include "git.h"

 typedef struct Eval	Eval;

-typedef struct XObject	XObject;

-typedef struct Objq	Objq;

+typedef struct Lcaq	Lcaq;

+

+struct Lcaq {

+	Objq;

+

+	Hash	*head;

+	Hash	*tail;

+	int	nhead;

+	int	ntail;

+

+	Object	*best;

+	int	dist;

+};

+

 enum {

 	Blank,

@@ -22,17 +34,10 @@

 	int	stksz;

 };

-struct XObject {

-	Object	*obj;

-	Object	*mark;

-	XObject	*queue;

-	XObject	*next;

-};

-

-struct Objq {

-	Objq	*next;

-	Object	*o;

-	int	color;

+static char *colors[] = {

+[Keep] "keep",

+[Drop] "drop",

+[Blank] "blank",

 };

 static Object zcommit = {

@@ -128,150 +133,98 @@

 	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)

+static int

+pickbest(Lcaq *q, Qelt *e, int color)

 {

-	Object *o, *p, *r;

-	XObject *ht[256];

-	XObject *h, *q, *q1, *q2;

-	int i;

+	int i, best, exact;

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

+	best = 0;

+	exact = 0;

+	if(color == Blank || e->color == color)

+		return 0;

+	if(e->dist < q->dist){

+		dprint(1, "found best (dist %d < %d): %H\n", e->dist, q->dist, e->o->hash);

+		best = 1;

 	}

-done:

-	for(i=0; i<nelem(ht); i++){

-		while(h = ht[i]){

-			ht[i] = h->next;

-			free(h);

+	for(i = 0; i < q->nhead; i++)

+		if(hasheq(&q->head[i], &e->o->hash)){

+			dprint(1, "found best (exact head): %H\n", e->o->hash);

+			best = 1;

+			exact = 1;

 		}

+	for(i = 0; i < q->ntail; i++)

+		if(hasheq(&q->tail[i], &e->o->hash)){

+			dprint(1, "found best (exact tail): %H\n", e->o->hash);

+			best = 1;

+			exact = 1;

+		}

+	if(best){

+		q->best = e->o;

+		q->dist = e->dist;

 	}

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

+	return exact;

 }

 static int

-repaint(Objset *keep, Objset *drop, Object *o)

+repaint(Lcaq *lcaq, Objset *keep, Objset *drop, Object *o, int dist, int ancestor)

 {

+	Lcaq objq;

+	Qelt e;

 	Object *p;

 	int i;

-	if(!oshas(keep, o->hash) && !oshas(drop, o->hash)){

-		dprint(2, "repaint: blank => drop %H\n", o->hash);

-		osadd(drop, o);

-		return 0;

-	}

-	if(oshas(keep, o->hash))

-		dprint(2, "repaint: keep => drop %H\n", o->hash);

-	osadd(drop, o);

-	for(i = 0; i < o->commit->nparent; i++){

-		if((p = readobject(o->commit->parent[i])) == nil)

-			return -1;

-		if(repaint(keep, drop, p) == -1)

-			return -1;

-		unref(p);

+	qinit(&objq);

+	if((o = readobject(o->hash)) == nil)

+		return -1;

+	qput(&objq, o, Drop, dist);

+	while(qpop(&objq, &e)){

+		o = e.o;

+		if(oshas(drop, o->hash))

+			continue;

+		if(ancestor && pickbest(lcaq, &e, Keep))

+			goto out;

+		if(!oshas(keep, o->hash)){

+			dprint(2, "repaint: blank => drop %H\n", o->hash);

+			osadd(drop, o);

+			continue;

+		}

+		for(i = 0; i < o->commit->nparent; i++){

+			if(oshas(drop, o->commit->parent[i]))

+				continue;

+			if((p = readobject(o->commit->parent[i])) == nil)

+				goto out;

+			if(p->type != GCommit){

+				fprint(2, "hash %H not commit\n", p->hash);

+				unref(p);

+			}

+			qput(&objq, p, Drop, e.dist+1);

+		}

+		unref(e.o);

 	}

+out:

+	qclear(&objq);

 	return 0;

 }

-int

-findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres)

+static int

+paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int ancestor)

 {

-	Objq *q, *e, *n, **p;

+	Qelt e;

+	Lcaq objq;

 	Objset keep, drop;

 	Object *o, *c;

 	int i, ncolor;

-	e = nil;

-	q = nil;

-	p = &q;

 	osinit(&keep);

 	osinit(&drop);

+	qinit(&objq);

+	objq.head = head;

+	objq.nhead = nhead;

+	objq.tail = tail;

+	objq.ntail = ntail;

+	objq.dist = 1<<30;

+

 	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 +235,11 @@

 			unref(o);

 			continue;

 		}

-		dprint(1, "twixt init: keep %H\n", o->hash);

-		e = emalloc(sizeof(Objq));

-		e->o = o;

-		e->color = Keep;

-		*p = e;

-		p = &e->next;

+		dprint(1, "init: keep %H\n", o->hash);

+		qput(&objq, o, Keep, 0);

 		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;

@@ -303,75 +250,115 @@

 			continue;

 		}

 		dprint(1, "init: drop %H\n", o->hash);

-		e = emalloc(sizeof(Objq));

-		e->o = o;

-		e->color = Drop;

-		*p = e;

-		p = &e->next;

+		qput(&objq, o, Drop, 0);

 		unref(o);

 	}

 	dprint(1, "finding twixt commits\n");

-	while(q != nil){

-		if(oshas(&drop, q->o->hash))

+	while(qpop(&objq, &e)){

+		if(oshas(&drop, e.o->hash))

 			ncolor = Drop;

-		else if(oshas(&keep, q->o->hash))

+		else if(oshas(&keep, e.o->hash))

 			ncolor = Keep;

 		else

 			ncolor = Blank;

-		if(ncolor == Drop || ncolor == Keep && q->color == Keep)

-			goto next;

-		if(ncolor == Keep && q->color == Drop){

-			if(repaint(&keep, &drop, q->o) == -1)

+		if(ancestor && pickbest(&objq, &e, ncolor))

+			goto exactlca;

+		if(ncolor == Keep && e.color == Keep || ncolor == Drop)

+			continue;

+		if(ncolor == Keep && e.color == Drop){

+			if(repaint(&objq, &keep, &drop, e.o, e.dist, ancestor) == -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);

+			if(e.color == Keep)

+				osadd(&keep, e.o);

 			else

-				osadd(&drop, q->o);

-			for(i = 0; i < q->o->commit->nparent; i++){

-				if((c = readobject(q->o->commit->parent[i])) == nil)

+				osadd(&drop, e.o);

+			o = readobject(e.o->hash);

+			for(i = 0; i < o->commit->nparent; i++){

+				if((c = readobject(e.o->commit->parent[i])) == nil)

 					goto error;

 				if(c->type != GCommit){

 					fprint(2, "warning: %H does not point at commit\n", c->hash);

 					unref(c);

 					continue;

 				}

-				dprint(2, "enqueue: %s %H\n", q->color == Keep ? "keep" : "drop", c->hash);

-				n = emalloc(sizeof(Objq));

-				n->color = q->color;

-				n->next = nil;

-				n->o = c;

-				e->next = n;

-				e = n;

+				dprint(2, "\tenqueue: %s %H\n", colors[e.color], c->hash);

+				qput(&objq, c, e.color, e.dist+1);

 				unref(c);

 			}

-		}else{

-			sysfatal("oops");

+			unref(o);

 		}

-next:

-		n = q->next;

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

+exactlca:

+	if(ancestor){

+		dprint(1, "found ancestor\n");

+		if(objq.best == nil){

+			*nres = 0;

+			*res = nil;

+		}else{

+			*nres = 1;

+			*res = eamalloc(1, sizeof(Object*));

+			(*res)[0] = objq.best;

+		}

+	}else{

+		dprint(1, "found twixt\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)++;

+			}

 		}

 	}

 	osclear(&keep);

 	osclear(&drop);

 	return 0;

 error:

-	for(; q != nil; q = n) {

-		n = q->next;

-		free(q);

-	}

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

+	free(objq.heap);

 	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 ref(r);

+}

+

+int

+lca(Eval *ev)

+{

+	Object *a, *b, **o;

+	int n;

+

+	if(ev->nstk < 2){

+		werrstr("ancestor needs 2 objects");

+		return -1;

+	}

+	n = 0;

+	b = pop(ev);

+	a = 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

--- a/sys/src/cmd/git/util.c	Sat Sep 11 08:26:35 2021

+++ b/sys/src/cmd/git/util.c	Sat Sep 11 13:46:26 2021

@@ -321,3 +321,74 @@

 	}

 	return pct;

 }

+

+void

+qinit(Objq *q)

+{

+	memset(q, 0, sizeof(Objq));

+	q->nheap = 0;

+	q->heapsz = 8;

+	q->heap = eamalloc(q->heapsz, sizeof(Qelt));

+}

+

+void

+qclear(Objq *q)

+{

+	free(q->heap);

+}

+

+void

+qput(Objq *q, Object *o, int color, int dist)

+{

+	Qelt t;

+	int i;

+

+	if(q->nheap == q->heapsz){

+		q->heapsz *= 2;

+		q->heap = earealloc(q->heap, q->heapsz, sizeof(Qelt));

+	}

+	q->heap[q->nheap].o = o;

+	q->heap[q->nheap].color = color;

+	q->heap[q->nheap].dist = dist;

+	q->heap[q->nheap].mtime = o->commit->mtime;

+	for(i = q->nheap; i > 0; i = (i-1)/2){

+		if(q->heap[i].mtime < q->heap[(i-1)/2].mtime)

+			break;

+		t = q->heap[i];

+		q->heap[i] = q->heap[(i-1)/2];

+		q->heap[(i-1)/2] = t;

+	}

+	q->nheap++;

+}

+

+int

+qpop(Objq *q, Qelt *e)

+{

+	int i, l, r, m;

+	Qelt t;

+

+	if(q->nheap == 0)

+		return 0;

+	*e = q->heap[0];

+	if(--q->nheap == 0)

+		return 1;

+

+	i = 0;

+	q->heap[0] = q->heap[q->nheap];

+	while(1){

+		m = i;

+		l = 2*i+1;

+		r = 2*i+2;

+		if(l < q->nheap && q->heap[m].mtime < q->heap[l].mtime)

+			m = l;

+		if(r < q->nheap && q->heap[m].mtime < q->heap[r].mtime)

+			m = r;

+		if(m == i)

+			break;

+		t = q->heap[m];

+		q->heap[m] = q->heap[i];

+		q->heap[i] = t;

+		i = m;

+	}

+	return 1;

+}