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

/*
 * GIT - The information manager from hell
 *
 * Copyright (C) Linus Torvalds, 2005
 */
#include "cache.h"

static int stage = 0;
static int update = 0;

static int unpack_tree(unsigned char *sha1)
{
	void *buffer;
	unsigned long size;
	int ret;

	buffer = read_object_with_reference(sha1, "tree", &size, NULL);
	if (!buffer)
		return -1;
	ret = read_tree(buffer, size, stage);
	free(buffer);
	return ret;
}

static int path_matches(struct cache_entry *a, struct cache_entry *b)
{
	int len = ce_namelen(a);
	return ce_namelen(b) == len &&
		!memcmp(a->name, b->name, len);
}

static int same(struct cache_entry *a, struct cache_entry *b)
{
	return a->ce_mode == b->ce_mode && 
		!memcmp(a->sha1, b->sha1, 20);
}


/*
 * This removes all trivial merges that don't change the tree
 * and collapses them to state 0.
 */
static struct cache_entry *merge_entries(struct cache_entry *a,
					 struct cache_entry *b,
					 struct cache_entry *c)
{
	/*
	 * Ok, all three entries describe the same
	 * filename, but maybe the contents or file
	 * mode have changed?
	 *
	 * The trivial cases end up being the ones where two
	 * out of three files are the same:
	 *  - both destinations the same, trivially take either
	 *  - one of the destination versions hasn't changed,
	 *    take the other.
	 *
	 * The "all entries exactly the same" case falls out as
	 * a special case of any of the "two same" cases.
	 *
	 * Here "a" is "original", and "b" and "c" are the two
	 * trees we are merging.
	 */
	if (a && b && c) {
		if (same(b,c))
			return c;
		if (same(a,b))
			return c;
		if (same(a,c))
			return b;
	}
	return NULL;
}

/*
 * When a CE gets turned into an unmerged entry, we
 * want it to be up-to-date
 */
static void verify_uptodate(struct cache_entry *ce)
{
	struct stat st;

	if (!lstat(ce->name, &st)) {
		unsigned changed = ce_match_stat(ce, &st);
		if (!changed)
			return;
		errno = 0;
	}
	if (errno == ENOENT)
		return;
	die("Entry '%s' not uptodate. Cannot merge.", ce->name);
}

/*
 * If the old tree contained a CE that isn't even in the
 * result, that's always a problem, regardless of whether
 * it's up-to-date or not (ie it can be a file that we
 * have updated but not committed yet).
 */
static void reject_merge(struct cache_entry *ce)
{
	die("Entry '%s' would be overwritten by merge. Cannot merge.", ce->name);
}

static int merged_entry(struct cache_entry *merge, struct cache_entry *old, struct cache_entry **dst)
{
	merge->ce_flags |= htons(CE_UPDATE);
	if (old) {
		/*
		 * See if we can re-use the old CE directly?
		 * That way we get the uptodate stat info.
		 *
		 * This also removes the UPDATE flag on
		 * a match.
		 */
		if (same(old, merge)) {
			*merge = *old;
		} else {
			verify_uptodate(old);
		}
	}
	merge->ce_flags &= ~htons(CE_STAGEMASK);
	*dst++ = merge;
	return 1;
}

static int threeway_merge(struct cache_entry *stages[4], struct cache_entry **dst)
{
	struct cache_entry *old = stages[0];
	struct cache_entry *a = stages[1], *b = stages[2], *c = stages[3];
	struct cache_entry *merge;
	int count;

	/*
	 * If we have an entry in the index cache ("old"), then we want
	 * to make sure that it matches any entries in stage 2 ("first
	 * branch", aka "b").
	 */
	if (old) {
		if (!b || !same(old, b))
			return -1;
	}
	merge = merge_entries(a, b, c);
	if (merge)
		return merged_entry(merge, old, dst);
	if (old)
		verify_uptodate(old);
	count = 0;
	if (a) { *dst++ = a; count++; }
	if (b) { *dst++ = b; count++; }
	if (c) { *dst++ = c; count++; }
	return count;
}

/*
 * Two-way merge.
 *
 * The rule is to "carry forward" what is in the index without losing
 * information across a "fast forward", favoring a successful merge
 * over a merge failure when it makes sense.  For details of the
 * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
 *
 */
