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

#include "cache.h"
#include "refs.h"
#include "tag.h"
#include "commit.h"
#include "tree.h"
#include "blob.h"
#include "epoch.h"
#include "diff.h"
#include "revision.h"

/* bits #0 and #1 in revision.h */

#define COUNTED		(1u << 2)
#define SHOWN		(1u << 3)
#define TREECHANGE	(1u << 4)
#define TMP_MARK	(1u << 5) /* for isolated cases; clean after use */

static const char rev_list_usage[] =
"git-rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
"  limiting output:\n"
"    --max-count=nr\n"
"    --max-age=epoch\n"
"    --min-age=epoch\n"
"    --sparse\n"
"    --no-merges\n"
"    --remove-empty\n"
"    --all\n"
"  ordering output:\n"
"    --merge-order [ --show-breaks ]\n"
"    --topo-order\n"
"    --date-order\n"
"  formatting output:\n"
"    --parents\n"
"    --objects | --objects-edge\n"
"    --unpacked\n"
"    --header | --pretty\n"
"    --abbrev=nr | --no-abbrev\n"
"  special purpose:\n"
"    --bisect"
;

struct rev_info revs;

static int bisect_list = 0;
static int verbose_header = 0;
static int abbrev = DEFAULT_ABBREV;
static int show_parents = 0;
static int hdr_termination = 0;
static const char *commit_prefix = "";
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 no_merges = 0;

static void show_commit(struct commit *commit)
{
	commit->object.flags |= SHOWN;
	if (show_breaks) {
		commit_prefix = "| ";
		if (commit->object.flags & DISCONTINUITY) {
			commit_prefix = "^ ";     
		} else if (commit->object.flags & BOUNDARY) {
			commit_prefix = "= ";
		} 
        }        		
	printf("%s%s", commit_prefix, sha1_to_hex(commit->object.sha1));
	if (show_parents) {
		struct commit_list *parents = commit->parents;
		while (parents) {
			struct object *o = &(parents->item->object);
			parents = parents->next;
			if (o->flags & TMP_MARK)
				continue;
			printf(" %s", sha1_to_hex(o->sha1));
			o->flags |= TMP_MARK;
		}
		/* TMP_MARK is a general purpose flag that can
		 * be used locally, but the user should clean
		 * things up after it is done with them.
		 */
		for (parents = commit->parents;
		     parents;
		     parents = parents->next)
			parents->item->object.flags &= ~TMP_MARK;
	}
	if (commit_format == CMIT_FMT_ONELINE)
		putchar(' ');
	else
		putchar('\n');

	if (verbose_header) {
		static char pretty_header[16384];
		pretty_print_commit(commit_format, commit, ~0, pretty_header, sizeof(pretty_header), abbrev);
		printf("%s%c", pretty_header, hdr_termination);
	}
	fflush(stdout);
}

static int rewrite_one(struct commit **pp)
{
	for (;;) {
		struct commit *p = *pp;
		if (p->object.flags & (TREECHANGE | UNINTERESTING))
			return 0;
		if (!p->parents)
			return -1;
		*pp = p->parents->item;
	}
}

static void rewrite_parents(struct commit *commit)
{
	struct commit_list **pp = &commit->parents;
	while (*pp) {
		struct commit_list *parent = *pp;
		if (rewrite_one(&parent->item) < 0) {
			*pp = parent->next;
			continue;
		}
		pp = &parent->next;
	}
}

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 (revs.min_age != -1 && (commit->date > revs.min_age))
		return CONTINUE;
	if (revs.max_age != -1 && (commit->date < revs.max_age)) {
		stop_traversal=1;
		return CONTINUE;
	}
	if (no_merges && (commit->parents && commit->parents->next))
		return CONTINUE;
	if (revs.paths && revs.dense) {
		if (!(commit->object.flags & TREECHANGE))
			return CONTINUE;
		rewrite_parents(commit);
	}
	return DO;
}

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

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

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

	if (revs.max_count != -1 && !revs.max_count--)
		return STOP;

	show_commit(commit);

	return CONTINUE;
}

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

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

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

	if (!revs.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, path, name);
	me.up = path;
	me.elem = name;
	me.elem_len = strlen(name);
	entry = tree->entries;
	tree->entries = NULL;
	while (entry) {
		struct tree_entry_list *next = entry->next;
		if (entry->directory)
			p = process_tree(entry->item.tree, p, &me, entry->name);
		else
			p = process_blob(entry->item.blob, p, &me, entry->name);
		free(entry);
		entry = next;
	}
	return p;
}

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, NULL, "");
		if (process_commit(commit) == STOP)
			break;
	}
	for (pending = revs.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, NULL, name);
			continue;
		}
		if (obj->type == tree_type) {
			p = process_tree((struct tree *)obj, p, NULL, name);
			continue;
		}
		if (obj->type == blob_type) {
			p = process_blob((struct blob *)obj, p, NULL, name);
			continue;
		}
		die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
	}
	while (objects) {
		/* An object with name "foo\n0000000..." can be used to
		 * confuse downstream git-pack-objects very badly.
		 */
		const char *ep = strchr(objects->name, '\n');
		if (ep) {
			printf("%s %.*s\n", sha1_to_hex(objects->item->sha1),
			       (int) (ep - objects->name),
			       objects->name);
		}
		else
			printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
		objects = objects->next;
	}
}

