Documentation: talk about guts of merge in tutorial.
[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                 struct commit *commit = pop_one_commit(list_p);
185                 int flags = commit->object.flags & all_mask;
186                 int still_interesting = !!interesting(*list_p);
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                         parse_commit(p);
203                         if (mark_seen(p, seen_p) && !still_interesting)
204                                 extra--;
205                         p->object.flags |= flags;
206                         insert_by_date(p, list_p);
207                 }
208         }
209 }
210
211 static void show_one_commit(struct commit *commit, int no_name)
212 {
213         char pretty[128], *cp;
214         struct commit_name *name = commit->object.util;
215         if (commit->object.parsed)
216                 pretty_print_commit(CMIT_FMT_ONELINE, commit->buffer, ~0,
217                                     pretty, sizeof(pretty));
218         else
219                 strcpy(pretty, "(unavailable)");
220         if (!strncmp(pretty, "[PATCH] ", 8))
221                 cp = pretty + 8;
222         else
223                 cp = pretty;
224
225         if (!no_name) {
226                 if (name && name->head_name) {
227                         printf("[%s", name->head_name);
228                         if (name->generation) {
229                                 if (name->generation == 1)
230                                         printf("^");
231                                 else
232                                         printf("~%d", name->generation);
233                         }
234                         printf("] ");
235                 }
236                 else
237                         printf("[%s] ",
238                                find_unique_abbrev(commit->object.sha1, 7));
239         }
240         puts(cp);
241 }
242
243 static char *ref_name[MAX_REVS + 1];
244 static int ref_name_cnt;
245
246 static int compare_ref_name(const void *a_, const void *b_)
247 {
248         const char * const*a = a_, * const*b = b_;
249         return strcmp(*a, *b);
250 }
251
252 static void sort_ref_range(int bottom, int top)
253 {
254         qsort(ref_name + bottom, top - bottom, sizeof(ref_name[0]),
255               compare_ref_name);
256 }
257
258 static int append_ref(const char *refname, const unsigned char *sha1)
259 {
260         struct commit *commit = lookup_commit_reference_gently(sha1, 1);
261         if (!commit)
262                 return 0;
263         if (MAX_REVS <= ref_name_cnt) {
264                 fprintf(stderr, "warning: ignoring %s; "
265                         "cannot handle more than %d refs",
266                         refname, MAX_REVS);
267                 return 0;
268         }
269         ref_name[ref_name_cnt++] = strdup(refname);
270         ref_name[ref_name_cnt] = NULL;
271         return 0;
272 }
273
274 static int append_head_ref(const char *refname, const unsigned char *sha1)
275 {
276         if (strncmp(refname, "refs/heads/", 11))
277                 return 0;
278         return append_ref(refname + 11, sha1);
279 }
280
281 static int append_tag_ref(const char *refname, const unsigned char *sha1)
282 {
283         if (strncmp(refname, "refs/tags/", 10))
284                 return 0;
285         return append_ref(refname + 5, sha1);
286 }
287
288 static void snarf_refs(int head, int tag)
289 {
290         if (head) {
291                 int orig_cnt = ref_name_cnt;
292                 for_each_ref(append_head_ref);
293                 sort_ref_range(orig_cnt, ref_name_cnt);
294         }
295         if (tag) {
296                 int orig_cnt = ref_name_cnt;
297                 for_each_ref(append_tag_ref);
298                 sort_ref_range(orig_cnt, ref_name_cnt);
299         }
300 }
301
302 static int rev_is_head(char *head_path, int headlen,
303                        char *name,
304                        unsigned char *head_sha1, unsigned char *sha1)
305 {
306         int namelen;
307         if ((!head_path[0]) || memcmp(head_sha1, sha1, 20))
308                 return 0;
309         namelen = strlen(name);
310         if ((headlen < namelen) ||
311             memcmp(head_path + headlen - namelen, name, namelen))
312                 return 0;
313         if (headlen == namelen ||
314             head_path[headlen - namelen - 1] == '/')
315                 return 1;
316         return 0;
317 }
318
319 static int show_merge_base(struct commit_list *seen, int num_rev)
320 {
321         int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
322         int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
323         int exit_status = 1;
324
325         while (seen) {
326                 struct commit *commit = pop_one_commit(&seen);
327                 int flags = commit->object.flags & all_mask;
328                 if (!(flags & UNINTERESTING) &&
329                     ((flags & all_revs) == all_revs)) {
330                         puts(sha1_to_hex(commit->object.sha1));
331                         exit_status = 0;
332                         commit->object.flags |= UNINTERESTING;
333                 }
334         }
335         return exit_status;
336 }
337
338 static int show_independent(struct commit **rev,
339                             int num_rev,
340                             char **ref_name,
341                             unsigned int *rev_mask)
342 {
343         int i;
344
345         for (i = 0; i < num_rev; i++) {
346                 struct commit *commit = rev[i];
347                 unsigned int flag = rev_mask[i];
348
349                 if (commit->object.flags == flag)
350                         puts(sha1_to_hex(commit->object.sha1));
351                 commit->object.flags |= UNINTERESTING;
352         }
353         return 0;
354 }
355
356 int main(int ac, char **av)
357 {
358         struct commit *rev[MAX_REVS], *commit;
359         struct commit_list *list = NULL, *seen = NULL;
360         unsigned int rev_mask[MAX_REVS];
361         int num_rev, i, extra = 0;
362         int all_heads = 0, all_tags = 0;
363         int all_mask, all_revs, shown_merge_point;
364         char head_path[128];
365         const char *head_path_p;
366         int head_path_len;
367         unsigned char head_sha1[20];
368         int merge_base = 0;
369         int independent = 0;
370         int no_name = 0;
371         int sha1_name = 0;
372
373         setup_git_directory();
374
375         while (1 < ac && av[1][0] == '-') {
376                 char *arg = av[1];
377                 if (!strcmp(arg, "--all"))
378                         all_heads = all_tags = 1;
379                 else if (!strcmp(arg, "--heads"))
380                         all_heads = 1;
381                 else if (!strcmp(arg, "--tags"))
382                         all_tags = 1;
383                 else if (!strcmp(arg, "--more"))
384                         extra = 1;
385                 else if (!strcmp(arg, "--list"))
386                         extra = -1;
387                 else if (!strcmp(arg, "--no-name"))
388                         no_name = 1;
389                 else if (!strcmp(arg, "--sha1-name"))
390                         sha1_name = 1;
391                 else if (!strncmp(arg, "--more=", 7))
392                         extra = atoi(arg + 7);
393                 else if (!strcmp(arg, "--merge-base"))
394                         merge_base = 1;
395                 else if (!strcmp(arg, "--independent"))
396                         independent = 1;
397                 else
398                         usage(show_branch_usage);
399                 ac--; av++;
400         }
401         ac--; av++;
402
403         /* Only one of these is allowed */
404         if (1 < independent + merge_base + (extra != 0))
405                 usage(show_branch_usage);
406
407         if (all_heads + all_tags)
408                 snarf_refs(all_heads, all_tags);
409
410         while (0 < ac) {
411                 unsigned char revkey[20];
412                 if (get_sha1(*av, revkey))
413                         die("bad sha1 reference %s", *av);
414                 append_ref(*av, revkey);
415                 ac--; av++;
416         }
417
418         /* If still no revs, then add heads */
419         if (!ref_name_cnt)
420                 snarf_refs(1, 0);
421
422         for (num_rev = 0; ref_name[num_rev]; num_rev++) {
423                 unsigned char revkey[20];
424                 unsigned int flag = 1u << (num_rev + REV_SHIFT);
425
426                 if (MAX_REVS <= num_rev)
427                         die("cannot handle more than %d revs.", MAX_REVS);
428                 if (get_sha1(ref_name[num_rev], revkey))
429                         usage(show_branch_usage);
430                 commit = lookup_commit_reference(revkey);
431                 if (!commit)
432                         die("cannot find commit %s (%s)",
433                             ref_name[num_rev], revkey);
434                 parse_commit(commit);
435                 mark_seen(commit, &seen);
436
437                 /* rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1,
438                  * and so on.  REV_SHIFT bits from bit 0 are used for
439                  * internal bookkeeping.
440                  */
441                 commit->object.flags |= flag;
442                 if (commit->object.flags == flag)
443                         insert_by_date(commit, &list);
444                 rev[num_rev] = commit;
445         }
446         for (i = 0; i < num_rev; i++)
447                 rev_mask[i] = rev[i]->object.flags;
448
449         if (0 <= extra)
450                 join_revs(&list, &seen, num_rev, extra);
451
452         head_path_p = resolve_ref(git_path("HEAD"), head_sha1, 1);
453         if (head_path_p) {
454                 head_path_len = strlen(head_path_p);
455                 memcpy(head_path, head_path_p, head_path_len + 1);
456         }
457         else {
458                 head_path_len = 0;
459                 head_path[0] = 0;
460         }
461
462         if (merge_base)
463                 return show_merge_base(seen, num_rev);
464
465         if (independent)
466                 return show_independent(rev, num_rev, ref_name, rev_mask);
467
468         /* Show list; --more=-1 means list-only */
469         if (1 < num_rev || extra < 0) {
470                 for (i = 0; i < num_rev; i++) {
471                         int j;
472                         int is_head = rev_is_head(head_path,
473                                                   head_path_len,
474                                                   ref_name[i],
475                                                   head_sha1,
476                                                   rev[i]->object.sha1);
477                         if (extra < 0)
478                                 printf("%c [%s] ",
479                                        is_head ? '*' : ' ', ref_name[i]);
480                         else {
481                                 for (j = 0; j < i; j++)
482                                         putchar(' ');
483                                 printf("%c [%s] ",
484                                        is_head ? '*' : '!', ref_name[i]);
485                         }
486                         /* header lines never need name */
487                         show_one_commit(rev[i], 1);
488                 }
489                 if (0 <= extra) {
490                         for (i = 0; i < num_rev; i++)
491                                 putchar('-');
492                         putchar('\n');
493                 }
494         }
495         if (extra < 0)
496                 exit(0);
497
498         /* Sort topologically */
499         sort_in_topological_order(&seen);
500
501         /* Give names to commits */
502         if (!sha1_name && !no_name)
503                 name_commits(seen, rev, ref_name, num_rev);
504
505         all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
506         all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
507         shown_merge_point = 0;
508
509         while (seen) {
510                 struct commit *commit = pop_one_commit(&seen);
511                 int this_flag = commit->object.flags;
512                 int is_merge_point = (this_flag & all_revs) == all_revs;
513
514                 if (is_merge_point)
515                         shown_merge_point = 1;
516
517                 if (1 < num_rev) {
518                         for (i = 0; i < num_rev; i++)
519                                 putchar((this_flag & (1u << (i + REV_SHIFT)))
520                                         ? '+' : ' ');
521                         putchar(' ');
522                 }
523                 show_one_commit(commit, no_name);
524                 if (shown_merge_point && is_merge_point)
525                         if (--extra < 0)
526                                 break;
527         }
528         return 0;
529 }