[thirdparty/git.git] / tree.c

#include "cache.h"
#include "cache-tree.h"
#include "tree.h"
#include "blob.h"
#include "commit.h"
#include "tag.h"
#include "tree-walk.h"

const char *tree_type = "tree";

static int read_one_entry_opt(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage, int opt)
{
	int len;
	unsigned int size;
	struct cache_entry *ce;

	if (S_ISDIR(mode))
		return READ_TREE_RECURSIVE;

	len = strlen(pathname);
	size = cache_entry_size(baselen + len);
	ce = xcalloc(1, size);

	ce->ce_mode = create_ce_mode(mode);
	ce->ce_flags = create_ce_flags(baselen + len, stage);
	memcpy(ce->name, base, baselen);
	memcpy(ce->name + baselen, pathname, len+1);
	hashcpy(ce->sha1, sha1);
	return add_cache_entry(ce, opt);
}

static int read_one_entry(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage, void *context)
{
	return read_one_entry_opt(sha1, base, baselen, pathname, mode, stage,
				  ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);
}

/*
 * This is used when the caller knows there is no existing entries at
 * the stage that will conflict with the entry being added.
 */
static int read_one_entry_quick(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage, void *context)
{
	return read_one_entry_opt(sha1, base, baselen, pathname, mode, stage,
				  ADD_CACHE_JUST_APPEND);
}

static int match_tree_entry(const char *base, int baselen, const char *path, unsigned int mode, const char **paths)
{
	const char *match;
	int pathlen;

	if (!paths)
		return 1;
	pathlen = strlen(path);
	while ((match = *paths++) != NULL) {
		int matchlen = strlen(match);

		if (baselen >= matchlen) {
			/* If it doesn't match, move along... */
			if (strncmp(base, match, matchlen))
				continue;
			/* pathspecs match only at the directory boundaries */
			if (!matchlen ||
			    baselen == matchlen ||
			    base[matchlen] == '/' ||
			    match[matchlen - 1] == '/')
				return 1;
			continue;
		}

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

		match += baselen;
		matchlen -= baselen;

		if (pathlen > matchlen)
			continue;

		if (matchlen > pathlen) {
			if (match[pathlen] != '/')
				continue;
			if (!S_ISDIR(mode))
				continue;
		}

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

		return 1;
	}
	return 0;
}

int read_tree_recursive(struct tree *tree,
			const char *base, int baselen,
			int stage, const char **match,
			read_tree_fn_t fn, void *context)
{
	struct tree_desc desc;
	struct name_entry entry;

	if (parse_tree(tree))
		return -1;

	init_tree_desc(&desc, tree->buffer, tree->size);

	while (tree_entry(&desc, &entry)) {
		if (!match_tree_entry(base, baselen, entry.path, entry.mode, match))
			continue;

		switch (fn(entry.sha1, base, baselen, entry.path, entry.mode, stage, context)) {
		case 0:
			continue;
		case READ_TREE_RECURSIVE:
			break;
		default:
			return -1;
		}
		if (S_ISDIR(entry.mode)) {
			int retval;
			char *newbase;
			unsigned int pathlen = tree_entry_len(entry.path, entry.sha1);

			newbase = xmalloc(baselen + 1 + pathlen);
			memcpy(newbase, base, baselen);
			memcpy(newbase + baselen, entry.path, pathlen);
			newbase[baselen + pathlen] = '/';
			retval = read_tree_recursive(lookup_tree(entry.sha1),
						     newbase,
						     baselen + pathlen + 1,
						     stage, match, fn, context);
			free(newbase);
			if (retval)
				return -1;
			continue;
		} else if (S_ISGITLINK(entry.mode)) {
			int retval;
			struct strbuf path;
			unsigned int entrylen;
			struct commit *commit;

			entrylen = tree_entry_len(entry.path, entry.sha1);
			strbuf_init(&path, baselen + entrylen + 1);
			strbuf_add(&path, base, baselen);
			strbuf_add(&path, entry.path, entrylen);
			strbuf_addch(&path, '/');

			commit = lookup_commit(entry.sha1);
			if (!commit)
				die("Commit %s in submodule path %s not found",
				    sha1_to_hex(entry.sha1), path.buf);

			if (parse_commit(commit))
				die("Invalid commit %s in submodule path %s",
				    sha1_to_hex(entry.sha1), path.buf);

			retval = read_tree_recursive(commit->tree,
						     path.buf, path.len,
						     stage, match, fn, context);
			strbuf_release(&path);
			if (retval)
				return -1;
			continue;
		}
	}
	return 0;
}

