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=2.3 required=5.0 tests=DATE_IN_PAST_96_XX, DKIM_INVALID,DKIM_SIGNED autolearn=no autolearn_force=no version=3.4.4 Received: (qmail 32714 invoked from network); 27 Sep 2022 23:56:12 -0000 Received: from 9front.inri.net (168.235.81.73) by inbox.vuxu.org with ESMTPUTF8; 27 Sep 2022 23:56:12 -0000 MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit Received: from mail-qt1-f171.google.com ([209.85.160.171]) by 9front; Tue Sep 27 19:54:54 -0400 2022 Received: by mail-qt1-f171.google.com with SMTP id y2so7072454qtv.5 for <9front@9front.org>; Tue, 27 Sep 2022 16:54:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mforney.org; s=google; h=subject:date:to:from:message-id:from:to:cc:subject:date; bh=CXVbIM0kt8if0UE6H6Oy188b1oINtIOX3qCr/dZjmpw=; b=G+IrJ7Dt0vZEHO+GJ07XNIBpgcGGRK+oHws4LIYvMNi/r+q7cIHmr3JUDlFO8FZD9Y akL/Hj2olrJ64BYNSx4muTSwZqtK1f2Bg0a/xDPGx5hP7YkDw+kmgcYPHcqzm98pXr1Z 9JWKkX/cl+k0Z69yXNSOVkiNAJavb4oXCOEZojwhjo68q6weJ0QGQv4GsYMWCqWZ3O8T hiEyXcWAY2/ftgrLjYH0XZOwL5ehdjtVJW84s/NlmMIxSl0g/7Mkvcp2+dPEdIWvkx7X cL7TMGN/hEP3Du5j9MhxMU0+ieLCwQ/ld8xSi1haSA/GEGCyWIaRzbschF8nu/0bHuS+ TZQA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=subject:date:to:from:message-id:x-gm-message-state:from:to:cc :subject:date; bh=CXVbIM0kt8if0UE6H6Oy188b1oINtIOX3qCr/dZjmpw=; b=MbB5H0FqhzS0xi/59s5wGVjE64bAiJtKPCxioiSGmvF0925NHOi8wGj0t599443OiV mouXWTIsMEcfuE7Q6TxGzgJGz8q26S7OlQzrU6IjwHzke3LVdyscbIN3qrGxyxtrnrQ5 pemf88GRDIdH5TQ9Kesh9ZnQAVlU5vFBDZFTZjy2mRDvSFS05F3KNNX6U9e/JUm5JSKv yQlLpmsA/Zx6qtPy7aWGdexTh17DpklQUCAe5A7MrSIz2r92pv0QHVeD/oAMEg9n8a19 7bjiP5vS8U6GT2CTSpu2nonZqWH9jnT0NNEJf/QFYem0ufPlCdMBzCWk9cqHhvgHrHVg fXwg== X-Gm-Message-State: ACrzQf2/LACtKb28SLvlOstw8Zc7JzK7A8qj8XiGQutnV2vPKUBwXN7w 3PvSoFOWja0y1ROp4a2n4hVUSfcSArpCmJqZXGA= X-Google-Smtp-Source: AMsMyM4hVR3YB7+CBdHsnSpV8RpEFmUwEbQ6hM6ZoVwV/KS1soS5Tx6lgjfdB01LhYi2gmULYVuA2w== X-Received: by 2002:ac8:5712:0:b0:35c:d6ad:6707 with SMTP id 18-20020ac85712000000b0035cd6ad6707mr25137686qtw.16.1664322890702; Tue, 27 Sep 2022 16:54:50 -0700 (PDT) Return-Path: Received: from localhost ([2600:1700:3ec0:6b60:cab2:9bff:fe88:d09c]) by smtp.gmail.com with ESMTPSA id x11-20020a05620a258b00b006bac157ec19sm1854483qko.123.2022.09.27.16.54.49 for <9front@9front.org> (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Tue, 27 Sep 2022 16:54:50 -0700 (PDT) Message-ID: <63338d4a.050a0220.10e9a.6f67@mx.google.com> From: Michael Forney To: 9front@9front.org Date: Sun, 13 Mar 2022 19:09:47 -0700 List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: content-addressed realtime control Subject: [9front] [PATCH] git/query: implement range using paint() Reply-To: 9front@9front.org Precedence: bulk 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. --- The main motivation for this patch is to make a..b work as expected when a is not an ancestor of b. This type of query is very useful to answer questions like "what commits do I have that upstream is missing?" (origin/front..HEAD) or "what commits does upstream have that I'm missing?" (HEAD..origin/front) when your branch has diverged from upstream. Of course, this is possible using the lca feature of ref syntax (origin/front HEAD @ .. HEAD), but my investigation revealed that there are other cases that are broken, even if a is an ancestor of b. I have some regress tests ready to commit once this is fixed. sys/src/cmd/git/ref.c | 120 ++++++++++++++++-------------------------- 1 file changed, 45 insertions(+), 75 deletions(-) diff --git a/sys/src/cmd/git/ref.c b/sys/src/cmd/git/ref.c index 11eea7a077..bf798e2664 100644 --- a/sys/src/cmd/git/ref.c +++ b/sys/src/cmd/git/ref.c @@ -13,6 +13,12 @@ enum { Skip, }; +enum { + Lca, + Twixt, + Range, +}; + struct Eval { char *str; char *p; @@ -102,18 +108,20 @@ take(Eval *ev, char *m) } 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 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in 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 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in } 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 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in *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,21 +229,36 @@ paint(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres, in (*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); osclear(&skip); return 0; error: - dprint(1, "twixt error: %r\n"); + dprint(1, "paint error: %r\n"); free(objq.heap); + free(range); 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); + return paint(head, nhead, tail, ntail, res, nres, Twixt); } Object* @@ -238,7 +267,7 @@ ancestor(Object *a, Object *b) 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 @@ lca(Eval *ev) 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); @@ -284,34 +313,11 @@ parent(Eval *ev) return 0; } -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 @@ range(Eval *ev) 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 -- 2.34.1