Re: [BUG] diffcore-rename with duplicate tree entries can segfault

[Jeff King <peff@peff.net>]

On Tue, Feb 24, 2015 at 02:42:42PM -0800, Junio C Hamano wrote:

> > That does fix this problem, and it doesn't break any other tests. But
> > frankly, I don't know what I'm doing and this feels like a giant hack.
> >
> > Given that this is tangentially related to the "-B -M" stuff you've been
> > looking at (and it's your code in the first place :) ), I thought you
> > might have some insight.
> 
> Indeed.
> 
> Honestly, I'd rather see us diagnose duplicate filepairs as an error
> and drop them on the floor upon entry to the diffcore_std(), even
> before we go into the rename codepath.

Yeah, I had a similar thought. Just saying "your diff is broken, we
can't do rename detection" is totally reasonable to me.

My main concern with that approach is that we would waste time finding
the duplicate paths, for something that comes up only rarely. At the
time of locate_rename_dst, we've already created a mapping, and it's
very easy to detect the duplicates. But before that, we have only the
linear list of queued items.

In theory they're sorted and we could do an O(n) pass to find
duplicates. But I'm not sure if the sorting holds in the face of other
breakages (like unsorted trees; they also shouldn't happen, but the
whole point here is to gracefully handle things that shouldn't).

I dunno. Maybe we could do an O(n) pass to check sort order and
uniqueness. If either fails (which should be rare), then we sort and
re-check uniqueness.

I'm assuming there _is_ a sane sort order. We have two halves of a
filepair, but I think before any of the rename or break detection kicks
in, each pair should either:

  1. Have a name in pair->one, and an invalid filespec in pair->two
     (i.e., a deletion).

  2. The opposite (name in pair->two, /dev/null in pair->one). An
     addition.

  3. The same name in pair->one and pair->two.

-Peff