{"thread":{"id":"21213","subject":"Supressing sorting of trees","startedAt":"2009-10-12T13:27:56Z","lastAt":"2009-10-13T20:49:22Z","messageCount":9,"participants":["Sal Mangano","Shawn O. Pearce","Johannes Schindelin","Martin Langhoff","Salvatore Mangano","Ealdwulf Wuffinga"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"124699","messageId":"loom.20091012T152113-874@post.gmane.org","threadId":"21213","inReplyTo":null,"subject":"Supressing sorting of trees","fromName":"Sal Mangano","fromEmail":"smangano@into-technology.com","sentAt":"2009-10-12T13:27:56Z","receivedAt":"2009-10-12T13:27:56Z","isPatch":false,"sender":{"key":"smangano@into-technology.com","avatar":"https://gravatar.com/avatar/5249353839fd665c6990f023a7d5f1a2b092891e09b5cac87cc02c691beea67f?d=mp&s=160"},"body":"I am using Git in a non-standard way and need to make a few twaeks in my \ncustom build. I have added a --nosort option to git mktree which will suppress\nthe qsort of the tree. \n\nWill this break any other git functions? Are there any commands that assume \ntrees are always sorted?\n"},{"id":"124700","messageId":"20091012142032.GG9261@spearce.org","threadId":"21213","inReplyTo":"loom.20091012T152113-874@post.gmane.org","subject":"Re: Supressing sorting of trees","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-10-12T14:20:32Z","receivedAt":"2009-10-12T14:20:32Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Sal Mangano wrote:\n> I am using Git in a non-standard way and need to make a few twaeks in my \n> custom build. I have added a --nosort option to git mktree which will suppress\n> the qsort of the tree. \n> \n> Will this break any other git functions? Are there any commands that assume \n> trees are always sorted?\n\n_YES IT BREAKS GIT_.\n\nYou cannot do this.\n\nA Git repository whose trees are not sorted according to the Git\nspecific sort ordering is severly broken and most tools will fail\nhorribly on it.\n\nAlmost all code which reads trees assumes the names are sorted in a\nspecific order. These tools perform sorted merges against other tree\nlike structures. If the names are out of order the merge will fail.\n`git fsck` will complain that the tree is not sorted properly.\nTools like `git log -- foo.c` will fail randomly because they break\nout of the entry lookup as soon as they find a name that is after\nfoo.c, as they assume the tree is sorted.\n\nI could go on. But there is no point.\n\nOh, and trust me when I say this, the tree sorting matters. Long ago\nJGit had a bug where it didn't sort trees correctly all of the time\nand we had a devil of a time tracking down that corruption.\n\n-- \nShawn.\n"},{"id":"124711","messageId":"loom.20091012T171550-239@post.gmane.org","threadId":"21213","inReplyTo":"20091012142032.GG9261@spearce.org","subject":"Re: Supressing sorting of trees","fromName":"Sal Mangano","fromEmail":"smangano@into-technology.com","sentAt":"2009-10-12T15:43:52Z","receivedAt":"2009-10-12T15:43:52Z","isPatch":false,"sender":{"key":"smangano@into-technology.com","avatar":"https://gravatar.com/avatar/5249353839fd665c6990f023a7d5f1a2b092891e09b5cac87cc02c691beea67f?d=mp&s=160"},"body":"Shawn O. Pearce spearce.org> writes:\n\n> \n> Sal Mangano into-technology.com> wrote:\n> > I am using Git in a non-standard way and need to make a few twaeks in my \n> > custom build. I have added a --nosort option to git mktree which will \nsuppress\n> > the qsort of the tree. \n> > \n> > Will this break any other git functions? Are there any commands that assume \n> > trees are always sorted?\n> \n> _YES IT BREAKS GIT_.\n> \n> You cannot do this.\n> \n> A Git repository whose trees are not sorted according to the Git\n> specific sort ordering is severly broken and most tools will fail\n> horribly on it.\n> \n> Almost all code which reads trees assumes the names are sorted in a\n> specific order. These tools perform sorted merges against other tree\n> like structures. If the names are out of order the merge will fail.\n> `git fsck` will complain that the tree is not sorted properly.\n> Tools like `git log -- foo.c` will fail randomly because they break\n> out of the entry lookup as soon as they find a name that is after\n> foo.c, as they assume the tree is sorted.\n> \n> I could go on. But there is no point.\n> \n> Oh, and trust me when I say this, the tree sorting matters. Long ago\n> JGit had a bug where it didn't sort trees correctly all of the time\n> and we had a devil of a time tracking down that corruption.\n> \n\nThanks Shawn. I get the picture. \n\nNow, let's assume I am stubborn, crazy or both :-)\n\nI can modify fsck to ignore unsorted and at the moment I don't care about \nmerging trees. If I hunt down all usage of base_name_compare will that identify \nall code with the sort assumption or is there other places as well? I can go \nthrough the entire source to figure this out myself but I need to get something \nhacked up very quickly and would appreciate help even if you think I am nuts! \n"},{"id":"124713","messageId":"alpine.DEB.1.00.0910121803360.4985@pacific.mpi-cbg.de","threadId":"21213","inReplyTo":"loom.20091012T171550-239@post.gmane.org","subject":"Re: Supressing sorting of trees","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-10-12T16:05:06Z","receivedAt":"2009-10-12T16:05:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 12 Oct 2009, Sal Mangano wrote:\n\n> Shawn O. Pearce spearce.org> writes:\n> \n> > \n> > Sal Mangano into-technology.com> wrote:\n> > > I am using Git in a non-standard way and need to make a few twaeks \n> > > in my custom build. I have added a --nosort option to git mktree \n> > > which will suppress the qsort of the tree.\n> > > \n> > > Will this break any other git functions? Are there any commands that \n> > > assume trees are always sorted?\n> > \n> > _YES IT BREAKS GIT_.\n> > \n> > You cannot do this.\n> > \n> > A Git repository whose trees are not sorted according to the Git \n> > specific sort ordering is severly broken and most tools will fail \n> > horribly on it.\n> > \n> > Almost all code which reads trees assumes the names are sorted in a \n> > specific order. These tools perform sorted merges against other tree \n> > like structures. If the names are out of order the merge will fail. \n> > `git fsck` will complain that the tree is not sorted properly. Tools \n> > like `git log -- foo.c` will fail randomly because they break out of \n> > the entry lookup as soon as they find a name that is after foo.c, as \n> > they assume the tree is sorted.\n> > \n> > I could go on. But there is no point.\n> > \n> > Oh, and trust me when I say this, the tree sorting matters. Long ago \n> > JGit had a bug where it didn't sort trees correctly all of the time \n> > and we had a devil of a time tracking down that corruption.\n> > \n> \n> Thanks Shawn. I get the picture. \n> \n> Now, let's assume I am stubborn, crazy or both :-)\n> \n> I can modify fsck to ignore unsorted and at the moment I don't care \n> about merging trees. If I hunt down all usage of base_name_compare will \n> that identify all code with the sort assumption or is there other places \n> as well? I can go > through the entire source to figure this out myself \n> but I need to get something hacked up very quickly and would appreciate \n> help even if you think I am nuts!\n\nLook, one of the most trusted Git contributors just told you that you are \nasking for trouble.\n\nIt has nothing to do with being stubborn if you insist on doing it now.\n\nBut I smell an XY problem. Why don't you just reveil _what_ you want to \ndo (as opposed to _how_ you think you should do it)?\n\nCiao,\nDscho\n"},{"id":"124715","messageId":"loom.20091012T182258-9@post.gmane.org","threadId":"21213","inReplyTo":"alpine.DEB.1.00.0910121803360.4985@pacific.mpi-cbg.de","subject":"Re: Supressing sorting of trees","fromName":"Sal Mangano","fromEmail":"smangano@into-technology.com","sentAt":"2009-10-12T16:51:59Z","receivedAt":"2009-10-12T16:51:59Z","isPatch":false,"sender":{"key":"smangano@into-technology.com","avatar":"https://gravatar.com/avatar/5249353839fd665c6990f023a7d5f1a2b092891e09b5cac87cc02c691beea67f?d=mp&s=160"},"body":"Johannes Schindelin gmx.de> writes:\n\n> \n> Hi,\n> \n> On Mon, 12 Oct 2009, Sal Mangano wrote:\n> \n> > Shawn O. Pearce spearce.org> writes:\n> > \n> > > \n> > > Sal Mangano into-technology.com> wrote:\n> > > > I am using Git in a non-standard way and need to make a few twaeks \n> > > > in my custom build. I have added a --nosort option to git mktree \n> > > > which will suppress the qsort of the tree.\n> > > > \n> > > > Will this break any other git functions? Are there any commands that \n> > > > assume trees are always sorted?\n> > > \n> > > _YES IT BREAKS GIT_.\n> > > \n> > > You cannot do this.\n> > > \n> > > A Git repository whose trees are not sorted according to the Git \n> > > specific sort ordering is severly broken and most tools will fail \n> > > horribly on it.\n> > > \n> > > Almost all code which reads trees assumes the names are sorted in a \n> > > specific order. These tools perform sorted merges against other tree \n> > > like structures. If the names are out of order the merge will fail. \n> > > `git fsck` will complain that the tree is not sorted properly. Tools \n> > > like `git log -- foo.c` will fail randomly because they break out of \n> > > the entry lookup as soon as they find a name that is after foo.c, as \n> > > they assume the tree is sorted.\n> > > \n> > > I could go on. But there is no point.\n> > > \n> > > Oh, and trust me when I say this, the tree sorting matters. Long ago \n> > > JGit had a bug where it didn't sort trees correctly all of the time \n> > > and we had a devil of a time tracking down that corruption.\n> > > \n> > \n> > Thanks Shawn. I get the picture. \n> > \n> > Now, let's assume I am stubborn, crazy or both \n> > \n> > I can modify fsck to ignore unsorted and at the moment I don't care \n> > about merging trees. If I hunt down all usage of base_name_compare will \n> > that identify all code with the sort assumption or is there other places \n> > as well? I can go > through the entire source to figure this out myself \n> > but I need to get something hacked up very quickly and would appreciate \n> > help even if you think I am nuts!\n> \n> Look, one of the most trusted Git contributors just told you that you are \n> asking for trouble.\n> \n> It has nothing to do with being stubborn if you insist on doing it now.\n> \n> But I smell an XY problem. Why don't you just reveil _what_ you want to \n> do (as opposed to _how_ you think you should do it)?\n> \n> Ciao,\n> Dscho\n> \n> \n\nMy apologies for being cryptic.\n\nI am working on a project where I need to create a repository consisting of \nhierarchical \"blobs\" of content (sound familiar?). In this repository the \norder of the blobs as specified by the end user is definitely important. \nHowever, I have a bunch of other reqs that fit Git perfectly such as the \nability to quickly tell if two trees are the same using their SHA1 and the \nability to version control the repository. My repository has no relationship \nto files stored on a file system unlike a typical use of Git. I also don't \ncare about whether my repository remains compatible with standard Git because \nno one will access this repository using standard Git.\n\nNow I can proceed in a few ways:\n\n1) I can write by repository from scratch.\n2) I can use Git unchanged but preserve order by storing some information in \neach sub tree (e.g. an extra blob) which retains the real order. I can also\nstore this information once for the whole \"chunks\" of the repository. \n3) I can change Git to suite my needs understanding that it is not Git \nanymore.\n\nFor me, (1) makes no sense at this time. I started with the hope that (2) \nwould work but realized it is very awkward and will cause performance problems\nbecause it means most updates where ordering matters will have to update the \nGit trees and my private ordering blob(s). So, after a quick look at the \nsource code it seemed like hacking Git into what I wanted was easier than 1 \nor 2. \n\nI realized tree merge would probably break and wanted to know what \nelse. It is good to know fsck breaks. What else will break that I have to \ndeal with?\n"},{"id":"124738","messageId":"46a038f90910121236x6bbe258bwa3bc3fdcc54de524@mail.gmail.com","threadId":"21213","inReplyTo":"loom.20091012T182258-9@post.gmane.org","subject":"Re: Supressing sorting of trees","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2009-10-12T19:36:59Z","receivedAt":"2009-10-12T19:36:59Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Mon, Oct 12, 2009 at 6:51 PM, Sal Mangano\n wrote:\n> 2) I can use Git unchanged but preserve order by storing some information in\n> each sub tree (e.g. an extra blob) which retains the real order. I can also\n\nThis #2 is your best bet by far. An extra blob in each subdir is just\none option, you can handle this \"extra metadata\" in a number of ways\n-- maybe external to git, on a separate history will work best.\n\nThe downsides of messing with internal tree handling of git are so\nstaggering that you'd do better to throw git away.\n\n(this is from experience of abusing git to various purposes that have\nlittle to do with version control :-) )\n\nIn other words: Shaun and Dscho are right, so right that it hurts.\n\nhth,\n\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"124743","messageId":"DF65B4B0-62B1-4469-99E1-3305434F9D59@into-technology.com","threadId":"21213","inReplyTo":"46a038f90910121236x6bbe258bwa3bc3fdcc54de524@mail.gmail.com","subject":"Re: Supressing sorting of trees","fromName":"Salvatore Mangano","fromEmail":"smangano@into-technology.com","sentAt":"2009-10-12T20:02:37Z","receivedAt":"2009-10-12T20:02:37Z","isPatch":false,"sender":{"key":"smangano@into-technology.com","avatar":"https://gravatar.com/avatar/5249353839fd665c6990f023a7d5f1a2b092891e09b5cac87cc02c691beea67f?d=mp&s=160"},"body":"\nOn Oct 12, 2009, at 3:36 PM, Martin Langhoff wrote:\n\n> On Mon, Oct 12, 2009 at 6:51 PM, Sal Mangano\n> wrote:\n>> 2) I can use Git unchanged but preserve order by storing some \n>> information in\n>> each sub tree (e.g. an extra blob) which retains the real order. I \n>> can also\n>\n> This #2 is your best bet by far. An extra blob in each subdir is just\n> one option, you can handle this \"extra metadata\" in a number of ways\n> -- maybe external to git, on a separate history will work best.\n>\n> The downsides of messing with internal tree handling of git are so\n> staggering that you'd do better to throw git away.\n>\n> (this is from experience of abusing git to various purposes that have\n> little to do with version control :-) )\n>\n> In other words: Shaun and Dscho are right, so right that it hurts.\n>\n\nThanks Martin. I suspect you, Shaun and Dscho are correct. But, can \nanyone point to specific code\nthat would allow me to see first hand that this is hopeless. So far, \nbased on the code I looked at, I see\nit as problematic but not hopeless. Here I define \"problematic\" as \nhaving to change a few files and/or\navoid using some features while \"hopeless\" meaning I'd have to change \nalmost very single plumbing\ncommand.\n"},{"id":"124744","messageId":"46a038f90910121324s34c29133t7ba4558771bf404f@mail.gmail.com","threadId":"21213","inReplyTo":"DF65B4B0-62B1-4469-99E1-3305434F9D59@into-technology.com","subject":"Re: Supressing sorting of trees","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2009-10-12T20:24:16Z","receivedAt":"2009-10-12T20:24:16Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Mon, Oct 12, 2009 at 10:02 PM, Salvatore Mangano\n wrote:\n> point to specific code\n\nShaun pointed out some very core code. And it is just a core concept.\nJust read up on the core organizing concept that is the \"tree\". Git\nrelies on the layout of the tree being strictly deterministic.\n\nIt is a prevalent assumption in the whole codebase.\n\nYes you can change it, but assume you will have to audit/rewrite 80%\nof the core code.\n\nWant \"proof\"? Go change it, then try \"make test\", or reimport a large\nrepository try to use the git commands over it. We'll relax and watch\nthe fireworks :-)\n\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"124893","messageId":"efe2b6d70910131349n4cab61d0h9a9c8099830095f9@mail.gmail.com","threadId":"21213","inReplyTo":"loom.20091012T182258-9@post.gmane.org","subject":"Re: Supressing sorting of trees","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-10-13T20:49:22Z","receivedAt":"2009-10-13T20:49:22Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Mon, Oct 12, 2009 at 5:51 PM, Sal Mangano\n wrote:\n\n> 1) I can write by repository from scratch.\n> 2) I can use Git unchanged but preserve order by storing some information in\n> each sub tree (e.g. an extra blob) which retains the real order. I can also\n> store this information once for the whole \"chunks\" of the repository.\n> 3) I can change Git to suite my needs understanding that it is not Git\n> anymore.\n>\n> For me, (1) makes no sense at this time. I started with the hope that (2)\n> would work but realized it is very awkward and will cause performance problems\n> because it means most updates where ordering matters will have to update the\n> Git trees and my private ordering blob(s). So, after a quick look at the\n> source code it seemed like hacking Git into what I wanted was easier than 1\n> or 2.\n\nYou could add a prefix to the names so you get the order you want. Eg:\na-foo\nb-bar\nc-baz\n\nIf you need to move foo to between bar and baz, you just rename it to\nba-foo, etc.\n\nEaldwulf\n"}]}