Merge branch 'sg/dir-trie-fixes'

Code clean-up and a bugfix in the logic used to tell worktree local
and repository global refs apart.

* sg/dir-trie-fixes:
  path.c: don't call the match function without value in trie_find()
  path.c: clarify two field names in 'struct common_dir'
  path.c: mark 'logs/HEAD' in 'common_list' as file
  path.c: clarify trie_find()'s in-code comment
  Documentation: mention more worktree-specific exceptions

1 files changed, 67 insertions, 55 deletions

diff --git a/path.c b/path.c
index e3da1f3..e21b00c 100644
--- a/path.c
+++ b/path.c
@@ -101,36 +101,36 @@ struct common_dir {
 	/* Not considered garbage for report_linked_checkout_garbage */
 	unsigned ignore_garbage:1;
 	unsigned is_dir:1;
-	/* Not common even though its parent is */
-	unsigned exclude:1;
-	const char *dirname;
+	/* Belongs to the common dir, though it may contain paths that don't */
+	unsigned is_common:1;
+	const char *path;
 };
 
 static struct common_dir common_list[] = {
-	{ 0, 1, 0, "branches" },
-	{ 0, 1, 0, "common" },
-	{ 0, 1, 0, "hooks" },
-	{ 0, 1, 0, "info" },
-	{ 0, 0, 1, "info/sparse-checkout" },
-	{ 1, 1, 0, "logs" },
-	{ 1, 1, 1, "logs/HEAD" },
-	{ 0, 1, 1, "logs/refs/bisect" },
-	{ 0, 1, 1, "logs/refs/rewritten" },
-	{ 0, 1, 1, "logs/refs/worktree" },
-	{ 0, 1, 0, "lost-found" },
-	{ 0, 1, 0, "objects" },
-	{ 0, 1, 0, "refs" },
-	{ 0, 1, 1, "refs/bisect" },
-	{ 0, 1, 1, "refs/rewritten" },
-	{ 0, 1, 1, "refs/worktree" },
-	{ 0, 1, 0, "remotes" },
-	{ 0, 1, 0, "worktrees" },
-	{ 0, 1, 0, "rr-cache" },
-	{ 0, 1, 0, "svn" },
-	{ 0, 0, 0, "config" },
-	{ 1, 0, 0, "gc.pid" },
-	{ 0, 0, 0, "packed-refs" },
-	{ 0, 0, 0, "shallow" },
+	{ 0, 1, 1, "branches" },
+	{ 0, 1, 1, "common" },
+	{ 0, 1, 1, "hooks" },
+	{ 0, 1, 1, "info" },
+	{ 0, 0, 0, "info/sparse-checkout" },
+	{ 1, 1, 1, "logs" },
+	{ 1, 0, 0, "logs/HEAD" },
+	{ 0, 1, 0, "logs/refs/bisect" },
+	{ 0, 1, 0, "logs/refs/rewritten" },
+	{ 0, 1, 0, "logs/refs/worktree" },
+	{ 0, 1, 1, "lost-found" },
+	{ 0, 1, 1, "objects" },
+	{ 0, 1, 1, "refs" },
+	{ 0, 1, 0, "refs/bisect" },
+	{ 0, 1, 0, "refs/rewritten" },
+	{ 0, 1, 0, "refs/worktree" },
+	{ 0, 1, 1, "remotes" },
+	{ 0, 1, 1, "worktrees" },
+	{ 0, 1, 1, "rr-cache" },
+	{ 0, 1, 1, "svn" },
+	{ 0, 0, 1, "config" },
+	{ 1, 0, 1, "gc.pid" },
+	{ 0, 0, 1, "packed-refs" },
+	{ 0, 0, 1, "shallow" },
 	{ 0, 0, 0, NULL }
 };
 
@@ -236,30 +236,41 @@ static void *add_to_trie(struct trie *root, const char *key, void *value)
 	return old;
 }
 
