Merge branch 'master' into next
[git] / show-branch.c
1 #include <stdlib.h>
2 #include <fnmatch.h>
3 #include "cache.h"
4 #include "commit.h"
5 #include "refs.h"
6
7 static const char show_branch_usage[] =
8 "git-show-branch [--current] [--all] [--heads] [--tags] [--topo-order] [--more=count | --list | --independent | --merge-base ] [--topics] [<refs>...]";
9
10 static int default_num = 0;
11 static int default_alloc = 0;
12 static char **default_arg = NULL;
13
14 #define UNINTERESTING   01
15
16 #define REV_SHIFT        2
17 #define MAX_REVS        29 /* should not exceed bits_per_int - REV_SHIFT */
18
19 static struct commit *interesting(struct commit_list *list)
20 {
21         while (list) {
22                 struct commit *commit = list->item;
23                 list = list->next;
24                 if (commit->object.flags & UNINTERESTING)
25                         continue;
26                 return commit;
27         }
28         return NULL;
29 }
30
31 static struct commit *pop_one_commit(struct commit_list **list_p)
32 {
33         struct commit *commit;
34         struct commit_list *list;
35         list = *list_p;
36         commit = list->item;
37         *list_p = list->next;
38         free(list);
39         return commit;
40 }
41
42 struct commit_name {
43         const char *head_name; /* which head's ancestor? */
44         int generation; /* how many parents away from head_name */
45 };
46
47 /* Name the commit as nth generation ancestor of head_name;
48  * we count only the first-parent relationship for naming purposes.
49  */
50 static void name_commit(struct commit *commit, const char *head_name, int nth)
51 {
52         struct commit_name *name;
53         if (!commit->object.util)
54                 commit->object.util = xmalloc(sizeof(struct commit_name));
55         name = commit->object.util;
56         name->head_name = head_name;
57         name->generation = nth;
58 }
59
60 /* Parent is the first parent of the commit.  We may name it
61  * as (n+1)th generation ancestor of the same head_name as
62  * commit is nth generation ancestor of, if that generation
63  * number is better than the name it already has.
64  */
65 static void name_parent(struct commit *commit, struct commit *parent)
66 {
67         struct commit_name *commit_name = commit->object.util;
68         struct commit_name *parent_name = parent->object.util;
69         if (!commit_name)
70                 return;
71         if (!parent_name ||
72             commit_name->generation + 1 < parent_name->generation)
73                 name_commit(parent, commit_name->head_name,
74                             commit_name->generation + 1);
75 }
76
77 static int name_first_parent_chain(struct commit *c)
78 {
79         int i = 0;
80         while (c) {
81                 struct commit *p;
82                 if (!c->object.util)
83                         break;
84                 if (!c->parents)
85                         break;
86                 p = c->parents->item;
87                 if (!p->object.util) {
88                         name_parent(c, p);
89                         i++;
90                 }
91                 c = p;
92         }
93         return i;
94 }
95
96 static void name_commits(struct commit_list *list,
97                          struct commit **rev,
98                          char **ref_name,
99                          int num_rev)
100 {
101         struct commit_list *cl;
102         struct commit *c;
103         int i;
104
105         /* First give names to the given heads */
106         for (cl = list; cl; cl = cl->next) {
107                 c = cl->item;
108                 if (c->object.util)
109                         continue;
110                 for (i = 0; i < num_rev; i++) {
111                         if (rev[i] == c) {
112                                 name_commit(c, ref_name[i], 0);
113                                 break;
114                         }
115                 }
116         }
117
118         /* Then commits on the first parent ancestry chain */
119         do {
120                 i = 0;
121                 for (cl = list; cl; cl = cl->next) {
122                         i += name_first_parent_chain(cl->item);
123                 }
124         } while (i);
125
126         /* Finally, any unnamed commits */
127         do {
128                 i = 0;
129                 for (cl = list; cl; cl = cl->next) {
130                         struct commit_list *parents;
131                         struct commit_name *n;
132                         int nth;
133                         c = cl->item;
134                         if (!c->object.util)
135                                 continue;
136                         n = c->object.util;
137                         parents = c->parents;
138                         nth = 0;
139                         while (parents) {
140                                 struct commit *p = parents->item;
141                                 char newname[1000], *en;
142                                 parents = parents->next;
143                                 nth++;
144                                 if (p->object.util)
145                                         continue;
146                                 en = newname;
147                                 switch (n->generation) {
148                                 case 0:
149                                         en += sprintf(en, "%s", n->head_name);
150                                         break;
151                                 case 1:
152                                         en += sprintf(en, "%s^", n->head_name);
153                                         break;
154                                 default:
155                                         en += sprintf(en, "%s~%d",
156                                                 n->head_name, n->generation);
157                                         break;
158                                 }
159                                 if (nth == 1)
160                                         en += sprintf(en, "^");
161                                 else
162                                         en += sprintf(en, "^%d", nth);
163                                 name_commit(p, strdup(newname), 0);
164                                 i++;
165                                 name_first_parent_chain(p);
166                         }
167                 }
168         } while (i);
169 }
170
171 static int mark_seen(struct commit *commit, struct commit_list **seen_p)
172 {
173         if (!commit->object.flags) {
174                 insert_by_date(commit, seen_p);
175                 return 1;
176         }
177         return 0;
178 }
179
180 static void join_revs(struct commit_list **list_p,
181                       struct commit_list **seen_p,
182                       int num_rev, int extra)
183 {
184         int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
185         int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
186
187         while (*list_p) {
188                 struct commit_list *parents;
189                 int still_interesting = !!interesting(*list_p);
190                 struct commit *commit = pop_one_commit(list_p);
191                 int flags = commit->object.flags & all_mask;
192
193                 if (!still_interesting && extra <= 0)
194                         break;
195
196                 mark_seen(commit, seen_p);
197                 if ((flags & all_revs) == all_revs)
198                         flags |= UNINTERESTING;
199                 parents = commit->parents;
200
201                 while (parents) {
202                         struct commit *p = parents->item;
203                         int this_flag = p->object.flags;
204                         parents = parents->next;
205                         if ((this_flag & flags) == flags)
206                                 continue;
207                         if (!p->object.parsed)
208                                 parse_commit(p);
209                         if (mark_seen(p, seen_p) && !still_interesting)
210                                 extra--;
211                         p->object.flags |= flags;
212                         insert_by_date(p, list_p);
213                 }
214         }
215
216         /*
217          * Postprocess to complete well-poisoning.
218          *
219          * At this point we have all the commits we have seen in
220          * seen_p list (which happens to be sorted chronologically but
221          * it does not really matter).  Mark anything that can be
222          * reached from uninteresting commits not interesting.
223          */
224         for (;;) {
225                 int changed = 0;
226                 struct commit_list *s;
227                 for (s = *seen_p; s; s = s->next) {
228                         struct commit *c = s->item;
229                         struct commit_list *parents;
230
231                         if (((c->object.flags & all_revs) != all_revs) &&
232                             !(c->object.flags & UNINTERESTING))
233                                 continue;
234
235                         /* The current commit is either a merge base or
236                          * already uninteresting one.  Mark its parents
237                          * as uninteresting commits _only_ if they are
238                          * already parsed.  No reason to find new ones
239                          * here.
240                          */
241                         parents = c->parents;
242                         while (parents) {
243                                 struct commit *p = parents->item;
244                                 parents = parents->next;
245                                 if (!(p->object.flags & UNINTERESTING)) {
246                                         p->object.flags |= UNINTERESTING;
247                                         changed = 1;
248                                 }
249                         }
250                 }
251                 if (!changed)
252                         break;
253         }
254 }
255
256 static void show_one_commit(struct commit *commit, int no_name)
257 {
258         char pretty[256], *cp;
259         struct commit_name *name = commit->object.util;
260         if (commit->object.parsed)
261                 pretty_print_commit(CMIT_FMT_ONELINE, commit, ~0,
262                                     pretty, sizeof(pretty), 0);
263         else
264                 strcpy(pretty, "(unavailable)");
265         if (!strncmp(pretty, "[PATCH] ", 8))
266                 cp = pretty + 8;
267         else
268                 cp = pretty;
269
270         if (!no_name) {
271                 if (name && name->head_name) {
272                         printf("[%s", name->head_name);
273                         if (name->generation) {
274                                 if (name->generation == 1)
275                                         printf("^");
276                                 else
277                                         printf("~%d", name->generation);
278                         }
279                         printf("] ");
280                 }
281                 else
282                         printf("[%s] ",
283                                find_unique_abbrev(commit->object.sha1, 7));
284         }
285         puts(cp);
286 }
287
288 static char *ref_name[MAX_REVS + 1];
289 static int ref_name_cnt;
290
291 static const char *find_digit_prefix(const char *s, int *v)
292 {
293         const char *p;
294         int ver;
295         char ch;
296
297         for (p = s, ver = 0;
298              '0' <= (ch = *p) && ch <= '9';
299              p++)
300                 ver = ver * 10 + ch - '0';
301         *v = ver;
302         return p;
303 }
304
305
306 static int version_cmp(const char *a, const char *b)
307 {
308         while (1) {
309                 int va, vb;
310
311                 a = find_digit_prefix(a, &va);
312                 b = find_digit_prefix(b, &vb);
313                 if (va != vb)
314                         return va - vb;
315
316                 while (1) {
317                         int ca = *a;
318                         int cb = *b;
319                         if ('0' <= ca && ca <= '9')
320                                 ca = 0;
321                         if ('0' <= cb && cb <= '9')
322                                 cb = 0;
323                         if (ca != cb)
324                                 return ca - cb;
325                         if (!ca)
326                                 break;
327                         a++;
328                         b++;
329                 }
330                 if (!*a && !*b)
331                         return 0;
332         }
333 }
334
335 static int compare_ref_name(const void *a_, const void *b_)
336 {
337         const char * const*a = a_, * const*b = b_;
338         return version_cmp(*a, *b);
339 }
340
341 static void sort_ref_range(int bottom, int top)
342 {
343         qsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]),
344               compare_ref_name);
345 }
346
347 static int append_ref(const char *refname, const unsigned char *sha1)
348 {
349         struct commit *commit = lookup_commit_reference_gently(sha1, 1);
350         int i;
351
352         if (!commit)
353                 return 0;
354         /* Avoid adding the same thing twice */
355         for (i = 0; i < ref_name_cnt; i++)
356                 if (!strcmp(refname, ref_name[i]))
357                         return 0;
358
359         if (MAX_REVS <= ref_name_cnt) {
360                 fprintf(stderr, "warning: ignoring %s; "
361                         "cannot handle more than %d refs\n",
362                         refname, MAX_REVS);
363                 return 0;
364         }
365         ref_name[ref_name_cnt++] = strdup(refname);
366         ref_name[ref_name_cnt] = NULL;
367         return 0;
368 }
369
370 static int append_head_ref(const char *refname, const unsigned char *sha1)
371 {
372         unsigned char tmp[20];
373         int ofs = 11;
374         if (strncmp(refname, "refs/heads/", ofs))
375                 return 0;
376         /* If both heads/foo and tags/foo exists, get_sha1 would
377          * get confused.
378          */
379         if (get_sha1(refname + ofs, tmp) || memcmp(tmp, sha1, 20))
380                 ofs = 5;
381         return append_ref(refname + ofs, sha1);
382 }
383
384 static int append_tag_ref(const char *refname, const unsigned char *sha1)
385 {
386         if (strncmp(refname, "refs/tags/", 10))
387                 return 0;
388         return append_ref(refname + 5, sha1);
389 }
390
391 static const char *match_ref_pattern = NULL;
392 static int match_ref_slash = 0;
393 static int count_slash(const char *s)
394 {
395         int cnt = 0;
396         while (*s)
397                 if (*s++ == '/')
398                         cnt++;
399         return cnt;
400 }
401
402 static int append_matching_ref(const char *refname, const unsigned char *sha1)
403 {
404         /* we want to allow pattern hold/<asterisk> to show all
405          * branches under refs/heads/hold/, and v0.99.9? to show
406          * refs/tags/v0.99.9a and friends.
407          */
408         const char *tail;
409         int slash = count_slash(refname);
410         for (tail = refname; *tail && match_ref_slash < slash; )
411                 if (*tail++ == '/')
412                         slash--;
413         if (!*tail)
414                 return 0;
415         if (fnmatch(match_ref_pattern, tail, 0))
416                 return 0;
417         if (!strncmp("refs/heads/", refname, 11))
418                 return append_head_ref(refname, sha1);
419         if (!strncmp("refs/tags/", refname, 10))
420                 return append_tag_ref(refname, sha1);
421         return append_ref(refname, sha1);
422 }
423
424 static void snarf_refs(int head, int tag)
425 {
426         if (head) {
427                 int orig_cnt = ref_name_cnt;
428                 for_each_ref(append_head_ref);
429                 sort_ref_range(orig_cnt, ref_name_cnt);
430         }
431         if (tag) {
432                 int orig_cnt = ref_name_cnt;
433                 for_each_ref(append_tag_ref);
434                 sort_ref_range(orig_cnt, ref_name_cnt);
435         }
436 }
437
438 static int rev_is_head(char *head_path, int headlen, char *name,
439                        unsigned char *head_sha1, unsigned char *sha1)
440 {
441         int namelen;
442         if ((!head_path[0]) ||
443             (head_sha1 && sha1 && memcmp(head_sha1, sha1, 20)))
444                 return 0;
445         namelen = strlen(name);
446         if ((headlen < namelen) ||
447             memcmp(head_path + headlen - namelen, name, namelen))
448                 return 0;
449         if (headlen == namelen ||
450             head_path[headlen - namelen - 1] == '/')
451                 return 1;
452         return 0;
453 }
454
455 static int show_merge_base(struct commit_list *seen, int num_rev)
456 {
457         int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
458         int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
459         int exit_status = 1;
460
461         while (seen) {
462                 struct commit *commit = pop_one_commit(&seen);
463                 int flags = commit->object.flags & all_mask;
464                 if (!(flags & UNINTERESTING) &&
465                     ((flags & all_revs) == all_revs)) {
466                         puts(sha1_to_hex(commit->object.sha1));
467                         exit_status = 0;
468                         commit->object.flags |= UNINTERESTING;
469                 }
470         }
471         return exit_status;
472 }
473
474 static int show_independent(struct commit **rev,
475                             int num_rev,
476                             char **ref_name,
477                             unsigned int *rev_mask)
478 {
479         int i;
480
481         for (i = 0; i < num_rev; i++) {
482                 struct commit *commit = rev[i];
483                 unsigned int flag = rev_mask[i];
484
485                 if (commit->object.flags == flag)
486                         puts(sha1_to_hex(commit->object.sha1));
487                 commit->object.flags |= UNINTERESTING;
488         }
489         return 0;
490 }
491
492 static void append_one_rev(const char *av)
493 {
494         unsigned char revkey[20];
495         if (!get_sha1(av, revkey)) {
496                 append_ref(av, revkey);
497                 return;
498         }
499         if (strchr(av, '*') || strchr(av, '?') || strchr(av, '[')) {
500                 /* glob style match */
501                 int saved_matches = ref_name_cnt;
502                 match_ref_pattern = av;
503                 match_ref_slash = count_slash(av);
504                 for_each_ref(append_matching_ref);
505                 if (saved_matches == ref_name_cnt &&
506                     ref_name_cnt < MAX_REVS)
507                         error("no matching refs with %s", av);
508                 if (saved_matches + 1 < ref_name_cnt)
509                         sort_ref_range(saved_matches, ref_name_cnt);
510                 return;
511         }
512         die("bad sha1 reference %s", av);
513 }
514
515 static int git_show_branch_config(const char *var, const char *value)
516 {
517         if (!strcmp(var, "showbranch.default")) {
518                 if (default_alloc <= default_num + 1) {
519                         default_alloc = default_alloc * 3 / 2 + 20;
520                         default_arg = xrealloc(default_arg, sizeof *default_arg * default_alloc);
521                 }
522                 default_arg[default_num++] = strdup(value);
523                 default_arg[default_num] = NULL;
524                 return 0;
525         }
526
527         return git_default_config(var, value);
528 }
529
530 int main(int ac, char **av)
531 {
532         struct commit *rev[MAX_REVS], *commit;
533         struct commit_list *list = NULL, *seen = NULL;
534         unsigned int rev_mask[MAX_REVS];
535         int num_rev, i, extra = 0;
536         int all_heads = 0, all_tags = 0;
537         int all_mask, all_revs;
538         int lifo = 1;
539         char head_path[128];
540         const char *head_path_p;
541         int head_path_len;
542         unsigned char head_sha1[20];
543         int merge_base = 0;
544         int independent = 0;
545         int no_name = 0;
546         int sha1_name = 0;
547         int shown_merge_point = 0;
548         int with_current_branch = 0;
549         int head_at = -1;
550         int topics = 0;
551
552         setup_git_directory();
553         git_config(git_show_branch_config);
554
555         /* If nothing is specified, try the default first */
556         if (ac == 1 && default_num) {
557                 ac = default_num + 1;
558                 av = default_arg - 1; /* ick; we would not address av[0] */
559         }
560
561         while (1 < ac && av[1][0] == '-') {
562                 char *arg = av[1];
563                 if (!strcmp(arg, "--")) {
564                         ac--; av++;
565                         break;
566                 }
567                 else if (!strcmp(arg, "--all"))
568                         all_heads = all_tags = 1;
569                 else if (!strcmp(arg, "--heads"))
570                         all_heads = 1;
571                 else if (!strcmp(arg, "--tags"))
572                         all_tags = 1;
573                 else if (!strcmp(arg, "--more"))
574                         extra = 1;
575                 else if (!strcmp(arg, "--list"))
576                         extra = -1;
577                 else if (!strcmp(arg, "--no-name"))
578                         no_name = 1;
579                 else if (!strcmp(arg, "--current"))
580                         with_current_branch = 1;
581                 else if (!strcmp(arg, "--sha1-name"))
582                         sha1_name = 1;
583                 else if (!strncmp(arg, "--more=", 7))
584                         extra = atoi(arg + 7);
585                 else if (!strcmp(arg, "--merge-base"))
586                         merge_base = 1;
587                 else if (!strcmp(arg, "--independent"))
588                         independent = 1;
589                 else if (!strcmp(arg, "--topo-order"))
590                         lifo = 1;
591                 else if (!strcmp(arg, "--topics"))
592                         topics = 1;
593                 else if (!strcmp(arg, "--date-order"))
594                         lifo = 0;
595                 else
596                         usage(show_branch_usage);
597                 ac--; av++;
598         }
599         ac--; av++;
600
601         /* Only one of these is allowed */
602         if (1 < independent + merge_base + (extra != 0))
603                 usage(show_branch_usage);
604
605         /* If nothing is specified, show all branches by default */
606         if (ac + all_heads + all_tags == 0)
607                 all_heads = 1;
608
609         if (all_heads + all_tags)
610                 snarf_refs(all_heads, all_tags);
611         while (0 < ac) {
612                 append_one_rev(*av);
613                 ac--; av++;
614         }
615
616         head_path_p = resolve_ref(git_path("HEAD"), head_sha1, 1);
617         if (head_path_p) {
618                 head_path_len = strlen(head_path_p);
619                 memcpy(head_path, head_path_p, head_path_len + 1);
620         }
621         else {
622                 head_path_len = 0;
623                 head_path[0] = 0;
624         }
625
626         if (with_current_branch && head_path_p) {
627                 int has_head = 0;
628                 for (i = 0; !has_head && i < ref_name_cnt; i++) {
629                         /* We are only interested in adding the branch
630                          * HEAD points at.
631                          */
632                         if (rev_is_head(head_path,
633                                         head_path_len,
634                                         ref_name[i],
635                                         head_sha1, NULL))
636                                 has_head++;
637                 }
638                 if (!has_head) {
639                         int pfxlen = strlen(git_path("refs/heads/"));
640                         append_one_rev(head_path + pfxlen);
641                 }
642         }
643
644         if (!ref_name_cnt) {
645                 fprintf(stderr, "No revs to be shown.\n");
646                 exit(0);
647         }
648
649         for (num_rev = 0; ref_name[num_rev]; num_rev++) {
650                 unsigned char revkey[20];
651                 unsigned int flag = 1u << (num_rev + REV_SHIFT);
652
653                 if (MAX_REVS <= num_rev)
654                         die("cannot handle more than %d revs.", MAX_REVS);
655                 if (get_sha1(ref_name[num_rev], revkey))
656                         die("'%s' is not a valid ref.", ref_name[num_rev]);
657                 commit = lookup_commit_reference(revkey);
658                 if (!commit)
659                         die("cannot find commit %s (%s)",
660                             ref_name[num_rev], revkey);
661                 parse_commit(commit);
662                 mark_seen(commit, &seen);
663
664                 /* rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1,
665                  * and so on.  REV_SHIFT bits from bit 0 are used for
666                  * internal bookkeeping.
667                  */
668                 commit->object.flags |= flag;
669                 if (commit->object.flags == flag)
670                         insert_by_date(commit, &list);
671                 rev[num_rev] = commit;
672         }
673         for (i = 0; i < num_rev; i++)
674                 rev_mask[i] = rev[i]->object.flags;
675
676         if (0 <= extra)
677                 join_revs(&list, &seen, num_rev, extra);
678
679         if (merge_base)
680                 return show_merge_base(seen, num_rev);
681
682         if (independent)
683                 return show_independent(rev, num_rev, ref_name, rev_mask);
684
685         /* Show list; --more=-1 means list-only */
686         if (1 < num_rev || extra < 0) {
687                 for (i = 0; i < num_rev; i++) {
688                         int j;
689                         int is_head = rev_is_head(head_path,
690                                                   head_path_len,
691                                                   ref_name[i],
692                                                   head_sha1,
693                                                   rev[i]->object.sha1);
694                         if (extra < 0)
695                                 printf("%c [%s] ",
696                                        is_head ? '*' : ' ', ref_name[i]);
697                         else {
698                                 for (j = 0; j < i; j++)
699                                         putchar(' ');
700                                 printf("%c [%s] ",
701                                        is_head ? '*' : '!', ref_name[i]);
702                         }
703                         /* header lines never need name */
704                         show_one_commit(rev[i], 1);
705                         if (is_head)
706                                 head_at = i;
707                 }
708                 if (0 <= extra) {
709                         for (i = 0; i < num_rev; i++)
710                                 putchar('-');
711                         putchar('\n');
712                 }
713         }
714         if (extra < 0)
715                 exit(0);
716
717         /* Sort topologically */
718         sort_in_topological_order(&seen, lifo);
719
720         /* Give names to commits */
721         if (!sha1_name && !no_name)
722                 name_commits(seen, rev, ref_name, num_rev);
723
724         all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
725         all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
726
727         while (seen) {
728                 struct commit *commit = pop_one_commit(&seen);
729                 int this_flag = commit->object.flags;
730                 int is_merge_point = ((this_flag & all_revs) == all_revs);
731
732                 shown_merge_point |= is_merge_point;
733
734                 if (1 < num_rev) {
735                         int is_merge = !!(commit->parents && commit->parents->next);
736                         if (topics &&
737                             !is_merge_point &&
738                             (this_flag & (1u << REV_SHIFT)))
739                                 continue;
740
741                         for (i = 0; i < num_rev; i++) {
742                                 int mark;
743                                 if (!(this_flag & (1u << (i + REV_SHIFT))))
744                                         mark = ' ';
745                                 else if (is_merge)
746                                         mark = '-';
747                                 else if (i == head_at)
748                                         mark = '*';
749                                 else
750                                         mark = '+';
751                                 putchar(mark);
752                         }
753                         putchar(' ');
754                 }
755                 show_one_commit(commit, no_name);
756
757                 if (shown_merge_point && --extra < 0)
758                         break;
759         }
760         return 0;
761 }