[thirdparty/git.git] / diff-tree.c

#include "cache.h"

static int recursive = 0;
static int line_termination = '\n';

// What paths are we interested in?
static int nr_paths = 0;
static char **paths = NULL;
static int *pathlens = NULL;

static int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base);

static void update_tree_entry(void **bufp, unsigned long *sizep)
{
	void *buf = *bufp;
	unsigned long size = *sizep;
	int len = strlen(buf) + 1 + 20;

	if (size < len)
		die("corrupt tree file");
	*bufp = buf + len;
	*sizep = size - len;
}

static const unsigned char *extract(void *tree, unsigned long size, const char **pathp, unsigned int *modep)
{
	int len = strlen(tree)+1;
	const unsigned char *sha1 = tree + len;
	const char *path = strchr(tree, ' ');

	if (!path || size < len + 20 || sscanf(tree, "%o", modep) != 1)
		die("corrupt tree file");
	*pathp = path+1;
	return sha1;
}

static char *malloc_base(const char *base, const char *path, int pathlen)
{
	int baselen = strlen(base);
	char *newbase = xmalloc(baselen + pathlen + 2);
	memcpy(newbase, base, baselen);
	memcpy(newbase + baselen, path, pathlen);
	memcpy(newbase + baselen + pathlen, "/", 2);
	return newbase;
}

static void show_file(const char *prefix, void *tree, unsigned long size, const char *base);

/* A whole sub-tree went away or appeared */
static void show_tree(const char *prefix, void *tree, unsigned long size, const char *base)
{
	while (size) {
		show_file(prefix, tree, size, base);
		update_tree_entry(&tree, &size);
	}
}

/* A file entry went away or appeared */
static void show_file(const char *prefix, void *tree, unsigned long size, const char *base)
{
	unsigned mode;
	const char *path;
	const unsigned char *sha1 = extract(tree, size, &path, &mode);

	if (recursive && S_ISDIR(mode)) {
		char type[20];
		unsigned long size;
		char *newbase = malloc_base(base, path, strlen(path));
		void *tree;

		tree = read_sha1_file(sha1, type, &size);
		if (!tree || strcmp(type, "tree"))
			die("corrupt tree sha %s", sha1_to_hex(sha1));

		show_tree(prefix, tree, size, newbase);
		
		free(tree);
		free(newbase);
		return;
	}

	printf("%s%o\t%s\t%s\t%s%s%c", prefix, mode,
	       S_ISDIR(mode) ? "tree" : "blob",
	       sha1_to_hex(sha1), base, path,
	       line_termination);
}

static int compare_tree_entry(void *tree1, unsigned long size1, void *tree2, unsigned long size2, const char *base)
{
	unsigned mode1, mode2;
	const char *path1, *path2;
	const unsigned char *sha1, *sha2;
	int cmp, pathlen1, pathlen2;
	char old_sha1_hex[50];

	sha1 = extract(tree1, size1, &path1, &mode1);
	sha2 = extract(tree2, size2, &path2, &mode2);

	pathlen1 = strlen(path1);
	pathlen2 = strlen(path2);
	cmp = cache_name_compare(path1, pathlen1, path2, pathlen2);
	if (cmp < 0) {
		show_file("-", tree1, size1, base);
		return -1;
	}
	if (cmp > 0) {
		show_file("+", tree2, size2, base);
		return 1;
	}
	if (!memcmp(sha1, sha2, 20) && mode1 == mode2)
		return 0;

	/*
	 * If the filemode has changed to/from a directory from/to a regular
	 * file, we need to consider it a remove and an add.
	 */
	if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
		show_file("-", tree1, size1, base);
		show_file("+", tree2, size2, base);
		return 0;
	}

	if (recursive && S_ISDIR(mode1)) {
		int retval;
		char *newbase = malloc_base(base, path1, pathlen1);
		retval = diff_tree_sha1(sha1, sha2, newbase);
		free(newbase);
		return retval;
	}

	strcpy(old_sha1_hex, sha1_to_hex(sha1));
	printf("*%o->%o\t%s\t%s->%s\t%s%s%c", mode1, mode2,
	       S_ISDIR(mode1) ? "tree" : "blob",
	       old_sha1_hex, sha1_to_hex(sha2), base, path1,
	       line_termination);
	return 0;
}

static int interesting(void *tree, unsigned long size, const char *base)
{
	const char *path;
	unsigned mode;
	int i;
	int baselen, pathlen;

	if (!nr_paths)
		return 1;

	(void)extract(tree, size, &path, &mode);

	pathlen = strlen(path);
	baselen = strlen(base);

	for (i=0; i < nr_paths; i++) {
		const char *match = paths[i];
		int matchlen = pathlens[i];

		if (baselen >= matchlen) {
			/* If it doesn't match, move along... */
			if (strncmp(base, match, matchlen))
				continue;

			/* The base is a subdirectory of a path which was specified. */
			return 1;
		}

		/* Does the base match? */
		if (strncmp(base, match, baselen))
			continue;

		match += baselen;
		matchlen -= baselen;

		if (pathlen > matchlen)
			continue;

		if (strncmp(path, match, pathlen))
			continue;

		return 1;
	}
	return 0; /* No matches */
}

