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

#include "cache.h"
#include "commit.h"
#include "epoch.h"

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

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"
		      "  --header\n"
		      "  --pretty\n"
		      "  --merge-order [ --show-breaks ]";

static int bisect_list = 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 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);
	}	
}

static int filter_commit(struct commit * commit)
{
	if (merge_order && 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)) {
		if (!merge_order)
			return STOP;
		else {
			stop_traversal = 1;
			return CONTINUE;
		}
	}
	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 void show_commit_list(struct commit_list *list)
{
	while (list) {
		struct commit *commit = pop_most_recent_commit(&list, SEEN);

		if (process_commit(commit) == STOP)
			break;
	}
}

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

	while (parents) {
		struct commit *commit = parents->item;
		commit->object.flags |= UNINTERESTING;
		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;
}

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

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

static enum cmit_fmt get_commit_format(const char *arg)
{
	if (!*arg)
		return CMIT_FMT_DEFAULT;
	if (!strcmp(arg, "=raw"))
		return CMIT_FMT_RAW;
	if (!strcmp(arg, "=medium"))
		return CMIT_FMT_MEDIUM;
	if (!strcmp(arg, "=short"))
		return CMIT_FMT_SHORT;
	usage(rev_list_usage);	
}			


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];
		unsigned char sha1[20];
		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 (!strncmp(arg, "--merge-order", 13)) {
		        merge_order = 1;
			continue;
		}
		if (!strncmp(arg, "--show-breaks", 13)) {
			show_breaks = 1;
			continue;
		}

		flags = 0;
		if (*arg == '^') {
			flags = UNINTERESTING;
			arg++;
			limited = 1;
		}
		if (get_sha1(arg, sha1) || (show_breaks && !merge_order))
			usage(rev_list_usage);
		commit = lookup_commit_reference(sha1);
		if (!commit || parse_commit(commit) < 0)
			die("bad commit object %s", arg);
		commit->object.flags |= flags;
		commit_list_insert(commit, &list);
	}

	if (!list)
		usage(rev_list_usage);

	if (!merge_order) {		
	        if (limited)
			list = limit_list(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 LT	1	#include "cache.h"
64745109 LT	2	#include "commit.h"
a3437b8c	3	#include "epoch.h"
64745109	4
8906300f LT	5	#define SEEN (1u << 0)
8906300f LT	6	#define INTERESTING (1u << 1)
8b3a1e05	7	#define COUNTED (1u << 2)
51b1e171	8	#define SHOWN (LAST_EPOCH_FLAG << 2)
8906300f	9
a6f68d47 LT	10	static const char rev_list_usage[] =
	11	"usage: git-rev-list [OPTION] commit-id <commit-id>\n"
	12	" --max-count=nr\n"
	13	" --max-age=epoch\n"
	14	" --min-age=epoch\n"
9d97aa64	15	" --header\n"
a3437b8c JS	16	" --pretty\n"
a3437b8c JS	17	" --merge-order [ --show-breaks ]";
a6f68d47	18
8b3a1e05	19	static int bisect_list = 0;
81f2bb1f LT	20	static int verbose_header = 0;
81f2bb1f LT	21	static int show_parents = 0;
81f2bb1f LT	22	static int hdr_termination = 0;
	23	static const char *prefix = "";
	24	static unsigned long max_age = -1;
	25	static unsigned long min_age = -1;
	26	static int max_count = -1;
000182ea	27	static enum cmit_fmt commit_format = CMIT_FMT_RAW;
a3437b8c JS	28	static int merge_order = 0;
a3437b8c JS	29	static int show_breaks = 0;
5e749e25	30	static int stop_traversal = 0;
81f2bb1f LT	31
	32	static void show_commit(struct commit *commit)
	33	{
51b1e171	34	commit->object.flags \|= SHOWN;
a3437b8c JS	35	if (show_breaks) {
	36	prefix = "\| ";
	37	if (commit->object.flags & DISCONTINUITY) {
	38	prefix = "^ ";
	39	} else if (commit->object.flags & BOUNDARY) {
	40	prefix = "= ";
	41	}
	42	}
81f2bb1f LT	43	printf("%s%s", prefix, sha1_to_hex(commit->object.sha1));
	44	if (show_parents) {
	45	struct commit_list *parents = commit->parents;
	46	while (parents) {
	47	printf(" %s", sha1_to_hex(parents->item->object.sha1));
	48	parents = parents->next;
	49	}
	50	}
	51	putchar('\n');
	52	if (verbose_header) {
000182ea LT	53	static char pretty_header[16384];
	54	pretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));
	55	printf("%s%c", pretty_header, hdr_termination);
a3437b8c JS	56	}
	57	}
	58
	59	static int filter_commit(struct commit * commit)
	60	{
5e749e25 JS	61	if (merge_order && stop_traversal && commit->object.flags & BOUNDARY)
5e749e25 JS	62	return STOP;
51b1e171	63	if (commit->object.flags & (UNINTERESTING\|SHOWN))
a3437b8c JS	64	return CONTINUE;
	65	if (min_age != -1 && (commit->date > min_age))
	66	return CONTINUE;
5e749e25 JS	67	if (max_age != -1 && (commit->date < max_age)) {
	68	if (!merge_order)
	69	return STOP;
	70	else {
	71	stop_traversal = 1;
	72	return CONTINUE;
	73	}
	74	}
a3437b8c JS	75	if (max_count != -1 && !max_count--)
a3437b8c JS	76	return STOP;
a3437b8c JS	77	return DO;
	78	}
	79
	80	static int process_commit(struct commit * commit)
	81	{
	82	int action=filter_commit(commit);
	83
	84	if (action == STOP) {
	85	return STOP;
	86	}
	87
	88	if (action == CONTINUE) {
	89	return CONTINUE;
81f2bb1f	90	}
a3437b8c JS	91
	92	show_commit(commit);
	93
	94	return CONTINUE;
81f2bb1f LT	95	}
	96
	97	static void show_commit_list(struct commit_list *list)
	98	{
	99	while (list) {
	100	struct commit *commit = pop_most_recent_commit(&list, SEEN);
	101
a3437b8c	102	if (process_commit(commit) == STOP)
81f2bb1f	103	break;
81f2bb1f LT	104	}
	105	}
	106
