Tell which packfile is corrupt when we die.
[git] / 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 }