Andrew's git / gitweb.git / commit.c
?
commit.con commit shallow clone: unparse and reparse an unshallowed commit (176d45c)
   1#include "cache.h"
   2#include "tag.h"
   3#include "commit.h"
   4#include "pkt-line.h"
   5
   6int save_commit_buffer = 1;
   7
   8struct sort_node
   9{
  10        /*
  11         * the number of children of the associated commit
  12         * that also occur in the list being sorted.
  13         */
  14        unsigned int indegree;
  15
  16        /*
  17         * reference to original list item that we will re-use
  18         * on output.
  19         */
  20        struct commit_list * list_item;
  21
  22};
  23
  24const char *commit_type = "commit";
  25
  26struct cmt_fmt_map {
  27        const char *n;
  28        size_t cmp_len;
  29        enum cmit_fmt v;
  30} cmt_fmts[] = {
  31        { "raw",        1,      CMIT_FMT_RAW },
  32        { "medium",     1,      CMIT_FMT_MEDIUM },
  33        { "short",      1,      CMIT_FMT_SHORT },
  34        { "email",      1,      CMIT_FMT_EMAIL },
  35        { "full",       5,      CMIT_FMT_FULL },
  36        { "fuller",     5,      CMIT_FMT_FULLER },
  37        { "oneline",    1,      CMIT_FMT_ONELINE },
  38};
  39
  40enum cmit_fmt get_commit_format(const char *arg)
  41{
  42        int i;
  43
  44        if (!arg || !*arg)
  45                return CMIT_FMT_DEFAULT;
  46        if (*arg == '=')
  47                arg++;
  48        for (i = 0; i < ARRAY_SIZE(cmt_fmts); i++) {
  49                if (!strncmp(arg, cmt_fmts[i].n, cmt_fmts[i].cmp_len))
  50                        return cmt_fmts[i].v;
  51        }
  52
  53        die("invalid --pretty format: %s", arg);
  54}
  55
  56static struct commit *check_commit(struct object *obj,
  57                                   const unsigned char *sha1,
  58                                   int quiet)
  59{
  60        if (obj->type != OBJ_COMMIT) {
  61                if (!quiet)
  62                        error("Object %s is a %s, not a commit",
  63                              sha1_to_hex(sha1), typename(obj->type));
  64                return NULL;
  65        }
  66        return (struct commit *) obj;
  67}
  68
  69struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
  70                                              int quiet)
  71{
  72        struct object *obj = deref_tag(parse_object(sha1), NULL, 0);
  73
  74        if (!obj)
  75                return NULL;
  76        return check_commit(obj, sha1, quiet);
  77}
  78
  79struct commit *lookup_commit_reference(const unsigned char *sha1)
  80{
  81        return lookup_commit_reference_gently(sha1, 0);
  82}
  83
  84struct commit *lookup_commit(const unsigned char *sha1)
  85{
  86        struct object *obj = lookup_object(sha1);
  87        if (!obj) {
  88                struct commit *ret = alloc_commit_node();
  89                created_object(sha1, &ret->object);
  90                ret->object.type = OBJ_COMMIT;
  91                return ret;
  92        }
  93        if (!obj->type)
  94                obj->type = OBJ_COMMIT;
  95        return check_commit(obj, sha1, 0);
  96}
  97
  98static unsigned long parse_commit_date(const char *buf)
  99{
 100        unsigned long date;
 101
 102        if (memcmp(buf, "author", 6))
 103                return 0;
 104        while (*buf++ != '\n')
 105                /* nada */;
 106        if (memcmp(buf, "committer", 9))
 107                return 0;
 108        while (*buf++ != '>')
 109                /* nada */;
 110        date = strtoul(buf, NULL, 10);
 111        if (date == ULONG_MAX)
 112                date = 0;
 113        return date;
 114}
 115
 116static struct commit_graft **commit_graft;
 117static int commit_graft_alloc, commit_graft_nr;
 118
 119static int commit_graft_pos(const unsigned char *sha1)
 120{
 121        int lo, hi;
 122        lo = 0;
 123        hi = commit_graft_nr;
 124        while (lo < hi) {
 125                int mi = (lo + hi) / 2;
 126                struct commit_graft *graft = commit_graft[mi];
 127                int cmp = hashcmp(sha1, graft->sha1);
 128                if (!cmp)
 129                        return mi;
 130                if (cmp < 0)
 131                        hi = mi;
 132                else
 133                        lo = mi + 1;
 134        }
 135        return -lo - 1;
 136}
 137
 138int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 139{
 140        int pos = commit_graft_pos(graft->sha1);
 141        
 142        if (0 <= pos) {
 143                if (ignore_dups)
 144                        free(graft);
 145                else {
 146                        free(commit_graft[pos]);
 147                        commit_graft[pos] = graft;
 148                }
 149                return 1;
 150        }
 151        pos = -pos - 1;
 152        if (commit_graft_alloc <= ++commit_graft_nr) {
 153                commit_graft_alloc = alloc_nr(commit_graft_alloc);
 154                commit_graft = xrealloc(commit_graft,
 155                                        sizeof(*commit_graft) *
 156                                        commit_graft_alloc);
 157        }
 158        if (pos < commit_graft_nr)
 159                memmove(commit_graft + pos + 1,
 160                        commit_graft + pos,
 161                        (commit_graft_nr - pos - 1) *
 162                        sizeof(*commit_graft));
 163        commit_graft[pos] = graft;
 164        return 0;
 165}
 166
 167struct commit_graft *read_graft_line(char *buf, int len)
 168{
 169        /* The format is just "Commit Parent1 Parent2 ...\n" */
 170        int i;
 171        struct commit_graft *graft = NULL;
 172
 173        if (buf[len-1] == '\n')
 174                buf[--len] = 0;
 175        if (buf[0] == '#' || buf[0] == '\0')
 176                return NULL;
 177        if ((len + 1) % 41) {
 178        bad_graft_data:
 179                error("bad graft data: %s", buf);
 180                free(graft);
 181                return NULL;
 182        }
 183        i = (len + 1) / 41 - 1;
 184        graft = xmalloc(sizeof(*graft) + 20 * i);
 185        graft->nr_parent = i;
 186        if (get_sha1_hex(buf, graft->sha1))
 187                goto bad_graft_data;
 188        for (i = 40; i < len; i += 41) {
 189                if (buf[i] != ' ')
 190                        goto bad_graft_data;
 191                if (get_sha1_hex(buf + i + 1, graft->parent[i/41]))
 192                        goto bad_graft_data;
 193        }
 194        return graft;
 195}
 196
 197int read_graft_file(const char *graft_file)
 198{
 199        FILE *fp = fopen(graft_file, "r");
 200        char buf[1024];
 201        if (!fp)
 202                return -1;
 203        while (fgets(buf, sizeof(buf), fp)) {
 204                /* The format is just "Commit Parent1 Parent2 ...\n" */
 205                int len = strlen(buf);
 206                struct commit_graft *graft = read_graft_line(buf, len);
 207                if (!graft)
 208                        continue;
 209                if (register_commit_graft(graft, 1))
 210                        error("duplicate graft data: %s", buf);
 211        }
 212        fclose(fp);
 213        return 0;
 214}
 215
 216static void prepare_commit_graft(void)
 217{
 218        static int commit_graft_prepared;
 219        char *graft_file;
 220
 221        if (commit_graft_prepared)
 222                return;
 223        graft_file = get_graft_file();
 224        read_graft_file(graft_file);
 225        /* make sure shallows are read */
 226        is_repository_shallow();
 227        commit_graft_prepared = 1;
 228}
 229
 230static struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
 231{
 232        int pos;
 233        prepare_commit_graft();
 234        pos = commit_graft_pos(sha1);
 235        if (pos < 0)
 236                return NULL;
 237        return commit_graft[pos];
 238}
 239
 240int write_shallow_commits(int fd, int use_pack_protocol)
 241{
 242        int i, count = 0;
 243        for (i = 0; i < commit_graft_nr; i++)
 244                if (commit_graft[i]->nr_parent < 0) {
 245                        const char *hex =
 246                                sha1_to_hex(commit_graft[i]->sha1);
 247                        count++;
 248                        if (use_pack_protocol)
 249                                packet_write(fd, "shallow %s", hex);
 250                        else {
 251                                write(fd, hex,  40);
 252                                write(fd, "\n", 1);
 253                        }
 254                }
 255        return count;
 256}
 257
 258int unregister_shallow(const unsigned char *sha1)
 259{
 260        int pos = commit_graft_pos(sha1);
 261        if (pos < 0)
 262                return -1;
 263        if (pos + 1 < commit_graft_nr)
 264                memcpy(commit_graft + pos, commit_graft + pos + 1,
 265                                sizeof(struct commit_graft *)
 266                                * (commit_graft_nr - pos - 1));
 267        commit_graft_nr--;
 268        return 0;
 269}
 270
 271int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 272{
 273        char *tail = buffer;
 274        char *bufptr = buffer;
 275        unsigned char parent[20];
 276        struct commit_list **pptr;
 277        struct commit_graft *graft;
 278        unsigned n_refs = 0;
 279
 280        if (item->object.parsed)
 281                return 0;
 282        item->object.parsed = 1;
 283        tail += size;
 284        if (tail <= bufptr + 5 || memcmp(bufptr, "tree ", 5))
 285                return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
 286        if (tail <= bufptr + 45 || get_sha1_hex(bufptr + 5, parent) < 0)
 287                return error("bad tree pointer in commit %s",
 288                             sha1_to_hex(item->object.sha1));
 289        item->tree = lookup_tree(parent);
 290        if (item->tree)
 291                n_refs++;
 292        bufptr += 46; /* "tree " + "hex sha1" + "\n" */
 293        pptr = &item->parents;
 294
 295        graft = lookup_commit_graft(item->object.sha1);
 296        while (bufptr + 48 < tail && !memcmp(bufptr, "parent ", 7)) {
 297                struct commit *new_parent;
 298
 299                if (tail <= bufptr + 48 ||
 300                    get_sha1_hex(bufptr + 7, parent) ||
 301                    bufptr[47] != '\n')
 302                        return error("bad parents in commit %s", sha1_to_hex(item->object.sha1));
 303                bufptr += 48;
 304                if (graft)
 305                        continue;
 306                new_parent = lookup_commit(parent);
 307                if (new_parent) {
 308                        pptr = &commit_list_insert(new_parent, pptr)->next;
 309                        n_refs++;
 310                }
 311        }
 312        if (graft) {
 313                int i;
 314                struct commit *new_parent;
 315                for (i = 0; i < graft->nr_parent; i++) {
 316                        new_parent = lookup_commit(graft->parent[i]);
 317                        if (!new_parent)
 318                                continue;
 319                        pptr = &commit_list_insert(new_parent, pptr)->next;
 320                        n_refs++;
 321                }
 322        }
 323        item->date = parse_commit_date(bufptr);
 324
 325        if (track_object_refs) {
 326                unsigned i = 0;
 327                struct commit_list *p;
 328                struct object_refs *refs = alloc_object_refs(n_refs);
 329                if (item->tree)
 330                        refs->ref[i++] = &item->tree->object;
 331                for (p = item->parents; p; p = p->next)
 332                        refs->ref[i++] = &p->item->object;
 333                set_object_refs(&item->object, refs);
 334        }
 335
 336        return 0;
 337}
 338
 339int parse_commit(struct commit *item)
 340{
 341        char type[20];
 342        void *buffer;
 343        unsigned long size;
 344        int ret;
 345
 346        if (item->object.parsed)
 347                return 0;
 348        buffer = read_sha1_file(item->object.sha1, type, &size);
 349        if (!buffer)
 350                return error("Could not read %s",
 351                             sha1_to_hex(item->object.sha1));
 352        if (strcmp(type, commit_type)) {
 353                free(buffer);
 354                return error("Object %s not a commit",
 355                             sha1_to_hex(item->object.sha1));
 356        }
 357        ret = parse_commit_buffer(item, buffer, size);
 358        if (save_commit_buffer && !ret) {
 359                item->buffer = buffer;
 360                return 0;
 361        }
 362        free(buffer);
 363        return ret;
 364}
 365
 366struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 367{
 368        struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
 369        new_list->item = item;
 370        new_list->next = *list_p;
 371        *list_p = new_list;
 372        return new_list;
 373}
 374
 375void free_commit_list(struct commit_list *list)
 376{
 377        while (list) {
 378                struct commit_list *temp = list;
 379                list = temp->next;
 380                free(temp);
 381        }
 382}
 383
 384struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
 385{
 386        struct commit_list **pp = list;
 387        struct commit_list *p;
 388        while ((p = *pp) != NULL) {
 389                if (p->item->date < item->date) {
 390                        break;
 391                }
 392                pp = &p->next;
 393        }
 394        return commit_list_insert(item, pp);
 395}
 396
 397        
 398void sort_by_date(struct commit_list **list)
 399{
 400        struct commit_list *ret = NULL;
 401        while (*list) {
 402                insert_by_date((*list)->item, &ret);
 403                *list = (*list)->next;
 404        }
 405        *list = ret;
 406}
 407
 408struct commit *pop_most_recent_commit(struct commit_list **list,
 409                                      unsigned int mark)
 410{
 411        struct commit *ret = (*list)->item;
 412        struct commit_list *parents = ret->parents;
 413        struct commit_list *old = *list;
 414
 415        *list = (*list)->next;
 416        free(old);
 417
 418        while (parents) {
 419                struct commit *commit = parents->item;
 420                parse_commit(commit);
 421                if (!(commit->object.flags & mark)) {
 422                        commit->object.flags |= mark;
 423                        insert_by_date(commit, list);
 424                }
 425                parents = parents->next;
 426        }
 427        return ret;
 428}
 429
 430void clear_commit_marks(struct commit *commit, unsigned int mark)
 431{
 432        struct commit_list *parents;
 433
 434        commit->object.flags &= ~mark;
 435        parents = commit->parents;
 436        while (parents) {
 437                struct commit *parent = parents->item;
 438
 439                /* Have we already cleared this? */
 440                if (mark & parent->object.flags)
 441                        clear_commit_marks(parent, mark);
 442                parents = parents->next;
 443        }
 444}
 445
 446/*
 447 * Generic support for pretty-printing the header
 448 */
 449static int get_one_line(const char *msg, unsigned long len)
 450{
 451        int ret = 0;
 452
 453        while (len--) {
 454                char c = *msg++;
 455                if (!c)
 456                        break;
 457                ret++;
 458                if (c == '\n')
 459                        break;
 460        }
 461        return ret;
 462}
 463
 464static int is_rfc2047_special(char ch)
 465{
 466        return ((ch & 0x80) || (ch == '=') || (ch == '?') || (ch == '_'));
 467}
 468
 469static int add_rfc2047(char *buf, const char *line, int len)
 470{
 471        char *bp = buf;
 472        int i, needquote;
 473        static const char q_utf8[] = "=?utf-8?q?";
 474
 475        for (i = needquote = 0; !needquote && i < len; i++) {
 476                unsigned ch = line[i];
 477                if (ch & 0x80)
 478                        needquote++;
 479                if ((i + 1 < len) &&
 480                    (ch == '=' && line[i+1] == '?'))
 481                        needquote++;
 482        }
 483        if (!needquote)
 484                return sprintf(buf, "%.*s", len, line);
 485
 486        memcpy(bp, q_utf8, sizeof(q_utf8)-1);
 487        bp += sizeof(q_utf8)-1;
 488        for (i = 0; i < len; i++) {
 489                unsigned ch = line[i] & 0xFF;
 490                if (is_rfc2047_special(ch)) {
 491                        sprintf(bp, "=%02X", ch);
 492                        bp += 3;
 493                }
 494                else if (ch == ' ')
 495                        *bp++ = '_';
 496                else
 497                        *bp++ = ch;
 498        }
 499        memcpy(bp, "?=", 2);
 500        bp += 2;
 501        return bp - buf;
 502}
 503
 504static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf,
 505                         const char *line, int relative_date)
 506{
 507        char *date;
 508        int namelen;
 509        unsigned long time;
 510        int tz, ret;
 511        const char *filler = "    ";
 512
 513        if (fmt == CMIT_FMT_ONELINE)
 514                return 0;
 515        date = strchr(line, '>');
 516        if (!date)
 517                return 0;
 518        namelen = ++date - line;
 519        time = strtoul(date, &date, 10);
 520        tz = strtol(date, NULL, 10);
 521
 522        if (fmt == CMIT_FMT_EMAIL) {
 523                char *name_tail = strchr(line, '<');
 524                int display_name_length;
 525                if (!name_tail)
 526                        return 0;
 527                while (line < name_tail && isspace(name_tail[-1]))
 528                        name_tail--;
 529                display_name_length = name_tail - line;
 530                filler = "";
 531                strcpy(buf, "From: ");
 532                ret = strlen(buf);
 533                ret += add_rfc2047(buf + ret, line, display_name_length);
 534                memcpy(buf + ret, name_tail, namelen - display_name_length);
 535                ret += namelen - display_name_length;
 536                buf[ret++] = '\n';
 537        }
 538        else {
 539                ret = sprintf(buf, "%s: %.*s%.*s\n", what,
 540                              (fmt == CMIT_FMT_FULLER) ? 4 : 0,
 541                              filler, namelen, line);
 542        }
 543        switch (fmt) {
 544        case CMIT_FMT_MEDIUM:
 545                ret += sprintf(buf + ret, "Date:   %s\n",
 546                               show_date(time, tz, relative_date));
 547                break;
 548        case CMIT_FMT_EMAIL:
 549                ret += sprintf(buf + ret, "Date: %s\n",
 550                               show_rfc2822_date(time, tz));
 551                break;
 552        case CMIT_FMT_FULLER:
 553                ret += sprintf(buf + ret, "%sDate: %s\n", what,
 554                               show_date(time, tz, relative_date));
 555                break;
 556        default:
 557                /* notin' */
 558                break;
 559        }
 560        return ret;
 561}
 562
 563static int is_empty_line(const char *line, int *len_p)
 564{
 565        int len = *len_p;
 566        while (len && isspace(line[len-1]))
 567                len--;
 568        *len_p = len;
 569        return !len;
 570}
 571
 572static int add_merge_info(enum cmit_fmt fmt, char *buf, const struct commit *commit, int abbrev)
 573{
 574        struct commit_list *parent = commit->parents;
 575        int offset;
 576
 577        if ((fmt == CMIT_FMT_ONELINE) || (fmt == CMIT_FMT_EMAIL) ||
 578            !parent || !parent->next)
 579                return 0;
 580
 581        offset = sprintf(buf, "Merge:");
 582
 583        while (parent) {
 584                struct commit *p = parent->item;
 585                const char *hex = NULL;
 586                const char *dots;
 587                if (abbrev)
 588                        hex = find_unique_abbrev(p->object.sha1, abbrev);
 589                if (!hex)
 590                        hex = sha1_to_hex(p->object.sha1);
 591                dots = (abbrev && strlen(hex) != 40) ?  "..." : "";
 592                parent = parent->next;
 593
 594                offset += sprintf(buf + offset, " %s%s", hex, dots);
 595        }
 596        buf[offset++] = '\n';
 597        return offset;
 598}
 599
 600unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
 601                                  unsigned long len, char *buf, unsigned long space,
 602                                  int abbrev, const char *subject,
 603                                  const char *after_subject, int relative_date)
 604{
 605        int hdr = 1, body = 0;
 606        unsigned long offset = 0;
 607        int indent = 4;
 608        int parents_shown = 0;
 609        const char *msg = commit->buffer;
 610        int plain_non_ascii = 0;
 611
 612        if (fmt == CMIT_FMT_ONELINE || fmt == CMIT_FMT_EMAIL)
 613                indent = 0;
 614
 615        /* After-subject is used to pass in Content-Type: multipart
 616         * MIME header; in that case we do not have to do the
 617         * plaintext content type even if the commit message has
 618         * non 7-bit ASCII character.  Otherwise, check if we need
 619         * to say this is not a 7-bit ASCII.
 620         */
 621        if (fmt == CMIT_FMT_EMAIL && !after_subject) {
 622                int i, ch, in_body;
 623
 624                for (in_body = i = 0; (ch = msg[i]) && i < len; i++) {
 625                        if (!in_body) {
 626                                /* author could be non 7-bit ASCII but
 627                                 * the log may so; skip over the
 628                                 * header part first.
 629                                 */
 630                                if (ch == '\n' &&
 631                                    i + 1 < len && msg[i+1] == '\n')
 632                                        in_body = 1;
 633                        }
 634                        else if (ch & 0x80) {
 635                                plain_non_ascii = 1;
 636                                break;
 637                        }
 638                }
 639        }
 640
 641        for (;;) {
 642                const char *line = msg;
 643                int linelen = get_one_line(msg, len);
 644
 645                if (!linelen)
 646                        break;
 647
 648                /*
 649                 * We want some slop for indentation and a possible
 650                 * final "...". Thus the "+ 20".
 651                 */
 652                if (offset + linelen + 20 > space) {
 653                        memcpy(buf + offset, "    ...\n", 8);
 654                        offset += 8;
 655                        break;
 656                }
 657
 658                msg += linelen;
 659                len -= linelen;
 660                if (hdr) {
 661                        if (linelen == 1) {
 662                                hdr = 0;
 663                                if ((fmt != CMIT_FMT_ONELINE) && !subject)
 664                                        buf[offset++] = '\n';
 665                                continue;
 666                        }
 667                        if (fmt == CMIT_FMT_RAW) {
 668                                memcpy(buf + offset, line, linelen);
 669                                offset += linelen;
 670                                continue;
 671                        }
 672                        if (!memcmp(line, "parent ", 7)) {
 673                                if (linelen != 48)
 674                                        die("bad parent line in commit");
 675                                continue;
 676                        }
 677
 678                        if (!parents_shown) {
 679                                offset += add_merge_info(fmt, buf + offset,
 680                                                         commit, abbrev);
 681                                parents_shown = 1;
 682                                continue;
 683                        }
 684                        /*
 685                         * MEDIUM == DEFAULT shows only author with dates.
 686                         * FULL shows both authors but not dates.
 687                         * FULLER shows both authors and dates.
 688                         */
 689                        if (!memcmp(line, "author ", 7))
 690                                offset += add_user_info("Author", fmt,
 691                                                        buf + offset,
 692                                                        line + 7,
 693                                                        relative_date);
 694                        if (!memcmp(line, "committer ", 10) &&
 695                            (fmt == CMIT_FMT_FULL || fmt == CMIT_FMT_FULLER))
 696                                offset += add_user_info("Commit", fmt,
 697                                                        buf + offset,
 698                                                        line + 10,
 699                                                        relative_date);
 700                        continue;
 701                }
 702
 703                if (!subject)
 704                        body = 1;
 705
 706                if (is_empty_line(line, &linelen)) {
 707                        if (!body)
 708                                continue;
 709                        if (subject)
 710                                continue;
 711                        if (fmt == CMIT_FMT_SHORT)
 712                                break;
 713                }
 714
 715                if (subject) {
 716                        int slen = strlen(subject);
 717                        memcpy(buf + offset, subject, slen);
 718                        offset += slen;
 719                        offset += add_rfc2047(buf + offset, line, linelen);
 720                }
 721                else {
 722                        memset(buf + offset, ' ', indent);
 723                        memcpy(buf + offset + indent, line, linelen);
 724                        offset += linelen + indent;
 725                }
 726                buf[offset++] = '\n';
 727                if (fmt == CMIT_FMT_ONELINE)
 728                        break;
 729                if (subject && plain_non_ascii) {
 730                        static const char header[] =
 731                                "Content-Type: text/plain; charset=UTF-8\n"
 732                                "Content-Transfer-Encoding: 8bit\n";
 733                        memcpy(buf + offset, header, sizeof(header)-1);
 734                        offset += sizeof(header)-1;
 735                }
 736                if (after_subject) {
 737                        int slen = strlen(after_subject);
 738                        if (slen > space - offset - 1)
 739                                slen = space - offset - 1;
 740                        memcpy(buf + offset, after_subject, slen);
 741                        offset += slen;
 742                        after_subject = NULL;
 743                }
 744                subject = NULL;
 745        }
 746        while (offset && isspace(buf[offset-1]))
 747                offset--;
 748        /* Make sure there is an EOLN for the non-oneline case */
 749        if (fmt != CMIT_FMT_ONELINE)
 750                buf[offset++] = '\n';
 751        /*
 752         * make sure there is another EOLN to separate the headers from whatever
 753         * body the caller appends if we haven't already written a body
 754         */
 755        if (fmt == CMIT_FMT_EMAIL && !body)
 756                buf[offset++] = '\n';
 757        buf[offset] = '\0';
 758        return offset;
 759}
 760
 761struct commit *pop_commit(struct commit_list **stack)
 762{
 763        struct commit_list *top = *stack;
 764        struct commit *item = top ? top->item : NULL;
 765
 766        if (top) {
 767                *stack = top->next;
 768                free(top);
 769        }
 770        return item;
 771}
 772
 773int count_parents(struct commit * commit)
 774{
 775        int count;
 776        struct commit_list * parents = commit->parents;
 777        for (count = 0; parents; parents = parents->next,count++)
 778                ;
 779        return count;
 780}
 781
 782void topo_sort_default_setter(struct commit *c, void *data)
 783{
 784        c->util = data;
 785}
 786
 787void *topo_sort_default_getter(struct commit *c)
 788{
 789        return c->util;
 790}
 791
 792/*
 793 * Performs an in-place topological sort on the list supplied.
 794 */
 795void sort_in_topological_order(struct commit_list ** list, int lifo)
 796{
 797        sort_in_topological_order_fn(list, lifo, topo_sort_default_setter,
 798                                     topo_sort_default_getter);
 799}
 800
 801void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
 802                                  topo_sort_set_fn_t setter,
 803                                  topo_sort_get_fn_t getter)
 804{
 805        struct commit_list * next = *list;
 806        struct commit_list * work = NULL, **insert;
 807        struct commit_list ** pptr = list;
 808        struct sort_node * nodes;
 809        struct sort_node * next_nodes;
 810        int count = 0;
 811
 812        /* determine the size of the list */
 813        while (next) {
 814                next = next->next;
 815                count++;
 816        }
 817        
 818        if (!count)
 819                return;
 820        /* allocate an array to help sort the list */
 821        nodes = xcalloc(count, sizeof(*nodes));
 822        /* link the list to the array */
 823        next_nodes = nodes;
 824        next=*list;
 825        while (next) {
 826                next_nodes->list_item = next;
 827                setter(next->item, next_nodes);
 828                next_nodes++;
 829                next = next->next;
 830        }
 831        /* update the indegree */
 832        next=*list;
 833        while (next) {
 834                struct commit_list * parents = next->item->parents;
 835                while (parents) {
 836                        struct commit * parent=parents->item;
 837                        struct sort_node * pn = (struct sort_node *) getter(parent);
 838
 839                        if (pn)
 840                                pn->indegree++;
 841                        parents=parents->next;
 842                }
 843                next=next->next;
 844        }
 845        /* 
 846         * find the tips
 847         *
 848         * tips are nodes not reachable from any other node in the list 
 849         * 
 850         * the tips serve as a starting set for the work queue.
 851         */
 852        next=*list;
 853        insert = &work;
 854        while (next) {
 855                struct sort_node * node = (struct sort_node *) getter(next->item);
 856
 857                if (node->indegree == 0) {
 858                        insert = &commit_list_insert(next->item, insert)->next;
 859                }
 860                next=next->next;
 861        }
 862
 863        /* process the list in topological order */
 864        if (!lifo)
 865                sort_by_date(&work);
 866        while (work) {
 867                struct commit * work_item = pop_commit(&work);
 868                struct sort_node * work_node = (struct sort_node *) getter(work_item);
 869                struct commit_list * parents = work_item->parents;
 870
 871                while (parents) {
 872                        struct commit * parent=parents->item;
 873                        struct sort_node * pn = (struct sort_node *) getter(parent);
 874
 875                        if (pn) {
 876                                /*
 877                                 * parents are only enqueued for emission 
 878                                 * when all their children have been emitted thereby
 879                                 * guaranteeing topological order.
 880                                 */
 881                                pn->indegree--;
 882                                if (!pn->indegree) {
 883                                        if (!lifo)
 884                                                insert_by_date(parent, &work);
 885                                        else
 886                                                commit_list_insert(parent, &work);
 887                                }
 888                        }
 889                        parents=parents->next;
 890                }
 891                /*
 892                 * work_item is a commit all of whose children
 893                 * have already been emitted. we can emit it now.
 894                 */
 895                *pptr = work_node->list_item;
 896                pptr = &(*pptr)->next;
 897                *pptr = NULL;
 898                setter(work_item, NULL);
 899        }
 900        free(nodes);
 901}
 902
 903/* merge-rebase stuff */
 904
 905/* bits #0..7 in revision.h */
 906#define PARENT1         (1u<< 8)
 907#define PARENT2         (1u<< 9)
 908#define STALE           (1u<<10)
 909#define RESULT          (1u<<11)
 910
 911static struct commit *interesting(struct commit_list *list)
 912{
 913        while (list) {
 914                struct commit *commit = list->item;
 915                list = list->next;
 916                if (commit->object.flags & STALE)
 917                        continue;
 918                return commit;
 919        }
 920        return NULL;
 921}
 922
 923static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 924{
 925        struct commit_list *list = NULL;
 926        struct commit_list *result = NULL;
 927
 928        if (one == two)
 929                /* We do not mark this even with RESULT so we do not
 930                 * have to clean it up.
 931                 */
 932                return commit_list_insert(one, &result);
 933
 934        parse_commit(one);
 935        parse_commit(two);
 936
 937        one->object.flags |= PARENT1;
 938        two->object.flags |= PARENT2;
 939        insert_by_date(one, &list);
 940        insert_by_date(two, &list);
 941
 942        while (interesting(list)) {
 943                struct commit *commit;
 944                struct commit_list *parents;
 945                struct commit_list *n;
 946                int flags;
 947
 948                commit = list->item;
 949                n = list->next;
 950                free(list);
 951                list = n;
 952
 953                flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 954                if (flags == (PARENT1 | PARENT2)) {
 955                        if (!(commit->object.flags & RESULT)) {
 956                                commit->object.flags |= RESULT;
 957                                insert_by_date(commit, &result);
 958                        }
 959                        /* Mark parents of a found merge stale */
 960                        flags |= STALE;
 961                }
 962                parents = commit->parents;
 963                while (parents) {
 964                        struct commit *p = parents->item;
 965                        parents = parents->next;
 966                        if ((p->object.flags & flags) == flags)
 967                                continue;
 968                        parse_commit(p);
 969                        p->object.flags |= flags;
 970                        insert_by_date(p, &list);
 971                }
 972        }
 973
 974        /* Clean up the result to remove stale ones */
 975        list = result; result = NULL;
 976        while (list) {
 977                struct commit_list *n = list->next;
 978                if (!(list->item->object.flags & STALE))
 979                        insert_by_date(list->item, &result);
 980                free(list);
 981                list = n;
 982        }
 983        return result;
 984}
 985
 986struct commit_list *get_merge_bases(struct commit *one,
 987                                    struct commit *two,
 988                                    int cleanup)
 989{
 990        const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
 991        struct commit_list *list;
 992        struct commit **rslt;
 993        struct commit_list *result;
 994        int cnt, i, j;
 995
 996        result = merge_bases(one, two);
 997        if (one == two)
 998                return result;
 999        if (!result || !result->next) {
1000                if (cleanup) {
1001                        clear_commit_marks(one, all_flags);
1002                        clear_commit_marks(two, all_flags);
1003                }
1004                return result;
1005        }
1006
1007        /* There are more than one */
1008        cnt = 0;
1009        list = result;
1010        while (list) {
1011                list = list->next;
1012                cnt++;
1013        }
1014        rslt = xcalloc(cnt, sizeof(*rslt));
1015        for (list = result, i = 0; list; list = list->next)
1016                rslt[i++] = list->item;
1017        free_commit_list(result);
1018
1019        clear_commit_marks(one, all_flags);
1020        clear_commit_marks(two, all_flags);
1021        for (i = 0; i < cnt - 1; i++) {
1022                for (j = i+1; j < cnt; j++) {
1023                        if (!rslt[i] || !rslt[j])
1024                                continue;
1025                        result = merge_bases(rslt[i], rslt[j]);
1026                        clear_commit_marks(rslt[i], all_flags);
1027                        clear_commit_marks(rslt[j], all_flags);
1028                        for (list = result; list; list = list->next) {
1029                                if (rslt[i] == list->item)
1030                                        rslt[i] = NULL;
1031                                if (rslt[j] == list->item)
1032                                        rslt[j] = NULL;
1033                        }
1034                }
1035        }
1036
1037        /* Surviving ones in rslt[] are the independent results */
1038        result = NULL;
1039        for (i = 0; i < cnt; i++) {
1040                if (rslt[i])
1041                        insert_by_date(rslt[i], &result);
1042        }
1043        free(rslt);
1044        return result;
1045}