static int everybody_uninteresting(struct commit_list *orig)
{
	struct commit_list *list = orig;
	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;
		if (!revs.paths || (commit->object.flags & TREECHANGE))
			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) {
		if (!revs.paths || (p->item->object.flags & TREECHANGE))
			nr++;
		p = p->next;
	}
	closest = 0;
	best = list;

	for (p = list; p; p = p->next) {
		int distance;

		if (revs.paths && !(p->item->object.flags & TREECHANGE))
			continue;

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

static void mark_edge_parents_uninteresting(struct commit *commit)
{
	struct commit_list *parents;

	for (parents = commit->parents; parents; parents = parents->next) {
		struct commit *parent = parents->item;
		if (!(parent->object.flags & UNINTERESTING))
			continue;
		mark_tree_uninteresting(parent->tree);
		if (revs.edge_hint && !(parent->object.flags & SHOWN)) {
			parent->object.flags |= SHOWN;
			printf("-%s\n", sha1_to_hex(parent->object.sha1));
		}
	}
}

static void mark_edges_uninteresting(struct commit_list *list)
{
	for ( ; list; list = list->next) {
		struct commit *commit = list->item;

		if (commit->object.flags & UNINTERESTING) {
			mark_tree_uninteresting(commit->tree);
			continue;
		}
		mark_edge_parents_uninteresting(commit);
	}
}

#define TREE_SAME	0
#define TREE_NEW	1
#define TREE_DIFFERENT	2
static int tree_difference = TREE_SAME;

static void file_add_remove(struct diff_options *options,
		    int addremove, unsigned mode,
		    const unsigned char *sha1,
		    const char *base, const char *path)
{
	int diff = TREE_DIFFERENT;

	/*
	 * Is it an add of a new file? It means that
	 * the old tree didn't have it at all, so we
	 * will turn "TREE_SAME" -> "TREE_NEW", but
	 * leave any "TREE_DIFFERENT" alone (and if
	 * it already was "TREE_NEW", we'll keep it
	 * "TREE_NEW" of course).
	 */
	if (addremove == '+') {
		diff = tree_difference;
		if (diff != TREE_SAME)
			return;
		diff = TREE_NEW;
	}
	tree_difference = diff;
}

static void file_change(struct diff_options *options,
		 unsigned old_mode, unsigned new_mode,
		 const unsigned char *old_sha1,
		 const unsigned char *new_sha1,
		 const char *base, const char *path)
{
	tree_difference = TREE_DIFFERENT;
}

static struct diff_options diff_opt = {
	.recursive = 1,
	.add_remove = file_add_remove,
	.change = file_change,
};

static int compare_tree(struct tree *t1, struct tree *t2)
{
	if (!t1)
		return TREE_NEW;
	if (!t2)
		return TREE_DIFFERENT;
	tree_difference = TREE_SAME;
	if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "", &diff_opt) < 0)
		return TREE_DIFFERENT;
	return tree_difference;
}

static int same_tree_as_empty(struct tree *t1)
{
	int retval;
	void *tree;
	struct tree_desc empty, real;

	if (!t1)
		return 0;

	tree = read_object_with_reference(t1->object.sha1, "tree", &real.size, NULL);
	if (!tree)
		return 0;
	real.buf = tree;

	empty.buf = "";
	empty.size = 0;

	tree_difference = 0;
	retval = diff_tree(&empty, &real, "", &diff_opt);
	free(tree);

	return retval >= 0 && !tree_difference;
}

static void try_to_simplify_commit(struct commit *commit)
{
	struct commit_list **pp, *parent;

	if (!commit->tree)
		return;

	if (!commit->parents) {
		if (!same_tree_as_empty(commit->tree))
			commit->object.flags |= TREECHANGE;
		return;
	}

	pp = &commit->parents;
	while ((parent = *pp) != NULL) {
		struct commit *p = parent->item;

		if (p->object.flags & UNINTERESTING) {
			pp = &parent->next;
			continue;
		}

		parse_commit(p);
		switch (compare_tree(p->tree, commit->tree)) {
		case TREE_SAME:
			parent->next = NULL;
			commit->parents = parent;
			return;

		case TREE_NEW:
			if (revs.remove_empty_trees && same_tree_as_empty(p->tree)) {
				*pp = parent->next;
				continue;
			}
		/* fallthrough */
		case TREE_DIFFERENT:
			pp = &parent->next;
			continue;
		}
		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
	}
	commit->object.flags |= TREECHANGE;
}

