From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: * X-Spam-Status: No, score=1.3 required=5.0 tests=RDNS_NONE autolearn=no autolearn_force=no version=3.4.4 Received: (qmail 11576 invoked from network); 29 Aug 2021 02:40:37 -0000 Received: from unknown (HELO 4ess.inri.net) (216.126.196.42) by inbox.vuxu.org with ESMTPUTF8; 29 Aug 2021 02:40:37 -0000 Received: from mimir.eigenstate.org ([206.124.132.107]) by 4ess; Sat Aug 28 22:33:35 -0400 2021 Received: from abbatoir.myfiosgateway.com (pool-74-108-56-225.nycmny.fios.verizon.net [74.108.56.225]) by mimir.eigenstate.org (OpenSMTPD) with ESMTPSA id 19681b34 (TLSv1.2:ECDHE-RSA-AES256-SHA:256:NO) for <9front@9front.org>; Sat, 28 Aug 2021 19:33:17 -0700 (PDT) Message-ID: <77A01EE7FDB6C6E09DFECCDC61185541@eigenstate.org> To: 9front@9front.org Date: Sat, 28 Aug 2021 22:33:15 -0400 From: ori@eigenstate.org In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: decentralized database SQL over SSL engine template content-driven optimizer Subject: Re: [9front] git/query: improve LCA results Reply-To: 9front@9front.org Precedence: bulk Quoth ori@eigenstate.org: > Since bugs here can lead to issues sysupdating, I'd > like some extra eyeballs, testing, and review on this > before I commit. A slightly improved version. The `haskeep()` optimization to break out early could cause us to leave before we'd found the best node. diff e6f0abc25e4e237fff97ef9bdd1dc98ee519def8 uncommitted --- a/sys/src/cmd/git/ref.c +++ b/sys/src/cmd/git/ref.c @@ -22,19 +22,19 @@ int stksz; }; -struct XObject { - Object *obj; - Object *mark; - XObject *queue; - XObject *next; -}; - struct Objq { Objq *next; Object *o; int color; + int dist; }; +static char *colors[] = { +[Keep] "keep", +[Drop] "drop", +[Blank] "blank", +}; + static Object zcommit = { .type=GCommit }; @@ -128,110 +128,6 @@ 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) -{ - Object *o, *p, *r; - XObject *ht[256]; - XObject *h, *q, *q1, *q2; - int i; - - 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; - } -done: - for(i=0; inext; - free(h); - } - } - 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; -} - static int repaint(Objset *keep, Objset *drop, Object *o) { @@ -249,29 +145,48 @@ for(i = 0; i < o->commit->nparent; i++){ if((p = readobject(o->commit->parent[i])) == nil) return -1; + if(oshas(drop, p->hash)) + goto next; if(repaint(keep, drop, p) == -1) return -1; +next: unref(p); } return 0; } -int -findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres) +static int +bestpick(Hash *head, int nhead, Hash *tail, int ntail, Objq *q, int dist) { + int i; + + if(q->dist < dist) + return 1; + for(i = 0; i < nhead; i++) + if(hasheq(&head[i], &q->o->hash)) + return 1; + for(i = 0; i < ntail; i++) + if(hasheq(&tail[i], &q->o->hash)) + return 1; + return 0; +} + +static int +paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, int ancestor) +{ Objq *q, *e, *n, **p; Objset keep, drop; - Object *o, *c; - int i, ncolor; + Object *o, *c, *best; + int i, dist, ncolor; e = nil; q = nil; p = &q; + best = nil; + dist = 1<<30; osinit(&keep); osinit(&drop); 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 +197,16 @@ unref(o); continue; } - dprint(1, "twixt init: keep %H\n", o->hash); + dprint(1, "init: keep %H\n", o->hash); e = emalloc(sizeof(Objq)); e->o = o; e->color = Keep; + e->dist = 0; *p = e; p = &e->next; 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; @@ -306,6 +220,7 @@ e = emalloc(sizeof(Objq)); e->o = o; e->color = Drop; + e->dist = 0; *p = e; p = &e->next; unref(o); @@ -319,18 +234,37 @@ ncolor = Keep; else ncolor = Blank; - if(ncolor == Drop || ncolor == Keep && q->color == Keep) + dprint(2, "visit: ncolor=%s, qcolor=%s %H\n", + colors[ncolor], colors[q->color], q->o->hash); + if(ncolor == Keep && q->color == Keep){ goto next; - if(ncolor == Keep && q->color == Drop){ + }else if(ncolor == Drop){ + dprint(2, "consider: best %H => %H (dist: %d => %d)\n", + best ? best->hash : Zhash, q->o->hash, + dist, q->dist); + if(q->color == Keep && bestpick(head, nhead, tail, ntail, q, dist)){ + dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n", + best ? best->hash : Zhash, q->o->hash, + dist, q->dist); + best = q->o; + dist = q->dist; + } + }else if(ncolor == Keep && q->color == Drop){ + dprint(2, "consider: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist); + if(bestpick(head, nhead, tail, ntail, q, dist)){ + dprint(2, "ancestor: best %H => %H (dist: %d => %d)\n", best ? best->hash : Zhash, q->o->hash, dist, q->dist); + best = q->o; + dist = q->dist; + } if(repaint(&keep, &drop, q->o) == -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); else osadd(&drop, q->o); - for(i = 0; i < q->o->commit->nparent; i++){ + o = readobject(q->o->hash); + for(i = 0; i < o->commit->nparent; i++){ if((c = readobject(q->o->commit->parent[i])) == nil) goto error; if(c->type != GCommit){ @@ -338,9 +272,10 @@ unref(c); continue; } - dprint(2, "enqueue: %s %H\n", q->color == Keep ? "keep" : "drop", c->hash); + dprint(2, "enqueue: %s %H\n", colors[q->color], c->hash); n = emalloc(sizeof(Objq)); n->color = q->color; + n->dist = q->dist + 1; n->next = nil; n->o = c; e->next = n; @@ -347,8 +282,9 @@ e = n; unref(c); } + unref(o); }else{ - sysfatal("oops"); + sysfatal("oops: ncolor==%d && qcolor==%d", ncolor, q->color); } next: n = q->next; @@ -355,13 +291,24 @@ 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)++; + if(ancestor){ + if(best == nil){ + *nres = 0; + *res = nil; + }else{ + *nres = 1; + *res = eamalloc(1, sizeof(Object*)); + (*res)[0] = best; } + }else{ + *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); @@ -372,6 +319,46 @@ free(q); } 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 r; +} + +int +lca(Eval *ev) +{ + Object *a, *b, **o; + int n; + + if(ev->nstk < 2){ + werrstr("ancestor needs 2 objects"); + return -1; + } + n = 0; + a = pop(ev); + b = 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