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