Sal ManganoI am using Git in a non-standard way and need to make a few twaeks in my custom build. I have added a --nosort option to git mktree which will suppress the qsort of the tree.
Will this break any other git functions? Are there any commands that assume trees are always sorted?
Shawn O. PearceRe: Supressing sorting of trees
Sal Mangano <smangano@into-technology.com> wrote:
> I am using Git in a non-standard way and need to make a few twaeks in my > custom build. I have added a --nosort option to git mktree which will suppress > the qsort of the tree. > > Will this break any other git functions? Are there any commands that assume > trees are always sorted?
_YES IT BREAKS GIT_.
You cannot do this.
A Git repository whose trees are not sorted according to the Git specific sort ordering is severly broken and most tools will fail horribly on it.
Almost all code which reads trees assumes the names are sorted in a specific order. These tools perform sorted merges against other tree like structures. If the names are out of order the merge will fail. `git fsck` will complain that the tree is not sorted properly. Tools like `git log -- foo.c` will fail randomly because they break out of the entry lookup as soon as they find a name that is after foo.c, as they assume the tree is sorted.
I could go on. But there is no point.
Oh, and trust me when I say this, the tree sorting matters. Long ago JGit had a bug where it didn't sort trees correctly all of the time and we had a devil of a time tracking down that corruption.
-- Shawn.
Sal ManganoRe: Supressing sorting of trees
Shawn O. Pearce <spearce <at> spearce.org> writes:
> > Sal Mangano <smangano <at> into-technology.com> wrote: > > I am using Git in a non-standard way and need to make a few twaeks in my > > custom build. I have added a --nosort option to git mktree which will
suppress
> > the qsort of the tree. > > > > Will this break any other git functions? Are there any commands that assume > > trees are always sorted? > > _YES IT BREAKS GIT_. > > You cannot do this. > > A Git repository whose trees are not sorted according to the Git > specific sort ordering is severly broken and most tools will fail > horribly on it. > > Almost all code which reads trees assumes the names are sorted in a > specific order. These tools perform sorted merges against other tree > like structures. If the names are out of order the merge will fail. > `git fsck` will complain that the tree is not sorted properly. > Tools like `git log -- foo.c` will fail randomly because they break > out of the entry lookup as soon as they find a name that is after > foo.c, as they assume the tree is sorted. > > I could go on. But there is no point. > > Oh, and trust me when I say this, the tree sorting matters. Long ago > JGit had a bug where it didn't sort trees correctly all of the time > and we had a devil of a time tracking down that corruption. >
Thanks Shawn. I get the picture.
Now, let's assume I am stubborn, crazy or both :-)
I can modify fsck to ignore unsorted and at the moment I don't care about merging trees. If I hunt down all usage of base_name_compare will that identify all code with the sort assumption or is there other places as well? I can go through the entire source to figure this out myself but I need to get something hacked up very quickly and would appreciate help even if you think I am nuts!
Johannes SchindelinRe: Supressing sorting of trees
Hi,
On Mon, 12 Oct 2009, Sal Mangano wrote:
> Shawn O. Pearce <spearce <at> spearce.org> writes: > > > > > Sal Mangano <smangano <at> into-technology.com> wrote: > > > I am using Git in a non-standard way and need to make a few twaeks > > > in my custom build. I have added a --nosort option to git mktree > > > which will suppress the qsort of the tree. > > > > > > Will this break any other git functions? Are there any commands that > > > assume trees are always sorted? > > > > _YES IT BREAKS GIT_. > > > > You cannot do this. > > > > A Git repository whose trees are not sorted according to the Git > > specific sort ordering is severly broken and most tools will fail > > horribly on it. > > > > Almost all code which reads trees assumes the names are sorted in a > > specific order. These tools perform sorted merges against other tree > > like structures. If the names are out of order the merge will fail. > > `git fsck` will complain that the tree is not sorted properly. Tools > > like `git log -- foo.c` will fail randomly because they break out of > > the entry lookup as soon as they find a name that is after foo.c, as > > they assume the tree is sorted. > > > > I could go on. But there is no point. > > > > Oh, and trust me when I say this, the tree sorting matters. Long ago > > JGit had a bug where it didn't sort trees correctly all of the time > > and we had a devil of a time tracking down that corruption. > > > > Thanks Shawn. I get the picture. > > Now, let's assume I am stubborn, crazy or both :-) > > I can modify fsck to ignore unsorted and at the moment I don't care > about merging trees. If I hunt down all usage of base_name_compare will > that identify all code with the sort assumption or is there other places > as well? I can go > through the entire source to figure this out myself > but I need to get something hacked up very quickly and would appreciate > help even if you think I am nuts!
Look, one of the most trusted Git contributors just told you that you are asking for trouble.
It has nothing to do with being stubborn if you insist on doing it now.
But I smell an XY problem. Why don't you just reveil _what_ you want to do (as opposed to _how_ you think you should do it)?
Ciao, Dscho
Sal ManganoRe: Supressing sorting of trees
Johannes Schindelin <Johannes.Schindelin <at> gmx.de> writes:
> > Hi, > > On Mon, 12 Oct 2009, Sal Mangano wrote: > > > Shawn O. Pearce <spearce <at> spearce.org> writes: > > > > > > > > Sal Mangano <smangano <at> into-technology.com> wrote: > > > > I am using Git in a non-standard way and need to make a few twaeks > > > > in my custom build. I have added a --nosort option to git mktree > > > > which will suppress the qsort of the tree. > > > > > > > > Will this break any other git functions? Are there any commands that > > > > assume trees are always sorted? > > > > > > _YES IT BREAKS GIT_. > > > > > > You cannot do this. > > > > > > A Git repository whose trees are not sorted according to the Git > > > specific sort ordering is severly broken and most tools will fail > > > horribly on it. > > > > > > Almost all code which reads trees assumes the names are sorted in a > > > specific order. These tools perform sorted merges against other tree > > > like structures. If the names are out of order the merge will fail. > > > `git fsck` will complain that the tree is not sorted properly. Tools > > > like `git log -- foo.c` will fail randomly because they break out of > > > the entry lookup as soon as they find a name that is after foo.c, as > > > they assume the tree is sorted. > > > > > > I could go on. But there is no point. > > > > > > Oh, and trust me when I say this, the tree sorting matters. Long ago > > > JGit had a bug where it didn't sort trees correctly all of the time > > > and we had a devil of a time tracking down that corruption. > > > > > > > Thanks Shawn. I get the picture. > > > > Now, let's assume I am stubborn, crazy or both > > > > I can modify fsck to ignore unsorted and at the moment I don't care > > about merging trees. If I hunt down all usage of base_name_compare will > > that identify all code with the sort assumption or is there other places > > as well? I can go > through the entire source to figure this out myself > > but I need to get something hacked up very quickly and would appreciate > > help even if you think I am nuts! > > Look, one of the most trusted Git contributors just told you that you are > asking for trouble. > > It has nothing to do with being stubborn if you insist on doing it now. > > But I smell an XY problem. Why don't you just reveil _what_ you want to > do (as opposed to _how_ you think you should do it)? > > Ciao, > Dscho > >
My apologies for being cryptic.
I am working on a project where I need to create a repository consisting of hierarchical "blobs" of content (sound familiar?). In this repository the order of the blobs as specified by the end user is definitely important. However, I have a bunch of other reqs that fit Git perfectly such as the ability to quickly tell if two trees are the same using their SHA1 and the ability to version control the repository. My repository has no relationship to files stored on a file system unlike a typical use of Git. I also don't care about whether my repository remains compatible with standard Git because no one will access this repository using standard Git.
Now I can proceed in a few ways:
1) I can write by repository from scratch. 2) I can use Git unchanged but preserve order by storing some information in each sub tree (e.g. an extra blob) which retains the real order. I can also store this information once for the whole "chunks" of the repository. 3) I can change Git to suite my needs understanding that it is not Git anymore.
For me, (1) makes no sense at this time. I started with the hope that (2) would work but realized it is very awkward and will cause performance problems because it means most updates where ordering matters will have to update the Git trees and my private ordering blob(s). So, after a quick look at the source code it seemed like hacking Git into what I wanted was easier than 1 or 2.
I realized tree merge would probably break and wanted to know what else. It is good to know fsck breaks. What else will break that I have to deal with?
Martin LanghoffRe: Supressing sorting of trees
On Mon, Oct 12, 2009 at 6:51 PM, Sal Mangano <smangano@into-technology.com> wrote:
> 2) I can use Git unchanged but preserve order by storing some information in > each sub tree (e.g. an extra blob) which retains the real order. I can also
This #2 is your best bet by far. An extra blob in each subdir is just one option, you can handle this "extra metadata" in a number of ways -- maybe external to git, on a separate history will work best.
The downsides of messing with internal tree handling of git are so staggering that you'd do better to throw git away.
(this is from experience of abusing git to various purposes that have little to do with version control :-) )
In other words: Shaun and Dscho are right, so right that it hurts.
hth,
m
-- martin.langhoff@gmail.com martin@laptop.org -- School Server Architect - ask interesting questions - don't get distracted with shiny stuff - working code first - http://wiki.laptop.org/go/User:Martinlanghoff
Salvatore ManganoRe: Supressing sorting of trees
On Oct 12, 2009, at 3:36 PM, Martin Langhoff wrote:
> On Mon, Oct 12, 2009 at 6:51 PM, Sal Mangano > <smangano@into-technology.com> wrote: >> 2) I can use Git unchanged but preserve order by storing some >> information in >> each sub tree (e.g. an extra blob) which retains the real order. I >> can also > > This #2 is your best bet by far. An extra blob in each subdir is just > one option, you can handle this "extra metadata" in a number of ways > -- maybe external to git, on a separate history will work best. > > The downsides of messing with internal tree handling of git are so > staggering that you'd do better to throw git away. > > (this is from experience of abusing git to various purposes that have > little to do with version control :-) ) > > In other words: Shaun and Dscho are right, so right that it hurts. >
Thanks Martin. I suspect you, Shaun and Dscho are correct. But, can anyone point to specific code that would allow me to see first hand that this is hopeless. So far, based on the code I looked at, I see it as problematic but not hopeless. Here I define "problematic" as having to change a few files and/or avoid using some features while "hopeless" meaning I'd have to change almost very single plumbing command.
Martin LanghoffRe: Supressing sorting of trees
On Mon, Oct 12, 2009 at 10:02 PM, Salvatore Mangano <smangano@into-technology.com> wrote:
> point to specific code
Shaun pointed out some very core code. And it is just a core concept. Just read up on the core organizing concept that is the "tree". Git relies on the layout of the tree being strictly deterministic.
It is a prevalent assumption in the whole codebase.
Yes you can change it, but assume you will have to audit/rewrite 80% of the core code.
Want "proof"? Go change it, then try "make test", or reimport a large repository try to use the git commands over it. We'll relax and watch the fireworks :-)
m
-- martin.langhoff@gmail.com martin@laptop.org -- School Server Architect - ask interesting questions - don't get distracted with shiny stuff - working code first - http://wiki.laptop.org/go/User:Martinlanghoff
Re: Supressing sorting of trees
On Mon, Oct 12, 2009 at 5:51 PM, Sal Mangano <smangano@into-technology.com> wrote:
> 1) I can write by repository from scratch. > 2) I can use Git unchanged but preserve order by storing some information in > each sub tree (e.g. an extra blob) which retains the real order. I can also > store this information once for the whole "chunks" of the repository. > 3) I can change Git to suite my needs understanding that it is not Git > anymore. > > For me, (1) makes no sense at this time. I started with the hope that (2) > would work but realized it is very awkward and will cause performance problems > because it means most updates where ordering matters will have to update the > Git trees and my private ordering blob(s). So, after a quick look at the > source code it seemed like hacking Git into what I wanted was easier than 1 > or 2.
You could add a prefix to the names so you get the order you want. Eg: a-foo b-bar c-baz
If you need to move foo to between bar and baz, you just rename it to ba-foo, etc.
Ealdwulf