1#include "cache.h"
2#include "refs.h"
3#include "tag.h"
4#include "commit.h"
5#include "tree.h"
6#include "blob.h"
7#include "epoch.h"
8#include "diff.h"
9
10#define SEEN (1u << 0)
11#define INTERESTING (1u << 1)
12#define COUNTED (1u << 2)
13#define SHOWN (1u << 3)
14#define TREECHANGE (1u << 4)
15
16static const char rev_list_usage[] =
17 "git-rev-list [OPTION] commit-id <commit-id>\n"
18 " --max-count=nr\n"
19 " --max-age=epoch\n"
20 " --min-age=epoch\n"
21 " --parents\n"
22 " --bisect\n"
23 " --objects\n"
24 " --unpacked\n"
25 " --header\n"
26 " --pretty\n"
27 " --no-merges\n"
28 " --merge-order [ --show-breaks ]\n"
29 " --topo-order";
30
31static int dense = 0;
32static int unpacked = 0;
33static int bisect_list = 0;
34static int tag_objects = 0;
35static int tree_objects = 0;
36static int blob_objects = 0;
37static int verbose_header = 0;
38static int show_parents = 0;
39static int hdr_termination = 0;
40static const char *commit_prefix = "";
41static unsigned long max_age = -1;
42static unsigned long min_age = -1;
43static int max_count = -1;
44static enum cmit_fmt commit_format = CMIT_FMT_RAW;
45static int merge_order = 0;
46static int show_breaks = 0;
47static int stop_traversal = 0;
48static int topo_order = 0;
49static int no_merges = 0;
50static const char **paths = NULL;
51
52static void show_commit(struct commit *commit)
53{
54 commit->object.flags |= SHOWN;
55 if (show_breaks) {
56 commit_prefix = "| ";
57 if (commit->object.flags & DISCONTINUITY) {
58 commit_prefix = "^ ";
59 } else if (commit->object.flags & BOUNDARY) {
60 commit_prefix = "= ";
61 }
62 }
63 printf("%s%s", commit_prefix, sha1_to_hex(commit->object.sha1));
64 if (show_parents) {
65 struct commit_list *parents = commit->parents;
66 while (parents) {
67 printf(" %s", sha1_to_hex(parents->item->object.sha1));
68 parents = parents->next;
69 }
70 }
71 if (commit_format == CMIT_FMT_ONELINE)
72 putchar(' ');
73 else
74 putchar('\n');
75
76 if (verbose_header) {
77 static char pretty_header[16384];
78 pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
79 printf("%s%c", pretty_header, hdr_termination);
80 }
81 fflush(stdout);
82}
83
84static int rewrite_one(struct commit **pp)
85{
86 for (;;) {
87 struct commit *p = *pp;
88 if (p->object.flags & (TREECHANGE | UNINTERESTING))
89 return 0;
90 if (!p->parents)
91 return -1;
92 *pp = p->parents->item;
93 }
94}
95
96static void rewrite_parents(struct commit *commit)
97{
98 struct commit_list **pp = &commit->parents;
99 while (*pp) {
100 struct commit_list *parent = *pp;
101 if (rewrite_one(&parent->item) < 0) {
102 *pp = parent->next;
103 continue;
104 }
105 pp = &parent->next;
106 }
107}
108
109static int filter_commit(struct commit * commit)
110{
111 if (stop_traversal && (commit->object.flags & BOUNDARY))
112 return STOP;
113 if (commit->object.flags & (UNINTERESTING|SHOWN))
114 return CONTINUE;
115 if (min_age != -1 && (commit->date > min_age))
116 return CONTINUE;
117 if (max_age != -1 && (commit->date < max_age)) {
118 stop_traversal=1;
119 return CONTINUE;
120 }
121 if (max_count != -1 && !max_count--)
122 return STOP;
123 if (no_merges && (commit->parents && commit->parents->next))
124 return CONTINUE;
125 if (paths && dense) {
126 if (!(commit->object.flags & TREECHANGE))
127 return CONTINUE;
128 rewrite_parents(commit);
129 }
130 return DO;
131}
132
133static int process_commit(struct commit * commit)
134{
135 int action=filter_commit(commit);
136
137 if (action == STOP) {
138 return STOP;
139 }
140
141 if (action == CONTINUE) {
142 return CONTINUE;
143 }
144
145 show_commit(commit);
146
147 return CONTINUE;
148}
149
150static struct object_list **add_object(struct object *obj, struct object_list **p, const char *name)
151{
152 struct object_list *entry = xmalloc(sizeof(*entry));
153 entry->item = obj;
154 entry->next = *p;
155 entry->name = name;
156 *p = entry;
157 return &entry->next;
158}
159
160static struct object_list **process_blob(struct blob *blob, struct object_list **p, const char *name)
161{
162 struct object *obj = &blob->object;
163
164 if (!blob_objects)
165 return p;
166 if (obj->flags & (UNINTERESTING | SEEN))
167 return p;
168 obj->flags |= SEEN;
169 return add_object(obj, p, name);
170}
171
172static struct object_list **process_tree(struct tree *tree, struct object_list **p, const char *name)
173{
174 struct object *obj = &tree->object;
175 struct tree_entry_list *entry;
176
177 if (!tree_objects)
178 return p;
179 if (obj->flags & (UNINTERESTING | SEEN))
180 return p;
181 if (parse_tree(tree) < 0)
182 die("bad tree object %s", sha1_to_hex(obj->sha1));
183 obj->flags |= SEEN;
184 p = add_object(obj, p, name);
185 entry = tree->entries;
186 tree->entries = NULL;
187 while (entry) {
188 struct tree_entry_list *next = entry->next;
189 if (entry->directory)
190 p = process_tree(entry->item.tree, p, entry->name);
191 else
192 p = process_blob(entry->item.blob, p, entry->name);
193 free(entry);
194 entry = next;
195 }
196 return p;
197}
198
199static struct object_list *pending_objects = NULL;
200
201static void show_commit_list(struct commit_list *list)
202{
203 struct object_list *objects = NULL, **p = &objects, *pending;
204 while (list) {
205 struct commit *commit = pop_most_recent_commit(&list, SEEN);
206
207 p = process_tree(commit->tree, p, "");
208 if (process_commit(commit) == STOP)
209 break;
210 }
211 for (pending = pending_objects; pending; pending = pending->next) {
212 struct object *obj = pending->item;
213 const char *name = pending->name;
214 if (obj->flags & (UNINTERESTING | SEEN))
215 continue;
216 if (obj->type == tag_type) {
217 obj->flags |= SEEN;
218 p = add_object(obj, p, name);
219 continue;
220 }
221 if (obj->type == tree_type) {
222 p = process_tree((struct tree *)obj, p, name);
223 continue;
224 }
225 if (obj->type == blob_type) {
226 p = process_blob((struct blob *)obj, p, name);
227 continue;
228 }
229 die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
230 }
231 while (objects) {
232 /* An object with name "foo\n0000000000000000000000000000000000000000"
233 * can be used confuse downstream git-pack-objects very badly.
234 */
235 const char *ep = strchr(objects->name, '\n');
236 if (ep) {
237 printf("%s %.*s\n", sha1_to_hex(objects->item->sha1),
238 (int) (ep - objects->name),
239 objects->name);
240 }
241 else
242 printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
243 objects = objects->next;
244 }
245}
246
247static void mark_blob_uninteresting(struct blob *blob)
248{
249 if (!blob_objects)
250 return;
251 if (blob->object.flags & UNINTERESTING)
252 return;
253 blob->object.flags |= UNINTERESTING;
254}
255
256static void mark_tree_uninteresting(struct tree *tree)
257{
258 struct object *obj = &tree->object;
259 struct tree_entry_list *entry;
260
261 if (!tree_objects)
262 return;
263 if (obj->flags & UNINTERESTING)
264 return;
265 obj->flags |= UNINTERESTING;
266 if (!has_sha1_file(obj->sha1))
267 return;
268 if (parse_tree(tree) < 0)
269 die("bad tree %s", sha1_to_hex(obj->sha1));
270 entry = tree->entries;
271 tree->entries = NULL;
272 while (entry) {
273 struct tree_entry_list *next = entry->next;
274 if (entry->directory)
275 mark_tree_uninteresting(entry->item.tree);
276 else
277 mark_blob_uninteresting(entry->item.blob);
278 free(entry);
279 entry = next;
280 }
281}
282
283static void mark_parents_uninteresting(struct commit *commit)
284{
285 struct commit_list *parents = commit->parents;
286
287 while (parents) {
288 struct commit *commit = parents->item;
289 commit->object.flags |= UNINTERESTING;
290
291 /*
292 * Normally we haven't parsed the parent
293 * yet, so we won't have a parent of a parent
294 * here. However, it may turn out that we've
295 * reached this commit some other way (where it
296 * wasn't uninteresting), in which case we need
297 * to mark its parents recursively too..
298 */
299 if (commit->parents)
300 mark_parents_uninteresting(commit);
301
302 /*
303 * A missing commit is ok iff its parent is marked
304 * uninteresting.
305 *
306 * We just mark such a thing parsed, so that when
307 * it is popped next time around, we won't be trying
308 * to parse it and get an error.
309 */
310 if (!has_sha1_file(commit->object.sha1))
311 commit->object.parsed = 1;
312 parents = parents->next;
313 }
314}
315
316static int everybody_uninteresting(struct commit_list *orig)
317{
318 struct commit_list *list = orig;
319 while (list) {
320 struct commit *commit = list->item;
321 list = list->next;
322 if (commit->object.flags & UNINTERESTING)
323 continue;
324 return 0;
325 }
326 return 1;
327}
328
329/*
330 * This is a truly stupid algorithm, but it's only
331 * used for bisection, and we just don't care enough.
332 *
333 * We care just barely enough to avoid recursing for
334 * non-merge entries.
335 */
336static int count_distance(struct commit_list *entry)
337{
338 int nr = 0;
339
340 while (entry) {
341 struct commit *commit = entry->item;
342 struct commit_list *p;
343
344 if (commit->object.flags & (UNINTERESTING | COUNTED))
345 break;
346 nr++;
347 commit->object.flags |= COUNTED;
348 p = commit->parents;
349 entry = p;
350 if (p) {
351 p = p->next;
352 while (p) {
353 nr += count_distance(p);
354 p = p->next;
355 }
356 }
357 }
358 return nr;
359}
360
361static void clear_distance(struct commit_list *list)
362{
363 while (list) {
364 struct commit *commit = list->item;
365 commit->object.flags &= ~COUNTED;
366 list = list->next;
367 }
368}
369
370static struct commit_list *find_bisection(struct commit_list *list)
371{
372 int nr, closest;
373 struct commit_list *p, *best;
374
375 nr = 0;
376 p = list;
377 while (p) {
378 nr++;
379 p = p->next;
380 }
381 closest = 0;
382 best = list;
383
384 p = list;
385 while (p) {
386 int distance = count_distance(p);
387 clear_distance(list);
388 if (nr - distance < distance)
389 distance = nr - distance;
390 if (distance > closest) {
391 best = p;
392 closest = distance;
393 }
394 p = p->next;
395 }
396 if (best)
397 best->next = NULL;
398 return best;
399}
400
401static void mark_edges_uninteresting(struct commit_list *list)
402{
403 for ( ; list; list = list->next) {
404 struct commit_list *parents = list->item->parents;
405
406 for ( ; parents; parents = parents->next) {
407 struct commit *commit = parents->item;
408 if (commit->object.flags & UNINTERESTING)
409 mark_tree_uninteresting(commit->tree);
410 }
411 }
412}
413
414static int is_different = 0;
415
416static void file_add_remove(struct diff_options *options,
417 int addremove, unsigned mode,
418 const unsigned char *sha1,
419 const char *base, const char *path)
420{
421 is_different = 1;
422}
423
424static void file_change(struct diff_options *options,
425 unsigned old_mode, unsigned new_mode,
426 const unsigned char *old_sha1,
427 const unsigned char *new_sha1,
428 const char *base, const char *path)
429{
430 is_different = 1;
431}
432
433static struct diff_options diff_opt = {
434 .recursive = 1,
435 .add_remove = file_add_remove,
436 .change = file_change,
437};
438
439static int same_tree(struct tree *t1, struct tree *t2)
440{
441 is_different = 0;
442 if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "", &diff_opt) < 0)
443 return 0;
444 return !is_different;
445}
446
447static int same_tree_as_empty(struct tree *t1)
448{
449 int retval;
450 void *tree;
451 struct tree_desc empty, real;
452
453 if (!t1)
454 return 0;
455
456 tree = read_object_with_reference(t1->object.sha1, "tree", &real.size, NULL);
457 if (!tree)
458 return 0;
459 real.buf = tree;
460
461 empty.buf = "";
462 empty.size = 0;
463
464 is_different = 0;
465 retval = diff_tree(&empty, &real, "", &diff_opt);
466 free(tree);
467
468 return retval >= 0 && !is_different;
469}
470
471static struct commit *try_to_simplify_merge(struct commit *commit, struct commit_list *parent)
472{
473 if (!commit->tree)
474 return NULL;
475
476 while (parent) {
477 struct commit *p = parent->item;
478 parent = parent->next;
479 parse_commit(p);
480 if (!p->tree)
481 continue;
482 if (same_tree(commit->tree, p->tree))
483 return p;
484 }
485 return NULL;
486}
487
488static void add_parents_to_list(struct commit *commit, struct commit_list **list)
489{
490 struct commit_list *parent = commit->parents;
491
492 /*
493 * If the commit is uninteresting, don't try to
494 * prune parents - we want the maximal uninteresting
495 * set.
496 *
497 * Normally we haven't parsed the parent
498 * yet, so we won't have a parent of a parent
499 * here. However, it may turn out that we've
500 * reached this commit some other way (where it
501 * wasn't uninteresting), in which case we need
502 * to mark its parents recursively too..
503 */
504 if (commit->object.flags & UNINTERESTING) {
505 while (parent) {
506 struct commit *p = parent->item;
507 parent = parent->next;
508 parse_commit(p);
509 p->object.flags |= UNINTERESTING;
510 if (p->parents)
511 mark_parents_uninteresting(p);
512 if (p->object.flags & SEEN)
513 continue;
514 p->object.flags |= SEEN;
515 insert_by_date(p, list);
516 }
517 return;
518 }
519
520 /*
521 * Ok, the commit wasn't uninteresting. If it
522 * is a merge, try to find the parent that has
523 * no differences in the path set if one exists.
524 */
525 if (paths && parent && parent->next) {
526 struct commit *preferred;
527
528 preferred = try_to_simplify_merge(commit, parent);
529 if (preferred) {
530 parent->item = preferred;
531 parent->next = NULL;
532 }
533 }
534
535 while (parent) {
536 struct commit *p = parent->item;
537
538 parent = parent->next;
539
540 parse_commit(p);
541 if (p->object.flags & SEEN)
542 continue;
543 p->object.flags |= SEEN;
544 insert_by_date(p, list);
545 }
546}
547
548static void compress_list(struct commit_list *list)
549{
550 while (list) {
551 struct commit *commit = list->item;
552 struct commit_list *parent = commit->parents;
553 list = list->next;
554
555 if (!parent) {
556 if (!same_tree_as_empty(commit->tree))
557 commit->object.flags |= TREECHANGE;
558 continue;
559 }
560
561 /*
562 * Exactly one parent? Check if it leaves the tree
563 * unchanged
564 */
565 if (!parent->next) {
566 struct tree *t1 = commit->tree;
567 struct tree *t2 = parent->item->tree;
568 if (!t1 || !t2 || same_tree(t1, t2))
569 continue;
570 }
571 commit->object.flags |= TREECHANGE;
572 }
573}
574
575static struct commit_list *limit_list(struct commit_list *list)
576{
577 struct commit_list *newlist = NULL;
578 struct commit_list **p = &newlist;
579 while (list) {
580 struct commit_list *entry = list;
581 struct commit *commit = list->item;
582 struct object *obj = &commit->object;
583
584 list = list->next;
585 free(entry);
586
587 if (max_age != -1 && (commit->date < max_age))
588 obj->flags |= UNINTERESTING;
589 if (unpacked && has_sha1_pack(obj->sha1))
590 obj->flags |= UNINTERESTING;
591 add_parents_to_list(commit, &list);
592 if (obj->flags & UNINTERESTING) {
593 mark_parents_uninteresting(commit);
594 if (everybody_uninteresting(list))
595 break;
596 continue;
597 }
598 if (min_age != -1 && (commit->date > min_age))
599 continue;
600 p = &commit_list_insert(commit, p)->next;
601 }
602 if (tree_objects)
603 mark_edges_uninteresting(newlist);
604 if (paths && dense)
605 compress_list(newlist);
606 if (bisect_list)
607 newlist = find_bisection(newlist);
608 return newlist;
609}
610
611static void add_pending_object(struct object *obj, const char *name)
612{
613 add_object(obj, &pending_objects, name);
614}
615
616static struct commit *get_commit_reference(const char *name, unsigned int flags)
617{
618 unsigned char sha1[20];
619 struct object *object;
620
621 if (get_sha1(name, sha1))
622 usage(rev_list_usage);
623 object = parse_object(sha1);
624 if (!object)
625 die("bad object %s", name);
626
627 /*
628 * Tag object? Look what it points to..
629 */
630 while (object->type == tag_type) {
631 struct tag *tag = (struct tag *) object;
632 object->flags |= flags;
633 if (tag_objects && !(object->flags & UNINTERESTING))
634 add_pending_object(object, tag->tag);
635 object = parse_object(tag->tagged->sha1);
636 if (!object)
637 die("bad object %s", sha1_to_hex(tag->tagged->sha1));
638 }
639
640 /*
641 * Commit object? Just return it, we'll do all the complex
642 * reachability crud.
643 */
644 if (object->type == commit_type) {
645 struct commit *commit = (struct commit *)object;
646 object->flags |= flags;
647 if (parse_commit(commit) < 0)
648 die("unable to parse commit %s", name);
649 if (flags & UNINTERESTING)
650 mark_parents_uninteresting(commit);
651 return commit;
652 }
653
654 /*
655 * Tree object? Either mark it uniniteresting, or add it
656 * to the list of objects to look at later..
657 */
658 if (object->type == tree_type) {
659 struct tree *tree = (struct tree *)object;
660 if (!tree_objects)
661 return NULL;
662 if (flags & UNINTERESTING) {
663 mark_tree_uninteresting(tree);
664 return NULL;
665 }
666 add_pending_object(object, "");
667 return NULL;
668 }
669
670 /*
671 * Blob object? You know the drill by now..
672 */
673 if (object->type == blob_type) {
674 struct blob *blob = (struct blob *)object;
675 if (!blob_objects)
676 return NULL;
677 if (flags & UNINTERESTING) {
678 mark_blob_uninteresting(blob);
679 return NULL;
680 }
681 add_pending_object(object, "");
682 return NULL;
683 }
684 die("%s is unknown object", name);
685}
686
687static void handle_one_commit(struct commit *com, struct commit_list **lst)
688{
689 if (!com || com->object.flags & SEEN)
690 return;
691 com->object.flags |= SEEN;
692 commit_list_insert(com, lst);
693}
694
695/* for_each_ref() callback does not allow user data -- Yuck. */
696static struct commit_list **global_lst;
697
698static int include_one_commit(const char *path, const unsigned char *sha1)
699{
700 struct commit *com = get_commit_reference(path, 0);
701 handle_one_commit(com, global_lst);
702 return 0;
703}
704
705static void handle_all(struct commit_list **lst)
706{
707 global_lst = lst;
708 for_each_ref(include_one_commit);
709 global_lst = NULL;
710}
711
712int main(int argc, const char **argv)
713{
714 const char *prefix = setup_git_directory();
715 struct commit_list *list = NULL;
716 int i, limited = 0;
717
718 for (i = 1 ; i < argc; i++) {
719 int flags;
720 const char *arg = argv[i];
721 char *dotdot;
722 struct commit *commit;
723
724 if (!strncmp(arg, "--max-count=", 12)) {
725 max_count = atoi(arg + 12);
726 continue;
727 }
728 if (!strncmp(arg, "--max-age=", 10)) {
729 max_age = atoi(arg + 10);
730 limited = 1;
731 continue;
732 }
733 if (!strncmp(arg, "--min-age=", 10)) {
734 min_age = atoi(arg + 10);
735 limited = 1;
736 continue;
737 }
738 if (!strcmp(arg, "--header")) {
739 verbose_header = 1;
740 continue;
741 }
742 if (!strncmp(arg, "--pretty", 8)) {
743 commit_format = get_commit_format(arg+8);
744 verbose_header = 1;
745 hdr_termination = '\n';
746 if (commit_format == CMIT_FMT_ONELINE)
747 commit_prefix = "";
748 else
749 commit_prefix = "commit ";
750 continue;
751 }
752 if (!strncmp(arg, "--no-merges", 11)) {
753 no_merges = 1;
754 continue;
755 }
756 if (!strcmp(arg, "--parents")) {
757 show_parents = 1;
758 continue;
759 }
760 if (!strcmp(arg, "--bisect")) {
761 bisect_list = 1;
762 continue;
763 }
764 if (!strcmp(arg, "--all")) {
765 handle_all(&list);
766 continue;
767 }
768 if (!strcmp(arg, "--objects")) {
769 tag_objects = 1;
770 tree_objects = 1;
771 blob_objects = 1;
772 continue;
773 }
774 if (!strcmp(arg, "--unpacked")) {
775 unpacked = 1;
776 limited = 1;
777 continue;
778 }
779 if (!strcmp(arg, "--merge-order")) {
780 merge_order = 1;
781 continue;
782 }
783 if (!strcmp(arg, "--show-breaks")) {
784 show_breaks = 1;
785 continue;
786 }
787 if (!strcmp(arg, "--topo-order")) {
788 topo_order = 1;
789 limited = 1;
790 continue;
791 }
792 if (!strcmp(arg, "--dense")) {
793 dense = 1;
794 continue;
795 }
796 if (!strcmp(arg, "--")) {
797 paths = get_pathspec(prefix, argv + i + 1);
798 if (paths) {
799 limited = 1;
800 diff_tree_setup_paths(paths);
801 }
802 break;
803 }
804
805 if (show_breaks && !merge_order)
806 usage(rev_list_usage);
807
808 flags = 0;
809 dotdot = strstr(arg, "..");
810 if (dotdot) {
811 char *next = dotdot + 2;
812 struct commit *exclude = NULL;
813 struct commit *include = NULL;
814 *dotdot = 0;
815 if (!*next)
816 next = "HEAD";
817 exclude = get_commit_reference(arg, UNINTERESTING);
818 include = get_commit_reference(next, 0);
819 if (exclude && include) {
820 limited = 1;
821 handle_one_commit(exclude, &list);
822 handle_one_commit(include, &list);
823 continue;
824 }
825 *dotdot = '.';
826 }
827 if (*arg == '^') {
828 flags = UNINTERESTING;
829 arg++;
830 limited = 1;
831 }
832 commit = get_commit_reference(arg, flags);
833 handle_one_commit(commit, &list);
834 }
835
836 save_commit_buffer = verbose_header;
837 track_object_refs = 0;
838
839 if (!merge_order) {
840 sort_by_date(&list);
841 if (list && !limited && max_count == 1 &&
842 !tag_objects && !tree_objects && !blob_objects) {
843 show_commit(list->item);
844 return 0;
845 }
846 if (limited)
847 list = limit_list(list);
848 if (topo_order)
849 sort_in_topological_order(&list);
850 show_commit_list(list);
851 } else {
852#ifndef NO_OPENSSL
853 if (sort_list_in_merge_order(list, &process_commit)) {
854 die("merge order sort failed\n");
855 }
856#else
857 die("merge order sort unsupported, OpenSSL not linked");
858#endif
859 }
860
861 return 0;
862}