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