static int twoway_merge(struct cache_entry **src, struct cache_entry **dst)
{
	struct cache_entry *current = src[0];
	struct cache_entry *oldtree = src[1], *newtree = src[2];

	if (src[3])
		return -1;

	if (current) {
		if ((!oldtree && !newtree) || /* 4 and 5 */
		    (!oldtree && newtree &&
		     same(current, newtree)) || /* 6 and 7 */
		    (oldtree && newtree &&
		     same(oldtree, newtree)) || /* 14 and 15 */
		    (oldtree && newtree &&
		     !same(oldtree, newtree) && /* 18 and 19*/
		     same(current, newtree))) {
			*dst++ = current;
			return 1;
		}
		else if (oldtree && !newtree && same(current, oldtree)) {
			/* 10 or 11 */
			verify_uptodate(current);
			return 0;
		}
		else if (oldtree && newtree &&
			 same(current, oldtree) && !same(current, newtree)) {
			/* 20 or 21 */
			verify_uptodate(current);
			return merged_entry(newtree, NULL, dst);
		}
		else
			/* all other failures */
			return -1;
	}
	else if (newtree)
		return merged_entry(newtree, NULL, dst);
	else
		return 0;
}

/*
 * One-way merge.
 *
 * The rule is:
 * - take the stat information from stage0, take the data from stage1
 */
static int oneway_merge(struct cache_entry **src, struct cache_entry **dst)
{
	struct cache_entry *old = src[0];
	struct cache_entry *a = src[1];

	if (src[2] || src[3])
		return -1;

	if (!a)
		return 0;
	if (old && same(old, a))
		*a = *old;
	a->ce_flags &= ~htons(CE_STAGEMASK);
	*dst++ = a;
	return 1;
}

static void check_updates(struct cache_entry **src, int nr)
{
	static struct checkout state = {
		.base_dir = "",
		.force = 1,
		.quiet = 1,
		.refresh_cache = 1,
	};
	unsigned short mask = htons(CE_UPDATE);
	while (nr--) {
		struct cache_entry *ce = *src++;
		if (ce->ce_flags & mask) {
			ce->ce_flags &= ~mask;
			if (update)
				checkout_entry(ce, &state);
		}
	}
}

typedef int (*merge_fn_t)(struct cache_entry **, struct cache_entry **);

static void merge_cache(struct cache_entry **src, int nr, merge_fn_t fn)
{
	struct cache_entry **dst = src;

	while (nr) {
		int entries;
		struct cache_entry *name, *ce, *stages[4] = { NULL, };

		name = ce = *src;
		for (;;) {
			int stage = ce_stage(ce);
			stages[stage] = ce;
			ce = *++src;
			active_nr--;
			if (!--nr)
				break;
			if (!path_matches(ce, name))
				break;
		}

		entries = fn(stages, dst);
		if (entries < 0)
			reject_merge(name);
		dst += entries;
		active_nr += entries;
	}
	check_updates(active_cache, active_nr);
}

static char *read_tree_usage = "git-read-tree (<sha> | -m <sha1> [<sha2> [<sha3>]])";

static struct cache_file cache_file;

int main(int argc, char **argv)
{
	int i, newfd, merge;
	unsigned char sha1[20];

	newfd = hold_index_file_for_update(&cache_file, get_index_file());
	if (newfd < 0)
		die("unable to create new cachefile");

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

		/* "-u" means "update", meaning that a merge will update the working directory */
		if (!strcmp(arg, "-u")) {
			update = 1;
			continue;
		}

		/* "-m" stands for "merge", meaning we start in stage 1 */
		if (!strcmp(arg, "-m")) {
			int i;
			if (stage)
				die("-m needs to come first");
			read_cache();
			for (i = 0; i < active_nr; i++) {
				if (ce_stage(active_cache[i]))
					die("you need to resolve your current index first");
			}
			stage = 1;
			merge = 1;
			continue;
		}
		if (get_sha1(arg, sha1) < 0)
			usage(read_tree_usage);
		if (stage > 3)
			usage(read_tree_usage);
		if (unpack_tree(sha1) < 0)
			die("failed to unpack tree object %s", arg);
		stage++;
	}
	if (merge) {
		static const merge_fn_t merge_function[] = {
			[1] = oneway_merge,
			[2] = twoway_merge,
			[3] = threeway_merge,
		};
		if (stage < 2 || stage > 4)
			die("just how do you expect me to merge %d trees?", stage-1);
		merge_cache(active_cache, active_nr, merge_function[stage-1]);
	}
	if (write_cache(newfd, active_cache, active_nr) ||
	    commit_index_file(&cache_file))
		die("unable to write new index file");
	return 0;
}
Commit	Line	Data
8bc9a0c7 LT	1	/*
	2	* GIT - The information manager from hell
	3	*
	4	* Copyright (C) Linus Torvalds, 2005
	5	*/
