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 /* make sure shallows are read */
226 is_repository_shallow();
227 commit_graft_prepared
= 1;
230 static struct commit_graft
*lookup_commit_graft(const unsigned char *sha1
)
233 prepare_commit_graft();
234 pos
= commit_graft_pos(sha1
);
237 return commit_graft
[pos
];
240 int write_shallow_commits(int fd
, int use_pack_protocol
)
243 for (i
= 0; i
< commit_graft_nr
; i
++)
244 if (commit_graft
[i
]->nr_parent
< 0) {
246 sha1_to_hex(commit_graft
[i
]->sha1
);
248 if (use_pack_protocol
)
249 packet_write(fd
, "shallow %s", hex
);
258 int parse_commit_buffer(struct commit
*item
, void *buffer
, unsigned long size
)
261 char *bufptr
= buffer
;
262 unsigned char parent
[20];
263 struct commit_list
**pptr
;
264 struct commit_graft
*graft
;
267 if (item
->object
.parsed
)
269 item
->object
.parsed
= 1;
271 if (tail
<= bufptr
+ 5 || memcmp(bufptr
, "tree ", 5))
272 return error("bogus commit object %s", sha1_to_hex(item
->object
.sha1
));
273 if (tail
<= bufptr
+ 45 || get_sha1_hex(bufptr
+ 5, parent
) < 0)
274 return error("bad tree pointer in commit %s",
275 sha1_to_hex(item
->object
.sha1
));
276 item
->tree
= lookup_tree(parent
);
279 bufptr
+= 46; /* "tree " + "hex sha1" + "\n" */
280 pptr
= &item
->parents
;
282 graft
= lookup_commit_graft(item
->object
.sha1
);
283 while (bufptr
+ 48 < tail
&& !memcmp(bufptr
, "parent ", 7)) {
284 struct commit
*new_parent
;
286 if (tail
<= bufptr
+ 48 ||
287 get_sha1_hex(bufptr
+ 7, parent
) ||
289 return error("bad parents in commit %s", sha1_to_hex(item
->object
.sha1
));
293 new_parent
= lookup_commit(parent
);
295 pptr
= &commit_list_insert(new_parent
, pptr
)->next
;
301 struct commit
*new_parent
;
302 for (i
= 0; i
< graft
->nr_parent
; i
++) {
303 new_parent
= lookup_commit(graft
->parent
[i
]);
306 pptr
= &commit_list_insert(new_parent
, pptr
)->next
;
310 item
->date
= parse_commit_date(bufptr
);
312 if (track_object_refs
) {
314 struct commit_list
*p
;
315 struct object_refs
*refs
= alloc_object_refs(n_refs
);
317 refs
->ref
[i
++] = &item
->tree
->object
;
318 for (p
= item
->parents
; p
; p
= p
->next
)
319 refs
->ref
[i
++] = &p
->item
->object
;
320 set_object_refs(&item
->object
, refs
);
326 int parse_commit(struct commit
*item
)
333 if (item
->object
.parsed
)
335 buffer
= read_sha1_file(item
->object
.sha1
, type
, &size
);
337 return error("Could not read %s",
338 sha1_to_hex(item
->object
.sha1
));
339 if (strcmp(type
, commit_type
)) {
341 return error("Object %s not a commit",
342 sha1_to_hex(item
->object
.sha1
));
344 ret
= parse_commit_buffer(item
, buffer
, size
);
345 if (save_commit_buffer
&& !ret
) {
346 item
->buffer
= buffer
;
353 struct commit_list
*commit_list_insert(struct commit
*item
, struct commit_list
**list_p
)
355 struct commit_list
*new_list
= xmalloc(sizeof(struct commit_list
));
356 new_list
->item
= item
;
357 new_list
->next
= *list_p
;
362 void free_commit_list(struct commit_list
*list
)
365 struct commit_list
*temp
= list
;
371 struct commit_list
* insert_by_date(struct commit
*item
, struct commit_list
**list
)
373 struct commit_list
**pp
= list
;
374 struct commit_list
*p
;
375 while ((p
= *pp
) != NULL
) {
376 if (p
->item
->date
< item
->date
) {
381 return commit_list_insert(item
, pp
);
385 void sort_by_date(struct commit_list
**list
)
387 struct commit_list
*ret
= NULL
;
389 insert_by_date((*list
)->item
, &ret
);
390 *list
= (*list
)->next
;
395 struct commit
*pop_most_recent_commit(struct commit_list
**list
,
398 struct commit
*ret
= (*list
)->item
;
399 struct commit_list
*parents
= ret
->parents
;
400 struct commit_list
*old
= *list
;
402 *list
= (*list
)->next
;
406 struct commit
*commit
= parents
->item
;
407 parse_commit(commit
);
408 if (!(commit
->object
.flags
& mark
)) {
409 commit
->object
.flags
|= mark
;
410 insert_by_date(commit
, list
);
412 parents
= parents
->next
;
417 void clear_commit_marks(struct commit
*commit
, unsigned int mark
)
419 struct commit_list
*parents
;
421 commit
->object
.flags
&= ~mark
;
422 parents
= commit
->parents
;
424 struct commit
*parent
= parents
->item
;
426 /* Have we already cleared this? */
427 if (mark
& parent
->object
.flags
)
428 clear_commit_marks(parent
, mark
);
429 parents
= parents
->next
;
434 * Generic support for pretty-printing the header
436 static int get_one_line(const char *msg
, unsigned long len
)
451 static int is_rfc2047_special(char ch
)
453 return ((ch
& 0x80) || (ch
== '=') || (ch
== '?') || (ch
== '_'));
456 static int add_rfc2047(char *buf
, const char *line
, int len
)
460 static const char q_utf8
[] = "=?utf-8?q?";
462 for (i
= needquote
= 0; !needquote
&& i
< len
; i
++) {
463 unsigned ch
= line
[i
];
467 (ch
== '=' && line
[i
+1] == '?'))
471 return sprintf(buf
, "%.*s", len
, line
);
473 memcpy(bp
, q_utf8
, sizeof(q_utf8
)-1);
474 bp
+= sizeof(q_utf8
)-1;
475 for (i
= 0; i
< len
; i
++) {
476 unsigned ch
= line
[i
] & 0xFF;
477 if (is_rfc2047_special(ch
)) {
478 sprintf(bp
, "=%02X", ch
);
491 static int add_user_info(const char *what
, enum cmit_fmt fmt
, char *buf
,
492 const char *line
, int relative_date
)
498 const char *filler
= " ";
500 if (fmt
== CMIT_FMT_ONELINE
)
502 date
= strchr(line
, '>');
505 namelen
= ++date
- line
;
506 time
= strtoul(date
, &date
, 10);
507 tz
= strtol(date
, NULL
, 10);
509 if (fmt
== CMIT_FMT_EMAIL
) {
510 char *name_tail
= strchr(line
, '<');
511 int display_name_length
;
514 while (line
< name_tail
&& isspace(name_tail
[-1]))
516 display_name_length
= name_tail
- line
;
518 strcpy(buf
, "From: ");
520 ret
+= add_rfc2047(buf
+ ret
, line
, display_name_length
);
521 memcpy(buf
+ ret
, name_tail
, namelen
- display_name_length
);
522 ret
+= namelen
- display_name_length
;
526 ret
= sprintf(buf
, "%s: %.*s%.*s\n", what
,
527 (fmt
== CMIT_FMT_FULLER
) ? 4 : 0,
528 filler
, namelen
, line
);
531 case CMIT_FMT_MEDIUM
:
532 ret
+= sprintf(buf
+ ret
, "Date: %s\n",
533 show_date(time
, tz
, relative_date
));
536 ret
+= sprintf(buf
+ ret
, "Date: %s\n",
537 show_rfc2822_date(time
, tz
));
539 case CMIT_FMT_FULLER
:
540 ret
+= sprintf(buf
+ ret
, "%sDate: %s\n", what
,
541 show_date(time
, tz
, relative_date
));
550 static int is_empty_line(const char *line
, int *len_p
)
553 while (len
&& isspace(line
[len
-1]))
559 static int add_merge_info(enum cmit_fmt fmt
, char *buf
, const struct commit
*commit
, int abbrev
)
561 struct commit_list
*parent
= commit
->parents
;
564 if ((fmt
== CMIT_FMT_ONELINE
) || (fmt
== CMIT_FMT_EMAIL
) ||
565 !parent
|| !parent
->next
)
568 offset
= sprintf(buf
, "Merge:");
571 struct commit
*p
= parent
->item
;
572 const char *hex
= NULL
;
575 hex
= find_unique_abbrev(p
->object
.sha1
, abbrev
);
577 hex
= sha1_to_hex(p
->object
.sha1
);
578 dots
= (abbrev
&& strlen(hex
) != 40) ? "..." : "";
579 parent
= parent
->next
;
581 offset
+= sprintf(buf
+ offset
, " %s%s", hex
, dots
);
583 buf
[offset
++] = '\n';
587 unsigned long pretty_print_commit(enum cmit_fmt fmt
, const struct commit
*commit
,
588 unsigned long len
, char *buf
, unsigned long space
,
589 int abbrev
, const char *subject
,
590 const char *after_subject
, int relative_date
)
592 int hdr
= 1, body
= 0;
593 unsigned long offset
= 0;
595 int parents_shown
= 0;
596 const char *msg
= commit
->buffer
;
597 int plain_non_ascii
= 0;
599 if (fmt
== CMIT_FMT_ONELINE
|| fmt
== CMIT_FMT_EMAIL
)
602 /* After-subject is used to pass in Content-Type: multipart
603 * MIME header; in that case we do not have to do the
604 * plaintext content type even if the commit message has
605 * non 7-bit ASCII character. Otherwise, check if we need
606 * to say this is not a 7-bit ASCII.
608 if (fmt
== CMIT_FMT_EMAIL
&& !after_subject
) {
611 for (in_body
= i
= 0; (ch
= msg
[i
]) && i
< len
; i
++) {
613 /* author could be non 7-bit ASCII but
614 * the log may so; skip over the
618 i
+ 1 < len
&& msg
[i
+1] == '\n')
621 else if (ch
& 0x80) {
629 const char *line
= msg
;
630 int linelen
= get_one_line(msg
, len
);
636 * We want some slop for indentation and a possible
637 * final "...". Thus the "+ 20".
639 if (offset
+ linelen
+ 20 > space
) {
640 memcpy(buf
+ offset
, " ...\n", 8);
650 if ((fmt
!= CMIT_FMT_ONELINE
) && !subject
)
651 buf
[offset
++] = '\n';
654 if (fmt
== CMIT_FMT_RAW
) {
655 memcpy(buf
+ offset
, line
, linelen
);
659 if (!memcmp(line
, "parent ", 7)) {
661 die("bad parent line in commit");
665 if (!parents_shown
) {
666 offset
+= add_merge_info(fmt
, buf
+ offset
,
672 * MEDIUM == DEFAULT shows only author with dates.
673 * FULL shows both authors but not dates.
674 * FULLER shows both authors and dates.
676 if (!memcmp(line
, "author ", 7))
677 offset
+= add_user_info("Author", fmt
,
681 if (!memcmp(line
, "committer ", 10) &&
682 (fmt
== CMIT_FMT_FULL
|| fmt
== CMIT_FMT_FULLER
))
683 offset
+= add_user_info("Commit", fmt
,
693 if (is_empty_line(line
, &linelen
)) {
698 if (fmt
== CMIT_FMT_SHORT
)
703 int slen
= strlen(subject
);
704 memcpy(buf
+ offset
, subject
, slen
);
706 offset
+= add_rfc2047(buf
+ offset
, line
, linelen
);
709 memset(buf
+ offset
, ' ', indent
);
710 memcpy(buf
+ offset
+ indent
, line
, linelen
);
711 offset
+= linelen
+ indent
;
713 buf
[offset
++] = '\n';
714 if (fmt
== CMIT_FMT_ONELINE
)
716 if (subject
&& plain_non_ascii
) {
717 static const char header
[] =
718 "Content-Type: text/plain; charset=UTF-8\n"
719 "Content-Transfer-Encoding: 8bit\n";
720 memcpy(buf
+ offset
, header
, sizeof(header
)-1);
721 offset
+= sizeof(header
)-1;
724 int slen
= strlen(after_subject
);
725 if (slen
> space
- offset
- 1)
726 slen
= space
- offset
- 1;
727 memcpy(buf
+ offset
, after_subject
, slen
);
729 after_subject
= NULL
;
733 while (offset
&& isspace(buf
[offset
-1]))
735 /* Make sure there is an EOLN for the non-oneline case */
736 if (fmt
!= CMIT_FMT_ONELINE
)
737 buf
[offset
++] = '\n';
739 * make sure there is another EOLN to separate the headers from whatever
740 * body the caller appends if we haven't already written a body
742 if (fmt
== CMIT_FMT_EMAIL
&& !body
)
743 buf
[offset
++] = '\n';
748 struct commit
*pop_commit(struct commit_list
**stack
)
750 struct commit_list
*top
= *stack
;
751 struct commit
*item
= top
? top
->item
: NULL
;
760 int count_parents(struct commit
* commit
)
763 struct commit_list
* parents
= commit
->parents
;
764 for (count
= 0; parents
; parents
= parents
->next
,count
++)
769 void topo_sort_default_setter(struct commit
*c
, void *data
)
774 void *topo_sort_default_getter(struct commit
*c
)
780 * Performs an in-place topological sort on the list supplied.
782 void sort_in_topological_order(struct commit_list
** list
, int lifo
)
784 sort_in_topological_order_fn(list
, lifo
, topo_sort_default_setter
,
785 topo_sort_default_getter
);
788 void sort_in_topological_order_fn(struct commit_list
** list
, int lifo
,
789 topo_sort_set_fn_t setter
,
790 topo_sort_get_fn_t getter
)
792 struct commit_list
* next
= *list
;
793 struct commit_list
* work
= NULL
, **insert
;
794 struct commit_list
** pptr
= list
;
795 struct sort_node
* nodes
;
796 struct sort_node
* next_nodes
;
799 /* determine the size of the list */
807 /* allocate an array to help sort the list */
808 nodes
= xcalloc(count
, sizeof(*nodes
));
809 /* link the list to the array */
813 next_nodes
->list_item
= next
;
814 setter(next
->item
, next_nodes
);
818 /* update the indegree */
821 struct commit_list
* parents
= next
->item
->parents
;
823 struct commit
* parent
=parents
->item
;
824 struct sort_node
* pn
= (struct sort_node
*) getter(parent
);
828 parents
=parents
->next
;
835 * tips are nodes not reachable from any other node in the list
837 * the tips serve as a starting set for the work queue.
842 struct sort_node
* node
= (struct sort_node
*) getter(next
->item
);
844 if (node
->indegree
== 0) {
845 insert
= &commit_list_insert(next
->item
, insert
)->next
;
850 /* process the list in topological order */
854 struct commit
* work_item
= pop_commit(&work
);
855 struct sort_node
* work_node
= (struct sort_node
*) getter(work_item
);
856 struct commit_list
* parents
= work_item
->parents
;
859 struct commit
* parent
=parents
->item
;
860 struct sort_node
* pn
= (struct sort_node
*) getter(parent
);
864 * parents are only enqueued for emission
865 * when all their children have been emitted thereby
866 * guaranteeing topological order.
871 insert_by_date(parent
, &work
);
873 commit_list_insert(parent
, &work
);
876 parents
=parents
->next
;
879 * work_item is a commit all of whose children
880 * have already been emitted. we can emit it now.
882 *pptr
= work_node
->list_item
;
883 pptr
= &(*pptr
)->next
;
885 setter(work_item
, NULL
);
890 /* merge-rebase stuff */
892 /* bits #0..7 in revision.h */
893 #define PARENT1 (1u<< 8)
894 #define PARENT2 (1u<< 9)
895 #define STALE (1u<<10)
896 #define RESULT (1u<<11)
898 static struct commit
*interesting(struct commit_list
*list
)
901 struct commit
*commit
= list
->item
;
903 if (commit
->object
.flags
& STALE
)
910 static struct commit_list
*merge_bases(struct commit
*one
, struct commit
*two
)
912 struct commit_list
*list
= NULL
;
913 struct commit_list
*result
= NULL
;
916 /* We do not mark this even with RESULT so we do not
917 * have to clean it up.
919 return commit_list_insert(one
, &result
);
924 one
->object
.flags
|= PARENT1
;
925 two
->object
.flags
|= PARENT2
;
926 insert_by_date(one
, &list
);
927 insert_by_date(two
, &list
);
929 while (interesting(list
)) {
930 struct commit
*commit
;
931 struct commit_list
*parents
;
932 struct commit_list
*n
;
940 flags
= commit
->object
.flags
& (PARENT1
| PARENT2
| STALE
);
941 if (flags
== (PARENT1
| PARENT2
)) {
942 if (!(commit
->object
.flags
& RESULT
)) {
943 commit
->object
.flags
|= RESULT
;
944 insert_by_date(commit
, &result
);
946 /* Mark parents of a found merge stale */
949 parents
= commit
->parents
;
951 struct commit
*p
= parents
->item
;
952 parents
= parents
->next
;
953 if ((p
->object
.flags
& flags
) == flags
)
956 p
->object
.flags
|= flags
;
957 insert_by_date(p
, &list
);
961 /* Clean up the result to remove stale ones */
962 list
= result
; result
= NULL
;
964 struct commit_list
*n
= list
->next
;
965 if (!(list
->item
->object
.flags
& STALE
))
966 insert_by_date(list
->item
, &result
);
973 struct commit_list
*get_merge_bases(struct commit
*one
,
977 const unsigned all_flags
= (PARENT1
| PARENT2
| STALE
| RESULT
);
978 struct commit_list
*list
;
979 struct commit
**rslt
;
980 struct commit_list
*result
;
983 result
= merge_bases(one
, two
);
986 if (!result
|| !result
->next
) {
988 clear_commit_marks(one
, all_flags
);
989 clear_commit_marks(two
, all_flags
);
994 /* There are more than one */
1001 rslt
= xcalloc(cnt
, sizeof(*rslt
));
1002 for (list
= result
, i
= 0; list
; list
= list
->next
)
1003 rslt
[i
++] = list
->item
;
1004 free_commit_list(result
);
1006 clear_commit_marks(one
, all_flags
);
1007 clear_commit_marks(two
, all_flags
);
1008 for (i
= 0; i
< cnt
- 1; i
++) {
1009 for (j
= i
+1; j
< cnt
; j
++) {
1010 if (!rslt
[i
] || !rslt
[j
])
1012 result
= merge_bases(rslt
[i
], rslt
[j
]);
1013 clear_commit_marks(rslt
[i
], all_flags
);
1014 clear_commit_marks(rslt
[j
], all_flags
);
1015 for (list
= result
; list
; list
= list
->next
) {
1016 if (rslt
[i
] == list
->item
)
1018 if (rslt
[j
] == list
->item
)
1024 /* Surviving ones in rslt[] are the independent results */
1026 for (i
= 0; i
< cnt
; i
++) {
1028 insert_by_date(rslt
[i
], &result
);