From c7dcc82b0be805717efbe77c98eaadf3ee1e31af Mon Sep 17 00:00:00 2001 From: Ori Bernstein Date: Sat, 11 Sep 2021 17:46:26 +0000 Subject: 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. --- sys/src/cmd/git/git.h | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'sys/src/cmd/git/git.h') 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*); -- cgit v1.2.3