Re: Efficiently detecting paths that differ from each other only in case

[Dun Peal <dunpealer@gmail.com>]

Thanks a lot everyone, and especially Jeff.

Running:

    git ls-tree -r HEAD

produces almost 100k lines of output, representing 100k total file +
directory count, which is a pretty big tree. I hope and expect to be
able to split out some branches in the future, but even with
everything included, the operation still only takes ~0.5s real (user +
sys).

So I think even with our relatively high user count and repository
traffic, that cost per commit should not completely break our
workflow.

Thus, I'm going to implement the hook to run the above command and
analyze the output per commit. Assumption is that with the script
overhead, we should be able to finish in less than a second, which is
reasonable latency.

I'll report back if there are any unexpected issues, or this doesn't
work as well as currently expected.

Thanks, D

On Sun, Oct 10, 2010 at 10:07 PM, Jeff King <peff@peff.net> wrote:
> On Fri, Oct 08, 2010 at 05:57:16PM -0500, Dun Peal wrote:
>
>> On Fri, Oct 8, 2010 at 3:06 PM, Jeff King <peff@peff.net> wrote:
>> > Re-reading your original message, I have a few more thoughts.
>> >
>> > One is that you don't need to do this per-commit. You probably want to
>> > do it per-updated-ref, each of which may be pushing many commits. And
>> > then you either reject the new ref value or not.
>>
>> I think I do, actually, because let's say the developer pushes two
>> commits, 1<-2. Suppose commit 1 violates the rule, but commit 2
>> reverts the violation. One might think that we don't care, since the
>> head will now be on 2, which is a correct state. But in fact we do,
>> because this is Git, and anyone may branch of from 1 in the future,
>> and voila we have a head in an incorrect state.
>
> Yeah, though it is not an especially likely state to branch from, since
> you have to specify it manually. However, a much more likely scenario is
> checkout out a past commit for testing, especially in bisection. So yes,
> if you want to be thorough, you need to check every commit.
>
>> Yeah, that's a pretty good idea, if not for the many ls-tree calls.
>> With their overhead, I strongly suspect it may be slower than the
>> solution you seem to propose, which is:
>>
>> git ls-tree -r <commit>
>>
>> which should give the full list of all paths in a commit, upon which I
>> can decide to accept or reject.
>
> Yeah, that is what I am proposing.
>
> One other thing you could try is to "ls-tree -r" the known-good state of
> the current HEAD at the beginning of the push, and then run "git log
> -diff-filter=AD --name-status $old..$new". For each commit in the log
> output, look for new entries that are in case-insensitive conflict with
> the existing tree, and then update your tree state appropriately with
> added and removed files. You only invoke two git commands, which saves
> on invocation overhead, and you only ls-tree once per push, not per
> commit. Git's internal diff shouldn't look at parts of the tree that
> aren't relevant.
>
> The downside is that the tree state you are keeping internally is not
> entirely accurate. For example, when receiving a merge between two
> parallel lines of development, you would process them linearly, when in
> fact there are two simultaneous different states. So there is a case
> where branch X removes "foo.txt" and branch Y adds "FOO.TXT", and then
> they merge. It looks OK because linearly, they did not both exist at the
> same time. But pre-merge, the commit in branch Y is broken.
>
> So really the straightforward approach of checking the tree state for
> each commit is probably simplest. If it's really too slow, you could try
> jgit or linking against git itself, which would eliminate the external
> process overhead.
>
> -Peff
>