builtin-show-branch.c

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