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