Merge branch 'lc/filter-branch-too-many-refs'
[git] / builtin / name-rev.c
1 #include "builtin.h"
2 #include "cache.h"
3 #include "commit.h"
4 #include "tag.h"
5 #include "refs.h"
6 #include "parse-options.h"
7 #include "sha1-lookup.h"
8
9 #define CUTOFF_DATE_SLOP 86400 /* one day */
10
11 typedef struct rev_name {
12         const char *tip_name;
13         int generation;
14         int distance;
15 } rev_name;
16
17 static long cutoff = LONG_MAX;
18
19 /* How many generations are maximally preferred over _one_ merge traversal? */
20 #define MERGE_TRAVERSAL_WEIGHT 65535
21
22 static void name_rev(struct commit *commit,
23                 const char *tip_name, int generation, int distance,
24                 int deref)
25 {
26         struct rev_name *name = (struct rev_name *)commit->util;
27         struct commit_list *parents;
28         int parent_number = 1;
29
30         if (!commit->object.parsed)
31                 parse_commit(commit);
32
33         if (commit->date < cutoff)
34                 return;
35
36         if (deref) {
37                 char *new_name = xmalloc(strlen(tip_name)+3);
38                 strcpy(new_name, tip_name);
39                 strcat(new_name, "^0");
40                 tip_name = new_name;
41
42                 if (generation)
43                         die("generation: %d, but deref?", generation);
44         }
45
46         if (name == NULL) {
47                 name = xmalloc(sizeof(rev_name));
48                 commit->util = name;
49                 goto copy_data;
50         } else if (name->distance > distance) {
51 copy_data:
52                 name->tip_name = tip_name;
53                 name->generation = generation;
54                 name->distance = distance;
55         } else
56                 return;
57
58         for (parents = commit->parents;
59                         parents;
60                         parents = parents->next, parent_number++) {
61                 if (parent_number > 1) {
62                         int len = strlen(tip_name);
63                         char *new_name = xmalloc(len +
64                                 1 + decimal_length(generation) +  /* ~<n> */
65                                 1 + 2 +                           /* ^NN */
66                                 1);
67
68                         if (len > 2 && !strcmp(tip_name + len - 2, "^0"))
69                                 len -= 2;
70                         if (generation > 0)
71                                 sprintf(new_name, "%.*s~%d^%d", len, tip_name,
72                                                 generation, parent_number);
73                         else
74                                 sprintf(new_name, "%.*s^%d", len, tip_name,
75                                                 parent_number);
76
77                         name_rev(parents->item, new_name, 0,
78                                 distance + MERGE_TRAVERSAL_WEIGHT, 0);
79                 } else {
80                         name_rev(parents->item, tip_name, generation + 1,
81                                 distance + 1, 0);
82                 }
83         }
84 }
85
86 static int subpath_matches(const char *path, const char *filter)
87 {
88         const char *subpath = path;
89
90         while (subpath) {
91                 if (!fnmatch(filter, subpath, 0))
92                         return subpath - path;
93                 subpath = strchr(subpath, '/');
94                 if (subpath)
95                         subpath++;
96         }
97         return -1;
98 }
99
100 static const char *name_ref_abbrev(const char *refname, int shorten_unambiguous)
101 {
102         if (shorten_unambiguous)
103                 refname = shorten_unambiguous_ref(refname, 0);
104         else if (!prefixcmp(refname, "refs/heads/"))
105                 refname = refname + 11;
106         else if (!prefixcmp(refname, "refs/"))
107                 refname = refname + 5;
108         return refname;
109 }
110
111 struct name_ref_data {
112         int tags_only;
113         int name_only;
114         const char *ref_filter;
115 };
116
117 static struct tip_table {
118         struct tip_table_entry {
119                 unsigned char sha1[20];
120                 const char *refname;
121         } *table;
122         int nr;
123         int alloc;
124         int sorted;
125 } tip_table;
126
127 static void add_to_tip_table(const unsigned char *sha1, const char *refname,
128                              int shorten_unambiguous)
129 {
130         refname = name_ref_abbrev(refname, shorten_unambiguous);
131
132         ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc);
133         hashcpy(tip_table.table[tip_table.nr].sha1, sha1);
134         tip_table.table[tip_table.nr].refname = xstrdup(refname);
135         tip_table.nr++;
136         tip_table.sorted = 0;
137 }
138
139 static int tipcmp(const void *a_, const void *b_)
140 {
141         const struct tip_table_entry *a = a_, *b = b_;
142         return hashcmp(a->sha1, b->sha1);
143 }
144
145 static int name_ref(const char *path, const unsigned char *sha1, int flags, void *cb_data)
146 {
147         struct object *o = parse_object(sha1);
148         struct name_ref_data *data = cb_data;
149         int can_abbreviate_output = data->tags_only && data->name_only;
150         int deref = 0;
151
152         if (data->tags_only && prefixcmp(path, "refs/tags/"))
153                 return 0;
154
155         if (data->ref_filter) {
156                 switch (subpath_matches(path, data->ref_filter)) {
157                 case -1: /* did not match */
158                         return 0;
159                 case 0:  /* matched fully */
160                         break;
161                 default: /* matched subpath */
162                         can_abbreviate_output = 1;
163                         break;
164                 }
165         }
166
167         add_to_tip_table(sha1, path, can_abbreviate_output);
168
169         while (o && o->type == OBJ_TAG) {
170                 struct tag *t = (struct tag *) o;
171                 if (!t->tagged)
172                         break; /* broken repository */
173                 o = parse_object(t->tagged->sha1);
174                 deref = 1;
175         }
176         if (o && o->type == OBJ_COMMIT) {
177                 struct commit *commit = (struct commit *)o;
178
179                 path = name_ref_abbrev(path, can_abbreviate_output);
180                 name_rev(commit, xstrdup(path), 0, 0, deref);
181         }
182         return 0;
183 }
184
185 static const unsigned char *nth_tip_table_ent(size_t ix, void *table_)
186 {
187         struct tip_table_entry *table = table_;
188         return table[ix].sha1;
189 }
190
191 static const char *get_exact_ref_match(const struct object *o)
192 {
193         int found;
194
195         if (!tip_table.table || !tip_table.nr)
196                 return NULL;
197
198         if (!tip_table.sorted) {
199                 qsort(tip_table.table, tip_table.nr, sizeof(*tip_table.table),
200                       tipcmp);
201                 tip_table.sorted = 1;
202         }
203
204         found = sha1_pos(o->sha1, tip_table.table, tip_table.nr,
205                          nth_tip_table_ent);
206         if (0 <= found)
207                 return tip_table.table[found].refname;
208         return NULL;
209 }
210
211 /* returns a static buffer */
212 static const char *get_rev_name(const struct object *o)
213 {
214         static char buffer[1024];
215         struct rev_name *n;
216         struct commit *c;
217
218         if (o->type != OBJ_COMMIT)
219                 return get_exact_ref_match(o);
220         c = (struct commit *) o;
221         n = c->util;
222         if (!n)
223                 return NULL;
224
225         if (!n->generation)
226                 return n->tip_name;
227         else {
228                 int len = strlen(n->tip_name);
229                 if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
230                         len -= 2;
231                 snprintf(buffer, sizeof(buffer), "%.*s~%d", len, n->tip_name,
232                                 n->generation);
233
234                 return buffer;
235         }
236 }
237
238 static void show_name(const struct object *obj,
239                       const char *caller_name,
240                       int always, int allow_undefined, int name_only)
241 {
242         const char *name;
243         const unsigned char *sha1 = obj->sha1;
244
245         if (!name_only)
246                 printf("%s ", caller_name ? caller_name : sha1_to_hex(sha1));
247         name = get_rev_name(obj);
248         if (name)
249                 printf("%s\n", name);
250         else if (allow_undefined)
251                 printf("undefined\n");
252         else if (always)
253                 printf("%s\n", find_unique_abbrev(sha1, DEFAULT_ABBREV));
254         else
255                 die("cannot describe '%s'", sha1_to_hex(sha1));
256 }
257
258 static char const * const name_rev_usage[] = {
259         N_("git name-rev [options] <commit>..."),
260         N_("git name-rev [options] --all"),
261         N_("git name-rev [options] --stdin"),
262         NULL
263 };
264
265 static void name_rev_line(char *p, struct name_ref_data *data)
266 {
267         int forty = 0;
268         char *p_start;
269         for (p_start = p; *p; p++) {
270 #define ishex(x) (isdigit((x)) || ((x) >= 'a' && (x) <= 'f'))
271                 if (!ishex(*p))
272                         forty = 0;
273                 else if (++forty == 40 &&
274                          !ishex(*(p+1))) {
275                         unsigned char sha1[40];
276                         const char *name = NULL;
277                         char c = *(p+1);
278                         int p_len = p - p_start + 1;
279
280                         forty = 0;
281
282                         *(p+1) = 0;
283                         if (!get_sha1(p - 39, sha1)) {
284                                 struct object *o =
285                                         lookup_object(sha1);
286                                 if (o)
287                                         name = get_rev_name(o);
288                         }
289                         *(p+1) = c;
290
291                         if (!name)
292                                 continue;
293
294                         if (data->name_only)
295                                 printf("%.*s%s", p_len - 40, p_start, name);
296                         else
297                                 printf("%.*s (%s)", p_len, p_start, name);
298                         p_start = p + 1;
299                 }
300         }
301
302         /* flush */
303         if (p_start != p)
304                 fwrite(p_start, p - p_start, 1, stdout);
305 }
306
307 int cmd_name_rev(int argc, const char **argv, const char *prefix)
308 {
309         struct object_array revs = OBJECT_ARRAY_INIT;
310         int all = 0, transform_stdin = 0, allow_undefined = 1, always = 0, peel_tag = 0;
311         struct name_ref_data data = { 0, 0, NULL };
312         struct option opts[] = {
313                 OPT_BOOL(0, "name-only", &data.name_only, N_("print only names (no SHA-1)")),
314                 OPT_BOOL(0, "tags", &data.tags_only, N_("only use tags to name the commits")),
315                 OPT_STRING(0, "refs", &data.ref_filter, N_("pattern"),
316                                    N_("only use refs matching <pattern>")),
317                 OPT_GROUP(""),
318                 OPT_BOOL(0, "all", &all, N_("list all commits reachable from all refs")),
319                 OPT_BOOL(0, "stdin", &transform_stdin, N_("read from stdin")),
320                 OPT_BOOL(0, "undefined", &allow_undefined, N_("allow to print `undefined` names (default)")),
321                 OPT_BOOL(0, "always",     &always,
322                            N_("show abbreviated commit object as fallback")),
323                 {
324                         /* A Hidden OPT_BOOL */
325                         OPTION_SET_INT, 0, "peel-tag", &peel_tag, NULL,
326                         N_("dereference tags in the input (internal use)"),
327                         PARSE_OPT_NOARG | PARSE_OPT_HIDDEN, NULL, 1,
328                 },
329                 OPT_END(),
330         };
331
332         git_config(git_default_config, NULL);
333         argc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);
334         if (all + transform_stdin + !!argc > 1) {
335                 error("Specify either a list, or --all, not both!");
336                 usage_with_options(name_rev_usage, opts);
337         }
338         if (all || transform_stdin)
339                 cutoff = 0;
340
341         for (; argc; argc--, argv++) {
342                 unsigned char sha1[20];
343                 struct object *object;
344                 struct commit *commit;
345
346                 if (get_sha1(*argv, sha1)) {
347                         fprintf(stderr, "Could not get sha1 for %s. Skipping.\n",
348                                         *argv);
349                         continue;
350                 }
351
352                 commit = NULL;
353                 object = parse_object(sha1);
354                 if (object) {
355                         struct object *peeled = deref_tag(object, *argv, 0);
356                         if (peeled && peeled->type == OBJ_COMMIT)
357                                 commit = (struct commit *)peeled;
358                 }
359
360                 if (!object) {
361                         fprintf(stderr, "Could not get object for %s. Skipping.\n",
362                                         *argv);
363                         continue;
364                 }
365
366                 if (commit) {
367                         if (cutoff > commit->date)
368                                 cutoff = commit->date;
369                 }
370
371                 if (peel_tag) {
372                         if (!commit) {
373                                 fprintf(stderr, "Could not get commit for %s. Skipping.\n",
374                                         *argv);
375                                 continue;
376                         }
377                         object = (struct object *)commit;
378                 }
379                 add_object_array(object, *argv, &revs);
380         }
381
382         if (cutoff)
383                 cutoff = cutoff - CUTOFF_DATE_SLOP;
384         for_each_ref(name_ref, &data);
385
386         if (transform_stdin) {
387                 char buffer[2048];
388
389                 while (!feof(stdin)) {
390                         char *p = fgets(buffer, sizeof(buffer), stdin);
391                         if (!p)
392                                 break;
393                         name_rev_line(p, &data);
394                 }
395         } else if (all) {
396                 int i, max;
397
398                 max = get_max_object_index();
399                 for (i = 0; i < max; i++) {
400                         struct object *obj = get_indexed_object(i);
401                         if (!obj || obj->type != OBJ_COMMIT)
402                                 continue;
403                         show_name(obj, NULL,
404                                   always, allow_undefined, data.name_only);
405                 }
406         } else {
407                 int i;
408                 for (i = 0; i < revs.nr; i++)
409                         show_name(revs.objects[i].item, revs.objects[i].name,
410                                   always, allow_undefined, data.name_only);
411         }
412
413         return 0;
414 }