[thirdparty/git.git] / rev-list.c

#include "cache.h"
#include "tag.h"
#include "commit.h"
#include "tree.h"
#include "blob.h"
#include "epoch.h"

#define SEEN		(1u << 0)
#define INTERESTING	(1u << 1)
#define COUNTED		(1u << 2)
#define SHOWN		(1u << 3)

static const char rev_list_usage[] =
	"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
		      "  --max-count=nr\n"
		      "  --max-age=epoch\n"
		      "  --min-age=epoch\n"
		      "  --bisect\n"
		      "  --objects\n"
		      "  --unpacked\n"
		      "  --header\n"
		      "  --pretty\n"
		      "  --merge-order [ --show-breaks ]";

static int unpacked = 0;
static int bisect_list = 0;
static int tag_objects = 0;
static int tree_objects = 0;
static int blob_objects = 0;
static int verbose_header = 0;
static int show_parents = 0;
static int hdr_termination = 0;
static const char *prefix = "";
static unsigned long max_age = -1;
static unsigned long min_age = -1;
static int max_count = -1;
static enum cmit_fmt commit_format = CMIT_FMT_RAW;
static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
static int topo_order = 0;

static void show_commit(struct commit *commit)
{
	commit->object.flags |= SHOWN;
	if (show_breaks) {
		prefix = "| ";
		if (commit->object.flags & DISCONTINUITY) {
			prefix = "^ ";     
		} else if (commit->object.flags & BOUNDARY) {
			prefix = "= ";
		} 
        }        		
	printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
	if (show_parents) {
		struct commit_list *parents = commit->parents;
		while (parents) {
			printf(" %s", sha1_to_hex(parents->item->object.sha1));
			parents = parents->next;
		}
	}
	putchar('\n');
	if (verbose_header) {
		static char pretty_header[16384];
		pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
		printf("%s%c", pretty_header, hdr_termination);
	}
	fflush(stdout);
}

static int filter_commit(struct commit * commit)
{
	if (stop_traversal && (commit->object.flags & BOUNDARY))
		return STOP;
	if (commit->object.flags & (UNINTERESTING|SHOWN))
		return CONTINUE;
	if (min_age != -1 && (commit->date > min_age))
		return CONTINUE;
	if (max_age != -1 && (commit->date < max_age)) {
		stop_traversal=1;
		return merge_order?CONTINUE:STOP;
	}
	if (max_count != -1 && !max_count--)
		return STOP;
	return DO;
}

static int process_commit(struct commit * commit)
{
	int action=filter_commit(commit);

	if (action == STOP) {
		return STOP;
	}

	if (action == CONTINUE) {
		return CONTINUE;
	}

	show_commit(commit);

	return CONTINUE;
}

static struct object_list **add_object(struct object *obj, struct object_list **p, const char *name)
{
	struct object_list *entry = xmalloc(sizeof(*entry));
	entry->item = obj;
	entry->next = *p;
	entry->name = name;
	*p = entry;
	return &entry->next;
}

static struct object_list **process_blob(struct blob *blob, struct object_list **p, const char *name)
{
	struct object *obj = &blob->object;

	if (!blob_objects)
		return p;
	if (obj->flags & (UNINTERESTING | SEEN))
		return p;
	obj->flags |= SEEN;
	return add_object(obj, p, name);
}

static struct object_list **process_tree(struct tree *tree, struct object_list **p, const char *name)
{
	struct object *obj = &tree->object;
	struct tree_entry_list *entry;

	if (!tree_objects)
		return p;
	if (obj->flags & (UNINTERESTING | SEEN))
		return p;
	if (parse_tree(tree) < 0)
		die("bad tree object %s", sha1_to_hex(obj->sha1));
	obj->flags |= SEEN;
	p = add_object(obj, p, name);
	for (entry = tree->entries ; entry ; entry = entry->next) {
		if (entry->directory)
			p = process_tree(entry->item.tree, p, entry->name);
		else
			p = process_blob(entry->item.blob, p, entry->name);
	}
	return p;
}

static struct object_list *pending_objects = NULL;