static int cmp_cache_name_compare(const void *a_, const void *b_)
{
	const struct cache_entry *ce1, *ce2;

	ce1 = *((const struct cache_entry **)a_);
	ce2 = *((const struct cache_entry **)b_);
	return cache_name_compare(ce1->name, ce1->ce_flags,
				  ce2->name, ce2->ce_flags);
}

int read_tree(struct tree *tree, int stage, const char **match)
{
	read_tree_fn_t fn = NULL;
	int i, err;

	/*
	 * Currently the only existing callers of this function all
	 * call it with stage=1 and after making sure there is nothing
	 * at that stage; we could always use read_one_entry_quick().
	 *
	 * But when we decide to straighten out git-read-tree not to
	 * use unpack_trees() in some cases, this will probably start
	 * to matter.
	 */

	/*
	 * See if we have cache entry at the stage.  If so,
	 * do it the original slow way, otherwise, append and then
	 * sort at the end.
	 */
	for (i = 0; !fn && i < active_nr; i++) {
		struct cache_entry *ce = active_cache[i];
		if (ce_stage(ce) == stage)
			fn = read_one_entry;
	}

	if (!fn)
		fn = read_one_entry_quick;
	err = read_tree_recursive(tree, "", 0, stage, match, fn, NULL);
	if (fn == read_one_entry || err)
		return err;

	/*
	 * Sort the cache entry -- we need to nuke the cache tree, though.
	 */
	cache_tree_free(&active_cache_tree);
	qsort(active_cache, active_nr, sizeof(active_cache[0]),
	      cmp_cache_name_compare);
	return 0;
}

struct tree *lookup_tree(const unsigned char *sha1)
{
	struct object *obj = lookup_object(sha1);
	if (!obj)
		return create_object(sha1, OBJ_TREE, alloc_tree_node());
	if (!obj->type)
		obj->type = OBJ_TREE;
	if (obj->type != OBJ_TREE) {
		error("Object %s is a %s, not a tree",
		      sha1_to_hex(sha1), typename(obj->type));
		return NULL;
	}
	return (struct tree *) obj;
}

int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size)
{
	if (item->object.parsed)
		return 0;
	item->object.parsed = 1;
	item->buffer = buffer;
	item->size = size;

	return 0;
}

int parse_tree(struct tree *item)
{
	 enum object_type type;
	 void *buffer;
	 unsigned long size;

	if (item->object.parsed)
		return 0;
	buffer = read_sha1_file(item->object.sha1, &type, &size);
	if (!buffer)
		return error("Could not read %s",
			     sha1_to_hex(item->object.sha1));
	if (type != OBJ_TREE) {
		free(buffer);
		return error("Object %s not a tree",
			     sha1_to_hex(item->object.sha1));
	}
	return parse_tree_buffer(item, buffer, size);
}

struct tree *parse_tree_indirect(const unsigned char *sha1)
{
	struct object *obj = parse_object(sha1);
	do {
		if (!obj)
			return NULL;
		if (obj->type == OBJ_TREE)
			return (struct tree *) obj;
		else if (obj->type == OBJ_COMMIT)
			obj = &(((struct commit *) obj)->tree->object);
		else if (obj->type == OBJ_TAG)
			obj = ((struct tag *) obj)->tagged;
		else
			return NULL;
		if (!obj->parsed)
			parse_object(obj->sha1);
	} while (1);
}
Commit	Line	Data
8f1d2e6f	1	#include "cache.h"
af3785dc	2	#include "cache-tree.h"
175785e5 DB	3	#include "tree.h"
175785e5 DB	4	#include "blob.h"
77675e2a DB	5	#include "commit.h"
77675e2a DB	6	#include "tag.h"
136f2e54	7	#include "tree-walk.h"
175785e5 DB	8
	9	const char *tree_type = "tree";
	10
