[PATCH v4 0/4] per-worktree bisection refs

[PATCH v4 0/4] per-worktree bisection refs

[David Turner]

This reroll includes changes suggested by Duy Nguyen:

A. Path normalization (partial).
B. Rearrangement of common_list struct to make formatting prettier.

It also includes a test style fix suggested by Eric Sunshine and
others: a bogus test_must_fail on a non-git command has been replaced
by a two-step check.

[PATCH v4 1/4] refs: clean up common_list

[David Turner]

Instead of common_list having formatting like ! and /, use a struct to
hold common_list data in a structured form.

We don't use 'exclude' yet; instead, we keep the old codepath that
handles info/sparse-checkout and logs/HEAD.  Later, we will use exclude.

Signed-off-by: David Turner <dturner@twopensource.com>
---
 path.c | 58 +++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 37 insertions(+), 21 deletions(-)

diff --git a/path.c b/path.c
index 10f4cbf..d24bfa2 100644
--- a/path.c
+++ b/path.c
@@ -91,35 +91,51 @@ static void replace_dir(struct strbuf *buf, int len, const char *newdir)
 		buf->buf[newlen] = '/';
 }
 
-static const char *common_list[] = {
-	"/branches", "/hooks", "/info", "!/logs", "/lost-found",
-	"/objects", "/refs", "/remotes", "/worktrees", "/rr-cache", "/svn",
-	"config", "!gc.pid", "packed-refs", "shallow",
-	NULL
+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;
+};
+
+struct common_dir common_list[] = {
+	{ 0, 1, 0, "branches" },
+	{ 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, 0, "lost-found" },
+	{ 0, 1, 0, "objects" },
+	{ 0, 1, 0, "refs" },
+	{ 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, 0, 0, NULL }
 };
 
 static void update_common_dir(struct strbuf *buf, int git_dir_len)
 {
 	char *base = buf->buf + git_dir_len;
-	const char **p;
+	const struct common_dir *p;
 
 	if (is_dir_file(base, "logs", "HEAD") ||
 	    is_dir_file(base, "info", "sparse-checkout"))
 		return;	/* keep this in $GIT_DIR */
-	for (p = common_list; *p; p++) {
-		const char *path = *p;
-		int is_dir = 0;
-		if (*path == '!')
-			path++;
-		if (*path == '/') {
-			path++;
-			is_dir = 1;
-		}
-		if (is_dir && dir_prefix(base, path)) {
+	for (p = common_list; p->dirname; p++) {
+		const char *path = p->dirname;
+		if (p->is_dir && dir_prefix(base, path)) {
 			replace_dir(buf, git_dir_len, get_git_common_dir());
 			return;
 		}
-		if (!is_dir && !strcmp(base, path)) {
+		if (!p->is_dir && !strcmp(base, path)) {
 			replace_dir(buf, git_dir_len, get_git_common_dir());
 			return;
 		}
@@ -129,16 +145,16 @@ static void update_common_dir(struct strbuf *buf, int git_dir_len)
 void report_linked_checkout_garbage(void)
 {
 	struct strbuf sb = STRBUF_INIT;
-	const char **p;
+	const struct common_dir *p;
 	int len;
 
 	if (!git_common_dir_env)
 		return;
 	strbuf_addf(&sb, "%s/", get_git_dir());
 	len = sb.len;
-	for (p = common_list; *p; p++) {
-		const char *path = *p;
-		if (*path == '!')
+	for (p = common_list; p->dirname; p++) {
+		const char *path = p->dirname;
+		if (p->ignore_garbage)
 			continue;
 		strbuf_setlen(&sb, len);
 		strbuf_addstr(&sb, path);
-- 
2.4.2.622.gac67c30-twtrsrc

[PATCH v4 2/4] path: optimize common dir checking

[David Turner]

Instead of a linear search over common_list to check whether
a path is common, use a trie.  The trie search operates on
path prefixes, and handles excludes.

Signed-off-by: David Turner <dturner@twopensource.com>
---
 path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----
 t/t0060-path-utils.sh |   1 +
 2 files changed, 213 insertions(+), 14 deletions(-)

diff --git a/path.c b/path.c
index d24bfa2..c7a4c40 100644
--- a/path.c
+++ b/path.c
@@ -121,25 +121,223 @@ struct common_dir common_list[] = {
 	{ 0, 0, 0, NULL }
 };
 
-static void update_common_dir(struct strbuf *buf, int git_dir_len)
+/*
+ * A compressed trie.  A trie node consists of zero or more characters that
+ * are common to all elements with this prefix, optionally followed by some
+ * children.  If value is not NULL, the trie node is a terminal node.
+ *
+ * For example, consider the following set of strings:
+ * abc
+ * def
+ * definite
+ * definition
+ *
+ * The trie would look look like:
+ * root: len = 0, value = (something), children a and d non-NULL.
+ *    a: len = 2, contents = bc
+ *    d: len = 2, contents = ef, children i non-NULL, value = (something)
+ *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL
+ *           e: len = 0, children all NULL, value = (something)
+ *           i: len = 2, contents = on, children all NULL, value = (something)
+ */
+struct trie {
+	struct trie *children[256];
+	int len;
+	char *contents;
+	void *value;
+};
+
+static struct trie *make_trie_node(const char *key, void *value)
 {
-	char *base = buf->buf + git_dir_len;
-	const struct common_dir *p;
+	struct trie *new_node = xcalloc(1, sizeof(*new_node));
+	new_node->len = strlen(key);
+	if (new_node->len) {
+		new_node->contents = xmalloc(new_node->len);
+		memcpy(new_node->contents, key, new_node->len);
+	}
+	new_node->value = value;
+	return new_node;
+}
 
-	if (is_dir_file(base, "logs", "HEAD") ||
-	    is_dir_file(base, "info", "sparse-checkout"))
-		return;	/* keep this in $GIT_DIR */
-	for (p = common_list; p->dirname; p++) {
-		const char *path = p->dirname;
-		if (p->is_dir && dir_prefix(base, path)) {
-			replace_dir(buf, git_dir_len, get_git_common_dir());
-			return;
+/*
+ * Add a key/value pair to a trie.  The key is assumed to be \0-terminated.
+ * If there was an existing value for this key, return it.
+ */
+static void *add_to_trie(struct trie *root, const char *key, void *value)
+{
+	struct trie *child;
+	void *old;
+	int i;
+
+	if (!*key) {
+		/* we have reached the end of the key */
+		old = root->value;
+		root->value = value;
+		return old;
+	}
+
+	for (i = 0; i < root->len; ++i) {
+		if (root->contents[i] == key[i])
+			continue;
+
+		/*
+		 * Split this node: child will contain this node's
+		 * existing children.
+		 */
+		child = malloc(sizeof(*child));
+		memcpy(child->children, root->children, sizeof(root->children));
+
+		child->len = root->len - i - 1;
+		if (child->len) {
+			child->contents = strndup(root->contents + i + 1,
+						   child->len);
 		}
-		if (!p->is_dir && !strcmp(base, path)) {
-			replace_dir(buf, git_dir_len, get_git_common_dir());
-			return;
+		child->value = root->value;
+		root->value = NULL;
+		root->len = i;
+
+		memset(root->children, 0, sizeof(root->children));
+		root->children[(unsigned char)root->contents[i]] = child;
+
+		/* This is the newly-added child. */
+		root->children[(unsigned char)key[i]] =
+			make_trie_node(key + i + 1, value);
+		return NULL;
+	}
+
+	/* We have matched the entire compressed section */
+	if (key[i]) {
+		child = root->children[(unsigned char)key[root->len]];
+		if (child) {
+			return add_to_trie(child, key + root->len + 1, value);
+		} else {
+			child = make_trie_node(key + root->len + 1, value);
+			root->children[(unsigned char)key[root->len]] = child;
+			return NULL;
 		}
 	}
+
+	old = root->value;
+	root->value = value;
+	return old;
+}
+
+typedef int (*match_fn)(const char *unmatched, void *data, 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.
+ *
+ * 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    |
+ * |-----------------|------------|---------------|--------------|
+ *
+ */
+static int trie_find(struct trie *root, const char *key, match_fn fn,
+		     void *baton)
+{
+	int i;
+	int result;
+	struct trie *child;
+
+	if (!*key) {
+		/* we have reached the end of the key */
+		if (root->value && !root->len)
+			return fn(key, root->value, baton);
+		else
+			return -1;
+	}
+
+	for (i = 0; i < root->len; ++i) {
+		/* Partial path normalization: skip consecutive slashes. */
+		if (key[i] == '/' && key[i+1] == '/') {
+			key++;
+			continue;
+		}
+		if (root->contents[i] != key[i])
+			return -1;
+	}
+
+	/* Matched the entire compressed section */
+	key += i;
+	if (!*key)
+		/* End of key */
+		return fn(key, root->value, baton);
+
+	/* Partial path normalization: skip consecutive slashes */
+	while (key[0] == '/' && key[1] == '/')
+		key ++;
+
+	child = root->children[(unsigned char)*key];
+	if (child)
+		result = trie_find(child, key + 1, fn, baton);
+	else
+		result = -1;
+
+	if (result >= 0 || (*key != '/' && *key != 0))
+		return result;
+	if (root->value)
+		return fn(key, root->value, baton);
+	else
+		return -1;
+}
+
+static struct trie common_trie;
+static int common_trie_done_setup;
+
+static void init_common_trie(void)
+{
+	struct common_dir *p;
+
+	if (common_trie_done_setup)
+		return;
+
+	for (p = common_list; p->dirname; p++)
+		add_to_trie(&common_trie, p->dirname, p);
+
+	common_trie_done_setup = 1;
+}
+
+/*
+ * Helper function for update_common_dir: returns 1 if the dir
+ * prefix is common.
+ */
+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;
+
+	if (!dir->is_dir && unmatched[0] == 0)
+		return !dir->exclude;
+
+	return 0;
+}
+
+static void update_common_dir(struct strbuf *buf, int git_dir_len)
+{
+	char *base = buf->buf + git_dir_len;
+	init_common_trie();
+	if (trie_find(&common_trie, base, check_common, NULL) > 0)
+		replace_dir(buf, git_dir_len, get_git_common_dir());
 }
 
 void report_linked_checkout_garbage(void)
diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh
index 93605f4..1ca49e1 100755
--- a/t/t0060-path-utils.sh
+++ b/t/t0060-path-utils.sh
@@ -271,6 +271,7 @@ test_git_path GIT_COMMON_DIR=bar objects/bar              bar/objects/bar
 test_git_path GIT_COMMON_DIR=bar info/exclude             bar/info/exclude
 test_git_path GIT_COMMON_DIR=bar info/grafts              bar/info/grafts
 test_git_path GIT_COMMON_DIR=bar info/sparse-checkout     .git/info/sparse-checkout
+test_git_path GIT_COMMON_DIR=bar info//sparse-checkout    .git/info//sparse-checkout
 test_git_path GIT_COMMON_DIR=bar remotes/bar              bar/remotes/bar
 test_git_path GIT_COMMON_DIR=bar branches/bar             bar/branches/bar
 test_git_path GIT_COMMON_DIR=bar logs/refs/heads/master   bar/logs/refs/heads/master
-- 
2.4.2.622.gac67c30-twtrsrc

[PATCH v4 3/4] refs: make refs/worktree/* per-worktree

[David Turner]

We need a place to stick refs for bisects in progress that is not
shared between worktrees.  So we use the refs/worktree/ hierarchy.

The is_per_worktree_ref function and associated docs learn that
refs/worktree/ is per-worktree, as does the git_path code in path.c

The ref-packing functions learn that per-worktree refs should not be
packed (since packed-refs is common rather than per-worktree).

Since refs/worktree is per-worktree, logs/refs/worktree should be too.

Signed-off-by: David Turner <dturner@twopensource.com>
---
 Documentation/glossary-content.txt |  5 +++--
 path.c                             |  2 ++
 refs.c                             | 32 +++++++++++++++++++++++++++++++-
 t/t0060-path-utils.sh              |  5 +++++
 t/t1400-update-ref.sh              | 19 +++++++++++++++++++
 t/t3210-pack-refs.sh               |  7 +++++++
 6 files changed, 67 insertions(+), 3 deletions(-)

diff --git a/Documentation/glossary-content.txt b/Documentation/glossary-content.txt
index 8c6478b..5c707e6 100644
--- a/Documentation/glossary-content.txt
+++ b/Documentation/glossary-content.txt
@@ -413,8 +413,9 @@ exclude;;
 
 [[def_per_worktree_ref]]per-worktree ref::
 	Refs that are per-<<def_working_tree,worktree>>, rather than
-	global.  This is presently only <<def_HEAD,HEAD>>, but might
-	later include other unusual refs.
+	global.  This is presently only <<def_HEAD,HEAD>> and any refs
+	that start with `refs/worktree/`, but might later include other
+	unusual refs.
 
 [[def_pseudoref]]pseudoref::
 	Pseudorefs are a class of files under `$GIT_DIR` which behave
diff --git a/path.c b/path.c
index c7a4c40..acac7b1 100644
--- a/path.c
+++ b/path.c
@@ -107,9 +107,11 @@ struct common_dir common_list[] = {
 	{ 0, 0, 1, "info/sparse-checkout" },
 	{ 1, 1, 0, "logs" },
 	{ 1, 1, 1, "logs/HEAD" },
+	{ 0, 1, 1,  "logs/refs/worktree" },
 	{ 0, 1, 0, "lost-found" },
 	{ 0, 1, 0, "objects" },
 	{ 0, 1, 0, "refs" },
+	{ 0, 1, 1, "refs/worktree", },
 	{ 0, 1, 0, "remotes" },
 	{ 0, 1, 0, "worktrees" },
 	{ 0, 1, 0, "rr-cache" },
diff --git a/refs.c b/refs.c
index e6fc3fe..30331bc 100644
--- a/refs.c
+++ b/refs.c
@@ -298,6 +298,11 @@ struct ref_entry {
 };
 
 static void read_loose_refs(const char *dirname, struct ref_dir *dir);
+static int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len);
+static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,
+					  const char *dirname, size_t len,
+					  int incomplete);
+static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry);
 
 static struct ref_dir *get_ref_dir(struct ref_entry *entry)
 {
@@ -306,6 +311,24 @@ static struct ref_dir *get_ref_dir(struct ref_entry *entry)
 	dir = &entry->u.subdir;
 	if (entry->flag & REF_INCOMPLETE) {
 		read_loose_refs(entry->name, dir);
+
+		/*
+		 * Manually add refs/worktree, which, being
+		 * per-worktree, might not appear in the directory
+		 * listing for refs/ in the main repo.
+		 */
+		if (!strcmp(entry->name, "refs/")) {
+			int pos = search_ref_dir(dir, "refs/worktree/", 14);
+			if (pos < 0) {
+				struct ref_entry *child_entry;
+				child_entry = create_dir_entry(dir->ref_cache,
+							       "refs/worktree/",
+							       14, 1);
+				add_entry_to_dir(dir, child_entry);
+				read_loose_refs("refs/worktree",
+						&child_entry->u.subdir);
+			}
+		}
 		entry->flag &= ~REF_INCOMPLETE;
 	}
 	return dir;
@@ -2643,6 +2666,8 @@ struct pack_refs_cb_data {
 	struct ref_to_prune *ref_to_prune;
 };
 
+static int is_per_worktree_ref(const char *refname);
+
 /*
  * An each_ref_entry_fn that is run over loose references only.  If
  * the loose reference can be packed, add an entry in the packed ref
@@ -2656,6 +2681,10 @@ static int pack_if_possible_fn(struct ref_entry *entry, void *cb_data)
 	struct ref_entry *packed_entry;
 	int is_tag_ref = starts_with(entry->name, "refs/tags/");
 
+	/* Do not pack per-worktree refs: */
+	if (is_per_worktree_ref(entry->name))
+		return 0;
+
 	/* ALWAYS pack tags */
 	if (!(cb->flags & PACK_REFS_ALL) && !is_tag_ref)
 		return 0;
@@ -2850,7 +2879,8 @@ static int delete_ref_loose(struct ref_lock *lock, int flag, struct strbuf *err)
 
 static int is_per_worktree_ref(const char *refname)
 {
-	return !strcmp(refname, "HEAD");
+	return !strcmp(refname, "HEAD") ||
+		starts_with(refname, "refs/worktree/");
 }
 
 static int is_pseudoref_syntax(const char *refname)
diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh
index 1ca49e1..b2d2005 100755
--- a/t/t0060-path-utils.sh
+++ b/t/t0060-path-utils.sh
@@ -266,6 +266,10 @@ test_expect_success 'setup common repository' 'git --git-dir=bar init'
 test_git_path GIT_COMMON_DIR=bar index                    .git/index
 test_git_path GIT_COMMON_DIR=bar HEAD                     .git/HEAD
 test_git_path GIT_COMMON_DIR=bar logs/HEAD                .git/logs/HEAD
+test_git_path GIT_COMMON_DIR=bar logs/refs/worktree/foo   .git/logs/refs/worktree/foo
+test_git_path GIT_COMMON_DIR=bar logs/refs/worktre/foo    bar/logs/refs/worktre/foo
+test_git_path GIT_COMMON_DIR=bar logs/refs/worktre        bar/logs/refs/worktre
+test_git_path GIT_COMMON_DIR=bar logs/refs/worktreefoo    bar/logs/refs/worktreefoo
 test_git_path GIT_COMMON_DIR=bar objects                  bar/objects
 test_git_path GIT_COMMON_DIR=bar objects/bar              bar/objects/bar
 test_git_path GIT_COMMON_DIR=bar info/exclude             bar/info/exclude
@@ -276,6 +280,7 @@ test_git_path GIT_COMMON_DIR=bar remotes/bar              bar/remotes/bar
 test_git_path GIT_COMMON_DIR=bar branches/bar             bar/branches/bar
 test_git_path GIT_COMMON_DIR=bar logs/refs/heads/master   bar/logs/refs/heads/master
 test_git_path GIT_COMMON_DIR=bar refs/heads/master        bar/refs/heads/master
+test_git_path GIT_COMMON_DIR=bar refs/worktree/foo        .git/refs/worktree/foo
 test_git_path GIT_COMMON_DIR=bar hooks/me                 bar/hooks/me
 test_git_path GIT_COMMON_DIR=bar config                   bar/config
 test_git_path GIT_COMMON_DIR=bar packed-refs              bar/packed-refs
diff --git a/t/t1400-update-ref.sh b/t/t1400-update-ref.sh
index 9d21c19..6dc29e6 100755
--- a/t/t1400-update-ref.sh
+++ b/t/t1400-update-ref.sh
@@ -1131,4 +1131,23 @@ test_expect_success ULIMIT_FILE_DESCRIPTORS 'large transaction deleting branches
 )
 '
 
+test_expect_success 'handle per-worktree refs in refs/worktree' '
+	git commit --allow-empty -m "initial commit" &&
+	git worktree add -b branch worktree &&
+	(
+		cd worktree &&
+		git commit --allow-empty -m "test commit"  &&
+		git for-each-ref >for-each-ref.out &&
+		! grep refs/worktree for-each-ref.out &&
+		git update-ref refs/worktree/something HEAD &&
+		git rev-parse refs/worktree/something >../worktree-head &&
+		git for-each-ref | grep refs/worktree/something
+	) &&
+	test_path_is_missing .git/refs/worktree &&
+	test_must_fail git rev-parse refs/worktree/something &&
+	git update-ref refs/worktree/something HEAD &&
+	git rev-parse refs/worktree/something >main-head &&
+	! test_cmp main-head worktree-head
+'
+
 test_done
diff --git a/t/t3210-pack-refs.sh b/t/t3210-pack-refs.sh
index 8aae98d..c54cd29 100755
--- a/t/t3210-pack-refs.sh
+++ b/t/t3210-pack-refs.sh
@@ -160,6 +160,13 @@ test_expect_success 'pack ref directly below refs/' '
 	test_path_is_missing .git/refs/top
 '
 
+test_expect_success 'do not pack ref in refs/worktree' '
+	git update-ref refs/worktree/local HEAD &&
+	git pack-refs --all --prune &&
+	! grep refs/worktree/local .git/packed-refs >/dev/null &&
+	test_path_is_file .git/refs/worktree/local
+'
+
 test_expect_success 'disable reflogs' '
 	git config core.logallrefupdates false &&
 	rm -rf .git/logs
-- 
2.4.2.622.gac67c30-twtrsrc

[PATCH v4 4/4] bisect: make bisection refs per-worktree

[David Turner]

Using the new refs/worktree/ refs, make bisection per-worktree.

Signed-off-by: David Turner <dturner@twopensource.com>
---
 Documentation/git-bisect.txt       |  4 ++--
 Documentation/rev-list-options.txt | 14 +++++++-------
 bisect.c                           |  2 +-
 builtin/rev-parse.c                |  6 ++++--
 git-bisect.sh                      | 14 +++++++-------
 revision.c                         |  2 +-
 t/t6030-bisect-porcelain.sh        | 20 ++++++++++----------
 7 files changed, 32 insertions(+), 30 deletions(-)

diff --git a/Documentation/git-bisect.txt b/Documentation/git-bisect.txt
index e97f2de..f0c52d1 100644
--- a/Documentation/git-bisect.txt
+++ b/Documentation/git-bisect.txt
@@ -82,7 +82,7 @@ to ask for the next commit that needs testing.
 
 Eventually there will be no more revisions left to inspect, and the
 command will print out a description of the first bad commit. The
-reference `refs/bisect/bad` will be left pointing at that commit.
+reference `refs/worktree/bisect/bad` will be left pointing at that commit.
 
 
 Bisect reset
@@ -373,7 +373,7 @@ on a single line.
 ------------
 $ git bisect start HEAD <known-good-commit> [ <boundary-commit> ... ] --no-checkout
 $ git bisect run sh -c '
-	GOOD=$(git for-each-ref "--format=%(objectname)" refs/bisect/good-*) &&
+	GOOD=$(git for-each-ref "--format=%(objectname)" refs/worktree/bisect/good-*) &&
 	git rev-list --objects BISECT_HEAD --not $GOOD >tmp.$$ &&
 	git pack-objects --stdout >/dev/null <tmp.$$
 	rc=$?
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index a9b808f..1175960 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -183,9 +183,9 @@ explicitly.
 
 ifndef::git-rev-list[]
 --bisect::
-	Pretend as if the bad bisection ref `refs/bisect/bad`
+	Pretend as if the bad bisection ref `refs/worktree/bisect/bad`
 	was listed and as if it was followed by `--not` and the good
-	bisection refs `refs/bisect/good-*` on the command
+	bisection refs `refs/worktree/bisect/good-*` on the command
 	line. Cannot be combined with --first-parent.
 endif::git-rev-list[]
 
@@ -548,10 +548,10 @@ Bisection Helpers
 --bisect::
 	Limit output to the one commit object which is roughly halfway between
 	included and excluded commits. Note that the bad bisection ref
-	`refs/bisect/bad` is added to the included commits (if it
-	exists) and the good bisection refs `refs/bisect/good-*` are
+	`refs/worktree/bisect/bad` is added to the included commits (if it
+	exists) and the good bisection refs `refs/worktree/bisect/good-*` are
 	added to the excluded commits (if they exist). Thus, supposing there
-	are no refs in `refs/bisect/`, if
+	are no refs in `refs/worktree/bisect/`, if
 +
 -----------------------------------------------------------------------
 	$ git rev-list --bisect foo ^bar ^baz
@@ -571,7 +571,7 @@ one. Cannot be combined with --first-parent.
 
 --bisect-vars::
 	This calculates the same as `--bisect`, except that refs in
-	`refs/bisect/` are not used, and except that this outputs
+	`refs/worktree/bisect/` are not used, and except that this outputs
 	text ready to be eval'ed by the shell. These lines will assign the
 	name of the midpoint revision to the variable `bisect_rev`, and the
 	expected number of commits to be tested after `bisect_rev` is tested
@@ -584,7 +584,7 @@ one. Cannot be combined with --first-parent.
 --bisect-all::
 	This outputs all the commit objects between the included and excluded
 	commits, ordered by their distance to the included and excluded
-	commits. Refs in `refs/bisect/` are not used. The farthest
+	commits. Refs in `refs/worktree/bisect/` are not used. The farthest
 	from them is displayed first. (This is the only one displayed by
 	`--bisect`.)
 +
diff --git a/bisect.c b/bisect.c
index 33ac88d..dbe3461 100644
--- a/bisect.c
+++ b/bisect.c
@@ -425,7 +425,7 @@ static int register_ref(const char *refname, const struct object_id *oid,
 
 static int read_bisect_refs(void)
 {
-	return for_each_ref_in("refs/bisect/", register_ref, NULL);
+	return for_each_ref_in("refs/worktree/bisect/", register_ref, NULL);
 }
 
 static void read_bisect_paths(struct argv_array *array)
diff --git a/builtin/rev-parse.c b/builtin/rev-parse.c
index 02d747d..3240ddf 100644
--- a/builtin/rev-parse.c
+++ b/builtin/rev-parse.c
@@ -663,8 +663,10 @@ int cmd_rev_parse(int argc, const char **argv, const char *prefix)
 				continue;
 			}
 			if (!strcmp(arg, "--bisect")) {
-				for_each_ref_in("refs/bisect/bad", show_reference, NULL);
-				for_each_ref_in("refs/bisect/good", anti_reference, NULL);
+				for_each_ref_in("refs/worktree/bisect/bad",
+						show_reference, NULL);
+				for_each_ref_in("refs/worktree/bisect/good",
+						anti_reference, NULL);
 				continue;
 			}
 			if (starts_with(arg, "--branches=")) {
diff --git a/git-bisect.sh b/git-bisect.sh
index ea63223..c16433d 100755
--- a/git-bisect.sh
+++ b/git-bisect.sh
@@ -210,7 +210,7 @@ bisect_write() {
 		*)
 			die "$(eval_gettext "Bad bisect_write argument: \$state")" ;;
 	esac
-	git update-ref "refs/bisect/$tag" "$rev" || exit
+	git update-ref "refs/worktree/bisect/$tag" "$rev" || exit
 	echo "# $state: $(git show-branch $rev)" >>"$GIT_DIR/BISECT_LOG"
 	test -n "$nolog" || echo "git bisect $state $rev" >>"$GIT_DIR/BISECT_LOG"
 }
@@ -282,8 +282,8 @@ bisect_state() {
 
 bisect_next_check() {
 	missing_good= missing_bad=
-	git show-ref -q --verify refs/bisect/$TERM_BAD || missing_bad=t
-	test -n "$(git for-each-ref "refs/bisect/$TERM_GOOD-*")" || missing_good=t
+	git show-ref -q --verify refs/worktree/bisect/$TERM_BAD || missing_bad=t
+	test -n "$(git for-each-ref "refs/worktree/bisect/$TERM_GOOD-*")" || missing_good=t
 
 	case "$missing_good,$missing_bad,$1" in
 	,,*)
@@ -341,15 +341,15 @@ bisect_next() {
 	# Check if we should exit because bisection is finished
 	if test $res -eq 10
 	then
-		bad_rev=$(git show-ref --hash --verify refs/bisect/$TERM_BAD)
+		bad_rev=$(git show-ref --hash --verify refs/worktree/bisect/$TERM_BAD)
 		bad_commit=$(git show-branch $bad_rev)
 		echo "# first $TERM_BAD commit: $bad_commit" >>"$GIT_DIR/BISECT_LOG"
 		exit 0
 	elif test $res -eq 2
 	then
 		echo "# only skipped commits left to test" >>"$GIT_DIR/BISECT_LOG"
-		good_revs=$(git for-each-ref --format="%(objectname)" "refs/bisect/$TERM_GOOD-*")
-		for skipped in $(git rev-list refs/bisect/$TERM_BAD --not $good_revs)
+		good_revs=$(git for-each-ref --format="%(objectname)" "refs/worktree/bisect/$TERM_GOOD-*")
+		for skipped in $(git rev-list refs/worktree/bisect/$TERM_BAD --not $good_revs)
 		do
 			skipped_commit=$(git show-branch $skipped)
 			echo "# possible first $TERM_BAD commit: $skipped_commit" >>"$GIT_DIR/BISECT_LOG"
@@ -412,7 +412,7 @@ Try 'git bisect reset <commit>'.")"
 
 bisect_clean_state() {
 	# There may be some refs packed during bisection.
-	git for-each-ref --format='%(refname) %(objectname)' refs/bisect/\* |
+	git for-each-ref --format='%(refname) %(objectname)' refs/worktree/bisect/\* |
 	while read ref hash
 	do
 		git update-ref -d $ref $hash || exit
diff --git a/revision.c b/revision.c
index b6b2cf7..974a11f 100644
--- a/revision.c
+++ b/revision.c
@@ -2084,7 +2084,7 @@ extern void read_bisect_terms(const char **bad, const char **good);
 static int for_each_bisect_ref(const char *submodule, each_ref_fn fn, void *cb_data, const char *term) {
 	struct strbuf bisect_refs = STRBUF_INIT;
 	int status;
-	strbuf_addf(&bisect_refs, "refs/bisect/%s", term);
+	strbuf_addf(&bisect_refs, "refs/worktree/bisect/%s", term);
 	status = for_each_ref_in_submodule(submodule, bisect_refs.buf, fn, cb_data);
 	strbuf_release(&bisect_refs);
 	return status;
diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 9e2c203..bfd5463 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -68,7 +68,7 @@ test_expect_success 'bisect fails if given any junk instead of revs' '
 	git bisect reset &&
 	test_must_fail git bisect start foo $HASH1 -- &&
 	test_must_fail git bisect start $HASH4 $HASH1 bar -- &&
-	test -z "$(git for-each-ref "refs/bisect/*")" &&
+	test -z "$(git for-each-ref "refs/worktree/bisect/*")" &&
 	test -z "$(ls .git/BISECT_* 2>/dev/null)" &&
 	git bisect start &&
 	test_must_fail git bisect good foo $HASH1 &&
@@ -77,7 +77,7 @@ test_expect_success 'bisect fails if given any junk instead of revs' '
 	test_must_fail git bisect bad $HASH3 $HASH4 &&
 	test_must_fail git bisect skip bar $HASH3 &&
 	test_must_fail git bisect skip $HASH1 foo &&
-	test -z "$(git for-each-ref "refs/bisect/*")" &&
+	test -z "$(git for-each-ref "refs/worktree/bisect/*")" &&
 	git bisect good $HASH1 &&
 	git bisect bad $HASH4
 '
@@ -115,7 +115,7 @@ test_expect_success 'bisect reset removes packed refs' '
 	git pack-refs --all --prune &&
 	git bisect next &&
 	git bisect reset &&
-	test -z "$(git for-each-ref "refs/bisect/*")" &&
+	test -z "$(git for-each-ref "refs/worktree/bisect/*")" &&
 	test -z "$(git for-each-ref "refs/heads/bisect")"
 '
 
@@ -126,7 +126,7 @@ test_expect_success 'bisect reset removes bisect state after --no-checkout' '
 	git bisect bad $HASH3 &&
 	git bisect next &&
 	git bisect reset &&
-	test -z "$(git for-each-ref "refs/bisect/*")" &&
+	test -z "$(git for-each-ref "refs/worktree/bisect/*")" &&
 	test -z "$(git for-each-ref "refs/heads/bisect")" &&
 	test -z "$(git for-each-ref "BISECT_HEAD")"
 '
@@ -176,7 +176,7 @@ test_expect_success 'bisect start: no ".git/BISECT_START" if checkout error' '
 	git branch > branch.output &&
 	grep "* other" branch.output > /dev/null &&
 	test_must_fail test -e .git/BISECT_START &&
-	test -z "$(git for-each-ref "refs/bisect/*")" &&
+	test -z "$(git for-each-ref "refs/worktree/bisect/*")" &&
 	git checkout HEAD hello
 '
 
@@ -671,7 +671,7 @@ test_expect_success 'bisect: --no-checkout - target before breakage' '
 	git bisect bad BISECT_HEAD &&
 	check_same BROKEN_HASH5 BISECT_HEAD &&
 	git bisect bad BISECT_HEAD &&
-	check_same BROKEN_HASH5 bisect/bad &&
+	check_same BROKEN_HASH5 refs/worktree/bisect/bad &&
 	git bisect reset
 '
 
@@ -682,7 +682,7 @@ test_expect_success 'bisect: --no-checkout - target in breakage' '
 	git bisect bad BISECT_HEAD &&
 	check_same BROKEN_HASH5 BISECT_HEAD &&
 	git bisect good BISECT_HEAD &&
-	check_same BROKEN_HASH6 bisect/bad &&
+	check_same BROKEN_HASH6 refs/worktree/bisect/bad &&
 	git bisect reset
 '
 
@@ -693,7 +693,7 @@ test_expect_success 'bisect: --no-checkout - target after breakage' '
 	git bisect good BISECT_HEAD &&
 	check_same BROKEN_HASH8 BISECT_HEAD &&
 	git bisect good BISECT_HEAD &&
-	check_same BROKEN_HASH9 bisect/bad &&
+	check_same BROKEN_HASH9 refs/worktree/bisect/bad &&
 	git bisect reset
 '
 
@@ -702,13 +702,13 @@ test_expect_success 'bisect: demonstrate identification of damage boundary' "
 	git checkout broken &&
 	git bisect start broken master --no-checkout &&
 	git bisect run \"\$SHELL_PATH\" -c '
-		GOOD=\$(git for-each-ref \"--format=%(objectname)\" refs/bisect/good-*) &&
+		GOOD=\$(git for-each-ref \"--format=%(objectname)\" refs/worktree/bisect/good-*) &&
 		git rev-list --objects BISECT_HEAD --not \$GOOD >tmp.\$\$ &&
 		git pack-objects --stdout >/dev/null < tmp.\$\$
 		rc=\$?
 		rm -f tmp.\$\$
 		test \$rc = 0' &&
-	check_same BROKEN_HASH6 bisect/bad &&
+	check_same BROKEN_HASH6 refs/worktree/bisect/bad &&
 	git bisect reset
 "
 
-- 
2.4.2.622.gac67c30-twtrsrc

Re: [PATCH v4 2/4] path: optimize common dir checking

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

> Instead of a linear search over common_list to check whether
> a path is common, use a trie.  The trie search operates on
> path prefixes, and handles excludes.
>
> Signed-off-by: David Turner <dturner@twopensource.com>
> ---
>  path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----
>  t/t0060-path-utils.sh |   1 +
>  2 files changed, 213 insertions(+), 14 deletions(-)
>
> diff --git a/path.c b/path.c
> index d24bfa2..c7a4c40 100644
> --- a/path.c
> +++ b/path.c
> @@ -121,25 +121,223 @@ struct common_dir common_list[] = {
>  	{ 0, 0, 0, NULL }
>  };
>  
> -static void update_common_dir(struct strbuf *buf, int git_dir_len)
> +/*
> + * A compressed trie.  A trie node consists of zero or more characters that
> + * are common to all elements with this prefix, optionally followed by some
> + * children.  If value is not NULL, the trie node is a terminal node.
> + *
> + * For example, consider the following set of strings:
> + * abc
> + * def
> + * definite
> + * definition
> + *
> + * The trie would look look like:
> + * root: len = 0, value = (something), children a and d non-NULL.

"value = NULL", as there is no empty string registered in the trie?

> + *    a: len = 2, contents = bc

"value = NULL" here, too (just showing I am following along, not
just skimming)?

> + *    d: len = 2, contents = ef, children i non-NULL, value = (something)
> + *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL
> + *           e: len = 0, children all NULL, value = (something)
> + *           i: len = 2, contents = on, children all NULL, value = (something)
> + */
> +struct trie {
> +	struct trie *children[256];
> +	int len;
> +	char *contents;
> +	void *value;
> +};
> +
> +static struct trie *make_trie_node(const char *key, void *value)
>  {
> -	char *base = buf->buf + git_dir_len;
> -	const struct common_dir *p;
> +	struct trie *new_node = xcalloc(1, sizeof(*new_node));
> +	new_node->len = strlen(key);
> +	if (new_node->len) {
> +		new_node->contents = xmalloc(new_node->len);
> +		memcpy(new_node->contents, key, new_node->len);
> +	}
> +	new_node->value = value;
> +	return new_node;
> +}
>  
> -	if (is_dir_file(base, "logs", "HEAD") ||
> -	    is_dir_file(base, "info", "sparse-checkout"))
> -		return;	/* keep this in $GIT_DIR */
> -	for (p = common_list; p->dirname; p++) {
> -		const char *path = p->dirname;
> -		if (p->is_dir && dir_prefix(base, path)) {
> -			replace_dir(buf, git_dir_len, get_git_common_dir());
> -			return;
> +/*
> + * Add a key/value pair to a trie.  The key is assumed to be \0-terminated.
> + * If there was an existing value for this key, return it.
> + */
> +static void *add_to_trie(struct trie *root, const char *key, void *value)
> +{
> +	struct trie *child;
> +	void *old;
> +	int i;
> +
> +	if (!*key) {
> +		/* we have reached the end of the key */
> +		old = root->value;
> +		root->value = value;
> +		return old;
> +	}
> +
> +	for (i = 0; i < root->len; ++i) {
> +		if (root->contents[i] == key[i])
> +			continue;
> +
> +		/*
> +		 * Split this node: child will contain this node's
> +		 * existing children.
> +		 */
> +		child = malloc(sizeof(*child));
> +		memcpy(child->children, root->children, sizeof(root->children));
> +
> +		child->len = root->len - i - 1;
> +		if (child->len) {
> +			child->contents = strndup(root->contents + i + 1,
> +						   child->len);
>  		}
> -		if (!p->is_dir && !strcmp(base, path)) {
> -			replace_dir(buf, git_dir_len, get_git_common_dir());
> -			return;
> +		child->value = root->value;
> +		root->value = NULL;
> +		root->len = i;
> +
> +		memset(root->children, 0, sizeof(root->children));
> +		root->children[(unsigned char)root->contents[i]] = child;
> +
> +		/* This is the newly-added child. */
> +		root->children[(unsigned char)key[i]] =
> +			make_trie_node(key + i + 1, value);
> +		return NULL;
> +	}
> +
> +	/* We have matched the entire compressed section */
> +	if (key[i]) {
> +		child = root->children[(unsigned char)key[root->len]];
> +		if (child) {
> +			return add_to_trie(child, key + root->len + 1, value);
> +		} else {
> +			child = make_trie_node(key + root->len + 1, value);
> +			root->children[(unsigned char)key[root->len]] = child;
> +			return NULL;
>  		}
>  	}
> +
> +	old = root->value;
> +	root->value = value;
> +	return old;
> +}
> +
> +typedef int (*match_fn)(const char *unmatched, void *data, 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.
> + *
> + * 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    |
> + * |-----------------|------------|---------------|--------------|
> + *
> + */
> +static int trie_find(struct trie *root, const char *key, match_fn fn,
> +		     void *baton)
> +{
> +	int i;
> +	int result;
> +	struct trie *child;
> +
> +	if (!*key) {
> +		/* we have reached the end of the key */
> +		if (root->value && !root->len)
> +			return fn(key, root->value, baton);
> +		else
> +			return -1;
> +	}
> +
> +	for (i = 0; i < root->len; ++i) {
> +		/* Partial path normalization: skip consecutive slashes. */
> +		if (key[i] == '/' && key[i+1] == '/') {
> +			key++;
> +			continue;
> +		}
> +		if (root->contents[i] != key[i])
> +			return -1;
> +	}
> +
> +	/* Matched the entire compressed section */
> +	key += i;
> +	if (!*key)
> +		/* End of key */
> +		return fn(key, root->value, baton);
> +
> +	/* Partial path normalization: skip consecutive slashes */
> +	while (key[0] == '/' && key[1] == '/')
> +		key ++;

These "skipping consecutive slashes" inside this function is cute.
I would have expected me to react "Eek, Ugly" to it, but somehow I
didn't find them ugly.

> +	child = root->children[(unsigned char)*key];
> +	if (child)
> +		result = trie_find(child, key + 1, fn, baton);
> +	else
> +		result = -1;
> +
> +	if (result >= 0 || (*key != '/' && *key != 0))
> +		return result;
> +	if (root->value)
> +		return fn(key, root->value, baton);
> +	else
> +		return -1;
> +}
> +
> +static struct trie common_trie;
> +static int common_trie_done_setup;
> +
> +static void init_common_trie(void)
> +{
> +	struct common_dir *p;
> +
> +	if (common_trie_done_setup)
> +		return;
> +
> +	for (p = common_list; p->dirname; p++)
> +		add_to_trie(&common_trie, p->dirname, p);
> +
> +	common_trie_done_setup = 1;
> +}

I somehow wonder if we'd want to precomute the trie at the build
time, though ;-)

> +/*
> + * Helper function for update_common_dir: returns 1 if the dir
> + * prefix is common.
> + */
> +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;
> +
> +	if (!dir->is_dir && unmatched[0] == 0)
> +		return !dir->exclude;
> +
> +	return 0;
> +}
> +
> +static void update_common_dir(struct strbuf *buf, int git_dir_len)
> +{
> +	char *base = buf->buf + git_dir_len;
> +	init_common_trie();
> +	if (trie_find(&common_trie, base, check_common, NULL) > 0)
> +		replace_dir(buf, git_dir_len, get_git_common_dir());
>  }

Thanks for a pleasant read.

>  
>  void report_linked_checkout_garbage(void)
> diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh
> index 93605f4..1ca49e1 100755
> --- a/t/t0060-path-utils.sh
> +++ b/t/t0060-path-utils.sh
> @@ -271,6 +271,7 @@ test_git_path GIT_COMMON_DIR=bar objects/bar              bar/objects/bar
>  test_git_path GIT_COMMON_DIR=bar info/exclude             bar/info/exclude
>  test_git_path GIT_COMMON_DIR=bar info/grafts              bar/info/grafts
>  test_git_path GIT_COMMON_DIR=bar info/sparse-checkout     .git/info/sparse-checkout
> +test_git_path GIT_COMMON_DIR=bar info//sparse-checkout    .git/info//sparse-checkout
>  test_git_path GIT_COMMON_DIR=bar remotes/bar              bar/remotes/bar
>  test_git_path GIT_COMMON_DIR=bar branches/bar             bar/branches/bar
>  test_git_path GIT_COMMON_DIR=bar logs/refs/heads/master   bar/logs/refs/heads/master

Re: [PATCH v4 2/4] path: optimize common dir checking

[David Turner]

On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:
> > + * For example, consider the following set of strings:
> > + * abc
> > + * def
> > + * definite
> > + * definition
> > + *
> > + * The trie would look look like:
> > + * root: len = 0, value = (something), children a and d non-NULL.
> 
> "value = NULL", as there is no empty string registered in the trie?

Indeed.

> > + *    a: len = 2, contents = bc
> 
> "value = NULL" here, too (just showing I am following along, not
> just skimming)?

Yep.

<snip>
> > +	/* Partial path normalization: skip consecutive slashes */
> > +	while (key[0] == '/' && key[1] == '/')
> > +		key ++;
> 
> These "skipping consecutive slashes" inside this function is cute.
> I would have expected me to react "Eek, Ugly" to it, but somehow I
> didn't find them ugly.

It's right on the cute/ugly edge for me too.

<snip>

> I somehow wonder if we'd want to precomute the trie at the build
> time, though ;-)

LOL.

<snip>
> Thanks for a pleasant read.

Thank you!  I'll re-roll with those last two fixes (re value=NULL)
tomorrow-ish.

Re: [PATCH v4 2/4] path: optimize common dir checking

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:
>
>> Thanks for a pleasant read.
>
> Thank you!  I'll re-roll with those last two fixes (re value=NULL)
> tomorrow-ish.

If these two "value = NULL" are the only things, I can locally fix
them up.  No need to resend.

Thanks.

Re: [PATCH v4 2/4] path: optimize common dir checking

[David Turner]

On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:
> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:
> > > + * For example, consider the following set of strings:
> > > + * abc
> > > + * def
> > > + * definite
> > > + * definition
> > > + *
> > > + * The trie would look look like:
> > > + * root: len = 0, value = (something), children a and d non-NULL.
> > 
> > "value = NULL", as there is no empty string registered in the trie?
> 
> Indeed.
> 
> > > + *    a: len = 2, contents = bc
> > 
> > "value = NULL" here, too (just showing I am following along, not
> > just skimming)?
> 
> Yep.

No, wait. value should be non-NULL, since abc is in the string set. 

Re: [PATCH v4 2/4] path: optimize common dir checking

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

> On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:
>> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:
>> > > + * For example, consider the following set of strings:
>> > > + * abc
>> > > + * def
>> > > + * definite
>> > > + * definition
>> > > + *
>> > > + * The trie would look look like:
>> > > + * root: len = 0, value = (something), children a and d non-NULL.
>> > 
>> > "value = NULL", as there is no empty string registered in the trie?
>> 
>> Indeed.
>> 
>> > > + *    a: len = 2, contents = bc
>> > 
>> > "value = NULL" here, too (just showing I am following along, not
>> > just skimming)?
>> 
>> Yep.
>
> No, wait. value should be non-NULL, since abc is in the string set. 

True.  Here is what I came up with on top of your original.  



 path.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/path.c b/path.c
index 4100ba6..ce0530b 100644
--- a/path.c
+++ b/path.c
@@ -133,12 +133,13 @@ struct common_dir common_list[] = {
  * definition
  *
  * The trie would look look like:
- * root: len = 0, value = (something), children a and d non-NULL.
- *    a: len = 2, contents = bc
- *    d: len = 2, contents = ef, children i non-NULL, value = (something)
+ * root: len = 0, children a and d non-NULL, value = NULL.
+ *    a: len = 2, contents = bc, value = (data for "abc")
+ *    d: len = 2, contents = ef, children i non-NULL, value = (data for "def")
  *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL
- *           e: len = 0, children all NULL, value = (something)
- *           i: len = 2, contents = on, children all NULL, value = (something)
+ *           e: len = 0, children all NULL, value = (data for "definite")
+ *           i: len = 2, contents = on, children all NULL,
+ *              value = (data for "definition")
  */
 struct trie {
 	struct trie *children[256];

Re: [PATCH v4 2/4] path: optimize common dir checking

[David Turner]

On Fri, 2015-08-28 at 09:39 -0700, Junio C Hamano wrote:
> David Turner <dturner@twopensource.com> writes:
> 
> > On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:
> >> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:
> >> > > + * For example, consider the following set of strings:
> >> > > + * abc
> >> > > + * def
> >> > > + * definite
> >> > > + * definition
> >> > > + *
> >> > > + * The trie would look look like:
> >> > > + * root: len = 0, value = (something), children a and d non-NULL.
> >> > 
> >> > "value = NULL", as there is no empty string registered in the trie?
> >> 
> >> Indeed.
> >> 
> >> > > + *    a: len = 2, contents = bc
> >> > 
> >> > "value = NULL" here, too (just showing I am following along, not
> >> > just skimming)?
> >> 
> >> Yep.
> >
> > No, wait. value should be non-NULL, since abc is in the string set. 
> 
> True.  Here is what I came up with on top of your original.  
> 
> 
> 
>  path.c | 11 ++++++-----
>  1 file changed, 6 insertions(+), 5 deletions(-)
> 
> diff --git a/path.c b/path.c
> index 4100ba6..ce0530b 100644
> --- a/path.c
> +++ b/path.c
> @@ -133,12 +133,13 @@ struct common_dir common_list[] = {
>   * definition
>   *
>   * The trie would look look like:
> - * root: len = 0, value = (something), children a and d non-NULL.
> - *    a: len = 2, contents = bc
> - *    d: len = 2, contents = ef, children i non-NULL, value = (something)
> + * root: len = 0, children a and d non-NULL, value = NULL.
> + *    a: len = 2, contents = bc, value = (data for "abc")
> + *    d: len = 2, contents = ef, children i non-NULL, value = (data for "def")
>   *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL
> - *           e: len = 0, children all NULL, value = (something)
> - *           i: len = 2, contents = on, children all NULL, value = (something)
> + *           e: len = 0, children all NULL, value = (data for "definite")
> + *           i: len = 2, contents = on, children all NULL,
> + *              value = (data for "definition")
>   */
>  struct trie {
>  	struct trie *children[256];

LGTM.

Re: [PATCH v4 2/4] path: optimize common dir checking

[Torsten Bögershausen]

On 26.08.15 21:46, David Turner wrote:
> Instead of a linear search over common_list to check whether
> a path is common, use a trie.  The trie search operates on
> path prefixes, and handles excludes.
> 
> Signed-off-by: David Turner <dturner@twopensource.com>
> ---
>  path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----
>  t/t0060-path-utils.sh |   1 +
>  2 files changed, 213 insertions(+), 14 deletions(-)
> 
> diff --git a/path.c b/path.c


> +		child->len = root->len - i - 1;
> +		if (child->len) {
> +			child->contents = strndup(root->contents + i + 1,
> +						   child->len);
>  		}
Could we use xtrndup() instead of strndup() ?
(Otherwise it won't compile under Mac OS here)

Re: [PATCH v4 2/4] path: optimize common dir checking

[David Turner]

On Sun, 2015-08-30 at 08:25 +0200, Torsten Bögershausen wrote:
> On 26.08.15 21:46, David Turner wrote:
> > Instead of a linear search over common_list to check whether
> > a path is common, use a trie.  The trie search operates on
> > path prefixes, and handles excludes.
> > 
> > Signed-off-by: David Turner <dturner@twopensource.com>
> > ---
> >  path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----
> >  t/t0060-path-utils.sh |   1 +
> >  2 files changed, 213 insertions(+), 14 deletions(-)
> > 
> > diff --git a/path.c b/path.c
> 
> 
> > +		child->len = root->len - i - 1;
> > +		if (child->len) {
> > +			child->contents = strndup(root->contents + i + 1,
> > +						   child->len);
> >  		}
> Could we use xtrndup() instead of strndup() ?
> (Otherwise it won't compile under Mac OS here)

Thanks.  Junio, can we squash in the following?  (Or let me know and I
can resend the series with both this and your patch squashed)

---
 path.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/path.c b/path.c
index 777af35..21306ab 100644
--- a/path.c
+++ b/path.c
@@ -191,7 +191,7 @@ static void *add_to_trie(struct trie *root, const
char *key, void *value)
 
 		child->len = root->len - i - 1;
 		if (child->len) {
-			child->contents = strndup(root->contents + i + 1,
+			child->contents = xstrndup(root->contents + i + 1,
 						   child->len);
 		}
 		child->value = root->value;