git log exclude pathspec from file - supported? plans?

@@ -726,6 +726,7 @@ TEST_BUILTINS_OBJS += test-online-cpus.o
 TEST_BUILTINS_OBJS += test-parse-options.o
 TEST_BUILTINS_OBJS += test-parse-pathspec-file.o
 TEST_BUILTINS_OBJS += test-path-utils.o
+TEST_BUILTINS_OBJS += test-pathspec.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
 TEST_BUILTINS_OBJS += test-prio-queue.o

@@ -760,3 +760,128 @@ int match_pathspec_attrs(struct index_state *istate,
 
 	return 1;
 }
+
+/*
+ * This is basically a strcmp, but we do not want the caller
+ * to have to terminate "a", so we pretend as if it had a NUL.
+ */
+static int pathspec_trie_cmp(const char *a, size_t a_len,
+			     const char *b)
+{
+	int ret = strncmp(a, b, a_len);
+	return ret ?
+		ret :
+		(unsigned char)0 - (unsigned char )b[a_len];
+}
+
+/*
+ * Do a binary search on one level of the pathspec_trie. If found,
+ * returns the offset of the item in the entry list. If not found,
+ * return a negative value encoding the offset where it would be inserted
+ * (you can recover the true offset with "-pos - 1").
+ */
+int pathspec_trie_lookup(const struct pathspec_trie *parent,
+			 const char *path, size_t len)
+{
+	int lo = 0, hi = parent->nr;
+	while (lo < hi) {
+		int mi = lo + ((hi - lo) / 2);
+		int cmp;
+
+		cmp = pathspec_trie_cmp(path, len, parent->entries[mi]->path);
+		if (!cmp)
+			return mi;
+		if (cmp < 0)
+			hi = mi;
+		else
+			lo = mi + 1;
+	}
+	return -lo - 1;
+}
+
+static struct pathspec_trie *alloc_pathspec_trie(const char *path, size_t len)
+{
+	struct pathspec_trie *ret = xcalloc(1, sizeof(*ret) + len);
+	memcpy(ret->path, path, len);
+	return ret;
+}
+
+/*
+ * Add "path" to the trie rooted at "t".
+ */
+static void add_pathspec_trie(struct pathspec_trie *t, const char *path)
+{
+	/*
+	 * Special case the empty path (i.e., "."), as our splitting algorithm
+	 * below assumes at least one component.
+	 */
+	if (!*path) {
+		t->terminal = 1;
+		return;
+	}
+
+	while (1) {
+		const char *slash = strchrnul(path, '/');
+		size_t len = slash - path;
+		int pos;
+
+		pos = pathspec_trie_lookup(t, path, len);
+		if (pos < 0) {
+			ALLOC_GROW(t->entries, t->nr + 1, t->alloc);
+
+			pos = -pos - 1;
+			if (pos < t->nr)
+				memmove(t->entries + pos + 1,
+					t->entries + pos,
+					sizeof(*t->entries) * (t->nr - pos));
+			t->entries[pos] = alloc_pathspec_trie(path, len);
+			t->nr++;
+		}
+
+		t = t->entries[pos];
+		path += len;
+
+		if (!*path) {
+			t->must_be_dir = 0;
+			t->terminal = 1;
+			return;
+		}
+
+		while (*path == '/')
+			path++;
+		if (!*path) {
+			/*
+			 * if we were already a terminal, then do not set
+			 * must_be_dir; we are "foo/", but we already had a
+			 * pathspec "foo", which is a superset of us.
+			 */
+			if (!t->terminal)
+				t->must_be_dir = 1;
+			t->terminal = 1;
+			return;
+		}
+	}
+}
+
+struct pathspec_trie *build_pathspec_trie(const struct pathspec *pathspec)
+{
+	struct pathspec_trie *ret;
+	int i;
+
+	/* we only make a trie for plain-vanilla pathspecs */
+	if (pathspec->has_wildcard || (pathspec->magic & ~PATHSPEC_LITERAL))
+		return NULL;
+
+	ret = alloc_pathspec_trie("", 0);
+
+	/*
+	 * XXX we could construct the trie more efficiently by creating each
+	 * node with all of its entries in sorted order. But this is much
+	 * simpler, and since we only do this once at the start of a traversal,
+	 * it's probably fast enough.
+	 */
+	for (i = 0; i < pathspec->nr; i++)
+		add_pathspec_trie(ret, pathspec->items[i].match);
+
+	return ret;
+}

@@ -22,6 +22,14 @@ struct index_state;
 
 #define PATHSPEC_ONESTAR 1	/* the pathspec pattern satisfies GFNM_ONESTAR */
 
