Re: [PATCH 5/5] cache-tree: fix verify_cache() to catch non-adjacent D/F conflicts

[Junio C Hamano <gitster@pobox.com>]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

> I could not find any caller in current git that both allows the index to
> get into this state and then tries to write it out without doing other
> checks beyond the verify_cache() call in cache_tree_update(), but
> verify_cache() is documented as a safety net for preventing corrupt
> trees and should actually provide that guarantee.

Oh, absolutely.  This kind of tightening is very much appreciated.

> diff --git a/cache-tree.c b/cache-tree.c
> index 7881b42aa2..f11844fe72 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -192,22 +192,62 @@ static int verify_cache(struct index_state *istate, int flags)
>  	for (i = 0; i + 1 < istate->cache_nr; i++) {
>  		/* path/file always comes after path because of the way
>  		 * the cache is sorted.  Also path can appear only once,
> -		 * which means conflicting one would immediately follow.
> +		 * so path/file is likely the immediately following path
> +		 * but might be separated if there is e.g. a
> +		 * path-internal/... file.
>  		 */
>  		const struct cache_entry *this_ce = istate->cache[i];
>  		const struct cache_entry *next_ce = istate->cache[i + 1];
>  		const char *this_name = this_ce->name;
>  		const char *next_name = next_ce->name;
>  		int this_len = ce_namelen(this_ce);
> +		const char *conflict_name = NULL;
> +
>  		if (this_len < ce_namelen(next_ce) &&
> -		    next_name[this_len] == '/' &&
> +		    next_name[this_len] <= '/' &&
>  		    strncmp(this_name, next_name, this_len) == 0) {
> +			if (next_name[this_len] == '/') {
> +				conflict_name = next_name;
> +			} else if (next_name[this_len] < '/') {
> +				/*
> +				 * The immediately next entry shares our
> +				 * prefix but sorts before "path/" (e.g.,
> +				 * "path-internal" between "path" and
> +				 * "path/file", since '-' (0x2D) < '/'
> +				 * (0x2F)).  Binary search to find where
> +				 * "path/" would be and check for a D/F
> +				 * conflict there.
> +				 */
> +				struct cache_entry *other;
> +				struct strbuf probe = STRBUF_INIT;
> +				int pos;
> +
> +				strbuf_add(&probe, this_name, this_len);
> +				strbuf_addch(&probe, '/');
> +				pos = index_name_pos_sparse(istate,
> +							    probe.buf,
> +							    probe.len);
> +				strbuf_release(&probe);
> +
> +				if (pos < 0)
> +					pos = -pos - 1;
> +				if (pos >= (int)istate->cache_nr)
> +					continue;
> +				other = istate->cache[pos];
> +				if (ce_namelen(other) > this_len &&
> +				    other->name[this_len] == '/' &&
> +				    !strncmp(this_name, other->name, this_len))
> +					conflict_name = other->name;
> +			}
> +		}

The narrow and tall comment block is a sign that this loop is
getting too deeply nested.  I wonder if it makes it easier to follow
if we extract this new logic into a small helper function on its
own?

What the code checks and how it does so both make sense to me, though.

Thanks.