{"thread":{"id":"40182","subject":"[PATCH v4 1/4] refs: clean up common_list","startedAt":"2015-08-26T19:46:01Z","lastAt":"2015-08-31T18:56:39Z","messageCount":13,"participants":["David Turner","Junio C Hamano","Torsten Bögershausen"],"isPatch":true,"patchVersion":4,"patchTotal":4},"messages":[{"id":"268746","messageId":"1440618365-20628-1-git-send-email-dturner@twopensource.com","threadId":"40182","inReplyTo":null,"subject":"[PATCH v4 0/4] per-worktree bisection refs","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T19:46:01Z","receivedAt":"2015-08-26T19:46:01Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"This reroll includes changes suggested by Duy Nguyen:\n\nA. Path normalization (partial).\nB. Rearrangement of common_list struct to make formatting prettier.\n\nIt also includes a test style fix suggested by Eric Sunshine and\nothers: a bogus test_must_fail on a non-git command has been replaced\nby a two-step check.\n"},{"id":"268745","messageId":"1440618365-20628-2-git-send-email-dturner@twopensource.com","threadId":"40182","inReplyTo":"1440618365-20628-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v4 1/4] refs: clean up common_list","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T19:46:02Z","receivedAt":"2015-08-26T19:46:02Z","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 <dturner@twopensource.com>\n---\n path.c | 58 +++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 37 insertions(+), 21 deletions(-)\n\ndiff --git a/path.c b/path.c\nindex 10f4cbf..d24bfa2 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.4.2.622.gac67c30-twtrsrc\n"},{"id":"268747","messageId":"1440618365-20628-3-git-send-email-dturner@twopensource.com","threadId":"40182","inReplyTo":"1440618365-20628-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v4 2/4] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T19:46:03Z","receivedAt":"2015-08-26T19:46:03Z","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 <dturner@twopensource.com>\n---\n path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----\n t/t0060-path-utils.sh |   1 +\n 2 files changed, 213 insertions(+), 14 deletions(-)\n\ndiff --git a/path.c b/path.c\nindex d24bfa2..c7a4c40 100644\n--- a/path.c\n+++ b/path.c\n@@ -121,25 +121,223 @@ 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, value = (something), children a and d non-NULL.\n+ *    a: len = 2, contents = bc\n+ *    d: len = 2, contents = ef, children i non-NULL, value = (something)\n+ *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL\n+ *           e: len = 0, children all NULL, value = (something)\n+ *           i: len = 2, contents = on, children all NULL, value = (something)\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 = strndup(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.4.2.622.gac67c30-twtrsrc\n"},{"id":"268749","messageId":"1440618365-20628-4-git-send-email-dturner@twopensource.com","threadId":"40182","inReplyTo":"1440618365-20628-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v4 3/4] refs: make refs/worktree/* per-worktree","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T19:46:04Z","receivedAt":"2015-08-26T19:46:04Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"We need a place to stick refs for bisects in progress that is not\nshared between worktrees.  So we use the refs/worktree/ hierarchy.\n\nThe is_per_worktree_ref function and associated docs learn that\nrefs/worktree/ 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/worktree is per-worktree, logs/refs/worktree should be too.\n\nSigned-off-by: David Turner <dturner@twopensource.com>\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..5c707e6 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-<<def_working_tree,worktree>>, rather than\n-\tglobal.  This is presently only <<def_HEAD,HEAD>>, but might\n-\tlater include other unusual refs.\n+\tglobal.  This is presently only <<def_HEAD,HEAD>> and any refs\n+\tthat start with `refs/worktree/`, 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 c7a4c40..acac7b1 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/worktree\" },\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/worktree\", },\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 e6fc3fe..30331bc 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -298,6 +298,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@@ -306,6 +311,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/worktree, 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/worktree/\", 14);\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/worktree/\",\n+\t\t\t\t\t\t\t       14, 1);\n+\t\t\t\tadd_entry_to_dir(dir, child_entry);\n+\t\t\t\tread_loose_refs(\"refs/worktree\",\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@@ -2643,6 +2666,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@@ -2656,6 +2681,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@@ -2850,7 +2879,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/worktree/\");\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..b2d2005 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/worktree/foo   .git/logs/refs/worktree/foo\n+test_git_path GIT_COMMON_DIR=bar logs/refs/worktre/foo    bar/logs/refs/worktre/foo\n+test_git_path GIT_COMMON_DIR=bar logs/refs/worktre        bar/logs/refs/worktre\n+test_git_path GIT_COMMON_DIR=bar logs/refs/worktreefoo    bar/logs/refs/worktreefoo\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/worktree/foo        .git/refs/worktree/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 9d21c19..6dc29e6 100755\n--- a/t/t1400-update-ref.sh\n+++ b/t/t1400-update-ref.sh\n@@ -1131,4 +1131,23 @@ test_expect_success ULIMIT_FILE_DESCRIPTORS 'large transaction deleting branches\n )\n '\n \n+test_expect_success 'handle per-worktree refs in refs/worktree' '\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/worktree for-each-ref.out &&\n+\t\tgit update-ref refs/worktree/something HEAD &&\n+\t\tgit rev-parse refs/worktree/something >../worktree-head &&\n+\t\tgit for-each-ref | grep refs/worktree/something\n+\t) &&\n+\ttest_path_is_missing .git/refs/worktree &&\n+\ttest_must_fail git rev-parse refs/worktree/something &&\n+\tgit update-ref refs/worktree/something HEAD &&\n+\tgit rev-parse refs/worktree/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 8aae98d..c54cd29 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/worktree' '\n+\tgit update-ref refs/worktree/local HEAD &&\n+\tgit pack-refs --all --prune &&\n+\t! grep refs/worktree/local .git/packed-refs >/dev/null &&\n+\ttest_path_is_file .git/refs/worktree/local\n+'\n+\n test_expect_success 'disable reflogs' '\n \tgit config core.logallrefupdates false &&\n \trm -rf .git/logs\n-- \n2.4.2.622.gac67c30-twtrsrc\n"},{"id":"268748","messageId":"1440618365-20628-5-git-send-email-dturner@twopensource.com","threadId":"40182","inReplyTo":"1440618365-20628-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v4 4/4] bisect: make bisection refs per-worktree","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T19:46:05Z","receivedAt":"2015-08-26T19:46:05Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"Using the new refs/worktree/ refs, make bisection per-worktree.\n\nSigned-off-by: David Turner <dturner@twopensource.com>\n---\n Documentation/git-bisect.txt       |  4 ++--\n Documentation/rev-list-options.txt | 14 +++++++-------\n bisect.c                           |  2 +-\n builtin/rev-parse.c                |  6 ++++--\n git-bisect.sh                      | 14 +++++++-------\n revision.c                         |  2 +-\n t/t6030-bisect-porcelain.sh        | 20 ++++++++++----------\n 7 files changed, 32 insertions(+), 30 deletions(-)\n\ndiff --git a/Documentation/git-bisect.txt b/Documentation/git-bisect.txt\nindex e97f2de..f0c52d1 100644\n--- a/Documentation/git-bisect.txt\n+++ b/Documentation/git-bisect.txt\n@@ -82,7 +82,7 @@ to ask for the next commit that needs testing.\n \n Eventually there will be no more revisions left to inspect, and the\n command will print out a description of the first bad commit. The\n-reference `refs/bisect/bad` will be left pointing at that commit.\n+reference `refs/worktree/bisect/bad` will be left pointing at that commit.\n \n \n Bisect reset\n@@ -373,7 +373,7 @@ on a single line.\n ------------\n $ git bisect start HEAD <known-good-commit> [ <boundary-commit> ... ] --no-checkout\n $ git bisect run sh -c '\n-\tGOOD=$(git for-each-ref \"--format=%(objectname)\" refs/bisect/good-*) &&\n+\tGOOD=$(git for-each-ref \"--format=%(objectname)\" refs/worktree/bisect/good-*) &&\n \tgit rev-list --objects BISECT_HEAD --not $GOOD >tmp.$$ &&\n \tgit pack-objects --stdout >/dev/null <tmp.$$\n \trc=$?\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex a9b808f..1175960 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -183,9 +183,9 @@ explicitly.\n \n ifndef::git-rev-list[]\n --bisect::\n-\tPretend as if the bad bisection ref `refs/bisect/bad`\n+\tPretend as if the bad bisection ref `refs/worktree/bisect/bad`\n \twas listed and as if it was followed by `--not` and the good\n-\tbisection refs `refs/bisect/good-*` on the command\n+\tbisection refs `refs/worktree/bisect/good-*` on the command\n \tline. Cannot be combined with --first-parent.\n endif::git-rev-list[]\n \n@@ -548,10 +548,10 @@ Bisection Helpers\n --bisect::\n \tLimit output to the one commit object which is roughly halfway between\n \tincluded and excluded commits. Note that the bad bisection ref\n-\t`refs/bisect/bad` is added to the included commits (if it\n-\texists) and the good bisection refs `refs/bisect/good-*` are\n+\t`refs/worktree/bisect/bad` is added to the included commits (if it\n+\texists) and the good bisection refs `refs/worktree/bisect/good-*` are\n \tadded to the excluded commits (if they exist). Thus, supposing there\n-\tare no refs in `refs/bisect/`, if\n+\tare no refs in `refs/worktree/bisect/`, if\n +\n -----------------------------------------------------------------------\n \t$ git rev-list --bisect foo ^bar ^baz\n@@ -571,7 +571,7 @@ one. Cannot be combined with --first-parent.\n \n --bisect-vars::\n \tThis calculates the same as `--bisect`, except that refs in\n-\t`refs/bisect/` are not used, and except that this outputs\n+\t`refs/worktree/bisect/` are not used, and except that this outputs\n \ttext ready to be eval'ed by the shell. These lines will assign the\n \tname of the midpoint revision to the variable `bisect_rev`, and the\n \texpected number of commits to be tested after `bisect_rev` is tested\n@@ -584,7 +584,7 @@ one. Cannot be combined with --first-parent.\n --bisect-all::\n \tThis outputs all the commit objects between the included and excluded\n \tcommits, ordered by their distance to the included and excluded\n-\tcommits. Refs in `refs/bisect/` are not used. The farthest\n+\tcommits. Refs in `refs/worktree/bisect/` are not used. The farthest\n \tfrom them is displayed first. (This is the only one displayed by\n \t`--bisect`.)\n +\ndiff --git a/bisect.c b/bisect.c\nindex 33ac88d..dbe3461 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -425,7 +425,7 @@ static int register_ref(const char *refname, const struct object_id *oid,\n \n static int read_bisect_refs(void)\n {\n-\treturn for_each_ref_in(\"refs/bisect/\", register_ref, NULL);\n+\treturn for_each_ref_in(\"refs/worktree/bisect/\", register_ref, NULL);\n }\n \n static void read_bisect_paths(struct argv_array *array)\ndiff --git a/builtin/rev-parse.c b/builtin/rev-parse.c\nindex 02d747d..3240ddf 100644\n--- a/builtin/rev-parse.c\n+++ b/builtin/rev-parse.c\n@@ -663,8 +663,10 @@ int cmd_rev_parse(int argc, const char **argv, const char *prefix)\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"--bisect\")) {\n-\t\t\t\tfor_each_ref_in(\"refs/bisect/bad\", show_reference, NULL);\n-\t\t\t\tfor_each_ref_in(\"refs/bisect/good\", anti_reference, NULL);\n+\t\t\t\tfor_each_ref_in(\"refs/worktree/bisect/bad\",\n+\t\t\t\t\t\tshow_reference, NULL);\n+\t\t\t\tfor_each_ref_in(\"refs/worktree/bisect/good\",\n+\t\t\t\t\t\tanti_reference, NULL);\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (starts_with(arg, \"--branches=\")) {\ndiff --git a/git-bisect.sh b/git-bisect.sh\nindex ea63223..c16433d 100755\n--- a/git-bisect.sh\n+++ b/git-bisect.sh\n@@ -210,7 +210,7 @@ bisect_write() {\n \t\t*)\n \t\t\tdie \"$(eval_gettext \"Bad bisect_write argument: \\$state\")\" ;;\n \tesac\n-\tgit update-ref \"refs/bisect/$tag\" \"$rev\" || exit\n+\tgit update-ref \"refs/worktree/bisect/$tag\" \"$rev\" || exit\n \techo \"# $state: $(git show-branch $rev)\" >>\"$GIT_DIR/BISECT_LOG\"\n \ttest -n \"$nolog\" || echo \"git bisect $state $rev\" >>\"$GIT_DIR/BISECT_LOG\"\n }\n@@ -282,8 +282,8 @@ bisect_state() {\n \n bisect_next_check() {\n \tmissing_good= missing_bad=\n-\tgit show-ref -q --verify refs/bisect/$TERM_BAD || missing_bad=t\n-\ttest -n \"$(git for-each-ref \"refs/bisect/$TERM_GOOD-*\")\" || missing_good=t\n+\tgit show-ref -q --verify refs/worktree/bisect/$TERM_BAD || missing_bad=t\n+\ttest -n \"$(git for-each-ref \"refs/worktree/bisect/$TERM_GOOD-*\")\" || missing_good=t\n \n \tcase \"$missing_good,$missing_bad,$1\" in\n \t,,*)\n@@ -341,15 +341,15 @@ bisect_next() {\n \t# Check if we should exit because bisection is finished\n \tif test $res -eq 10\n \tthen\n-\t\tbad_rev=$(git show-ref --hash --verify refs/bisect/$TERM_BAD)\n+\t\tbad_rev=$(git show-ref --hash --verify refs/worktree/bisect/$TERM_BAD)\n \t\tbad_commit=$(git show-branch $bad_rev)\n \t\techo \"# first $TERM_BAD commit: $bad_commit\" >>\"$GIT_DIR/BISECT_LOG\"\n \t\texit 0\n \telif test $res -eq 2\n \tthen\n \t\techo \"# only skipped commits left to test\" >>\"$GIT_DIR/BISECT_LOG\"\n-\t\tgood_revs=$(git for-each-ref --format=\"%(objectname)\" \"refs/bisect/$TERM_GOOD-*\")\n-\t\tfor skipped in $(git rev-list refs/bisect/$TERM_BAD --not $good_revs)\n+\t\tgood_revs=$(git for-each-ref --format=\"%(objectname)\" \"refs/worktree/bisect/$TERM_GOOD-*\")\n+\t\tfor skipped in $(git rev-list refs/worktree/bisect/$TERM_BAD --not $good_revs)\n \t\tdo\n \t\t\tskipped_commit=$(git show-branch $skipped)\n \t\t\techo \"# possible first $TERM_BAD commit: $skipped_commit\" >>\"$GIT_DIR/BISECT_LOG\"\n@@ -412,7 +412,7 @@ Try 'git bisect reset <commit>'.\")\"\n \n bisect_clean_state() {\n \t# There may be some refs packed during bisection.\n-\tgit for-each-ref --format='%(refname) %(objectname)' refs/bisect/\\* |\n+\tgit for-each-ref --format='%(refname) %(objectname)' refs/worktree/bisect/\\* |\n \twhile read ref hash\n \tdo\n \t\tgit update-ref -d $ref $hash || exit\ndiff --git a/revision.c b/revision.c\nindex b6b2cf7..974a11f 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2084,7 +2084,7 @@ extern void read_bisect_terms(const char **bad, const char **good);\n static int for_each_bisect_ref(const char *submodule, each_ref_fn fn, void *cb_data, const char *term) {\n \tstruct strbuf bisect_refs = STRBUF_INIT;\n \tint status;\n-\tstrbuf_addf(&bisect_refs, \"refs/bisect/%s\", term);\n+\tstrbuf_addf(&bisect_refs, \"refs/worktree/bisect/%s\", term);\n \tstatus = for_each_ref_in_submodule(submodule, bisect_refs.buf, fn, cb_data);\n \tstrbuf_release(&bisect_refs);\n \treturn status;\ndiff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh\nindex 9e2c203..bfd5463 100755\n--- a/t/t6030-bisect-porcelain.sh\n+++ b/t/t6030-bisect-porcelain.sh\n@@ -68,7 +68,7 @@ test_expect_success 'bisect fails if given any junk instead of revs' '\n \tgit bisect reset &&\n \ttest_must_fail git bisect start foo $HASH1 -- &&\n \ttest_must_fail git bisect start $HASH4 $HASH1 bar -- &&\n-\ttest -z \"$(git for-each-ref \"refs/bisect/*\")\" &&\n+\ttest -z \"$(git for-each-ref \"refs/worktree/bisect/*\")\" &&\n \ttest -z \"$(ls .git/BISECT_* 2>/dev/null)\" &&\n \tgit bisect start &&\n \ttest_must_fail git bisect good foo $HASH1 &&\n@@ -77,7 +77,7 @@ test_expect_success 'bisect fails if given any junk instead of revs' '\n \ttest_must_fail git bisect bad $HASH3 $HASH4 &&\n \ttest_must_fail git bisect skip bar $HASH3 &&\n \ttest_must_fail git bisect skip $HASH1 foo &&\n-\ttest -z \"$(git for-each-ref \"refs/bisect/*\")\" &&\n+\ttest -z \"$(git for-each-ref \"refs/worktree/bisect/*\")\" &&\n \tgit bisect good $HASH1 &&\n \tgit bisect bad $HASH4\n '\n@@ -115,7 +115,7 @@ test_expect_success 'bisect reset removes packed refs' '\n \tgit pack-refs --all --prune &&\n \tgit bisect next &&\n \tgit bisect reset &&\n-\ttest -z \"$(git for-each-ref \"refs/bisect/*\")\" &&\n+\ttest -z \"$(git for-each-ref \"refs/worktree/bisect/*\")\" &&\n \ttest -z \"$(git for-each-ref \"refs/heads/bisect\")\"\n '\n \n@@ -126,7 +126,7 @@ test_expect_success 'bisect reset removes bisect state after --no-checkout' '\n \tgit bisect bad $HASH3 &&\n \tgit bisect next &&\n \tgit bisect reset &&\n-\ttest -z \"$(git for-each-ref \"refs/bisect/*\")\" &&\n+\ttest -z \"$(git for-each-ref \"refs/worktree/bisect/*\")\" &&\n \ttest -z \"$(git for-each-ref \"refs/heads/bisect\")\" &&\n \ttest -z \"$(git for-each-ref \"BISECT_HEAD\")\"\n '\n@@ -176,7 +176,7 @@ test_expect_success 'bisect start: no \".git/BISECT_START\" if checkout error' '\n \tgit branch > branch.output &&\n \tgrep \"* other\" branch.output > /dev/null &&\n \ttest_must_fail test -e .git/BISECT_START &&\n-\ttest -z \"$(git for-each-ref \"refs/bisect/*\")\" &&\n+\ttest -z \"$(git for-each-ref \"refs/worktree/bisect/*\")\" &&\n \tgit checkout HEAD hello\n '\n \n@@ -671,7 +671,7 @@ test_expect_success 'bisect: --no-checkout - target before breakage' '\n \tgit bisect bad BISECT_HEAD &&\n \tcheck_same BROKEN_HASH5 BISECT_HEAD &&\n \tgit bisect bad BISECT_HEAD &&\n-\tcheck_same BROKEN_HASH5 bisect/bad &&\n+\tcheck_same BROKEN_HASH5 refs/worktree/bisect/bad &&\n \tgit bisect reset\n '\n \n@@ -682,7 +682,7 @@ test_expect_success 'bisect: --no-checkout - target in breakage' '\n \tgit bisect bad BISECT_HEAD &&\n \tcheck_same BROKEN_HASH5 BISECT_HEAD &&\n \tgit bisect good BISECT_HEAD &&\n-\tcheck_same BROKEN_HASH6 bisect/bad &&\n+\tcheck_same BROKEN_HASH6 refs/worktree/bisect/bad &&\n \tgit bisect reset\n '\n \n@@ -693,7 +693,7 @@ test_expect_success 'bisect: --no-checkout - target after breakage' '\n \tgit bisect good BISECT_HEAD &&\n \tcheck_same BROKEN_HASH8 BISECT_HEAD &&\n \tgit bisect good BISECT_HEAD &&\n-\tcheck_same BROKEN_HASH9 bisect/bad &&\n+\tcheck_same BROKEN_HASH9 refs/worktree/bisect/bad &&\n \tgit bisect reset\n '\n \n@@ -702,13 +702,13 @@ test_expect_success 'bisect: demonstrate identification of damage boundary' \"\n \tgit checkout broken &&\n \tgit bisect start broken master --no-checkout &&\n \tgit bisect run \\\"\\$SHELL_PATH\\\" -c '\n-\t\tGOOD=\\$(git for-each-ref \\\"--format=%(objectname)\\\" refs/bisect/good-*) &&\n+\t\tGOOD=\\$(git for-each-ref \\\"--format=%(objectname)\\\" refs/worktree/bisect/good-*) &&\n \t\tgit rev-list --objects BISECT_HEAD --not \\$GOOD >tmp.\\$\\$ &&\n \t\tgit pack-objects --stdout >/dev/null < tmp.\\$\\$\n \t\trc=\\$?\n \t\trm -f tmp.\\$\\$\n \t\ttest \\$rc = 0' &&\n-\tcheck_same BROKEN_HASH6 bisect/bad &&\n+\tcheck_same BROKEN_HASH6 refs/worktree/bisect/bad &&\n \tgit bisect reset\n \"\n \n-- \n2.4.2.622.gac67c30-twtrsrc\n"},{"id":"268758","messageId":"xmqqwpwh21ky.fsf@gitster.dls.corp.google.com","threadId":"40182","inReplyTo":"1440618365-20628-3-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-08-26T21:15:41Z","receivedAt":"2015-08-26T21:15:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\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>\n> Signed-off-by: David Turner <dturner@twopensource.com>\n> ---\n>  path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----\n>  t/t0060-path-utils.sh |   1 +\n>  2 files changed, 213 insertions(+), 14 deletions(-)\n>\n> diff --git a/path.c b/path.c\n> index d24bfa2..c7a4c40 100644\n> --- a/path.c\n> +++ b/path.c\n> @@ -121,25 +121,223 @@ 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, value = (something), children a and d non-NULL.\n\n\"value = NULL\", as there is no empty string registered in the trie?\n\n> + *    a: len = 2, contents = bc\n\n\"value = NULL\" here, too (just showing I am following along, not\njust skimming)?\n\n> + *    d: len = 2, contents = ef, children i non-NULL, value = (something)\n> + *       i: len = 3, contents = nit, children e and i non-NULL, value = NULL\n> + *           e: len = 0, children all NULL, value = (something)\n> + *           i: len = 2, contents = on, children all NULL, value = (something)\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 = strndup(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\nThese \"skipping consecutive slashes\" inside this function is cute.\nI would have expected me to react \"Eek, Ugly\" to it, but somehow I\ndidn't find them ugly.\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\nI somehow wonder if we'd want to precomute the trie at the build\ntime, though ;-)\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\nThanks for a pleasant read.\n\n>  \n>  void report_linked_checkout_garbage(void)\n> diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh\n> index 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"},{"id":"268761","messageId":"1440627031.26055.5.camel@twopensource.com","threadId":"40182","inReplyTo":"xmqqwpwh21ky.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T22:10:31Z","receivedAt":"2015-08-26T22:10:31Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:\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, value = (something), children a and d non-NULL.\n> \n> \"value = NULL\", as there is no empty string registered in the trie?\n\nIndeed.\n\n> > + *    a: len = 2, contents = bc\n> \n> \"value = NULL\" here, too (just showing I am following along, not\n> just skimming)?\n\nYep.\n\n<snip>\n> > +\t/* Partial path normalization: skip consecutive slashes */\n> > +\twhile (key[0] == '/' && key[1] == '/')\n> > +\t\tkey ++;\n> \n> These \"skipping consecutive slashes\" inside this function is cute.\n> I would have expected me to react \"Eek, Ugly\" to it, but somehow I\n> didn't find them ugly.\n\nIt's right on the cute/ugly edge for me too.\n\n<snip>\n\n> I somehow wonder if we'd want to precomute the trie at the build\n> time, though ;-)\n\nLOL.\n\n<snip>\n> Thanks for a pleasant read.\n\nThank you!  I'll re-roll with those last two fixes (re value=NULL)\ntomorrow-ish.\n"},{"id":"268762","messageId":"xmqqoaht1ysx.fsf@gitster.dls.corp.google.com","threadId":"40182","inReplyTo":"1440627031.26055.5.camel@twopensource.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-08-26T22:15:42Z","receivedAt":"2015-08-26T22:15:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:\n>\n>> Thanks for a pleasant read.\n>\n> Thank you!  I'll re-roll with those last two fixes (re value=NULL)\n> tomorrow-ish.\n\nIf these two \"value = NULL\" are the only things, I can locally fix\nthem up.  No need to resend.\n\nThanks.\n"},{"id":"268763","messageId":"1440627545.26055.8.camel@twopensource.com","threadId":"40182","inReplyTo":"1440627031.26055.5.camel@twopensource.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-26T22:19:05Z","receivedAt":"2015-08-26T22:19:05Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:\n> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:\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, value = (something), children a and d non-NULL.\n> > \n> > \"value = NULL\", as there is no empty string registered in the trie?\n> \n> Indeed.\n> \n> > > + *    a: len = 2, contents = bc\n> > \n> > \"value = NULL\" here, too (just showing I am following along, not\n> > just skimming)?\n> \n> Yep.\n\nNo, wait. value should be non-NULL, since abc is in the string set. \n"},{"id":"268844","messageId":"xmqqoahr2wqj.fsf@gitster.mtv.corp.google.com","threadId":"40182","inReplyTo":"1440627545.26055.8.camel@twopensource.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-08-28T16:39:32Z","receivedAt":"2015-08-28T16:39:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:\n>> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:\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, value = (something), children a and d non-NULL.\n>> > \n>> > \"value = NULL\", as there is no empty string registered in the trie?\n>> \n>> Indeed.\n>> \n>> > > + *    a: len = 2, contents = bc\n>> > \n>> > \"value = NULL\" here, too (just showing I am following along, not\n>> > just skimming)?\n>> \n>> Yep.\n>\n> No, wait. value should be non-NULL, since abc is in the string set. \n\nTrue.  Here is what I came up with on top of your original.  \n\n\n\n path.c | 11 ++++++-----\n 1 file changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/path.c b/path.c\nindex 4100ba6..ce0530b 100644\n--- a/path.c\n+++ b/path.c\n@@ -133,12 +133,13 @@ struct common_dir common_list[] = {\n  * definition\n  *\n  * The trie would look look like:\n- * root: len = 0, value = (something), children a and d non-NULL.\n- *    a: len = 2, contents = bc\n- *    d: len = 2, contents = ef, children i non-NULL, value = (something)\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 = (something)\n- *           i: len = 2, contents = on, children all NULL, value = (something)\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"},{"id":"268865","messageId":"1440787007.25570.0.camel@twopensource.com","threadId":"40182","inReplyTo":"xmqqoahr2wqj.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-28T18:36:47Z","receivedAt":"2015-08-28T18:36:47Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Fri, 2015-08-28 at 09:39 -0700, Junio C Hamano wrote:\n> David Turner <dturner@twopensource.com> writes:\n> \n> > On Wed, 2015-08-26 at 18:10 -0400, David Turner wrote:\n> >> On Wed, 2015-08-26 at 14:15 -0700, Junio C Hamano wrote:\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, value = (something), children a and d non-NULL.\n> >> > \n> >> > \"value = NULL\", as there is no empty string registered in the trie?\n> >> \n> >> Indeed.\n> >> \n> >> > > + *    a: len = 2, contents = bc\n> >> > \n> >> > \"value = NULL\" here, too (just showing I am following along, not\n> >> > just skimming)?\n> >> \n> >> Yep.\n> >\n> > No, wait. value should be non-NULL, since abc is in the string set. \n> \n> True.  Here is what I came up with on top of your original.  \n> \n> \n> \n>  path.c | 11 ++++++-----\n>  1 file changed, 6 insertions(+), 5 deletions(-)\n> \n> diff --git a/path.c b/path.c\n> index 4100ba6..ce0530b 100644\n> --- a/path.c\n> +++ b/path.c\n> @@ -133,12 +133,13 @@ struct common_dir common_list[] = {\n>   * definition\n>   *\n>   * The trie would look look like:\n> - * root: len = 0, value = (something), children a and d non-NULL.\n> - *    a: len = 2, contents = bc\n> - *    d: len = 2, contents = ef, children i non-NULL, value = (something)\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 = (something)\n> - *           i: len = 2, contents = on, children all NULL, value = (something)\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\nLGTM.\n"},{"id":"268917","messageId":"55E2A1BF.5080204@web.de","threadId":"40182","inReplyTo":"1440618365-20628-3-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"Torsten Bögershausen","fromEmail":"tboegi@web.de","sentAt":"2015-08-30T06:25:03Z","receivedAt":"2015-08-30T06:25:03Z","isPatch":true,"sender":{"key":"tboegi@web.de","avatar":"https://avatars.githubusercontent.com/u/7138363?v=4"},"body":"On 26.08.15 21:46, 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> \n> Signed-off-by: David Turner <dturner@twopensource.com>\n> ---\n>  path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----\n>  t/t0060-path-utils.sh |   1 +\n>  2 files changed, 213 insertions(+), 14 deletions(-)\n> \n> diff --git a/path.c b/path.c\n\n\n> +\t\tchild->len = root->len - i - 1;\n> +\t\tif (child->len) {\n> +\t\t\tchild->contents = strndup(root->contents + i + 1,\n> +\t\t\t\t\t\t   child->len);\n>  \t\t}\nCould we use xtrndup() instead of strndup() ?\n(Otherwise it won't compile under Mac OS here)\n"},{"id":"269024","messageId":"1441047399.25570.20.camel@twopensource.com","threadId":"40182","inReplyTo":"55E2A1BF.5080204@web.de","subject":"Re: [PATCH v4 2/4] path: optimize common dir checking","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-08-31T18:56:39Z","receivedAt":"2015-08-31T18:56:39Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Sun, 2015-08-30 at 08:25 +0200, Torsten Bögershausen wrote:\n> On 26.08.15 21:46, 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> > \n> > Signed-off-by: David Turner <dturner@twopensource.com>\n> > ---\n> >  path.c                | 226 ++++++++++++++++++++++++++++++++++++++++++++++----\n> >  t/t0060-path-utils.sh |   1 +\n> >  2 files changed, 213 insertions(+), 14 deletions(-)\n> > \n> > diff --git a/path.c b/path.c\n> \n> \n> > +\t\tchild->len = root->len - i - 1;\n> > +\t\tif (child->len) {\n> > +\t\t\tchild->contents = strndup(root->contents + i + 1,\n> > +\t\t\t\t\t\t   child->len);\n> >  \t\t}\n> Could we use xtrndup() instead of strndup() ?\n> (Otherwise it won't compile under Mac OS here)\n\nThanks.  Junio, can we squash in the following?  (Or let me know and I\ncan resend the series with both this and your patch squashed)\n\n---\n path.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/path.c b/path.c\nindex 777af35..21306ab 100644\n--- a/path.c\n+++ b/path.c\n@@ -191,7 +191,7 @@ static void *add_to_trie(struct trie *root, const\nchar *key, void *value)\n \n \t\tchild->len = root->len - i - 1;\n \t\tif (child->len) {\n-\t\t\tchild->contents = strndup(root->contents + i + 1,\n+\t\t\tchild->contents = xstrndup(root->contents + i + 1,\n \t\t\t\t\t\t   child->len);\n \t\t}\n \t\tchild->value = root->value;\n"}]}