+struct pathspec_trie {
+	struct pathspec_trie **entries;
+	int nr, alloc;
+	unsigned terminal:1,
+		 must_be_dir:1;
+	char path[FLEX_ARRAY];
+};
+
 /**
  * See glossary-context.txt for the syntax of pathspec.
  * In memory, a pathspec set is represented by "struct pathspec" and is

@@ -172,4 +180,8 @@ int match_pathspec_attrs(struct index_state *istate,
 			 const char *name, int namelen,
 			 const struct pathspec_item *item);
 
+struct pathspec_trie *build_pathspec_trie(const struct pathspec *);
+int pathspec_trie_lookup(const struct pathspec_trie *pst,
+			 const char *path, size_t len);
+
 #endif /* PATHSPEC_H */

@@ -0,0 +1,98 @@
+#include "test-tool.h"
+#include "pathspec.h"
+
+static const char usage_msg[] =
+"test-tool pathspec trie [pathspecs...] -- [paths....]";
+
+/*
+ * XXX Yuck. This is a lot of complicated code specific to our test. Even if it
+ * runs correctly, we have no real guarantee that the actual trie users are
+ * doing it right. And reusing their code is tough, because it happens as part
+ * of their own traversals (e.g., we walk the pathspec trie while walking the
+ * tree objects themselves).
+ *
+ * This whole test program should probably go away in favor of directly testing
+ * the tree-diff code.
+ */
+static int trie_match(const struct pathspec_trie *pst,
+		      const char *path)
+{
+	int pathlen = strlen(path);
+	int is_dir = 0;
+
+	if (pathlen > 0 && path[pathlen-1] == '/') {
+		is_dir = 1;
+		pathlen--;
+	}
+
+	while (pathlen) {
+		const char *slash = memchr(path, '/', pathlen);
+		int component_len;
+		int pos;
+
+		if (slash)
+			component_len = slash - path;
+		else
+			component_len = pathlen;
+
+		pos = pathspec_trie_lookup(pst, path, component_len);
+		if (pos < 0)
+			return 0;
+
+		pst = pst->entries[pos];
+		path += component_len;
+		pathlen -= component_len;
+
+		while (pathlen && *path == '/') {
+			path++;
+			pathlen--;
+		}
+
+		if (pst->terminal) {
+			if (!pst->must_be_dir)
+				return 1;
+			if (pathlen)
+				return 1;
+			return is_dir;
+		}
+	}
+	return 0;
+}
+
+static int cmd_trie(const char **argv)
+{
+	const char **specs, **paths;
+	struct pathspec pathspec;
+	struct pathspec_trie *trie;
+
+	paths = specs = argv;
+	while (*paths && strcmp(*paths, "--"))
+		paths++;
+	if (*paths)
+		*paths++ = NULL;
+
+	parse_pathspec(&pathspec, 0, 0, "", specs);
+	trie = build_pathspec_trie(&pathspec);
+	if (!trie)
+		die("unable to make trie from pathspec");
+
+	for (; *paths; paths++) {
+		if (trie_match(trie, *paths))
+			printf("yes\n");
+		else
+			printf("no\n");
+	}
+	return 0;
+}
+
+int cmd__pathspec(int argc, const char **argv)
+{
+	const char *cmd = argv[1];
+
+	if (!cmd)
+		usage(usage_msg);
+	else if (!strcmp(cmd, "trie"))
+		return cmd_trie(argv + 2);
+	else
+		die("unknown cmd: %s", cmd);
+}

@@ -47,6 +47,7 @@ static struct test_cmd cmds[] = {
 	{ "parse-options", cmd__parse_options },
 	{ "parse-pathspec-file", cmd__parse_pathspec_file },
 	{ "path-utils", cmd__path_utils },
+	{ "pathspec", cmd__pathspec },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
 	{ "prio-queue", cmd__prio_queue },

@@ -35,6 +35,7 @@ int cmd__oidmap(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);
 int cmd__parse_pathspec_file(int argc, const char** argv);
+int cmd__pathspec(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);

@@ -0,0 +1,57 @@
+#!/bin/sh
+
+test_description='test optimized pathspec trie lookup'
+. ./test-lib.sh
+
+# This is a basic lookup test; the offsets are there to provide
+# some variation in where we land in our binary search.
+ps="faa fzz foo/bar foo/baa foo/bzz"
+for offset in a "a b" "a b c"; do
+	test_expect_success "lookups with ps=$offset $ps" "
+		cat >expect <<-\\EOF &&
+		no
+		yes
+		yes
+		no
+		EOF
+		test-tool pathspec trie $offset $ps -- f faa foo/bar foo/baz >actual &&
+		test_cmp expect actual
+	"
+done
+
+test_expect_success 'pathspecs match by prefix' '
+	cat >expect <<-\EOF &&
+	yes
+	yes
+	yes
+	EOF
+	test-tool pathspec trie foo -- foo foo/bar foo/with/deep/subdirs >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'trailing slash sets must_be_dir' '
+	cat >expect <<-\EOF &&
+	no
+	yes
+	yes
+	EOF
+	test-tool pathspec trie dir/ -- dir dir/ dir/foo
+'
+
+test_expect_success 'overlapping pathspecs allow the "loose" side' '
+	echo yes >expect &&
+	test-tool pathspec trie foo foo/ -- foo >actual &&
+	test_cmp expect actual &&
+	test-tool pathspec trie foo/ foo -- foo >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success '"." at the root matches everything' '
+	cat >expect <<-\EOF &&
+	yes
+	yes
+	EOF
+	test-tool pathspec trie . -- foo foo/bar
+'
+
+test_done

@@ -639,6 +639,8 @@ void parse_pathspec(struct pathspec *pathspec,
 			BUG("PATHSPEC_MAXDEPTH_VALID and PATHSPEC_KEEP_ORDER are incompatible");
 		QSORT(pathspec->items, pathspec->nr, pathspec_item_cmp);
 	}
+
+	pathspec->trie = build_pathspec_trie(pathspec);
 }
 
 void parse_pathspec_file(struct pathspec *pathspec, unsigned magic_mask,

@@ -61,6 +61,7 @@ struct pathspec {
 		} *attr_match;
 		struct attr_check *attr_check;
 	} *items;
