10 #define SEEN (1u << 0)
11 #define INTERESTING (1u << 1)
12 #define COUNTED (1u << 2)
13 #define SHOWN (1u << 3)
15 static const char rev_list_usage
[] =
16 "git-rev-list [OPTION] commit-id <commit-id>\n"
27 " --merge-order [ --show-breaks ]\n"
30 static int unpacked
= 0;
31 static int bisect_list
= 0;
32 static int tag_objects
= 0;
33 static int tree_objects
= 0;
34 static int blob_objects
= 0;
35 static int verbose_header
= 0;
36 static int show_parents
= 0;
37 static int hdr_termination
= 0;
38 static const char *commit_prefix
= "";
39 static unsigned long max_age
= -1;
40 static unsigned long min_age
= -1;
41 static int max_count
= -1;
42 static enum cmit_fmt commit_format
= CMIT_FMT_RAW
;
43 static int merge_order
= 0;
44 static int show_breaks
= 0;
45 static int stop_traversal
= 0;
46 static int topo_order
= 0;
47 static int no_merges
= 0;
48 static const char **paths
= NULL
;
50 static void show_commit(struct commit
*commit
)
52 commit
->object
.flags
|= SHOWN
;
55 if (commit
->object
.flags
& DISCONTINUITY
) {
57 } else if (commit
->object
.flags
& BOUNDARY
) {
61 printf("%s%s", commit_prefix
, sha1_to_hex(commit
->object
.sha1
));
63 struct commit_list
*parents
= commit
->parents
;
65 printf(" %s", sha1_to_hex(parents
->item
->object
.sha1
));
66 parents
= parents
->next
;
69 if (commit_format
== CMIT_FMT_ONELINE
)
75 static char pretty_header
[16384];
76 pretty_print_commit(commit_format
, commit
->buffer
, ~0, pretty_header
, sizeof(pretty_header
));
77 printf("%s%c", pretty_header
, hdr_termination
);
82 static int filter_commit(struct commit
* commit
)
84 if (stop_traversal
&& (commit
->object
.flags
& BOUNDARY
))
86 if (commit
->object
.flags
& (UNINTERESTING
|SHOWN
))
88 if (min_age
!= -1 && (commit
->date
> min_age
))
90 if (max_age
!= -1 && (commit
->date
< max_age
)) {
94 if (max_count
!= -1 && !max_count
--)
96 if (no_merges
&& (commit
->parents
&& commit
->parents
->next
))
101 static int process_commit(struct commit
* commit
)
103 int action
=filter_commit(commit
);
105 if (action
== STOP
) {
109 if (action
== CONTINUE
) {
118 static struct object_list
**add_object(struct object
*obj
, struct object_list
**p
, const char *name
)
120 struct object_list
*entry
= xmalloc(sizeof(*entry
));
128 static struct object_list
**process_blob(struct blob
*blob
, struct object_list
**p
, const char *name
)
130 struct object
*obj
= &blob
->object
;
134 if (obj
->flags
& (UNINTERESTING
| SEEN
))
137 return add_object(obj
, p
, name
);
140 static struct object_list
**process_tree(struct tree
*tree
, struct object_list
**p
, const char *name
)
142 struct object
*obj
= &tree
->object
;
143 struct tree_entry_list
*entry
;
147 if (obj
->flags
& (UNINTERESTING
| SEEN
))
149 if (parse_tree(tree
) < 0)
150 die("bad tree object %s", sha1_to_hex(obj
->sha1
));
152 p
= add_object(obj
, p
, name
);
153 entry
= tree
->entries
;
154 tree
->entries
= NULL
;
156 struct tree_entry_list
*next
= entry
->next
;
157 if (entry
->directory
)
158 p
= process_tree(entry
->item
.tree
, p
, entry
->name
);
160 p
= process_blob(entry
->item
.blob
, p
, entry
->name
);
167 static struct object_list
*pending_objects
= NULL
;
169 static void show_commit_list(struct commit_list
*list
)
171 struct object_list
*objects
= NULL
, **p
= &objects
, *pending
;
173 struct commit
*commit
= pop_most_recent_commit(&list
, SEEN
);
175 p
= process_tree(commit
->tree
, p
, "");
176 if (process_commit(commit
) == STOP
)
179 for (pending
= pending_objects
; pending
; pending
= pending
->next
) {
180 struct object
*obj
= pending
->item
;
181 const char *name
= pending
->name
;
182 if (obj
->flags
& (UNINTERESTING
| SEEN
))
184 if (obj
->type
== tag_type
) {
186 p
= add_object(obj
, p
, name
);
189 if (obj
->type
== tree_type
) {
190 p
= process_tree((struct tree
*)obj
, p
, name
);
193 if (obj
->type
== blob_type
) {
194 p
= process_blob((struct blob
*)obj
, p
, name
);
197 die("unknown pending object %s (%s)", sha1_to_hex(obj
->sha1
), name
);
200 /* An object with name "foo\n0000000000000000000000000000000000000000"
201 * can be used confuse downstream git-pack-objects very badly.
203 const char *ep
= strchr(objects
->name
, '\n');
205 printf("%s %.*s\n", sha1_to_hex(objects
->item
->sha1
),
206 (int) (ep
- objects
->name
),
210 printf("%s %s\n", sha1_to_hex(objects
->item
->sha1
), objects
->name
);
211 objects
= objects
->next
;
215 static void mark_blob_uninteresting(struct blob
*blob
)
219 if (blob
->object
.flags
& UNINTERESTING
)
221 blob
->object
.flags
|= UNINTERESTING
;
224 static void mark_tree_uninteresting(struct tree
*tree
)
226 struct object
*obj
= &tree
->object
;
227 struct tree_entry_list
*entry
;
231 if (obj
->flags
& UNINTERESTING
)
233 obj
->flags
|= UNINTERESTING
;
234 if (!has_sha1_file(obj
->sha1
))
236 if (parse_tree(tree
) < 0)
237 die("bad tree %s", sha1_to_hex(obj
->sha1
));
238 entry
= tree
->entries
;
239 tree
->entries
= NULL
;
241 struct tree_entry_list
*next
= entry
->next
;
242 if (entry
->directory
)
243 mark_tree_uninteresting(entry
->item
.tree
);
245 mark_blob_uninteresting(entry
->item
.blob
);
251 static void mark_parents_uninteresting(struct commit
*commit
)
253 struct commit_list
*parents
= commit
->parents
;
256 struct commit
*commit
= parents
->item
;
257 commit
->object
.flags
|= UNINTERESTING
;
260 * Normally we haven't parsed the parent
261 * yet, so we won't have a parent of a parent
262 * here. However, it may turn out that we've
263 * reached this commit some other way (where it
264 * wasn't uninteresting), in which case we need
265 * to mark its parents recursively too..
268 mark_parents_uninteresting(commit
);
271 * A missing commit is ok iff its parent is marked
274 * We just mark such a thing parsed, so that when
275 * it is popped next time around, we won't be trying
276 * to parse it and get an error.
278 if (!has_sha1_file(commit
->object
.sha1
))
279 commit
->object
.parsed
= 1;
280 parents
= parents
->next
;
284 static int everybody_uninteresting(struct commit_list
*orig
)
286 struct commit_list
*list
= orig
;
288 struct commit
*commit
= list
->item
;
290 if (commit
->object
.flags
& UNINTERESTING
)
298 * This is a truly stupid algorithm, but it's only
299 * used for bisection, and we just don't care enough.
301 * We care just barely enough to avoid recursing for
304 static int count_distance(struct commit_list
*entry
)
309 struct commit
*commit
= entry
->item
;
310 struct commit_list
*p
;
312 if (commit
->object
.flags
& (UNINTERESTING
| COUNTED
))
315 commit
->object
.flags
|= COUNTED
;
321 nr
+= count_distance(p
);
329 static void clear_distance(struct commit_list
*list
)
332 struct commit
*commit
= list
->item
;
333 commit
->object
.flags
&= ~COUNTED
;
338 static struct commit_list
*find_bisection(struct commit_list
*list
)
341 struct commit_list
*p
, *best
;
354 int distance
= count_distance(p
);
355 clear_distance(list
);
356 if (nr
- distance
< distance
)
357 distance
= nr
- distance
;
358 if (distance
> closest
) {
369 static void mark_edges_uninteresting(struct commit_list
*list
)
371 for ( ; list
; list
= list
->next
) {
372 struct commit_list
*parents
= list
->item
->parents
;
374 for ( ; parents
; parents
= parents
->next
) {
375 struct commit
*commit
= parents
->item
;
376 if (commit
->object
.flags
& UNINTERESTING
)
377 mark_tree_uninteresting(commit
->tree
);
382 static int is_different
= 0;
384 static void file_add_remove(struct diff_options
*options
,
385 int addremove
, unsigned mode
,
386 const unsigned char *sha1
,
387 const char *base
, const char *path
)
392 static void file_change(struct diff_options
*options
,
393 unsigned old_mode
, unsigned new_mode
,
394 const unsigned char *old_sha1
,
395 const unsigned char *new_sha1
,
396 const char *base
, const char *path
)
401 static struct diff_options diff_opt
= {
403 .add_remove
= file_add_remove
,
404 .change
= file_change
,
407 static struct commit
*try_to_simplify_merge(struct commit
*commit
, struct commit_list
*parent
)
413 struct commit
*p
= parent
->item
;
414 parent
= parent
->next
;
419 if (diff_tree_sha1(commit
->tree
->object
.sha1
,
420 p
->tree
->object
.sha1
, "", &diff_opt
) < 0)
428 static void add_parents_to_list(struct commit
*commit
, struct commit_list
**list
)
430 struct commit_list
*parent
= commit
->parents
;
433 * If the commit is uninteresting, don't try to
434 * prune parents - we want the maximal uninteresting
437 * Normally we haven't parsed the parent
438 * yet, so we won't have a parent of a parent
439 * here. However, it may turn out that we've
440 * reached this commit some other way (where it
441 * wasn't uninteresting), in which case we need
442 * to mark its parents recursively too..
444 if (commit
->object
.flags
& UNINTERESTING
) {
446 struct commit
*p
= parent
->item
;
447 parent
= parent
->next
;
449 p
->object
.flags
|= UNINTERESTING
;
451 mark_parents_uninteresting(p
);
452 if (p
->object
.flags
& SEEN
)
454 p
->object
.flags
|= SEEN
;
455 insert_by_date(p
, list
);
461 * Ok, the commit wasn't uninteresting. If it
462 * is a merge, try to find the parent that has
463 * no differences in the path set if one exists.
465 if (paths
&& parent
&& parent
->next
) {
466 struct commit
*preferred
;
468 preferred
= try_to_simplify_merge(commit
, parent
);
470 parent
->item
= preferred
;
476 struct commit
*p
= parent
->item
;
478 parent
= parent
->next
;
481 if (p
->object
.flags
& SEEN
)
483 p
->object
.flags
|= SEEN
;
484 insert_by_date(p
, list
);
488 static struct commit_list
*limit_list(struct commit_list
*list
)
490 struct commit_list
*newlist
= NULL
;
491 struct commit_list
**p
= &newlist
;
493 struct commit_list
*entry
= list
;
494 struct commit
*commit
= list
->item
;
495 struct object
*obj
= &commit
->object
;
500 if (max_age
!= -1 && (commit
->date
< max_age
))
501 obj
->flags
|= UNINTERESTING
;
502 if (unpacked
&& has_sha1_pack(obj
->sha1
))
503 obj
->flags
|= UNINTERESTING
;
504 add_parents_to_list(commit
, &list
);
505 if (obj
->flags
& UNINTERESTING
) {
506 mark_parents_uninteresting(commit
);
507 if (everybody_uninteresting(list
))
511 if (min_age
!= -1 && (commit
->date
> min_age
))
513 p
= &commit_list_insert(commit
, p
)->next
;
516 mark_edges_uninteresting(newlist
);
518 newlist
= find_bisection(newlist
);
522 static void add_pending_object(struct object
*obj
, const char *name
)
524 add_object(obj
, &pending_objects
, name
);
527 static struct commit
*get_commit_reference(const char *name
, unsigned int flags
)
529 unsigned char sha1
[20];
530 struct object
*object
;
532 if (get_sha1(name
, sha1
))
533 usage(rev_list_usage
);
534 object
= parse_object(sha1
);
536 die("bad object %s", name
);
539 * Tag object? Look what it points to..
541 while (object
->type
== tag_type
) {
542 struct tag
*tag
= (struct tag
*) object
;
543 object
->flags
|= flags
;
544 if (tag_objects
&& !(object
->flags
& UNINTERESTING
))
545 add_pending_object(object
, tag
->tag
);
546 object
= parse_object(tag
->tagged
->sha1
);
548 die("bad object %s", sha1_to_hex(tag
->tagged
->sha1
));
552 * Commit object? Just return it, we'll do all the complex
555 if (object
->type
== commit_type
) {
556 struct commit
*commit
= (struct commit
*)object
;
557 object
->flags
|= flags
;
558 if (parse_commit(commit
) < 0)
559 die("unable to parse commit %s", name
);
560 if (flags
& UNINTERESTING
)
561 mark_parents_uninteresting(commit
);
566 * Tree object? Either mark it uniniteresting, or add it
567 * to the list of objects to look at later..
569 if (object
->type
== tree_type
) {
570 struct tree
*tree
= (struct tree
*)object
;
573 if (flags
& UNINTERESTING
) {
574 mark_tree_uninteresting(tree
);
577 add_pending_object(object
, "");
582 * Blob object? You know the drill by now..
584 if (object
->type
== blob_type
) {
585 struct blob
*blob
= (struct blob
*)object
;
588 if (flags
& UNINTERESTING
) {
589 mark_blob_uninteresting(blob
);
592 add_pending_object(object
, "");
595 die("%s is unknown object", name
);
598 static void handle_one_commit(struct commit
*com
, struct commit_list
**lst
)
600 if (!com
|| com
->object
.flags
& SEEN
)
602 com
->object
.flags
|= SEEN
;
603 commit_list_insert(com
, lst
);
606 /* for_each_ref() callback does not allow user data -- Yuck. */
607 static struct commit_list
**global_lst
;
609 static int include_one_commit(const char *path
, const unsigned char *sha1
)
611 struct commit
*com
= get_commit_reference(path
, 0);
612 handle_one_commit(com
, global_lst
);
616 static void handle_all(struct commit_list
**lst
)
619 for_each_ref(include_one_commit
);
623 int main(int argc
, const char **argv
)
625 const char *prefix
= setup_git_directory();
626 struct commit_list
*list
= NULL
;
629 for (i
= 1 ; i
< argc
; i
++) {
631 const char *arg
= argv
[i
];
633 struct commit
*commit
;
635 if (!strncmp(arg
, "--max-count=", 12)) {
636 max_count
= atoi(arg
+ 12);
639 if (!strncmp(arg
, "--max-age=", 10)) {
640 max_age
= atoi(arg
+ 10);
644 if (!strncmp(arg
, "--min-age=", 10)) {
645 min_age
= atoi(arg
+ 10);
649 if (!strcmp(arg
, "--header")) {
653 if (!strncmp(arg
, "--pretty", 8)) {
654 commit_format
= get_commit_format(arg
+8);
656 hdr_termination
= '\n';
657 if (commit_format
== CMIT_FMT_ONELINE
)
660 commit_prefix
= "commit ";
663 if (!strncmp(arg
, "--no-merges", 11)) {
667 if (!strcmp(arg
, "--parents")) {
671 if (!strcmp(arg
, "--bisect")) {
675 if (!strcmp(arg
, "--all")) {
679 if (!strcmp(arg
, "--objects")) {
685 if (!strcmp(arg
, "--unpacked")) {
690 if (!strcmp(arg
, "--merge-order")) {
694 if (!strcmp(arg
, "--show-breaks")) {
698 if (!strcmp(arg
, "--topo-order")) {
703 if (!strcmp(arg
, "--")) {
704 paths
= get_pathspec(prefix
, argv
+ i
+ 1);
707 diff_tree_setup_paths(paths
);
712 if (show_breaks
&& !merge_order
)
713 usage(rev_list_usage
);
716 dotdot
= strstr(arg
, "..");
718 char *next
= dotdot
+ 2;
719 struct commit
*exclude
= NULL
;
720 struct commit
*include
= NULL
;
724 exclude
= get_commit_reference(arg
, UNINTERESTING
);
725 include
= get_commit_reference(next
, 0);
726 if (exclude
&& include
) {
728 handle_one_commit(exclude
, &list
);
729 handle_one_commit(include
, &list
);
735 flags
= UNINTERESTING
;
739 commit
= get_commit_reference(arg
, flags
);
740 handle_one_commit(commit
, &list
);
743 save_commit_buffer
= verbose_header
;
744 track_object_refs
= 0;
748 if (list
&& !limited
&& max_count
== 1 &&
749 !tag_objects
&& !tree_objects
&& !blob_objects
) {
750 show_commit(list
->item
);
754 list
= limit_list(list
);
756 sort_in_topological_order(&list
);
757 show_commit_list(list
);
760 if (sort_list_in_merge_order(list
, &process_commit
)) {
761 die("merge order sort failed\n");
764 die("merge order sort unsupported, OpenSSL not linked");