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