Andrew's git / gitweb.git / commit.c
?
commit.con commit Merge branch 'ts/doctar' (3532998)
   1#include "cache.h"
   2#include "tag.h"
   3#include "commit.h"
   4
   5int save_commit_buffer = 1;
   6
   7struct sort_node
   8{
   9        /*
  10         * the number of children of the associated commit
  11         * that also occur in the list being sorted.
  12         */
  13        unsigned int indegree;
  14
  15        /*
  16         * reference to original list item that we will re-use
  17         * on output.
  18         */
  19        struct commit_list * list_item;
  20
  21};
  22
  23const char *commit_type = "commit";
  24
  25struct cmt_fmt_map {
  26        const char *n;
  27        size_t cmp_len;
  28        enum cmit_fmt v;
  29} cmt_fmts[] = {
  30        { "raw",        1,      CMIT_FMT_RAW },
  31        { "medium",     1,      CMIT_FMT_MEDIUM },
  32        { "short",      1,      CMIT_FMT_SHORT },
  33        { "full",       5,      CMIT_FMT_FULL },
  34        { "fuller",     5,      CMIT_FMT_FULLER },
  35        { "oneline",    1,      CMIT_FMT_ONELINE },
  36};
  37
  38enum cmit_fmt get_commit_format(const char *arg)
  39{
  40        int i;
  41
  42        if (!arg || !*arg)
  43                return CMIT_FMT_DEFAULT;
  44        if (*arg == '=')
  45                arg++;
  46        for (i = 0; i < ARRAY_SIZE(cmt_fmts); i++) {
  47                if (!strncmp(arg, cmt_fmts[i].n, cmt_fmts[i].cmp_len))
  48                        return cmt_fmts[i].v;
  49        }
  50
  51        die("invalid --pretty format: %s", arg);
  52}
  53
  54static struct commit *check_commit(struct object *obj,
  55                                   const unsigned char *sha1,
  56                                   int quiet)
  57{
  58        if (obj->type != commit_type) {
  59                if (!quiet)
  60                        error("Object %s is a %s, not a commit",
  61                              sha1_to_hex(sha1), obj->type);
  62                return NULL;
  63        }
  64        return (struct commit *) obj;
  65}
  66
  67struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
  68                                              int quiet)
  69{
  70        struct object *obj = deref_tag(parse_object(sha1), NULL, 0);
  71
  72        if (!obj)
  73                return NULL;
  74        return check_commit(obj, sha1, quiet);
  75}
  76
  77struct commit *lookup_commit_reference(const unsigned char *sha1)
  78{
  79        return lookup_commit_reference_gently(sha1, 0);
  80}
  81
  82struct commit *lookup_commit(const unsigned char *sha1)
  83{
  84        struct object *obj = lookup_object(sha1);
  85        if (!obj) {
  86                struct commit *ret = xcalloc(1, sizeof(struct commit));
  87                created_object(sha1, &ret->object);
  88                ret->object.type = commit_type;
  89                return ret;
  90        }
  91        if (!obj->type)
  92                obj->type = commit_type;
  93        return check_commit(obj, sha1, 0);
  94}
  95
  96static unsigned long parse_commit_date(const char *buf)
  97{
  98        unsigned long date;
  99
 100        if (memcmp(buf, "author", 6))
 101                return 0;
 102        while (*buf++ != '\n')
 103                /* nada */;
 104        if (memcmp(buf, "committer", 9))
 105                return 0;
 106        while (*buf++ != '>')
 107                /* nada */;
 108        date = strtoul(buf, NULL, 10);
 109        if (date == ULONG_MAX)
 110                date = 0;
 111        return date;
 112}
 113
 114static struct commit_graft **commit_graft;
 115static int commit_graft_alloc, commit_graft_nr;
 116
 117static int commit_graft_pos(const unsigned char *sha1)
 118{
 119        int lo, hi;
 120        lo = 0;
 121        hi = commit_graft_nr;
 122        while (lo < hi) {
 123                int mi = (lo + hi) / 2;
 124                struct commit_graft *graft = commit_graft[mi];
 125                int cmp = memcmp(sha1, graft->sha1, 20);
 126                if (!cmp)
 127                        return mi;
 128                if (cmp < 0)
 129                        hi = mi;
 130                else
 131                        lo = mi + 1;
 132        }
 133        return -lo - 1;
 134}
 135
 136int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 137{
 138        int pos = commit_graft_pos(graft->sha1);
 139        
 140        if (0 <= pos) {
 141                if (ignore_dups)
 142                        free(graft);
 143                else {
 144                        free(commit_graft[pos]);
 145                        commit_graft[pos] = graft;
 146                }
 147                return 1;
 148        }
 149        pos = -pos - 1;
 150        if (commit_graft_alloc <= ++commit_graft_nr) {
 151                commit_graft_alloc = alloc_nr(commit_graft_alloc);
 152                commit_graft = xrealloc(commit_graft,
 153                                        sizeof(*commit_graft) *
 154                                        commit_graft_alloc);
 155        }
 156        if (pos < commit_graft_nr)
 157                memmove(commit_graft + pos + 1,
 158                        commit_graft + pos,
 159                        (commit_graft_nr - pos - 1) *
 160                        sizeof(*commit_graft));
 161        commit_graft[pos] = graft;
 162        return 0;
 163}
 164
 165struct commit_graft *read_graft_line(char *buf, int len)
 166{
 167        /* The format is just "Commit Parent1 Parent2 ...\n" */
 168        int i;
 169        struct commit_graft *graft = NULL;
 170
 171        if (buf[len-1] == '\n')
 172                buf[--len] = 0;
 173        if (buf[0] == '#' || buf[0] == '\0')
 174                return NULL;
 175        if ((len + 1) % 41) {
 176        bad_graft_data:
 177                error("bad graft data: %s", buf);
 178                free(graft);
 179                return NULL;
 180        }
 181        i = (len + 1) / 41 - 1;
 182        graft = xmalloc(sizeof(*graft) + 20 * i);
 183        graft->nr_parent = i;
 184        if (get_sha1_hex(buf, graft->sha1))
 185                goto bad_graft_data;
 186        for (i = 40; i < len; i += 41) {
 187                if (buf[i] != ' ')
 188                        goto bad_graft_data;
 189                if (get_sha1_hex(buf + i + 1, graft->parent[i/41]))
 190                        goto bad_graft_data;
 191        }
 192        return graft;
 193}
 194
 195int read_graft_file(const char *graft_file)
 196{
 197        FILE *fp = fopen(graft_file, "r");
 198        char buf[1024];
 199        if (!fp)
 200                return -1;
 201        while (fgets(buf, sizeof(buf), fp)) {
 202                /* The format is just "Commit Parent1 Parent2 ...\n" */
 203                int len = strlen(buf);
 204                struct commit_graft *graft = read_graft_line(buf, len);
 205                if (!graft)
 206                        continue;
 207                if (register_commit_graft(graft, 1))
 208                        error("duplicate graft data: %s", buf);
 209        }
 210        fclose(fp);
 211        return 0;
 212}
 213
 214static void prepare_commit_graft(void)
 215{
 216        static int commit_graft_prepared;
 217        char *graft_file;
 218
 219        if (commit_graft_prepared)
 220                return;
 221        graft_file = get_graft_file();
 222        read_graft_file(graft_file);
 223        commit_graft_prepared = 1;
 224}
 225
 226static struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
 227{
 228        int pos;
 229        prepare_commit_graft();
 230        pos = commit_graft_pos(sha1);
 231        if (pos < 0)
 232                return NULL;
 233        return commit_graft[pos];
 234}
 235
 236int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 237{
 238        char *bufptr = buffer;
 239        unsigned char parent[20];
 240        struct commit_list **pptr;
 241        struct commit_graft *graft;
 242        unsigned n_refs = 0;
 243
 244        if (item->object.parsed)
 245                return 0;
 246        item->object.parsed = 1;
 247        if (memcmp(bufptr, "tree ", 5))
 248                return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
 249        if (get_sha1_hex(bufptr + 5, parent) < 0)
 250                return error("bad tree pointer in commit %s",
 251                             sha1_to_hex(item->object.sha1));
 252        item->tree = lookup_tree(parent);
 253        if (item->tree)
 254                n_refs++;
 255        bufptr += 46; /* "tree " + "hex sha1" + "\n" */
 256        pptr = &item->parents;
 257
 258        graft = lookup_commit_graft(item->object.sha1);
 259        while (!memcmp(bufptr, "parent ", 7)) {
 260                struct commit *new_parent;
 261
 262                if (get_sha1_hex(bufptr + 7, parent) || bufptr[47] != '\n')
 263                        return error("bad parents in commit %s", sha1_to_hex(item->object.sha1));
 264                bufptr += 48;
 265                if (graft)
 266                        continue;
 267                new_parent = lookup_commit(parent);
 268                if (new_parent) {
 269                        pptr = &commit_list_insert(new_parent, pptr)->next;
 270                        n_refs++;
 271                }
 272        }
 273        if (graft) {
 274                int i;
 275                struct commit *new_parent;
 276                for (i = 0; i < graft->nr_parent; i++) {
 277                        new_parent = lookup_commit(graft->parent[i]);
 278                        if (!new_parent)
 279                                continue;
 280                        pptr = &commit_list_insert(new_parent, pptr)->next;
 281                        n_refs++;
 282                }
 283        }
 284        item->date = parse_commit_date(bufptr);
 285
 286        if (track_object_refs) {
 287                unsigned i = 0;
 288                struct commit_list *p;
 289                struct object_refs *refs = alloc_object_refs(n_refs);
 290                if (item->tree)
 291                        refs->ref[i++] = &item->tree->object;
 292                for (p = item->parents; p; p = p->next)
 293                        refs->ref[i++] = &p->item->object;
 294                set_object_refs(&item->object, refs);
 295        }
 296
 297        return 0;
 298}
 299
 300int parse_commit(struct commit *item)
 301{
 302        char type[20];
 303        void *buffer;
 304        unsigned long size;
 305        int ret;
 306
 307        if (item->object.parsed)
 308                return 0;
 309        buffer = read_sha1_file(item->object.sha1, type, &size);
 310        if (!buffer)
 311                return error("Could not read %s",
 312                             sha1_to_hex(item->object.sha1));
 313        if (strcmp(type, commit_type)) {
 314                free(buffer);
 315                return error("Object %s not a commit",
 316                             sha1_to_hex(item->object.sha1));
 317        }
 318        ret = parse_commit_buffer(item, buffer, size);
 319        if (save_commit_buffer && !ret) {
 320                item->buffer = buffer;
 321                return 0;
 322        }
 323        free(buffer);
 324        return ret;
 325}
 326
 327struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 328{
 329        struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
 330        new_list->item = item;
 331        new_list->next = *list_p;
 332        *list_p = new_list;
 333        return new_list;
 334}
 335
 336void free_commit_list(struct commit_list *list)
 337{
 338        while (list) {
 339                struct commit_list *temp = list;
 340                list = temp->next;
 341                free(temp);
 342        }
 343}
 344
 345struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
 346{
 347        struct commit_list **pp = list;
 348        struct commit_list *p;
 349        while ((p = *pp) != NULL) {
 350                if (p->item->date < item->date) {
 351                        break;
 352                }
 353                pp = &p->next;
 354        }
 355        return commit_list_insert(item, pp);
 356}
 357
 358        
 359void sort_by_date(struct commit_list **list)
 360{
 361        struct commit_list *ret = NULL;
 362        while (*list) {
 363                insert_by_date((*list)->item, &ret);
 364                *list = (*list)->next;
 365        }
 366        *list = ret;
 367}
 368
 369struct commit *pop_most_recent_commit(struct commit_list **list,
 370                                      unsigned int mark)
 371{
 372        struct commit *ret = (*list)->item;
 373        struct commit_list *parents = ret->parents;
 374        struct commit_list *old = *list;
 375
 376        *list = (*list)->next;
 377        free(old);
 378
 379        while (parents) {
 380                struct commit *commit = parents->item;
 381                parse_commit(commit);
 382                if (!(commit->object.flags & mark)) {
 383                        commit->object.flags |= mark;
 384                        insert_by_date(commit, list);
 385                }
 386                parents = parents->next;
 387        }
 388        return ret;
 389}
 390
 391void clear_commit_marks(struct commit *commit, unsigned int mark)
 392{
 393        struct commit_list *parents;
 394
 395        parents = commit->parents;
 396        commit->object.flags &= ~mark;
 397        while (parents) {
 398                struct commit *parent = parents->item;
 399                if (parent && parent->object.parsed &&
 400                    (parent->object.flags & mark))
 401                        clear_commit_marks(parent, mark);
 402                parents = parents->next;
 403        }
 404}
 405
 406/*
 407 * Generic support for pretty-printing the header
 408 */
 409static int get_one_line(const char *msg, unsigned long len)
 410{
 411        int ret = 0;
 412
 413        while (len--) {
 414                char c = *msg++;
 415                if (!c)
 416                        break;
 417                ret++;
 418                if (c == '\n')
 419                        break;
 420        }
 421        return ret;
 422}
 423
 424static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const char *line)
 425{
 426        char *date;
 427        int namelen;
 428        unsigned long time;
 429        int tz, ret;
 430        const char *filler = "    ";
 431
 432        if (fmt == CMIT_FMT_ONELINE)
 433                return 0;
 434        date = strchr(line, '>');
 435        if (!date)
 436                return 0;
 437        namelen = ++date - line;
 438        time = strtoul(date, &date, 10);
 439        tz = strtol(date, NULL, 10);
 440
 441        ret = sprintf(buf, "%s: %.*s%.*s\n", what,
 442                      (fmt == CMIT_FMT_FULLER) ? 4 : 0,
 443                      filler, namelen, line);
 444        switch (fmt) {
 445        case CMIT_FMT_MEDIUM:
 446                ret += sprintf(buf + ret, "Date:   %s\n", show_date(time, tz));
 447                break;
 448        case CMIT_FMT_FULLER:
 449                ret += sprintf(buf + ret, "%sDate: %s\n", what, show_date(time, tz));
 450                break;
 451        default:
 452                /* notin' */
 453                break;
 454        }
 455        return ret;
 456}
 457
 458static int is_empty_line(const char *line, int len)
 459{
 460        while (len && isspace(line[len-1]))
 461                len--;
 462        return !len;
 463}
 464
 465static int add_merge_info(enum cmit_fmt fmt, char *buf, const struct commit *commit, int abbrev)
 466{
 467        struct commit_list *parent = commit->parents;
 468        int offset;
 469
 470        if ((fmt == CMIT_FMT_ONELINE) || !parent || !parent->next)
 471                return 0;
 472
 473        offset = sprintf(buf, "Merge:");
 474
 475        while (parent) {
 476                struct commit *p = parent->item;
 477                const char *hex = abbrev
 478                        ? find_unique_abbrev(p->object.sha1, abbrev)
 479                        : sha1_to_hex(p->object.sha1);
 480                char *dots = (abbrev && strlen(hex) != 40) ? "..." : "";
 481                parent = parent->next;
 482
 483                offset += sprintf(buf + offset, " %s%s", hex, dots);
 484        }
 485        buf[offset++] = '\n';
 486        return offset;
 487}
 488
 489unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit, unsigned long len, char *buf, unsigned long space, int abbrev)
 490{
 491        int hdr = 1, body = 0;
 492        unsigned long offset = 0;
 493        int indent = (fmt == CMIT_FMT_ONELINE) ? 0 : 4;
 494        int parents_shown = 0;
 495        const char *msg = commit->buffer;
 496
 497        for (;;) {
 498                const char *line = msg;
 499                int linelen = get_one_line(msg, len);
 500
 501                if (!linelen)
 502                        break;
 503
 504                /*
 505                 * We want some slop for indentation and a possible
 506                 * final "...". Thus the "+ 20".
 507                 */
 508                if (offset + linelen + 20 > space) {
 509                        memcpy(buf + offset, "    ...\n", 8);
 510                        offset += 8;
 511                        break;
 512                }
 513
 514                msg += linelen;
 515                len -= linelen;
 516                if (hdr) {
 517                        if (linelen == 1) {
 518                                hdr = 0;
 519                                if (fmt != CMIT_FMT_ONELINE)
 520                                        buf[offset++] = '\n';
 521                                continue;
 522                        }
 523                        if (fmt == CMIT_FMT_RAW) {
 524                                memcpy(buf + offset, line, linelen);
 525                                offset += linelen;
 526                                continue;
 527                        }
 528                        if (!memcmp(line, "parent ", 7)) {
 529                                if (linelen != 48)
 530                                        die("bad parent line in commit");
 531                                continue;
 532                        }
 533
 534                        if (!parents_shown) {
 535                                offset += add_merge_info(fmt, buf + offset,
 536                                                         commit, abbrev);
 537                                parents_shown = 1;
 538                                continue;
 539                        }
 540                        /*
 541                         * MEDIUM == DEFAULT shows only author with dates.
 542                         * FULL shows both authors but not dates.
 543                         * FULLER shows both authors and dates.
 544                         */
 545                        if (!memcmp(line, "author ", 7))
 546                                offset += add_user_info("Author", fmt,
 547                                                        buf + offset,
 548                                                        line + 7);
 549                        if (!memcmp(line, "committer ", 10) &&
 550                            (fmt == CMIT_FMT_FULL || fmt == CMIT_FMT_FULLER))
 551                                offset += add_user_info("Commit", fmt,
 552                                                        buf + offset,
 553                                                        line + 10);
 554                        continue;
 555                }
 556
 557                if (is_empty_line(line, linelen)) {
 558                        if (!body)
 559                                continue;
 560                        if (fmt == CMIT_FMT_SHORT)
 561                                break;
 562                } else {
 563                        body = 1;
 564                }
 565
 566                memset(buf + offset, ' ', indent);
 567                memcpy(buf + offset + indent, line, linelen);
 568                offset += linelen + indent;
 569                if (fmt == CMIT_FMT_ONELINE)
 570                        break;
 571        }
 572        while (offset && isspace(buf[offset-1]))
 573                offset--;
 574        /* Make sure there is an EOLN for the non-oneline case */
 575        if (fmt != CMIT_FMT_ONELINE)
 576                buf[offset++] = '\n';
 577        buf[offset] = '\0';
 578        return offset;
 579}
 580
 581struct commit *pop_commit(struct commit_list **stack)
 582{
 583        struct commit_list *top = *stack;
 584        struct commit *item = top ? top->item : NULL;
 585
 586        if (top) {
 587                *stack = top->next;
 588                free(top);
 589        }
 590        return item;
 591}
 592
 593int count_parents(struct commit * commit)
 594{
 595        int count = 0;
 596        struct commit_list * parents = commit->parents;
 597        for (count=0;parents; parents=parents->next,count++)
 598          ;
 599        return count;
 600}
 601
 602void topo_sort_default_setter(struct commit *c, void *data)
 603{
 604        c->object.util = data;
 605}
 606
 607void *topo_sort_default_getter(struct commit *c)
 608{
 609        return c->object.util;
 610}
 611
 612/*
 613 * Performs an in-place topological sort on the list supplied.
 614 */
 615void sort_in_topological_order(struct commit_list ** list, int lifo)
 616{
 617        sort_in_topological_order_fn(list, lifo, topo_sort_default_setter,
 618                                     topo_sort_default_getter);
 619}
 620
 621void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
 622                                  topo_sort_set_fn_t setter,
 623                                  topo_sort_get_fn_t getter)
 624{
 625        struct commit_list * next = *list;
 626        struct commit_list * work = NULL, **insert;
 627        struct commit_list ** pptr = list;
 628        struct sort_node * nodes;
 629        struct sort_node * next_nodes;
 630        int count = 0;
 631
 632        /* determine the size of the list */
 633        while (next) {
 634                next = next->next;
 635                count++;
 636        }
 637        
 638        if (!count)
 639                return;
 640        /* allocate an array to help sort the list */
 641        nodes = xcalloc(count, sizeof(*nodes));
 642        /* link the list to the array */
 643        next_nodes = nodes;
 644        next=*list;
 645        while (next) {
 646                next_nodes->list_item = next;
 647                setter(next->item, next_nodes);
 648                next_nodes++;
 649                next = next->next;
 650        }
 651        /* update the indegree */
 652        next=*list;
 653        while (next) {
 654                struct commit_list * parents = next->item->parents;
 655                while (parents) {
 656                        struct commit * parent=parents->item;
 657                        struct sort_node * pn = (struct sort_node *) getter(parent);
 658
 659                        if (pn)
 660                                pn->indegree++;
 661                        parents=parents->next;
 662                }
 663                next=next->next;
 664        }
 665        /* 
 666         * find the tips
 667         *
 668         * tips are nodes not reachable from any other node in the list 
 669         * 
 670         * the tips serve as a starting set for the work queue.
 671         */
 672        next=*list;
 673        insert = &work;
 674        while (next) {
 675                struct sort_node * node = (struct sort_node *) getter(next->item);
 676
 677                if (node->indegree == 0) {
 678                        insert = &commit_list_insert(next->item, insert)->next;
 679                }
 680                next=next->next;
 681        }
 682
 683        /* process the list in topological order */
 684        if (!lifo)
 685                sort_by_date(&work);
 686        while (work) {
 687                struct commit * work_item = pop_commit(&work);
 688                struct sort_node * work_node = (struct sort_node *) getter(work_item);
 689                struct commit_list * parents = work_item->parents;
 690
 691                while (parents) {
 692                        struct commit * parent=parents->item;
 693                        struct sort_node * pn = (struct sort_node *) getter(parent);
 694
 695                        if (pn) {
 696                                /*
 697                                 * parents are only enqueued for emission 
 698                                 * when all their children have been emitted thereby
 699                                 * guaranteeing topological order.
 700                                 */
 701                                pn->indegree--;
 702                                if (!pn->indegree) {
 703                                        if (!lifo)
 704                                                insert_by_date(parent, &work);
 705                                        else
 706                                                commit_list_insert(parent, &work);
 707                                }
 708                        }
 709                        parents=parents->next;
 710                }
 711                /*
 712                 * work_item is a commit all of whose children
 713                 * have already been emitted. we can emit it now.
 714                 */
 715                *pptr = work_node->list_item;
 716                pptr = &(*pptr)->next;
 717                *pptr = NULL;
 718                setter(work_item, NULL);
 719        }
 720        free(nodes);
 721}