static void add_parents_to_list(struct commit *commit, struct commit_list **list)
{
	struct commit_list *parent = commit->parents;

	/*
	 * If the commit is uninteresting, don't try to
	 * prune parents - we want the maximal uninteresting
	 * set.
	 *
	 * Normally we haven't parsed the parent
	 * yet, so we won't have a parent of a parent
	 * here. However, it may turn out that we've
	 * reached this commit some other way (where it
	 * wasn't uninteresting), in which case we need
	 * to mark its parents recursively too..
	 */
	if (commit->object.flags & UNINTERESTING) {
		while (parent) {
			struct commit *p = parent->item;
			parent = parent->next;
			parse_commit(p);
			p->object.flags |= UNINTERESTING;
			if (p->parents)
				mark_parents_uninteresting(p);
			if (p->object.flags & SEEN)
				continue;
			p->object.flags |= SEEN;
			insert_by_date(p, list);
		}
		return;
	}

	/*
	 * Ok, the commit wasn't uninteresting. Try to
	 * simplify the commit history and find the parent
	 * that has no differences in the path set if one exists.
	 */
	if (revs.paths)
		try_to_simplify_commit(commit);

	parent = commit->parents;
	while (parent) {
		struct commit *p = parent->item;

		parent = parent->next;

		parse_commit(p);
		if (p->object.flags & SEEN)
			continue;
		p->object.flags |= SEEN;
		insert_by_date(p, list);
	}
}

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

		list = list->next;
		free(entry);

		if (revs.max_age != -1 && (commit->date < revs.max_age))
			obj->flags |= UNINTERESTING;
		if (revs.unpacked && has_sha1_pack(obj->sha1))
			obj->flags |= UNINTERESTING;
		add_parents_to_list(commit, &list);
		if (obj->flags & UNINTERESTING) {
			mark_parents_uninteresting(commit);
			if (everybody_uninteresting(list))
				break;
			continue;
		}
		if (revs.min_age != -1 && (commit->date > revs.min_age))
			continue;
		p = &commit_list_insert(commit, p)->next;
	}
	if (revs.tree_objects)
		mark_edges_uninteresting(newlist);
	if (bisect_list)
		newlist = find_bisection(newlist);
	return newlist;
}

int main(int argc, const char **argv)
{
	struct commit_list *list;
	int i;

	argc = setup_revisions(argc, argv, &revs);

	for (i = 1 ; i < argc; i++) {
		const char *arg = argv[i];

		/* accept -<digit>, like traditilnal "head" */
		if ((*arg == '-') && isdigit(arg[1])) {
			revs.max_count = atoi(arg + 1);
			continue;
		}
		if (!strcmp(arg, "-n")) {
			if (++i >= argc)
				die("-n requires an argument");
			revs.max_count = atoi(argv[i]);
			continue;
		}
		if (!strncmp(arg,"-n",2)) {
			revs.max_count = atoi(arg + 2);
			continue;
		}
		if (!strcmp(arg, "--header")) {
			verbose_header = 1;
			continue;
		}
		if (!strcmp(arg, "--no-abbrev")) {
			abbrev = 0;
			continue;
		}
		if (!strncmp(arg, "--abbrev=", 9)) {
			abbrev = strtoul(arg + 9, NULL, 10);
			if (abbrev && abbrev < MINIMUM_ABBREV)
				abbrev = MINIMUM_ABBREV;
			else if (40 < abbrev)
				abbrev = 40;
			continue;
		}
		if (!strncmp(arg, "--pretty", 8)) {
			commit_format = get_commit_format(arg+8);
			verbose_header = 1;
			hdr_termination = '\n';
			if (commit_format == CMIT_FMT_ONELINE)
				commit_prefix = "";
			else
				commit_prefix = "commit ";
			continue;
		}
		if (!strncmp(arg, "--no-merges", 11)) {
			no_merges = 1;
			continue;
		}
		if (!strcmp(arg, "--parents")) {
			show_parents = 1;
			continue;
		}
		if (!strcmp(arg, "--bisect")) {
			bisect_list = 1;
			continue;
		}
		if (!strcmp(arg, "--merge-order")) {
		        merge_order = 1;
			continue;
		}
		if (!strcmp(arg, "--show-breaks")) {
			show_breaks = 1;
			continue;
		}
		usage(rev_list_usage);

	}

	list = revs.commits;

	if (!list &&
	    (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) && !revs.pending_objects))
		usage(rev_list_usage);

	if (revs.paths)
		diff_tree_setup_paths(revs.paths);

	save_commit_buffer = verbose_header;
	track_object_refs = 0;

	if (!merge_order) {		
		sort_by_date(&list);
		if (list && !revs.limited && revs.max_count == 1 &&
		    !revs.tag_objects && !revs.tree_objects && !revs.blob_objects) {
			show_commit(list->item);
			return 0;
		}
	        if (revs.limited)
			list = limit_list(list);
		if (revs.topo_order)
			sort_in_topological_order(&list, revs.lifo);
		show_commit_list(list);
	} else {
#ifndef NO_OPENSSL
		if (sort_list_in_merge_order(list, &process_commit)) {
			die("merge order sort failed\n");
		}
#else
		die("merge order sort unsupported, OpenSSL not linked");
#endif
	}

	return 0;
}
Commit	Line	Data
64745109	1	#include "cache.h"
e091eb93	2	#include "refs.h"
36f8d174	3	#include "tag.h"
64745109	4	#include "commit.h"
9de48752 LT	5	#include "tree.h"
9de48752 LT	6	#include "blob.h"
a3437b8c	7	#include "epoch.h"
cf484544	8	#include "diff.h"
ae563542 LT	9	#include "revision.h"
	10
	11	/* bits #0 and #1 in revision.h */
64745109	12
8b3a1e05	13	#define COUNTED (1u << 2)
bce62866	14	#define SHOWN (1u << 3)
1b9e059d	15	#define TREECHANGE (1u << 4)
88494423	16	#define TMP_MARK (1u << 5) /* for isolated cases; clean after use */
8906300f	17
a6f68d47	18	static const char rev_list_usage[] =
69e0c256 JH	19	"git-rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
	20	" limiting output:\n"
	21	" --max-count=nr\n"
	22	" --max-age=epoch\n"
	23	" --min-age=epoch\n"
	24	" --sparse\n"
	25	" --no-merges\n"
