{"thread":{"id":"40236","subject":"(unknown)","startedAt":"2015-09-01T02:13:08Z","lastAt":"2015-10-05T20:43:21Z","messageCount":10,"participants":["David Turner","Junio C Hamano","Michael Haggerty"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"269072","messageId":"1441073591-639-1-git-send-email-dturner@twopensource.com","threadId":"40236","inReplyTo":null,"subject":"(unknown)","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-09-01T02:13:08Z","receivedAt":"2015-09-01T02:13:08Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"This version of the patch series squashes in Junio's comment fix and\nthe xstrndup fix.\n\nIn addition, it removes refs/worktree, and just makes refs/bisect\nper-worktree. If we later discover that other things need to be\nper-worktree, we can do refs/worktree, but for now, this is\nbackwards-compatible so we'll do this.\n"},{"id":"269073","messageId":"1441073591-639-2-git-send-email-dturner@twopensource.com","threadId":"40236","inReplyTo":"1441073591-639-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v5 1/3] refs: clean up common_list","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-09-01T02:13:09Z","receivedAt":"2015-09-01T02:13:09Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Instead of common_list having formatting like ! and /, use a struct to\nhold common_list data in a structured form.\n\nWe don't use 'exclude' yet; instead, we keep the old codepath that\nhandles info/sparse-checkout and logs/HEAD. Later, we will use exclude.\n\nSigned-off-by: David Turner \nSigned-off-by: Junio C Hamano \n---\n path.c | 58 +++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 37 insertions(+), 21 deletions(-)\n\ndiff --git a/path.c b/path.c\nindex 95acbaf..f1ffe37 100644\n--- a/path.c\n+++ b/path.c\n@@ -91,35 +91,51 @@ static void replace_dir(struct strbuf *buf, int len, const char *newdir)\n \t\tbuf->buf[newlen] = '/';\n }\n \n-static const char *common_list[] = {\n-\t\"/branches\", \"/hooks\", \"/info\", \"!/logs\", \"/lost-found\",\n-\t\"/objects\", \"/refs\", \"/remotes\", \"/worktrees\", \"/rr-cache\", \"/svn\",\n-\t\"config\", \"!gc.pid\", \"packed-refs\", \"shallow\",\n-\tNULL\n+struct common_dir {\n+\t/* Not considered garbage for report_linked_checkout_garbage */\n+\tunsigned ignore_garbage:1;\n+\tunsigned is_dir:1;\n+\t/* Not common even though its parent is */\n+\tunsigned exclude:1;\n+\tconst char *dirname;\n+};\n+\n+struct common_dir common_list[] = {\n+\t{ 0, 1, 0, \"branches\" },\n+\t{ 0, 1, 0, \"hooks\" },\n+\t{ 0, 1, 0, \"info\" },\n+\t{ 0, 0, 1, \"info/sparse-checkout\" },\n+\t{ 1, 1, 0, \"logs\" },\n+\t{ 1, 1, 1, \"logs/HEAD\" },\n+\t{ 0, 1, 0, \"lost-found\" },\n+\t{ 0, 1, 0, \"objects\" },\n+\t{ 0, 1, 0, \"refs\" },\n+\t{ 0, 1, 0, \"remotes\" },\n+\t{ 0, 1, 0, \"worktrees\" },\n+\t{ 0, 1, 0, \"rr-cache\" },\n+\t{ 0, 1, 0, \"svn\" },\n+\t{ 0, 0, 0, \"config\" },\n+\t{ 1, 0, 0, \"gc.pid\" },\n+\t{ 0, 0, 0, \"packed-refs\" },\n+\t{ 0, 0, 0, \"shallow\" },\n+\t{ 0, 0, 0, NULL }\n };\n \n static void update_common_dir(struct strbuf *buf, int git_dir_len)\n {\n \tchar *base = buf->buf + git_dir_len;\n-\tconst char **p;\n+\tconst struct common_dir *p;\n \n \tif (is_dir_file(base, \"logs\", \"HEAD\") ||\n \t is_dir_file(base, \"info\", \"sparse-checkout\"))\n \t\treturn;\t/* keep this in $GIT_DIR */\n-\tfor (p = common_list; *p; p++) {\n-\t\tconst char *path = *p;\n-\t\tint is_dir = 0;\n-\t\tif (*path == '!')\n-\t\t\tpath++;\n-\t\tif (*path == '/') {\n-\t\t\tpath++;\n-\t\t\tis_dir = 1;\n-\t\t}\n-\t\tif (is_dir && dir_prefix(base, path)) {\n+\tfor (p = common_list; p->dirname; p++) {\n+\t\tconst char *path = p->dirname;\n+\t\tif (p->is_dir && dir_prefix(base, path)) {\n \t\t\treplace_dir(buf, git_dir_len, get_git_common_dir());\n \t\t\treturn;\n \t\t}\n-\t\tif (!is_dir && !strcmp(base, path)) {\n+\t\tif (!p->is_dir && !strcmp(base, path)) {\n \t\t\treplace_dir(buf, git_dir_len, get_git_common_dir());\n \t\t\treturn;\n \t\t}\n@@ -129,16 +145,16 @@ static void update_common_dir(struct strbuf *buf, int git_dir_len)\n void report_linked_checkout_garbage(void)\n {\n \tstruct strbuf sb = STRBUF_INIT;\n-\tconst char **p;\n+\tconst struct common_dir *p;\n \tint len;\n \n \tif (!git_common_dir_env)\n \t\treturn;\n \tstrbuf_addf(&sb, \"%s/\", get_git_dir());\n \tlen = sb.len;\n-\tfor (p = common_list; *p; p++) {\n-\t\tconst char *path = *p;\n-\t\tif (*path == '!')\n+\tfor (p = common_list; p->dirname; p++) {\n+\t\tconst char *path = p->dirname;\n+\t\tif (p->ignore_garbage)\n \t\t\tcontinue;\n \t\tstrbuf_setlen(&sb, len);\n \t\tstrbuf_addstr(&sb, path);\n-- \n2.0.4.315.gad8727a-twtrsrc\n"},{"id":"269074","messageId":"1441073591-639-3-git-send-email-dturner@twopensource.com","threadId":"40236","inReplyTo":"1441073591-639-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v5 2/3] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-09-01T02:13:10Z","receivedAt":"2015-09-01T02:13:10Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Instead of a linear search over common_list to check whether\na path is common, use a trie. The trie search operates on\npath prefixes, and handles excludes.\n\nSigned-off-by: David Turner \nSigned-off-by: Junio C Hamano \n---\n path.c | 227 ++++++++++++++++++++++++++++++++++++++++++++++----\n t/t0060-path-utils.sh | 1 +\n 2 files changed, 214 insertions(+), 14 deletions(-)\n\ndiff --git a/path.c b/path.c\nindex f1ffe37..c87f44a 100644\n--- a/path.c\n+++ b/path.c\n@@ -121,25 +121,224 @@ struct common_dir common_list[] = {\n \t{ 0, 0, 0, NULL }\n };\n \n-static void update_common_dir(struct strbuf *buf, int git_dir_len)\n+/*\n+ * A compressed trie. A trie node consists of zero or more characters that\n+ * are common to all elements with this prefix, optionally followed by some\n+ * children. If value is not NULL, the trie node is a terminal node.\n+ *\n+ * For example, consider the following set of strings:\n+ * abc\n+ * def\n+ * definite\n+ * definition\n+ *\n+ * The trie would look look like:\n+ * root: len = 0, children a and d non-NULL, value = NULL.\n+ * a: len = 2, contents = bc, value = (data for \"abc\")\n+ * d: len = 2, contents = ef, children i non-NULL, value = (data for \"def\")\n+ * i: len = 3, contents = nit, children e and i non-NULL, value = NULL\n+ * e: len = 0, children all NULL, value = (data for \"definite\")\n+ * i: len = 2, contents = on, children all NULL,\n+ * value = (data for \"definition\")\n+ */\n+struct trie {\n+\tstruct trie *children[256];\n+\tint len;\n+\tchar *contents;\n+\tvoid *value;\n+};\n+\n+static struct trie *make_trie_node(const char *key, void *value)\n {\n-\tchar *base = buf->buf + git_dir_len;\n-\tconst struct common_dir *p;\n+\tstruct trie *new_node = xcalloc(1, sizeof(*new_node));\n+\tnew_node->len = strlen(key);\n+\tif (new_node->len) {\n+\t\tnew_node->contents = xmalloc(new_node->len);\n+\t\tmemcpy(new_node->contents, key, new_node->len);\n+\t}\n+\tnew_node->value = value;\n+\treturn new_node;\n+}\n \n-\tif (is_dir_file(base, \"logs\", \"HEAD\") ||\n-\t is_dir_file(base, \"info\", \"sparse-checkout\"))\n-\t\treturn;\t/* keep this in $GIT_DIR */\n-\tfor (p = common_list; p->dirname; p++) {\n-\t\tconst char *path = p->dirname;\n-\t\tif (p->is_dir && dir_prefix(base, path)) {\n-\t\t\treplace_dir(buf, git_dir_len, get_git_common_dir());\n-\t\t\treturn;\n+/*\n+ * Add a key/value pair to a trie. The key is assumed to be \\0-terminated.\n+ * If there was an existing value for this key, return it.\n+ */\n+static void *add_to_trie(struct trie *root, const char *key, void *value)\n+{\n+\tstruct trie *child;\n+\tvoid *old;\n+\tint i;\n+\n+\tif (!*key) {\n+\t\t/* we have reached the end of the key */\n+\t\told = root->value;\n+\t\troot->value = value;\n+\t\treturn old;\n+\t}\n+\n+\tfor (i = 0; i < root->len; i++) {\n+\t\tif (root->contents[i] == key[i])\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * Split this node: child will contain this node's\n+\t\t * existing children.\n+\t\t */\n+\t\tchild = malloc(sizeof(*child));\n+\t\tmemcpy(child->children, root->children, sizeof(root->children));\n+\n+\t\tchild->len = root->len - i - 1;\n+\t\tif (child->len) {\n+\t\t\tchild->contents = xstrndup(root->contents + i + 1,\n+\t\t\t\t\t\t child->len);\n \t\t}\n-\t\tif (!p->is_dir && !strcmp(base, path)) {\n-\t\t\treplace_dir(buf, git_dir_len, get_git_common_dir());\n-\t\t\treturn;\n+\t\tchild->value = root->value;\n+\t\troot->value = NULL;\n+\t\troot->len = i;\n+\n+\t\tmemset(root->children, 0, sizeof(root->children));\n+\t\troot->children[(unsigned char)root->contents[i]] = child;\n+\n+\t\t/* This is the newly-added child. */\n+\t\troot->children[(unsigned char)key[i]] =\n+\t\t\tmake_trie_node(key + i + 1, value);\n+\t\treturn NULL;\n+\t}\n+\n+\t/* We have matched the entire compressed section */\n+\tif (key[i]) {\n+\t\tchild = root->children[(unsigned char)key[root->len]];\n+\t\tif (child) {\n+\t\t\treturn add_to_trie(child, key + root->len + 1, value);\n+\t\t} else {\n+\t\t\tchild = make_trie_node(key + root->len + 1, value);\n+\t\t\troot->children[(unsigned char)key[root->len]] = child;\n+\t\t\treturn NULL;\n \t\t}\n \t}\n+\n+\told = root->value;\n+\troot->value = value;\n+\treturn old;\n+}\n+\n+typedef int (*match_fn)(const char *unmatched, void *data, void *baton);\n+\n+/*\n+ * Search a trie for some key. Find the longest /-or-\\0-terminated\n+ * prefix of the key for which the trie contains a value. Call fn\n+ * with the unmatched portion of the key and the found value, and\n+ * return its return value. If there is no such prefix, return -1.\n+ *\n+ * The key is partially normalized: consecutive slashes are skipped.\n+ *\n+ * For example, consider the trie containing only [refs,\n+ * refs/worktree] (both with values).\n+ *\n+ * | key | unmatched | val from node | return value |\n+ * |-----------------|------------|---------------|--------------|\n+ * | a | not called | n/a | -1 |\n+ * | refs | \\0 | refs | as per fn |\n+ * | refs/ | / | refs | as per fn |\n+ * | refs/w | /w | refs | as per fn |\n+ * | refs/worktree | \\0 | refs/worktree | as per fn |\n+ * | refs/worktree/ | / | refs/worktree | as per fn |\n+ * | refs/worktree/a | /a | refs/worktree | as per fn |\n+ * |-----------------|------------|---------------|--------------|\n+ *\n+ */\n+static int trie_find(struct trie *root, const char *key, match_fn fn,\n+\t\t void *baton)\n+{\n+\tint i;\n+\tint result;\n+\tstruct trie *child;\n+\n+\tif (!*key) {\n+\t\t/* we have reached the end of the key */\n+\t\tif (root->value && !root->len)\n+\t\t\treturn fn(key, root->value, baton);\n+\t\telse\n+\t\t\treturn -1;\n+\t}\n+\n+\tfor (i = 0; i < root->len; i++) {\n+\t\t/* Partial path normalization: skip consecutive slashes. */\n+\t\tif (key[i] == '/' && key[i+1] == '/') {\n+\t\t\tkey++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (root->contents[i] != key[i])\n+\t\t\treturn -1;\n+\t}\n+\n+\t/* Matched the entire compressed section */\n+\tkey += i;\n+\tif (!*key)\n+\t\t/* End of key */\n+\t\treturn fn(key, root->value, baton);\n+\n+\t/* Partial path normalization: skip consecutive slashes */\n+\twhile (key[0] == '/' && key[1] == '/')\n+\t\tkey++;\n+\n+\tchild = root->children[(unsigned char)*key];\n+\tif (child)\n+\t\tresult = trie_find(child, key + 1, fn, baton);\n+\telse\n+\t\tresult = -1;\n+\n+\tif (result >= 0 || (*key != '/' && *key != 0))\n+\t\treturn result;\n+\tif (root->value)\n+\t\treturn fn(key, root->value, baton);\n+\telse\n+\t\treturn -1;\n+}\n+\n+static struct trie common_trie;\n+static int common_trie_done_setup;\n+\n+static void init_common_trie(void)\n+{\n+\tstruct common_dir *p;\n+\n+\tif (common_trie_done_setup)\n+\t\treturn;\n+\n+\tfor (p = common_list; p->dirname; p++)\n+\t\tadd_to_trie(&common_trie, p->dirname, p);\n+\n+\tcommon_trie_done_setup = 1;\n+}\n+\n+/*\n+ * Helper function for update_common_dir: returns 1 if the dir\n+ * prefix is common.\n+ */\n+static int check_common(const char *unmatched, void *value, void *baton)\n+{\n+\tstruct common_dir *dir = value;\n+\n+\tif (!dir)\n+\t\treturn 0;\n+\n+\tif (dir->is_dir && (unmatched[0] == 0 || unmatched[0] == '/'))\n+\t\treturn !dir->exclude;\n+\n+\tif (!dir->is_dir && unmatched[0] == 0)\n+\t\treturn !dir->exclude;\n+\n+\treturn 0;\n+}\n+\n+static void update_common_dir(struct strbuf *buf, int git_dir_len)\n+{\n+\tchar *base = buf->buf + git_dir_len;\n+\tinit_common_trie();\n+\tif (trie_find(&common_trie, base, check_common, NULL) > 0)\n+\t\treplace_dir(buf, git_dir_len, get_git_common_dir());\n }\n \n void report_linked_checkout_garbage(void)\ndiff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh\nindex 93605f4..1ca49e1 100755\n--- a/t/t0060-path-utils.sh\n+++ b/t/t0060-path-utils.sh\n@@ -271,6 +271,7 @@ test_git_path GIT_COMMON_DIR=bar objects/bar bar/objects/bar\n test_git_path GIT_COMMON_DIR=bar info/exclude bar/info/exclude\n test_git_path GIT_COMMON_DIR=bar info/grafts bar/info/grafts\n test_git_path GIT_COMMON_DIR=bar info/sparse-checkout .git/info/sparse-checkout\n+test_git_path GIT_COMMON_DIR=bar info//sparse-checkout .git/info//sparse-checkout\n test_git_path GIT_COMMON_DIR=bar remotes/bar bar/remotes/bar\n test_git_path GIT_COMMON_DIR=bar branches/bar bar/branches/bar\n test_git_path GIT_COMMON_DIR=bar logs/refs/heads/master bar/logs/refs/heads/master\n-- \n2.0.4.315.gad8727a-twtrsrc\n"},{"id":"269075","messageId":"1441073591-639-4-git-send-email-dturner@twopensource.com","threadId":"40236","inReplyTo":"1441073591-639-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v5 3/3] refs: make refs/bisect/* per-worktree","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-09-01T02:13:11Z","receivedAt":"2015-09-01T02:13:11Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"We need the place we stick refs for bisects in progress to not be\nshared between worktrees. So we make the refs/bisect/ hierarchy\nper-worktree.\n\nThe is_per_worktree_ref function and associated docs learn that\nrefs/bisect/ is per-worktree, as does the git_path code in path.c\n\nThe ref-packing functions learn that per-worktree refs should not be\npacked (since packed-refs is common rather than per-worktree).\n\nSince refs/bisect is per-worktree, logs/refs/bisect should be too.\n\nSigned-off-by: David Turner \nSigned-off-by: Junio C Hamano \n---\n Documentation/glossary-content.txt | 5 +++--\n path.c | 2 ++\n refs.c | 32 +++++++++++++++++++++++++++++++-\n t/t0060-path-utils.sh | 5 +++++\n t/t1400-update-ref.sh | 19 +++++++++++++++++++\n t/t3210-pack-refs.sh | 7 +++++++\n 6 files changed, 67 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/glossary-content.txt b/Documentation/glossary-content.txt\nindex 8c6478b..e225974 100644\n--- a/Documentation/glossary-content.txt\n+++ b/Documentation/glossary-content.txt\n@@ -413,8 +413,9 @@ exclude;;\n \n [[def_per_worktree_ref]]per-worktree ref::\n \tRefs that are per-<>, rather than\n-\tglobal. This is presently only <>, but might\n-\tlater include other unusual refs.\n+\tglobal. This is presently only <> and any refs\n+\tthat start with `refs/bisect/`, but might later include other\n+\tunusual refs.\n \n [[def_pseudoref]]pseudoref::\n \tPseudorefs are a class of files under `$GIT_DIR` which behave\ndiff --git a/path.c b/path.c\nindex c87f44a..26723a9 100644\n--- a/path.c\n+++ b/path.c\n@@ -107,9 +107,11 @@ struct common_dir common_list[] = {\n \t{ 0, 0, 1, \"info/sparse-checkout\" },\n \t{ 1, 1, 0, \"logs\" },\n \t{ 1, 1, 1, \"logs/HEAD\" },\n+\t{ 0, 1, 1, \"logs/refs/bisect\" },\n \t{ 0, 1, 0, \"lost-found\" },\n \t{ 0, 1, 0, \"objects\" },\n \t{ 0, 1, 0, \"refs\" },\n+\t{ 0, 1, 1, \"refs/bisect\" },\n \t{ 0, 1, 0, \"remotes\" },\n \t{ 0, 1, 0, \"worktrees\" },\n \t{ 0, 1, 0, \"rr-cache\" },\ndiff --git a/refs.c b/refs.c\nindex 4e15f60..24401f7 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -304,6 +304,11 @@ struct ref_entry {\n };\n \n static void read_loose_refs(const char *dirname, struct ref_dir *dir);\n+static int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len);\n+static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,\n+\t\t\t\t\t const char *dirname, size_t len,\n+\t\t\t\t\t int incomplete);\n+static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry);\n \n static struct ref_dir *get_ref_dir(struct ref_entry *entry)\n {\n@@ -312,6 +317,24 @@ static struct ref_dir *get_ref_dir(struct ref_entry *entry)\n \tdir = &entry->u.subdir;\n \tif (entry->flag & REF_INCOMPLETE) {\n \t\tread_loose_refs(entry->name, dir);\n+\n+\t\t/*\n+\t\t * Manually add refs/bisect, which, being\n+\t\t * per-worktree, might not appear in the directory\n+\t\t * listing for refs/ in the main repo.\n+\t\t */\n+\t\tif (!strcmp(entry->name, \"refs/\")) {\n+\t\t\tint pos = search_ref_dir(dir, \"refs/bisect/\", 12);\n+\t\t\tif (pos < 0) {\n+\t\t\t\tstruct ref_entry *child_entry;\n+\t\t\t\tchild_entry = create_dir_entry(dir->ref_cache,\n+\t\t\t\t\t\t\t \"refs/bisect/\",\n+\t\t\t\t\t\t\t 12, 1);\n+\t\t\t\tadd_entry_to_dir(dir, child_entry);\n+\t\t\t\tread_loose_refs(\"refs/bisect\",\n+\t\t\t\t\t\t&child_entry->u.subdir);\n+\t\t\t}\n+\t\t}\n \t\tentry->flag &= ~REF_INCOMPLETE;\n \t}\n \treturn dir;\n@@ -2649,6 +2672,8 @@ struct pack_refs_cb_data {\n \tstruct ref_to_prune *ref_to_prune;\n };\n \n+static int is_per_worktree_ref(const char *refname);\n+\n /*\n * An each_ref_entry_fn that is run over loose references only. If\n * the loose reference can be packed, add an entry in the packed ref\n@@ -2662,6 +2687,10 @@ static int pack_if_possible_fn(struct ref_entry *entry, void *cb_data)\n \tstruct ref_entry *packed_entry;\n \tint is_tag_ref = starts_with(entry->name, \"refs/tags/\");\n \n+\t/* Do not pack per-worktree refs: */\n+\tif (is_per_worktree_ref(entry->name))\n+\t\treturn 0;\n+\n \t/* ALWAYS pack tags */\n \tif (!(cb->flags & PACK_REFS_ALL) && !is_tag_ref)\n \t\treturn 0;\n@@ -2856,7 +2885,8 @@ static int delete_ref_loose(struct ref_lock *lock, int flag, struct strbuf *err)\n \n static int is_per_worktree_ref(const char *refname)\n {\n-\treturn !strcmp(refname, \"HEAD\");\n+\treturn !strcmp(refname, \"HEAD\") ||\n+\t\tstarts_with(refname, \"refs/bisect/\");\n }\n \n static int is_pseudoref_syntax(const char *refname)\ndiff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh\nindex 1ca49e1..627ef85 100755\n--- a/t/t0060-path-utils.sh\n+++ b/t/t0060-path-utils.sh\n@@ -266,6 +266,10 @@ test_expect_success 'setup common repository' 'git --git-dir=bar init'\n test_git_path GIT_COMMON_DIR=bar index .git/index\n test_git_path GIT_COMMON_DIR=bar HEAD .git/HEAD\n test_git_path GIT_COMMON_DIR=bar logs/HEAD .git/logs/HEAD\n+test_git_path GIT_COMMON_DIR=bar logs/refs/bisect/foo .git/logs/refs/bisect/foo\n+test_git_path GIT_COMMON_DIR=bar logs/refs/bisec/foo bar/logs/refs/bisec/foo\n+test_git_path GIT_COMMON_DIR=bar logs/refs/bisec bar/logs/refs/bisec\n+test_git_path GIT_COMMON_DIR=bar logs/refs/bisectfoo bar/logs/refs/bisectfoo\n test_git_path GIT_COMMON_DIR=bar objects bar/objects\n test_git_path GIT_COMMON_DIR=bar objects/bar bar/objects/bar\n test_git_path GIT_COMMON_DIR=bar info/exclude bar/info/exclude\n@@ -276,6 +280,7 @@ test_git_path GIT_COMMON_DIR=bar remotes/bar bar/remotes/bar\n test_git_path GIT_COMMON_DIR=bar branches/bar bar/branches/bar\n test_git_path GIT_COMMON_DIR=bar logs/refs/heads/master bar/logs/refs/heads/master\n test_git_path GIT_COMMON_DIR=bar refs/heads/master bar/refs/heads/master\n+test_git_path GIT_COMMON_DIR=bar refs/bisect/foo .git/refs/bisect/foo\n test_git_path GIT_COMMON_DIR=bar hooks/me bar/hooks/me\n test_git_path GIT_COMMON_DIR=bar config bar/config\n test_git_path GIT_COMMON_DIR=bar packed-refs bar/packed-refs\ndiff --git a/t/t1400-update-ref.sh b/t/t1400-update-ref.sh\nindex 97406fa..af1b20d 100755\n--- a/t/t1400-update-ref.sh\n+++ b/t/t1400-update-ref.sh\n@@ -1130,4 +1130,23 @@ test_expect_success ULIMIT_FILE_DESCRIPTORS 'large transaction deleting branches\n )\n '\n \n+test_expect_success 'handle per-worktree refs in refs/bisect' '\n+\tgit commit --allow-empty -m \"initial commit\" &&\n+\tgit worktree add -b branch worktree &&\n+\t(\n+\t\tcd worktree &&\n+\t\tgit commit --allow-empty -m \"test commit\" &&\n+\t\tgit for-each-ref >for-each-ref.out &&\n+\t\t! grep refs/bisect for-each-ref.out &&\n+\t\tgit update-ref refs/bisect/something HEAD &&\n+\t\tgit rev-parse refs/bisect/something >../worktree-head &&\n+\t\tgit for-each-ref | grep refs/bisect/something\n+\t) &&\n+\ttest_path_is_missing .git/refs/bisect &&\n+\ttest_must_fail git rev-parse refs/bisect/something &&\n+\tgit update-ref refs/bisect/something HEAD &&\n+\tgit rev-parse refs/bisect/something >main-head &&\n+\t! test_cmp main-head worktree-head\n+'\n+\n test_done\ndiff --git a/t/t3210-pack-refs.sh b/t/t3210-pack-refs.sh\nindex 7b5b6d4..db244d2 100755\n--- a/t/t3210-pack-refs.sh\n+++ b/t/t3210-pack-refs.sh\n@@ -160,6 +160,13 @@ test_expect_success 'pack ref directly below refs/' '\n \ttest_path_is_missing .git/refs/top\n '\n \n+test_expect_success 'do not pack ref in refs/bisect' '\n+\tgit update-ref refs/bisect/local HEAD &&\n+\tgit pack-refs --all --prune &&\n+\t! grep refs/bisect/local .git/packed-refs >/dev/null &&\n+\ttest_path_is_file .git/refs/bisect/local\n+'\n+\n test_expect_success 'disable reflogs' '\n \tgit config core.logallrefupdates false &&\n \trm -rf .git/logs\n-- \n2.0.4.315.gad8727a-twtrsrc\n"},{"id":"269101","messageId":"xmqq7foat81a.fsf@gitster.mtv.corp.google.com","threadId":"40236","inReplyTo":"1441073591-639-1-git-send-email-dturner@twopensource.com","subject":"Re: making refs/bisect/ per worktree (was Re: (unknown))","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-09-01T16:32:17Z","receivedAt":"2015-09-01T16:32:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner writes:\n\n> This version of the patch series squashes in Junio's comment fix and\n> the xstrndup fix.\n>\n> In addition, it removes refs/worktree, and just makes refs/bisect\n> per-worktree. If we later discover that other things need to be\n> per-worktree, we can do refs/worktree, but for now, this is\n> backwards-compatible so we'll do this.\n\nI've already squashed the \"make common_list[] static\" from Ramsay\ninto 1/3, so no need to resend for that one.\n\nLet's wait for a few days to see if people spot any more issues,\nmerge to and cook in 'next' for the remainder of this cycle, and aim\nto merge this down to 'master' in the first batch after the upcoming\nrelease.\n\nThanks.\n"},{"id":"271112","messageId":"5611E7B1.3090001@alum.mit.edu","threadId":"40236","inReplyTo":"1441073591-639-3-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v5 2/3] path: optimize common dir checking","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-10-05T03:00:01Z","receivedAt":"2015-10-05T03:00:01Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/01/2015 04:13 AM, David Turner wrote:\n> Instead of a linear search over common_list to check whether\n> a path is common, use a trie. The trie search operates on\n> path prefixes, and handles excludes.\n\nHere I am, coming late to the discussion as usual. Sorry for that.\n\nI dug into this code yesterday and got all nerd-tingly and started\nrefactoring and optimizing it. But after I slept on it I realized that\nI'm a bit hazy on its justification. A trie is a beautiful data\nstructure and all, but have there been any benchmarks showing (1) that\nthis lookup is a bottleneck and (2) that the trie is an improvement on\nsomething simpler, like, say, a sorted string_list? Or is there a\nrealistic hope that the trie might be generally useful for other purposes?\n\nThe latter seems unlikely, at least with the current implementation,\nbecause it is very wasteful of space. It allocates one or two (usually\ntwo) `struct trie` for every single string that is added to it. Each\n`struct trie` contains an array of 256 pointers and usually needs two\nmalloc calls to instantiate. So *each entry* stored in the trie costs\nsomething like 4 kilobytes on a 64-bit system, plus usually 4 calls to\nmalloc. The large memory footprint, in turn, will cause access\nnon-locality and might impact the lookup performance. So it is pretty\nclear that the current code would be unusable for a large number of strings.\n\nFor this particular application, where we only have 19 strings to store,\nI suppose we could tolerate the use of approximately 64k of RAM to store\n174 characters worth of strings *if* it would bring us big time savings.\nBut I think we need some evidence of the time savings.\n\nIf this lookup is really a bottleneck, I bet there are other\nalternatives that are just as fast as this trie and use less code,\nespecially given that there are only 19 strings that need checking.\n\nWith respect to the implementation, it looks correct to me. I would make\nthe following three suggestions:\n\n* Please document that the `contents` field of `struct trie` is not\nNUL-terminated, because that would otherwise be a common assumption. (It\nis clearly not NUL-terminated because of the way it is initialized using\nxmalloc and memcpy in make_trie_node() and because of the way its length\nis adjusted in add_to_trie().)\n* But in add_to_trie(), you set `contents` using xstrdup(), which *does*\nNUL-terminate the string. It would be more consistent to set it using\nxmalloc and memcpy here.\n* Please use size_t instead of int for indexing into strings, at least\nin the trie_find() function, where the input is likely to be under the\ncontrol of users.\n\nIf we expected to use the trie for other purposes, then I would suggest\na raft of other improvements. Ask me if you are interested.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"271145","messageId":"xmqqd1wtz0w2.fsf@gitster.mtv.corp.google.com","threadId":"40236","inReplyTo":"5611E7B1.3090001@alum.mit.edu","subject":"Re: [PATCH v5 2/3] path: optimize common dir checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-10-05T17:22:05Z","receivedAt":"2015-10-05T17:22:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> For this particular application, where we only have 19 strings to store,\n> I suppose we could tolerate the use of approximately 64k of RAM to store\n> 174 characters worth of strings *if* it would bring us big time savings.\n> But I think we need some evidence of the time savings.\n>\n> If this lookup is really a bottleneck, I bet there are other\n> alternatives that are just as fast as this trie and use less code,\n> especially given that there are only 19 strings that need checking.\n\nVery good point. I agree that we need to know that the dumb linear\nscan in the original is on the bottleneck and that any replacement\nis an improvement.\n"},{"id":"271157","messageId":"1444075810.5158.7.camel@twopensource.com","threadId":"40236","inReplyTo":"xmqqd1wtz0w2.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v5 2/3] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-10-05T20:10:10Z","receivedAt":"2015-10-05T20:10:10Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-10-05 at 10:22 -0700, Junio C Hamano wrote:\n> Michael Haggerty writes:\n> \n> > For this particular application, where we only have 19 strings to store,\n> > I suppose we could tolerate the use of approximately 64k of RAM to store\n> > 174 characters worth of strings *if* it would bring us big time savings.\n> > But I think we need some evidence of the time savings.\n> >\n> > If this lookup is really a bottleneck, I bet there are other\n> > alternatives that are just as fast as this trie and use less code,\n> > especially given that there are only 19 strings that need checking.\n> \n> Very good point. I agree that we need to know that the dumb linear\n> scan in the original is on the bottleneck and that any replacement\n> is an improvement.\n\nJust did a tiny bit of microbenchmarking:\n\nThe trie code is indeed somewhat faster, but it's not the bottleneck in\nthe git_path family of functions. The sprintf stuff takes way more\ntime. Most callers don't need this functionality (an append would do).\n\nBut this is a benchmark of just git_path. I don't happen to see any\ncases where git_path is taking up an appreciable amount of runtime.\n\nI only added this because Junio requested a speedup. So I am perfectly\nhappy to drop this patch from the series. \n"},{"id":"271171","messageId":"xmqqsi5pxdc0.fsf@gitster.mtv.corp.google.com","threadId":"40236","inReplyTo":"1444075810.5158.7.camel@twopensource.com","subject":"Re: [PATCH v5 2/3] path: optimize common dir checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-10-05T20:36:15Z","receivedAt":"2015-10-05T20:36:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner writes:\n\n> But this is a benchmark of just git_path. I don't happen to see any\n> cases where git_path is taking up an appreciable amount of runtime.\n>\n> I only added this because Junio requested a speedup. So I am perfectly\n> happy to drop this patch from the series. \n\nOk, then let's drop it for now. Thanks.\n"},{"id":"271174","messageId":"xmqqoagdxd06.fsf@gitster.mtv.corp.google.com","threadId":"40236","inReplyTo":"xmqqsi5pxdc0.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v5 2/3] path: optimize common dir checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-10-05T20:43:21Z","receivedAt":"2015-10-05T20:43:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> David Turner writes:\n>\n>> But this is a benchmark of just git_path. I don't happen to see any\n>> cases where git_path is taking up an appreciable amount of runtime.\n>>\n>> I only added this because Junio requested a speedup. So I am perfectly\n>> happy to drop this patch from the series. \n>\n> Ok, then let's drop it for now. Thanks.\n\nHaving said all that, this conversation happened way after I started\ntoday's integration cycle, I am not inclined to redo all of that,\nespecially with extra tagging involved in the work done today.\n\nSo it is in 'master' now. I'm open to a patch to revert this\ncommit, though.\n\nThanks.\n"}]}