[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)

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