static int diff_tree(void *tree1, unsigned long size1, void *tree2, unsigned long size2, const char *base)
{
	while (size1 | size2) {
		if (nr_paths && size1 && !interesting(tree1, size1, base)) {
			update_tree_entry(&tree1, &size1);
			continue;
		}
		if (nr_paths && size2 && !interesting(tree2, size2, base)) {
			update_tree_entry(&tree2, &size2);
			continue;
		}
		if (!size1) {
			show_file("+", tree2, size2, base);
			update_tree_entry(&tree2, &size2);
			continue;
		}
		if (!size2) {
			show_file("-", tree1, size1, base);
			update_tree_entry(&tree1, &size1);
			continue;
		}
		switch (compare_tree_entry(tree1, size1, tree2, size2, base)) {
		case -1:
			update_tree_entry(&tree1, &size1);
			continue;
		case 0:
			update_tree_entry(&tree1, &size1);
			/* Fallthrough */
		case 1:
			update_tree_entry(&tree2, &size2);
			continue;
		}
		die("diff-tree: internal error");
	}
	return 0;
}

static int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base)
{
	void *tree1, *tree2;
	unsigned long size1, size2;
	int retval;

	tree1 = read_tree_with_tree_or_commit_sha1(old, &size1, 0);
	if (!tree1)
		die("unable to read source tree (%s)", sha1_to_hex(old));
	tree2 = read_tree_with_tree_or_commit_sha1(new, &size2, 0);
	if (!tree2)
		die("unable to read destination tree (%s)", sha1_to_hex(new));
	retval = diff_tree(tree1, size1, tree2, size2, base);
	free(tree1);
	free(tree2);
	return retval;
}

static char *diff_tree_usage = "diff-tree [-r] [-z] <tree sha1> <tree sha1>";

int main(int argc, char **argv)
{
	unsigned char old[20], new[20];

	for (;;) {
		char *arg = argv[1];

		if (!arg || *arg != '-')
			break;

		argv++;
		argc--;
		if (!strcmp(arg, "-r")) {
			recursive = 1;
			continue;
		}
		if (!strcmp(arg, "-z")) {
			line_termination = '\0';
			continue;
		}
		usage(diff_tree_usage);
	}

	if (argc < 3 || get_sha1_hex(argv[1], old) || get_sha1_hex(argv[2], new))
		usage(diff_tree_usage);

	if (argc > 3) {
		int i;

		paths = &argv[3];
		nr_paths = argc - 3;
		pathlens = xmalloc(nr_paths * sizeof(int));
		for (i=0; i<nr_paths; i++)
			pathlens[i] = strlen(paths[i]);
	}

	return diff_tree_sha1(old, new, "");
}
Commit	Line	Data
9174026c LT	1	#include "cache.h"
9174026c LT	2
73134b6d	3	static int recursive = 0;
6cbd72f8	4	static int line_termination = '\n';
9174026c	5
c5b42386 LT	6	// What paths are we interested in?
	7	static int nr_paths = 0;
	8	static char **paths = NULL;
	9	static int *pathlens = NULL;
	10
eeb79916	11	static int diff_tree_sha1(const unsigned char old, const unsigned char new, const char *base);
73134b6d LT	12
73134b6d LT	13	static void update_tree_entry(void *bufp, unsigned long sizep)
9174026c LT	14	{
	15	void buf = bufp;
	16	unsigned long size = *sizep;
	17	int len = strlen(buf) + 1 + 20;
	18
	19	if (size < len)
2de381f9	20	die("corrupt tree file");
9174026c LT	21	*bufp = buf + len;
9174026c LT	22	*sizep = size - len;
9174026c LT	23	}
	24
	25	static const unsigned char extract(void tree, unsigned long size, const char *pathp, unsigned int modep)
	26	{
	27	int len = strlen(tree)+1;
	28	const unsigned char *sha1 = tree + len;
	29	const char *path = strchr(tree, ' ');
	30
	31	if (!path \|\| size < len + 20 \|\| sscanf(tree, "%o", modep) != 1)
2de381f9	32	die("corrupt tree file");
9174026c LT	33	*pathp = path+1;
	34	return sha1;
	35	}
	36