93b74bca	26	" --remove-empty\n"
69e0c256 JH	27	" --all\n"
	28	" ordering output:\n"
	29	" --merge-order [ --show-breaks ]\n"
	30	" --topo-order\n"
4c8725f1	31	" --date-order\n"
69e0c256 JH	32	" formatting output:\n"
69e0c256 JH	33	" --parents\n"
c6496575	34	" --objects \| --objects-edge\n"
69e0c256 JH	35	" --unpacked\n"
69e0c256 JH	36	" --header \| --pretty\n"
9da5c2f0	37	" --abbrev=nr \| --no-abbrev\n"
69e0c256 JH	38	" special purpose:\n"
	39	" --bisect"
	40	;
a6f68d47	41
ae563542 LT	42	struct rev_info revs;
ae563542 LT	43
8b3a1e05	44	static int bisect_list = 0;
81f2bb1f	45	static int verbose_header = 0;
9da5c2f0	46	static int abbrev = DEFAULT_ABBREV;
81f2bb1f	47	static int show_parents = 0;
81f2bb1f	48	static int hdr_termination = 0;
d998a089	49	static const char *commit_prefix = "";
000182ea	50	static enum cmit_fmt commit_format = CMIT_FMT_RAW;
a3437b8c JS	51	static int merge_order = 0;
a3437b8c JS	52	static int show_breaks = 0;
5e749e25	53	static int stop_traversal = 0;
76cd8eb6	54	static int no_merges = 0;
e646de0d	55
81f2bb1f LT	56	static void show_commit(struct commit *commit)
81f2bb1f LT	57	{
51b1e171	58	commit->object.flags \|= SHOWN;
a3437b8c	59	if (show_breaks) {
d998a089	60	commit_prefix = "\| ";
a3437b8c	61	if (commit->object.flags & DISCONTINUITY) {
d998a089	62	commit_prefix = "^ ";
a3437b8c	63	} else if (commit->object.flags & BOUNDARY) {
d998a089	64	commit_prefix = "= ";
a3437b8c JS	65	}
a3437b8c JS	66	}
d998a089	67	printf("%s%s", commit_prefix, sha1_to_hex(commit->object.sha1));
81f2bb1f LT	68	if (show_parents) {
	69	struct commit_list *parents = commit->parents;
	70	while (parents) {
88494423	71	struct object *o = &(parents->item->object);
81f2bb1f	72	parents = parents->next;
88494423 JH	73	if (o->flags & TMP_MARK)
	74	continue;
	75	printf(" %s", sha1_to_hex(o->sha1));
	76	o->flags \|= TMP_MARK;
81f2bb1f	77	}
88494423 JH	78	/* TMP_MARK is a general purpose flag that can
	79	* be used locally, but the user should clean
	80	* things up after it is done with them.
	81	*/
	82	for (parents = commit->parents;
	83	parents;
	84	parents = parents->next)
	85	parents->item->object.flags &= ~TMP_MARK;
81f2bb1f	86	}
d87449c5 JH	87	if (commit_format == CMIT_FMT_ONELINE)
	88	putchar(' ');
	89	else
	90	putchar('\n');
	91
81f2bb1f	92	if (verbose_header) {
000182ea	93	static char pretty_header[16384];
9da5c2f0	94	pretty_print_commit(commit_format, commit, ~0, pretty_header, sizeof(pretty_header), abbrev);
000182ea	95	printf("%s%c", pretty_header, hdr_termination);
7620d39f LT	96	}
7620d39f LT	97	fflush(stdout);
a3437b8c JS	98	}
a3437b8c JS	99
129adf4d	100	static int rewrite_one(struct commit **pp)
1b9e059d LT	101	{
	102	for (;;) {
	103	struct commit p = pp;
	104	if (p->object.flags & (TREECHANGE \| UNINTERESTING))
129adf4d LT	105	return 0;
	106	if (!p->parents)
	107	return -1;
1b9e059d LT	108	*pp = p->parents->item;
	109	}
	110	}
	111
	112	static void rewrite_parents(struct commit *commit)
	113	{
129adf4d LT	114	struct commit_list **pp = &commit->parents;
	115	while (*pp) {
	116	struct commit_list parent = pp;
	117	if (rewrite_one(&parent->item) < 0) {
	118	*pp = parent->next;
	119	continue;
	120	}
	121	pp = &parent->next;
1b9e059d LT	122	}
	123	}
	124
