builtin-describe.c

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