commit.c

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