e83c5163 LT	6	#include "cache.h"
e83c5163 LT	7
d99082e0	8	static int stage = 0;
220a0b52	9	static int update = 0;
d99082e0	10
94537c78	11	static int unpack_tree(unsigned char *sha1)
b12ec373 JH	12	{
	13	void *buffer;
	14	unsigned long size;
14242464	15	int ret;
b12ec373	16
e99d59ff	17	buffer = read_object_with_reference(sha1, "tree", &size, NULL);
aba06682 LT	18	if (!buffer)
aba06682 LT	19	return -1;
14242464 PB	20	ret = read_tree(buffer, size, stage);
	21	free(buffer);
	22	return ret;
b12ec373 JH	23	}
b12ec373 JH	24
ca016f0e LT	25	static int path_matches(struct cache_entry a, struct cache_entry b)
	26	{
	27	int len = ce_namelen(a);
	28	return ce_namelen(b) == len &&
	29	!memcmp(a->name, b->name, len);
	30	}
	31
43f91266 LT	32	static int same(struct cache_entry a, struct cache_entry b)
	33	{
	34	return a->ce_mode == b->ce_mode &&
	35	!memcmp(a->sha1, b->sha1, 20);
	36	}
	37
	38
d99082e0	39	/*
43f91266 LT	40	* This removes all trivial merges that don't change the tree
43f91266 LT	41	* and collapses them to state 0.
d99082e0	42	*/
43f91266 LT	43	static struct cache_entry merge_entries(struct cache_entry a,
	44	struct cache_entry *b,
	45	struct cache_entry *c)
d99082e0	46	{
43f91266 LT	47	/*
	48	* Ok, all three entries describe the same
	49	* filename, but maybe the contents or file
	50	* mode have changed?
	51	*
	52	* The trivial cases end up being the ones where two
	53	* out of three files are the same:
	54	* - both destinations the same, trivially take either
	55	* - one of the destination versions hasn't changed,
	56	* take the other.
	57	*
	58	* The "all entries exactly the same" case falls out as
	59	* a special case of any of the "two same" cases.
	60	*
	61	* Here "a" is "original", and "b" and "c" are the two
	62	* trees we are merging.
	63	*/
d723c690 LT	64	if (a && b && c) {
	65	if (same(b,c))
	66	return c;
	67	if (same(a,b))
	68	return c;
	69	if (same(a,c))
	70	return b;
	71	}
43f91266	72	return NULL;
d99082e0 LT	73	}
d99082e0 LT	74
02ede67a LT	75	/*
	76	* When a CE gets turned into an unmerged entry, we
	77	* want it to be up-to-date
	78	*/
	79	static void verify_uptodate(struct cache_entry *ce)
	80	{
	81	struct stat st;
	82
	83	if (!lstat(ce->name, &st)) {
	84	unsigned changed = ce_match_stat(ce, &st);
	85	if (!changed)
	86	return;
	87	errno = 0;
	88	}
	89	if (errno == ENOENT)
	90	return;
	91	die("Entry '%s' not uptodate. Cannot merge.", ce->name);
	92	}
	93
	94	/*
	95	* If the old tree contained a CE that isn't even in the
	96	* result, that's always a problem, regardless of whether
	97	* it's up-to-date or not (ie it can be a file that we
	98	* have updated but not committed yet).
	99	*/