static void show_commit_list(struct commit_list *list)
{
	struct object_list *objects = NULL, **p = &objects, *pending;
	while (list) {
		struct commit *commit = pop_most_recent_commit(&list, SEEN);

		p = process_tree(commit->tree, p, "");
		if (process_commit(commit) == STOP)
			break;
	}
	for (pending = pending_objects; pending; pending = pending->next) {
		struct object *obj = pending->item;
		const char *name = pending->name;
		if (obj->flags & (UNINTERESTING | SEEN))
			continue;
		if (obj->type == tag_type) {
			obj->flags |= SEEN;
			p = add_object(obj, p, name);
			continue;
		}
		if (obj->type == tree_type) {
			p = process_tree((struct tree *)obj, p, name);
			continue;
		}
		if (obj->type == blob_type) {
			p = process_blob((struct blob *)obj, p, name);
			continue;
		}
		die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
	}
	while (objects) {
		printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
		objects = objects->next;
	}
}

static void mark_blob_uninteresting(struct blob *blob)
{
	if (!blob_objects)
		return;
	if (blob->object.flags & UNINTERESTING)
		return;
	blob->object.flags |= UNINTERESTING;
}

static void mark_tree_uninteresting(struct tree *tree)
{
	struct object *obj = &tree->object;
	struct tree_entry_list *entry;

	if (!tree_objects)
		return;
	if (obj->flags & UNINTERESTING)
		return;
	obj->flags |= UNINTERESTING;
	if (!has_sha1_file(obj->sha1))
		return;
	if (parse_tree(tree) < 0)
		die("bad tree %s", sha1_to_hex(obj->sha1));
	entry = tree->entries;
	while (entry) {
		if (entry->directory)
			mark_tree_uninteresting(entry->item.tree);
		else
			mark_blob_uninteresting(entry->item.blob);
		entry = entry->next;
	}
}

static void mark_parents_uninteresting(struct commit *commit)
{
	struct commit_list *parents = commit->parents;

	if (tree_objects)
		mark_tree_uninteresting(commit->tree);
	while (parents) {
		struct commit *commit = parents->item;
		commit->object.flags |= UNINTERESTING;

		/*
		 * A missing commit is ok iff its parent is marked 
		 * uninteresting.
		 *
		 * We just mark such a thing parsed, so that when
		 * it is popped next time around, we won't be trying
		 * to parse it and get an error.
		 */
		if (!has_sha1_file(commit->object.sha1))
			commit->object.parsed = 1;
		parents = parents->next;
	}
}

static int everybody_uninteresting(struct commit_list *list)
{
	while (list) {
		struct commit *commit = list->item;
		list = list->next;
		if (commit->object.flags & UNINTERESTING)
			continue;
		return 0;
	}
	return 1;
}

/*
 * This is a truly stupid algorithm, but it's only
 * used for bisection, and we just don't care enough.
 *
 * We care just barely enough to avoid recursing for
 * non-merge entries.
 */
static int count_distance(struct commit_list *entry)
{
	int nr = 0;

	while (entry) {
		struct commit *commit = entry->item;
		struct commit_list *p;

		if (commit->object.flags & (UNINTERESTING | COUNTED))
			break;
		nr++;
		commit->object.flags |= COUNTED;
		p = commit->parents;
		entry = p;
		if (p) {
			p = p->next;
			while (p) {
				nr += count_distance(p);
				p = p->next;
			}
		}
	}
	return nr;
}

static void clear_distance(struct commit_list *list)
{
	while (list) {
		struct commit *commit = list->item;
		commit->object.flags &= ~COUNTED;
		list = list->next;
	}
}

static struct commit_list *find_bisection(struct commit_list *list)
{
	int nr, closest;
	struct commit_list *p, *best;

	nr = 0;
	p = list;
	while (p) {
		nr++;
		p = p->next;
	}
	closest = 0;
	best = list;

	p = list;
	while (p) {
		int distance = count_distance(p);
		clear_distance(list);
		if (nr - distance < distance)
			distance = nr - distance;
		if (distance > closest) {
			best = p;
			closest = distance;
		}
		p = p->next;
	}
	if (best)
		best->next = NULL;
	return best;
}

