6 int save_commit_buffer
= 1;
11 * the number of children of the associated commit
12 * that also occur in the list being sorted.
14 unsigned int indegree
;
17 * reference to original list item that we will re-use
20 struct commit_list
* list_item
;
24 const char *commit_type
= "commit";
31 { "raw", 1, CMIT_FMT_RAW
},
32 { "medium", 1, CMIT_FMT_MEDIUM
},
33 { "short", 1, CMIT_FMT_SHORT
},
34 { "email", 1, CMIT_FMT_EMAIL
},
35 { "full", 5, CMIT_FMT_FULL
},
36 { "fuller", 5, CMIT_FMT_FULLER
},
37 { "oneline", 1, CMIT_FMT_ONELINE
},
40 enum cmit_fmt
get_commit_format(const char *arg
)
45 return CMIT_FMT_DEFAULT
;
48 for (i
= 0; i
< ARRAY_SIZE(cmt_fmts
); i
++) {
49 if (!strncmp(arg
, cmt_fmts
[i
].n
, cmt_fmts
[i
].cmp_len
))
53 die("invalid --pretty format: %s", arg
);
56 static struct commit
*check_commit(struct object
*obj
,
57 const unsigned char *sha1
,
60 if (obj
->type
!= OBJ_COMMIT
) {
62 error("Object %s is a %s, not a commit",
63 sha1_to_hex(sha1
), typename(obj
->type
));
66 return (struct commit
*) obj
;
69 struct commit
*lookup_commit_reference_gently(const unsigned char *sha1
,
72 struct object
*obj
= deref_tag(parse_object(sha1
), NULL
, 0);
76 return check_commit(obj
, sha1
, quiet
);
79 struct commit
*lookup_commit_reference(const unsigned char *sha1
)
81 return lookup_commit_reference_gently(sha1
, 0);
84 struct commit
*lookup_commit(const unsigned char *sha1
)
86 struct object
*obj
= lookup_object(sha1
);
88 struct commit
*ret
= alloc_commit_node();
89 created_object(sha1
, &ret
->object
);
90 ret
->object
.type
= OBJ_COMMIT
;
94 obj
->type
= OBJ_COMMIT
;
95 return check_commit(obj
, sha1
, 0);
98 static unsigned long parse_commit_date(const char *buf
)
102 if (memcmp(buf
, "author", 6))
104 while (*buf
++ != '\n')
106 if (memcmp(buf
, "committer", 9))
108 while (*buf
++ != '>')
110 date
= strtoul(buf
, NULL
, 10);
111 if (date
== ULONG_MAX
)
116 static struct commit_graft
**commit_graft
;
117 static int commit_graft_alloc
, commit_graft_nr
;
119 static int commit_graft_pos(const unsigned char *sha1
)
123 hi
= commit_graft_nr
;
125 int mi
= (lo
+ hi
) / 2;
126 struct commit_graft
*graft
= commit_graft
[mi
];
127 int cmp
= hashcmp(sha1
, graft
->sha1
);
138 int register_commit_graft(struct commit_graft
*graft
, int ignore_dups
)
140 int pos
= commit_graft_pos(graft
->sha1
);
146 free(commit_graft
[pos
]);
147 commit_graft
[pos
] = graft
;
152 if (commit_graft_alloc
<= ++commit_graft_nr
) {
153 commit_graft_alloc
= alloc_nr(commit_graft_alloc
);
154 commit_graft
= xrealloc(commit_graft
,
155 sizeof(*commit_graft
) *
158 if (pos
< commit_graft_nr
)
159 memmove(commit_graft
+ pos
+ 1,
161 (commit_graft_nr
- pos
- 1) *
162 sizeof(*commit_graft
));
163 commit_graft
[pos
] = graft
;
167 struct commit_graft
*read_graft_line(char *buf
, int len
)
169 /* The format is just "Commit Parent1 Parent2 ...\n" */
171 struct commit_graft
*graft
= NULL
;
173 if (buf
[len
-1] == '\n')
175 if (buf
[0] == '#' || buf
[0] == '\0')
177 if ((len
+ 1) % 41) {
179 error("bad graft data: %s", buf
);
183 i
= (len
+ 1) / 41 - 1;
184 graft
= xmalloc(sizeof(*graft
) + 20 * i
);
185 graft
->nr_parent
= i
;
186 if (get_sha1_hex(buf
, graft
->sha1
))
188 for (i
= 40; i
< len
; i
+= 41) {
191 if (get_sha1_hex(buf
+ i
+ 1, graft
->parent
[i
/41]))
197 int read_graft_file(const char *graft_file
)
199 FILE *fp
= fopen(graft_file
, "r");
203 while (fgets(buf
, sizeof(buf
), fp
)) {
204 /* The format is just "Commit Parent1 Parent2 ...\n" */
205 int len
= strlen(buf
);
206 struct commit_graft
*graft
= read_graft_line(buf
, len
);
209 if (register_commit_graft(graft
, 1))
210 error("duplicate graft data: %s", buf
);
216 static void prepare_commit_graft(void)
218 static int commit_graft_prepared
;
221 if (commit_graft_prepared
)
223 graft_file
= get_graft_file();
224 read_graft_file(graft_file
);
225 commit_graft_prepared
= 1;
228 static struct commit_graft
*lookup_commit_graft(const unsigned char *sha1
)
231 prepare_commit_graft();
232 pos
= commit_graft_pos(sha1
);
235 return commit_graft
[pos
];
238 int parse_commit_buffer(struct commit
*item
, void *buffer
, unsigned long size
)
241 char *bufptr
= buffer
;
242 unsigned char parent
[20];
243 struct commit_list
**pptr
;
244 struct commit_graft
*graft
;
247 if (item
->object
.parsed
)
249 item
->object
.parsed
= 1;
251 if (tail
<= bufptr
+ 5 || memcmp(bufptr
, "tree ", 5))
252 return error("bogus commit object %s", sha1_to_hex(item
->object
.sha1
));
253 if (tail
<= bufptr
+ 45 || get_sha1_hex(bufptr
+ 5, parent
) < 0)
254 return error("bad tree pointer in commit %s",
255 sha1_to_hex(item
->object
.sha1
));
256 item
->tree
= lookup_tree(parent
);
259 bufptr
+= 46; /* "tree " + "hex sha1" + "\n" */
260 pptr
= &item
->parents
;
262 graft
= lookup_commit_graft(item
->object
.sha1
);
263 while (bufptr
+ 48 < tail
&& !memcmp(bufptr
, "parent ", 7)) {
264 struct commit
*new_parent
;
266 if (tail
<= bufptr
+ 48 ||
267 get_sha1_hex(bufptr
+ 7, parent
) ||
269 return error("bad parents in commit %s", sha1_to_hex(item
->object
.sha1
));
273 new_parent
= lookup_commit(parent
);
275 pptr
= &commit_list_insert(new_parent
, pptr
)->next
;
281 struct commit
*new_parent
;
282 for (i
= 0; i
< graft
->nr_parent
; i
++) {
283 new_parent
= lookup_commit(graft
->parent
[i
]);
286 pptr
= &commit_list_insert(new_parent
, pptr
)->next
;
290 item
->date
= parse_commit_date(bufptr
);
292 if (track_object_refs
) {
294 struct commit_list
*p
;
295 struct object_refs
*refs
= alloc_object_refs(n_refs
);
297 refs
->ref
[i
++] = &item
->tree
->object
;
298 for (p
= item
->parents
; p
; p
= p
->next
)
299 refs
->ref
[i
++] = &p
->item
->object
;
300 set_object_refs(&item
->object
, refs
);
306 int parse_commit(struct commit
*item
)
313 if (item
->object
.parsed
)
315 buffer
= read_sha1_file(item
->object
.sha1
, type
, &size
);
317 return error("Could not read %s",
318 sha1_to_hex(item
->object
.sha1
));
319 if (strcmp(type
, commit_type
)) {
321 return error("Object %s not a commit",
322 sha1_to_hex(item
->object
.sha1
));
324 ret
= parse_commit_buffer(item
, buffer
, size
);
325 if (save_commit_buffer
&& !ret
) {
326 item
->buffer
= buffer
;
333 struct commit_list
*commit_list_insert(struct commit
*item
, struct commit_list
**list_p
)
335 struct commit_list
*new_list
= xmalloc(sizeof(struct commit_list
));
336 new_list
->item
= item
;
337 new_list
->next
= *list_p
;
342 void free_commit_list(struct commit_list
*list
)
345 struct commit_list
*temp
= list
;
351 struct commit_list
* insert_by_date(struct commit
*item
, struct commit_list
**list
)
353 struct commit_list
**pp
= list
;
354 struct commit_list
*p
;
355 while ((p
= *pp
) != NULL
) {
356 if (p
->item
->date
< item
->date
) {
361 return commit_list_insert(item
, pp
);
365 void sort_by_date(struct commit_list
**list
)
367 struct commit_list
*ret
= NULL
;
369 insert_by_date((*list
)->item
, &ret
);
370 *list
= (*list
)->next
;
375 struct commit
*pop_most_recent_commit(struct commit_list
**list
,
378 struct commit
*ret
= (*list
)->item
;
379 struct commit_list
*parents
= ret
->parents
;
380 struct commit_list
*old
= *list
;
382 *list
= (*list
)->next
;
386 struct commit
*commit
= parents
->item
;
387 parse_commit(commit
);
388 if (!(commit
->object
.flags
& mark
)) {
389 commit
->object
.flags
|= mark
;
390 insert_by_date(commit
, list
);
392 parents
= parents
->next
;
397 void clear_commit_marks(struct commit
*commit
, unsigned int mark
)
399 struct commit_list
*parents
;
401 commit
->object
.flags
&= ~mark
;
402 parents
= commit
->parents
;
404 struct commit
*parent
= parents
->item
;
406 /* Have we already cleared this? */
407 if (mark
& parent
->object
.flags
)
408 clear_commit_marks(parent
, mark
);
409 parents
= parents
->next
;
414 * Generic support for pretty-printing the header
416 static int get_one_line(const char *msg
, unsigned long len
)
431 static int is_rfc2047_special(char ch
)
433 return ((ch
& 0x80) || (ch
== '=') || (ch
== '?') || (ch
== '_'));
436 static int add_rfc2047(char *buf
, const char *line
, int len
)
440 static const char q_utf8
[] = "=?utf-8?q?";
442 for (i
= needquote
= 0; !needquote
&& i
< len
; i
++) {
443 unsigned ch
= line
[i
];
447 (ch
== '=' && line
[i
+1] == '?'))
451 return sprintf(buf
, "%.*s", len
, line
);
453 memcpy(bp
, q_utf8
, sizeof(q_utf8
)-1);
454 bp
+= sizeof(q_utf8
)-1;
455 for (i
= 0; i
< len
; i
++) {
456 unsigned ch
= line
[i
] & 0xFF;
457 if (is_rfc2047_special(ch
)) {
458 sprintf(bp
, "=%02X", ch
);
471 static int add_user_info(const char *what
, enum cmit_fmt fmt
, char *buf
,
472 const char *line
, int relative_date
)
478 const char *filler
= " ";
480 if (fmt
== CMIT_FMT_ONELINE
)
482 date
= strchr(line
, '>');
485 namelen
= ++date
- line
;
486 time
= strtoul(date
, &date
, 10);
487 tz
= strtol(date
, NULL
, 10);
489 if (fmt
== CMIT_FMT_EMAIL
) {
490 char *name_tail
= strchr(line
, '<');
491 int display_name_length
;
494 while (line
< name_tail
&& isspace(name_tail
[-1]))
496 display_name_length
= name_tail
- line
;
498 strcpy(buf
, "From: ");
500 ret
+= add_rfc2047(buf
+ ret
, line
, display_name_length
);
501 memcpy(buf
+ ret
, name_tail
, namelen
- display_name_length
);
502 ret
+= namelen
- display_name_length
;
506 ret
= sprintf(buf
, "%s: %.*s%.*s\n", what
,
507 (fmt
== CMIT_FMT_FULLER
) ? 4 : 0,
508 filler
, namelen
, line
);
511 case CMIT_FMT_MEDIUM
:
512 ret
+= sprintf(buf
+ ret
, "Date: %s\n",
513 show_date(time
, tz
, relative_date
));
516 ret
+= sprintf(buf
+ ret
, "Date: %s\n",
517 show_rfc2822_date(time
, tz
));
519 case CMIT_FMT_FULLER
:
520 ret
+= sprintf(buf
+ ret
, "%sDate: %s\n", what
,
521 show_date(time
, tz
, relative_date
));
530 static int is_empty_line(const char *line
, int *len_p
)
533 while (len
&& isspace(line
[len
-1]))
539 static int add_merge_info(enum cmit_fmt fmt
, char *buf
, const struct commit
*commit
, int abbrev
)
541 struct commit_list
*parent
= commit
->parents
;
544 if ((fmt
== CMIT_FMT_ONELINE
) || (fmt
== CMIT_FMT_EMAIL
) ||
545 !parent
|| !parent
->next
)
548 offset
= sprintf(buf
, "Merge:");
551 struct commit
*p
= parent
->item
;
552 const char *hex
= NULL
;
555 hex
= find_unique_abbrev(p
->object
.sha1
, abbrev
);
557 hex
= sha1_to_hex(p
->object
.sha1
);
558 dots
= (abbrev
&& strlen(hex
) != 40) ? "..." : "";
559 parent
= parent
->next
;
561 offset
+= sprintf(buf
+ offset
, " %s%s", hex
, dots
);
563 buf
[offset
++] = '\n';
567 static char *get_header(const struct commit
*commit
, const char *key
)
569 int key_len
= strlen(key
);
570 const char *line
= commit
->buffer
;
573 const char *eol
= strchr(line
, '\n'), *next
;
578 eol
= line
+ strlen(line
);
582 if (!strncmp(line
, key
, key_len
) && line
[key_len
] == ' ') {
583 int len
= eol
- line
- key_len
;
584 char *ret
= xmalloc(len
);
585 memcpy(ret
, line
+ key_len
+ 1, len
- 1);
593 static char *logmsg_reencode(const struct commit
*commit
)
595 char *encoding
= get_header(commit
, "encoding");
598 if (!encoding
|| !strcmp(encoding
, git_commit_encoding
))
600 out
= reencode_string(commit
->buffer
, git_commit_encoding
, encoding
);
607 unsigned long pretty_print_commit(enum cmit_fmt fmt
,
608 const struct commit
*commit
,
610 char *buf
, unsigned long space
,
611 int abbrev
, const char *subject
,
612 const char *after_subject
,
615 int hdr
= 1, body
= 0;
616 unsigned long offset
= 0;
618 int parents_shown
= 0;
619 const char *msg
= commit
->buffer
;
620 int plain_non_ascii
= 0;
621 char *reencoded
= NULL
;
623 if (*git_commit_encoding
) {
624 reencoded
= logmsg_reencode(commit
);
631 if (fmt
== CMIT_FMT_ONELINE
|| fmt
== CMIT_FMT_EMAIL
)
634 /* After-subject is used to pass in Content-Type: multipart
635 * MIME header; in that case we do not have to do the
636 * plaintext content type even if the commit message has
637 * non 7-bit ASCII character. Otherwise, check if we need
638 * to say this is not a 7-bit ASCII.
640 if (fmt
== CMIT_FMT_EMAIL
&& !after_subject
) {
643 for (in_body
= i
= 0; (ch
= msg
[i
]) && i
< len
; i
++) {
645 /* author could be non 7-bit ASCII but
646 * the log may so; skip over the
650 i
+ 1 < len
&& msg
[i
+1] == '\n')
653 else if (ch
& 0x80) {
661 const char *line
= msg
;
662 int linelen
= get_one_line(msg
, len
);
668 * We want some slop for indentation and a possible
669 * final "...". Thus the "+ 20".
671 if (offset
+ linelen
+ 20 > space
) {
672 memcpy(buf
+ offset
, " ...\n", 8);
682 if ((fmt
!= CMIT_FMT_ONELINE
) && !subject
)
683 buf
[offset
++] = '\n';
686 if (fmt
== CMIT_FMT_RAW
) {
687 memcpy(buf
+ offset
, line
, linelen
);
691 if (!memcmp(line
, "parent ", 7)) {
693 die("bad parent line in commit");
697 if (!parents_shown
) {
698 offset
+= add_merge_info(fmt
, buf
+ offset
,
704 * MEDIUM == DEFAULT shows only author with dates.
705 * FULL shows both authors but not dates.
706 * FULLER shows both authors and dates.
708 if (!memcmp(line
, "author ", 7))
709 offset
+= add_user_info("Author", fmt
,
713 if (!memcmp(line
, "committer ", 10) &&
714 (fmt
== CMIT_FMT_FULL
|| fmt
== CMIT_FMT_FULLER
))
715 offset
+= add_user_info("Commit", fmt
,
725 if (is_empty_line(line
, &linelen
)) {
730 if (fmt
== CMIT_FMT_SHORT
)
735 int slen
= strlen(subject
);
736 memcpy(buf
+ offset
, subject
, slen
);
738 offset
+= add_rfc2047(buf
+ offset
, line
, linelen
);
741 memset(buf
+ offset
, ' ', indent
);
742 memcpy(buf
+ offset
+ indent
, line
, linelen
);
743 offset
+= linelen
+ indent
;
745 buf
[offset
++] = '\n';
746 if (fmt
== CMIT_FMT_ONELINE
)
748 if (subject
&& plain_non_ascii
) {
749 static const char header
[] =
750 "Content-Type: text/plain; charset=UTF-8\n"
751 "Content-Transfer-Encoding: 8bit\n";
752 memcpy(buf
+ offset
, header
, sizeof(header
)-1);
753 offset
+= sizeof(header
)-1;
756 int slen
= strlen(after_subject
);
757 if (slen
> space
- offset
- 1)
758 slen
= space
- offset
- 1;
759 memcpy(buf
+ offset
, after_subject
, slen
);
761 after_subject
= NULL
;
765 while (offset
&& isspace(buf
[offset
-1]))
767 /* Make sure there is an EOLN for the non-oneline case */
768 if (fmt
!= CMIT_FMT_ONELINE
)
769 buf
[offset
++] = '\n';
771 * make sure there is another EOLN to separate the headers from whatever
772 * body the caller appends if we haven't already written a body
774 if (fmt
== CMIT_FMT_EMAIL
&& !body
)
775 buf
[offset
++] = '\n';
782 struct commit
*pop_commit(struct commit_list
**stack
)
784 struct commit_list
*top
= *stack
;
785 struct commit
*item
= top
? top
->item
: NULL
;
794 int count_parents(struct commit
* commit
)
797 struct commit_list
* parents
= commit
->parents
;
798 for (count
= 0; parents
; parents
= parents
->next
,count
++)
803 void topo_sort_default_setter(struct commit
*c
, void *data
)
808 void *topo_sort_default_getter(struct commit
*c
)
814 * Performs an in-place topological sort on the list supplied.
816 void sort_in_topological_order(struct commit_list
** list
, int lifo
)
818 sort_in_topological_order_fn(list
, lifo
, topo_sort_default_setter
,
819 topo_sort_default_getter
);
822 void sort_in_topological_order_fn(struct commit_list
** list
, int lifo
,
823 topo_sort_set_fn_t setter
,
824 topo_sort_get_fn_t getter
)
826 struct commit_list
* next
= *list
;
827 struct commit_list
* work
= NULL
, **insert
;
828 struct commit_list
** pptr
= list
;
829 struct sort_node
* nodes
;
830 struct sort_node
* next_nodes
;
833 /* determine the size of the list */
841 /* allocate an array to help sort the list */
842 nodes
= xcalloc(count
, sizeof(*nodes
));
843 /* link the list to the array */
847 next_nodes
->list_item
= next
;
848 setter(next
->item
, next_nodes
);
852 /* update the indegree */
855 struct commit_list
* parents
= next
->item
->parents
;
857 struct commit
* parent
=parents
->item
;
858 struct sort_node
* pn
= (struct sort_node
*) getter(parent
);
862 parents
=parents
->next
;
869 * tips are nodes not reachable from any other node in the list
871 * the tips serve as a starting set for the work queue.
876 struct sort_node
* node
= (struct sort_node
*) getter(next
->item
);
878 if (node
->indegree
== 0) {
879 insert
= &commit_list_insert(next
->item
, insert
)->next
;
884 /* process the list in topological order */
888 struct commit
* work_item
= pop_commit(&work
);
889 struct sort_node
* work_node
= (struct sort_node
*) getter(work_item
);
890 struct commit_list
* parents
= work_item
->parents
;
893 struct commit
* parent
=parents
->item
;
894 struct sort_node
* pn
= (struct sort_node
*) getter(parent
);
898 * parents are only enqueued for emission
899 * when all their children have been emitted thereby
900 * guaranteeing topological order.
905 insert_by_date(parent
, &work
);
907 commit_list_insert(parent
, &work
);
910 parents
=parents
->next
;
913 * work_item is a commit all of whose children
914 * have already been emitted. we can emit it now.
916 *pptr
= work_node
->list_item
;
917 pptr
= &(*pptr
)->next
;
919 setter(work_item
, NULL
);
924 /* merge-rebase stuff */
926 /* bits #0..15 in revision.h */
927 #define PARENT1 (1u<<16)
928 #define PARENT2 (1u<<17)
929 #define STALE (1u<<18)
930 #define RESULT (1u<<19)
932 static struct commit
*interesting(struct commit_list
*list
)
935 struct commit
*commit
= list
->item
;
937 if (commit
->object
.flags
& STALE
)
944 static struct commit_list
*merge_bases(struct commit
*one
, struct commit
*two
)
946 struct commit_list
*list
= NULL
;
947 struct commit_list
*result
= NULL
;
950 /* We do not mark this even with RESULT so we do not
951 * have to clean it up.
953 return commit_list_insert(one
, &result
);
958 one
->object
.flags
|= PARENT1
;
959 two
->object
.flags
|= PARENT2
;
960 insert_by_date(one
, &list
);
961 insert_by_date(two
, &list
);
963 while (interesting(list
)) {
964 struct commit
*commit
;
965 struct commit_list
*parents
;
966 struct commit_list
*n
;
974 flags
= commit
->object
.flags
& (PARENT1
| PARENT2
| STALE
);
975 if (flags
== (PARENT1
| PARENT2
)) {
976 if (!(commit
->object
.flags
& RESULT
)) {
977 commit
->object
.flags
|= RESULT
;
978 insert_by_date(commit
, &result
);
980 /* Mark parents of a found merge stale */
983 parents
= commit
->parents
;
985 struct commit
*p
= parents
->item
;
986 parents
= parents
->next
;
987 if ((p
->object
.flags
& flags
) == flags
)
990 p
->object
.flags
|= flags
;
991 insert_by_date(p
, &list
);
995 /* Clean up the result to remove stale ones */
996 list
= result
; result
= NULL
;
998 struct commit_list
*n
= list
->next
;
999 if (!(list
->item
->object
.flags
& STALE
))
1000 insert_by_date(list
->item
, &result
);
1007 struct commit_list
*get_merge_bases(struct commit
*one
,
1011 const unsigned all_flags
= (PARENT1
| PARENT2
| STALE
| RESULT
);
1012 struct commit_list
*list
;
1013 struct commit
**rslt
;
1014 struct commit_list
*result
;
1017 result
= merge_bases(one
, two
);
1020 if (!result
|| !result
->next
) {
1022 clear_commit_marks(one
, all_flags
);
1023 clear_commit_marks(two
, all_flags
);
1028 /* There are more than one */
1035 rslt
= xcalloc(cnt
, sizeof(*rslt
));
1036 for (list
= result
, i
= 0; list
; list
= list
->next
)
1037 rslt
[i
++] = list
->item
;
1038 free_commit_list(result
);
1040 clear_commit_marks(one
, all_flags
);
1041 clear_commit_marks(two
, all_flags
);
1042 for (i
= 0; i
< cnt
- 1; i
++) {
1043 for (j
= i
+1; j
< cnt
; j
++) {
1044 if (!rslt
[i
] || !rslt
[j
])
1046 result
= merge_bases(rslt
[i
], rslt
[j
]);
1047 clear_commit_marks(rslt
[i
], all_flags
);
1048 clear_commit_marks(rslt
[j
], all_flags
);
1049 for (list
= result
; list
; list
= list
->next
) {
1050 if (rslt
[i
] == list
->item
)
1052 if (rslt
[j
] == list
->item
)
1058 /* Surviving ones in rslt[] are the independent results */
1060 for (i
= 0; i
< cnt
; i
++) {
1062 insert_by_date(rslt
[i
], &result
);