Merge http://www.kernel.org/pub/scm/gitk/gitk
[git] / show-branch.c
1 #include <stdlib.h>
2 #include "cache.h"
3 #include "commit.h"
4 #include "refs.h"
5
6 static const char show_branch_usage[] =
7 "git-show-branch [--all] [--heads] [--tags] [--more=count | --list | --independent | --merge-base ] [<refs>...]";
8
9 #define UNINTERESTING   01
10
11 #define REV_SHIFT        2
12 #define MAX_REVS        29 /* should not exceed bits_per_int - REV_SHIFT */
13
14 static struct commit *interesting(struct commit_list *list)
15 {
16         while (list) {
17                 struct commit *commit = list->item;
18                 list = list->next;
19                 if (commit->object.flags & UNINTERESTING)
20                         continue;
21                 return commit;
22         }
23         return NULL;
24 }
25
26 static struct commit *pop_one_commit(struct commit_list **list_p)
27 {
28         struct commit *commit;
29         struct commit_list *list;
30         list = *list_p;
31         commit = list->item;
32         *list_p = list->next;
33         free(list);
34         return commit;
35 }
36
37 struct commit_name {
38         const char *head_name; /* which head's ancestor? */
39         int generation; /* how many parents away from head_name */
40 };
41
42 /* Name the commit as nth generation ancestor of head_name;
43  * we count only the first-parent relationship for naming purposes.
44  */
45 static void name_commit(struct commit *commit, const char *head_name, int nth)
46 {
47         struct commit_name *name;
48         if (!commit->object.util)
49                 commit->object.util = xmalloc(sizeof(struct commit_name));
50         name = commit->object.util;
51         name->head_name = head_name;
52         name->generation = nth;
53 }
54
55 /* Parent is the first parent of the commit.  We may name it
56  * as (n+1)th generation ancestor of the same head_name as
57  * commit is nth generation ancestore of, if that generation
58  * number is better than the name it already has.
59  */
60 static void name_parent(struct commit *commit, struct commit *parent)
61 {
62         struct commit_name *commit_name = commit->object.util;
63         struct commit_name *parent_name = parent->object.util;
64         if (!commit_name)
65                 return;
66         if (!parent_name ||
67             commit_name->generation + 1 < parent_name->generation)
68                 name_commit(parent, commit_name->head_name,
69                             commit_name->generation + 1);
70 }
71
72 static int name_first_parent_chain(struct commit *c)
73 {
74         int i = 0;
75         while (c) {
76                 struct commit *p;
77                 if (!c->object.util)
78                         break;
79                 if (!c->parents)
80                         break;
81                 p = c->parents->item;
82                 if (!p->object.util) {
83                         name_parent(c, p);
84                         i++;
85                 }
86                 c = p;
87         }
88         return i;
89 }
90
91 static void name_commits(struct commit_list *list,
92                          struct commit **rev,
93                          char **ref_name,
94                          int num_rev)
95 {
96         struct commit_list *cl;
97         struct commit *c;
98         int i;
99
100         /* First give names to the given heads */
101         for (cl = list; cl; cl = cl->next) {
102                 c = cl->item;
103                 if (c->object.util)
104                         continue;
105                 for (i = 0; i < num_rev; i++) {
106                         if (rev[i] == c) {
107                                 name_commit(c, ref_name[i], 0);
108                                 break;
109                         }
110                 }
111         }
112
113         /* Then commits on the first parent ancestry chain */
114         do {
115                 i = 0;
116                 for (cl = list; cl; cl = cl->next) {
117                         i += name_first_parent_chain(cl->item);
118                 }
119         } while (i);
120
121         /* Finally, any unnamed commits */
122         do {
123                 i = 0;
124                 for (cl = list; cl; cl = cl->next) {
125                         struct commit_list *parents;
126                         struct commit_name *n;
127                         int nth;
128                         c = cl->item;
129                         if (!c->object.util)
130                                 continue;
131                         n = c->object.util;
132                         parents = c->parents;
133                         nth = 0;
134                         while (parents) {
135                                 struct commit *p = parents->item;
136                                 char newname[1000], *en;
137                                 parents = parents->next;
138                                 nth++;
139                                 if (p->object.util)
140                                         continue;
141                                 en = newname;
142                                 switch (n->generation) {
143                                 case 0:
144                                         en += sprintf(en, "%s", n->head_name);
145                                         break;
146                                 case 1:
147                                         en += sprintf(en, "%s^", n->head_name);
148                                         break;
149                                 default:
150                                         en += sprintf(en, "%s~%d",
151                                                 n->head_name, n->generation);
152                                         break;
153                                 }
154                                 if (nth == 1)
155                                         en += sprintf(en, "^");
156                                 else
157                                         en += sprintf(en, "^%d", nth);
158                                 name_commit(p, strdup(newname), 0);
159                                 i++;
160                                 name_first_parent_chain(p);
161                         }
162                 }
163         } while (i);
164 }
165
166 static int mark_seen(struct commit *commit, struct commit_list **seen_p)
167 {
168         if (!commit->object.flags) {
169                 insert_by_date(commit, seen_p);
170                 return 1;
171         }
172         return 0;
173 }
174
175 static void join_revs(struct commit_list **list_p,
176                       struct commit_list **seen_p,
177                       int num_rev, int extra)
178 {
179         int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
180         int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
181
182         while (*list_p) {
183                 struct commit_list *parents;
184                 int still_interesting = !!interesting(*list_p);
185                 struct commit *commit = pop_one_commit(list_p);
186                 int flags = commit->object.flags & all_mask;
187
188                 if (!still_interesting && extra <= 0)
189                         break;
190
191                 mark_seen(commit, seen_p);
192                 if ((flags & all_revs) == all_revs)
193                         flags |= UNINTERESTING;
194                 parents = commit->parents;
195
196                 while (parents) {
197                         struct commit *p = parents->item;
198                         int this_flag = p->object.flags;
199                         parents = parents->next;
200                         if ((this_flag & flags) == flags)
201                                 continue;
202                         if (!p->object.parsed)
203                                 parse_commit(p);
204                         if (mark_seen(p, seen_p) && !still_interesting)
205                                 extra--;
206                         p->object.flags |= flags;
207                         insert_by_date(p, list_p);
208                 }
209         }
210
211         /*
212          * Postprocess to complete well-poisoning.
213          *
214          * At this point we have all the commits we have seen in
215          * seen_p list (which happens to be sorted chronologically but
216          * it does not really matter).  Mark anything that can be
217          * reached from uninteresting commits not interesting.
218          */
219         for (;;) {
220                 int changed = 0;
221                 struct commit_list *s;
222                 for (s = *seen_p; s; s = s->next) {
223                         struct commit *c = s->item;
224                         struct commit_list *parents;
225
226                         if (((c->object.flags & all_revs) != all_revs) &&
227                             !(c->object.flags & UNINTERESTING))
228                                 continue;
229
230                         /* The current commit is either a merge base or
231                          * already uninteresting one.  Mark its parents
232                          * as uninteresting commits _only_ if they are
233                          * already parsed.  No reason to find new ones
234                          * here.
235                          */
236                         parents = c->parents;
237                         while (parents) {
238                                 struct commit *p = parents->item;
239                                 parents = parents->next;
240                                 if (!(p->object.flags & UNINTERESTING)) {
241                                         p->object.flags |= UNINTERESTING;
242                                         changed = 1;
243                                 }
244                         }
245                 }
246                 if (!changed)
247                         break;
248         }
249 }
250
251 static void show_one_commit(struct commit *commit, int no_name)
252 {
253         char pretty[256], *cp;
254         struct commit_name *name = commit->object.util;
255         if (commit->object.parsed)
256                 pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0,
257                                     pretty, sizeof(pretty));
258         else
259                 strcpy(pretty, "(unavailable)");
260         if (!strncmp(pretty, "[PATCH] ", 8))
261                 cp = pretty + 8;
262         else
263                 cp = pretty;
264
265         if (!no_name) {
266                 if (name && name->head_name) {
267                         printf("[%s", name->head_name);
268                         if (name->generation) {
269                                 if (name->generation == 1)
270                                         printf("^");
271                                 else
272                                         printf("~%d", name->generation);
273                         }
274                         printf("] ");
275                 }
276                 else
277                         printf("[%s] ",
278                                find_unique_abbrev(commit->object.sha1, 7));
279         }
280         puts(cp);
281 }
282
283 static char *ref_name[MAX_REVS + 1];
284 static int ref_name_cnt;
285
286 static int compare_ref_name(const void *a_, const void *b_)
287 {
288         const char * const*a = a_, * const*b = b_;
289         return strcmp(*a, *b);
290 }
291
292 static void sort_ref_range(int bottom, int top)
293 {
294         qsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]),
295               compare_ref_name);
296 }
297
298 static int append_ref(const char *refname, const unsigned char *sha1)
299 {
300         struct commit *commit = lookup_commit_reference_gently(sha1, 1);
301         if (!commit)
302                 return 0;
303         if (MAX_REVS <= ref_name_cnt) {
304                 fprintf(stderr, "warning: ignoring %s; "
305                         "cannot handle more than %d refs",
306                         refname, MAX_REVS);
307                 return 0;
308         }
309         ref_name[ref_name_cnt++] = strdup(refname);
310         ref_name[ref_name_cnt] = NULL;
311         return 0;
312 }
313
314 static int append_head_ref(const char *refname, const unsigned char *sha1)
315 {
316         unsigned char tmp[20];
317         int ofs = 11;
318         if (strncmp(refname, "refs/heads/", ofs))
319                 return 0;
320         /* If both heads/foo and tags/foo exists, get_sha1 would
321          * get confused.
322          */
323         if (get_sha1(refname + ofs, tmp) || memcmp(tmp, sha1, 20))
324                 ofs = 5;
325         return append_ref(refname + ofs, sha1);
326 }
327
328 static int append_tag_ref(const char *refname, const unsigned char *sha1)
329 {
330         if (strncmp(refname, "refs/tags/", 10))
331                 return 0;
332         return append_ref(refname + 5, sha1);
333 }
334
335 static void snarf_refs(int head, int tag)
336 {
337         if (head) {
338                 int orig_cnt = ref_name_cnt;
339                 for_each_ref(append_head_ref);
340                 sort_ref_range(orig_cnt, ref_name_cnt);
341         }
342         if (tag) {
343                 int orig_cnt = ref_name_cnt;
344                 for_each_ref(append_tag_ref);
345                 sort_ref_range(orig_cnt, ref_name_cnt);
346         }
347 }
348
349 static int rev_is_head(char *head_path, int headlen,
350                        char *name,
351                        unsigned char *head_sha1, unsigned char *sha1)
352 {
353         int namelen;
354         if ((!head_path[0]) || memcmp(head_sha1, sha1, 20))
355                 return 0;
356         namelen = strlen(name);
357         if ((headlen < namelen) ||
358             memcmp(head_path + headlen - namelen, name, namelen))
359                 return 0;
360         if (headlen == namelen ||
361             head_path[headlen - namelen - 1] == '/')
362                 return 1;
363         return 0;
364 }
365
366 static int show_merge_base(struct commit_list *seen, int num_rev)
367 {
368         int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
369         int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
370         int exit_status = 1;
371
372         while (seen) {
373                 struct commit *commit = pop_one_commit(&seen);
374                 int flags = commit->object.flags & all_mask;
375                 if (!(flags & UNINTERESTING) &&
376                     ((flags & all_revs) == all_revs)) {
377                         puts(sha1_to_hex(commit->object.sha1));
378                         exit_status = 0;
379                         commit->object.flags |= UNINTERESTING;
380                 }
381         }
382         return exit_status;
383 }
384
385 static int show_independent(struct commit **rev,
386                             int num_rev,
387                             char **ref_name,
388                             unsigned int *rev_mask)
389 {
390         int i;
391
392         for (i = 0; i < num_rev; i++) {
393                 struct commit *commit = rev[i];
394                 unsigned int flag = rev_mask[i];
395
396                 if (commit->object.flags == flag)
397                         puts(sha1_to_hex(commit->object.sha1));
398                 commit->object.flags |= UNINTERESTING;
399         }
400         return 0;
401 }
402
403 int main(int ac, char **av)
404 {
405         struct commit *rev[MAX_REVS], *commit;
406         struct commit_list *list = NULL, *seen = NULL;
407         unsigned int rev_mask[MAX_REVS];
408         int num_rev, i, extra = 0;
409         int all_heads = 0, all_tags = 0;
410         int all_mask, all_revs;
411         char head_path[128];
412         const char *head_path_p;
413         int head_path_len;
414         unsigned char head_sha1[20];
415         int merge_base = 0;
416         int independent = 0;
417         int no_name = 0;
418         int sha1_name = 0;
419         int shown_merge_point = 0;
420         int topo_order = 0;
421
422         setup_git_directory();
423
424         while (1 < ac && av[1][0] == '-') {
425                 char *arg = av[1];
426                 if (!strcmp(arg, "--all"))
427                         all_heads = all_tags = 1;
428                 else if (!strcmp(arg, "--heads"))
429                         all_heads = 1;
430                 else if (!strcmp(arg, "--tags"))
431                         all_tags = 1;
432                 else if (!strcmp(arg, "--more"))
433                         extra = 1;
434                 else if (!strcmp(arg, "--list"))
435                         extra = -1;
436                 else if (!strcmp(arg, "--no-name"))
437                         no_name = 1;
438                 else if (!strcmp(arg, "--sha1-name"))
439                         sha1_name = 1;
440                 else if (!strncmp(arg, "--more=", 7))
441                         extra = atoi(arg + 7);
442                 else if (!strcmp(arg, "--merge-base"))
443                         merge_base = 1;
444                 else if (!strcmp(arg, "--independent"))
445                         independent = 1;
446                 else if (!strcmp(arg, "--topo-order"))
447                         topo_order = 1;
448                 else
449                         usage(show_branch_usage);
450                 ac--; av++;
451         }
452         ac--; av++;
453
454         /* Only one of these is allowed */
455         if (1 < independent + merge_base + (extra != 0))
456                 usage(show_branch_usage);
457
458         if (all_heads + all_tags)
459                 snarf_refs(all_heads, all_tags);
460
461         while (0 < ac) {
462                 unsigned char revkey[20];
463                 if (get_sha1(*av, revkey))
464                         die("bad sha1 reference %s", *av);
465                 append_ref(*av, revkey);
466                 ac--; av++;
467         }
468
469         /* If still no revs, then add heads */
470         if (!ref_name_cnt)
471                 snarf_refs(1, 0);
472
473         for (num_rev = 0; ref_name[num_rev]; num_rev++) {
474                 unsigned char revkey[20];
475                 unsigned int flag = 1u << (num_rev + REV_SHIFT);
476
477                 if (MAX_REVS <= num_rev)
478                         die("cannot handle more than %d revs.", MAX_REVS);
479                 if (get_sha1(ref_name[num_rev], revkey))
480                         die("'%s' is not a valid ref.\n", ref_name[num_rev]);
481                 commit = lookup_commit_reference(revkey);
482                 if (!commit)
483                         die("cannot find commit %s (%s)",
484                             ref_name[num_rev], revkey);
485                 parse_commit(commit);
486                 mark_seen(commit, &seen);
487
488                 /* rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1,
489                  * and so on.  REV_SHIFT bits from bit 0 are used for
490                  * internal bookkeeping.
491                  */
492                 commit->object.flags |= flag;
493                 if (commit->object.flags == flag)
494                         insert_by_date(commit, &list);
495                 rev[num_rev] = commit;
496         }
497         for (i = 0; i < num_rev; i++)
498                 rev_mask[i] = rev[i]->object.flags;
499
500         if (0 <= extra)
501                 join_revs(&list, &seen, num_rev, extra);
502
503         head_path_p = resolve_ref(git_path("HEAD"), head_sha1, 1);
504         if (head_path_p) {
505                 head_path_len = strlen(head_path_p);
506                 memcpy(head_path, head_path_p, head_path_len + 1);
507         }
508         else {
509                 head_path_len = 0;
510                 head_path[0] = 0;
511         }
512
513         if (merge_base)
514                 return show_merge_base(seen, num_rev);
515
516         if (independent)
517                 return show_independent(rev, num_rev, ref_name, rev_mask);
518
519         /* Show list; --more=-1 means list-only */
520         if (1 < num_rev || extra < 0) {
521                 for (i = 0; i < num_rev; i++) {
522                         int j;
523                         int is_head = rev_is_head(head_path,
524                                                   head_path_len,
525                                                   ref_name[i],
526                                                   head_sha1,
527                                                   rev[i]->object.sha1);
528                         if (extra < 0)
529                                 printf("%c [%s] ",
530                                        is_head ? '*' : ' ', ref_name[i]);
531                         else {
532                                 for (j = 0; j < i; j++)
533                                         putchar(' ');
534                                 printf("%c [%s] ",
535                                        is_head ? '*' : '!', ref_name[i]);
536                         }
537                         /* header lines never need name */
538                         show_one_commit(rev[i], 1);
539                 }
540                 if (0 <= extra) {
541                         for (i = 0; i < num_rev; i++)
542                                 putchar('-');
543                         putchar('\n');
544                 }
545         }
546         if (extra < 0)
547                 exit(0);
548
549         /* Sort topologically */
550         if (topo_order)
551                 sort_in_topological_order(&seen);
552
553         /* Give names to commits */
554         if (!sha1_name && !no_name)
555                 name_commits(seen, rev, ref_name, num_rev);
556
557         all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
558         all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
559
560         while (seen) {
561                 struct commit *commit = pop_one_commit(&seen);
562                 int this_flag = commit->object.flags;
563
564                 shown_merge_point |= ((this_flag & all_revs) == all_revs);
565
566                 if (1 < num_rev) {
567                         for (i = 0; i < num_rev; i++)
568                                 putchar((this_flag & (1u << (i + REV_SHIFT)))
569                                         ? '+' : ' ');
570                         putchar(' ');
571                 }
572                 show_one_commit(commit, no_name);
573
574                 if (shown_merge_point && --extra < 0)
575                         break;
576         }
577         return 0;
578 }