static struct commit_list *limit_list(struct commit_list *list)
{
	struct commit_list *newlist = NULL;
	struct commit_list **p = &newlist;
	while (list) {
		struct commit *commit = pop_most_recent_commit(&list, SEEN);
		struct object *obj = &commit->object;

		if (unpacked && has_sha1_pack(obj->sha1))
			obj->flags |= UNINTERESTING;
		if (obj->flags & UNINTERESTING) {
			mark_parents_uninteresting(commit);
			if (everybody_uninteresting(list))
				break;
			continue;
		}
		p = &commit_list_insert(commit, p)->next;
	}
	if (bisect_list)
		newlist = find_bisection(newlist);
	return newlist;
}

static void add_pending_object(struct object *obj, const char *name)
{
	add_object(obj, &pending_objects, name);
}

static struct commit *get_commit_reference(const char *name, unsigned int flags)
{
	unsigned char sha1[20];
	struct object *object;

	if (get_sha1(name, sha1))
		usage(rev_list_usage);
	object = parse_object(sha1);
	if (!object)
		die("bad object %s", name);

	/*
	 * Tag object? Look what it points to..
	 */
	while (object->type == tag_type) {
		struct tag *tag = (struct tag *) object;
		object->flags |= flags;
		if (tag_objects && !(object->flags & UNINTERESTING))
			add_pending_object(object, tag->tag);
		object = parse_object(tag->tagged->sha1);
	}

	/*
	 * Commit object? Just return it, we'll do all the complex
	 * reachability crud.
	 */
	if (object->type == commit_type) {
		struct commit *commit = (struct commit *)object;
		object->flags |= flags;
		if (parse_commit(commit) < 0)
			die("unable to parse commit %s", name);
		if (flags & UNINTERESTING)
			mark_parents_uninteresting(commit);
		return commit;
	}

	/*
	 * Tree object? Either mark it uniniteresting, or add it
	 * to the list of objects to look at later..
	 */
	if (object->type == tree_type) {
		struct tree *tree = (struct tree *)object;
		if (!tree_objects)
			return NULL;
		if (flags & UNINTERESTING) {
			mark_tree_uninteresting(tree);
			return NULL;
		}
		add_pending_object(object, "");
		return NULL;
	}

	/*
	 * Blob object? You know the drill by now..
	 */
	if (object->type == blob_type) {
		struct blob *blob = (struct blob *)object;
		if (!blob_objects)
			return NULL;
		if (flags & UNINTERESTING) {
			mark_blob_uninteresting(blob);
			return NULL;
		}
		add_pending_object(object, "");
		return NULL;
	}
	die("%s is unknown object", name);
}

