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