commit.c

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