int main(int argc, char **argv)
{
	struct commit_list *list = NULL;
	int i, limited = 0;

	for (i = 1 ; i < argc; i++) {
		int flags;
		char *arg = argv[i];
		struct commit *commit;

		if (!strncmp(arg, "--max-count=", 12)) {
			max_count = atoi(arg + 12);
			continue;
		}
		if (!strncmp(arg, "--max-age=", 10)) {
			max_age = atoi(arg + 10);
			continue;
		}
		if (!strncmp(arg, "--min-age=", 10)) {
			min_age = atoi(arg + 10);
			continue;
		}
		if (!strcmp(arg, "--header")) {
			verbose_header = 1;
			continue;
		}
		if (!strncmp(arg, "--pretty", 8)) {
			commit_format = get_commit_format(arg+8);
			verbose_header = 1;
			hdr_termination = '\n';
			prefix = "commit ";
			continue;
		}
		if (!strcmp(arg, "--parents")) {
			show_parents = 1;
			continue;
		}
		if (!strcmp(arg, "--bisect")) {
			bisect_list = 1;
			continue;
		}
		if (!strcmp(arg, "--objects")) {
			tag_objects = 1;
			tree_objects = 1;
			blob_objects = 1;
			continue;
		}
		if (!strcmp(arg, "--unpacked")) {
			unpacked = 1;
			limited = 1;
			continue;
		}
		if (!strcmp(arg, "--merge-order")) {
		        merge_order = 1;
			continue;
		}
		if (!strcmp(arg, "--show-breaks")) {
			show_breaks = 1;
			continue;
		}
		if (!strcmp(arg, "--topo-order")) {
		        topo_order = 1;
		        limited = 1;
			continue;
		}

		flags = 0;
		if (*arg == '^') {
			flags = UNINTERESTING;
			arg++;
			limited = 1;
		}
		if (show_breaks && !merge_order)
			usage(rev_list_usage);
		commit = get_commit_reference(arg, flags);
		if (!commit)
			continue;
		if (commit->object.flags & SEEN)
			continue;
		commit->object.flags |= SEEN;
		commit_list_insert(commit, &list);
	}

	if (!merge_order) {		
		sort_by_date(&list);
	        if (limited)
			list = limit_list(list);
		if (topo_order)
			sort_in_topological_order(&list);
		show_commit_list(list);
	} else {
		if (sort_list_in_merge_order(list, &process_commit)) {
			  die("merge order sort failed\n");
		}
	}

	return 0;
}
Commit	Line	Data
64745109	1	#include "cache.h"
36f8d174	2	#include "tag.h"
64745109	3	#include "commit.h"
9de48752 LT	4	#include "tree.h"
9de48752 LT	5	#include "blob.h"
a3437b8c	6	#include "epoch.h"
64745109	7
8906300f LT	8	#define SEEN (1u << 0)
8906300f LT	9	#define INTERESTING (1u << 1)
8b3a1e05	10	#define COUNTED (1u << 2)
bce62866	11	#define SHOWN (1u << 3)
8906300f	12
a6f68d47 LT	13	static const char rev_list_usage[] =
	14	"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
	15	" --max-count=nr\n"
	16	" --max-age=epoch\n"
	17	" --min-age=epoch\n"
12d2a187 LT	18	" --bisect\n"
	19	" --objects\n"
	20	" --unpacked\n"
9d97aa64	21	" --header\n"
a3437b8c JS	22	" --pretty\n"
a3437b8c JS	23	" --merge-order [ --show-breaks ]";
a6f68d47	24
12d2a187	25	static int unpacked = 0;
8b3a1e05	26	static int bisect_list = 0;
3c90f03d	27	static int tag_objects = 0;
9de48752 LT	28	static int tree_objects = 0;
9de48752 LT	29	static int blob_objects = 0;
81f2bb1f LT	30	static int verbose_header = 0;
81f2bb1f LT	31	static int show_parents = 0;
81f2bb1f LT	32	static int hdr_termination = 0;
	33	static const char *prefix = "";
	34	static unsigned long max_age = -1;
	35	static unsigned long min_age = -1;
	36	static int max_count = -1;
