1#include "tag.h"
2#include "commit.h"
3#include "cache.h"
4int save_commit_buffer = 1;
6struct 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 /*
16 * reference to original list item that we will re-use
17 * on output.
18 */
19 struct commit_list * list_item;
20};
22const char *commit_type = "commit";
24enum 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}
41static 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}
54struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
56 int quiet)
57{
58 struct object *obj = deref_tag(parse_object(sha1));
59 if (!obj)
61 return NULL;
62 return check_commit(obj, sha1, quiet);
63}
64struct commit *lookup_commit_reference(const unsigned char *sha1)
66{
67 return lookup_commit_reference_gently(sha1, 0);
68}
69struct 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}
84static unsigned long parse_commit_date(const char *buf)
86{
87 unsigned long date;
88 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}
102static struct commit_graft {
104 unsigned char sha1[20];
105 int nr_parent;
106 unsigned char parent[0][20]; /* more */
107} **commit_graft;
108static int commit_graft_alloc, commit_graft_nr;
109static 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}
128static 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 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}
187static 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}
198int 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 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 graft = lookup_commit_graft(item->object.sha1);
220 while (!memcmp(bufptr, "parent ", 7)) {
221 struct commit *new_parent;
222 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}
248int parse_commit(struct commit *item)
250{
251 char type[20];
252 void *buffer;
253 unsigned long size;
254 int ret;
255 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}
275struct 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}
284void 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}
293struct 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
308void 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}
317struct 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 *list = (*list)->next;
326 free(old);
327 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/*
341 * Generic support for pretty-printing the header
342 */
343static int get_one_line(const char *msg, unsigned long len)
344{
345 int ret = 0;
346 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}
357static 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 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 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}
379static int is_empty_line(const char *line, int len)
381{
382 while (len && isspace(line[len-1]))
383 len--;
384 return !len;
385}
386static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents)
388{
389 int offset = 0;
390 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}
407unsigned 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 for (;;) {
416 const char *line = msg;
417 int linelen = get_one_line(msg, len);
418 if (!linelen)
420 break;
421 /*
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 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 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 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}
488struct commit *pop_commit(struct commit_list **stack)
490{
491 struct commit_list *top = *stack;
492 struct commit *item = top ? top->item : NULL;
493 if (top) {
495 *stack = top->next;
496 free(top);
497 }
498 return item;
499}
500int 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/*
511 * Performs an in-place topological sort on the list supplied.
512 */
513void 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 /* 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 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 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}