76f38347	100	static void reject_merge(struct cache_entry *ce)
02ede67a	101	{
76f38347	102	die("Entry '%s' would be overwritten by merge. Cannot merge.", ce->name);
02ede67a LT	103	}
02ede67a LT	104
d723c690	105	static int merged_entry(struct cache_entry merge, struct cache_entry old, struct cache_entry **dst)
d99082e0	106	{
d723c690 LT	107	merge->ce_flags \|= htons(CE_UPDATE);
d723c690 LT	108	if (old) {
02ede67a	109	/*
d723c690 LT	110	* See if we can re-use the old CE directly?
	111	* That way we get the uptodate stat info.
	112	*
	113	* This also removes the UPDATE flag on
	114	* a match.
02ede67a	115	*/
d723c690 LT	116	if (same(old, merge)) {
	117	merge = old;
	118	} else {
	119	verify_uptodate(old);
	120	}
a3a65234	121	}
d723c690 LT	122	merge->ce_flags &= ~htons(CE_STAGEMASK);
	123	*dst++ = merge;
	124	return 1;
a3a65234 LT	125	}
a3a65234 LT	126
d723c690	127	static int threeway_merge(struct cache_entry stages[4], struct cache_entry *dst)
e6ee623b	128	{
d723c690 LT	129	struct cache_entry *old = stages[0];
	130	struct cache_entry a = stages[1], b = stages[2], *c = stages[3];
	131	struct cache_entry *merge;
	132	int count;
	133
	134	/*
	135	* If we have an entry in the index cache ("old"), then we want
	136	* to make sure that it matches any entries in stage 2 ("first
	137	* branch", aka "b").
	138	*/
	139	if (old) {
	140	if (!b \|\| !same(old, b))
	141	return -1;
e6ee623b	142	}
d723c690 LT	143	merge = merge_entries(a, b, c);
	144	if (merge)
	145	return merged_entry(merge, old, dst);
	146	if (old)
	147	verify_uptodate(old);
	148	count = 0;
	149	if (a) { *dst++ = a; count++; }
	150	if (b) { *dst++ = b; count++; }
	151	if (c) { *dst++ = c; count++; }
	152	return count;
e6ee623b LT	153	}
e6ee623b LT	154
220a0b52 LT	155	/*
	156	* Two-way merge.
	157	*
c8596009 JH	158	* The rule is to "carry forward" what is in the index without losing
	159	* information across a "fast forward", favoring a successful merge
	160	* over a merge failure when it makes sense. For details of the
	161	* "carry forward" rule, please see <Documentation/git-read-tree.txt>.
	162	*
220a0b52	163	*/
d723c690	164	static int twoway_merge(struct cache_entry src, struct cache_entry dst)
a3a65234	165	{
c8596009 JH	166	struct cache_entry *current = src[0];
c8596009 JH	167	struct cache_entry oldtree = src[1], newtree = src[2];
220a0b52	168
d723c690 LT	169	if (src[3])
d723c690 LT	170	return -1;
e6ee623b	171
c8596009 JH	172	if (current) {
	173	if ((!oldtree && !newtree) \|\| /* 4 and 5 */
	174	(!oldtree && newtree &&
	175	same(current, newtree)) \|\| /* 6 and 7 */
	176	(oldtree && newtree &&
	177	same(oldtree, newtree)) \|\| /* 14 and 15 */
	178	(oldtree && newtree &&
	179	!same(oldtree, newtree) && /* 18 and 19*/
	180	same(current, newtree))) {
	181	*dst++ = current;
	182	return 1;
	183	}
	184	else if (oldtree && !newtree && same(current, oldtree)) {
	185	/* 10 or 11 */
	186	verify_uptodate(current);
	187	return 0;
	188	}
	189	else if (oldtree && newtree &&
	190	same(current, oldtree) && !same(current, newtree)) {
	191	/* 20 or 21 */
	192	verify_uptodate(current);
	193	return merged_entry(newtree, NULL, dst);
	194	}
	195	else
	196	/* all other failures */
d723c690	197	return -1;
e6ee623b	198	}
c8596009 JH	199	else if (newtree)
	200	return merged_entry(newtree, NULL, dst);
	201	else
	202	return 0;
220a0b52 LT	203	}
220a0b52 LT	204
d723c690 LT	205	/*
	206	* One-way merge.
	207	*
	208	* The rule is:
	209	* - take the stat information from stage0, take the data from stage1
	210	*/
	211	static int oneway_merge(struct cache_entry src, struct cache_entry dst)