000182ea	37	static enum cmit_fmt commit_format = CMIT_FMT_RAW;
a3437b8c JS	38	static int merge_order = 0;
a3437b8c JS	39	static int show_breaks = 0;
5e749e25	40	static int stop_traversal = 0;
d2d02a49	41	static int topo_order = 0;
81f2bb1f LT	42
	43	static void show_commit(struct commit *commit)
	44	{
51b1e171	45	commit->object.flags \|= SHOWN;
a3437b8c JS	46	if (show_breaks) {
	47	prefix = "\| ";
	48	if (commit->object.flags & DISCONTINUITY) {
	49	prefix = "^ ";
	50	} else if (commit->object.flags & BOUNDARY) {
	51	prefix = "= ";
	52	}
	53	}
81f2bb1f LT	54	printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
	55	if (show_parents) {
	56	struct commit_list *parents = commit->parents;
	57	while (parents) {
	58	printf(" %s", sha1_to_hex(parents->item->object.sha1));
	59	parents = parents->next;
	60	}
	61	}
	62	putchar('\n');
	63	if (verbose_header) {
000182ea LT	64	static char pretty_header[16384];
	65	pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
	66	printf("%s%c", pretty_header, hdr_termination);
7620d39f LT	67	}
7620d39f LT	68	fflush(stdout);
a3437b8c JS	69	}
	70
	71	static int filter_commit(struct commit * commit)
	72	{
d2775a81	73	if (stop_traversal && (commit->object.flags & BOUNDARY))
5e749e25	74	return STOP;
51b1e171	75	if (commit->object.flags & (UNINTERESTING\|SHOWN))
a3437b8c JS	76	return CONTINUE;
	77	if (min_age != -1 && (commit->date > min_age))
	78	return CONTINUE;
5e749e25	79	if (max_age != -1 && (commit->date < max_age)) {
d2775a81 JS	80	stop_traversal=1;
d2775a81 JS	81	return merge_order?CONTINUE:STOP;
5e749e25	82	}
a3437b8c JS	83	if (max_count != -1 && !max_count--)
a3437b8c JS	84	return STOP;
a3437b8c JS	85	return DO;
	86	}
	87
	88	static int process_commit(struct commit * commit)
	89	{
	90	int action=filter_commit(commit);
	91
	92	if (action == STOP) {
	93	return STOP;
	94	}
	95
	96	if (action == CONTINUE) {
	97	return CONTINUE;
81f2bb1f	98	}
a3437b8c JS	99
	100	show_commit(commit);
	101
	102	return CONTINUE;
81f2bb1f LT	103	}
81f2bb1f LT	104
9ce43d1c	105	static struct object_list *add_object(struct object obj, struct object_list *p, const char name)
9de48752 LT	106	{
	107	struct object_list entry = xmalloc(sizeof(entry));
	108	entry->item = obj;
36f8d174	109	entry->next = *p;
9ce43d1c	110	entry->name = name;
9de48752 LT	111	*p = entry;
	112	return &entry->next;
	113	}
	114
9ce43d1c	115	static struct object_list *process_blob(struct blob blob, struct object_list *p, const char name)
9de48752 LT	116	{
	117	struct object *obj = &blob->object;
	118
	119	if (!blob_objects)
	120	return p;
	121	if (obj->flags & (UNINTERESTING \| SEEN))
	122	return p;
	123	obj->flags \|= SEEN;
9ce43d1c	124	return add_object(obj, p, name);
9de48752 LT	125	}
9de48752 LT	126
9ce43d1c	127	static struct object_list *process_tree(struct tree tree, struct object_list *p, const char name)
9de48752 LT	128	{
	129	struct object *obj = &tree->object;
	130	struct tree_entry_list *entry;
	131
	132	if (!tree_objects)
	133	return p;
	134	if (obj->flags & (UNINTERESTING \| SEEN))
	135	return p;
	136	if (parse_tree(tree) < 0)
	137	die("bad tree object %s", sha1_to_hex(obj->sha1));
	138	obj->flags \|= SEEN;
9ce43d1c	139	p = add_object(obj, p, name);
9de48752 LT	140	for (entry = tree->entries ; entry ; entry = entry->next) {
9de48752 LT	141	if (entry->directory)
9ce43d1c	142	p = process_tree(entry->item.tree, p, entry->name);
9de48752	143	else
9ce43d1c	144	p = process_blob(entry->item.blob, p, entry->name);
9de48752 LT	145	}
	146	return p;
	147	}
	148