262e82b4 LT	37	static char malloc_base(const char base, const char *path, int pathlen)
	38	{
	39	int baselen = strlen(base);
812666c8	40	char *newbase = xmalloc(baselen + pathlen + 2);
262e82b4 LT	41	memcpy(newbase, base, baselen);
	42	memcpy(newbase + baselen, path, pathlen);
	43	memcpy(newbase + baselen + pathlen, "/", 2);
	44	return newbase;
	45	}
	46
	47	static void show_file(const char prefix, void tree, unsigned long size, const char *base);
	48
	49	/* A whole sub-tree went away or appeared */
	50	static void show_tree(const char prefix, void tree, unsigned long size, const char *base)
	51	{
	52	while (size) {
	53	show_file(prefix, tree, size, base);
	54	update_tree_entry(&tree, &size);
	55	}
	56	}
	57
	58	/* A file entry went away or appeared */
73134b6d	59	static void show_file(const char prefix, void tree, unsigned long size, const char *base)
9174026c LT	60	{
	61	unsigned mode;
	62	const char *path;
	63	const unsigned char *sha1 = extract(tree, size, &path, &mode);
262e82b4 LT	64
	65	if (recursive && S_ISDIR(mode)) {
	66	char type[20];
	67	unsigned long size;
	68	char *newbase = malloc_base(base, path, strlen(path));
	69	void *tree;
	70
	71	tree = read_sha1_file(sha1, type, &size);
	72	if (!tree \|\| strcmp(type, "tree"))
2de381f9	73	die("corrupt tree sha %s", sha1_to_hex(sha1));
262e82b4 LT	74
	75	show_tree(prefix, tree, size, newbase);
	76
	77	free(tree);
	78	free(newbase);
	79	return;
	80	}
	81
33b238d1 PB	82	printf("%s%o\t%s\t%s\t%s%s%c", prefix, mode,
33b238d1 PB	83	S_ISDIR(mode) ? "tree" : "blob",
6cbd72f8 LT	84	sha1_to_hex(sha1), base, path,
6cbd72f8 LT	85	line_termination);
9174026c LT	86	}
9174026c LT	87
eeb79916	88	static int compare_tree_entry(void tree1, unsigned long size1, void tree2, unsigned long size2, const char *base)
9174026c LT	89	{
	90	unsigned mode1, mode2;
	91	const char path1, path2;
	92	const unsigned char sha1, sha2;
73134b6d	93	int cmp, pathlen1, pathlen2;
eeb79916	94	char old_sha1_hex[50];
9174026c LT	95
	96	sha1 = extract(tree1, size1, &path1, &mode1);
	97	sha2 = extract(tree2, size2, &path2, &mode2);
	98
73134b6d LT	99	pathlen1 = strlen(path1);
	100	pathlen2 = strlen(path2);
	101	cmp = cache_name_compare(path1, pathlen1, path2, pathlen2);
9174026c	102	if (cmp < 0) {
eeb79916	103	show_file("-", tree1, size1, base);
9174026c LT	104	return -1;
	105	}
	106	if (cmp > 0) {
eeb79916	107	show_file("+", tree2, size2, base);
9174026c LT	108	return 1;
	109	}
	110	if (!memcmp(sha1, sha2, 20) && mode1 == mode2)
	111	return 0;
262e82b4 LT	112
	113	/*
	114	* If the filemode has changed to/from a directory from/to a regular
aebb2679	115	* file, we need to consider it a remove and an add.
262e82b4 LT	116	*/
	117	if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
	118	show_file("-", tree1, size1, base);
	119	show_file("+", tree2, size2, base);
	120	return 0;
	121	}
	122
	123	if (recursive && S_ISDIR(mode1)) {
eeb79916	124	int retval;
262e82b4	125	char *newbase = malloc_base(base, path1, pathlen1);
eeb79916 LT	126	retval = diff_tree_sha1(sha1, sha2, newbase);
	127	free(newbase);
	128	return retval;
73134b6d LT	129	}
73134b6d LT	130
eeb79916	131	strcpy(old_sha1_hex, sha1_to_hex(sha1));
33b238d1 PB	132	printf("*%o->%o\t%s\t%s->%s\t%s%s%c", mode1, mode2,
33b238d1 PB	133	S_ISDIR(mode1) ? "tree" : "blob",
6cbd72f8 LT	134	old_sha1_hex, sha1_to_hex(sha2), base, path1,
6cbd72f8 LT	135	line_termination);
9174026c LT	136	return 0;
	137	}
	138
