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