af3785dc	11	static int read_one_entry_opt(const unsigned char sha1, const char base, int baselen, const char *pathname, unsigned mode, int stage, int opt)
94537c78	12	{
3c5e8468 LT	13	int len;
	14	unsigned int size;
	15	struct cache_entry *ce;
	16
	17	if (S_ISDIR(mode))
	18	return READ_TREE_RECURSIVE;
	19
	20	len = strlen(pathname);
	21	size = cache_entry_size(baselen + len);
90321c10	22	ce = xcalloc(1, size);
94537c78 LT	23
	24	ce->ce_mode = create_ce_mode(mode);
	25	ce->ce_flags = create_ce_flags(baselen + len, stage);
	26	memcpy(ce->name, base, baselen);
	27	memcpy(ce->name + baselen, pathname, len+1);
e702496e	28	hashcpy(ce->sha1, sha1);
af3785dc JH	29	return add_cache_entry(ce, opt);
	30	}
	31
671f0707	32	static int read_one_entry(const unsigned char sha1, const char base, int baselen, const char pathname, unsigned mode, int stage, void context)
af3785dc JH	33	{
	34	return read_one_entry_opt(sha1, base, baselen, pathname, mode, stage,
	35	ADD_CACHE_OK_TO_ADD\|ADD_CACHE_SKIP_DFCHECK);
	36	}
	37
	38	/*
	39	* This is used when the caller knows there is no existing entries at
	40	* the stage that will conflict with the entry being added.
	41	*/
671f0707	42	static int read_one_entry_quick(const unsigned char sha1, const char base, int baselen, const char pathname, unsigned mode, int stage, void context)
af3785dc JH	43	{
	44	return read_one_entry_opt(sha1, base, baselen, pathname, mode, stage,
	45	ADD_CACHE_JUST_APPEND);
94537c78 LT	46	}
94537c78 LT	47
3e587635	48	static int match_tree_entry(const char base, int baselen, const char path, unsigned int mode, const char **paths)
0ca14a57	49	{
3e587635	50	const char *match;
0ca14a57 LT	51	int pathlen;
	52
	53	if (!paths)
	54	return 1;
	55	pathlen = strlen(path);
	56	while ((match = *paths++) != NULL) {
	57	int matchlen = strlen(match);
	58
	59	if (baselen >= matchlen) {
	60	/* If it doesn't match, move along... */
	61	if (strncmp(base, match, matchlen))
	62	continue;
8092bfb6 JH	63	/* pathspecs match only at the directory boundaries */
8092bfb6 JH	64	if (!matchlen \|\|
7183c09d	65	baselen == matchlen \|\|
8092bfb6 JH	66	base[matchlen] == '/' \|\|
	67	match[matchlen - 1] == '/')
	68	return 1;
	69	continue;
0ca14a57 LT	70	}
	71
	72	/* Does the base match? */
	73	if (strncmp(base, match, baselen))
	74	continue;
	75
	76	match += baselen;
	77	matchlen -= baselen;
	78
	79	if (pathlen > matchlen)
	80	continue;
	81
	82	if (matchlen > pathlen) {
	83	if (match[pathlen] != '/')
	84	continue;
	85	if (!S_ISDIR(mode))
	86	continue;
	87	}
	88
	89	if (strncmp(path, match, pathlen))
	90	continue;
3e587635 LT	91
3e587635 LT	92	return 1;
0ca14a57 LT	93	}
	94	return 0;
	95	}
	96
