Adding upstream version 1:2.39.2.upstream/1%2.39.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1286 insertions, 0 deletions

diff --git a/tree-walk.c b/tree-walk.c
new file mode 100644
index 0000000..74f4d71
--- /dev/null
+++ b/tree-walk.c
@@ -0,0 +1,1286 @@
+#include "cache.h"
+#include "tree-walk.h"
+#include "dir.h"
+#include "object-store.h"
+#include "tree.h"
+#include "pathspec.h"
+#include "json-writer.h"
+
+static const char *get_mode(const char *str, unsigned int *modep)
+{
+	unsigned char c;
+	unsigned int mode = 0;
+
+	if (*str == ' ')
+		return NULL;
+
+	while ((c = *str++) != ' ') {
+		if (c < '0' || c > '7')
+			return NULL;
+		mode = (mode << 3) + (c - '0');
+	}
+	*modep = mode;
+	return str;
+}
+
+static int decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size, struct strbuf *err)
+{
+	const char *path;
+	unsigned int mode, len;
+	const unsigned hashsz = the_hash_algo->rawsz;
+
+	if (size < hashsz + 3 || buf[size - (hashsz + 1)]) {
+		strbuf_addstr(err, _("too-short tree object"));
+		return -1;
+	}
+
+	path = get_mode(buf, &mode);
+	if (!path) {
+		strbuf_addstr(err, _("malformed mode in tree entry"));
+		return -1;
+	}
+	if (!*path) {
+		strbuf_addstr(err, _("empty filename in tree entry"));
+		return -1;
+	}
+	len = strlen(path) + 1;
+
+	/* Initialize the descriptor entry */
+	desc->entry.path = path;
+	desc->entry.mode = (desc->flags & TREE_DESC_RAW_MODES) ? mode : canon_mode(mode);
+	desc->entry.pathlen = len - 1;
+	oidread(&desc->entry.oid, (const unsigned char *)path + len);
+
+	return 0;
+}
+
+static int init_tree_desc_internal(struct tree_desc *desc, const void *buffer,
+				   unsigned long size, struct strbuf *err,
+				   enum tree_desc_flags flags)
+{
+	desc->buffer = buffer;
+	desc->size = size;
+	desc->flags = flags;
+	if (size)
+		return decode_tree_entry(desc, buffer, size, err);
+	return 0;
+}
+
+void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
+{
+	struct strbuf err = STRBUF_INIT;
+	if (init_tree_desc_internal(desc, buffer, size, &err, 0))
+		die("%s", err.buf);
+	strbuf_release(&err);
+}
+
+int init_tree_desc_gently(struct tree_desc *desc, const void *buffer, unsigned long size,
+			  enum tree_desc_flags flags)
+{
+	struct strbuf err = STRBUF_INIT;
+	int result = init_tree_desc_internal(desc, buffer, size, &err, flags);
+	if (result)
+		error("%s", err.buf);
+	strbuf_release(&err);
+	return result;
+}
+
+void *fill_tree_descriptor(struct repository *r,
+			   struct tree_desc *desc,
+			   const struct object_id *oid)
+{
+	unsigned long size = 0;
+	void *buf = NULL;
+
+	if (oid) {
+		buf = read_object_with_reference(r, oid, OBJ_TREE, &size, NULL);
+		if (!buf)
+			die("unable to read tree %s", oid_to_hex(oid));
+	}
+	init_tree_desc(desc, buf, size);
+	return buf;
+}
+
+static void entry_clear(struct name_entry *a)
+{
+	memset(a, 0, sizeof(*a));
+}
+
+static void entry_extract(struct tree_desc *t, struct name_entry *a)
+{
+	*a = t->entry;
+}
+
+static int update_tree_entry_internal(struct tree_desc *desc, struct strbuf *err)
+{
+	const void *buf = desc->buffer;
+	const unsigned char *end = (const unsigned char *)desc->entry.path + desc->entry.pathlen + 1 + the_hash_algo->rawsz;
+	unsigned long size = desc->size;
+	unsigned long len = end - (const unsigned char *)buf;
+
+	if (size < len)
+		die(_("too-short tree file"));
+	buf = end;
+	size -= len;
+	desc->buffer = buf;
+	desc->size = size;
+	if (size)
+		return decode_tree_entry(desc, buf, size, err);
+	return 0;
+}
+
+void update_tree_entry(struct tree_desc *desc)
+{
+	struct strbuf err = STRBUF_INIT;
+	if (update_tree_entry_internal(desc, &err))
+		die("%s", err.buf);
+	strbuf_release(&err);
+}
+
+int update_tree_entry_gently(struct tree_desc *desc)
+{
+	struct strbuf err = STRBUF_INIT;
+	if (update_tree_entry_internal(desc, &err)) {
+		error("%s", err.buf);
+		strbuf_release(&err);
+		/* Stop processing this tree after error */
+		desc->size = 0;
+		return -1;
+	}
+	strbuf_release(&err);
+	return 0;
+}
+
+int tree_entry(struct tree_desc *desc, struct name_entry *entry)
+{
+	if (!desc->size)
+		return 0;
+
+	*entry = desc->entry;
+	update_tree_entry(desc);
+	return 1;
+}
+
+int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
+{
+	if (!desc->size)
+		return 0;
+
+	*entry = desc->entry;
+	if (update_tree_entry_gently(desc))
+		return 0;
+	return 1;
+}
+
+static int traverse_trees_atexit_registered;
+static int traverse_trees_count;
+static int traverse_trees_cur_depth;
+static int traverse_trees_max_depth;
+
+static void trace2_traverse_trees_statistics_atexit(void)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count);
+	jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth);
+	jw_end(&jw);
+
+	trace2_data_json("traverse_trees", the_repository, "statistics", &jw);
+
+	jw_release(&jw);
+}
+
+void setup_traverse_info(struct traverse_info *info, const char *base)
+{
+	size_t pathlen = strlen(base);
+	static struct traverse_info dummy;
+
+	memset(info, 0, sizeof(*info));
+	if (pathlen && base[pathlen-1] == '/')
+		pathlen--;
+	info->pathlen = pathlen ? pathlen + 1 : 0;
+	info->name = base;
+	info->namelen = pathlen;
+	if (pathlen)
+		info->prev = &dummy;
+
+	if (trace2_is_enabled() && !traverse_trees_atexit_registered) {
+		atexit(trace2_traverse_trees_statistics_atexit);
+		traverse_trees_atexit_registered = 1;
+	}
+}
+
+char *make_traverse_path(char *path, size_t pathlen,
+			 const struct traverse_info *info,
+			 const char *name, size_t namelen)
+{
+	/* Always points to the end of the name we're about to add */
+	size_t pos = st_add(info->pathlen, namelen);
+
+	if (pos >= pathlen)
+		BUG("too small buffer passed to make_traverse_path");
+
+	path[pos] = 0;
+	for (;;) {
+		if (pos < namelen)
+			BUG("traverse_info pathlen does not match strings");
+		pos -= namelen;
+		memcpy(path + pos, name, namelen);
+
+		if (!pos)
+			break;
+		path[--pos] = '/';
+
+		if (!info)
+			BUG("traverse_info ran out of list items");
+		name = info->name;
+		namelen = info->namelen;
+		info = info->prev;
+	}
+	return path;
+}
+
+void strbuf_make_traverse_path(struct strbuf *out,
+			       const struct traverse_info *info,
+			       const char *name, size_t namelen)
+{
+	size_t len = traverse_path_len(info, namelen);
+
+	strbuf_grow(out, len);
+	make_traverse_path(out->buf + out->len, out->alloc - out->len,
+			   info, name, namelen);
+	strbuf_setlen(out, out->len + len);
+}
+
+struct tree_desc_skip {
+	struct tree_desc_skip *prev;
+	const void *ptr;
+};
+
+struct tree_desc_x {
+	struct tree_desc d;
+	struct tree_desc_skip *skip;
+};
+
+static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
+{
+	/*
+	 * The caller wants to pick *a* from a tree or nothing.
+	 * We are looking at *b* in a tree.
+	 *
+	 * (0) If a and b are the same name, we are trivially happy.
+	 *
+	 * There are three possibilities where *a* could be hiding
+	 * behind *b*.
+	 *
+	 * (1) *a* == "t",   *b* == "ab"  i.e. *b* sorts earlier than *a* no
+	 *                                matter what.
+	 * (2) *a* == "t",   *b* == "t-2" and "t" is a subtree in the tree;
+	 * (3) *a* == "t-2", *b* == "t"   and "t-2" is a blob in the tree.
+	 *
+	 * Otherwise we know *a* won't appear in the tree without
+	 * scanning further.
+	 */
+
+	int cmp = name_compare(a, a_len, b, b_len);
+
+	/* Most common case first -- reading sync'd trees */
+	if (!cmp)
+		return cmp;
+
+	if (0 < cmp) {
+		/* a comes after b; it does not matter if it is case (3)
+		if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
+			return 1;
+		*/
+		return 1; /* keep looking */
+	}
+
+	/* b comes after a; are we looking at case (2)? */
+	if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
+		return 1; /* keep looking */
+
+	return -1; /* a cannot appear in the tree */
+}
+
+/*
+ * From the extended tree_desc, extract the first name entry, while
+ * paying attention to the candidate "first" name.  Most importantly,
+ * when looking for an entry, if there are entries that sorts earlier
+ * in the tree object representation than that name, skip them and
+ * process the named entry first.  We will remember that we haven't
+ * processed the first entry yet, and in the later call skip the
+ * entry we processed early when update_extended_entry() is called.
+ *
+ * E.g. if the underlying tree object has these entries:
+ *
+ *    blob    "t-1"
+ *    blob    "t-2"
+ *    tree    "t"
+ *    blob    "t=1"
+ *
+ * and the "first" asks for "t", remember that we still need to
+ * process "t-1" and "t-2" but extract "t".  After processing the
+ * entry "t" from this call, the caller will let us know by calling
+ * update_extended_entry() that we can remember "t" has been processed
+ * already.
+ */
+
+static void extended_entry_extract(struct tree_desc_x *t,
+				   struct name_entry *a,
+				   const char *first,
+				   int first_len)
+{
+	const char *path;
+	int len;
+	struct tree_desc probe;
+	struct tree_desc_skip *skip;
+
+	/*
+	 * Extract the first entry from the tree_desc, but skip the
+	 * ones that we already returned in earlier rounds.
+	 */
+	while (1) {
+		if (!t->d.size) {
+			entry_clear(a);
+			break; /* not found */
+		}
+		entry_extract(&t->d, a);
+		for (skip = t->skip; skip; skip = skip->prev)
+			if (a->path == skip->ptr)
+				break; /* found */
+		if (!skip)
+			break;
+		/* We have processed this entry already. */
+		update_tree_entry(&t->d);
+	}
+
+	if (!first || !a->path)
+		return;
+
+	/*
+	 * The caller wants "first" from this tree, or nothing.
+	 */
+	path = a->path;
+	len = tree_entry_len(a);
+	switch (check_entry_match(first, first_len, path, len)) {
+	case -1:
+		entry_clear(a);
+	case 0:
+		return;
+	default:
+		break;
+	}
+
+	/*
+	 * We need to look-ahead -- we suspect that a subtree whose
+	 * name is "first" may be hiding behind the current entry "path".
+	 */
+	probe = t->d;
+	while (probe.size) {
+		entry_extract(&probe, a);
+		path = a->path;
+		len = tree_entry_len(a);
+		switch (check_entry_match(first, first_len, path, len)) {
+		case -1:
+			entry_clear(a);
+		case 0:
+			return;
+		default:
+			update_tree_entry(&probe);
+			break;
+		}
+		/* keep looking */
+	}
+	entry_clear(a);
+}
+
+static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
+{
+	if (t->d.entry.path == a->path) {
+		update_tree_entry(&t->d);
+	} else {
+		/* we have returned this entry early */
+		struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
+		skip->ptr = a->path;
+		skip->prev = t->skip;
+		t->skip = skip;
+	}
+}
+
+static void free_extended_entry(struct tree_desc_x *t)
+{
+	struct tree_desc_skip *p, *s;
+
+	for (s = t->skip; s; s = p) {
+		p = s->prev;
+		free(s);
+	}
+}
+
+static inline int prune_traversal(struct index_state *istate,
+				  struct name_entry *e,
+				  struct traverse_info *info,
+				  struct strbuf *base,
+				  int still_interesting)
+{
+	if (!info->pathspec || still_interesting == 2)
+		return 2;
+	if (still_interesting < 0)
+		return still_interesting;
+	return tree_entry_interesting(istate, e, base,
+				      0, info->pathspec);
+}
+
+int traverse_trees(struct index_state *istate,
+		   int n, struct tree_desc *t,
+		   struct traverse_info *info)
+{
+	int error = 0;
+	struct name_entry entry[MAX_TRAVERSE_TREES];
+	int i;
+	struct tree_desc_x tx[ARRAY_SIZE(entry)];
+	struct strbuf base = STRBUF_INIT;
+	int interesting = 1;
+	char *traverse_path;
+
+	traverse_trees_count++;
+	traverse_trees_cur_depth++;
+
+	if (traverse_trees_cur_depth > traverse_trees_max_depth)
+		traverse_trees_max_depth = traverse_trees_cur_depth;
+
+	if (n >= ARRAY_SIZE(entry))
+		BUG("traverse_trees() called with too many trees (%d)", n);
+
+	for (i = 0; i < n; i++) {
+		tx[i].d = t[i];
+		tx[i].skip = NULL;
+	}
+
+	if (info->prev) {
+		strbuf_make_traverse_path(&base, info->prev,
+					  info->name, info->namelen);
+		strbuf_addch(&base, '/');
+		traverse_path = xstrndup(base.buf, base.len);
+	} else {
+		traverse_path = xstrndup(info->name, info->pathlen);
+	}
+	info->traverse_path = traverse_path;
+	for (;;) {
+		int trees_used;
+		unsigned long mask, dirmask;
+		const char *first = NULL;
+		int first_len = 0;
+		struct name_entry *e = NULL;
+		int len;
+
+		for (i = 0; i < n; i++) {
+			e = entry + i;
+			extended_entry_extract(tx + i, e, NULL, 0);
+		}
+
+		/*
+		 * A tree may have "t-2" at the current location even
+		 * though it may have "t" that is a subtree behind it,
+		 * and another tree may return "t".  We want to grab
+		 * all "t" from all trees to match in such a case.
+		 */
+		for (i = 0; i < n; i++) {
+			e = entry + i;
+			if (!e->path)
+				continue;
+			len = tree_entry_len(e);
+			if (!first) {
+				first = e->path;
+				first_len = len;
+				continue;
+			}
+			if (name_compare(e->path, len, first, first_len) < 0) {
+				first = e->path;
+				first_len = len;
+			}
+		}
+
+		if (first) {
+			for (i = 0; i < n; i++) {
+				e = entry + i;
+				extended_entry_extract(tx + i, e, first, first_len);
+				/* Cull the ones that are not the earliest */
+				if (!e->path)
+					continue;
+				len = tree_entry_len(e);
+				if (name_compare(e->path, len, first, first_len))
+					entry_clear(e);
+			}
+		}
+
+		/* Now we have in entry[i] the earliest name from the trees */
+		mask = 0;
+		dirmask = 0;
+		for (i = 0; i < n; i++) {
+			if (!entry[i].path)
+				continue;
+			mask |= 1ul << i;
+			if (S_ISDIR(entry[i].mode))
+				dirmask |= 1ul << i;
+			e = &entry[i];
+		}
+		if (!mask)
+			break;
+		interesting = prune_traversal(istate, e, info, &base, interesting);
+		if (interesting < 0)
+			break;
+		if (interesting) {
+			trees_used = info->fn(n, mask, dirmask, entry, info);
+			if (trees_used < 0) {
+				error = trees_used;
+				if (!info->show_all_errors)
+					break;
+			}
+			mask &= trees_used;
+		}
+		for (i = 0; i < n; i++)
+			if (mask & (1ul << i))
+				update_extended_entry(tx + i, entry + i);
+	}
+	for (i = 0; i < n; i++)
+		free_extended_entry(tx + i);
+	free(traverse_path);
+	info->traverse_path = NULL;
+	strbuf_release(&base);
+
+	traverse_trees_cur_depth--;
+	return error;
+}
+
+struct dir_state {
+	void *tree;
+	unsigned long size;
+	struct object_id oid;
+};
+
+static int find_tree_entry(struct repository *r, struct tree_desc *t,
+			   const char *name, struct object_id *result,
+			   unsigned short *mode)
+{
+	int namelen = strlen(name);
+	while (t->size) {
+		const char *entry;
+		struct object_id oid;
+		int entrylen, cmp;
+
+		oidcpy(&oid, tree_entry_extract(t, &entry, mode));
+		entrylen = tree_entry_len(&t->entry);
+		update_tree_entry(t);
+		if (entrylen > namelen)
+			continue;
+		cmp = memcmp(name, entry, entrylen);
+		if (cmp > 0)
+			continue;
+		if (cmp < 0)
+			break;
+		if (entrylen == namelen) {
+			oidcpy(result, &oid);
+			return 0;
+		}
+		if (name[entrylen] != '/')
+			continue;
+		if (!S_ISDIR(*mode))
+			break;
+		if (++entrylen == namelen) {
+			oidcpy(result, &oid);
+			return 0;
+		}
+		return get_tree_entry(r, &oid, name + entrylen, result, mode);
+	}
+	return -1;
+}
+
+int get_tree_entry(struct repository *r,
+		   const struct object_id *tree_oid,
+		   const char *name,
+		   struct object_id *oid,
+		   unsigned short *mode)
+{
+	int retval;
+	void *tree;
+	unsigned long size;
+	struct object_id root;
+
+	tree = read_object_with_reference(r, tree_oid, OBJ_TREE, &size, &root);
+	if (!tree)
+		return -1;
+
+	if (name[0] == '\0') {
+		oidcpy(oid, &root);
+		free(tree);
+		return 0;
+	}
+
+	if (!size) {
+		retval = -1;
+	} else {
+		struct tree_desc t;
+		init_tree_desc(&t, tree, size);
+		retval = find_tree_entry(r, &t, name, oid, mode);
+	}
+	free(tree);
+	return retval;
+}
+
+/*
+ * This is Linux's built-in max for the number of symlinks to follow.
+ * That limit, of course, does not affect git, but it's a reasonable
+ * choice.
+ */
+#define GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS 40
+
+/**
+ * Find a tree entry by following symlinks in tree_sha (which is
+ * assumed to be the root of the repository).  In the event that a
+ * symlink points outside the repository (e.g. a link to /foo or a
+ * root-level link to ../foo), the portion of the link which is
+ * outside the repository will be returned in result_path, and *mode
+ * will be set to 0.  It is assumed that result_path is uninitialized.
+ * If there are no symlinks, or the end result of the symlink chain
+ * points to an object inside the repository, result will be filled in
+ * with the sha1 of the found object, and *mode will hold the mode of
+ * the object.
+ *
+ * See the code for enum get_oid_result for a description of
+ * the return values.
+ */
+enum get_oid_result get_tree_entry_follow_symlinks(struct repository *r,
+		struct object_id *tree_oid, const char *name,
+		struct object_id *result, struct strbuf *result_path,
+		unsigned short *mode)
+{
+	int retval = MISSING_OBJECT;
+	struct dir_state *parents = NULL;
+	size_t parents_alloc = 0;
+	size_t i, parents_nr = 0;
+	struct object_id current_tree_oid;
+	struct strbuf namebuf = STRBUF_INIT;
+	struct tree_desc t;
+	int follows_remaining = GET_TREE_ENTRY_FOLLOW_SYMLINKS_MAX_LINKS;
+
+	init_tree_desc(&t, NULL, 0UL);
+	strbuf_addstr(&namebuf, name);
+	oidcpy(&current_tree_oid, tree_oid);
+
+	while (1) {
+		int find_result;
+		char *first_slash;
+		char *remainder = NULL;
+
+		if (!t.buffer) {
+			void *tree;
+			struct object_id root;
+			unsigned long size;
+			tree = read_object_with_reference(r,
+							  &current_tree_oid,
+							  OBJ_TREE, &size,
+							  &root);
+			if (!tree)
+				goto done;
+
+			ALLOC_GROW(parents, parents_nr + 1, parents_alloc);
+			parents[parents_nr].tree = tree;
+			parents[parents_nr].size = size;
+			oidcpy(&parents[parents_nr].oid, &root);
+			parents_nr++;
+
+			if (namebuf.buf[0] == '\0') {
+				oidcpy(result, &root);
+				retval = FOUND;
+				goto done;
+			}
+
+			if (!size)
+				goto done;
+
+			/* descend */
+			init_tree_desc(&t, tree, size);
+		}
+
+		/* Handle symlinks to e.g. a//b by removing leading slashes */
+		while (namebuf.buf[0] == '/') {
+			strbuf_remove(&namebuf, 0, 1);
+		}
+
+		/* Split namebuf into a first component and a remainder */
+		if ((first_slash = strchr(namebuf.buf, '/'))) {
+			*first_slash = 0;
+			remainder = first_slash + 1;
+		}
+
+		if (!strcmp(namebuf.buf, "..")) {
+			struct dir_state *parent;
+			/*
+			 * We could end up with .. in the namebuf if it
+			 * appears in a symlink.
+			 */
+
+			if (parents_nr == 1) {
+				if (remainder)
+					*first_slash = '/';
+				strbuf_add(result_path, namebuf.buf,
+					   namebuf.len);
+				*mode = 0;
+				retval = FOUND;
+				goto done;
+			}
+			parent = &parents[parents_nr - 1];
+			free(parent->tree);
+			parents_nr--;
+			parent = &parents[parents_nr - 1];
+			init_tree_desc(&t, parent->tree, parent->size);
+			strbuf_remove(&namebuf, 0, remainder ? 3 : 2);
+			continue;
+		}
+
+		/* We could end up here via a symlink to dir/.. */
+		if (namebuf.buf[0] == '\0') {
+			oidcpy(result, &parents[parents_nr - 1].oid);
+			retval = FOUND;
+			goto done;
+		}
+
+		/* Look up the first (or only) path component in the tree. */
+		find_result = find_tree_entry(r, &t, namebuf.buf,
+					      &current_tree_oid, mode);
+		if (find_result) {
+			goto done;
+		}
+
+		if (S_ISDIR(*mode)) {
+			if (!remainder) {
+				oidcpy(result, &current_tree_oid);
+				retval = FOUND;
+				goto done;
+			}
+			/* Descend the tree */
+			t.buffer = NULL;
+			strbuf_remove(&namebuf, 0,
+				      1 + first_slash - namebuf.buf);
+		} else if (S_ISREG(*mode)) {
+			if (!remainder) {
+				oidcpy(result, &current_tree_oid);
+				retval = FOUND;
+			} else {
+				retval = NOT_DIR;
+			}
+			goto done;
+		} else if (S_ISLNK(*mode)) {
+			/* Follow a symlink */
+			unsigned long link_len;
+			size_t len;
+			char *contents, *contents_start;
+			struct dir_state *parent;
+			enum object_type type;
+
+			if (follows_remaining-- == 0) {
+				/* Too many symlinks followed */
+				retval = SYMLINK_LOOP;
+				goto done;
+			}
+
+			/*
+			 * At this point, we have followed at a least
+			 * one symlink, so on error we need to report this.
+			 */
+			retval = DANGLING_SYMLINK;
+
+			contents = repo_read_object_file(r,
+						    &current_tree_oid, &type,
+						    &link_len);
+
+			if (!contents)
+				goto done;
+
+			if (contents[0] == '/') {
+				strbuf_addstr(result_path, contents);
+				free(contents);
+				*mode = 0;
+				retval = FOUND;
+				goto done;
+			}
+
+			if (remainder)
+				len = first_slash - namebuf.buf;
+			else
+				len = namebuf.len;
+
+			contents_start = contents;
+
+			parent = &parents[parents_nr - 1];
+			init_tree_desc(&t, parent->tree, parent->size);
+			strbuf_splice(&namebuf, 0, len,
+				      contents_start, link_len);
+			if (remainder)
+				namebuf.buf[link_len] = '/';
+			free(contents);
+		}
+	}
+done:
+	for (i = 0; i < parents_nr; i++)
+		free(parents[i].tree);
+	free(parents);
+
+	strbuf_release(&namebuf);
+	return retval;
+}
+
+static int match_entry(const struct pathspec_item *item,
+		       const struct name_entry *entry, int pathlen,
+		       const char *match, int matchlen,
+		       enum interesting *never_interesting)
+{
+	int m = -1; /* signals that we haven't called strncmp() */
+
+	if (item->magic & PATHSPEC_ICASE)
+		/*
+		 * "Never interesting" trick requires exact
+		 * matching. We could do something clever with inexact
+		 * matching, but it's trickier (and not to forget that
+		 * strcasecmp is locale-dependent, at least in
+		 * glibc). Just disable it for now. It can't be worse
+		 * than the wildcard's codepath of '[Tt][Hi][Is][Ss]'
+		 * pattern.
+		 */
+		*never_interesting = entry_not_interesting;
+	else if (*never_interesting != entry_not_interesting) {
+		/*
+		 * We have not seen any match that sorts later
+		 * than the current path.
+		 */
+
+		/*
+		 * Does match sort strictly earlier than path
+		 * with their common parts?
+		 */
+		m = strncmp(match, entry->path,
+			    (matchlen < pathlen) ? matchlen : pathlen);
+		if (m < 0)
+			return 0;
+
+		/*
+		 * If we come here even once, that means there is at
+		 * least one pathspec that would sort equal to or
+		 * later than the path we are currently looking at.
+		 * In other words, if we have never reached this point
+		 * after iterating all pathspecs, it means all
+		 * pathspecs are either outside of base, or inside the
+		 * base but sorts strictly earlier than the current
+		 * one.  In either case, they will never match the
+		 * subsequent entries.  In such a case, we initialized
+		 * the variable to -1 and that is what will be
+		 * returned, allowing the caller to terminate early.
+		 */
+		*never_interesting = entry_not_interesting;
+	}
+
+	if (pathlen > matchlen)
+		return 0;
+
+	if (matchlen > pathlen) {
+		if (match[pathlen] != '/')
+			return 0;
+		/*
+		 * Reject non-directories as partial pathnames, except
+		 * when match is a submodule with a trailing slash and
+		 * nothing else (to handle 'submod/' and 'submod'
+		 * uniformly).
+		 */
+		if (!S_ISDIR(entry->mode) &&
+		    (!S_ISGITLINK(entry->mode) || matchlen > pathlen + 1))
+			return 0;
+	}
+
+	if (m == -1)
+		/*
+		 * we cheated and did not do strncmp(), so we do
+		 * that here.
+		 */
+		m = ps_strncmp(item, match, entry->path, pathlen);
+
+	/*
+	 * If common part matched earlier then it is a hit,
+	 * because we rejected the case where path is not a
+	 * leading directory and is shorter than match.
+	 */
+	if (!m)
+		/*
+		 * match_entry does not check if the prefix part is
+		 * matched case-sensitively. If the entry is a
+		 * directory and part of prefix, it'll be rematched
+		 * eventually by basecmp with special treatment for
+		 * the prefix.
+		 */
+		return 1;
+
+	return 0;
+}
+
+/* :(icase)-aware string compare */
+static int basecmp(const struct pathspec_item *item,
+		   const char *base, const char *match, int len)
+{
+	if (item->magic & PATHSPEC_ICASE) {
+		int ret, n = len > item->prefix ? item->prefix : len;
+		ret = strncmp(base, match, n);
+		if (ret)
+			return ret;
+		base += n;
+		match += n;
+		len -= n;
+	}
+	return ps_strncmp(item, base, match, len);
+}
+
+static int match_dir_prefix(const struct pathspec_item *item,
+			    const char *base,
+			    const char *match, int matchlen)
+{
+	if (basecmp(item, base, match, matchlen))
+		return 0;
+
+	/*
+	 * If the base is a subdirectory of a path which
+	 * was specified, all of them are interesting.
+	 */
+	if (!matchlen ||
+	    base[matchlen] == '/' ||
+	    match[matchlen - 1] == '/')
+		return 1;
+
+	/* Just a random prefix match */
+	return 0;
+}
+
+/*
+ * Perform matching on the leading non-wildcard part of
+ * pathspec. item->nowildcard_len must be greater than zero. Return
+ * non-zero if base is matched.
+ */
+static int match_wildcard_base(const struct pathspec_item *item,
+			       const char *base, int baselen,
+			       int *matched)
+{
+	const char *match = item->match;
+	/* the wildcard part is not considered in this function */
+	int matchlen = item->nowildcard_len;
+
+	if (baselen) {
+		int dirlen;
+		/*
+		 * Return early if base is longer than the
+		 * non-wildcard part but it does not match.
+		 */
+		if (baselen >= matchlen) {
+			*matched = matchlen;
+			return !basecmp(item, base, match, matchlen);
+		}
+
+		dirlen = matchlen;
+		while (dirlen && match[dirlen - 1] != '/')
+			dirlen--;
+
+		/*
+		 * Return early if base is shorter than the
+		 * non-wildcard part but it does not match. Note that
+		 * base ends with '/' so we are sure it really matches
+		 * directory
+		 */
+		if (basecmp(item, base, match, baselen))
+			return 0;
+		*matched = baselen;
+	} else
+		*matched = 0;
+	/*
+	 * we could have checked entry against the non-wildcard part
+	 * that is not in base and does similar never_interesting
+	 * optimization as in match_entry. For now just be happy with
+	 * base comparison.
+	 */
+	return entry_interesting;
+}
+
+/*
+ * Is a tree entry interesting given the pathspec we have?
+ *
+ * Pre-condition: either baselen == base_offset (i.e. empty path)
+ * or base[baselen-1] == '/' (i.e. with trailing slash).
+ */
+static enum interesting do_match(struct index_state *istate,
+				 const struct name_entry *entry,
+				 struct strbuf *base, int base_offset,
+				 const struct pathspec *ps,
+				 int exclude)
+{
+	int i;
+	int pathlen, baselen = base->len - base_offset;
+	enum interesting never_interesting = ps->has_wildcard ?
+		entry_not_interesting : all_entries_not_interesting;
+
+	GUARD_PATHSPEC(ps,
+		       PATHSPEC_FROMTOP |
+		       PATHSPEC_MAXDEPTH |
+		       PATHSPEC_LITERAL |
+		       PATHSPEC_GLOB |
+		       PATHSPEC_ICASE |
+		       PATHSPEC_EXCLUDE |
+		       PATHSPEC_ATTR);
+
+	if (!ps->nr) {
+		if (!ps->recursive ||
+		    !(ps->magic & PATHSPEC_MAXDEPTH) ||
+		    ps->max_depth == -1)
+			return all_entries_interesting;
+		return within_depth(base->buf + base_offset, baselen,
+				    !!S_ISDIR(entry->mode),
+				    ps->max_depth) ?
+			entry_interesting : entry_not_interesting;
+	}
+
+	pathlen = tree_entry_len(entry);
+
+	for (i = ps->nr - 1; i >= 0; i--) {
+		const struct pathspec_item *item = ps->items+i;
+		const char *match = item->match;
+		const char *base_str = base->buf + base_offset;
+		int matchlen = item->len, matched = 0;
+
+		if ((!exclude &&   item->magic & PATHSPEC_EXCLUDE) ||
+		    ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
+			continue;
+
+		if (baselen >= matchlen) {
+			/* If it doesn't match, move along... */
+			if (!match_dir_prefix(item, base_str, match, matchlen))
+				goto match_wildcards;
+
+			if (!ps->recursive ||
+			    !(ps->magic & PATHSPEC_MAXDEPTH) ||
+			    ps->max_depth == -1) {
+				if (!item->attr_match_nr)
+					return all_entries_interesting;
+				else
+					goto interesting;
+			}
+
+			if (within_depth(base_str + matchlen + 1,
+					 baselen - matchlen - 1,
+					 !!S_ISDIR(entry->mode),
+					 ps->max_depth))
+				goto interesting;
+			else
+				return entry_not_interesting;
+		}
+
+		/* Either there must be no base, or the base must match. */
+		if (baselen == 0 || !basecmp(item, base_str, match, baselen)) {
+			if (match_entry(item, entry, pathlen,
+					match + baselen, matchlen - baselen,
+					&never_interesting))
+				goto interesting;
+
+			if (item->nowildcard_len < item->len) {
+				if (!git_fnmatch(item, match + baselen, entry->path,
+						 item->nowildcard_len - baselen))
+					goto interesting;
+
+				/*
+				 * Match all directories. We'll try to
+				 * match files later on.
+				 */
+				if (ps->recursive && S_ISDIR(entry->mode))
+					return entry_interesting;
+
+				/*
+				 * When matching against submodules with
+				 * wildcard characters, ensure that the entry
+				 * at least matches up to the first wild
+				 * character.  More accurate matching can then
+				 * be performed in the submodule itself.
+				 */
+				if (ps->recurse_submodules &&
+				    S_ISGITLINK(entry->mode) &&
+				    !ps_strncmp(item, match + baselen,
+						entry->path,
+						item->nowildcard_len - baselen))
+					goto interesting;
+			}
+
+			continue;
+		}
+
+match_wildcards:
+		if (item->nowildcard_len == item->len)
+			continue;
+
+		if (item->nowildcard_len &&
+		    !match_wildcard_base(item, base_str, baselen, &matched))
+			continue;
+
+		/*
+		 * Concatenate base and entry->path into one and do
+		 * fnmatch() on it.
+		 *
+		 * While we could avoid concatenation in certain cases
+		 * [1], which saves a memcpy and potentially a
+		 * realloc, it turns out not worth it. Measurement on
+		 * linux-2.6 does not show any clear improvements,
+		 * partly because of the nowildcard_len optimization
+		 * in git_fnmatch(). Avoid micro-optimizations here.
+		 *
+		 * [1] if match_wildcard_base() says the base
+		 * directory is already matched, we only need to match
+		 * the rest, which is shorter so _in theory_ faster.
+		 */
+
+		strbuf_add(base, entry->path, pathlen);
+
+		if (!git_fnmatch(item, match, base->buf + base_offset,
+				 item->nowildcard_len)) {
+			strbuf_setlen(base, base_offset + baselen);
+			goto interesting;
+		}
+
+		/*
+		 * When matching against submodules with
+		 * wildcard characters, ensure that the entry
+		 * at least matches up to the first wild
+		 * character.  More accurate matching can then
+		 * be performed in the submodule itself.
+		 */
+		if (ps->recurse_submodules && S_ISGITLINK(entry->mode) &&
+		    !ps_strncmp(item, match, base->buf + base_offset,
+				item->nowildcard_len)) {
+			strbuf_setlen(base, base_offset + baselen);
+			goto interesting;
+		}
+
+		strbuf_setlen(base, base_offset + baselen);
+
+		/*
+		 * Match all directories. We'll try to match files
+		 * later on.
+		 * max_depth is ignored but we may consider support it
+		 * in future, see
+		 * https://lore.kernel.org/git/7vmxo5l2g4.fsf@alter.siamese.dyndns.org/
+		 */
+		if (ps->recursive && S_ISDIR(entry->mode))
+			return entry_interesting;
+		continue;
+interesting:
+		if (item->attr_match_nr) {
+			int ret;
+
+			/*
+			 * Must not return all_entries_not_interesting
+			 * prematurely. We do not know if all entries do not
+			 * match some attributes with current attr API.
+			 */
+			never_interesting = entry_not_interesting;
+
+			/*
+			 * Consider all directories interesting (because some
+			 * of those files inside may match some attributes
+			 * even though the parent dir does not)
+			 *
+			 * FIXME: attributes _can_ match directories and we
+			 * can probably return all_entries_interesting or
+			 * all_entries_not_interesting here if matched.
+			 */
+			if (S_ISDIR(entry->mode))
+				return entry_interesting;
+
+			strbuf_add(base, entry->path, pathlen);
+			ret = match_pathspec_attrs(istate, base->buf + base_offset,
+						   base->len - base_offset, item);
+			strbuf_setlen(base, base_offset + baselen);
+			if (!ret)
+				continue;
+		}
+		return entry_interesting;
+	}
+	return never_interesting; /* No matches */
+}
+
+/*
+ * Is a tree entry interesting given the pathspec we have?
+ *
+ * Pre-condition: either baselen == base_offset (i.e. empty path)
+ * or base[baselen-1] == '/' (i.e. with trailing slash).
+ */
+enum interesting tree_entry_interesting(struct index_state *istate,
+					const struct name_entry *entry,
+					struct strbuf *base, int base_offset,
+					const struct pathspec *ps)
+{
+	enum interesting positive, negative;
+	positive = do_match(istate, entry, base, base_offset, ps, 0);
+
+	/*
+	 * case | entry | positive | negative | result
+	 * -----+-------+----------+----------+-------
+	 *   1  |  file |   -1     |  -1..2   |  -1
+	 *   2  |  file |    0     |  -1..2   |   0
+	 *   3  |  file |    1     |   -1     |   1
+	 *   4  |  file |    1     |    0     |   1
+	 *   5  |  file |    1     |    1     |   0
+	 *   6  |  file |    1     |    2     |   0
+	 *   7  |  file |    2     |   -1     |   2
+	 *   8  |  file |    2     |    0     |   1
+	 *   9  |  file |    2     |    1     |   0
+	 *  10  |  file |    2     |    2     |  -1
+	 * -----+-------+----------+----------+-------
+	 *  11  |  dir  |   -1     |  -1..2   |  -1
+	 *  12  |  dir  |    0     |  -1..2   |   0
+	 *  13  |  dir  |    1     |   -1     |   1
+	 *  14  |  dir  |    1     |    0     |   1
+	 *  15  |  dir  |    1     |    1     |   1 (*)
+	 *  16  |  dir  |    1     |    2     |   0
+	 *  17  |  dir  |    2     |   -1     |   2
+	 *  18  |  dir  |    2     |    0     |   1
+	 *  19  |  dir  |    2     |    1     |   1 (*)
+	 *  20  |  dir  |    2     |    2     |  -1
+	 *
+	 * (*) An exclude pattern interested in a directory does not
+	 * necessarily mean it will exclude all of the directory. In
+	 * wildcard case, it can't decide until looking at individual
+	 * files inside. So don't write such directories off yet.
+	 */
+
+	if (!(ps->magic & PATHSPEC_EXCLUDE) ||
+	    positive <= entry_not_interesting) /* #1, #2, #11, #12 */
+		return positive;
+
+	negative = do_match(istate, entry, base, base_offset, ps, 1);
+
+	/* #8, #18 */
+	if (positive == all_entries_interesting &&
+	    negative == entry_not_interesting)
+		return entry_interesting;
+
+	/* #3, #4, #7, #13, #14, #17 */
+	if (negative <= entry_not_interesting)
+		return positive;
+
+	/* #15, #19 */
+	if (S_ISDIR(entry->mode) &&
+	    positive >= entry_interesting &&
+	    negative == entry_interesting)
+		return entry_interesting;
+
+	if ((positive == entry_interesting &&
+	     negative >= entry_interesting) || /* #5, #6, #16 */
+	    (positive == all_entries_interesting &&
+	     negative == entry_interesting)) /* #9 */
+		return entry_not_interesting;
+
+	return all_entries_not_interesting; /* #10, #20 */
+}