a3437b8c JS	125	static int filter_commit(struct commit * commit)
a3437b8c JS	126	{
d2775a81	127	if (stop_traversal && (commit->object.flags & BOUNDARY))
5e749e25	128	return STOP;
51b1e171	129	if (commit->object.flags & (UNINTERESTING\|SHOWN))
a3437b8c	130	return CONTINUE;
ae563542	131	if (revs.min_age != -1 && (commit->date > revs.min_age))
a3437b8c	132	return CONTINUE;
ae563542	133	if (revs.max_age != -1 && (commit->date < revs.max_age)) {
d2775a81	134	stop_traversal=1;
27cfe2e2	135	return CONTINUE;
5e749e25	136	}
76cd8eb6 JS	137	if (no_merges && (commit->parents && commit->parents->next))
76cd8eb6 JS	138	return CONTINUE;
ae563542	139	if (revs.paths && revs.dense) {
1b9e059d LT	140	if (!(commit->object.flags & TREECHANGE))
	141	return CONTINUE;
	142	rewrite_parents(commit);
	143	}
a3437b8c JS	144	return DO;
	145	}
	146
	147	static int process_commit(struct commit * commit)
	148	{
	149	int action=filter_commit(commit);
	150
	151	if (action == STOP) {
	152	return STOP;
	153	}
	154
	155	if (action == CONTINUE) {
	156	return CONTINUE;
81f2bb1f	157	}
a3437b8c	158
ae563542	159	if (revs.max_count != -1 && !revs.max_count--)
07f92477 LT	160	return STOP;
07f92477 LT	161
a3437b8c JS	162	show_commit(commit);
	163
	164	return CONTINUE;
81f2bb1f LT	165	}
81f2bb1f LT	166
e646de0d JH	167	static struct object_list *process_blob(struct blob blob,
	168	struct object_list **p,
	169	struct name_path *path,
	170	const char *name)
9de48752 LT	171	{
	172	struct object *obj = &blob->object;
	173
ae563542	174	if (!revs.blob_objects)
9de48752 LT	175	return p;
	176	if (obj->flags & (UNINTERESTING \| SEEN))
	177	return p;
	178	obj->flags \|= SEEN;
e646de0d	179	return add_object(obj, p, path, name);
9de48752 LT	180	}
9de48752 LT	181
e646de0d JH	182	static struct object_list *process_tree(struct tree tree,
	183	struct object_list **p,
	184	struct name_path *path,
	185	const char *name)
9de48752 LT	186	{
	187	struct object *obj = &tree->object;
	188	struct tree_entry_list *entry;
e646de0d	189	struct name_path me;
9de48752	190
ae563542	191	if (!revs.tree_objects)
9de48752 LT	192	return p;
	193	if (obj->flags & (UNINTERESTING \| SEEN))
	194	return p;
	195	if (parse_tree(tree) < 0)
	196	die("bad tree object %s", sha1_to_hex(obj->sha1));
	197	obj->flags \|= SEEN;
e646de0d JH	198	p = add_object(obj, p, path, name);
	199	me.up = path;
	200	me.elem = name;
	201	me.elem_len = strlen(name);
b0d8923e LT	202	entry = tree->entries;
	203	tree->entries = NULL;
	204	while (entry) {
	205	struct tree_entry_list *next = entry->next;
9de48752	206	if (entry->directory)
e646de0d	207	p = process_tree(entry->item.tree, p, &me, entry->name);
9de48752	208	else
e646de0d	209	p = process_blob(entry->item.blob, p, &me, entry->name);
b0d8923e LT	210	free(entry);
b0d8923e LT	211	entry = next;
9de48752 LT	212	}
	213	return p;
	214	}
	215
81f2bb1f LT	216	static void show_commit_list(struct commit_list *list)
81f2bb1f LT	217	{
36f8d174	218	struct object_list objects = NULL, p = &objects, pending;
81f2bb1f LT	219	while (list) {
	220	struct commit *commit = pop_most_recent_commit(&list, SEEN);
	221
e646de0d	222	p = process_tree(commit->tree, p, NULL, "");
a3437b8c	223	if (process_commit(commit) == STOP)
81f2bb1f	224	break;
81f2bb1f	225	}
d9cfb964	226	for (pending = revs.pending_objects; pending; pending = pending->next) {
36f8d174 LT	227	struct object *obj = pending->item;
	228	const char *name = pending->name;
	229	if (obj->flags & (UNINTERESTING \| SEEN))
	230	continue;
	231	if (obj->type == tag_type) {
	232	obj->flags \|= SEEN;
e646de0d	233	p = add_object(obj, p, NULL, name);
36f8d174 LT	234	continue;
	235	}
	236	if (obj->type == tree_type) {
e646de0d	237	p = process_tree((struct tree *)obj, p, NULL, name);
36f8d174 LT	238	continue;
	239	}
	240	if (obj->type == blob_type) {
e646de0d	241	p = process_blob((struct blob *)obj, p, NULL, name);
36f8d174 LT	242	continue;
	243	}
	244	die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
	245	}
9de48752	246	while (objects) {
50319850 JH	247	/* An object with name "foo\n0000000..." can be used to
50319850 JH	248	* confuse downstream git-pack-objects very badly.
c807f771 JH	249	*/
	250	const char *ep = strchr(objects->name, '\n');
	251	if (ep) {
	252	printf("%s %.*s\n", sha1_to_hex(objects->item->sha1),
	253	(int) (ep - objects->name),
	254	objects->name);
	255	}
	256	else
	257	printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
9de48752 LT	258	objects = objects->next;
	259	}
	260	}
	261
4311d328	262	static int everybody_uninteresting(struct commit_list *orig)
8906300f	263	{
4311d328	264	struct commit_list *list = orig;
8906300f LT	265	while (list) {
	266	struct commit *commit = list->item;
	267	list = list->next;
	268	if (commit->object.flags & UNINTERESTING)
	269	continue;
	270	return 0;
	271	}
	272	return 1;
	273	}
	274
