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

From: Jeff King <peff@peff.net>
Date: Feb 24, 2015, 22:49 UTC
Message-ID: <20150224224918.GA24749@peff.net>
In-Reply-To: <xmqqh9uborrx.fsf@gitster.dls.corp.google.com>

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

Show 12 quoted lines

> > 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