builtin-describe.c

   1 #include "cache.h"
   2 #include "commit.h"
   3 #include "tag.h"
   4 #include "refs.h"
   5 #include "builtin.h"
   6
   7 #define SEEN            (1u<<0)
   8 #define MAX_TAGS        (FLAG_BITS - 1)
   9
  10 static const char describe_usage[] =
  11 "git-describe [--all] [--tags] [--abbrev=<n>] <committish>*";
  12
  13 static int debug;       /* Display lots of verbose info */
  14 static int all; /* Default to annotated tags only */
  15 static int tags;        /* But allow any tags if --tags is specified */
  16 static int abbrev = DEFAULT_ABBREV;
  17 static int max_candidates = 10;
  18
  19 static unsigned int names[256], allocs[256];
  20 static struct commit_name {
  21         struct commit *commit;
  22         int prio; /* annotated tag = 2, tag = 1, head = 0 */
  23         char path[FLEX_ARRAY]; /* more */
  24 } **name_array[256];
  25
  26 static struct commit_name *match(struct commit *cmit)
  27 {
  28         unsigned char level0 = cmit->object.sha1[0];
  29         struct commit_name **p = name_array[level0];
  30         unsigned int hi = names[level0];
  31         unsigned int lo = 0;
  32
  33         while (lo < hi) {
  34                 unsigned int mi = (lo + hi) / 2;
  35                 int cmp = hashcmp(p[mi]->commit->object.sha1,
  36                         cmit->object.sha1);
  37                 if (!cmp) {
  38                         while (mi && p[mi - 1]->commit == cmit)
  39                                 mi--;
  40                         return p[mi];
  41                 }
  42                 if (cmp > 0)
  43                         hi = mi;
  44                 else
  45                         lo = mi+1;
  46         }
  47         return NULL;
  48 }
  49
  50 static void add_to_known_names(const char *path,
  51                                struct commit *commit,
  52                                int prio)
  53 {
  54         int idx;
  55         int len = strlen(path)+1;
  56         struct commit_name *name = xmalloc(sizeof(struct commit_name) + len);
  57         unsigned char m = commit->object.sha1[0];
  58
  59         name->commit = commit;
  60         name->prio = prio;
  61         memcpy(name->path, path, len);
  62         idx = names[m];
  63         if (idx >= allocs[m]) {
  64                 allocs[m] = (idx + 50) * 3 / 2;
  65                 name_array[m] = xrealloc(name_array[m],
  66                         allocs[m] * sizeof(*name_array));
  67         }
  68         name_array[m][idx] = name;
  69         names[m] = ++idx;
  70 }
  71
  72 static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)
  73 {
  74         struct commit *commit = lookup_commit_reference_gently(sha1, 1);
  75         struct object *object;
  76         int prio;
  77
  78         if (!commit)
  79                 return 0;
  80         object = parse_object(sha1);
  81         /* If --all, then any refs are used.
  82          * If --tags, then any tags are used.
  83          * Otherwise only annotated tags are used.
  84          */
  85         if (!strncmp(path, "refs/tags/", 10)) {
  86                 if (object->type == OBJ_TAG)
  87                         prio = 2;
  88                 else
  89                         prio = 1;
  90         }
  91         else
  92                 prio = 0;
  93
  94         if (!all) {
  95                 if (!prio)
  96                         return 0;
  97                 if (!tags && prio < 2)
  98                         return 0;
  99         }
 100         add_to_known_names(all ? path + 5 : path + 10, commit, prio);
 101         return 0;
 102 }
 103
 104 static int compare_names(const void *_a, const void *_b)
 105 {
 106         struct commit_name *a = *(struct commit_name **)_a;
 107         struct commit_name *b = *(struct commit_name **)_b;
 108         unsigned long a_date = a->commit->date;
 109         unsigned long b_date = b->commit->date;
 110         int cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);
 111
 112         if (cmp)
 113                 return cmp;
 114         if (a->prio != b->prio)
 115                 return b->prio - a->prio;
 116         return (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;
 117 }
 118
 119 struct possible_tag {
 120         struct commit_name *name;
 121         unsigned long depth;
 122         unsigned flag_within;
 123 };
 124
 125 static void describe(const char *arg, int last_one)
 126 {
 127         unsigned char sha1[20];
 128         struct commit *cmit, *gave_up_on = NULL;
 129         struct commit_list *list;
 130         static int initialized = 0;
 131         struct commit_name *n;
 132         struct possible_tag all_matches[MAX_TAGS], *min_match;
 133         unsigned int match_cnt = 0, annotated_cnt = 0, cur_match;
 134         unsigned long seen_commits = 0;
 135
 136         if (get_sha1(arg, sha1))
 137                 die("Not a valid object name %s", arg);
 138         cmit = lookup_commit_reference(sha1);
 139         if (!cmit)
 140                 die("%s is not a valid '%s' object", arg, commit_type);
 141
 142         if (!initialized) {
 143                 unsigned int m;
 144                 initialized = 1;
 145                 for_each_ref(get_name, NULL);
 146                 for (m = 0; m < ARRAY_SIZE(name_array); m++)
 147                         qsort(name_array[m], names[m],
 148                                 sizeof(*name_array[m]), compare_names);
 149         }
 150
 151         n = match(cmit);
 152         if (n) {
 153                 printf("%s\n", n->path);
 154                 return;
 155         }
 156
 157         if (debug)
 158                 fprintf(stderr, "searching to describe %s\n", arg);
 159
 160         list = NULL;
 161         cmit->object.flags = SEEN;
 162         commit_list_insert(cmit, &list);
 163         while (list) {
 164                 struct commit *c = pop_commit(&list);
 165                 struct commit_list *parents = c->parents;
 166                 seen_commits++;
 167                 n = match(c);
 168                 if (n) {
 169                         if (match_cnt < max_candidates) {
 170                                 struct possible_tag *t = &all_matches[match_cnt++];
 171                                 t->name = n;
 172                                 t->depth = seen_commits - 1;
 173                                 t->flag_within = 1u << match_cnt;
 174                                 c->object.flags |= t->flag_within;
 175                                 if (n->prio == 2)
 176                                         annotated_cnt++;
 177                         }
 178                         else {
 179                                 gave_up_on = c;
 180                                 break;
 181                         }
 182                 }
 183                 for (cur_match = 0; cur_match < match_cnt; cur_match++) {
 184                         struct possible_tag *t = &all_matches[cur_match];
 185                         if (!(c->object.flags & t->flag_within))
 186                                 t->depth++;
 187                 }
 188                 if (annotated_cnt && !list) {
 189                         if (debug)
 190                                 fprintf(stderr, "finished search at %s\n",
 191                                         sha1_to_hex(c->object.sha1));
 192                         break;
 193                 }
 194                 while (parents) {
 195                         struct commit *p = parents->item;
 196                         parse_commit(p);
 197                         if (!(p->object.flags & SEEN))
 198                                 insert_by_date(p, &list);
 199                         p->object.flags |= c->object.flags;
 200                         parents = parents->next;
 201                 }
 202         }
 203         free_commit_list(list);
 204
 205         if (!match_cnt)
 206                 die("cannot describe '%s'", sha1_to_hex(cmit->object.sha1));
 207
 208         min_match = &all_matches[0];
 209         for (cur_match = 1; cur_match < match_cnt; cur_match++) {
 210                 struct possible_tag *t = &all_matches[cur_match];
 211                 if (t->depth < min_match->depth
 212                         && t->name->prio >= min_match->name->prio)
 213                         min_match = t;
 214         }
 215         if (debug) {
 216                 for (cur_match = 0; cur_match < match_cnt; cur_match++) {
 217                         struct possible_tag *t = &all_matches[cur_match];
 218                         fprintf(stderr, " %c %8lu %s\n",
 219                                 min_match == t ? '*' : ' ',
 220                                 t->depth, t->name->path);
 221                 }
 222                 fprintf(stderr, "traversed %lu commits\n", seen_commits);
 223                 if (gave_up_on) {
 224                         fprintf(stderr,
 225                                 "more than %i tags found; listed %i most recent\n"
 226                                 "gave up search at %s\n",
 227                                 max_candidates, max_candidates,
 228                                 sha1_to_hex(gave_up_on->object.sha1));
 229                 }
 230         }
 231         printf("%s-g%s\n", min_match->name->path,
 232                    find_unique_abbrev(cmit->object.sha1, abbrev));
 233
 234         if (!last_one)
 235                 clear_commit_marks(cmit, -1);
 236 }
 237
 238 int cmd_describe(int argc, const char **argv, const char *prefix)
 239 {
 240         int i;
 241
 242         for (i = 1; i < argc; i++) {
 243                 const char *arg = argv[i];
 244
 245                 if (*arg != '-')
 246                         break;
 247                 else if (!strcmp(arg, "--debug"))
 248                         debug = 1;
 249                 else if (!strcmp(arg, "--all"))
 250                         all = 1;
 251                 else if (!strcmp(arg, "--tags"))
 252                         tags = 1;
 253                 else if (!strncmp(arg, "--abbrev=", 9)) {
 254                         abbrev = strtoul(arg + 9, NULL, 10);
 255                         if (abbrev < MINIMUM_ABBREV || 40 < abbrev)
 256                                 abbrev = DEFAULT_ABBREV;
 257                 }
 258                 else if (!strncmp(arg, "--candidates=", 13)) {
 259                         max_candidates = strtoul(arg + 13, NULL, 10);
 260                         if (max_candidates < 1)
 261                                 max_candidates = 1;
 262                         else if (max_candidates > MAX_TAGS)
 263                                 max_candidates = MAX_TAGS;
 264                 }
 265                 else
 266                         usage(describe_usage);
 267         }
 268
 269         save_commit_buffer = 0;
 270
 271         if (argc <= i)
 272                 describe("HEAD", 1);
 273         else
 274                 while (i < argc) {
 275                         describe(argv[i], (i == argc - 1));
 276                         i++;
 277                 }
 278
 279         return 0;
 280 }