git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Junio C Hamano <gitster@pobox.com>
Date
Jun 14, 2026, 15:22 UTC
Message-ID
<xmqq5x3ldu4h.fsf@gitster.g>
In-Reply-To
<cf50f1aabcf84aa755808318756c233305cc008d.1781419047.git.gitgitgadget@gmail.com>
"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 30 quoted lines
> diff --git a/cache-tree.c b/cache-tree.c
> index 7881b42aa2..4d2669b312 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -161,6 +161,54 @@ void cache_tree_invalidate_path(struct index_state *istate, const char *path)
>  		istate->cache_changed |= CACHE_TREE_CHANGED;
>  }
>  
> +/*
> + * Check whether this_ce and the next entry in the index form a D/F
> + * conflict ("path" vs "path/file").  Returns the conflicting "path/..."
> + * name when one is found, or NULL otherwise.
> + *
> + * The cache is sorted, so "path/file" sorts after "path" and the
> + * conflict is usually visible as adjacent entries.  But other entries
> + * can sort between them -- e.g. "path-internal" sits between "path"
> + * and "path/file" because '-' (0x2D) precedes '/' (0x2F) -- so when
> + * the immediately following entry shares our prefix but starts with a
> + * character that sorts before '/', binary search for "path/" instead.
> + */
> +static const char *find_df_conflict(struct index_state *istate,
> +				    const struct cache_entry *this_ce,
> +				    const struct cache_entry *next_ce)
> +{
> +	const char *this_name = this_ce->name;
> +	const char *next_name = next_ce->name;
> +	int this_len = ce_namelen(this_ce);
> +	const struct cache_entry *other;
> +	struct strbuf probe = STRBUF_INIT;
> +	int pos;
> +	if (this_len >= ce_namelen(next_ce) ||
> +	    next_name[this_len] > '/' ||
> +	    strncmp(this_name, next_name, this_len))
> +		return NULL;

First we reject an abvious "cannot conflict" case. If the current one is not strictly shorter than the next one, it cannot be an overlapping with one of the leading directories in the next one and the next one cannot be "hiding" an overlapping one in the "docs, docs-i, docs/r" relationship described in the log message (where next=="docs-i' hides the fact that this=="docs" conflicts with "docs/r"). Of course, the current one cannot be such a confliciting entry, if an earlier part of the next name does not entirely match the current name. In addition, if the byte after the matching leading part in the next name is larger than '/', any entry that comes later than the next name cannot have '/' at that byte position.

Makes sense.
> +	if (next_name[this_len] == '/')
> +		return next_name;
And if we see '/' there, we definitely have conflict right there.

So these trivial cases after us, we need to see if an entry that comes after next has a name whose leading part is identical to this name, plus '/'. How would we compute it?

> +	strbuf_add(&probe, this_name, this_len);
> +	strbuf_addch(&probe, '/');
> +	pos = index_name_pos_sparse(istate, probe.buf, probe.len);
> +	strbuf_release(&probe);

We see where the first of such a name (i.e. this name followed by '/') may appear. Normal cache entries in the index would never have a trailing slash in their names, so I expect that this would either find an directory that is sparsed out and returns a non-negative index into the .cache[] array, or a negative index that indicates where a name like this + '/' + anything would appear.

> +
> +	if (pos < 0)
> +		pos = -pos - 1;

So in order to check both cases, we do the usual index flipping. We do not need to to treat "it exists---that's sparse dir" case and "it is expanded and we are trying to find the first entry in that index" case differently below, which simplifies things a bit.

> +	if (pos >= (int)istate->cache_nr)
> +		return NULL;

OK, such an entry whose name is this followed by '/' does not exist so we are safe.

Show 6 quoted lines
> +	other = istate->cache[pos];
> +	if (ce_namelen(other) > this_len &&
> +	    other->name[this_len] == '/' &&
> +	    !strncmp(this_name, other->name, this_len))
> +		return other->name;
> +	return NULL;

This looks very similar to the inverse of the earlier one but slightly different. It might be easier to spot where it differs, if we flipped the polarity, like so, perhaps?

	other = istate->cache[pos];
	if (this_len >= ce_namelen(other) ||
	    other->name[this_len] != '/' ||
	    strncmp(this_name, other->name, this_len))
		return NULL;
	return other->name;

Or perhaps not. I do not care very strongly, but I only spotted the subtle difference while attempting to flip the polarity in my head, so it might help ther readers the same way. I dunno.

Thanks, looking very good.
Previous: Elijah Newren via GitGitGadget
Message 23 of 23 in “Duplicate entry hardening”
  1. 0/5 Duplicate entry hardeningElijah Newren via GitGitGadget, Apr 21, 2026
  2. 1/5 merge-ort: propagate callback errors from traverse_trees_wrapper()Elijah Newren via GitGitGadget, Apr 21, 2026
  3. Junio C HamanoJun 1, 2026
  4. Elijah NewrenJun 14, 2026
  5. 2/5 merge-ort: drop unnecessary show_all_errors from collect_merge_info()Elijah Newren via GitGitGadget, Apr 21, 2026
  6. Junio C HamanoJun 1, 2026
  7. 3/5 merge-ort: free diff pairs queue in clear_or_reinit_internal_opts()Elijah Newren via GitGitGadget, Apr 21, 2026
  8. 4/5 merge-ort: abort merge when trees have duplicate entriesElijah Newren via GitGitGadget, Apr 21, 2026
  9. Junio C HamanoJun 1, 2026
  10. 5/5 cache-tree: fix verify_cache() to catch non-adjacent D/F conflictsElijah Newren via GitGitGadget, Apr 21, 2026
  11. Junio C HamanoJun 1, 2026
  12. Elijah NewrenJun 14, 2026
  13. Junio C HamanoJun 1, 2026
  14. Patrick SteinhardtJun 1, 2026
  15. Automated reviews by AI (was Re: [PATCH 0/5] Duplicate entry hardening)Christian Couder, Jun 12, 2026
  16. Junio C HamanoJun 12, 2026
  17. 0/5 Duplicate entry hardeningElijah Newren via GitGitGadget, Jun 14, 2026
  18. 1/5 merge-ort: propagate callback errors from traverse_trees_wrapper()Elijah Newren via GitGitGadget, Jun 14, 2026
  19. 2/5 merge-ort: drop unnecessary show_all_errors from collect_merge_info()Elijah Newren via GitGitGadget, Jun 14, 2026
  20. 3/5 merge-ort: free diff pairs queue in clear_or_reinit_internal_opts()Elijah Newren via GitGitGadget, Jun 14, 2026
  21. 4/5 merge-ort: abort merge when trees have duplicate entriesElijah Newren via GitGitGadget, Jun 14, 2026
  22. 5/5 cache-tree: fix verify_cache() to catch non-adjacent D/F conflictsElijah Newren via GitGitGadget, Jun 14, 2026
  23. Junio C HamanoJun 14, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.