diff options
Diffstat (limited to 'third_party/git/builtin/name-rev.c')
| -rw-r--r-- | third_party/git/builtin/name-rev.c | 289 |
1 files changed, 85 insertions, 204 deletions
diff --git a/third_party/git/builtin/name-rev.c b/third_party/git/builtin/name-rev.c index a9dcd25e4647..c785fe16bade 100644 --- a/third_party/git/builtin/name-rev.c +++ b/third_party/git/builtin/name-rev.c @@ -6,25 +6,20 @@ #include "tag.h" #include "refs.h" #include "parse-options.h" -#include "prio-queue.h" #include "sha1-lookup.h" #include "commit-slab.h" -/* - * One day. See the 'name a rev shortly after epoch' test in t6120 when - * changing this value - */ -#define CUTOFF_DATE_SLOP 86400 +#define CUTOFF_DATE_SLOP 86400 /* one day */ -struct rev_name { - char *tip_name; +typedef struct rev_name { + const char *tip_name; timestamp_t taggerdate; int generation; int distance; int from_tag; -}; +} rev_name; -define_commit_slab(commit_rev_name, struct rev_name); +define_commit_slab(commit_rev_name, struct rev_name *); static timestamp_t cutoff = TIME_MAX; static struct commit_rev_name rev_names; @@ -32,16 +27,16 @@ static struct commit_rev_name rev_names; /* How many generations are maximally preferred over _one_ merge traversal? */ #define MERGE_TRAVERSAL_WEIGHT 65535 -static int is_valid_rev_name(const struct rev_name *name) +static struct rev_name *get_commit_rev_name(struct commit *commit) { - return name && (name->generation || name->tip_name); + struct rev_name **slot = commit_rev_name_peek(&rev_names, commit); + + return slot ? *slot : NULL; } -static struct rev_name *get_commit_rev_name(const struct commit *commit) +static void set_commit_rev_name(struct commit *commit, struct rev_name *name) { - struct rev_name *name = commit_rev_name_peek(&rev_names, commit); - - return is_valid_rev_name(name) ? name : NULL; + *commit_rev_name_at(&rev_names, commit) = name; } static int is_better_name(struct rev_name *name, @@ -80,135 +75,68 @@ static int is_better_name(struct rev_name *name, return 0; } -static struct rev_name *create_or_update_name(struct commit *commit, - timestamp_t taggerdate, - int generation, int distance, - int from_tag) -{ - struct rev_name *name = commit_rev_name_at(&rev_names, commit); - - if (is_valid_rev_name(name)) { - if (!is_better_name(name, taggerdate, distance, from_tag)) - return NULL; - - /* - * This string might still be shared with ancestors - * (generation > 0). We can release it here regardless, - * because the new name that has just won will be better - * for them as well, so name_rev() will replace these - * stale pointers when it processes the parents. - */ - if (!name->generation) - free(name->tip_name); - } - - name->taggerdate = taggerdate; - name->generation = generation; - name->distance = distance; - name->from_tag = from_tag; - - return name; -} - -static char *get_parent_name(const struct rev_name *name, int parent_number) -{ - struct strbuf sb = STRBUF_INIT; - size_t len; - - strip_suffix(name->tip_name, "^0", &len); - if (name->generation > 0) { - strbuf_grow(&sb, len + - 1 + decimal_width(name->generation) + - 1 + decimal_width(parent_number)); - strbuf_addf(&sb, "%.*s~%d^%d", (int)len, name->tip_name, - name->generation, parent_number); - } else { - strbuf_grow(&sb, len + - 1 + decimal_width(parent_number)); - strbuf_addf(&sb, "%.*s^%d", (int)len, name->tip_name, - parent_number); - } - return strbuf_detach(&sb, NULL); -} - -static void name_rev(struct commit *start_commit, +static void name_rev(struct commit *commit, const char *tip_name, timestamp_t taggerdate, - int from_tag, int deref) + int generation, int distance, int from_tag, + int deref) { - struct prio_queue queue; - struct commit *commit; - struct commit **parents_to_queue = NULL; - size_t parents_to_queue_nr, parents_to_queue_alloc = 0; - struct rev_name *start_name; - - parse_commit(start_commit); - if (start_commit->date < cutoff) - return; + struct rev_name *name = get_commit_rev_name(commit); + struct commit_list *parents; + int parent_number = 1; + char *to_free = NULL; - start_name = create_or_update_name(start_commit, taggerdate, 0, 0, - from_tag); - if (!start_name) - return; - if (deref) - start_name->tip_name = xstrfmt("%s^0", tip_name); - else - start_name->tip_name = xstrdup(tip_name); + parse_commit(commit); - memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */ - prio_queue_put(&queue, start_commit); - - while ((commit = prio_queue_get(&queue))) { - struct rev_name *name = get_commit_rev_name(commit); - struct commit_list *parents; - int parent_number = 1; - - parents_to_queue_nr = 0; + if (commit->date < cutoff) + return; - for (parents = commit->parents; - parents; - parents = parents->next, parent_number++) { - struct commit *parent = parents->item; - struct rev_name *parent_name; - int generation, distance; + if (deref) { + tip_name = to_free = xstrfmt("%s^0", tip_name); - parse_commit(parent); - if (parent->date < cutoff) - continue; + if (generation) + die("generation: %d, but deref?", generation); + } - if (parent_number > 1) { - generation = 0; - distance = name->distance + MERGE_TRAVERSAL_WEIGHT; - } else { - generation = name->generation + 1; - distance = name->distance + 1; - } + if (name == NULL) { + name = xmalloc(sizeof(rev_name)); + set_commit_rev_name(commit, name); + goto copy_data; + } else if (is_better_name(name, taggerdate, distance, from_tag)) { +copy_data: + name->tip_name = tip_name; + name->taggerdate = taggerdate; + name->generation = generation; + name->distance = distance; + name->from_tag = from_tag; + } else { + free(to_free); + return; + } - parent_name = create_or_update_name(parent, taggerdate, - generation, - distance, from_tag); - if (parent_name) { - if (parent_number > 1) - parent_name->tip_name = - get_parent_name(name, - parent_number); - else - parent_name->tip_name = name->tip_name; - ALLOC_GROW(parents_to_queue, - parents_to_queue_nr + 1, - parents_to_queue_alloc); - parents_to_queue[parents_to_queue_nr] = parent; - parents_to_queue_nr++; - } + for (parents = commit->parents; + parents; + parents = parents->next, parent_number++) { + if (parent_number > 1) { + size_t len; + char *new_name; + + strip_suffix(tip_name, "^0", &len); + if (generation > 0) + new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name, + generation, parent_number); + else + new_name = xstrfmt("%.*s^%d", (int)len, tip_name, + parent_number); + + name_rev(parents->item, new_name, taggerdate, 0, + distance + MERGE_TRAVERSAL_WEIGHT, + from_tag, 0); + } else { + name_rev(parents->item, tip_name, taggerdate, + generation + 1, distance + 1, + from_tag, 0); } - - /* The first parent must come out first from the prio_queue */ - while (parents_to_queue_nr) - prio_queue_put(&queue, - parents_to_queue[--parents_to_queue_nr]); } - - clear_prio_queue(&queue); - free(parents_to_queue); } static int subpath_matches(const char *path, const char *filter) @@ -229,10 +157,10 @@ static const char *name_ref_abbrev(const char *refname, int shorten_unambiguous) { if (shorten_unambiguous) refname = shorten_unambiguous_ref(refname, 0); - else if (skip_prefix(refname, "refs/heads/", &refname)) - ; /* refname already advanced */ - else - skip_prefix(refname, "refs/", &refname); + else if (starts_with(refname, "refs/heads/")) + refname = refname + 11; + else if (starts_with(refname, "refs/")) + refname = refname + 5; return refname; } @@ -247,10 +175,6 @@ static struct tip_table { struct tip_table_entry { struct object_id oid; const char *refname; - struct commit *commit; - timestamp_t taggerdate; - unsigned int from_tag:1; - unsigned int deref:1; } *table; int nr; int alloc; @@ -258,18 +182,13 @@ static struct tip_table { } tip_table; static void add_to_tip_table(const struct object_id *oid, const char *refname, - int shorten_unambiguous, struct commit *commit, - timestamp_t taggerdate, int from_tag, int deref) + int shorten_unambiguous) { refname = name_ref_abbrev(refname, shorten_unambiguous); ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc); oidcpy(&tip_table.table[tip_table.nr].oid, oid); tip_table.table[tip_table.nr].refname = xstrdup(refname); - tip_table.table[tip_table.nr].commit = commit; - tip_table.table[tip_table.nr].taggerdate = taggerdate; - tip_table.table[tip_table.nr].from_tag = from_tag; - tip_table.table[tip_table.nr].deref = deref; tip_table.nr++; tip_table.sorted = 0; } @@ -280,30 +199,12 @@ static int tipcmp(const void *a_, const void *b_) return oidcmp(&a->oid, &b->oid); } -static int cmp_by_tag_and_age(const void *a_, const void *b_) -{ - const struct tip_table_entry *a = a_, *b = b_; - int cmp; - - /* Prefer tags. */ - cmp = b->from_tag - a->from_tag; - if (cmp) - return cmp; - - /* Older is better. */ - if (a->taggerdate < b->taggerdate) - return -1; - return a->taggerdate != b->taggerdate; -} - static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data) { struct object *o = parse_object(the_repository, oid); struct name_ref_data *data = cb_data; int can_abbreviate_output = data->tags_only && data->name_only; int deref = 0; - int from_tag = 0; - struct commit *commit = NULL; timestamp_t taggerdate = TIME_MAX; if (data->tags_only && !starts_with(path, "refs/tags/")) @@ -352,6 +253,8 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo return 0; } + add_to_tip_table(oid, path, can_abbreviate_output); + while (o && o->type == OBJ_TAG) { struct tag *t = (struct tag *) o; if (!t->tagged) @@ -361,33 +264,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo taggerdate = t->date; } if (o && o->type == OBJ_COMMIT) { - commit = (struct commit *)o; - from_tag = starts_with(path, "refs/tags/"); - if (taggerdate == TIME_MAX) - taggerdate = commit->date; - } + struct commit *commit = (struct commit *)o; + int from_tag = starts_with(path, "refs/tags/"); - add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate, + if (taggerdate == TIME_MAX) + taggerdate = ((struct commit *)o)->date; + path = name_ref_abbrev(path, can_abbreviate_output); + name_rev(commit, xstrdup(path), taggerdate, 0, 0, from_tag, deref); - return 0; -} - -static void name_tips(void) -{ - int i; - - /* - * Try to set better names first, so that worse ones spread - * less. - */ - QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age); - for (i = 0; i < tip_table.nr; i++) { - struct tip_table_entry *e = &tip_table.table[i]; - if (e->commit) { - name_rev(e->commit, e->refname, e->taggerdate, - e->from_tag, e->deref); - } } + return 0; } static const unsigned char *nth_tip_table_ent(size_t ix, void *table_) @@ -419,11 +305,11 @@ static const char *get_exact_ref_match(const struct object *o) static const char *get_rev_name(const struct object *o, struct strbuf *buf) { struct rev_name *n; - const struct commit *c; + struct commit *c; if (o->type != OBJ_COMMIT) return get_exact_ref_match(o); - c = (const struct commit *) o; + c = (struct commit *) o; n = get_commit_rev_name(c); if (!n) return NULL; @@ -431,10 +317,11 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf) if (!n->generation) return n->tip_name; else { + int len = strlen(n->tip_name); + if (len > 2 && !strcmp(n->tip_name + len - 2, "^0")) + len -= 2; strbuf_reset(buf); - strbuf_addstr(buf, n->tip_name); - strbuf_strip_suffix(buf, "^0"); - strbuf_addf(buf, "~%d", n->generation); + strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation); return buf->buf; } } @@ -594,15 +481,9 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix) add_object_array(object, *argv, &revs); } - if (cutoff) { - /* check for undeflow */ - if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP) - cutoff = cutoff - CUTOFF_DATE_SLOP; - else - cutoff = TIME_MIN; - } + if (cutoff) + cutoff = cutoff - CUTOFF_DATE_SLOP; for_each_ref(name_ref, &data); - name_tips(); if (transform_stdin) { char buffer[2048]; |