-typedef int (*match_fn)(const char *unmatched, void *data, void *baton);
+typedef int (*match_fn)(const char *unmatched, void *value, void *baton);
 
 /*
  * Search a trie for some key.  Find the longest /-or-\0-terminated
- * prefix of the key for which the trie contains a value.  Call fn
- * with the unmatched portion of the key and the found value, and
- * return its return value.  If there is no such prefix, return -1.
+ * prefix of the key for which the trie contains a value.  If there is
+ * no such prefix, return -1.  Otherwise call fn with the unmatched
+ * portion of the key and the found value.  If fn returns 0 or
+ * positive, then return its return value.  If fn returns negative,
+ * then call fn with the next-longest /-terminated prefix of the key
+ * (i.e. a parent directory) for which the trie contains a value, and
+ * handle its return value the same way.  If there is no shorter
+ * /-terminated prefix with a value left, then return the negative
+ * return value of the most recent fn invocation.
  *
  * The key is partially normalized: consecutive slashes are skipped.
  *
- * For example, consider the trie containing only [refs,
- * refs/worktree] (both with values).
- *
- * | key             | unmatched  | val from node | return value |
- * |-----------------|------------|---------------|--------------|
- * | a               | not called | n/a           | -1           |
- * | refs            | \0         | refs          | as per fn    |
- * | refs/           | /          | refs          | as per fn    |
- * | refs/w          | /w         | refs          | as per fn    |
- * | refs/worktree   | \0         | refs/worktree | as per fn    |
- * | refs/worktree/  | /          | refs/worktree | as per fn    |
- * | refs/worktree/a | /a         | refs/worktree | as per fn    |
- * |-----------------|------------|---------------|--------------|
+ * For example, consider the trie containing only [logs,
+ * logs/refs/bisect], both with values, but not logs/refs.
  *
+ * | key                | unmatched      | prefix to node   | return value |
+ * |--------------------|----------------|------------------|--------------|
+ * | a                  | not called     | n/a              | -1           |
+ * | logstore           | not called     | n/a              | -1           |
+ * | logs               | \0             | logs             | as per fn    |
+ * | logs/              | /              | logs             | as per fn    |
+ * | logs/refs          | /refs          | logs             | as per fn    |
+ * | logs/refs/         | /refs/         | logs             | as per fn    |
+ * | logs/refs/b        | /refs/b        | logs             | as per fn    |
+ * | logs/refs/bisected | /refs/bisected | logs             | as per fn    |
+ * | logs/refs/bisect   | \0             | logs/refs/bisect | as per fn    |
+ * | logs/refs/bisect/  | /              | logs/refs/bisect | as per fn    |
+ * | logs/refs/bisect/a | /a             | logs/refs/bisect | as per fn    |
+ * | (If fn in the previous line returns -1, then fn is called once more:) |
+ * | logs/refs/bisect/a | /refs/bisect/a | logs             | as per fn    |
+ * |--------------------|----------------|------------------|--------------|
  */
 static int trie_find(struct trie *root, const char *key, match_fn fn,
 		     void *baton)
@@ -288,9 +299,13 @@ static int trie_find(struct trie *root, const char *key, match_fn fn,
 
 	/* Matched the entire compressed section */
 	key += i;
-	if (!*key)
+	if (!*key) {
 		/* End of key */
-		return fn(key, root->value, baton);
+		if (root->value)
+			return fn(key, root->value, baton);
+		else
+			return -1;
+	}
 
 	/* Partial path normalization: skip consecutive slashes */
 	while (key[0] == '/' && key[1] == '/')
@@ -320,8 +335,8 @@ static void init_common_trie(void)
 	if (common_trie_done_setup)
 		return;
 
-	for (p = common_list; p->dirname; p++)
-		add_to_trie(&common_trie, p->dirname, p);
+	for (p = common_list; p->path; p++)
+		add_to_trie(&common_trie, p->path, p);
 
 	common_trie_done_setup = 1;
 }
@@ -334,14 +349,11 @@ static int check_common(const char *unmatched, void *value, void *baton)
 {
 	struct common_dir *dir = value;
 
-	if (!dir)
-		return 0;
-
 	if (dir->is_dir && (unmatched[0] == 0 || unmatched[0] == '/'))
-		return !dir->exclude;
+		return dir->is_common;
 
 	if (!dir->is_dir && unmatched[0] == 0)
-		return !dir->exclude;
+		return dir->is_common;
 
 	return 0;
 }
@@ -365,8 +377,8 @@ void report_linked_checkout_garbage(void)
 		return;
 	strbuf_addf(&sb, "%s/", get_git_dir());
 	len = sb.len;
-	for (p = common_list; p->dirname; p++) {
-		const char *path = p->dirname;
+	for (p = common_list; p->path; p++) {
+		const char *path = p->path;
 		if (p->ignore_garbage)
 			continue;
 		strbuf_setlen(&sb, len);