Andrew's git / gitweb.git / commit.c
?
commit.con commit Teach parse_commit_buffer about grafting. (5da5c8f)
   1#include <ctype.h>
   2#include "tag.h"
   3#include "commit.h"
   4#include "cache.h"
   5
   6struct sort_node
   7{
   8        /*
   9         * the number of children of the associated commit
  10         * that also occur in the list being sorted.
  11         */
  12        unsigned int indegree;
  13
  14        /*
  15         * reference to original list item that we will re-use
  16         * on output.
  17         */
  18        struct commit_list * list_item;
  19
  20};
  21
  22const char *commit_type = "commit";
  23
  24enum cmit_fmt get_commit_format(const char *arg)
  25{
  26        if (!*arg)
  27                return CMIT_FMT_DEFAULT;
  28        if (!strcmp(arg, "=raw"))
  29                return CMIT_FMT_RAW;
  30        if (!strcmp(arg, "=medium"))
  31                return CMIT_FMT_MEDIUM;
  32        if (!strcmp(arg, "=short"))
  33                return CMIT_FMT_SHORT;
  34        if (!strcmp(arg, "=full"))
  35                return CMIT_FMT_FULL;
  36        die("invalid --pretty format");
  37}
  38
  39static struct commit *check_commit(struct object *obj, const unsigned char *sha1)
  40{
  41        if (obj->type != commit_type) {
  42                error("Object %s is a %s, not a commit", 
  43                      sha1_to_hex(sha1), obj->type);
  44                return NULL;
  45        }
  46        return (struct commit *) obj;
  47}
  48
  49struct commit *lookup_commit_reference(const unsigned char *sha1)
  50{
  51        struct object *obj = parse_object(sha1);
  52
  53        if (!obj)
  54                return NULL;
  55        while (obj->type == tag_type)
  56                obj = parse_object(((struct tag *)obj)->tagged->sha1);
  57
  58        return check_commit(obj, sha1);
  59}
  60
  61struct commit *lookup_commit(const unsigned char *sha1)
  62{
  63        struct object *obj = lookup_object(sha1);
  64        if (!obj) {
  65                struct commit *ret = xmalloc(sizeof(struct commit));
  66                memset(ret, 0, sizeof(struct commit));
  67                created_object(sha1, &ret->object);
  68                ret->object.type = commit_type;
  69                return ret;
  70        }
  71        if (!obj->type)
  72                obj->type = commit_type;
  73        return check_commit(obj, sha1);
  74}
  75
  76static unsigned long parse_commit_date(const char *buf)
  77{
  78        unsigned long date;
  79
  80        if (memcmp(buf, "author", 6))
  81                return 0;
  82        while (*buf++ != '\n')
  83                /* nada */;
  84        if (memcmp(buf, "committer", 9))
  85                return 0;
  86        while (*buf++ != '>')
  87                /* nada */;
  88        date = strtoul(buf, NULL, 10);
  89        if (date == ULONG_MAX)
  90                date = 0;
  91        return date;
  92}
  93
  94static struct commit_graft {
  95        unsigned char sha1[20];
  96        int nr_parent;
  97        unsigned char parent[0][20]; /* more */
  98} **commit_graft;
  99static int commit_graft_alloc, commit_graft_nr;
 100
 101static int commit_graft_pos(const unsigned char *sha1)
 102{
 103        int lo, hi;
 104        lo = 0;
 105        hi = commit_graft_nr;
 106        while (lo < hi) {
 107                int mi = (lo + hi) / 2;
 108                struct commit_graft *graft = commit_graft[mi];
 109                int cmp = memcmp(sha1, graft->sha1, 20);
 110                if (!cmp)
 111                        return mi;
 112                if (cmp < 0)
 113                        hi = mi;
 114                else
 115                        lo = mi + 1;
 116        }
 117        return -lo - 1;
 118}
 119
 120static void prepare_commit_graft(void)
 121{
 122        char *graft_file = get_graft_file();
 123        FILE *fp = fopen(graft_file, "r");
 124        char buf[1024];
 125        if (!fp) {
 126                commit_graft = (struct commit_graft **) "hack";
 127                return;
 128        }
 129        while (fgets(buf, sizeof(buf), fp)) {
 130                /* The format is just "Commit Parent1 Parent2 ...\n" */
 131                int len = strlen(buf);
 132                int i;
 133                struct commit_graft *graft = NULL;
 134
 135                if (buf[len-1] == '\n')
 136                        buf[--len] = 0;
 137                if (buf[0] == '#')
 138                        continue;
 139                if ((len + 1) % 41) {
 140                bad_graft_data:
 141                        error("bad graft data: %s", buf);
 142                        free(graft);
 143                        continue;
 144                }
 145                i = (len + 1) / 41 - 1;
 146                graft = xmalloc(sizeof(*graft) + 20 * i);
 147                graft->nr_parent = i;
 148                if (get_sha1_hex(buf, graft->sha1))
 149                        goto bad_graft_data;
 150                for (i = 40; i < len; i += 41) {
 151                        if (buf[i] != ' ')
 152                                goto bad_graft_data;
 153                        if (get_sha1_hex(buf + i + 1, graft->parent[i/41]))
 154                                goto bad_graft_data;
 155                }
 156                i = commit_graft_pos(graft->sha1);
 157                if (0 <= i) {
 158                        error("duplicate graft data: %s", buf);
 159                        free(graft);
 160                        continue;
 161                }
 162                i = -i - 1;
 163                if (commit_graft_alloc <= ++commit_graft_nr) {
 164                        commit_graft_alloc = alloc_nr(commit_graft_alloc);
 165                        commit_graft = xrealloc(commit_graft,
 166                                                sizeof(*commit_graft) *
 167                                                commit_graft_alloc);
 168                }
 169                if (i < commit_graft_nr)
 170                        memmove(commit_graft + i + 1,
 171                                commit_graft + i,
 172                                (commit_graft_nr - i - 1) *
 173                                sizeof(*commit_graft));
 174                commit_graft[i] = graft;
 175        }
 176        fclose(fp);
 177}
 178
 179static struct commit_graft *lookup_commit_graft(const unsigned char *sha1)
 180{
 181        int pos;
 182        if (!commit_graft)
 183                prepare_commit_graft();
 184        pos = commit_graft_pos(sha1);
 185        if (pos < 0)
 186                return NULL;
 187        return commit_graft[pos];
 188}
 189
 190int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)
 191{
 192        char *bufptr = buffer;
 193        unsigned char parent[20];
 194        struct commit_list **pptr;
 195        struct commit_graft *graft;
 196
 197        if (item->object.parsed)
 198                return 0;
 199        item->object.parsed = 1;
 200        if (memcmp(bufptr, "tree ", 5))
 201                return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
 202        if (get_sha1_hex(bufptr + 5, parent) < 0)
 203                return error("bad tree pointer in commit %s\n", sha1_to_hex(item->object.sha1));
 204        item->tree = lookup_tree(parent);
 205        if (item->tree)
 206                add_ref(&item->object, &item->tree->object);
 207        bufptr += 46; /* "tree " + "hex sha1" + "\n" */
 208        pptr = &item->parents;
 209
 210        graft = lookup_commit_graft(item->object.sha1);
 211        while (!memcmp(bufptr, "parent ", 7)) {
 212                struct commit *new_parent;
 213
 214                if (get_sha1_hex(bufptr + 7, parent) || bufptr[47] != '\n')
 215                        return error("bad parents in commit %s", sha1_to_hex(item->object.sha1));
 216                bufptr += 48;
 217                if (graft)
 218                        continue;
 219                new_parent = lookup_commit(parent);
 220                if (new_parent) {
 221                        pptr = &commit_list_insert(new_parent, pptr)->next;
 222                        add_ref(&item->object, &new_parent->object);
 223                }
 224        }
 225        if (graft) {
 226                int i;
 227                struct commit *new_parent;
 228                for (i = 0; i < graft->nr_parent; i++) {
 229                        new_parent = lookup_commit(graft->parent[i]);
 230                        if (!new_parent)
 231                                continue;
 232                        pptr = &commit_list_insert(new_parent, pptr)->next;
 233                        add_ref(&item->object, &new_parent->object);
 234                }
 235        }
 236        item->date = parse_commit_date(bufptr);
 237        return 0;
 238}
 239
 240int parse_commit(struct commit *item)
 241{
 242        char type[20];
 243        void *buffer;
 244        unsigned long size;
 245        int ret;
 246
 247        if (item->object.parsed)
 248                return 0;
 249        buffer = read_sha1_file(item->object.sha1, type, &size);
 250        if (!buffer)
 251                return error("Could not read %s",
 252                             sha1_to_hex(item->object.sha1));
 253        if (strcmp(type, commit_type)) {
 254                free(buffer);
 255                return error("Object %s not a commit",
 256                             sha1_to_hex(item->object.sha1));
 257        }
 258        ret = parse_commit_buffer(item, buffer, size);
 259        if (!ret) {
 260                item->buffer = buffer;
 261                return 0;
 262        }
 263        free(buffer);
 264        return ret;
 265}
 266
 267struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 268{
 269        struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
 270        new_list->item = item;
 271        new_list->next = *list_p;
 272        *list_p = new_list;
 273        return new_list;
 274}
 275
 276void free_commit_list(struct commit_list *list)
 277{
 278        while (list) {
 279                struct commit_list *temp = list;
 280                list = temp->next;
 281                free(temp);
 282        }
 283}
 284
 285struct commit_list * insert_by_date(struct commit *item, struct commit_list **list)
 286{
 287        struct commit_list **pp = list;
 288        struct commit_list *p;
 289        while ((p = *pp) != NULL) {
 290                if (p->item->date < item->date) {
 291                        break;
 292                }
 293                pp = &p->next;
 294        }
 295        return commit_list_insert(item, pp);
 296}
 297
 298        
 299void sort_by_date(struct commit_list **list)
 300{
 301        struct commit_list *ret = NULL;
 302        while (*list) {
 303                insert_by_date((*list)->item, &ret);
 304                *list = (*list)->next;
 305        }
 306        *list = ret;
 307}
 308
 309struct commit *pop_most_recent_commit(struct commit_list **list,
 310                                      unsigned int mark)
 311{
 312        struct commit *ret = (*list)->item;
 313        struct commit_list *parents = ret->parents;
 314        struct commit_list *old = *list;
 315
 316        *list = (*list)->next;
 317        free(old);
 318
 319        while (parents) {
 320                struct commit *commit = parents->item;
 321                parse_commit(commit);
 322                if (!(commit->object.flags & mark)) {
 323                        commit->object.flags |= mark;
 324                        insert_by_date(commit, list);
 325                }
 326                parents = parents->next;
 327        }
 328        return ret;
 329}
 330
 331/*
 332 * Generic support for pretty-printing the header
 333 */
 334static int get_one_line(const char *msg, unsigned long len)
 335{
 336        int ret = 0;
 337
 338        while (len--) {
 339                char c = *msg++;
 340                ret++;
 341                if (c == '\n')
 342                        break;
 343                if (!c)
 344                        return 0;
 345        }
 346        return ret;
 347}
 348
 349static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const char *line)
 350{
 351        char *date;
 352        unsigned int namelen;
 353        unsigned long time;
 354        int tz, ret;
 355
 356        date = strchr(line, '>');
 357        if (!date)
 358                return 0;
 359        namelen = ++date - line;
 360        time = strtoul(date, &date, 10);
 361        tz = strtol(date, NULL, 10);
 362
 363        ret = sprintf(buf, "%s: %.*s\n", what, namelen, line);
 364        if (fmt == CMIT_FMT_MEDIUM)
 365                ret += sprintf(buf + ret, "Date:   %s\n", show_date(time, tz));
 366        return ret;
 367}
 368
 369static int is_empty_line(const char *line, int len)
 370{
 371        while (len && isspace(line[len-1]))
 372                len--;
 373        return !len;
 374}
 375
 376static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents)
 377{
 378        int offset = 0;
 379        switch (parents) {
 380        case 1:
 381                break;
 382        case 2:
 383                /* Go back to the previous line: 40 characters of previous parent, and one '\n' */
 384                offset = sprintf(buf, "Merge: %.40s\n", line-41);
 385                /* Fallthrough */
 386        default:
 387                /* Replace the previous '\n' with a space */
 388                buf[offset-1] = ' ';
 389                offset += sprintf(buf + offset, "%.40s\n", line+7);
 390        }
 391        return offset;
 392}
 393
 394unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space)
 395{
 396        int hdr = 1, body = 0;
 397        unsigned long offset = 0;
 398        int parents = 0;
 399
 400        for (;;) {
 401                const char *line = msg;
 402                int linelen = get_one_line(msg, len);
 403
 404                if (!linelen)
 405                        break;
 406
 407                /*
 408                 * We want some slop for indentation and a possible
 409                 * final "...". Thus the "+ 20".
 410                 */
 411                if (offset + linelen + 20 > space) {
 412                        memcpy(buf + offset, "    ...\n", 8);
 413                        offset += 8;
 414                        break;
 415                }
 416
 417                msg += linelen;
 418                len -= linelen;
 419                if (hdr) {
 420                        if (linelen == 1) {
 421                                hdr = 0;
 422                                buf[offset++] = '\n';
 423                                continue;
 424                        }
 425                        if (fmt == CMIT_FMT_RAW) {
 426                                memcpy(buf + offset, line, linelen);
 427                                offset += linelen;
 428                                continue;
 429                        }
 430                        if (!memcmp(line, "parent ", 7)) {
 431                                if (linelen != 48)
 432                                        die("bad parent line in commit");
 433                                offset += add_parent_info(fmt, buf + offset, line, ++parents);
 434                        }
 435                        if (!memcmp(line, "author ", 7))
 436                                offset += add_user_info("Author", fmt, buf + offset, line + 7);
 437                        if (fmt == CMIT_FMT_FULL) {
 438                                if (!memcmp(line, "committer ", 10))
 439                                        offset += add_user_info("Commit", fmt, buf + offset, line + 10);
 440                        }
 441                        continue;
 442                }
 443
 444                if (is_empty_line(line, linelen)) {
 445                        if (!body)
 446                                continue;
 447                        if (fmt == CMIT_FMT_SHORT)
 448                                break;
 449                } else {
 450                        body = 1;
 451                }
 452                memset(buf + offset, ' ', 4);
 453                memcpy(buf + offset + 4, line, linelen);
 454                offset += linelen + 4;
 455        }
 456        /* Make sure there is an EOLN */
 457        if (buf[offset - 1] != '\n')
 458                buf[offset++] = '\n';
 459        buf[offset] = '\0';
 460        return offset;
 461}
 462
 463struct commit *pop_commit(struct commit_list **stack)
 464{
 465        struct commit_list *top = *stack;
 466        struct commit *item = top ? top->item : NULL;
 467
 468        if (top) {
 469                *stack = top->next;
 470                free(top);
 471        }
 472        return item;
 473}
 474
 475int count_parents(struct commit * commit)
 476{
 477        int count = 0;
 478        struct commit_list * parents = commit->parents;
 479        for (count=0;parents; parents=parents->next,count++)
 480          ;
 481        return count;
 482}
 483
 484/*
 485 * Performs an in-place topological sort on the list supplied.
 486 */
 487void sort_in_topological_order(struct commit_list ** list)
 488{
 489        struct commit_list * next = *list;
 490        struct commit_list * work = NULL;
 491        struct commit_list ** pptr = list;
 492        struct sort_node * nodes;
 493        struct sort_node * next_nodes;
 494        int count = 0;
 495
 496        /* determine the size of the list */
 497        while (next) {
 498                next = next->next;
 499                count++;
 500        }
 501        /* allocate an array to help sort the list */
 502        nodes = xcalloc(count, sizeof(*nodes));
 503        /* link the list to the array */
 504        next_nodes = nodes;
 505        next=*list;
 506        while (next) {
 507                next_nodes->list_item = next;
 508                next->item->object.util = next_nodes;
 509                next_nodes++;
 510                next = next->next;
 511        }
 512        /* update the indegree */
 513        next=*list;
 514        while (next) {
 515                struct commit_list * parents = next->item->parents;
 516                while (parents) {
 517                        struct commit * parent=parents->item;
 518                        struct sort_node * pn = (struct sort_node *)parent->object.util;
 519                        
 520                        if (pn)
 521                                pn->indegree++;
 522                        parents=parents->next;
 523                }
 524                next=next->next;
 525        }
 526        /* 
 527         * find the tips
 528         *
 529         * tips are nodes not reachable from any other node in the list 
 530         * 
 531         * the tips serve as a starting set for the work queue.
 532         */
 533        next=*list;
 534        while (next) {
 535                struct sort_node * node = (struct sort_node *)next->item->object.util;
 536
 537                if (node->indegree == 0) {
 538                        commit_list_insert(next->item, &work);
 539                }
 540                next=next->next;
 541        }
 542        /* process the list in topological order */
 543        while (work) {
 544                struct commit * work_item = pop_commit(&work);
 545                struct sort_node * work_node = (struct sort_node *)work_item->object.util;
 546                struct commit_list * parents = work_item->parents;
 547
 548                while (parents) {
 549                        struct commit * parent=parents->item;
 550                        struct sort_node * pn = (struct sort_node *)parent->object.util;
 551                        
 552                        if (pn) {
 553                                /* 
 554                                 * parents are only enqueued for emission 
 555                                 * when all their children have been emitted thereby
 556                                 * guaranteeing topological order.
 557                                 */
 558                                pn->indegree--;
 559                                if (!pn->indegree) 
 560                                        commit_list_insert(parent, &work);
 561                        }
 562                        parents=parents->next;
 563                }
 564                /*
 565                 * work_item is a commit all of whose children
 566                 * have already been emitted. we can emit it now.
 567                 */
 568                *pptr = work_node->list_item;
 569                pptr = &(*pptr)->next;
 570                *pptr = NULL;
 571                work_item->object.util = NULL;
 572        }
 573        free(nodes);
 574}