+	struct pathspec_trie *trie;
 };
 
 #define GUARD_PATHSPEC(ps, mask) \

@@ -63,7 +63,6 @@ static int cmd_trie(const char **argv)
 {
 	const char **specs, **paths;
 	struct pathspec pathspec;
-	struct pathspec_trie *trie;
 
 	paths = specs = argv;
 	while (*paths && strcmp(*paths, "--"))

@@ -72,12 +71,11 @@ static int cmd_trie(const char **argv)
 		*paths++ = NULL;
 
 	parse_pathspec(&pathspec, 0, 0, "", specs);
-	trie = build_pathspec_trie(&pathspec);
-	if (!trie)
+	if (!pathspec.trie)
 		die("unable to make trie from pathspec");
 
 	for (; *paths; paths++) {
-		if (trie_match(trie, *paths))
+		if (trie_match(pathspec.trie, *paths))
 			printf("yes\n");
 		else
 			printf("no\n");

@@ -0,0 +1,26 @@
+#!/bin/sh
+
+test_description='diff performance with many pathspecs'
+. ./perf-lib.sh
+
+test_perf_default_repo
+
+sizes='1 2 4 8 16 32 64 128 256 512 1024'
+
+test_expect_success 'create pathspec lists' '
+	git ls-tree --name-only -r HEAD >all &&
+	for i in $sizes; do
+		{
+			printf "%s\n" -- &&
+			head -$i all
+		} >ps-$i
+	done
+'
+
+for i in $sizes; do
+	test_perf "size=$i" "
+		git rev-list HEAD --stdin <ps-$i >/dev/null
+	"
+done
+
+test_done

@@ -28,7 +28,8 @@
 static struct combine_diff_path *ll_diff_tree_paths(
 	struct combine_diff_path *p, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
-	struct strbuf *base, struct diff_options *opt);
+	struct strbuf *base, struct diff_options *opt,
+	struct pathspec_trie *pst);
 static void ll_diff_tree_oid(const struct object_id *old_oid,
 			     const struct object_id *new_oid,
 			     struct strbuf *base, struct diff_options *opt);

@@ -179,7 +180,7 @@ static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 	struct strbuf *base, struct diff_options *opt, int nparent,
 	struct tree_desc *t, struct tree_desc *tp,
-	int imin)
+	int imin, struct pathspec_trie *pst)
 {
 	unsigned short mode;
 	const char *path;

@@ -283,23 +284,95 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 			parents_oid[i] = tpi_valid ? &tp[i].entry.oid : NULL;
 		}
 
+		/*
+		 * As we recurse through the tree objects, move through
+		 * our pathspec trie, as well. The one exception is if
+		 * we already hit a terminal node. This means we have a strict
+		 * prefix match (e.g., "foo/" matched, and we are in
+		 * "foo/bar"). We don't have to bother with checking the
+		 * pathspec at all anymore in that case.
+		 *
+		 * Note that the "pos < 0" case should not happen here,
+		 * as we would have skipped the tree entry as uninteresting
+		 * earlier. As a safety measure, we turn off the trie
+		 * optimization and fall back to doing regular pathspec
+		 * matching in this case.
+		 */
+		if (pst && !pst->terminal) {
+			int pos = pathspec_trie_lookup(pst, path, pathlen);
+			if (pos < 0)
+				pst = NULL;
+			else
+				pst = pst->entries[pos];
+		}
+
 		strbuf_add(base, path, pathlen);
 		strbuf_addch(base, '/');