521698b1	97	int read_tree_recursive(struct tree *tree,
3c5e8468 LT	98	const char *base, int baselen,
3c5e8468 LT	99	int stage, const char **match,
671f0707	100	read_tree_fn_t fn, void *context)
94537c78	101	{
0790a42a	102	struct tree_desc desc;
4c068a98	103	struct name_entry entry;
0790a42a	104
521698b1 DB	105	if (parse_tree(tree))
521698b1 DB	106	return -1;
0790a42a	107
6fda5e51	108	init_tree_desc(&desc, tree->buffer, tree->size);
0790a42a	109
4c068a98 LT	110	while (tree_entry(&desc, &entry)) {
4c068a98 LT	111	if (!match_tree_entry(base, baselen, entry.path, entry.mode, match))
0ca14a57 LT	112	continue;
0ca14a57 LT	113
671f0707	114	switch (fn(entry.sha1, base, baselen, entry.path, entry.mode, stage, context)) {
3c5e8468 LT	115	case 0:
	116	continue;
	117	case READ_TREE_RECURSIVE:
ba19a808	118	break;
3c5e8468 LT	119	default:
	120	return -1;
	121	}
4c068a98	122	if (S_ISDIR(entry.mode)) {
94537c78	123	int retval;
1c9da46d	124	char *newbase;
a8c40471	125	unsigned int pathlen = tree_entry_len(entry.path, entry.sha1);
94537c78	126
a8c40471	127	newbase = xmalloc(baselen + 1 + pathlen);
94537c78	128	memcpy(newbase, base, baselen);
a8c40471 LT	129	memcpy(newbase + baselen, entry.path, pathlen);
a8c40471 LT	130	newbase[baselen + pathlen] = '/';
4c068a98	131	retval = read_tree_recursive(lookup_tree(entry.sha1),
94537c78	132	newbase,
a8c40471	133	baselen + pathlen + 1,
671f0707	134	stage, match, fn, context);
94537c78 LT	135	free(newbase);
	136	if (retval)
	137	return -1;
	138	continue;
d3bee161 LH	139	} else if (S_ISGITLINK(entry.mode)) {
	140	int retval;
	141	struct strbuf path;
	142	unsigned int entrylen;
	143	struct commit *commit;
	144
	145	entrylen = tree_entry_len(entry.path, entry.sha1);
	146	strbuf_init(&path, baselen + entrylen + 1);
	147	strbuf_add(&path, base, baselen);
	148	strbuf_add(&path, entry.path, entrylen);
	149	strbuf_addch(&path, '/');
	150
	151	commit = lookup_commit(entry.sha1);
	152	if (!commit)
	153	die("Commit %s in submodule path %s not found",
	154	sha1_to_hex(entry.sha1), path.buf);
	155
	156	if (parse_commit(commit))
	157	die("Invalid commit %s in submodule path %s",
	158	sha1_to_hex(entry.sha1), path.buf);
	159
	160	retval = read_tree_recursive(commit->tree,
	161	path.buf, path.len,
	162	stage, match, fn, context);
	163	strbuf_release(&path);
	164	if (retval)
	165	return -1;
	166	continue;
94537c78	167	}
94537c78 LT	168	}
	169	return 0;
	170	}
	171
