diff options
Diffstat (limited to 'builtin/name-rev.c')
| -rw-r--r-- | builtin/name-rev.c | 289 |
1 files changed, 204 insertions, 85 deletions
diff --git a/builtin/name-rev.c b/builtin/name-rev.c index c785fe16bade..a9dcd25e4647 100644 --- a/builtin/name-rev.c +++ b/builtin/name-rev.c @@ -6,20 +6,25 @@ #include "tag.h" #include "refs.h" #include "parse-options.h" +#include "prio-queue.h" #include "sha1-lookup.h" #include "commit-slab.h" -#define CUTOFF_DATE_SLOP 86400 /* one day */ +/* + * One day. See the 'name a rev shortly after epoch' test in t6120 when + * changing this value + */ +#define CUTOFF_DATE_SLOP 86400 -typedef struct rev_name { - const char *tip_name; +struct rev_name { + 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; @@ -27,16 +32,16 @@ static struct commit_rev_name rev_names; /* How many generations are maximally preferred over _one_ merge traversal? */ #define MERGE_TRAVERSAL_WEIGHT 65535 -static struct rev_name *get_commit_rev_name(struct commit *commit) +static int is_valid_rev_name(const struct rev_name *name) { - struct rev_name **slot = commit_rev_name_peek(&rev_names, commit); - - return slot ? *slot : NULL; + return name && (name->generation || name->tip_name); } -static void set_commit_rev_name(struct commit *commit, struct rev_name *name) +static struct rev_name *get_commit_rev_name(const struct commit *commit) { - *commit_rev_name_at(&rev_names, commit) = name; + struct rev_name *name = commit_rev_name_peek(&rev_names, commit); + + return is_valid_rev_name(name) ? name : NULL; } static int is_better_name(struct rev_name *name, @@ -75,68 +80,135 @@ static int is_better_name(struct rev_name *name, return 0; } -static void name_rev(struct commit *commit, - const char *tip_name, timestamp_t taggerdate, - int generation, int distance, int from_tag, - int deref) +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 = get_commit_rev_name(commit); - struct commit_list *parents; - int parent_number = 1; - char *to_free = NULL; - - parse_commit(commit); + 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); + } - if (commit->date < cutoff) - return; + name->taggerdate = taggerdate; + name->generation = generation; + name->distance = distance; + name->from_tag = from_tag; - if (deref) { - tip_name = to_free = xstrfmt("%s^0", tip_name); + return name; +} - if (generation) - die("generation: %d, but deref?", generation); +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); +} - 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); +static void name_rev(struct commit *start_commit, + const char *tip_name, timestamp_t taggerdate, + 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; - } - 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); + 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); + + 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; + + for (parents = commit->parents; + parents; + parents = parents->next, parent_number++) { + struct commit *parent = parents->item; + struct rev_name *parent_name; + int generation, distance; + + parse_commit(parent); + if (parent->date < cutoff) + continue; + + if (parent_number > 1) { + generation = 0; + distance = name->distance + MERGE_TRAVERSAL_WEIGHT; + } else { + generation = name->generation + 1; + distance = name->distance + 1; + } + + 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++; + } } + + /* 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) @@ -157,10 +229,10 @@ static const char *name_ref_abbrev(const char *refname, int shorten_unambiguous) { if (shorten_unambiguous) refname = shorten_unambiguous_ref(refname, 0); - else if (starts_with(refname, "refs/heads/")) - refname = refname + 11; - else if (starts_with(refname, "refs/")) - refname = refname + 5; + else if (skip_prefix(refname, "refs/heads/", &refname)) + ; /* refname already advanced */ + else + skip_prefix(refname, "refs/", &refname); return refname; } @@ -175,6 +247,10 @@ 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; @@ -182,13 +258,18 @@ static struct tip_table { } tip_table; static void add_to_tip_table(const struct object_id *oid, const char *refname, - int shorten_unambiguous) + int shorten_unambiguous, struct commit *commit, + timestamp_t taggerdate, int from_tag, int deref) { 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; } @@ -199,12 +280,30 @@ 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/")) @@ -253,8 +352,6 @@ 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) @@ -264,18 +361,35 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo taggerdate = t->date; } if (o && o->type == OBJ_COMMIT) { - struct commit *commit = (struct commit *)o; - int from_tag = starts_with(path, "refs/tags/"); - + commit = (struct commit *)o; + from_tag = starts_with(path, "refs/tags/"); 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); + taggerdate = commit->date; } + + add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate, + 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); + } + } +} + static const unsigned char *nth_tip_table_ent(size_t ix, void *table_) { struct tip_table_entry *table = table_; @@ -305,11 +419,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; - struct commit *c; + const struct commit *c; if (o->type != OBJ_COMMIT) return get_exact_ref_match(o); - c = (struct commit *) o; + c = (const struct commit *) o; n = get_commit_rev_name(c); if (!n) return NULL; @@ -317,11 +431,10 @@ 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_addf(buf, "%.*s~%d", len, n->tip_name, n->generation); + strbuf_addstr(buf, n->tip_name); + strbuf_strip_suffix(buf, "^0"); + strbuf_addf(buf, "~%d", n->generation); return buf->buf; } } @@ -481,9 +594,15 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix) add_object_array(object, *argv, &revs); } - if (cutoff) - cutoff = cutoff - CUTOFF_DATE_SLOP; + if (cutoff) { + /* check for undeflow */ + if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP) + cutoff = cutoff - CUTOFF_DATE_SLOP; + else + cutoff = TIME_MIN; + } for_each_ref(name_ref, &data); + name_tips(); if (transform_stdin) { char buffer[2048]; |