220a0b52	212	{
d723c690 LT	213	struct cache_entry *old = src[0];
d723c690 LT	214	struct cache_entry *a = src[1];
a3a65234	215
d723c690 LT	216	if (src[2] \|\| src[3])
d723c690 LT	217	return -1;
a3a65234	218
d723c690 LT	219	if (!a)
	220	return 0;
	221	if (old && same(old, a))
	222	a = old;
	223	a->ce_flags &= ~htons(CE_STAGEMASK);
	224	*dst++ = a;
	225	return 1;
d99082e0 LT	226	}
d99082e0 LT	227
220a0b52 LT	228	static void check_updates(struct cache_entry **src, int nr)
	229	{
	230	static struct checkout state = {
	231	.base_dir = "",
	232	.force = 1,
	233	.quiet = 1,
	234	.refresh_cache = 1,
	235	};
	236	unsigned short mask = htons(CE_UPDATE);
	237	while (nr--) {
	238	struct cache_entry ce = src++;
	239	if (ce->ce_flags & mask) {
	240	ce->ce_flags &= ~mask;
	241	if (update)
	242	checkout_entry(ce, &state);
	243	}
	244	}
	245	}
	246
45132251 LT	247	typedef int (merge_fn_t)(struct cache_entry , struct cache_entry *);
	248
	249	static void merge_cache(struct cache_entry **src, int nr, merge_fn_t fn)
d723c690 LT	250	{
	251	struct cache_entry **dst = src;
	252
	253	while (nr) {
	254	int entries;
	255	struct cache_entry name, ce, *stages[4] = { NULL, };
	256
	257	name = ce = *src;
	258	for (;;) {
	259	int stage = ce_stage(ce);
	260	stages[stage] = ce;
	261	ce = *++src;
	262	active_nr--;
	263	if (!--nr)
	264	break;
	265	if (!path_matches(ce, name))
	266	break;
	267	}
	268
	269	entries = fn(stages, dst);
	270	if (entries < 0)
	271	reject_merge(name);
	272	dst += entries;
	273	active_nr += entries;
	274	}
	275	check_updates(active_cache, active_nr);
	276	}
	277
220a0b52	278	static char *read_tree_usage = "git-read-tree (<sha> \| -m <sha1> [<sha2> [<sha3>]])";
c5bac17a	279
96cd5429 JH	280	static struct cache_file cache_file;
96cd5429 JH	281
e83c5163 LT	282	int main(int argc, char **argv)
e83c5163 LT	283	{
ca016f0e	284	int i, newfd, merge;
e83c5163	285	unsigned char sha1[20];
bb233d69	286
96cd5429	287	newfd = hold_index_file_for_update(&cache_file, get_index_file());
83adac3c	288	if (newfd < 0)
2de381f9	289	die("unable to create new cachefile");
83adac3c	290
ca016f0e	291	merge = 0;
83adac3c LT	292	for (i = 1; i < argc; i++) {
	293	const char *arg = argv[i];
	294
220a0b52 LT	295	/* "-u" means "update", meaning that a merge will update the working directory */
	296	if (!strcmp(arg, "-u")) {
	297	update = 1;
	298	continue;
	299	}
	300
d99082e0	301	/* "-m" stands for "merge", meaning we start in stage 1 */
83adac3c	302	if (!strcmp(arg, "-m")) {
ca016f0e LT	303	int i;
ca016f0e LT	304	if (stage)
c5bac17a	305	die("-m needs to come first");
ca016f0e LT	306	read_cache();
	307	for (i = 0; i < active_nr; i++) {
	308	if (ce_stage(active_cache[i]))
c5bac17a	309	die("you need to resolve your current index first");
ca016f0e	310	}
d99082e0	311	stage = 1;
ca016f0e	312	merge = 1;
83adac3c LT	313	continue;
83adac3c LT	314	}
3c249c95	315	if (get_sha1(arg, sha1) < 0)
c5bac17a	316	usage(read_tree_usage);
d99082e0	317	if (stage > 3)
c5bac17a	318	usage(read_tree_usage);
94537c78	319	if (unpack_tree(sha1) < 0)
2de381f9	320	die("failed to unpack tree object %s", arg);
d99082e0	321	stage++;
83adac3c	322	}
ca016f0e	323	if (merge) {
45132251 LT	324	static const merge_fn_t merge_function[] = {
	325	[1] = oneway_merge,
	326	[2] = twoway_merge,
	327	[3] = threeway_merge,
	328	};
	329	if (stage < 2 \|\| stage > 4)
a3a65234	330	die("just how do you expect me to merge %d trees?", stage-1);
45132251	331	merge_cache(active_cache, active_nr, merge_function[stage-1]);
ca016f0e	332	}
96cd5429 JH	333	if (write_cache(newfd, active_cache, active_nr) \|\|
96cd5429 JH	334	commit_index_file(&cache_file))
2de381f9	335	die("unable to write new index file");
9614b8dc	336	return 0;
e83c5163	337	}