36f8d174 LT	149	static struct object_list *pending_objects = NULL;
36f8d174 LT	150
81f2bb1f LT	151	static void show_commit_list(struct commit_list *list)
81f2bb1f LT	152	{
36f8d174	153	struct object_list objects = NULL, p = &objects, pending;
81f2bb1f LT	154	while (list) {
	155	struct commit *commit = pop_most_recent_commit(&list, SEEN);
	156
9ce43d1c	157	p = process_tree(commit->tree, p, "");
a3437b8c	158	if (process_commit(commit) == STOP)
81f2bb1f	159	break;
81f2bb1f	160	}
36f8d174 LT	161	for (pending = pending_objects; pending; pending = pending->next) {
	162	struct object *obj = pending->item;
	163	const char *name = pending->name;
	164	if (obj->flags & (UNINTERESTING \| SEEN))
	165	continue;
	166	if (obj->type == tag_type) {
	167	obj->flags \|= SEEN;
	168	p = add_object(obj, p, name);
	169	continue;
	170	}
	171	if (obj->type == tree_type) {
	172	p = process_tree((struct tree *)obj, p, name);
	173	continue;
	174	}
	175	if (obj->type == blob_type) {
	176	p = process_blob((struct blob *)obj, p, name);
	177	continue;
	178	}
	179	die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
	180	}
9de48752	181	while (objects) {
9ce43d1c	182	printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
9de48752 LT	183	objects = objects->next;
	184	}
	185	}
	186
	187	static void mark_blob_uninteresting(struct blob *blob)
	188	{
	189	if (!blob_objects)
	190	return;
	191	if (blob->object.flags & UNINTERESTING)
	192	return;
	193	blob->object.flags \|= UNINTERESTING;
	194	}
	195
	196	static void mark_tree_uninteresting(struct tree *tree)
	197	{
	198	struct object *obj = &tree->object;
	199	struct tree_entry_list *entry;
	200
	201	if (!tree_objects)
	202	return;
	203	if (obj->flags & UNINTERESTING)
	204	return;
	205	obj->flags \|= UNINTERESTING;
454fbbcd LT	206	if (!has_sha1_file(obj->sha1))
454fbbcd LT	207	return;
9de48752 LT	208	if (parse_tree(tree) < 0)
	209	die("bad tree %s", sha1_to_hex(obj->sha1));
	210	entry = tree->entries;
	211	while (entry) {
	212	if (entry->directory)
	213	mark_tree_uninteresting(entry->item.tree);
	214	else
	215	mark_blob_uninteresting(entry->item.blob);
	216	entry = entry->next;
	217	}
81f2bb1f LT	218	}
81f2bb1f LT	219
8906300f LT	220	static void mark_parents_uninteresting(struct commit *commit)
	221	{
	222	struct commit_list *parents = commit->parents;
	223
9de48752 LT	224	if (tree_objects)
9de48752 LT	225	mark_tree_uninteresting(commit->tree);
8906300f LT	226	while (parents) {
	227	struct commit *commit = parents->item;
	228	commit->object.flags \|= UNINTERESTING;
454fbbcd LT	229
	230	/*
	231	* A missing commit is ok iff its parent is marked
	232	* uninteresting.
	233	*
	234	* We just mark such a thing parsed, so that when
	235	* it is popped next time around, we won't be trying
	236	* to parse it and get an error.
	237	*/
	238	if (!has_sha1_file(commit->object.sha1))
	239	commit->object.parsed = 1;
8906300f LT	240	parents = parents->next;
	241	}
	242	}
	243
	244	static int everybody_uninteresting(struct commit_list *list)
	245	{
	246	while (list) {
	247	struct commit *commit = list->item;
	248	list = list->next;
	249	if (commit->object.flags & UNINTERESTING)
	250	continue;
	251	return 0;
	252	}
	253	return 1;
	254	}
	255
8b3a1e05 LT	256	/*
	257	* This is a truly stupid algorithm, but it's only
	258	* used for bisection, and we just don't care enough.
	259	*
	260	* We care just barely enough to avoid recursing for
	261	* non-merge entries.
	262	*/
	263	static int count_distance(struct commit_list *entry)
	264	{
	265	int nr = 0;
	266
	267	while (entry) {
	268	struct commit *commit = entry->item;
	269	struct commit_list *p;
	270
	271	if (commit->object.flags & (UNINTERESTING \| COUNTED))
	272	break;
	273	nr++;
	274	commit->object.flags \|= COUNTED;
	275	p = commit->parents;
	276	entry = p;
	277	if (p) {
	278	p = p->next;
	279	while (p) {
	280	nr += count_distance(p);
	281	p = p->next;
	282	}
	283	}
	284	}
	285	return nr;
	286	}
	287
