{"thread":{"id":"25389","subject":"Efficiently detecting paths that differ from each other only in case","startedAt":"2010-10-08T06:13:07Z","lastAt":"2010-10-17T04:25:25Z","messageCount":14,"participants":["Dun Peal","Jeff King","Jonathan Nieder","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"152947","messageId":"AANLkTimGAbosbD0pprROu_g-UW38faotYA2dTxj9scsP@mail.gmail.com","threadId":"25389","inReplyTo":null,"subject":"Efficiently detecting paths that differ from each other only in case","fromName":"Dun Peal","fromEmail":"dunpealer@gmail.com","sentAt":"2010-10-08T06:13:07Z","receivedAt":"2010-10-08T06:13:07Z","isPatch":false,"sender":{"key":"dunpealer@gmail.com","avatar":"https://gravatar.com/avatar/42f3e6a1166eb44e33f24c20ccbe809fa8591413f366dfe3755c8a8d4935ace9?d=mp&s=160"},"body":"Hi,\n\nI'm writing a Git hook, for a bare central repo, to reject pushes of\npaths that differ from existing tracked paths only by letter case.\n\nSo, for example, if the following path is tracked in the repo:\n\nfoo/bar.py\n\nCommits adding any of the following paths would be rejected:\n\nFoo/bar.py\nfoo/Bar.py\nfOO/BAR.py\n\nEtc. I know how to do it by listing paths with ls-files, but my repo\ncontains many thousands of files, so I was wondering if there was a\nmore efficient way than for every commit:\n\n1. Get a list of all paths in the repo from ls-files.\n2. Lowercase all paths.\n3. Check for repeats.\n\nThanks, D\n"},{"id":"152974","messageId":"20101008135034.GC5163@sigill.intra.peff.net","threadId":"25389","inReplyTo":"AANLkTimGAbosbD0pprROu_g-UW38faotYA2dTxj9scsP@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-10-08T13:50:34Z","receivedAt":"2010-10-08T13:50:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 08, 2010 at 01:13:07AM -0500, Dun Peal wrote:\n\n> Etc. I know how to do it by listing paths with ls-files, but my repo\n> contains many thousands of files, so I was wondering if there was a\n> more efficient way than for every commit:\n> \n> 1. Get a list of all paths in the repo from ls-files.\n> 2. Lowercase all paths.\n> 3. Check for repeats.\n\nYou can do:\n\n git ls-files | tr A-Z a-z | sort | uniq -d\n\nbut:\n\n 1. It will print only the lowercased version, not all versions.\n\n 2. It doesn't handle filenames with embedded newlines.\n\nYou could fix both with something like:\n\n git ls-files -z | perl -0ne '\n push @{$h{lc($_)}}, $_;\n END {\n print join(\"\\n\", @{$h{$_}}) . \"\\n\\n\"\n foreach grep { @{$h{$_}} > 1 } keys(%h);\n }\n '\n\n-Peff\n"},{"id":"153000","messageId":"AANLkTik6pSJFUkY9sooSH7iANaKLhxdN+ouKRXJn1B9G@mail.gmail.com","threadId":"25389","inReplyTo":"20101008135034.GC5163@sigill.intra.peff.net","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Dun Peal","fromEmail":"dunpealer@gmail.com","sentAt":"2010-10-08T19:44:05Z","receivedAt":"2010-10-08T19:44:05Z","isPatch":false,"sender":{"key":"dunpealer@gmail.com","avatar":"https://gravatar.com/avatar/42f3e6a1166eb44e33f24c20ccbe809fa8591413f366dfe3755c8a8d4935ace9?d=mp&s=160"},"body":"On Fri, Oct 8, 2010 at 8:50 AM, Jeff King wrote:\n> You can do:\n>\n>  git ls-files | tr A-Z a-z | sort | uniq -d\n\nThanks, but the main issue is that this is a very large repository\nwith tens of thousands of paths (files and directories).\n\ngit ls-files thus takes a long time, almost a second. Since this is a\ncommit-heavy repo, I'd rather avoid that overhead.\n\nIncidentally, there's an SVN hook that does the exact same thing that\nI want to do:\n\nhttp://svn.apache.org/repos/asf/subversion/trunk/contrib/hook-scripts/case-insensitive.py\n\nD\n"},{"id":"153001","messageId":"20101008195120.GA10810@sigill.intra.peff.net","threadId":"25389","inReplyTo":"AANLkTik6pSJFUkY9sooSH7iANaKLhxdN+ouKRXJn1B9G@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-10-08T19:51:20Z","receivedAt":"2010-10-08T19:51:20Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 08, 2010 at 02:44:05PM -0500, Dun Peal wrote:\n\n> On Fri, Oct 8, 2010 at 8:50 AM, Jeff King wrote:\n> > You can do:\n> >\n> >  git ls-files | tr A-Z a-z | sort | uniq -d\n> \n> Thanks, but the main issue is that this is a very large repository\n> with tens of thousands of paths (files and directories).\n> \n> git ls-files thus takes a long time, almost a second. Since this is a\n> commit-heavy repo, I'd rather avoid that overhead.\n\nI don't think you will find a solution that is faster. ls-files is just\nreading the list of files from git's index file. I'm not seeing anything\nnear that long to do an ls-files on my machine:\n\n $ cd linux-2.6\n $ git ls-files | wc -l\n 34296\n $ time git ls-files >/dev/null\n real 0m0.034s\n user 0m0.028s\n sys 0m0.012s\n\nOne thing to consider, though, is if this is a hook running on the\nserver, you probably don't want to look at the index. You probably want\nto look for duplicates in one tree entry (fed to the hook). So you would\nbe using git ls-tree, which probably is a bit slower.\n\n-Peff\n"},{"id":"153004","messageId":"20101008195658.GF14311@burratino","threadId":"25389","inReplyTo":"AANLkTik6pSJFUkY9sooSH7iANaKLhxdN+ouKRXJn1B9G@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-08T19:56:58Z","receivedAt":"2010-10-08T19:56:58Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Dun Peal wrote:\n\n> git ls-files thus takes a long time, almost a second. Since this is a\n> commit-heavy repo, I'd rather avoid that overhead.\n> \n> Incidentally, there's an SVN hook that does the exact same thing that\n> I want to do:\n> \n> http://svn.apache.org/repos/asf/subversion/trunk/contrib/hook-scripts/case-insensitive.py\n\nWell, can't you do the same thing that hook does?\n\n1. Decide on the desired semantics.\n\nShould a broken push of multiple branches be entirely rejected, or\njust the broken branches? The answer determines whether you should\nbe using a pre-receive or an update hook; see githooks(5).\n\n2. Get a list of added files with git-diff-tree(1) --diff-filter.\n3. Break file names into directory + basename.\n4. For each directory with new files or subdirectories:\n - List its children in the new version with git-ls-tree(1)\n - Canonicalize path names\n - Find clashes\n\nIf this should be general-purpose, take care to handle:\n\n - new branches ( = 00000000...)\n - new subdirectory whose name clashes with an existing file\n - filename clash within a new subdirectory\n\nGood luck,\nJonathan\n"},{"id":"153003","messageId":"AANLkTimAhjHm5Z4ekTOBaxwzyw2YD6MrRnB1O8E6nAtw@mail.gmail.com","threadId":"25389","inReplyTo":"20101008195120.GA10810@sigill.intra.peff.net","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Dun Peal","fromEmail":"dunpealer@gmail.com","sentAt":"2010-10-08T19:57:49Z","receivedAt":"2010-10-08T19:57:49Z","isPatch":false,"sender":{"key":"dunpealer@gmail.com","avatar":"https://gravatar.com/avatar/42f3e6a1166eb44e33f24c20ccbe809fa8591413f366dfe3755c8a8d4935ace9?d=mp&s=160"},"body":"On Fri, Oct 8, 2010 at 2:51 PM, Jeff King wrote:\n> One thing to consider, though, is if this is a hook running on the\n> server, you probably don't want to look at the index. You probably want\n> to look for duplicates in one tree entry (fed to the hook). So you would\n> be using git ls-tree, which probably is a bit slower.\n\nThanks, but why is that? Why can't I use ls-files, and must use use\nls-tree, which you say would be slower?\n\nFor extra details: is the central Git repository, running under\nGitorious, on a fairly powerful server. It's a bare repo, naturally.\n\nD\n"},{"id":"153005","messageId":"20101008200657.GA10954@sigill.intra.peff.net","threadId":"25389","inReplyTo":"AANLkTimAhjHm5Z4ekTOBaxwzyw2YD6MrRnB1O8E6nAtw@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-10-08T20:06:57Z","receivedAt":"2010-10-08T20:06:57Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 08, 2010 at 02:57:49PM -0500, Dun Peal wrote:\n\n> On Fri, Oct 8, 2010 at 2:51 PM, Jeff King wrote:\n> > One thing to consider, though, is if this is a hook running on the\n> > server, you probably don't want to look at the index. You probably want\n> > to look for duplicates in one tree entry (fed to the hook). So you would\n> > be using git ls-tree, which probably is a bit slower.\n> \n> Thanks, but why is that? Why can't I use ls-files, and must use use\n> ls-tree, which you say would be slower?\n\nFor two reasons:\n\n 1. Bare repos generally don't _have_ an index, as it is about\n maintaining the state of the working tree.\n\n 2. Even if you did have an index, it would presumably represent the\n contents of HEAD. But if you are feeding a commit to a hook, then\n that hook will get some sha1 of the to-be-pushed commit. So you\n need to look at the paths that are in that hook.\n\nRe-reading your original message, I have a few more thoughts.\n\nOne is that you don't need to do this per-commit. You probably want to\ndo it per-updated-ref, each of which may be pushing many commits. And\nthen you either reject the new ref value or not.\n\nAlso, you could try not looking at the whole tree by doing something\nlike:\n\n git diff-tree --diff-filter=A --name-only $old $new\n\nand then only considering duplicates for newly introduced files. But\nthat means for each introduced file, you need to enumerate the tree to\nfind case-sensitive matches. You can avoid looking at the whole tree\nonly be manually expanding each level (e.g., you see that foo/bar is\nnew. So you look at the root tree, looking for \"foo\" or case-insensitive\nequivalents. For each one you find, you look further down for \"bar\" or a\ncase-insensitive equivalent). But that means many git ls-tree calls. So\nI don't think it buys you anything in practice.\n\n-Peff\n"},{"id":"153019","messageId":"AANLkTi=YQOVYsK6Brq5pMiAdrH3Un7RgrWvYf_pymT=d@mail.gmail.com","threadId":"25389","inReplyTo":"20101008200657.GA10954@sigill.intra.peff.net","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Dun Peal","fromEmail":"dunpealer@gmail.com","sentAt":"2010-10-08T22:57:16Z","receivedAt":"2010-10-08T22:57:16Z","isPatch":false,"sender":{"key":"dunpealer@gmail.com","avatar":"https://gravatar.com/avatar/42f3e6a1166eb44e33f24c20ccbe809fa8591413f366dfe3755c8a8d4935ace9?d=mp&s=160"},"body":"On Fri, Oct 8, 2010 at 3:06 PM, Jeff King wrote:\n> Re-reading your original message, I have a few more thoughts.\n>\n> One is that you don't need to do this per-commit. You probably want to\n> do it per-updated-ref, each of which may be pushing many commits. And\n> then you either reject the new ref value or not.\n\nI think I do, actually, because let's say the developer pushes two\ncommits, 1<-2. Suppose commit 1 violates the rule, but commit 2\nreverts the violation. One might think that we don't care, since the\nhead will now be on 2, which is a correct state. But in fact we do,\nbecause this is Git, and anyone may branch of from 1 in the future,\nand voila we have a head in an incorrect state.\n\n> Also, you could try not looking at the whole tree by [...]\n> only be manually expanding each level [...]\n> But that means many git ls-tree calls.\n\nYeah, that's a pretty good idea, if not for the many ls-tree calls.\nWith their overhead, I strongly suspect it may be slower than the\nsolution you seem to propose, which is:\n\ngit ls-tree -r \n\nwhich should give the full list of all paths in a commit, upon which I\ncan decide to accept or reject.\n\nThanks, D\n"},{"id":"153047","messageId":"m3aamng3dt.fsf@localhost.localdomain","threadId":"25389","inReplyTo":"AANLkTi=YQOVYsK6Brq5pMiAdrH3Un7RgrWvYf_pymT=d@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-10-09T08:47:12Z","receivedAt":"2010-10-09T08:47:12Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Dun Peal writes:\n> On Fri, Oct 8, 2010 at 3:06 PM, Jeff King wrote:\n\n> > Re-reading your original message, I have a few more thoughts.\n> >\n> > One is that you don't need to do this per-commit. You probably want to\n> > do it per-updated-ref, each of which may be pushing many commits. And\n> > then you either reject the new ref value or not.\n> \n> I think I do, actually, because let's say the developer pushes two\n> commits, 1<-2. Suppose commit 1 violates the rule, but commit 2\n> reverts the violation. One might think that we don't care, since the\n> head will now be on 2, which is a correct state. But in fact we do,\n> because this is Git, and anyone may branch of from 1 in the future,\n> and voila we have a head in an incorrect state.\n\nSidenote: why not detect violation earlier, by having pre-commit hook\nin each developer repository check for such violation? It is not as\ntime sensitive on the local side (when creating a commit, you have to\ntake some time to write commit message anyway).\n\nSee how example pre-commit hook check for \"non-ascii\" file names.\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"153102","messageId":"AANLkTinzH3EWy=E2H9hQJzCdPB3Epu5WQkmuv2CWKFtc@mail.gmail.com","threadId":"25389","inReplyTo":"m3aamng3dt.fsf@localhost.localdomain","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Dun Peal","fromEmail":"dunpealer@gmail.com","sentAt":"2010-10-09T22:00:10Z","receivedAt":"2010-10-09T22:00:10Z","isPatch":false,"sender":{"key":"dunpealer@gmail.com","avatar":"https://gravatar.com/avatar/42f3e6a1166eb44e33f24c20ccbe809fa8591413f366dfe3755c8a8d4935ace9?d=mp&s=160"},"body":"On Sat, Oct 9, 2010 at 3:47 AM, Jakub Narebski wrote:\n> Sidenote: why not detect violation earlier, by having pre-commit hook\n> in each developer repository check for such violation?  It is not as\n> time sensitive on the local side (when creating a commit, you have to\n> take some time to write commit message anyway).\n\nThat's a solution, but as you surely know hooks are not automatically\ncloned with the repository. There's no way to ensure that all of our\nmany users install that hook, and we can't allow an incorrect state on\nthe central node.\n\nA pre-receive hook on that node seems like the only way to really ensure that.\n\nD\n"},{"id":"153106","messageId":"201010100031.11791.jnareb@gmail.com","threadId":"25389","inReplyTo":"AANLkTinzH3EWy=E2H9hQJzCdPB3Epu5WQkmuv2CWKFtc@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-10-09T22:31:10Z","receivedAt":"2010-10-09T22:31:10Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Sun, Oct 10, 2010, Dun Peal wrote:\n> On Sat, Oct 9, 2010 at 3:47 AM, Jakub Narebski wrote:\n\n> > Sidenote: why not detect violation earlier, by having pre-commit hook\n> > in each developer repository check for such violation?  It is not as\n> > time sensitive on the local side (when creating a commit, you have to\n> > take some time to write commit message anyway).\n> \n> That's a solution, but as you surely know hooks are not automatically\n> cloned with the repository. There's no way to ensure that all of our\n> many users install that hook, and we can't allow an incorrect state on\n> the central node.\n> \n> A pre-receive hook on that node seems like the only way to really ensure that.\n\nWell, if you can control git installation on client side, you can\nmodify git templates (usually in /usr/share/git-core/templates) to\nhave appropriate pre-commit hok enabled in all repositories created\nthere... but I agree that it is not an universal solution.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"153217","messageId":"20101011030755.GB6523@sigill.intra.peff.net","threadId":"25389","inReplyTo":"AANLkTi=YQOVYsK6Brq5pMiAdrH3Un7RgrWvYf_pymT=d@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-10-11T03:07:55Z","receivedAt":"2010-10-11T03:07:55Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 08, 2010 at 05:57:16PM -0500, Dun Peal wrote:\n\n> On Fri, Oct 8, 2010 at 3:06 PM, Jeff King wrote:\n> > Re-reading your original message, I have a few more thoughts.\n> >\n> > One is that you don't need to do this per-commit. You probably want to\n> > do it per-updated-ref, each of which may be pushing many commits. And\n> > then you either reject the new ref value or not.\n> \n> I think I do, actually, because let's say the developer pushes two\n> commits, 1<-2. Suppose commit 1 violates the rule, but commit 2\n> reverts the violation. One might think that we don't care, since the\n> head will now be on 2, which is a correct state. But in fact we do,\n> because this is Git, and anyone may branch of from 1 in the future,\n> and voila we have a head in an incorrect state.\n\nYeah, though it is not an especially likely state to branch from, since\nyou have to specify it manually. However, a much more likely scenario is\ncheckout out a past commit for testing, especially in bisection. So yes,\nif you want to be thorough, you need to check every commit.\n\n> Yeah, that's a pretty good idea, if not for the many ls-tree calls.\n> With their overhead, I strongly suspect it may be slower than the\n> solution you seem to propose, which is:\n> \n> git ls-tree -r \n> \n> which should give the full list of all paths in a commit, upon which I\n> can decide to accept or reject.\n\nYeah, that is what I am proposing.\n\nOne other thing you could try is to \"ls-tree -r\" the known-good state of\nthe current HEAD at the beginning of the push, and then run \"git log\n-diff-filter=AD --name-status $old..$new\". For each commit in the log\noutput, look for new entries that are in case-insensitive conflict with\nthe existing tree, and then update your tree state appropriately with\nadded and removed files. You only invoke two git commands, which saves\non invocation overhead, and you only ls-tree once per push, not per\ncommit. Git's internal diff shouldn't look at parts of the tree that\naren't relevant.\n\nThe downside is that the tree state you are keeping internally is not\nentirely accurate. For example, when receiving a merge between two\nparallel lines of development, you would process them linearly, when in\nfact there are two simultaneous different states. So there is a case\nwhere branch X removes \"foo.txt\" and branch Y adds \"FOO.TXT\", and then\nthey merge. It looks OK because linearly, they did not both exist at the\nsame time. But pre-merge, the commit in branch Y is broken.\n\nSo really the straightforward approach of checking the tree state for\neach commit is probably simplest. If it's really too slow, you could try\njgit or linking against git itself, which would eliminate the external\nprocess overhead.\n\n-Peff\n"},{"id":"153642","messageId":"AANLkTimSNTKFYnYgpha4MpyiC5CdZU5ay1B-848JQrzJ@mail.gmail.com","threadId":"25389","inReplyTo":"20101011030755.GB6523@sigill.intra.peff.net","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Dun Peal","fromEmail":"dunpealer@gmail.com","sentAt":"2010-10-16T22:37:53Z","receivedAt":"2010-10-16T22:37:53Z","isPatch":false,"sender":{"key":"dunpealer@gmail.com","avatar":"https://gravatar.com/avatar/42f3e6a1166eb44e33f24c20ccbe809fa8591413f366dfe3755c8a8d4935ace9?d=mp&s=160"},"body":"Thanks a lot everyone, and especially Jeff.\n\nRunning:\n\n git ls-tree -r HEAD\n\nproduces almost 100k lines of output, representing 100k total file +\ndirectory count, which is a pretty big tree. I hope and expect to be\nable to split out some branches in the future, but even with\neverything included, the operation still only takes ~0.5s real (user +\nsys).\n\nSo I think even with our relatively high user count and repository\ntraffic, that cost per commit should not completely break our\nworkflow.\n\nThus, I'm going to implement the hook to run the above command and\nanalyze the output per commit. Assumption is that with the script\noverhead, we should be able to finish in less than a second, which is\nreasonable latency.\n\nI'll report back if there are any unexpected issues, or this doesn't\nwork as well as currently expected.\n\nThanks, D\n\nOn Sun, Oct 10, 2010 at 10:07 PM, Jeff King wrote:\n> On Fri, Oct 08, 2010 at 05:57:16PM -0500, Dun Peal wrote:\n>\n>> On Fri, Oct 8, 2010 at 3:06 PM, Jeff King wrote:\n>> > Re-reading your original message, I have a few more thoughts.\n>> >\n>> > One is that you don't need to do this per-commit. You probably want to\n>> > do it per-updated-ref, each of which may be pushing many commits. And\n>> > then you either reject the new ref value or not.\n>>\n>> I think I do, actually, because let's say the developer pushes two\n>> commits, 1<-2. Suppose commit 1 violates the rule, but commit 2\n>> reverts the violation. One might think that we don't care, since the\n>> head will now be on 2, which is a correct state. But in fact we do,\n>> because this is Git, and anyone may branch of from 1 in the future,\n>> and voila we have a head in an incorrect state.\n>\n> Yeah, though it is not an especially likely state to branch from, since\n> you have to specify it manually. However, a much more likely scenario is\n> checkout out a past commit for testing, especially in bisection. So yes,\n> if you want to be thorough, you need to check every commit.\n>\n>> Yeah, that's a pretty good idea, if not for the many ls-tree calls.\n>> With their overhead, I strongly suspect it may be slower than the\n>> solution you seem to propose, which is:\n>>\n>> git ls-tree -r \n>>\n>> which should give the full list of all paths in a commit, upon which I\n>> can decide to accept or reject.\n>\n> Yeah, that is what I am proposing.\n>\n> One other thing you could try is to \"ls-tree -r\" the known-good state of\n> the current HEAD at the beginning of the push, and then run \"git log\n> -diff-filter=AD --name-status $old..$new\". For each commit in the log\n> output, look for new entries that are in case-insensitive conflict with\n> the existing tree, and then update your tree state appropriately with\n> added and removed files. You only invoke two git commands, which saves\n> on invocation overhead, and you only ls-tree once per push, not per\n> commit. Git's internal diff shouldn't look at parts of the tree that\n> aren't relevant.\n>\n> The downside is that the tree state you are keeping internally is not\n> entirely accurate. For example, when receiving a merge between two\n> parallel lines of development, you would process them linearly, when in\n> fact there are two simultaneous different states. So there is a case\n> where branch X removes \"foo.txt\" and branch Y adds \"FOO.TXT\", and then\n> they merge. It looks OK because linearly, they did not both exist at the\n> same time. But pre-merge, the commit in branch Y is broken.\n>\n> So really the straightforward approach of checking the tree state for\n> each commit is probably simplest. If it's really too slow, you could try\n> jgit or linking against git itself, which would eliminate the external\n> process overhead.\n>\n> -Peff\n>\n"},{"id":"153654","messageId":"20101017042525.GA15595@sigill.intra.peff.net","threadId":"25389","inReplyTo":"AANLkTimSNTKFYnYgpha4MpyiC5CdZU5ay1B-848JQrzJ@mail.gmail.com","subject":"Re: Efficiently detecting paths that differ from each other only in case","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-10-17T04:25:25Z","receivedAt":"2010-10-17T04:25:25Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 16, 2010 at 05:37:53PM -0500, Dun Peal wrote:\n\n> Running:\n> \n> git ls-tree -r HEAD\n> \n> produces almost 100k lines of output, representing 100k total file +\n> directory count, which is a pretty big tree. I hope and expect to be\n> able to split out some branches in the future, but even with\n> everything included, the operation still only takes ~0.5s real (user +\n> sys).\n\nOut of curiosity, is your bare repo fully packed? My linux-2.6 repo is\nonly ~35000 entries, but it can ls-tree -r with a warm cache in about\n.09s. If it scaled linearly with the number of files, that would be\nalmost twice as fast as yours.\n\nThe distribution of files within your directories can impact exactly how\nmany trees you have, and thus the lookup performance. Or maybe your\nmachine is simply a little bit slower. But since you seem\nperformance-conscious, it might be worth double-checking.\n\n-Peff\n"}]}