8906300f LT	107	static void mark_parents_uninteresting(struct commit *commit)
	108	{
	109	struct commit_list *parents = commit->parents;
	110
	111	while (parents) {
	112	struct commit *commit = parents->item;
	113	commit->object.flags \|= UNINTERESTING;
	114	parents = parents->next;
	115	}
	116	}
	117
	118	static int everybody_uninteresting(struct commit_list *list)
	119	{
	120	while (list) {
	121	struct commit *commit = list->item;
	122	list = list->next;
	123	if (commit->object.flags & UNINTERESTING)
	124	continue;
	125	return 0;
	126	}
	127	return 1;
	128	}
	129
8b3a1e05 LT	130	/*
	131	* This is a truly stupid algorithm, but it's only
	132	* used for bisection, and we just don't care enough.
	133	*
	134	* We care just barely enough to avoid recursing for
	135	* non-merge entries.
	136	*/
	137	static int count_distance(struct commit_list *entry)
	138	{
	139	int nr = 0;
	140
	141	while (entry) {
	142	struct commit *commit = entry->item;
	143	struct commit_list *p;
	144
	145	if (commit->object.flags & (UNINTERESTING \| COUNTED))
	146	break;
	147	nr++;
	148	commit->object.flags \|= COUNTED;
	149	p = commit->parents;
	150	entry = p;
	151	if (p) {
	152	p = p->next;
	153	while (p) {
	154	nr += count_distance(p);
	155	p = p->next;
	156	}
	157	}
	158	}
	159	return nr;
	160	}
	161
3d958064	162	static void clear_distance(struct commit_list *list)
8b3a1e05 LT	163	{
	164	while (list) {
	165	struct commit *commit = list->item;
	166	commit->object.flags &= ~COUNTED;
	167	list = list->next;
	168	}
	169	}
	170
	171	static struct commit_list find_bisection(struct commit_list list)
	172	{
	173	int nr, closest;
	174	struct commit_list p, best;
	175
	176	nr = 0;
	177	p = list;
	178	while (p) {
	179	nr++;
	180	p = p->next;
	181	}
	182	closest = 0;
	183	best = list;
	184
	185	p = list;
	186	while (p) {
	187	int distance = count_distance(p);
	188	clear_distance(list);
	189	if (nr - distance < distance)
	190	distance = nr - distance;
	191	if (distance > closest) {
	192	best = p;
	193	closest = distance;
	194	}
	195	p = p->next;
	196	}
	197	if (best)
	198	best->next = NULL;
	199	return best;
	200	}
	201
