user-manual: finding commits referencing given file content
[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 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 }