{"thread":{"id":"58535","subject":"icase pathspec magic support in ls-tree","startedAt":"2022-09-30T12:05:13Z","lastAt":"2022-10-17T15:47:13Z","messageCount":16,"participants":["Tao Klerks","Ævar Arnfjörð Bjarmason","brian m. carlson","Torsten Bögershausen","Elijah Newren","Erik Cervin Edin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"463948","messageId":"CAPMMpogcnwJDUazw82OB0DvdgvNS6hpUN9Qs69ppTFb1QFbLSg@mail.gmail.com","threadId":"58535","inReplyTo":null,"subject":"icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-09-30T12:04:50Z","receivedAt":"2022-09-30T12:05:13Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"Hi folks,\n\nI just found out today both that icase magic exists (awesome!), and\nthat it isn't supported in ls-tree (boo).\n\nAs far as I can tell, getting it supported would be the only way to\n*efficiently* prevent caseless-duplicate files from being created in a\nrepo, in an \"update\" hook: I'd want to call ls-tree on the new head\ncommit for the branch, passing in an icase pathspec for all the files\nbeing added since the previous state - and then sort and uniq.\n\nOf course, for entirely new branches I'd have to do a full check of\nthe tree, and for very large changes that might be the fastest/best\nthing to do anyway, rather than creating a silly-sized pathspec - but\nchecking the full tree costs me about 1 second, a price that I'm loath\nto pay for everyday commit verifications of a handful of files, vs a\n200,000-file full tree.\n\nI tried changing ls-tree \"naively\" to just permit the icase magic,\nwithout any logic changes, and found at least one case where it\ndoesn't work: when combining wildcards with case-insensitivity, like\nan icased \"T/*\" patchspec in the git repo; ls-files finds all the\ntests, and a naively updated ls-tree does not.\n\nI think I see the last person to update this was Nguyễn Thái Ngọc Duy\nin 2013, giving a hint as to what would need to be done to make this\nbe supported; is this an area anyone else might be looking at at the\nmoment?\n\nThanks,\nTao\n"},{"id":"463952","messageId":"220930.86r0ztufwd.gmgdl@evledraar.gmail.com","threadId":"58535","inReplyTo":"CAPMMpogcnwJDUazw82OB0DvdgvNS6hpUN9Qs69ppTFb1QFbLSg@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-09-30T13:53:16Z","receivedAt":"2022-09-30T13:54:18Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Sep 30 2022, Tao Klerks wrote:\n\n> Hi folks,\n>\n> I just found out today both that icase magic exists (awesome!), and\n> that it isn't supported in ls-tree (boo).\n>\n> As far as I can tell, getting it supported would be the only way to\n> *efficiently* prevent caseless-duplicate files from being created in a\n> repo, in an \"update\" hook: I'd want to call ls-tree on the new head\n> commit for the branch, passing in an icase pathspec for all the files\n> being added since the previous state - and then sort and uniq.\n>\n> Of course, for entirely new branches I'd have to do a full check of\n> the tree, and for very large changes that might be the fastest/best\n> thing to do anyway, rather than creating a silly-sized pathspec - but\n> checking the full tree costs me about 1 second, a price that I'm loath\n> to pay for everyday commit verifications of a handful of files, vs a\n> 200,000-file full tree.\n>\n> I tried changing ls-tree \"naively\" to just permit the icase magic,\n> without any logic changes, and found at least one case where it\n> doesn't work: when combining wildcards with case-insensitivity, like\n> an icased \"T/*\" patchspec in the git repo; ls-files finds all the\n> tests, and a naively updated ls-tree does not.\n>\n> I think I see the last person to update this was Nguyễn Thái Ngọc Duy\n> in 2013, giving a hint as to what would need to be done to make this\n> be supported; is this an area anyone else might be looking at at the\n> moment?\n\nYou might find ASCII-only sufficient, but note that even if you get this\nworking you won't catch the more complex Unicode normalization rules\nvarious filesystems perform, see the fsck code we carefully crafted to\nmake sure we don't get something those FS's will mistake for a \".git\"\ndirectory in-tree.\n"},{"id":"464056","messageId":"YznhYzWztkPc9pJk@tapette.crustytoothpaste.net","threadId":"58535","inReplyTo":"220930.86r0ztufwd.gmgdl@evledraar.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2022-10-02T19:07:15Z","receivedAt":"2022-10-02T19:07:23Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2022-09-30 at 13:53:16, Ævar Arnfjörð Bjarmason wrote:\n> You might find ASCII-only sufficient, but note that even if you get this\n> working you won't catch the more complex Unicode normalization rules\n> various filesystems perform, see the fsck code we carefully crafted to\n> make sure we don't get something those FS's will mistake for a \".git\"\n> directory in-tree.\n\nWhat's even worse is that different OSes case-fold differently and the\nbehaviour differs based on the version of the OS that formatted the file\nsystem (which is of course not exposed to userspace), so in general it's\nimpossible to know exactly how case folding works on a particular\nsystem.\n\nIt might be possible to implement some general rules that are\noverzealous (in that they will catch patterns that will case-fold on\n_some_ system), but in general this is very difficult.  The rules will\nalso almost certainly change with newer versions of Unicode.\n\nI'll also point out that there is no locale-independent way to correctly\ncase-fold Unicode text.  Correct case-folding is sensitive to the\nlanguage, script, and region.\n-- \nbrian m. carlson (he/him or they/them)\nToronto, Ontario, CA\n"},{"id":"464798","messageId":"CAPMMpojy8OMxYT0WuZCOZjwvufmVucvoHPtvLHatopXvuk9K5Q@mail.gmail.com","threadId":"58535","inReplyTo":"YznhYzWztkPc9pJk@tapette.crustytoothpaste.net","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-13T06:35:11Z","receivedAt":"2022-10-13T06:35:34Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"On Sun, Oct 2, 2022 at 9:07 PM brian m. carlson\n<sandals@crustytoothpaste.net> wrote:\n>\n> On 2022-09-30 at 13:53:16, Ævar Arnfjörð Bjarmason wrote:\n> > You might find ASCII-only sufficient, but note that even if you get this\n> > working you won't catch the more complex Unicode normalization rules\n> > various filesystems perform, see the fsck code we carefully crafted to\n> > make sure we don't get something those FS's will mistake for a \".git\"\n> > directory in-tree.\n>\n> What's even worse is that different OSes case-fold differently and the\n> behaviour differs based on the version of the OS that formatted the file\n> system (which is of course not exposed to userspace), so in general it's\n> impossible to know exactly how case folding works on a particular\n> system.\n>\n> It might be possible to implement some general rules that are\n> overzealous (in that they will catch patterns that will case-fold on\n> _some_ system), but in general this is very difficult.  The rules will\n> also almost certainly change with newer versions of Unicode.\n>\n> I'll also point out that there is no locale-independent way to correctly\n> case-fold Unicode text.  Correct case-folding is sensitive to the\n> language, script, and region.\n\nThanks for the feedback!\n\nIf I'm understanding correctly, both of these responses were targeted\nspecifically at my motivation/usecase (preventing the submission of\ncase-insensitively duplicate files into a repository) rather than the\nquestion of whether anyone has worked or is working on anything\nrelevant to adding icase pathspec magic support to ls-tree.\n\nI understand that case-folding is a complex topic, and doing it\ncorrectly in some universal sense is undoubtedly beyond me - but \"my\"\ncontext certainly does not require a high standard of correctness:\nThere's a repo shared by some 1000 engineers, 200k files, lots of\nactivity, three different OSes of which two default to\ncase-insensitive filesystems, and every once in a while a user on\nlinux creates a case-insensitive-duplicate file with differing\ncontent, which causes git on case-insensitive filesystems to lose the\nplot (you end up with one file's content looking like changes to the\nother file's content - \"ghost changes\" that appear as soon as you\ncheck out, that prevent you from doing a simple \"pull\", and that you\njust can't reset).\n\nI don't imagine I can make a perfectly correct and universal fix to\nthis, but with case-insensitive matching on ls-tree in an update hook\nI believe I could reduce the frequency of this already-infrequent\nissue by at least 1000X, which would suit my purposes just fine. In my\ncase filenames are mostly ansi-based, and I don't expect we've ever\nhad Turkish filenames (turkish \"i\" being the most famous case-folding\ngotcha I think?).\n\nComing at this from another angle, I guess we could teach git on\ncase-insensitive filesystems to detect this situation (where two files\nin the index, with different contents, are pointing to the exact same\nfilesystem file) and more explicitly warn the user of what's wrong,\ngiving them clear help on how to fix it? And temporarily exclude those\ntwo files from its change reconciliation processes altogether to avoid\nghost changes interfering with recovery actions like \"pull\"? Certainly\nthat would be better than the current \"ghost changes\" behavior... but\nit would still be far less convenient than preventing (the vast\nmajority of) these issues altogether, be that with a custom hook or a\ncore option prohibiting clearly case-insensitive-duplicate files from\nbeing pushed.\n\nBy the time a case-insensitive-FS-user encounters this issue in their\nrepo as they checkout or clone, it's likely that the problem is in\nmaster/main and others are already affected, and both the cycle time\nto fixing the issue, and the communication impact in the current state\n(\"please wait, the issue is being addressed, once the remote branch is\nfixed here's what you'll do to 'pull' successfully in spite of the\nlocal repo thinking there are filesystem changes that really don't\nexist and can't be reset\") are... suboptimal.\n\nIt feels like adding case-insensitivity pathspec magic support to\nls-tree (however reliable or universal the subsequent\nduplicate-detection is or isn't) *should* be much simpler than what it\nwould have taken to support it in ls-files in the first place - but at\na glance, I see the official pathspec-supporting function\n\"match_pathspec()\" is deep in index-land, with an \"index_state\"\nstructure being passed around all over the place. If it really was\neasy, someone would already have done it I guess? :)\n\nI don't see this being something I can take on in my spare time, so\nfor now I suspect I'll have to do a full-tree duplicate-file-search on\nevery ref update, and simply accept the 1-second update hook\nprocessing time/delay per pushed ref :(\n\nI'm assuming the \"ghost changes\" behavior I allude to here (where two\ndifferent files in the index, with different contents, point to the\nsame single file in the case-insensitive filesystem, and one or the\nother index file appears modified / the working tree looks \"dirty\") is\na known issue, but if there's any value in my opening a thread more\nclearly/explicitly about this behavior, please let me know.\n\nThanks,\nTao\n"},{"id":"464906","messageId":"20221014045140.7ibix3632w4uset5@tb-raspi4","threadId":"58535","inReplyTo":"CAPMMpojy8OMxYT0WuZCOZjwvufmVucvoHPtvLHatopXvuk9K5Q@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Torsten Bögershausen","fromEmail":"tboegi@web.de","sentAt":"2022-10-14T04:51:40Z","receivedAt":"2022-10-14T04:51:58Z","isPatch":false,"sender":{"key":"tboegi@web.de","avatar":"https://avatars.githubusercontent.com/u/7138363?v=4"},"body":"On Thu, Oct 13, 2022 at 08:35:11AM +0200, Tao Klerks wrote:\n> On Sun, Oct 2, 2022 at 9:07 PM brian m. carlson\n> <sandals@crustytoothpaste.net> wrote:\n> >\n> > On 2022-09-30 at 13:53:16, Ævar Arnfjörð Bjarmason wrote:\n> > > You might find ASCII-only sufficient, but note that even if you get this\n> > > working you won't catch the more complex Unicode normalization rules\n> > > various filesystems perform, see the fsck code we carefully crafted to\n> > > make sure we don't get something those FS's will mistake for a \".git\"\n> > > directory in-tree.\n> >\n> > What's even worse is that different OSes case-fold differently and the\n> > behaviour differs based on the version of the OS that formatted the file\n> > system (which is of course not exposed to userspace), so in general it's\n> > impossible to know exactly how case folding works on a particular\n> > system.\n> >\n> > It might be possible to implement some general rules that are\n> > overzealous (in that they will catch patterns that will case-fold on\n> > _some_ system), but in general this is very difficult.  The rules will\n> > also almost certainly change with newer versions of Unicode.\n> >\n> > I'll also point out that there is no locale-independent way to correctly\n> > case-fold Unicode text.  Correct case-folding is sensitive to the\n> > language, script, and region.\n>\n> Thanks for the feedback!\n>\n> If I'm understanding correctly, both of these responses were targeted\n> specifically at my motivation/usecase (preventing the submission of\n> case-insensitively duplicate files into a repository) rather than the\n> question of whether anyone has worked or is working on anything\n> relevant to adding icase pathspec magic support to ls-tree.\n>\n> I understand that case-folding is a complex topic, and doing it\n> correctly in some universal sense is undoubtedly beyond me - but \"my\"\n> context certainly does not require a high standard of correctness:\n> There's a repo shared by some 1000 engineers, 200k files, lots of\n> activity, three different OSes of which two default to\n> case-insensitive filesystems, and every once in a while a user on\n> linux creates a case-insensitive-duplicate file with differing\n> content, which causes git on case-insensitive filesystems to lose the\n> plot (you end up with one file's content looking like changes to the\n> other file's content - \"ghost changes\" that appear as soon as you\n> check out, that prevent you from doing a simple \"pull\", and that you\n> just can't reset).\n>\n> I don't imagine I can make a perfectly correct and universal fix to\n> this, but with case-insensitive matching on ls-tree in an update hook\n> I believe I could reduce the frequency of this already-infrequent\n> issue by at least 1000X, which would suit my purposes just fine. In my\n> case filenames are mostly ansi-based, and I don't expect we've ever\n> had Turkish filenames (turkish \"i\" being the most famous case-folding\n> gotcha I think?).\n>\n> Coming at this from another angle, I guess we could teach git on\n> case-insensitive filesystems to detect this situation (where two files\n> in the index, with different contents, are pointing to the exact same\n> filesystem file) and more explicitly warn the user of what's wrong,\n> giving them clear help on how to fix it? And temporarily exclude those\n> two files from its change reconciliation processes altogether to avoid\n> ghost changes interfering with recovery actions like \"pull\"? Certainly\n> that would be better than the current \"ghost changes\" behavior... but\n> it would still be far less convenient than preventing (the vast\n> majority of) these issues altogether, be that with a custom hook or a\n> core option prohibiting clearly case-insensitive-duplicate files from\n> being pushed.\n>\n> By the time a case-insensitive-FS-user encounters this issue in their\n> repo as they checkout or clone, it's likely that the problem is in\n> master/main and others are already affected, and both the cycle time\n> to fixing the issue, and the communication impact in the current state\n> (\"please wait, the issue is being addressed, once the remote branch is\n> fixed here's what you'll do to 'pull' successfully in spite of the\n> local repo thinking there are filesystem changes that really don't\n> exist and can't be reset\") are... suboptimal.\n>\n> It feels like adding case-insensitivity pathspec magic support to\n> ls-tree (however reliable or universal the subsequent\n> duplicate-detection is or isn't) *should* be much simpler than what it\n> would have taken to support it in ls-files in the first place - but at\n> a glance, I see the official pathspec-supporting function\n> \"match_pathspec()\" is deep in index-land, with an \"index_state\"\n> structure being passed around all over the place. If it really was\n> easy, someone would already have done it I guess? :)\n>\n> I don't see this being something I can take on in my spare time, so\n> for now I suspect I'll have to do a full-tree duplicate-file-search on\n> every ref update, and simply accept the 1-second update hook\n> processing time/delay per pushed ref :(\n>\n> I'm assuming the \"ghost changes\" behavior I allude to here (where two\n> different files in the index, with different contents, point to the\n> same single file in the case-insensitive filesystem, and one or the\n> other index file appears modified / the working tree looks \"dirty\") is\n> a known issue, but if there's any value in my opening a thread more\n> clearly/explicitly about this behavior, please let me know.\n>\n> Thanks,\n> Tao\n\n\nThanks for sharing your experience in detail.\n\nDid you ever consider to write a shell script,\nthat can detect icase-collisions ?\n\nFor example, we can use Linux:\n git ls-files | tr 'A-Z' 'a-z' | sort | uniq -d ; echo $?\n include/uapi/linux/netfilter_ipv4/ipt_ecn.h\n include/uapi/linux/netfilter_ipv4/ipt_ttl.h\n [snip the other files]\n\nThe GNU versions of uniq allow an even shorter command,\n(But the POSIX versions don't)\n\ngit ls-files  | sort | uniq -i -d\n\nI think that a script like this could do the trick:\n\n#!/bin/sh\nret=1\n>/tmp/$$-exp\ngit ls-files  | sort | uniq -i -d >/tmp/$$-act &&\n  cmp /tmp/$$-exp /tmp/$$-act &&\n    ret=0\n    rm -f /tmp/$$-exp /tmp/$$-act\n    exit $ret\n\n\n####################\nThe usage of files in /tmp is probably debatable,\nI want just illustrate how a combination of shell\nscripts in combination with existing commands can be used.\n\nThe biggest step may be to introduce a server-side hook\nthat does a check.\nBut once that is done and working, you probably do\nnot want to miss it.\n"},{"id":"464909","messageId":"CABPp-BHaMCcLjdx2m4CALZQiTRQy_LovWfbdrga6XWhQJhoxWQ@mail.gmail.com","threadId":"58535","inReplyTo":"CAPMMpojy8OMxYT0WuZCOZjwvufmVucvoHPtvLHatopXvuk9K5Q@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-10-14T07:41:11Z","receivedAt":"2022-10-14T07:41:46Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Oct 12, 2022 at 11:49 PM Tao Klerks <tao@klerks.biz> wrote:\n>\n[...]\n> I understand that case-folding is a complex topic, and doing it\n> correctly in some universal sense is undoubtedly beyond me - but \"my\"\n> context certainly does not require a high standard of correctness:\n> There's a repo shared by some 1000 engineers, 200k files, lots of\n> activity, three different OSes of which two default to\n> case-insensitive filesystems, and every once in a while a user on\n> linux creates a case-insensitive-duplicate file with differing\n> content, which causes git on case-insensitive filesystems to lose the\n> plot (you end up with one file's content looking like changes to the\n> other file's content - \"ghost changes\" that appear as soon as you\n> check out, that prevent you from doing a simple \"pull\", and that you\n> just can't reset).\n\nI've felt that same pain.\n\n> I don't imagine I can make a perfectly correct and universal fix to\n> this, but with case-insensitive matching on ls-tree in an update hook\n> I believe I could reduce the frequency of this already-infrequent\n> issue by at least 1000X, which would suit my purposes just fine. In my\n> case filenames are mostly ansi-based, and I don't expect we've ever\n> had Turkish filenames (turkish \"i\" being the most famous case-folding\n> gotcha I think?).\n\nHow exactly would case-insensitive matching in ls-tree help you here?\nCan't you write a hook without such capability that rejects such\ncollisions?\n\n> I don't see this being something I can take on in my spare time, so\n> for now I suspect I'll have to do a full-tree duplicate-file-search on\n> every ref update, and simply accept the 1-second update hook\n> processing time/delay per pushed ref :(\n\nI don't see why you need to do full-tree with existing options, nor\nwhy the ls-tree option you want would somehow make it easier to avoid.\nI think you can avoid the full-tree search with something like:\n\ngit diff --diff-filter=A --no-renames --name-only $OLDHASH $NEWHASH |\nsed -e s%/[^/]*$%/% | uniq | xargs git ls-tree --name-only $NEWHASH |\n\\\n   sort | uniq -i -d\n\nThe final \"sort | uniq -i -d\" is taken from Torsten's suggestion.\n\nThe git diff ... xargs git ls-tree section on the first line will\nprovide a list of all files (& subdirs) in the same directory as any\nadded file.  (Although, it has a blind spot for paths in the toplevel\ndirectory.)\n"},{"id":"464913","messageId":"CA+JQ7M8s1W68+mzfe__+T5bJ821wYJqfgLBqA1=dSVH9Tx9fHA@mail.gmail.com","threadId":"58535","inReplyTo":"CABPp-BHaMCcLjdx2m4CALZQiTRQy_LovWfbdrga6XWhQJhoxWQ@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Erik Cervin Edin","fromEmail":"erik@cervined.in","sentAt":"2022-10-14T08:03:56Z","receivedAt":"2022-10-14T08:04:37Z","isPatch":false,"sender":{"key":"erik@cervined.in","avatar":null},"body":"> I don't imagine I can make a perfectly correct and universal fix to\n> this, but with case-insensitive matching on ls-tree in an update hook\n> I believe I could reduce the frequency of this already-infrequent\n> issue by at least 1000X, which would suit my purposes just fine. In my\n> case filenames are mostly ansi-based, and I don't expect we've ever\n> had Turkish filenames (turkish \"i\" being the most famous case-folding\n> gotcha I think?).\n\nHow about doing it in something that's not ls-tree? Sounds like you\nalready have a script, it just takes a bit too long?\n\nSomething similar to\n\nOn Fri, Oct 14, 2022 at 6:59 AM Torsten Bögershausen <tboegi@web.de> wrote:\n>\n> For example, we can use Linux:\n>  git ls-files | tr 'A-Z' 'a-z' | sort | uniq -d ; echo $?\n\nIn a repo with many files, maybe use git diff --name-only and just run\nit periodically as a part of a check-in hook or something?\n\n  git diff --name-only HEAD~100..HEAD | tr 'A-Z' 'a-z' | sort | uniq -d\n\n\nOn Fri, Oct 14, 2022 at 9:59 AM Elijah Newren <newren@gmail.com> wrote:\n>\n> git diff --diff-filter=A --no-renames --name-only $OLDHASH $NEWHASH |\n> sed -e s%/[^/]*$%/% | uniq | xargs git ls-tree --name-only $NEWHASH |\n> \\\n>    sort | uniq -i -d\n\nOr what Elijah just wrote\n\n> Coming at this from another angle, I guess we could teach git on\n> case-insensitive filesystems to detect this situation (where two files\n> in the index, with different contents, are pointing to the exact same\n> filesystem file) and more explicitly warn the user of what's wrong,\n> giving them clear help on how to fix it? And temporarily exclude those\n> two files from its change reconciliation processes altogether to avoid\n> ghost changes interfering with recovery actions like \"pull\"? Certainly\n> that would be better than the current \"ghost changes\" behavior... but\n> it would still be far less convenient than preventing (the vast\n> majority of) these issues altogether, be that with a custom hook or a\n> core option prohibiting clearly case-insensitive-duplicate files from\n> being pushed.\n\nThat's not to say this isn't a good idea but for now I'd advice an\nautomated scripted route.\n"},{"id":"464915","messageId":"CAPMMpogoX+R7eHkTZQKkx6HiS4ksk_sjryyuAufD_xuLfCVD+A@mail.gmail.com","threadId":"58535","inReplyTo":"20221014045140.7ibix3632w4uset5@tb-raspi4","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-14T08:31:06Z","receivedAt":"2022-10-14T08:31:22Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"On Fri, Oct 14, 2022 at 6:51 AM Torsten Bögershausen <tboegi@web.de> wrote:\n>\n> On Thu, Oct 13, 2022 at 08:35:11AM +0200, Tao Klerks wrote:\n>\n> Did you ever consider to write a shell script,\n> that can detect icase-collisions ?\n>\n> For example, we can use Linux:\n>  git ls-files | tr 'A-Z' 'a-z' | sort | uniq -d ; echo $?\n>  include/uapi/linux/netfilter_ipv4/ipt_ecn.h\n>  include/uapi/linux/netfilter_ipv4/ipt_ttl.h\n>  [snip the other files]\n>\n> The GNU versions of uniq allow an even shorter command,\n> (But the POSIX versions don't)\n>\n> git ls-files  | sort | uniq -i -d\n>\n> I think that a script like this could do the trick:\n>\n> #!/bin/sh\n> ret=1\n> >/tmp/$$-exp\n> git ls-files  | sort | uniq -i -d >/tmp/$$-act &&\n>   cmp /tmp/$$-exp /tmp/$$-act &&\n>     ret=0\n>     rm -f /tmp/$$-exp /tmp/$$-act\n>     exit $ret\n>\n>\n> ####################\n> The usage of files in /tmp is probably debatable,\n> I want just illustrate how a combination of shell\n> scripts in combination with existing commands can be used.\n>\n> The biggest step may be to introduce a server-side hook\n> that does a check.\n> But once that is done and working, you probably do\n> not want to miss it.\n\nThanks for the proposal! Sorry I was a bit vague in my \"I suspect I'll\nhave to do a full-tree duplicate-file-search on every ref update\", but\nyour suggestion is almost exactly what I meant.\n\nOn my machine, on this repo, a full-tree case-insensitive duplicate\nsearch costs me about 800ms for 100k files, or 1,800ms for 200k files:\n\ngit ls-tree --name-only -r $NEWHASH | sort | uniq -i -d\n\nI need to use ls-tree rather than ls-files because this is indeed a\ncommand to run in an update hook, and there is no working tree - no\n(relevant) index, in a server-side update hook.\n\nThe 800ms for 100k files are composed of 200ms of ls-tree, 600ms of\nsort, and about 10ms of uniq.\n\nMy intent with supporting icase pathspec magic was to do something like:\n\ngit --icase-pathspecs ls-tree --name-only -r $NEWHASH -- PATHS OF\nADDED FILES | sort | uniq -i -d\n\nWhich would be near-instantaneous in the vast majority of cases (and\nI'd have some file count limit past which I would fall back to doing\nthe full tree, to avoid excessive command lengths). Unfortunately,\n\"--icase-pathspecs\" is not supported in ls-tree, hence this thread :)\n\nBut yes - ultimately, paying that \"full dupe search\" per-update server\nhook processing time cost has seemed like the only sensible way of\ndoing this - until I thought about Elijah's suggestion a little harder\nthat is!\n\nMore in the next part of the thread.\n"},{"id":"464916","messageId":"CA+JQ7M9tfey7oUJuWORXUw2=WGZ=++Q7bUfmt1x9M8HuCXDNTA@mail.gmail.com","threadId":"58535","inReplyTo":"CAPMMpogoX+R7eHkTZQKkx6HiS4ksk_sjryyuAufD_xuLfCVD+A@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Erik Cervin Edin","fromEmail":"erik@cervined.in","sentAt":"2022-10-14T08:37:51Z","receivedAt":"2022-10-14T08:38:36Z","isPatch":false,"sender":{"key":"erik@cervined.in","avatar":null},"body":"On Fri, Oct 14, 2022 at 10:32 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> I need to use ls-tree rather than ls-files because this is indeed a\n> command to run in an update hook, and there is no working tree - no\n> (relevant) index, in a server-side update hook.\n\nI believe\n  git diff --name-only\ndoesn't need a working tree\n"},{"id":"464917","messageId":"CAPMMpojvDj7Yc27HKQU4seSqg5Tx61RY3LOgMfkK=a0J25QYQw@mail.gmail.com","threadId":"58535","inReplyTo":"CABPp-BHaMCcLjdx2m4CALZQiTRQy_LovWfbdrga6XWhQJhoxWQ@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-14T08:48:37Z","receivedAt":"2022-10-14T08:48:55Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"On Fri, Oct 14, 2022 at 9:41 AM Elijah Newren <newren@gmail.com> wrote:\n>\n>\n> How exactly would case-insensitive matching in ls-tree help you here?\n\nI just attempted to demonstrate in response to Torsten's email; the\nassumption was that I could list the added files' paths in a\ncase-insensitive pathspec, and thereby get all duplicates fast and\nefficiently, for reasonably-sized commits.\n\n(new refs and very large commits would still need a full-tree dupe scan)\n\n> Can't you write a hook without such capability that rejects such\n> collisions?\n\nIt is possible, but far less convenient and I'm not confident that my\nshell scripting abilities will get me to a good place.\n\nThat said, having thought about your point, my shell scripting\nabilities are more likely to get me to a good place than attempting to\nadd icase pathspec magic support to ls-tree :)\n\n>\n> > I don't see this being something I can take on in my spare time, so\n> > for now I suspect I'll have to do a full-tree duplicate-file-search on\n> > every ref update, and simply accept the 1-second update hook\n> > processing time/delay per pushed ref :(\n>\n> I don't see why you need to do full-tree with existing options, nor\n> why the ls-tree option you want would somehow make it easier to avoid.\n> I think you can avoid the full-tree search with something like:\n>\n> git diff --diff-filter=A --no-renames --name-only $OLDHASH $NEWHASH |\n> sed -e s%/[^/]*$%/% | uniq | xargs git ls-tree --name-only $NEWHASH |\n> \\\n>    sort | uniq -i -d\n>\n> The final \"sort | uniq -i -d\" is taken from Torsten's suggestion.\n>\n> The git diff ... xargs git ls-tree section on the first line will\n> provide a list of all files (& subdirs) in the same directory as any\n> added file.  (Although, it has a blind spot for paths in the toplevel\n> directory.)\n\nThe theoretical problem with this approach is that it only addresses\ncase-insensitive-duplicate files, not directories.\n\nDirectories have been the problem, in \"my\" repo, around one-third of\nthe time - typically someone does a directory rename, and someone else\ndoes a bad merge and reintroduces the old directory.\n\nThat said, what \"icase pathspec magic\" actually *does*, is break down\nthe pathspec into iteratively more complete paths, level by level,\nlooking for case-duplicates at each level. That's something I could\npresumably do in shell scripting, collecting all the interesting\nsub-paths first, and then getting ls-tree to tell me about the\nimmediate children for each sub-path, doing case-insensitive dupe\nsearches across children for each of these sub-paths.\n\nls-tree supporting icase pathspec magic would clearly be more\nefficient (I wouldn't need N ls-tree git processes, where N is the\nnumber of sub-paths in the diff), but this should be plenty efficient\nfor normal commits, with a fallback to the full search\n\nThis seems like a sensible direction, I'll have a play.\n"},{"id":"464926","messageId":"CAPMMpoiPvWc9fNnzDRqPHtf1BdNsSd0ef9nzd6jcVOkvM3-LEw@mail.gmail.com","threadId":"58535","inReplyTo":"CA+JQ7M8s1W68+mzfe__+T5bJ821wYJqfgLBqA1=dSVH9Tx9fHA@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-14T08:57:11Z","receivedAt":"2022-10-14T08:57:47Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"On Fri, Oct 14, 2022 at 10:04 AM Erik Cervin Edin <erik@cervined.in> wrote:\n>\n>\n> On Fri, Oct 14, 2022 at 6:59 AM Torsten Bögershausen <tboegi@web.de> wrote:\n> >\n> > For example, we can use Linux:\n> >  git ls-files | tr 'A-Z' 'a-z' | sort | uniq -d ; echo $?\n>\n> In a repo with many files, maybe use git diff --name-only and just run\n> it periodically as a part of a check-in hook or something?\n>\n>   git diff --name-only HEAD~100..HEAD | tr 'A-Z' 'a-z' | sort | uniq -d\n>\n>\n[... next email...]\n> I believe\n>  git diff --name-only\n> doesn't need a working tree\n\nI don't understand this suggestion; doesn't it only catch duplicates\nwhere both instances were introduced in the same 100-commit range?\n\nThat has often or typically not been the case, in my experience. Often\none version of the file or folder will have existed for some time\n(days, months, years), and then a \"duplicate\" will be introduced.\n\nAs far as I can tell this \"diff large range\" approach is quite\nexpensive (37 seconds in a trivial test on this repo), and\nnon-comprehensive.\n"},{"id":"464927","messageId":"CAPMMpog94YUDPZswcGZ0ns10QXhaWOGmE95mgZEpdcx4GKsV3w@mail.gmail.com","threadId":"58535","inReplyTo":"CAPMMpojvDj7Yc27HKQU4seSqg5Tx61RY3LOgMfkK=a0J25QYQw@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-14T09:07:56Z","receivedAt":"2022-10-14T09:08:14Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"Small typo / confusion on my part:\n\nOn Fri, Oct 14, 2022 at 10:48 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> That said, what \"icase pathspec magic\" actually *does*, is break down\n> the pathspec into iteratively more complete paths, level by level,\n> looking for case-duplicates at each level.\n\nI meant what it does is *collect path matches* at iteratively more\ncomplete paths, level by level - it doesn't care about duplicates; any\nduplicate-detection is what you can then do on the result.\n"},{"id":"464934","messageId":"CA+JQ7M9nEHeALeHKO465xsNwmP8C3TXXDjuXAN9cFMmC-XEJnA@mail.gmail.com","threadId":"58535","inReplyTo":"CAPMMpog94YUDPZswcGZ0ns10QXhaWOGmE95mgZEpdcx4GKsV3w@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Erik Cervin Edin","fromEmail":"erik@cervined.in","sentAt":"2022-10-14T12:00:07Z","receivedAt":"2022-10-14T12:00:53Z","isPatch":false,"sender":{"key":"erik@cervined.in","avatar":null},"body":"On Fri, Oct 14, 2022 at 10:58 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> I don't understand this suggestion; doesn't it only catch duplicates\n> where both instances were introduced in the same 100-commit range?\n\nYes. It was a bit half-baked but the main idea was to limit the tree\nto a smaller subset (and not the whole tree) and incrementally\nchecking for introduced duplicates instead of a full tree search. I\nthink that's basically Elijah's idea. Get all (added?) files\nintroduced in a certain revision range (last change, since yesterday\netc.) and then only check those against the tree for duplicates in a\nmanner of how you define duplicates\n\nOn Fri, Oct 14, 2022 at 10:50 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> Directories have been the problem, in \"my\" repo, around one-third of\n> the time - typically someone does a directory rename, and someone else\n> does a bad merge and reintroduces the old directory.\n\nThat adds a bit of complexity :/\nbut should still be doable.\n\nNot perfect but maybe something along these lines? (caveat, possibly GNU only)\n\n#!/bin/sh\n\n# files added between revisions x y\nadded_files() {\n    git diff --diff-filter=A --name-only --no-renames $1 $2 ;\n}\n\n# folders of those added files\nadded_folders() {\n    added_files $1 $2 |\n        sed -e '/[^\\/]*/s@^@./@' -e 's@/[^/]*$@/@' |\n         sort -u ;\n}\n\n# all files tracked by git in *those* folders at HEAD\npossible_dupes() {\n    added_folders $1 $2 |\n        xargs git ls-tree --name-only HEAD ;\n}\n\n# case insensitive columns separated by \\x1\n# eg.\n#path\\x1PaTh\n#path\\x1path\ncase_insensitive() {\n    sed -e 's@.*@\\L\\0\\E\\x1\\0@' |\n        sort ;\n}\n\n\nx=$1\ny=$2\n# Find all duplicates paths (case insensitive)\n# in directories which were added between $x $y\npossible_dupes $x $y |\n    case_insensitive |\n    awk -F '\\x1' '\n        # actual \"duplicate\" paths, column $2\n        # as determined by case-insensitive column $1\n        $1 in a { print a[$1]; print $2 }\n        { a[$1]=$2 }\n    '    | uniq\n"},{"id":"464967","messageId":"CABPp-BEFoco4wg4BVE_aPz95cfMwAmbwU19eFyUOJTKj3q6wJA@mail.gmail.com","threadId":"58535","inReplyTo":"CAPMMpojvDj7Yc27HKQU4seSqg5Tx61RY3LOgMfkK=a0J25QYQw@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-10-14T17:06:23Z","receivedAt":"2022-10-14T17:06:42Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Oct 14, 2022 at 1:48 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> On Fri, Oct 14, 2022 at 9:41 AM Elijah Newren <newren@gmail.com> wrote:\n> >\n[...]\n> > I don't see why you need to do full-tree with existing options, nor\n> > why the ls-tree option you want would somehow make it easier to avoid.\n> > I think you can avoid the full-tree search with something like:\n> >\n> > git diff --diff-filter=A --no-renames --name-only $OLDHASH $NEWHASH |\n> > sed -e s%/[^/]*$%/% | uniq | xargs git ls-tree --name-only $NEWHASH |\n> > \\\n> >    sort | uniq -i -d\n> >\n> > The final \"sort | uniq -i -d\" is taken from Torsten's suggestion.\n> >\n> > The git diff ... xargs git ls-tree section on the first line will\n> > provide a list of all files (& subdirs) in the same directory as any\n> > added file.  (Although, it has a blind spot for paths in the toplevel\n> > directory.)\n>\n> The theoretical problem with this approach is that it only addresses\n> case-insensitive-duplicate files, not directories.\n\nIt'll catch some case-insensitive-duplicate directories too -- note\nthat I did call out that it'd print subdirs.  But to be more cautious,\nyou would need to carefully grab all leading directories of any added\npath, not just the immediate leading directory.\n\n> Directories have been the problem, in \"my\" repo, around one-third of\n> the time - typically someone does a directory rename, and someone else\n> does a bad merge and reintroduces the old directory.\n>\n> That said, what \"icase pathspec magic\" actually *does*, is break down\n> the pathspec into iteratively more complete paths, level by level,\n> looking for case-duplicates at each level. That's something I could\n> presumably do in shell scripting, collecting all the interesting\n> sub-paths first, and then getting ls-tree to tell me about the\n> immediate children for each sub-path, doing case-insensitive dupe\n> searches across children for each of these sub-paths.\n>\n> ls-tree supporting icase pathspec magic would clearly be more\n> efficient (I wouldn't need N ls-tree git processes, where N is the\n> number of sub-paths in the diff), but this should be plenty efficient\n> for normal commits, with a fallback to the full search\n>\n> This seems like a sensible direction, I'll have a play.\n\nIf you create a script that gives you all leading directories of any\nlisted path (plus replacing the toplevel dir with ':/'), such as this\n(which I'm calling 'all-leading-dirs.py'):\n\n\"\"\"\n#!/usr/bin/env python3\n\nimport os\nimport sys\n\npaths = sys.stdin.read().splitlines()\ndirs_seen = set()\nfor path in paths:\n  dir = path\n  while dir:\n    dir = os.path.dirname(dir)\n    if dir in dirs_seen:\n      continue\n    dirs_seen.add(dir)\nif dirs_seen:\n  # Replace top-level dir of \"\" with \":\"; we'll add the trailing '/'\nbelow when adding it to all other dirs\n  dirs_seen.remove(\"\")\n  dirs_seen.add(':')\n  for dir in dirs_seen:\n    print(dir+'/')  # ls-tree wants the trailing '/' if we are going\nto list contents within that tree rather than just the tree itself\n\"\"\"\n\nThen the following will catch duplicates files and directories for you:\n\ngit diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\nall-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n-t HEAD | sort | uniq -i -d\n\nand it no longer has problems catching duplicates in the toplevel\ndirectory either.  It does have (at most) two git invocations, but\nonly one invocation of ls-tree.  Here's a test script to prove it\nworks:\n\n\"\"\"\n#!/bin/bash\n\ngit init -b main nukeme\ncd nukeme\nmkdir -p dir1/subdir/whatever\nmkdir -p dir2/subdir/whatever\n>dir1/subdir/whatever/foo\n>dir2/subdir/whatever/foo\ngit add .\ngit commit -m initial\n\nmkdir -p dir1/SubDir/whatever\n>dir1/SubDir/whatever/foo\ngit add .\ngit commit -m stuff\n\ngit diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\nall-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n-t HEAD | sort | uniq -i -d\n\"\"\"\n\nThe output of this script is\n\"\"\"\ndir1/subdir\n\"\"\"\nwhich correctly notifies on the duplicate (dir1/SubDir being the\nother; uniq is the one that picks which of the two duplicate names to\nprint)\n"},{"id":"465035","messageId":"CAPMMpoictABXUhVCASZOiYZ4nydGtqiDYRpAELEBvbPn_5jRWA@mail.gmail.com","threadId":"58535","inReplyTo":"CABPp-BEFoco4wg4BVE_aPz95cfMwAmbwU19eFyUOJTKj3q6wJA@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-15T22:06:50Z","receivedAt":"2022-10-15T22:07:10Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"This seems to be working, thank you!!!\n\nTwo updates I had to make, in case this is useful to anyone else:\n\n1: I'm getting some weird behavior I can't explain yet, where some\npaths are returned from the ls-tree call twice: The input to ls-tree\nis all unique paths, but the output somehow includes a relatively\nsmall subset of paths twice.\nThis mysterious issue is easily addressed by adding an extra \"uniq\"\ncall to remove the \"trivial dupes\" before hunting for the\n\"case-insensitive dupes\" we're interested in:\n\ngit diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\nall-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n-t HEAD | sort | uniq | uniq -i -d\n\n2: The xargs call has issues with paths with spaces in them. Adding\n-d\"\\n\" seems to be a clean way to fix this\n\ngit diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\nall-leading-dirs.py | xargs -d\"\\n\" --no-run-if-empty git ls-tree --name-only\n-t HEAD | sort | uniq | uniq -i -d\n\n\nNot only does this approach seem to work well, but it also has far\nbetter performance characteristics than I was expecting!\n\nSimple small commit (10 files): 20ms\nReasonably large commit (10,000 files): 250ms\nDiff from empty on a smaller branch (100,000 files): 2,800ms\nDiff from empty on a larger branch (200,000 files): 5,400ms\n\n\nIt still makes sense to check the number of files/lines after doing\nthe diff, and do a \"simple\" 800ms full-tree (no-pathspec) dupe check\ninstead of this when your diff size goes past some file count\nthreshold, but it looks like that threshold would be quite high in my\nenvironment - 30k files maybe?\n\nI will have a go at writing a full update hook, and (without knowing\nwhether it will make sense from a performance perspective) I'd like to\ntry to implement the \"all-leading-dirs\" logic in bash 4 using\nassociative arrays, to remove the python dependency. If I make it work\nI'll post back here.\n\nThis seems to cover what I needed icase pathspec magic for in ls-tree,\nwithout having to implement it - so thanks again!\n\nTao\n\nOn Fri, Oct 14, 2022 at 7:06 PM Elijah Newren <newren@gmail.com> wrote:\n>\n> On Fri, Oct 14, 2022 at 1:48 AM Tao Klerks <tao@klerks.biz> wrote:\n> >\n> > On Fri, Oct 14, 2022 at 9:41 AM Elijah Newren <newren@gmail.com> wrote:\n> > >\n> [...]\n> > > I don't see why you need to do full-tree with existing options, nor\n> > > why the ls-tree option you want would somehow make it easier to avoid.\n> > > I think you can avoid the full-tree search with something like:\n> > >\n> > > git diff --diff-filter=A --no-renames --name-only $OLDHASH $NEWHASH |\n> > > sed -e s%/[^/]*$%/% | uniq | xargs git ls-tree --name-only $NEWHASH |\n> > > \\\n> > >    sort | uniq -i -d\n> > >\n> > > The final \"sort | uniq -i -d\" is taken from Torsten's suggestion.\n> > >\n> > > The git diff ... xargs git ls-tree section on the first line will\n> > > provide a list of all files (& subdirs) in the same directory as any\n> > > added file.  (Although, it has a blind spot for paths in the toplevel\n> > > directory.)\n> >\n> > The theoretical problem with this approach is that it only addresses\n> > case-insensitive-duplicate files, not directories.\n>\n> It'll catch some case-insensitive-duplicate directories too -- note\n> that I did call out that it'd print subdirs.  But to be more cautious,\n> you would need to carefully grab all leading directories of any added\n> path, not just the immediate leading directory.\n>\n> > Directories have been the problem, in \"my\" repo, around one-third of\n> > the time - typically someone does a directory rename, and someone else\n> > does a bad merge and reintroduces the old directory.\n> >\n> > That said, what \"icase pathspec magic\" actually *does*, is break down\n> > the pathspec into iteratively more complete paths, level by level,\n> > looking for case-duplicates at each level. That's something I could\n> > presumably do in shell scripting, collecting all the interesting\n> > sub-paths first, and then getting ls-tree to tell me about the\n> > immediate children for each sub-path, doing case-insensitive dupe\n> > searches across children for each of these sub-paths.\n> >\n> > ls-tree supporting icase pathspec magic would clearly be more\n> > efficient (I wouldn't need N ls-tree git processes, where N is the\n> > number of sub-paths in the diff), but this should be plenty efficient\n> > for normal commits, with a fallback to the full search\n> >\n> > This seems like a sensible direction, I'll have a play.\n>\n> If you create a script that gives you all leading directories of any\n> listed path (plus replacing the toplevel dir with ':/'), such as this\n> (which I'm calling 'all-leading-dirs.py'):\n>\n> \"\"\"\n> #!/usr/bin/env python3\n>\n> import os\n> import sys\n>\n> paths = sys.stdin.read().splitlines()\n> dirs_seen = set()\n> for path in paths:\n>   dir = path\n>   while dir:\n>     dir = os.path.dirname(dir)\n>     if dir in dirs_seen:\n>       continue\n>     dirs_seen.add(dir)\n> if dirs_seen:\n>   # Replace top-level dir of \"\" with \":\"; we'll add the trailing '/'\n> below when adding it to all other dirs\n>   dirs_seen.remove(\"\")\n>   dirs_seen.add(':')\n>   for dir in dirs_seen:\n>     print(dir+'/')  # ls-tree wants the trailing '/' if we are going\n> to list contents within that tree rather than just the tree itself\n> \"\"\"\n>\n> Then the following will catch duplicates files and directories for you:\n>\n> git diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\n> all-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n> -t HEAD | sort | uniq -i -d\n>\n> and it no longer has problems catching duplicates in the toplevel\n> directory either.  It does have (at most) two git invocations, but\n> only one invocation of ls-tree.  Here's a test script to prove it\n> works:\n>\n> \"\"\"\n> #!/bin/bash\n>\n> git init -b main nukeme\n> cd nukeme\n> mkdir -p dir1/subdir/whatever\n> mkdir -p dir2/subdir/whatever\n> >dir1/subdir/whatever/foo\n> >dir2/subdir/whatever/foo\n> git add .\n> git commit -m initial\n>\n> mkdir -p dir1/SubDir/whatever\n> >dir1/SubDir/whatever/foo\n> git add .\n> git commit -m stuff\n>\n> git diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\n> all-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n> -t HEAD | sort | uniq -i -d\n> \"\"\"\n>\n> The output of this script is\n> \"\"\"\n> dir1/subdir\n> \"\"\"\n> which correctly notifies on the duplicate (dir1/SubDir being the\n> other; uniq is the one that picks which of the two duplicate names to\n> print)\n"},{"id":"465110","messageId":"CAPMMpognADkh7ZJ+qYwE2GOoQ+knAthXJC-K6QAjN8qLwuS=7Q@mail.gmail.com","threadId":"58535","inReplyTo":"CAPMMpoictABXUhVCASZOiYZ4nydGtqiDYRpAELEBvbPn_5jRWA@mail.gmail.com","subject":"Re: icase pathspec magic support in ls-tree","fromName":"Tao Klerks","fromEmail":"tao@klerks.biz","sentAt":"2022-10-17T15:46:44Z","receivedAt":"2022-10-17T15:47:13Z","isPatch":false,"sender":{"key":"tao@klerks.biz","avatar":"https://avatars.githubusercontent.com/u/531704?v=4"},"body":"Thanks again for the code samples above!\n\nI've spent some time productizing this for my environment, and I think\nit's pretty close to optimal for my environment at least.\n\nIn case this can be of value to anyone else, I've attached the final thing.\n\nThis version is genericized a little - two specific specializations\nfor my environment not included here are:\n* a specific strategy for determining the most-likely-correct upstream\nbranch to use as a default for \"diff from\" for new branches, to avoid\nhaving to do a full-tree dupe search; in most environments choosing\n\"master\" or \"main\" would likely be the right thing most of the time\n* a specific list of branch paths that we should validate (vs others\nthat we should not)\n\nBest regards,\nTao\n\nOn Sun, Oct 16, 2022 at 12:06 AM Tao Klerks <tao@klerks.biz> wrote:\n>\n> This seems to be working, thank you!!!\n>\n> Two updates I had to make, in case this is useful to anyone else:\n>\n> 1: I'm getting some weird behavior I can't explain yet, where some\n> paths are returned from the ls-tree call twice: The input to ls-tree\n> is all unique paths, but the output somehow includes a relatively\n> small subset of paths twice.\n> This mysterious issue is easily addressed by adding an extra \"uniq\"\n> call to remove the \"trivial dupes\" before hunting for the\n> \"case-insensitive dupes\" we're interested in:\n>\n> git diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\n> all-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n> -t HEAD | sort | uniq | uniq -i -d\n>\n> 2: The xargs call has issues with paths with spaces in them. Adding\n> -d\"\\n\" seems to be a clean way to fix this\n>\n> git diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\n> all-leading-dirs.py | xargs -d\"\\n\" --no-run-if-empty git ls-tree --name-only\n> -t HEAD | sort | uniq | uniq -i -d\n>\n>\n> Not only does this approach seem to work well, but it also has far\n> better performance characteristics than I was expecting!\n>\n> Simple small commit (10 files): 20ms\n> Reasonably large commit (10,000 files): 250ms\n> Diff from empty on a smaller branch (100,000 files): 2,800ms\n> Diff from empty on a larger branch (200,000 files): 5,400ms\n>\n>\n> It still makes sense to check the number of files/lines after doing\n> the diff, and do a \"simple\" 800ms full-tree (no-pathspec) dupe check\n> instead of this when your diff size goes past some file count\n> threshold, but it looks like that threshold would be quite high in my\n> environment - 30k files maybe?\n>\n> I will have a go at writing a full update hook, and (without knowing\n> whether it will make sense from a performance perspective) I'd like to\n> try to implement the \"all-leading-dirs\" logic in bash 4 using\n> associative arrays, to remove the python dependency. If I make it work\n> I'll post back here.\n>\n> This seems to cover what I needed icase pathspec magic for in ls-tree,\n> without having to implement it - so thanks again!\n>\n> Tao\n>\n> On Fri, Oct 14, 2022 at 7:06 PM Elijah Newren <newren@gmail.com> wrote:\n> >\n> > On Fri, Oct 14, 2022 at 1:48 AM Tao Klerks <tao@klerks.biz> wrote:\n> > >\n> > > On Fri, Oct 14, 2022 at 9:41 AM Elijah Newren <newren@gmail.com> wrote:\n> > > >\n> > [...]\n> > > > I don't see why you need to do full-tree with existing options, nor\n> > > > why the ls-tree option you want would somehow make it easier to avoid.\n> > > > I think you can avoid the full-tree search with something like:\n> > > >\n> > > > git diff --diff-filter=A --no-renames --name-only $OLDHASH $NEWHASH |\n> > > > sed -e s%/[^/]*$%/% | uniq | xargs git ls-tree --name-only $NEWHASH |\n> > > > \\\n> > > >    sort | uniq -i -d\n> > > >\n> > > > The final \"sort | uniq -i -d\" is taken from Torsten's suggestion.\n> > > >\n> > > > The git diff ... xargs git ls-tree section on the first line will\n> > > > provide a list of all files (& subdirs) in the same directory as any\n> > > > added file.  (Although, it has a blind spot for paths in the toplevel\n> > > > directory.)\n> > >\n> > > The theoretical problem with this approach is that it only addresses\n> > > case-insensitive-duplicate files, not directories.\n> >\n> > It'll catch some case-insensitive-duplicate directories too -- note\n> > that I did call out that it'd print subdirs.  But to be more cautious,\n> > you would need to carefully grab all leading directories of any added\n> > path, not just the immediate leading directory.\n> >\n> > > Directories have been the problem, in \"my\" repo, around one-third of\n> > > the time - typically someone does a directory rename, and someone else\n> > > does a bad merge and reintroduces the old directory.\n> > >\n> > > That said, what \"icase pathspec magic\" actually *does*, is break down\n> > > the pathspec into iteratively more complete paths, level by level,\n> > > looking for case-duplicates at each level. That's something I could\n> > > presumably do in shell scripting, collecting all the interesting\n> > > sub-paths first, and then getting ls-tree to tell me about the\n> > > immediate children for each sub-path, doing case-insensitive dupe\n> > > searches across children for each of these sub-paths.\n> > >\n> > > ls-tree supporting icase pathspec magic would clearly be more\n> > > efficient (I wouldn't need N ls-tree git processes, where N is the\n> > > number of sub-paths in the diff), but this should be plenty efficient\n> > > for normal commits, with a fallback to the full search\n> > >\n> > > This seems like a sensible direction, I'll have a play.\n> >\n> > If you create a script that gives you all leading directories of any\n> > listed path (plus replacing the toplevel dir with ':/'), such as this\n> > (which I'm calling 'all-leading-dirs.py'):\n> >\n> > \"\"\"\n> > #!/usr/bin/env python3\n> >\n> > import os\n> > import sys\n> >\n> > paths = sys.stdin.read().splitlines()\n> > dirs_seen = set()\n> > for path in paths:\n> >   dir = path\n> >   while dir:\n> >     dir = os.path.dirname(dir)\n> >     if dir in dirs_seen:\n> >       continue\n> >     dirs_seen.add(dir)\n> > if dirs_seen:\n> >   # Replace top-level dir of \"\" with \":\"; we'll add the trailing '/'\n> > below when adding it to all other dirs\n> >   dirs_seen.remove(\"\")\n> >   dirs_seen.add(':')\n> >   for dir in dirs_seen:\n> >     print(dir+'/')  # ls-tree wants the trailing '/' if we are going\n> > to list contents within that tree rather than just the tree itself\n> > \"\"\"\n> >\n> > Then the following will catch duplicates files and directories for you:\n> >\n> > git diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\n> > all-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n> > -t HEAD | sort | uniq -i -d\n> >\n> > and it no longer has problems catching duplicates in the toplevel\n> > directory either.  It does have (at most) two git invocations, but\n> > only one invocation of ls-tree.  Here's a test script to prove it\n> > works:\n> >\n> > \"\"\"\n> > #!/bin/bash\n> >\n> > git init -b main nukeme\n> > cd nukeme\n> > mkdir -p dir1/subdir/whatever\n> > mkdir -p dir2/subdir/whatever\n> > >dir1/subdir/whatever/foo\n> > >dir2/subdir/whatever/foo\n> > git add .\n> > git commit -m initial\n> >\n> > mkdir -p dir1/SubDir/whatever\n> > >dir1/SubDir/whatever/foo\n> > git add .\n> > git commit -m stuff\n> >\n> > git diff --diff-filter=A --no-renames --name-only HEAD~1 HEAD |\n> > all-leading-dirs.py | xargs --no-run-if-empty git ls-tree --name-only\n> > -t HEAD | sort | uniq -i -d\n> > \"\"\"\n> >\n> > The output of this script is\n> > \"\"\"\n> > dir1/subdir\n> > \"\"\"\n> > which correctly notifies on the duplicate (dir1/SubDir being the\n> > other; uniq is the one that picks which of the two duplicate names to\n> > print)\n"}]}