af3785dc JH	172	static int cmp_cache_name_compare(const void a_, const void b_)
	173	{
	174	const struct cache_entry ce1, ce2;
	175
	176	ce1 = ((const struct cache_entry *)a_);
	177	ce2 = ((const struct cache_entry *)b_);
7a51ed66 LT	178	return cache_name_compare(ce1->name, ce1->ce_flags,
7a51ed66 LT	179	ce2->name, ce2->ce_flags);
af3785dc JH	180	}
af3785dc JH	181
521698b1	182	int read_tree(struct tree tree, int stage, const char *match)
94537c78	183	{
af3785dc JH	184	read_tree_fn_t fn = NULL;
	185	int i, err;
	186
	187	/*
	188	* Currently the only existing callers of this function all
	189	* call it with stage=1 and after making sure there is nothing
	190	* at that stage; we could always use read_one_entry_quick().
	191	*
	192	* But when we decide to straighten out git-read-tree not to
	193	* use unpack_trees() in some cases, this will probably start
	194	* to matter.
	195	*/
	196
	197	/*
	198	* See if we have cache entry at the stage. If so,
	199	* do it the original slow way, otherwise, append and then
	200	* sort at the end.
	201	*/
	202	for (i = 0; !fn && i < active_nr; i++) {
	203	struct cache_entry *ce = active_cache[i];
	204	if (ce_stage(ce) == stage)
	205	fn = read_one_entry;
	206	}
	207
	208	if (!fn)
	209	fn = read_one_entry_quick;
671f0707	210	err = read_tree_recursive(tree, "", 0, stage, match, fn, NULL);
af3785dc JH	211	if (fn == read_one_entry \|\| err)
	212	return err;
	213
	214	/*
	215	* Sort the cache entry -- we need to nuke the cache tree, though.
	216	*/
	217	cache_tree_free(&active_cache_tree);
	218	qsort(active_cache, active_nr, sizeof(active_cache[0]),
	219	cmp_cache_name_compare);
	220	return 0;
94537c78 LT	221	}
94537c78 LT	222
5d6ccf5c	223	struct tree lookup_tree(const unsigned char sha1)
175785e5 DB	224	{
175785e5 DB	225	struct object *obj = lookup_object(sha1);
100c5f3b LT	226	if (!obj)
100c5f3b LT	227	return create_object(sha1, OBJ_TREE, alloc_tree_node());
d1af002d	228	if (!obj->type)
1974632c LT	229	obj->type = OBJ_TREE;
1974632c LT	230	if (obj->type != OBJ_TREE) {
885a86ab LT	231	error("Object %s is a %s, not a tree",
885a86ab LT	232	sha1_to_hex(sha1), typename(obj->type));
175785e5 DB	233	return NULL;
	234	}
	235	return (struct tree *) obj;
	236	}
	237
2d9c58c6 LT	238	int parse_tree_buffer(struct tree item, void buffer, unsigned long size)
2d9c58c6 LT	239	{
175785e5 DB	240	if (item->object.parsed)
	241	return 0;
	242	item->object.parsed = 1;
136f2e54 LT	243	item->buffer = buffer;
	244	item->size = size;
	245
2d9c58c6 LT	246	return 0;
	247	}
	248
bd2c39f5 NP	249	int parse_tree(struct tree *item)
bd2c39f5 NP	250	{
21666f1a	251	enum object_type type;
bd2c39f5 NP	252	void *buffer;
bd2c39f5 NP	253	unsigned long size;
bd2c39f5 NP	254
	255	if (item->object.parsed)
	256	return 0;
21666f1a	257	buffer = read_sha1_file(item->object.sha1, &type, &size);
bd2c39f5 NP	258	if (!buffer)
	259	return error("Could not read %s",
	260	sha1_to_hex(item->object.sha1));
21666f1a	261	if (type != OBJ_TREE) {
bd2c39f5 NP	262	free(buffer);
	263	return error("Object %s not a tree",
	264	sha1_to_hex(item->object.sha1));
	265	}
136f2e54	266	return parse_tree_buffer(item, buffer, size);
bd2c39f5	267	}
77675e2a DB	268
	269	struct tree parse_tree_indirect(const unsigned char sha1)
	270	{
	271	struct object *obj = parse_object(sha1);
	272	do {
	273	if (!obj)
	274	return NULL;
1974632c	275	if (obj->type == OBJ_TREE)
77675e2a	276	return (struct tree *) obj;
1974632c	277	else if (obj->type == OBJ_COMMIT)
77675e2a	278	obj = &(((struct commit *) obj)->tree->object);
1974632c	279	else if (obj->type == OBJ_TAG)
77675e2a DB	280	obj = ((struct tag *) obj)->tagged;
	281	else
	282	return NULL;
	283	if (!obj->parsed)
	284	parse_object(obj->sha1);
	285	} while (1);
	286	}