-		p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
+		p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt, pst);
 		FAST_ARRAY_FREE(parents_oid, nparent);
 	}
 
 	strbuf_setlen(base, old_baselen);
 	return p;
 }
 
+static enum interesting match_pathspec_trie_entry(struct pathspec_trie *pst,
+						  const struct name_entry *entry)
+{
+	int pos;
+
+	/*
+	 * If our base directory is matched, then everything below is
+	 * interesting (i.e., a prefix match).
+	 */
+	if (pst->terminal)
+		return entry_interesting;
+
+	/*
+	 * Otherwise, look up the actual entry. If we don't mention it at all,
+	 * it's definitely uninteresting. But furthermore, if we're at the
+	 * end of our sorted list, we know that nothing after it is
+	 * interesting, either.
+	 *
+	 * XXX It seems like we should have to make special consideration here
+	 * for the sort order of trees. But tree_entry_interesting does not
+	 * seem to. Is it OK, is tree_entry_interesting buggy too, or am I
+	 * reading it wrong? This optimization gives substantial speedups, so
+	 * we really need to keep it or something like it.
+	 */
+	pos = pathspec_trie_lookup(pst, entry->path, tree_entry_len(entry));
+	if (pos < 0) {
+		if (-pos - 1 == pst->nr)
+			return all_entries_not_interesting;
+		else
+			return entry_not_interesting;
+	}
+
+	/*
+	 * We definitely have the entry. First we have to resolve any directory
+	 * restrictions; if there aren't any, then it's definitely interesting.
+	 *
+	 * Note that we do not need to check the "terminal" flag of the
+	 * resulting trie node. If it is not set, then this particular entry
+	 * does not match our pathspec, but we do still need to traverse
+	 * through it to get to the interesting things inside. It's interesting
+	 * either way.
+	 */
+	if (pst->entries[pos]->must_be_dir)
+		return !!S_ISDIR(entry->mode);
+	return entry_interesting;
+}
+
 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
-			       struct diff_options *opt)
+			       struct diff_options *opt,
+			       struct pathspec_trie *pst)
 {
 	enum interesting match;
 
 	while (t->size) {
-		match = tree_entry_interesting(opt->repo->index, &t->entry,
+		match = pst ?
+			match_pathspec_trie_entry(pst, &t->entry) :
+			tree_entry_interesting(opt->repo->index, &t->entry,
 					       base, 0, &opt->pathspec);
 		if (match) {
 			if (match == all_entries_not_interesting)

@@ -310,7 +383,6 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 	}
 }
 
-
 /*
  * generate paths for combined diff D(sha1,parents_oid[])
  *

@@ -406,7 +478,8 @@ static inline void update_tp_entries(struct tree_desc *tp, int nparent)
 static struct combine_diff_path *ll_diff_tree_paths(
 	struct combine_diff_path *p, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
-	struct strbuf *base, struct diff_options *opt)
+	struct strbuf *base, struct diff_options *opt,
+	struct pathspec_trie *pst)
 {
 	struct tree_desc t, *tp;
 	void *ttree, **tptree;

@@ -438,9 +511,9 @@ static struct combine_diff_path *ll_diff_tree_paths(
 			break;
 
 		if (opt->pathspec.nr) {
-			skip_uninteresting(&t, base, opt);
+			skip_uninteresting(&t, base, opt, pst);
 			for (i = 0; i < nparent; i++)
-				skip_uninteresting(&tp[i], base, opt);
+				skip_uninteresting(&tp[i], base, opt, pst);
 		}
 
 		/* comparing is finished when all trees are done */

@@ -505,7 +578,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 
 			/* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
 			p = emit_path(p, base, opt, nparent,
-					&t, tp, imin);
+					&t, tp, imin, pst);
 
 		skip_emit_t_tp:
 			/* t↓,  ∀ pi=p[imin]  pi↓ */

@@ -517,7 +590,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		else if (cmp < 0) {
 			/* D += "+t" */
 			p = emit_path(p, base, opt, nparent,
-					&t, /*tp=*/NULL, -1);
+					&t, /*tp=*/NULL, -1, pst);
 
 			/* t↓ */
 			update_tree_entry(&t);

@@ -533,7 +606,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 			}
 
 			p = emit_path(p, base, opt, nparent,
-					/*t=*/NULL, tp, imin);
+					/*t=*/NULL, tp, imin, pst);
 
 		skip_emit_tp:
 			/* ∀ pi=p[imin]  pi↓ */

@@ -555,7 +628,10 @@ struct combine_diff_path *diff_tree_paths(
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt)
 {
-	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt);
+	/* XXX if base is not empty, we need to walk its paths
+	 * to get to the right level of the trie */
+	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt,
+			       opt->pathspec.trie);
 
 	/*
 	 * free pre-allocated last element, if any