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