337cb3fb	202	struct commit_list limit_list(struct commit_list list)
3b42a63c LT	203	{
	204	struct commit_list *newlist = NULL;
	205	struct commit_list **p = &newlist;
	206	do {
	207	struct commit *commit = pop_most_recent_commit(&list, SEEN);
	208	struct object *obj = &commit->object;
	209
337cb3fb	210	if (obj->flags & UNINTERESTING) {
3b42a63c LT	211	mark_parents_uninteresting(commit);
	212	if (everybody_uninteresting(list))
	213	break;
	214	continue;
	215	}
	216	p = &commit_list_insert(commit, p)->next;
	217	} while (list);
8b3a1e05 LT	218	if (bisect_list)
8b3a1e05 LT	219	newlist = find_bisection(newlist);
3b42a63c LT	220	return newlist;
	221	}
	222
000182ea LT	223	static enum cmit_fmt get_commit_format(const char *arg)
	224	{
	225	if (!*arg)
	226	return CMIT_FMT_DEFAULT;
	227	if (!strcmp(arg, "=raw"))
	228	return CMIT_FMT_RAW;
	229	if (!strcmp(arg, "=medium"))
	230	return CMIT_FMT_MEDIUM;
	231	if (!strcmp(arg, "=short"))
	232	return CMIT_FMT_SHORT;
	233	usage(rev_list_usage);
	234	}
	235
	236
64745109 LT	237	int main(int argc, char **argv)
64745109 LT	238	{
64745109	239	struct commit_list *list = NULL;
337cb3fb	240	int i, limited = 0;
64745109	241
fcfda02b	242	for (i = 1 ; i < argc; i++) {
337cb3fb	243	int flags;
fcfda02b	244	char *arg = argv[i];
337cb3fb LT	245	unsigned char sha1[20];
337cb3fb LT	246	struct commit *commit;
fcfda02b KS	247
	248	if (!strncmp(arg, "--max-count=", 12)) {
	249	max_count = atoi(arg + 12);
a6f68d47 LT	250	continue;
	251	}
	252	if (!strncmp(arg, "--max-age=", 10)) {
fcfda02b	253	max_age = atoi(arg + 10);
a6f68d47 LT	254	continue;
	255	}
	256	if (!strncmp(arg, "--min-age=", 10)) {
fcfda02b	257	min_age = atoi(arg + 10);
a6f68d47	258	continue;
fcfda02b	259	}
a6f68d47 LT	260	if (!strcmp(arg, "--header")) {
	261	verbose_header = 1;
	262	continue;
	263	}
000182ea LT	264	if (!strncmp(arg, "--pretty", 8)) {
000182ea LT	265	commit_format = get_commit_format(arg+8);
9d97aa64	266	verbose_header = 1;
9d97aa64 LT	267	hdr_termination = '\n';
	268	prefix = "commit ";
	269	continue;
	270	}
97658004 LT	271	if (!strcmp(arg, "--parents")) {
	272	show_parents = 1;
	273	continue;
	274	}
8b3a1e05 LT	275	if (!strcmp(arg, "--bisect")) {
	276	bisect_list = 1;
	277	continue;
	278	}
a3437b8c JS	279	if (!strncmp(arg, "--merge-order", 13)) {
	280	merge_order = 1;
	281	continue;
	282	}
	283	if (!strncmp(arg, "--show-breaks", 13)) {
	284	show_breaks = 1;
	285	continue;
	286	}
a6f68d47	287
337cb3fb LT	288	flags = 0;
	289	if (*arg == '^') {
	290	flags = UNINTERESTING;
	291	arg++;
	292	limited = 1;
	293	}
a3437b8c	294	if (get_sha1(arg, sha1) \|\| (show_breaks && !merge_order))
a6f68d47	295	usage(rev_list_usage);
337cb3fb LT	296	commit = lookup_commit_reference(sha1);
	297	if (!commit \|\| parse_commit(commit) < 0)
	298	die("bad commit object %s", arg);
	299	commit->object.flags \|= flags;
	300	commit_list_insert(commit, &list);
fcfda02b KS	301	}
fcfda02b KS	302
337cb3fb	303	if (!list)
a6f68d47	304	usage(rev_list_usage);
64745109	305
a3437b8c	306	if (!merge_order) {
17ebe977	307	if (limited)
a3437b8c JS	308	list = limit_list(list);
a3437b8c JS	309	show_commit_list(list);
a3437b8c	310	} else {
a3437b8c JS	311	if (sort_list_in_merge_order(list, &process_commit)) {
	312	die("merge order sort failed\n");
	313	}
a3437b8c	314	}
8906300f	315
64745109 LT	316	return 0;
64745109 LT	317	}