c5b42386 LT	139	static int interesting(void tree, unsigned long size, const char base)
	140	{
	141	const char *path;
	142	unsigned mode;
	143	int i;
	144	int baselen, pathlen;
	145
	146	if (!nr_paths)
	147	return 1;
	148
	149	(void)extract(tree, size, &path, &mode);
	150
	151	pathlen = strlen(path);
	152	baselen = strlen(base);
	153
	154	for (i=0; i < nr_paths; i++) {
	155	const char *match = paths[i];
	156	int matchlen = pathlens[i];
	157
	158	if (baselen >= matchlen) {
	159	/* If it doesn't match, move along... */
	160	if (strncmp(base, match, matchlen))
	161	continue;
	162
	163	/* The base is a subdirectory of a path which was specified. */
	164	return 1;
	165	}
	166
	167	/* Does the base match? */
	168	if (strncmp(base, match, baselen))
	169	continue;
	170
	171	match += baselen;
	172	matchlen -= baselen;
	173
	174	if (pathlen > matchlen)
	175	continue;
	176
	177	if (strncmp(path, match, pathlen))
	178	continue;
	179
	180	return 1;
	181	}
	182	return 0; /* No matches */
	183	}
	184
eeb79916	185	static int diff_tree(void tree1, unsigned long size1, void tree2, unsigned long size2, const char *base)
9174026c LT	186	{
9174026c LT	187	while (size1 \| size2) {
c5b42386 LT	188	if (nr_paths && size1 && !interesting(tree1, size1, base)) {
	189	update_tree_entry(&tree1, &size1);
	190	continue;
	191	}
	192	if (nr_paths && size2 && !interesting(tree2, size2, base)) {
	193	update_tree_entry(&tree2, &size2);
	194	continue;
	195	}
9174026c	196	if (!size1) {
eeb79916	197	show_file("+", tree2, size2, base);
9174026c LT	198	update_tree_entry(&tree2, &size2);
	199	continue;
	200	}
	201	if (!size2) {
eeb79916	202	show_file("-", tree1, size1, base);
9174026c LT	203	update_tree_entry(&tree1, &size1);
	204	continue;
	205	}
eeb79916	206	switch (compare_tree_entry(tree1, size1, tree2, size2, base)) {
9174026c LT	207	case -1:
	208	update_tree_entry(&tree1, &size1);
	209	continue;
	210	case 0:
	211	update_tree_entry(&tree1, &size1);
	212	/* Fallthrough */
	213	case 1:
	214	update_tree_entry(&tree2, &size2);
	215	continue;
	216	}
2de381f9	217	die("diff-tree: internal error");
9174026c LT	218	}
	219	return 0;
	220	}
	221
eeb79916	222	static int diff_tree_sha1(const unsigned char old, const unsigned char new, const char *base)
9174026c	223	{
9174026c LT	224	void tree1, tree2;
9174026c LT	225	unsigned long size1, size2;
73134b6d	226	int retval;
9174026c	227
c1fdf2a6 JH	228	tree1 = read_tree_with_tree_or_commit_sha1(old, &size1, 0);
c1fdf2a6 JH	229	if (!tree1)
2de381f9	230	die("unable to read source tree (%s)", sha1_to_hex(old));
c1fdf2a6 JH	231	tree2 = read_tree_with_tree_or_commit_sha1(new, &size2, 0);
c1fdf2a6 JH	232	if (!tree2)
2de381f9	233	die("unable to read destination tree (%s)", sha1_to_hex(new));
eeb79916	234	retval = diff_tree(tree1, size1, tree2, size2, base);
73134b6d LT	235	free(tree1);
	236	free(tree2);
	237	return retval;
	238	}
	239
c5bac17a JH	240	static char *diff_tree_usage = "diff-tree [-r] [-z] <tree sha1> <tree sha1>";
c5bac17a JH	241
73134b6d LT	242	int main(int argc, char **argv)
	243	{
	244	unsigned char old[20], new[20];
	245
c5b42386	246	for (;;) {
73134b6d	247	char *arg = argv[1];
c5b42386 LT	248
	249	if (!arg \|\| *arg != '-')
	250	break;
	251
73134b6d LT	252	argv++;
73134b6d LT	253	argc--;
bf16c71e	254	if (!strcmp(arg, "-r")) {
73134b6d LT	255	recursive = 1;
	256	continue;
	257	}
6cbd72f8 LT	258	if (!strcmp(arg, "-z")) {
	259	line_termination = '\0';
	260	continue;
	261	}
c5bac17a	262	usage(diff_tree_usage);
73134b6d LT	263	}
73134b6d LT	264
c5b42386	265	if (argc < 3 \|\| get_sha1_hex(argv[1], old) \|\| get_sha1_hex(argv[2], new))
c5bac17a	266	usage(diff_tree_usage);
c5b42386 LT	267
	268	if (argc > 3) {
	269	int i;
	270
	271	paths = &argv[3];
	272	nr_paths = argc - 3;
812666c8	273	pathlens = xmalloc(nr_paths * sizeof(int));
c5b42386 LT	274	for (i=0; i<nr_paths; i++)
	275	pathlens[i] = strlen(paths[i]);
	276	}
	277
eeb79916	278	return diff_tree_sha1(old, new, "");
9174026c	279	}