3d958064	288	static void clear_distance(struct commit_list *list)
8b3a1e05 LT	289	{
	290	while (list) {
	291	struct commit *commit = list->item;
	292	commit->object.flags &= ~COUNTED;
	293	list = list->next;
	294	}
	295	}
	296
	297	static struct commit_list find_bisection(struct commit_list list)
	298	{
	299	int nr, closest;
	300	struct commit_list p, best;
	301
	302	nr = 0;
	303	p = list;
	304	while (p) {
	305	nr++;
	306	p = p->next;
	307	}
	308	closest = 0;
	309	best = list;
	310
	311	p = list;
	312	while (p) {
	313	int distance = count_distance(p);
	314	clear_distance(list);
	315	if (nr - distance < distance)
	316	distance = nr - distance;
	317	if (distance > closest) {
	318	best = p;
	319	closest = distance;
	320	}
	321	p = p->next;
	322	}
	323	if (best)
	324	best->next = NULL;
	325	return best;
	326	}
	327
6da4016a	328	static struct commit_list limit_list(struct commit_list list)
3b42a63c LT	329	{
	330	struct commit_list *newlist = NULL;
	331	struct commit_list **p = &newlist;
36f8d174	332	while (list) {
3b42a63c LT	333	struct commit *commit = pop_most_recent_commit(&list, SEEN);
	334	struct object *obj = &commit->object;
	335
12d2a187 LT	336	if (unpacked && has_sha1_pack(obj->sha1))
12d2a187 LT	337	obj->flags \|= UNINTERESTING;
337cb3fb	338	if (obj->flags & UNINTERESTING) {
3b42a63c LT	339	mark_parents_uninteresting(commit);
	340	if (everybody_uninteresting(list))
	341	break;
	342	continue;
	343	}
	344	p = &commit_list_insert(commit, p)->next;
36f8d174	345	}
8b3a1e05 LT	346	if (bisect_list)
8b3a1e05 LT	347	newlist = find_bisection(newlist);
3b42a63c LT	348	return newlist;
	349	}
	350
36f8d174 LT	351	static void add_pending_object(struct object obj, const char name)
	352	{
	353	add_object(obj, &pending_objects, name);
	354	}
	355