8b3a1e05 LT	275	/*
	276	* This is a truly stupid algorithm, but it's only
	277	* used for bisection, and we just don't care enough.
	278	*
	279	* We care just barely enough to avoid recursing for
	280	* non-merge entries.
	281	*/
	282	static int count_distance(struct commit_list *entry)
	283	{
	284	int nr = 0;
	285
	286	while (entry) {
	287	struct commit *commit = entry->item;
	288	struct commit_list *p;
	289
	290	if (commit->object.flags & (UNINTERESTING \| COUNTED))
	291	break;
ae563542	292	if (!revs.paths \|\| (commit->object.flags & TREECHANGE))
b3cfd939	293	nr++;
8b3a1e05 LT	294	commit->object.flags \|= COUNTED;
	295	p = commit->parents;
	296	entry = p;
	297	if (p) {
	298	p = p->next;
	299	while (p) {
	300	nr += count_distance(p);
	301	p = p->next;
	302	}
	303	}
	304	}
b3cfd939	305
8b3a1e05 LT	306	return nr;
	307	}
	308
3d958064	309	static void clear_distance(struct commit_list *list)
8b3a1e05 LT	310	{
	311	while (list) {
	312	struct commit *commit = list->item;
	313	commit->object.flags &= ~COUNTED;
	314	list = list->next;
	315	}
	316	}
	317
	318	static struct commit_list find_bisection(struct commit_list list)
	319	{
	320	int nr, closest;
	321	struct commit_list p, best;
	322
	323	nr = 0;
	324	p = list;
	325	while (p) {
ae563542	326	if (!revs.paths \|\| (p->item->object.flags & TREECHANGE))
b3cfd939	327	nr++;
8b3a1e05 LT	328	p = p->next;
	329	}
	330	closest = 0;
	331	best = list;
	332
b3cfd939 LT	333	for (p = list; p; p = p->next) {
	334	int distance;
	335
ae563542	336	if (revs.paths && !(p->item->object.flags & TREECHANGE))
b3cfd939 LT	337	continue;
	338
	339	distance = count_distance(p);
8b3a1e05 LT	340	clear_distance(list);
	341	if (nr - distance < distance)
	342	distance = nr - distance;
	343	if (distance > closest) {
	344	best = p;
	345	closest = distance;
	346	}
8b3a1e05 LT	347	}
	348	if (best)
	349	best->next = NULL;
	350	return best;
	351	}
	352
c6496575 JH	353	static void mark_edge_parents_uninteresting(struct commit *commit)
	354	{
	355	struct commit_list *parents;
	356
	357	for (parents = commit->parents; parents; parents = parents->next) {
	358	struct commit *parent = parents->item;
	359	if (!(parent->object.flags & UNINTERESTING))
	360	continue;
	361	mark_tree_uninteresting(parent->tree);
ae563542	362	if (revs.edge_hint && !(parent->object.flags & SHOWN)) {
eb38cc68	363	parent->object.flags \|= SHOWN;
c6496575	364	printf("-%s\n", sha1_to_hex(parent->object.sha1));
eb38cc68	365	}
c6496575 JH	366	}
	367	}
	368
5bdbaaa4 LT	369	static void mark_edges_uninteresting(struct commit_list *list)
	370	{
	371	for ( ; list; list = list->next) {
c6496575	372	struct commit *commit = list->item;
5bdbaaa4	373
c6496575 JH	374	if (commit->object.flags & UNINTERESTING) {
	375	mark_tree_uninteresting(commit->tree);
	376	continue;
5bdbaaa4	377	}
c6496575	378	mark_edge_parents_uninteresting(commit);
5bdbaaa4 LT	379	}
	380	}
	381
461cf59f LT	382	#define TREE_SAME 0
	383	#define TREE_NEW 1
	384	#define TREE_DIFFERENT 2
	385	static int tree_difference = TREE_SAME;
cf484544 LT	386
	387	static void file_add_remove(struct diff_options *options,
	388	int addremove, unsigned mode,
	389	const unsigned char *sha1,
	390	const char base, const char path)
	391	{
461cf59f LT	392	int diff = TREE_DIFFERENT;
	393
	394	/*
	395	* Is it an add of a new file? It means that
	396	* the old tree didn't have it at all, so we
	397	* will turn "TREE_SAME" -> "TREE_NEW", but
	398	* leave any "TREE_DIFFERENT" alone (and if
	399	* it already was "TREE_NEW", we'll keep it
	400	* "TREE_NEW" of course).
	401	*/
	402	if (addremove == '+') {
	403	diff = tree_difference;
	404	if (diff != TREE_SAME)
	405	return;
	406	diff = TREE_NEW;
	407	}
	408	tree_difference = diff;
cf484544 LT	409	}
	410
	411	static void file_change(struct diff_options *options,
	412	unsigned old_mode, unsigned new_mode,
	413	const unsigned char *old_sha1,
	414	const unsigned char *new_sha1,
	415	const char base, const char path)
	416	{
461cf59f	417	tree_difference = TREE_DIFFERENT;
cf484544 LT	418	}
	419
	420	static struct diff_options diff_opt = {
	421	.recursive = 1,
	422	.add_remove = file_add_remove,
	423	.change = file_change,
	424	};
	425
