e51eda15243614d83948f31ee3814120ad61b1fe
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,
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}
53struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
55 int quiet)
56{
57 struct object *obj = deref_tag(parse_object(sha1));
58 if (!obj)
60 return NULL;
61 return check_commit(obj, sha1, quiet);
62}
63struct commit *lookup_commit_reference(const unsigned char *sha1)
65{
66 return lookup_commit_reference_gently(sha1, 0);
67}
68struct 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}
83static unsigned long parse_commit_date(const char *buf)
85{
86 unsigned long date;
87 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}
101static struct commit_graft {
103 unsigned char sha1[20];
104 int nr_parent;
105 unsigned char parent[0][20]; /* more */
106} **commit_graft;
107static int commit_graft_alloc, commit_graft_nr;
108static 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}
127static 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 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}
186static 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}
197int 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 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 graft = lookup_commit_graft(item->object.sha1);
219 while (!memcmp(bufptr, "parent ", 7)) {
220 struct commit *new_parent;
221 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}
247int parse_commit(struct commit *item)
249{
250 char type[20];
251 void *buffer;
252 unsigned long size;
253 int ret;
254 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}
274struct 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}
283void 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}
292struct 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
307void 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}
316struct 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 *list = (*list)->next;
325 free(old);
326 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/*
340 * Generic support for pretty-printing the header
341 */
342static int get_one_line(const char *msg, unsigned long len)
343{
344 int ret = 0;
345 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}
356static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf, const char *line)
358{
359 char *date;
360 unsigned int namelen;
361 unsigned long time;
362 int tz, ret;
363 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 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}
378static int is_empty_line(const char *line, int len)
380{
381 while (len && isspace(line[len-1]))
382 len--;
383 return !len;
384}
385static int add_parent_info(enum cmit_fmt fmt, char *buf, const char *line, int parents)
387{
388 int offset = 0;
389 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}
406unsigned 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 for (;;) {
415 const char *line = msg;
416 int linelen = get_one_line(msg, len);
417 if (!linelen)
419 break;
420 /*
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 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 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 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}
487struct commit *pop_commit(struct commit_list **stack)
489{
490 struct commit_list *top = *stack;
491 struct commit *item = top ? top->item : NULL;
492 if (top) {
494 *stack = top->next;
495 free(top);
496 }
497 return item;
498}
499int 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/*
510 * Performs an in-place topological sort on the list supplied.
511 */
512void 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 /* 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 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 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}