Add documentation for git-config-set
[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         if (strncmp(refname, "refs/heads/", 11))
317                 return 0;
318         return append_ref(refname + 11, sha1);
319 }
320
321 static int append_tag_ref(const char *refname, const unsigned char *sha1)
322 {
323         if (strncmp(refname, "refs/tags/", 10))
324                 return 0;
325         return append_ref(refname + 5, sha1);
326 }
327
328 static void snarf_refs(int head, int tag)
329 {
330         if (head) {
331                 int orig_cnt = ref_name_cnt;
332                 for_each_ref(append_head_ref);
333                 sort_ref_range(orig_cnt, ref_name_cnt);
334         }
335         if (tag) {
336                 int orig_cnt = ref_name_cnt;
337                 for_each_ref(append_tag_ref);
338                 sort_ref_range(orig_cnt, ref_name_cnt);
339         }
340 }
341
342 static int rev_is_head(char *head_path, int headlen,
343                        char *name,
344                        unsigned char *head_sha1, unsigned char *sha1)
345 {
346         int namelen;
347         if ((!head_path[0]) || memcmp(head_sha1, sha1, 20))
348                 return 0;
349         namelen = strlen(name);
350         if ((headlen < namelen) ||
351             memcmp(head_path + headlen - namelen, name, namelen))
352                 return 0;
353         if (headlen == namelen ||
354             head_path[headlen - namelen - 1] == '/')
355                 return 1;
356         return 0;
357 }
358
359 static int show_merge_base(struct commit_list *seen, int num_rev)
360 {
361         int all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
362         int all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
363         int exit_status = 1;
364
365         while (seen) {
366                 struct commit *commit = pop_one_commit(&seen);
367                 int flags = commit->object.flags & all_mask;
368                 if (!(flags & UNINTERESTING) &&
369                     ((flags & all_revs) == all_revs)) {
370                         puts(sha1_to_hex(commit->object.sha1));
371                         exit_status = 0;
372                         commit->object.flags |= UNINTERESTING;
373                 }
374         }
375         return exit_status;
376 }
377
378 static int show_independent(struct commit **rev,
379                             int num_rev,
380                             char **ref_name,
381                             unsigned int *rev_mask)
382 {
383         int i;
384
385         for (i = 0; i < num_rev; i++) {
386                 struct commit *commit = rev[i];
387                 unsigned int flag = rev_mask[i];
388
389                 if (commit->object.flags == flag)
390                         puts(sha1_to_hex(commit->object.sha1));
391                 commit->object.flags |= UNINTERESTING;
392         }
393         return 0;
394 }
395
396 int main(int ac, char **av)
397 {
398         struct commit *rev[MAX_REVS], *commit;
399         struct commit_list *list = NULL, *seen = NULL;
400         unsigned int rev_mask[MAX_REVS];
401         int num_rev, i, extra = 0;
402         int all_heads = 0, all_tags = 0;
403         int all_mask, all_revs;
404         char head_path[128];
405         const char *head_path_p;
406         int head_path_len;
407         unsigned char head_sha1[20];
408         int merge_base = 0;
409         int independent = 0;
410         int no_name = 0;
411         int sha1_name = 0;
412         int shown_merge_point = 0;
413         int topo_order = 0;
414
415         setup_git_directory();
416
417         while (1 < ac && av[1][0] == '-') {
418                 char *arg = av[1];
419                 if (!strcmp(arg, "--all"))
420                         all_heads = all_tags = 1;
421                 else if (!strcmp(arg, "--heads"))
422                         all_heads = 1;
423                 else if (!strcmp(arg, "--tags"))
424                         all_tags = 1;
425                 else if (!strcmp(arg, "--more"))
426                         extra = 1;
427                 else if (!strcmp(arg, "--list"))
428                         extra = -1;
429                 else if (!strcmp(arg, "--no-name"))
430                         no_name = 1;
431                 else if (!strcmp(arg, "--sha1-name"))
432                         sha1_name = 1;
433                 else if (!strncmp(arg, "--more=", 7))
434                         extra = atoi(arg + 7);
435                 else if (!strcmp(arg, "--merge-base"))
436                         merge_base = 1;
437                 else if (!strcmp(arg, "--independent"))
438                         independent = 1;
439                 else if (!strcmp(arg, "--topo-order"))
440                         topo_order = 1;
441                 else
442                         usage(show_branch_usage);
443                 ac--; av++;
444         }
445         ac--; av++;
446
447         /* Only one of these is allowed */
448         if (1 < independent + merge_base + (extra != 0))
449                 usage(show_branch_usage);
450
451         if (all_heads + all_tags)
452                 snarf_refs(all_heads, all_tags);
453
454         while (0 < ac) {
455                 unsigned char revkey[20];
456                 if (get_sha1(*av, revkey))
457                         die("bad sha1 reference %s", *av);
458                 append_ref(*av, revkey);
459                 ac--; av++;
460         }
461
462         /* If still no revs, then add heads */
463         if (!ref_name_cnt)
464                 snarf_refs(1, 0);
465
466         for (num_rev = 0; ref_name[num_rev]; num_rev++) {
467                 unsigned char revkey[20];
468                 unsigned int flag = 1u << (num_rev + REV_SHIFT);
469
470                 if (MAX_REVS <= num_rev)
471                         die("cannot handle more than %d revs.", MAX_REVS);
472                 if (get_sha1(ref_name[num_rev], revkey))
473                         usage(show_branch_usage);
474                 commit = lookup_commit_reference(revkey);
475                 if (!commit)
476                         die("cannot find commit %s (%s)",
477                             ref_name[num_rev], revkey);
478                 parse_commit(commit);
479                 mark_seen(commit, &seen);
480
481                 /* rev#0 uses bit REV_SHIFT, rev#1 uses bit REV_SHIFT+1,
482                  * and so on.  REV_SHIFT bits from bit 0 are used for
483                  * internal bookkeeping.
484                  */
485                 commit->object.flags |= flag;
486                 if (commit->object.flags == flag)
487                         insert_by_date(commit, &list);
488                 rev[num_rev] = commit;
489         }
490         for (i = 0; i < num_rev; i++)
491                 rev_mask[i] = rev[i]->object.flags;
492
493         if (0 <= extra)
494                 join_revs(&list, &seen, num_rev, extra);
495
496         head_path_p = resolve_ref(git_path("HEAD"), head_sha1, 1);
497         if (head_path_p) {
498                 head_path_len = strlen(head_path_p);
499                 memcpy(head_path, head_path_p, head_path_len + 1);
500         }
501         else {
502                 head_path_len = 0;
503                 head_path[0] = 0;
504         }
505
506         if (merge_base)
507                 return show_merge_base(seen, num_rev);
508
509         if (independent)
510                 return show_independent(rev, num_rev, ref_name, rev_mask);
511
512         /* Show list; --more=-1 means list-only */
513         if (1 < num_rev || extra < 0) {
514                 for (i = 0; i < num_rev; i++) {
515                         int j;
516                         int is_head = rev_is_head(head_path,
517                                                   head_path_len,
518                                                   ref_name[i],
519                                                   head_sha1,
520                                                   rev[i]->object.sha1);
521                         if (extra < 0)
522                                 printf("%c [%s] ",
523                                        is_head ? '*' : ' ', ref_name[i]);
524                         else {
525                                 for (j = 0; j < i; j++)
526                                         putchar(' ');
527                                 printf("%c [%s] ",
528                                        is_head ? '*' : '!', ref_name[i]);
529                         }
530                         /* header lines never need name */
531                         show_one_commit(rev[i], 1);
532                 }
533                 if (0 <= extra) {
534                         for (i = 0; i < num_rev; i++)
535                                 putchar('-');
536                         putchar('\n');
537                 }
538         }
539         if (extra < 0)
540                 exit(0);
541
542         /* Sort topologically */
543         if (topo_order)
544                 sort_in_topological_order(&seen);
545
546         /* Give names to commits */
547         if (!sha1_name && !no_name)
548                 name_commits(seen, rev, ref_name, num_rev);
549
550         all_mask = ((1u << (REV_SHIFT + num_rev)) - 1);
551         all_revs = all_mask & ~((1u << REV_SHIFT) - 1);
552
553         while (seen) {
554                 struct commit *commit = pop_one_commit(&seen);
555                 int this_flag = commit->object.flags;
556
557                 shown_merge_point |= ((this_flag & all_revs) == all_revs);
558
559                 if (1 < num_rev) {
560                         for (i = 0; i < num_rev; i++)
561                                 putchar((this_flag & (1u << (i + REV_SHIFT)))
562                                         ? '+' : ' ');
563                         putchar(' ');
564                 }
565                 show_one_commit(commit, no_name);
566
567                 if (shown_merge_point && --extra < 0)
568                         break;
569         }
570         return 0;
571 }