commit.c

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