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.

1 files changed, 22 insertions, 0 deletions

diff --git a/sys/src/cmd/git/git.h b/sys/src/cmd/git/git.h
index 76c215b59..839fcfe60 100644
--- a/sys/src/cmd/git/git.h
+++ b/sys/src/cmd/git/git.h
@@ -18,6 +18,8 @@ typedef struct Idxent	Idxent;
 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 @@ struct Objset {
 	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	gitconnect(Conn *, char *, char *);
 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*);