461cf59f	426	static int compare_tree(struct tree t1, struct tree t2)
1b9e059d	427	{
461cf59f LT	428	if (!t1)
	429	return TREE_NEW;
	430	if (!t2)
	431	return TREE_DIFFERENT;
	432	tree_difference = TREE_SAME;
1b9e059d	433	if (diff_tree_sha1(t1->object.sha1, t2->object.sha1, "", &diff_opt) < 0)
461cf59f LT	434	return TREE_DIFFERENT;
461cf59f LT	435	return tree_difference;
1b9e059d LT	436	}
1b9e059d LT	437
129adf4d LT	438	static int same_tree_as_empty(struct tree *t1)
	439	{
	440	int retval;
	441	void *tree;
	442	struct tree_desc empty, real;
	443
	444	if (!t1)
	445	return 0;
	446
	447	tree = read_object_with_reference(t1->object.sha1, "tree", &real.size, NULL);
	448	if (!tree)
	449	return 0;
	450	real.buf = tree;
	451
	452	empty.buf = "";
	453	empty.size = 0;
	454
461cf59f	455	tree_difference = 0;
129adf4d LT	456	retval = diff_tree(&empty, &real, "", &diff_opt);
	457	free(tree);
	458
461cf59f	459	return retval >= 0 && !tree_difference;
129adf4d LT	460	}
129adf4d LT	461
461cf59f	462	static void try_to_simplify_commit(struct commit *commit)
cf484544	463	{
461cf59f LT	464	struct commit_list *pp, parent;
461cf59f LT	465
cf484544	466	if (!commit->tree)
461cf59f	467	return;
cf484544	468
461cf59f LT	469	if (!commit->parents) {
	470	if (!same_tree_as_empty(commit->tree))
	471	commit->object.flags \|= TREECHANGE;
	472	return;
	473	}
	474
	475	pp = &commit->parents;
	476	while ((parent = *pp) != NULL) {
cf484544	477	struct commit *p = parent->item;
461cf59f LT	478
	479	if (p->object.flags & UNINTERESTING) {
	480	pp = &parent->next;
	481	continue;
	482	}
	483
cf484544	484	parse_commit(p);
461cf59f LT	485	switch (compare_tree(p->tree, commit->tree)) {
	486	case TREE_SAME:
	487	parent->next = NULL;
	488	commit->parents = parent;
	489	return;
	490
	491	case TREE_NEW:
ae563542	492	if (revs.remove_empty_trees && same_tree_as_empty(p->tree)) {
461cf59f LT	493	*pp = parent->next;
	494	continue;
	495	}
	496	/* fallthrough */
	497	case TREE_DIFFERENT:
	498	pp = &parent->next;
cf484544	499	continue;
461cf59f LT	500	}
461cf59f LT	501	die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
cf484544	502	}
461cf59f	503	commit->object.flags \|= TREECHANGE;
cf484544 LT	504	}
	505
	506	static void add_parents_to_list(struct commit commit, struct commit_list *list)
	507	{
	508	struct commit_list *parent = commit->parents;
	509
	510	/*
	511	* If the commit is uninteresting, don't try to
	512	* prune parents - we want the maximal uninteresting
	513	* set.
	514	*
	515	* Normally we haven't parsed the parent
	516	* yet, so we won't have a parent of a parent
	517	* here. However, it may turn out that we've
	518	* reached this commit some other way (where it
	519	* wasn't uninteresting), in which case we need
	520	* to mark its parents recursively too..
	521	*/
	522	if (commit->object.flags & UNINTERESTING) {
	523	while (parent) {
	524	struct commit *p = parent->item;
	525	parent = parent->next;
	526	parse_commit(p);
	527	p->object.flags \|= UNINTERESTING;
	528	if (p->parents)
	529	mark_parents_uninteresting(p);
	530	if (p->object.flags & SEEN)
	531	continue;
	532	p->object.flags \|= SEEN;
	533	insert_by_date(p, list);
	534	}
	535	return;
	536	}
	537
	538	/*
461cf59f LT	539	* Ok, the commit wasn't uninteresting. Try to
	540	* simplify the commit history and find the parent
	541	* that has no differences in the path set if one exists.
cf484544	542	*/
ae563542	543	if (revs.paths)
461cf59f	544	try_to_simplify_commit(commit);
cf484544	545
461cf59f	546	parent = commit->parents;
cf484544 LT	547	while (parent) {
	548	struct commit *p = parent->item;
	549
	550	parent = parent->next;
	551
	552	parse_commit(p);
	553	if (p->object.flags & SEEN)
	554	continue;
	555	p->object.flags \|= SEEN;
	556	insert_by_date(p, list);
	557	}
	558	}
	559
6da4016a	560	static struct commit_list limit_list(struct commit_list list)
3b42a63c LT	561	{
	562	struct commit_list *newlist = NULL;
	563	struct commit_list **p = &newlist;
36f8d174	564	while (list) {
cf484544 LT	565	struct commit_list *entry = list;
cf484544 LT	566	struct commit *commit = list->item;
3b42a63c LT	567	struct object *obj = &commit->object;
3b42a63c LT	568
cf484544 LT	569	list = list->next;
	570	free(entry);
	571
ae563542	572	if (revs.max_age != -1 && (commit->date < revs.max_age))
27cfe2e2	573	obj->flags \|= UNINTERESTING;
d9a83684	574	if (revs.unpacked && has_sha1_pack(obj->sha1))
12d2a187	575	obj->flags \|= UNINTERESTING;
cf484544	576	add_parents_to_list(commit, &list);
337cb3fb	577	if (obj->flags & UNINTERESTING) {
3b42a63c LT	578	mark_parents_uninteresting(commit);
	579	if (everybody_uninteresting(list))
	580	break;
	581	continue;
	582	}
ae563542	583	if (revs.min_age != -1 && (commit->date > revs.min_age))
27cfe2e2	584	continue;
3b42a63c	585	p = &commit_list_insert(commit, p)->next;
36f8d174	586	}
ae563542	587	if (revs.tree_objects)
5bdbaaa4	588	mark_edges_uninteresting(newlist);
8b3a1e05 LT	589	if (bisect_list)
8b3a1e05 LT	590	newlist = find_bisection(newlist);
3b42a63c LT	591	return newlist;
	592	}
	593