3c90f03d LT	356	static struct commit get_commit_reference(const char name, unsigned int flags)
	357	{
	358	unsigned char sha1[20];
36f8d174	359	struct object *object;
3c90f03d LT	360
	361	if (get_sha1(name, sha1))
	362	usage(rev_list_usage);
36f8d174 LT	363	object = parse_object(sha1);
	364	if (!object)
	365	die("bad object %s", name);
	366
	367	/*
	368	* Tag object? Look what it points to..
	369	*/
013aab82	370	while (object->type == tag_type) {
36f8d174 LT	371	struct tag tag = (struct tag ) object;
	372	object->flags \|= flags;
	373	if (tag_objects && !(object->flags & UNINTERESTING))
	374	add_pending_object(object, tag->tag);
013aab82	375	object = parse_object(tag->tagged->sha1);
36f8d174 LT	376	}
	377
	378	/*
	379	* Commit object? Just return it, we'll do all the complex
	380	* reachability crud.
	381	*/
	382	if (object->type == commit_type) {
	383	struct commit commit = (struct commit )object;
	384	object->flags \|= flags;
	385	if (parse_commit(commit) < 0)
	386	die("unable to parse commit %s", name);
454fbbcd LT	387	if (flags & UNINTERESTING)
454fbbcd LT	388	mark_parents_uninteresting(commit);
36f8d174 LT	389	return commit;
	390	}
	391
	392	/*
	393	* Tree object? Either mark it uniniteresting, or add it
	394	* to the list of objects to look at later..
	395	*/
	396	if (object->type == tree_type) {
	397	struct tree tree = (struct tree )object;
	398	if (!tree_objects)
960bba0d	399	return NULL;
36f8d174 LT	400	if (flags & UNINTERESTING) {
	401	mark_tree_uninteresting(tree);
	402	return NULL;
	403	}
	404	add_pending_object(object, "");
	405	return NULL;
	406	}
	407
	408	/*
	409	* Blob object? You know the drill by now..
	410	*/
	411	if (object->type == blob_type) {
	412	struct blob blob = (struct blob )object;
	413	if (!blob_objects)
960bba0d	414	return NULL;
36f8d174 LT	415	if (flags & UNINTERESTING) {
	416	mark_blob_uninteresting(blob);
	417	return NULL;
	418	}
	419	add_pending_object(object, "");
	420	return NULL;
	421	}
	422	die("%s is unknown object", name);
3c90f03d LT	423	}
3c90f03d LT	424
64745109 LT	425	int main(int argc, char **argv)
64745109 LT	426	{
64745109	427	struct commit_list *list = NULL;
337cb3fb	428	int i, limited = 0;
64745109	429
fcfda02b	430	for (i = 1 ; i < argc; i++) {
337cb3fb	431	int flags;
fcfda02b	432	char *arg = argv[i];
337cb3fb	433	struct commit *commit;
fcfda02b KS	434
	435	if (!strncmp(arg, "--max-count=", 12)) {
	436	max_count = atoi(arg + 12);
a6f68d47 LT	437	continue;
	438	}
	439	if (!strncmp(arg, "--max-age=", 10)) {
fcfda02b	440	max_age = atoi(arg + 10);
a6f68d47 LT	441	continue;
	442	}
	443	if (!strncmp(arg, "--min-age=", 10)) {
fcfda02b	444	min_age = atoi(arg + 10);
a6f68d47	445	continue;
fcfda02b	446	}
a6f68d47 LT	447	if (!strcmp(arg, "--header")) {
	448	verbose_header = 1;
	449	continue;
	450	}
000182ea LT	451	if (!strncmp(arg, "--pretty", 8)) {
000182ea LT	452	commit_format = get_commit_format(arg+8);
9d97aa64	453	verbose_header = 1;
9d97aa64 LT	454	hdr_termination = '\n';
	455	prefix = "commit ";
	456	continue;
	457	}
97658004 LT	458	if (!strcmp(arg, "--parents")) {
	459	show_parents = 1;
	460	continue;
	461	}
8b3a1e05 LT	462	if (!strcmp(arg, "--bisect")) {
	463	bisect_list = 1;
	464	continue;
	465	}
9de48752	466	if (!strcmp(arg, "--objects")) {
3c90f03d	467	tag_objects = 1;
9de48752 LT	468	tree_objects = 1;
	469	blob_objects = 1;
	470	continue;
	471	}
12d2a187 LT	472	if (!strcmp(arg, "--unpacked")) {
	473	unpacked = 1;
	474	limited = 1;
	475	continue;
	476	}
12ba7eaf	477	if (!strcmp(arg, "--merge-order")) {
a3437b8c JS	478	merge_order = 1;
	479	continue;
	480	}
12ba7eaf	481	if (!strcmp(arg, "--show-breaks")) {
a3437b8c JS	482	show_breaks = 1;
	483	continue;
	484	}
d2d02a49 LT	485	if (!strcmp(arg, "--topo-order")) {
d2d02a49 LT	486	topo_order = 1;
e6c3505b	487	limited = 1;
d2d02a49 LT	488	continue;
d2d02a49 LT	489	}
a6f68d47	490
337cb3fb LT	491	flags = 0;
	492	if (*arg == '^') {
	493	flags = UNINTERESTING;
	494	arg++;
	495	limited = 1;
	496	}
3c90f03d	497	if (show_breaks && !merge_order)
a6f68d47	498	usage(rev_list_usage);
3c90f03d LT	499	commit = get_commit_reference(arg, flags);
	500	if (!commit)
	501	continue;
960cea2d	502	if (commit->object.flags & SEEN)
bce62866	503	continue;
960cea2d	504	commit->object.flags \|= SEEN;
a7336ae5	505	commit_list_insert(commit, &list);
fcfda02b KS	506	}
fcfda02b KS	507
a3437b8c	508	if (!merge_order) {
a7336ae5	509	sort_by_date(&list);
17ebe977	510	if (limited)
a3437b8c	511	list = limit_list(list);
d2d02a49 LT	512	if (topo_order)
d2d02a49 LT	513	sort_in_topological_order(&list);
a3437b8c	514	show_commit_list(list);
a3437b8c	515	} else {
a3437b8c JS	516	if (sort_list_in_merge_order(list, &process_commit)) {
	517	die("merge order sort failed\n");
	518	}
a3437b8c	519	}
8906300f	520
64745109 LT	521	return 0;
64745109 LT	522	}