# [PATCH 1/5] Documentation: mention more worktree-specific exceptions 14 messages from 2019-10-21 to 2019-10-28. Participants: SZEDER Gábor, David Turner, Junio C Hamano, Johannes Schindelin. Thread: https://gitlist.dev/t/52082 ## SZEDER Gábor, 2019-10-21 16:00 Subject: [PATCH 1/5] Documentation: mention more worktree-specific exceptions Message-ID: <20191021160043.701-2-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20191021160043.701-2-szeder.dev%40gmail.com In-Reply-To: <20191021160043.701-1-szeder.dev@gmail.com> ``` If a directory in $GIT_DIR is overridden when $GIT_COMMON_DIR is set, then usually all paths within that directory are overridden as well. There are a couple of exceptions, though, and two of them, namely 'refs/rewritten' and 'logs/HEAD' are not mentioned in 'gitrepository-layout'. Document them as well. Signed-off-by: SZEDER Gábor --- Documentation/gitrepository-layout.txt | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/Documentation/gitrepository-layout.txt b/Documentation/gitrepository-layout.txt index d6388f10bb..1a2ef4c150 100644 --- a/Documentation/gitrepository-layout.txt +++ b/Documentation/gitrepository-layout.txt @@ -96,9 +96,9 @@ refs:: directory. The 'git prune' command knows to preserve objects reachable from refs found in this directory and its subdirectories. - This directory is ignored (except refs/bisect and - refs/worktree) if $GIT_COMMON_DIR is set and - "$GIT_COMMON_DIR/refs" will be used instead. + This directory is ignored (except refs/bisect, + refs/rewritten and refs/worktree) if $GIT_COMMON_DIR is + set and "$GIT_COMMON_DIR/refs" will be used instead. refs/heads/`name`:: records tip-of-the-tree commit objects of branch `name` @@ -240,8 +240,8 @@ remotes:: logs:: Records of changes made to refs are stored in this directory. See linkgit:git-update-ref[1] for more information. This - directory is ignored if $GIT_COMMON_DIR is set and - "$GIT_COMMON_DIR/logs" will be used instead. + directory is ignored (except logs/HEAD) if $GIT_COMMON_DIR is + set and "$GIT_COMMON_DIR/logs" will be used instead. logs/refs/heads/`name`:: Records all changes made to the branch tip named `name`. -- 2.24.0.rc0.472.ga6f06c86b4 ``` ## SZEDER Gábor, 2019-10-21 16:00 Subject: [PATCH 0/5] path.c: a couple of common dir/trie fixes Message-ID: <20191021160043.701-1-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20191021160043.701-1-szeder.dev%40gmail.com In-Reply-To: <20191018113557.GA29845@szeder.dev> ``` On Fri, Oct 18, 2019 at 01:35:57PM +0200, SZEDER Gábor wrote: > > unfortunately, see two more bugs, And there are documentation bugs as well, both user-visible (i.e. in a man page) and in in-code comment. > > and one of them is a "proper" bug leading to bogus > > output: > > > > $ git -C WT/ rev-parse --git-path logs/refs --git-path logs/refs/ > > /home/szeder/src/git/.git/logs/refs > > /home/szeder/src/git/.git/worktrees/WT/logs/refs/ > > This one-liner below fixes it, but I haven't yet made up my mind about > whether this is the right fix or whether there could be any fallout > (at least the test suite doesn't show any). > > $ ./git -C WT/ rev-parse --git-path logs/refs --git-path logs/refs/ > /home/szeder/src/git/.git/logs/refs > /home/szeder/src/git/.git/logs/refs/ > > > diff --git a/path.c b/path.c > index 04b69b9feb..9019169418 100644 > --- a/path.c > +++ b/path.c > @@ -335,7 +335,7 @@ static int check_common(const char *unmatched, void *value, void *baton) > struct common_dir *dir = value; > > if (!dir) > - return 0; > + return -1; > > if (dir->is_dir && (unmatched[0] == 0 || unmatched[0] == '/')) > return !dir->exclude; Now I made up mind: this isn't the right fix :) The proper fix is in the last patch of this series. Cc-ing David Turner, the trie's author; if I misunderstood anything, then hopefully he can spot and clarify it. SZEDER Gábor (5): Documentation: mention more worktree-specific exceptions path.c: clarify trie_find()'s in-code comment path.c: mark 'logs/HEAD' in 'common_list' as file path.c: clarify two field names in 'struct common_dir' path.c: don't call the match function without value in trie_find() Documentation/gitrepository-layout.txt | 10 +- path.c | 122 ++++++++++++++----------- t/t0060-path-utils.sh | 2 + 3 files changed, 74 insertions(+), 60 deletions(-) -- 2.24.0.rc0.472.ga6f06c86b4 ``` ## SZEDER Gábor, 2019-10-21 16:00 Subject: [PATCH 3/5] path.c: mark 'logs/HEAD' in 'common_list' as file Message-ID: <20191021160043.701-4-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20191021160043.701-4-szeder.dev%40gmail.com In-Reply-To: <20191021160043.701-1-szeder.dev@gmail.com> ``` 'logs/HEAD', i.e. HEAD's reflog, is a file, but its entry in 'common_list' has the 'is_dir' bit set. Unset that bit to make it consistent with what 'logs/HEAD' is supposed to be. This doesn't make a difference in behavior: check_common() is the only function that looks at the 'is_dir' bit, and that function either returns 0, or '!exclude', which for 'logs/HEAD' results in 0 as well. Signed-off-by: SZEDER Gábor --- path.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/path.c b/path.c index 4ac9a101f5..3fac5f5726 100644 --- a/path.c +++ b/path.c @@ -113,7 +113,7 @@ static struct common_dir common_list[] = { { 0, 1, 0, "info" }, { 0, 0, 1, "info/sparse-checkout" }, { 1, 1, 0, "logs" }, - { 1, 1, 1, "logs/HEAD" }, + { 1, 0, 1, "logs/HEAD" }, { 0, 1, 1, "logs/refs/bisect" }, { 0, 1, 1, "logs/refs/rewritten" }, { 0, 1, 1, "logs/refs/worktree" }, -- 2.24.0.rc0.472.ga6f06c86b4 ``` ## SZEDER Gábor, 2019-10-21 16:00 Subject: [PATCH 2/5] path.c: clarify trie_find()'s in-code comment Message-ID: <20191021160043.701-3-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20191021160043.701-3-szeder.dev%40gmail.com In-Reply-To: <20191021160043.701-1-szeder.dev@gmail.com> ``` A fairly long comment describes trie_find()'s behavior and shows examples, but it's slightly incomplete/inaccurate. Update this comment to specify how trie_find() handles a negative return value from the given match function. Furthermore, update the list of examples to include not only two but three levels of path components. This makes the examples slightly more complicated, but it can illustrate the behavior in more corner cases. Finally, basically everything refers to the data stored for a key as "value", with two confusing exceptions: - The type definition of the match function calls its corresponding parameter 'data'. Rename that parameter to 'value'. (check_common(), the only function of this type already calls it 'value'). - The table of examples above trie_find() has a "val from node" column, which has nothing to do with the value stored in the trie: it's a "prefix of the key for which the trie contains a value" that led to that node. Rename that column header to "prefix to node". Note that neither the original nor the updated description and examples correspond 100% to the current implementation, because the implementation is a bit buggy, but the comment describes the desired behavior. The bug will be fixed in the last patch of this series. Signed-off-by: SZEDER Gábor --- path.c | 45 ++++++++++++++++++++++++++++----------------- 1 file changed, 28 insertions(+), 17 deletions(-) diff --git a/path.c b/path.c index e3da1f3c4e..4ac9a101f5 100644 --- a/path.c +++ b/path.c @@ -236,30 +236,41 @@ static void *add_to_trie(struct trie *root, const char *key, void *value) return old; } -typedef int (*match_fn)(const char *unmatched, void *data, void *baton); +typedef int (*match_fn)(const char *unmatched, void *value, void *baton); /* * Search a trie for some key. Find the longest /-or-\0-terminated - * prefix of the key for which the trie contains a value. Call fn - * with the unmatched portion of the key and the found value, and - * return its return value. If there is no such prefix, return -1. + * prefix of the key for which the trie contains a value. If there is + * no such prefix, return -1. Otherwise call fn with the unmatched + * portion of the key and the found value. If fn returns 0 or + * positive, then return its return value. If fn returns negative, + * then call fn with the next-longest /-terminated prefix of the key + * (i.e. a parent directory) for which the trie contains a value, and + * handle its return value the same way. If there is no shorter + * /-terminated prefix with a value left, then return the negative + * return value of the most recent fn invocation. * * The key is partially normalized: consecutive slashes are skipped. * - * For example, consider the trie containing only [refs, - * refs/worktree] (both with values). - * - * | key | unmatched | val from node | return value | - * |-----------------|------------|---------------|--------------| - * | a | not called | n/a | -1 | - * | refs | \0 | refs | as per fn | - * | refs/ | / | refs | as per fn | - * | refs/w | /w | refs | as per fn | - * | refs/worktree | \0 | refs/worktree | as per fn | - * | refs/worktree/ | / | refs/worktree | as per fn | - * | refs/worktree/a | /a | refs/worktree | as per fn | - * |-----------------|------------|---------------|--------------| + * For example, consider the trie containing only [logs, + * logs/refs/bisect], both with values, but not logs/refs. * + * | key | unmatched | prefix to node | return value | + * |--------------------|----------------|------------------|--------------| + * | a | not called | n/a | -1 | + * | logstore | not called | n/a | -1 | + * | logs | \0 | logs | as per fn | + * | logs/ | / | logs | as per fn | + * | logs/refs | /refs | logs | as per fn | + * | logs/refs/ | /refs/ | logs | as per fn | + * | logs/refs/b | /refs/b | logs | as per fn | + * | logs/refs/bisected | /refs/bisected | logs | as per fn | + * | logs/refs/bisect | \0 | logs/refs/bisect | as per fn | + * | logs/refs/bisect/ | / | logs/refs/bisect | as per fn | + * | logs/refs/bisect/a | /a | logs/refs/bisect | as per fn | + * | (If fn in the previous line returns -1, then fn is called once more:) | + * | logs/refs/bisect/a | /refs/bisect/a | logs | as per fn | + * |--------------------|----------------|------------------|--------------| */ static int trie_find(struct trie *root, const char *key, match_fn fn, void *baton) -- 2.24.0.rc0.472.ga6f06c86b4 ``` ## SZEDER Gábor, 2019-10-21 16:00 Subject: [PATCH 4/5] path.c: clarify two field names in 'struct common_dir' Message-ID: <20191021160043.701-5-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20191021160043.701-5-szeder.dev%40gmail.com In-Reply-To: <20191021160043.701-1-szeder.dev@gmail.com> ``` An array of 'struct common_dir' instances is used to specify whether various paths in $GIT_DIR are specific to a worktree, or are common, i.e. belong to main worktree. The names of two fields in this struct are somewhat confusing or ambigious: - The path is recorded in the struct's 'dirname' field, even though several entries are regular files e.g. 'gc.pid', 'packed-refs', etc. Rename this field to 'path' to reduce confusion. - The field 'exclude' tells whether the path is excluded... from where? Excluded from the common dir or from the worktree? It means the former, but it's ambigious. Rename this field to 'is_common' to make it unambigious what it means. This, however, means the exact opposite of what 'exclude' meant, so we have to negate the field's value in all entries as well. The diff is best viewed with '--color-words'. Signed-off-by: SZEDER Gábor --- path.c | 66 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 33 insertions(+), 33 deletions(-) diff --git a/path.c b/path.c index 3fac5f5726..cf57bd52dd 100644 --- a/path.c +++ b/path.c @@ -101,36 +101,36 @@ struct common_dir { /* Not considered garbage for report_linked_checkout_garbage */ unsigned ignore_garbage:1; unsigned is_dir:1; - /* Not common even though its parent is */ - unsigned exclude:1; - const char *dirname; + /* Belongs to the common dir, though it may contain paths that don't */ + unsigned is_common:1; + const char *path; }; static struct common_dir common_list[] = { - { 0, 1, 0, "branches" }, - { 0, 1, 0, "common" }, - { 0, 1, 0, "hooks" }, - { 0, 1, 0, "info" }, - { 0, 0, 1, "info/sparse-checkout" }, - { 1, 1, 0, "logs" }, - { 1, 0, 1, "logs/HEAD" }, - { 0, 1, 1, "logs/refs/bisect" }, - { 0, 1, 1, "logs/refs/rewritten" }, - { 0, 1, 1, "logs/refs/worktree" }, - { 0, 1, 0, "lost-found" }, - { 0, 1, 0, "objects" }, - { 0, 1, 0, "refs" }, - { 0, 1, 1, "refs/bisect" }, - { 0, 1, 1, "refs/rewritten" }, - { 0, 1, 1, "refs/worktree" }, - { 0, 1, 0, "remotes" }, - { 0, 1, 0, "worktrees" }, - { 0, 1, 0, "rr-cache" }, - { 0, 1, 0, "svn" }, - { 0, 0, 0, "config" }, - { 1, 0, 0, "gc.pid" }, - { 0, 0, 0, "packed-refs" }, - { 0, 0, 0, "shallow" }, + { 0, 1, 1, "branches" }, + { 0, 1, 1, "common" }, + { 0, 1, 1, "hooks" }, + { 0, 1, 1, "info" }, + { 0, 0, 0, "info/sparse-checkout" }, + { 1, 1, 1, "logs" }, + { 1, 0, 0, "logs/HEAD" }, + { 0, 1, 0, "logs/refs/bisect" }, + { 0, 1, 0, "logs/refs/rewritten" }, + { 0, 1, 0, "logs/refs/worktree" }, + { 0, 1, 1, "lost-found" }, + { 0, 1, 1, "objects" }, + { 0, 1, 1, "refs" }, + { 0, 1, 0, "refs/bisect" }, + { 0, 1, 0, "refs/rewritten" }, + { 0, 1, 0, "refs/worktree" }, + { 0, 1, 1, "remotes" }, + { 0, 1, 1, "worktrees" }, + { 0, 1, 1, "rr-cache" }, + { 0, 1, 1, "svn" }, + { 0, 0, 1, "config" }, + { 1, 0, 1, "gc.pid" }, + { 0, 0, 1, "packed-refs" }, + { 0, 0, 1, "shallow" }, { 0, 0, 0, NULL } }; @@ -331,8 +331,8 @@ static void init_common_trie(void) if (common_trie_done_setup) return; - for (p = common_list; p->dirname; p++) - add_to_trie(&common_trie, p->dirname, p); + for (p = common_list; p->path; p++) + add_to_trie(&common_trie, p->path, p); common_trie_done_setup = 1; } @@ -349,10 +349,10 @@ static int check_common(const char *unmatched, void *value, void *baton) return 0; if (dir->is_dir && (unmatched[0] == 0 || unmatched[0] == '/')) - return !dir->exclude; + return dir->is_common; if (!dir->is_dir && unmatched[0] == 0) - return !dir->exclude; + return dir->is_common; return 0; } @@ -376,8 +376,8 @@ void report_linked_checkout_garbage(void) return; strbuf_addf(&sb, "%s/", get_git_dir()); len = sb.len; - for (p = common_list; p->dirname; p++) { - const char *path = p->dirname; + for (p = common_list; p->path; p++) { + const char *path = p->path; if (p->ignore_garbage) continue; strbuf_setlen(&sb, len); -- 2.24.0.rc0.472.ga6f06c86b4 ``` ## SZEDER Gábor, 2019-10-21 16:00 Subject: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: <20191021160043.701-6-szeder.dev@gmail.com> URL: https://gitlist.dev/e/20191021160043.701-6-szeder.dev%40gmail.com In-Reply-To: <20191021160043.701-1-szeder.dev@gmail.com> ``` 'logs/refs' is not a working tree-specific path, but since commit b9317d55a3 (Make sure refs/rewritten/ is per-worktree, 2019-03-07) 'git rev-parse --git-path' has been returning a bogus path if a trailing '/' is present: $ git -C WT/ rev-parse --git-path logs/refs --git-path logs/refs/ /home/szeder/src/git/.git/logs/refs /home/szeder/src/git/.git/worktrees/WT/logs/refs/ We use a trie data structure to efficiently decide whether a path belongs to the common dir or is working tree-specific. As it happens b9317d55a3 triggered a bug that is as old as the trie implementation itself, added in 4e09cf2acf (path: optimize common dir checking, 2015-08-31). - According to the comment describing trie_find(), it should only call the given match function 'fn' for a "/-or-\0-terminated prefix of the key for which the trie contains a value". This is not true: there are three places where trie_find() calls the match function, but one of them is missing the check for value's existence. - b9317d55a3 added two new keys to the trie: 'logs/refs/rewritten' and 'logs/refs/worktree', next to the already existing 'logs/refs/bisect'. This resulted in a trie node with the path 'logs/refs', which didn't exist before, and which doesn't have a value attached. A query for 'logs/refs/' finds this node and then hits that one callsite of the match function which doesn't check for the value's existence, and thus invokes the match function with NULL as value. - When the match function check_common() is invoked with a NULL value, it returns 0, which indicates that the queried path doesn't belong to the common directory, ultimately resulting the bogus path shown above. Add the missing condition to trie_find() so it will never invoke the match function with a non-existing value. check_common() will then no longer have to check that it got a non-NULL value, so remove that condition. I believe that there are no other paths that could cause similar bogus output. AFAICT the only other key resulting in the match function being called with a NULL value is 'co' (because of the keys 'common' and 'config'). However, as they are not in a directory that belongs to the common directory the resulting working tree-specific path is expected. Signed-off-by: SZEDER Gábor --- path.c | 11 ++++++----- t/t0060-path-utils.sh | 2 ++ 2 files changed, 8 insertions(+), 5 deletions(-) diff --git a/path.c b/path.c index cf57bd52dd..e21b00c4d4 100644 --- a/path.c +++ b/path.c @@ -299,9 +299,13 @@ static int trie_find(struct trie *root, const char *key, match_fn fn, /* Matched the entire compressed section */ key += i; - if (!*key) + if (!*key) { /* End of key */ - return fn(key, root->value, baton); + if (root->value) + return fn(key, root->value, baton); + else + return -1; + } /* Partial path normalization: skip consecutive slashes */ while (key[0] == '/' && key[1] == '/') @@ -345,9 +349,6 @@ 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->is_common; diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh index c7b53e494b..501e1a288d 100755 --- a/t/t0060-path-utils.sh +++ b/t/t0060-path-utils.sh @@ -288,6 +288,8 @@ 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/bisect/foo .git/logs/refs/bisect/foo +test_git_path GIT_COMMON_DIR=bar logs/refs bar/logs/refs +test_git_path GIT_COMMON_DIR=bar logs/refs/ bar/logs/refs/ test_git_path GIT_COMMON_DIR=bar logs/refs/bisec/foo bar/logs/refs/bisec/foo test_git_path GIT_COMMON_DIR=bar logs/refs/bisec bar/logs/refs/bisec test_git_path GIT_COMMON_DIR=bar logs/refs/bisectfoo bar/logs/refs/bisectfoo -- 2.24.0.rc0.472.ga6f06c86b4 ``` ## David Turner, 2019-10-21 17:39 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: <0f62325e46901322346184b47329940f7700a1e3.camel@novalis.org> URL: https://gitlist.dev/e/0f62325e46901322346184b47329940f7700a1e3.camel%40novalis.org In-Reply-To: <20191021160043.701-6-szeder.dev@gmail.com> ``` On Mon, 2019-10-21 at 18:00 +0200, SZEDER Gábor wrote: > Add the missing condition to trie_find() so it will never invoke the > match function with a non-existing value. check_common() will then > no > longer have to check that it got a non-NULL value, so remove that > condition. ... > > /* Partial path normalization: skip consecutive slashes */ > while (key[0] == '/' && key[1] == '/') > @@ -345,9 +349,6 @@ static int check_common(const char *unmatched, > void *value, void *baton) > { > struct common_dir *dir = value; > > - if (!dir) > - return 0; Do we want to assert(dir) here? Overall, LGTM. Thanks for the clean-up. ``` ## SZEDER Gábor, 2019-10-21 20:57 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: <20191021205703.GB4348@szeder.dev> URL: https://gitlist.dev/e/20191021205703.GB4348%40szeder.dev In-Reply-To: <20191021160043.701-6-szeder.dev@gmail.com> ``` On Mon, Oct 21, 2019 at 06:00:43PM +0200, SZEDER Gábor wrote: > 'logs/refs' is not a working tree-specific path, but since commit > b9317d55a3 (Make sure refs/rewritten/ is per-worktree, 2019-03-07) > 'git rev-parse --git-path' has been returning a bogus path if a > trailing '/' is present: > > $ git -C WT/ rev-parse --git-path logs/refs --git-path logs/refs/ > /home/szeder/src/git/.git/logs/refs > /home/szeder/src/git/.git/worktrees/WT/logs/refs/ > > We use a trie data structure to efficiently decide whether a path > belongs to the common dir or is working tree-specific. As it happens > b9317d55a3 triggered a bug that is as old as the trie implementation > itself, added in 4e09cf2acf (path: optimize common dir checking, > 2015-08-31). > > - According to the comment describing trie_find(), it should only > call the given match function 'fn' for a "/-or-\0-terminated > prefix of the key for which the trie contains a value". This is > not true: there are three places where trie_find() calls the match > function, but one of them is missing the check for value's > existence. > > - b9317d55a3 added two new keys to the trie: 'logs/refs/rewritten' > and 'logs/refs/worktree', next to the already existing > 'logs/refs/bisect'. This resulted in a trie node with the path > 'logs/refs', which didn't exist before, and which doesn't have a Oops, I missed the trailing slash, that must be 'logs/refs/'! > value attached. A query for 'logs/refs/' finds this node and then > hits that one callsite of the match function which doesn't check > for the value's existence, and thus invokes the match function > with NULL as value. ``` ## Junio C Hamano, 2019-10-23 04:01 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: URL: https://gitlist.dev/e/xmqqa79si003.fsf%40gitster-ct.c.googlers.com In-Reply-To: <20191021205703.GB4348@szeder.dev> ``` SZEDER Gábor writes: >> - b9317d55a3 added two new keys to the trie: 'logs/refs/rewritten' >> and 'logs/refs/worktree', next to the already existing >> 'logs/refs/bisect'. This resulted in a trie node with the path >> 'logs/refs', which didn't exist before, and which doesn't have a > > Oops, I missed the trailing slash, that must be 'logs/refs/'! > >> value attached. A query for 'logs/refs/' finds this node and then >> hits that one callsite of the match function which doesn't check >> for the value's existence, and thus invokes the match function >> with NULL as value. Given that the trie is maintained by hand in common_list[], I wonder if we can mechanically catch errors like the one b9317d55a3 added, by perhaps having a self-test function that a t/helper/ program calls to perform consistency check after the "git" gets built. Thanks. ``` ## SZEDER Gábor, 2019-10-23 16:20 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: <20191023162048.GI4348@szeder.dev> URL: https://gitlist.dev/e/20191023162048.GI4348%40szeder.dev In-Reply-To: ``` On Wed, Oct 23, 2019 at 01:01:00PM +0900, Junio C Hamano wrote: > SZEDER Gábor writes: > > >> - b9317d55a3 added two new keys to the trie: 'logs/refs/rewritten' > >> and 'logs/refs/worktree', next to the already existing > >> 'logs/refs/bisect'. This resulted in a trie node with the path > >> 'logs/refs', which didn't exist before, and which doesn't have a > > > > Oops, I missed the trailing slash, that must be 'logs/refs/'! > > > >> value attached. A query for 'logs/refs/' finds this node and then > >> hits that one callsite of the match function which doesn't check > >> for the value's existence, and thus invokes the match function > >> with NULL as value. > > Given that the trie is maintained by hand in common_list[], I wonder > if we can mechanically catch errors like the one b9317d55a3 added, > by perhaps having a self-test function that a t/helper/ program > calls to perform consistency check after the "git" gets built. I'm not sure what you mean by "consistency check". The resulting trie looked as expected both before and after b9317d55a3, i.e. each trie node had the right contents, value, and children, as far as I could tell. The issue was in the lookup function. ``` ## Junio C Hamano, 2019-10-24 03:29 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: URL: https://gitlist.dev/e/xmqq5zkehld3.fsf%40gitster-ct.c.googlers.com In-Reply-To: <20191023162048.GI4348@szeder.dev> ``` SZEDER Gábor writes: > I'm not sure what you mean by "consistency check". The resulting trie > looked as expected both before and after b9317d55a3, i.e. each trie > node had the right contents, value, and children, as far as I could > tell. The issue was in the lookup function. I saw the change to the code as a band-aid, which wouldn't have been necessary if we had the missing refs/ entry. Fully populating the leading levels explicitly may give the application more flexibility by yielding results different from hardcoded -1 like the patched code gives. But perhaps treating a path that matches a missing intermediate level just like a path that did not match anything in the trie is what we want anyway, so I guess the code change was the right thing (as opposed to a band-aid). Thanks. ``` ## Johannes Schindelin, 2019-10-28 10:57 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: URL: https://gitlist.dev/e/nycvar.QRO.7.76.6.1910281155220.46%40tvgsbejvaqbjf.bet In-Reply-To: <20191021160043.701-6-szeder.dev@gmail.com> ``` Hi Gábor, On Mon, 21 Oct 2019, SZEDER Gábor wrote: > 'logs/refs' is not a working tree-specific path, but since commit > b9317d55a3 (Make sure refs/rewritten/ is per-worktree, 2019-03-07) > 'git rev-parse --git-path' has been returning a bogus path if a > trailing '/' is present: > > $ git -C WT/ rev-parse --git-path logs/refs --git-path logs/refs/ > /home/szeder/src/git/.git/logs/refs > /home/szeder/src/git/.git/worktrees/WT/logs/refs/ > > We use a trie data structure to efficiently decide whether a path > belongs to the common dir or is working tree-specific. As it happens > b9317d55a3 triggered a bug that is as old as the trie implementation > itself, added in 4e09cf2acf (path: optimize common dir checking, > 2015-08-31). > > - According to the comment describing trie_find(), it should only > call the given match function 'fn' for a "/-or-\0-terminated > prefix of the key for which the trie contains a value". This is > not true: there are three places where trie_find() calls the match > function, but one of them is missing the check for value's > existence. > > - b9317d55a3 added two new keys to the trie: 'logs/refs/rewritten' > and 'logs/refs/worktree', next to the already existing > 'logs/refs/bisect'. This resulted in a trie node with the path > 'logs/refs', which didn't exist before, and which doesn't have a > value attached. A query for 'logs/refs/' finds this node and then > hits that one callsite of the match function which doesn't check > for the value's existence, and thus invokes the match function > with NULL as value. > > - When the match function check_common() is invoked with a NULL > value, it returns 0, which indicates that the queried path doesn't > belong to the common directory, ultimately resulting the bogus > path shown above. > > Add the missing condition to trie_find() so it will never invoke the > match function with a non-existing value. check_common() will then no > longer have to check that it got a non-NULL value, so remove that > condition. > > I believe that there are no other paths that could cause similar bogus > output. AFAICT the only other key resulting in the match function > being called with a NULL value is 'co' (because of the keys 'common' > and 'config'). However, as they are not in a directory that belongs > to the common directory the resulting working tree-specific path is > expected. > > Signed-off-by: SZEDER Gábor Thank you for this entire patch series. Just one nit: > diff --git a/path.c b/path.c > index cf57bd52dd..e21b00c4d4 100644 > --- a/path.c > +++ b/path.c > @@ -299,9 +299,13 @@ static int trie_find(struct trie *root, const char *key, match_fn fn, > > /* Matched the entire compressed section */ > key += i; > - if (!*key) > + if (!*key) { > /* End of key */ > - return fn(key, root->value, baton); > + if (root->value) > + return fn(key, root->value, baton); > + else > + return -1; I would have preferred this: + if (!root->value) + return -1; + return fn(key, root->value, baton); ... as it would more accurately reflect my mental model of an "early out". But as I said, this is just a nit-pick. Thank you for working on this! Dscho > + } > > /* Partial path normalization: skip consecutive slashes */ > while (key[0] == '/' && key[1] == '/') > @@ -345,9 +349,6 @@ 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->is_common; > > diff --git a/t/t0060-path-utils.sh b/t/t0060-path-utils.sh > index c7b53e494b..501e1a288d 100755 > --- a/t/t0060-path-utils.sh > +++ b/t/t0060-path-utils.sh > @@ -288,6 +288,8 @@ 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/bisect/foo .git/logs/refs/bisect/foo > +test_git_path GIT_COMMON_DIR=bar logs/refs bar/logs/refs > +test_git_path GIT_COMMON_DIR=bar logs/refs/ bar/logs/refs/ > test_git_path GIT_COMMON_DIR=bar logs/refs/bisec/foo bar/logs/refs/bisec/foo > test_git_path GIT_COMMON_DIR=bar logs/refs/bisec bar/logs/refs/bisec > test_git_path GIT_COMMON_DIR=bar logs/refs/bisectfoo bar/logs/refs/bisectfoo > -- > 2.24.0.rc0.472.ga6f06c86b4 > > ``` ## SZEDER Gábor, 2019-10-28 12:00 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: <20191028120054.GS4348@szeder.dev> URL: https://gitlist.dev/e/20191028120054.GS4348%40szeder.dev In-Reply-To: ``` On Mon, Oct 28, 2019 at 11:57:10AM +0100, Johannes Schindelin wrote: > > - According to the comment describing trie_find(), it should only > > call the given match function 'fn' for a "/-or-\0-terminated > > prefix of the key for which the trie contains a value". This is > > not true: there are three places where trie_find() calls the match > > function, but one of them is missing the check for value's > > existence. > Thank you for this entire patch series. Just one nit: > > > > diff --git a/path.c b/path.c > > index cf57bd52dd..e21b00c4d4 100644 > > --- a/path.c > > +++ b/path.c > > @@ -299,9 +299,13 @@ static int trie_find(struct trie *root, const char *key, match_fn fn, > > > > /* Matched the entire compressed section */ > > key += i; > > - if (!*key) > > + if (!*key) { > > /* End of key */ > > - return fn(key, root->value, baton); > > + if (root->value) > > + return fn(key, root->value, baton); > > + else > > + return -1; > > I would have preferred this: > > + if (!root->value) > + return -1; > + return fn(key, root->value, baton); > > ... as it would more accurately reflect my mental model of an "early > out". The checks at the other two of those three callsites look like this, and I just followed suit for the sake of consistency. ``` ## Johannes Schindelin, 2019-10-28 21:30 Subject: Re: [PATCH 5/5] path.c: don't call the match function without value in trie_find() Message-ID: URL: https://gitlist.dev/e/nycvar.QRO.7.76.6.1910282229480.46%40tvgsbejvaqbjf.bet In-Reply-To: <20191028120054.GS4348@szeder.dev> ``` Hi Gábor, On Mon, 28 Oct 2019, SZEDER Gábor wrote: > On Mon, Oct 28, 2019 at 11:57:10AM +0100, Johannes Schindelin wrote: > > > - According to the comment describing trie_find(), it should only > > > call the given match function 'fn' for a "/-or-\0-terminated > > > prefix of the key for which the trie contains a value". This is > > > not true: there are three places where trie_find() calls the match > > > function, but one of them is missing the check for value's > > > existence. > > > Thank you for this entire patch series. Just one nit: > > > > > > > diff --git a/path.c b/path.c > > > index cf57bd52dd..e21b00c4d4 100644 > > > --- a/path.c > > > +++ b/path.c > > > @@ -299,9 +299,13 @@ static int trie_find(struct trie *root, const char *key, match_fn fn, > > > > > > /* Matched the entire compressed section */ > > > key += i; > > > - if (!*key) > > > + if (!*key) { > > > /* End of key */ > > > - return fn(key, root->value, baton); > > > + if (root->value) > > > + return fn(key, root->value, baton); > > > + else > > > + return -1; > > > > I would have preferred this: > > > > + if (!root->value) > > + return -1; > > + return fn(key, root->value, baton); > > > > ... as it would more accurately reflect my mental model of an "early > > out". > > The checks at the other two of those three callsites look like this, > and I just followed suit for the sake of consistency. Oh, okay. Sorry for the noise, then. Thanks, Dscho ```