cf484544	594	int main(int argc, const char **argv)
64745109	595	{
ae563542	596	struct commit_list *list;
d9a83684	597	int i;
64745109	598
ae563542 LT	599	argc = setup_revisions(argc, argv, &revs);
ae563542 LT	600
fcfda02b	601	for (i = 1 ; i < argc; i++) {
cf484544	602	const char *arg = argv[i];
fcfda02b	603
8233340c EW	604	/* accept -<digit>, like traditilnal "head" */
8233340c EW	605	if ((*arg == '-') && isdigit(arg[1])) {
ae563542	606	revs.max_count = atoi(arg + 1);
8233340c EW	607	continue;
8233340c EW	608	}
3af06987 EW	609	if (!strcmp(arg, "-n")) {
	610	if (++i >= argc)
	611	die("-n requires an argument");
ae563542	612	revs.max_count = atoi(argv[i]);
3af06987 EW	613	continue;
	614	}
	615	if (!strncmp(arg,"-n",2)) {
ae563542	616	revs.max_count = atoi(arg + 2);
a6f68d47	617	continue;
fcfda02b	618	}
a6f68d47 LT	619	if (!strcmp(arg, "--header")) {
	620	verbose_header = 1;
	621	continue;
	622	}
9da5c2f0 JH	623	if (!strcmp(arg, "--no-abbrev")) {
	624	abbrev = 0;
	625	continue;
	626	}
	627	if (!strncmp(arg, "--abbrev=", 9)) {
	628	abbrev = strtoul(arg + 9, NULL, 10);
	629	if (abbrev && abbrev < MINIMUM_ABBREV)
	630	abbrev = MINIMUM_ABBREV;
	631	else if (40 < abbrev)
	632	abbrev = 40;
	633	continue;
	634	}
000182ea LT	635	if (!strncmp(arg, "--pretty", 8)) {
000182ea LT	636	commit_format = get_commit_format(arg+8);
9d97aa64	637	verbose_header = 1;
9d97aa64	638	hdr_termination = '\n';
d87449c5	639	if (commit_format == CMIT_FMT_ONELINE)
d998a089	640	commit_prefix = "";
d87449c5	641	else
d998a089	642	commit_prefix = "commit ";
9d97aa64 LT	643	continue;
9d97aa64 LT	644	}
76cd8eb6 JS	645	if (!strncmp(arg, "--no-merges", 11)) {
	646	no_merges = 1;
	647	continue;
	648	}
97658004 LT	649	if (!strcmp(arg, "--parents")) {
	650	show_parents = 1;
	651	continue;
	652	}
8b3a1e05 LT	653	if (!strcmp(arg, "--bisect")) {
	654	bisect_list = 1;
	655	continue;
	656	}
12ba7eaf	657	if (!strcmp(arg, "--merge-order")) {
a3437b8c JS	658	merge_order = 1;
	659	continue;
	660	}
12ba7eaf	661	if (!strcmp(arg, "--show-breaks")) {
a3437b8c JS	662	show_breaks = 1;
	663	continue;
	664	}
ae563542	665	usage(rev_list_usage);
a6f68d47	666
fcfda02b KS	667	}
fcfda02b KS	668
ae563542	669	list = revs.commits;
ae563542	670
ef1cc2cc	671	if (!list &&
ae563542	672	(!(revs.tag_objects\|\|revs.tree_objects\|\|revs.blob_objects) && !revs.pending_objects))
7b34c2fa LT	673	usage(rev_list_usage);
7b34c2fa LT	674
d9a83684	675	if (revs.paths)
ae563542	676	diff_tree_setup_paths(revs.paths);
7b34c2fa	677
60ab26de	678	save_commit_buffer = verbose_header;
8805ccac	679	track_object_refs = 0;
60ab26de	680
a3437b8c	681	if (!merge_order) {
a7336ae5	682	sort_by_date(&list);
d9a83684	683	if (list && !revs.limited && revs.max_count == 1 &&
ae563542	684	!revs.tag_objects && !revs.tree_objects && !revs.blob_objects) {
fe5f51ce LT	685	show_commit(list->item);
	686	return 0;
	687	}
d9a83684	688	if (revs.limited)
a3437b8c	689	list = limit_list(list);
ae563542 LT	690	if (revs.topo_order)
ae563542 LT	691	sort_in_topological_order(&list, revs.lifo);
a3437b8c	692	show_commit_list(list);
a3437b8c	693	} else {
dd53c7ab	694	#ifndef NO_OPENSSL
a3437b8c	695	if (sort_list_in_merge_order(list, &process_commit)) {
dd53c7ab	696	die("merge order sort failed\n");
a3437b8c	697	}
dd53c7ab PB	698	#else
	699	die("merge order sort unsupported, OpenSSL not linked");
	700	#endif
a3437b8c	701	}
8906300f	702
64745109 LT	703	return 0;
64745109 LT	704	}