ref: 768963687f66b324a6442ec46e1d9939944ed37a
dir: /ref.c/
#include <u.h> #include <libc.h> #include <ctype.h> #include "git.h" typedef struct Eval Eval; typedef struct XObject XObject; typedef struct Objq Objq; enum { Blank, Keep, Drop, }; struct Eval { char *str; char *p; Object **stk; int nstk; int stksz; }; struct XObject { Object *obj; Object *mark; XObject *queue; XObject *next; }; struct Objq { Objq *next; Object *o; int color; }; void eatspace(Eval *ev) { while(isspace(ev->p[0])) ev->p++; } int objdatecmp(void *pa, void *pb) { Object *a, *b; a = *(Object**)pa; b = *(Object**)pb; assert(a->type == GCommit && b->type == GCommit); if(a->commit->mtime == b->commit->mtime) return 0; else if(a->commit->mtime < b->commit->mtime) return -1; else return 1; } void push(Eval *ev, Object *o) { if(ev->nstk == ev->stksz){ ev->stksz = 2*ev->stksz + 1; ev->stk = erealloc(ev->stk, ev->stksz*sizeof(Object*)); } ev->stk[ev->nstk++] = o; } Object* pop(Eval *ev) { if(ev->nstk == 0) sysfatal("stack underflow"); return ev->stk[--ev->nstk]; } Object* peek(Eval *ev) { if(ev->nstk == 0) sysfatal("stack underflow"); return ev->stk[ev->nstk - 1]; } int isword(char e) { return isalnum(e) || e == '/' || e == '-' || e == '_' || e == '.'; } int word(Eval *ev, char *b, int nb) { char *p, *e; int n; p = ev->p; for(e = p; isword(*e) && strncmp(e, "..", 2) != 0; e++) /* nothing */; /* 1 for nul terminator */ n = e - p + 1; if(n >= nb) n = nb; snprint(b, n, "%s", p); ev->p = e; return n > 0; } int take(Eval *ev, char *m) { int l; l = strlen(m); if(strncmp(ev->p, m, l) != 0) return 0; ev->p += l; 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 = malloc(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; i<nelem(ht); i++){ while(h = ht[i]){ ht[i] = h->next; 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) { 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); } return 0; } int findtwixt(Hash *head, int nhead, Hash *tail, int ntail, Object ***res, int *nres) { Objq *q, *e, *n, **p; Objset keep, drop; Object *o, *c; int i, ncolor; e = nil; q = nil; p = &q; osinit(&keep); osinit(&drop); for(i = 0; i < nhead; i++){ if((o = readobject(head[i])) == nil) sysfatal("read head %H: %r", head[i]); dprint(1, "twixt init: keep %H\n", o->hash); e = emalloc(sizeof(Objq)); e->o = o; e->color = Keep; *p = e; p = &e->next; unref(o); } for(i = 0; i < ntail; i++){ if((o = readobject(tail[i])) == nil) sysfatal("read tail %H: %r", tail[i]); dprint(1, "init: drop %H\n", o->hash); e = emalloc(sizeof(Objq)); e->o = o; e->color = Drop; *p = e; p = &e->next; unref(o); } dprint(1, "finding twixt commits\n"); while(q != nil){ if(oshas(&drop, q->o->hash)) ncolor = Drop; else if(oshas(&keep, q->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) 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++){ if((c = readobject(q->o->commit->parent[i])) == nil) goto error; 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; unref(c); } }else{ sysfatal("oops"); } next: n = q->next; free(q); q = n; } *res = emalloc(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); } return -1; } static int parent(Eval *ev) { Object *o, *p; o = pop(ev); /* Special case: first commit has no parent. */ if(o->commit->nparent == 0) p = emptydir(); else if ((p = readobject(o->commit->parent[0])) == nil){ werrstr("no parent for %H", o->hash); return -1; } push(ev, p); 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; } } return -1; } static int range(Eval *ev) { Object *a, *b, *p, **all; int nall, *idx, mark; Objset keep, skip; b = pop(ev); a = pop(ev); if(a->type != GCommit || b->type != GCommit){ werrstr("non-commit object in range"); return -1; } p = b; all = nil; idx = nil; nall = 0; mark = ev->nstk; osinit(&keep); osinit(&skip); while(1){ all = erealloc(all, (nall + 1)*sizeof(Object*)); idx = erealloc(idx, (nall + 1)*sizeof(int)); all[nall] = p; idx[nall] = 0; if(p == a) 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((p = readobject(p->commit->parent[idx[nall]])) == nil) sysfatal("bad commit %H", p->commit->parent[idx[nall]]); nall++; } free(all); qsort(ev->stk + mark, ev->nstk - mark, sizeof(Object*), objdatecmp); return 0; } int readref(Hash *h, char *ref) { static char *try[] = {"", "refs/", "refs/heads/", "refs/remotes/", "refs/tags/", nil}; char buf[256], s[256], **pfx; int r, f, n; /* TODO: support hash prefixes */ if((r = hparse(h, ref)) != -1) return r; if(strcmp(ref, "HEAD") == 0){ snprint(buf, sizeof(buf), ".git/HEAD"); if((f = open(buf, OREAD)) == -1) return -1; if((n = readn(f, s, sizeof(s) - 1))== -1) return -1; s[n] = 0; strip(s); r = hparse(h, s); goto found; } for(pfx = try; *pfx; pfx++){ snprint(buf, sizeof(buf), ".git/%s%s", *pfx, ref); if((f = open(buf, OREAD)) == -1) continue; if((n = readn(f, s, sizeof(s) - 1)) == -1) continue; s[n] = 0; strip(s); r = hparse(h, s); close(f); goto found; } return -1; found: if(r == -1 && strstr(s, "ref: ") == s) r = readref(h, s + strlen("ref: ")); return r; } int evalpostfix(Eval *ev) { char name[256]; Object *o; Hash h; eatspace(ev); if(!word(ev, name, sizeof(name))){ werrstr("expected name in expression"); return -1; } if(readref(&h, name) == -1){ werrstr("invalid ref %s", name); return -1; }else if((o = readobject(h)) == nil){ werrstr("invalid ref %s (hash %H)", name, h); return -1; } push(ev, o); while(1){ eatspace(ev); switch(ev->p[0]){ case '^': case '~': ev->p++; if(parent(ev) == -1) return -1; break; case '@': ev->p++; if(lca(ev) == -1) return -1; break; default: goto done; break; } } done: return 0; } int evalexpr(Eval *ev, char *ref) { memset(ev, 0, sizeof(*ev)); ev->str = ref; ev->p = ref; while(1){ if(evalpostfix(ev) == -1) return -1; if(ev->p[0] == '\0') return 0; else if(take(ev, ":") || take(ev, "..")){ if(evalpostfix(ev) == -1) return -1; if(ev->p[0] != '\0'){ werrstr("junk at end of expression"); return -1; } return range(ev); } } } int resolverefs(Hash **r, char *ref) { Eval ev; Hash *h; int i; if(evalexpr(&ev, ref) == -1){ free(ev.stk); return -1; } h = emalloc(ev.nstk*sizeof(Hash)); for(i = 0; i < ev.nstk; i++) h[i] = ev.stk[i]->hash; *r = h; free(ev.stk); return ev.nstk; } int resolveref(Hash *r, char *ref) { Eval ev; if(evalexpr(&ev, ref) == -1){ free(ev.stk); return -1; } if(ev.nstk != 1){ werrstr("ambiguous ref expr"); free(ev.stk); return -1; } *r = ev.stk[0]->hash; free(ev.stk); return 0; } int readrefdir(Hash **refs, char ***names, int *nrefs, char *dpath, char *dname) { Dir *d, *e, *dir; char *path, *name, *sep; int ndir; if((ndir = slurpdir(dpath, &dir)) == -1) return -1; sep = (*dname == '\0') ? "" : "/"; e = dir + ndir; for(d = dir; d != e; d++){ path = smprint("%s/%s", dpath, d->name); name = smprint("%s%s%s", dname, sep, d->name); if(d->mode & DMDIR) { if(readrefdir(refs, names, nrefs, path, name) == -1) goto noref; }else{ *refs = erealloc(*refs, (*nrefs + 1)*sizeof(Hash)); *names = erealloc(*names, (*nrefs + 1)*sizeof(char*)); if(resolveref(&(*refs)[*nrefs], name) == -1) goto noref; (*names)[*nrefs] = name; *nrefs += 1; goto next; } noref: free(name); next: free(path); } free(dir); return 0; } int listrefs(Hash **refs, char ***names) { int nrefs; *refs = nil; *names = nil; nrefs = 0; if(readrefdir(refs, names, &nrefs, ".git/refs", "") == -1){ free(*refs); return -1; } return nrefs; }