{"thread":{"id":"30183","subject":"In tree object, Must the","startedAt":"2012-04-08T03:43:56Z","lastAt":"2012-04-09T21:03:06Z","messageCount":7,"participants":["Yi, EungJun","Carlos Martín Nieto","Junio C Hamano","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"188754","messageId":"CAFT+Tg-+s5=pFNwY7ZMxem4z6YHu53kyOs0B_rkmphq=mEtpTg@mail.gmail.com","threadId":"30183","inReplyTo":null,"subject":"In tree object, Must the","fromName":"Yi, EungJun","fromEmail":"semtlenori@gmail.com","sentAt":"2012-04-08T03:43:56Z","receivedAt":"2012-04-08T03:43:56Z","isPatch":false,"sender":{"key":"semtlenori@gmail.com","avatar":"https://gravatar.com/avatar/8363435d2badb3450df0dd7c4ec2113f6e1d62c44dd3cf7dfe83c5a389b8a9bf?d=mp&s=160"},"body":"Hello,\n\nI'm implementing Git using node.js, and I have a question while I\nwrite some code to store tree object.\n\nTree object looks a table consists of three fields: blob's mode, name\nand id, as below.\n\ne.g.)\n$ git cat-file -p 45799547\n100644 blob cd242b1e5bb403500feb49a1aa656c21c6c0be69\tMakefile\n100644 blob bf382321749577d52bd2fbf2281df0510b4bad31\tREADME.md\n100644 blob 5441bb48428611a3cb140d8192d39484fcf3b742\tfsutil.js\n100644 blob 0af680a5c0dd4482b09aa7f8e837234bed0b7cfa\tpackage.json\n040000 tree 39a4d45669addfb1e8f0a499deebc5b97b4edfa0\ttest\n\nIt seems that the table is stored in order by blob's name.\n\nIf it is true, what happens if it is not ordered?\n\nDoes that cause any troubles to users to use a git repository created\nand managed by my Git implementation?\n"},{"id":"188778","messageId":"1333891217.7419.5.camel@centaur.lab.cmartin.tk","threadId":"30183","inReplyTo":"CAFT+Tg-+s5=pFNwY7ZMxem4z6YHu53kyOs0B_rkmphq=mEtpTg@mail.gmail.com","subject":"Re: In tree object, Must the","fromName":"Carlos Martín Nieto","fromEmail":"cmn@elego.de","sentAt":"2012-04-08T13:20:17Z","receivedAt":"2012-04-08T13:20:17Z","isPatch":false,"sender":{"key":"cmn@elego.de","avatar":"https://avatars.githubusercontent.com/u/335443?v=4"},"body":"On Sun, 2012-04-08 at 12:43 +0900, Yi, EungJun wrote:\n> Hello,\n> \n> I'm implementing Git using node.js, and I have a question while I\n> write some code to store tree object.\n> \n> Tree object looks a table consists of three fields: blob's mode, name\n> and id, as below.\n> \n> e.g.)\n> $ git cat-file -p 45799547\n> 100644 blob cd242b1e5bb403500feb49a1aa656c21c6c0be69\tMakefile\n> 100644 blob bf382321749577d52bd2fbf2281df0510b4bad31\tREADME.md\n> 100644 blob 5441bb48428611a3cb140d8192d39484fcf3b742\tfsutil.js\n> 100644 blob 0af680a5c0dd4482b09aa7f8e837234bed0b7cfa\tpackage.json\n> 040000 tree 39a4d45669addfb1e8f0a499deebc5b97b4edfa0\ttest\n> \n> It seems that the table is stored in order by blob's name.\n\nYes, the entries in the tree are alpha-sorted. The exception are trees,\nwhere you have to pretend that there is a trailing slash. In other\nwords, the order is the same as you'd see in the index (as there, the\ntest/ directory in your example would be stored with a slash and the\nname of the subdirs and files in it.\n\n> \n> If it is true, what happens if it is not ordered?\n\nfsck complains for one.\n\n> \n> Does that cause any troubles to users to use a git repository created\n> and managed by my Git implementation?\n\nHow does your implementation store things? You haven't said (maybe\nhinted that you may be writing trees with the wrong order). Depending on\nthe particular implementation of whatever is reading the git repository,\nit might not be able to find an entry in your tree, as it's wrongly\nsorted, but that depends on the exact implementation and possibly luck.\n\nDo you need to write this in pure js? There are some bindings for\nnode.js[0] already for libgit2 so you don't need to redo the low-level\nwork.\n\nCheers,\n cmn\n\n[0] https://github.com/libgit2/node-gitteh\n\n"},{"id":"188784","messageId":"CAFT+Tg8K9H4hnjJcXBtM931MpeRDC8V1OV-uns1F9+sAWwf8VQ@mail.gmail.com","threadId":"30183","inReplyTo":"1333891217.7419.5.camel@centaur.lab.cmartin.tk","subject":"Re: In tree object, Must the","fromName":"Yi, EungJun","fromEmail":"semtlenori@gmail.com","sentAt":"2012-04-08T15:22:59Z","receivedAt":"2012-04-08T15:22:59Z","isPatch":false,"sender":{"key":"semtlenori@gmail.com","avatar":"https://gravatar.com/avatar/8363435d2badb3450df0dd7c4ec2113f6e1d62c44dd3cf7dfe83c5a389b8a9bf?d=mp&s=160"},"body":"You are right. I tried to clone a repository which has a unordered\ntree object and all you said happened, as below.\n\n$ git ls-tree HEAD\n100644 blob a6ccb8dec6b21e9d3e0b716d3a0915262a8c4474\tb\n100644 blob a3df8f3749f855a2d905d92f11590a9c18a1bcbb\ta\n100644 blob 424907d3fe9f1fa4b2e3a0bb65ab99780d9acfba\tc\n$ git show -- b\n$ git show -- a\n$ git fsck\nerror in tree 3f5a56e992a01f2e500bed57360f3961323b9d6e: not properly sorted\nerror in tree a94e7dc2820eb4d0ef308fac1a32b3715e82dc76: not properly sorted\n\nI want to allow users to clone the git repository created by my implementation,\nbut before I have to sort tree objects. Thanks to you, I know that now.\n\nAnd your suggestion to use node-gitteh is also thankful,\nbut I want pure js implementation without libgit2.\n\n2012년 4월 8일 오후 10:20, Carlos Martín Nieto 님의 말:\n> On Sun, 2012-04-08 at 12:43 +0900, Yi, EungJun wrote:\n>> Hello,\n>>\n>> I'm implementing Git using node.js, and I have a question while I\n>> write some code to store tree object.\n>>\n>> Tree object looks a table consists of three fields: blob's mode, name\n>> and id, as below.\n>>\n>> e.g.)\n>> $ git cat-file -p 45799547\n>> 100644 blob cd242b1e5bb403500feb49a1aa656c21c6c0be69  Makefile\n>> 100644 blob bf382321749577d52bd2fbf2281df0510b4bad31  README.md\n>> 100644 blob 5441bb48428611a3cb140d8192d39484fcf3b742  fsutil.js\n>> 100644 blob 0af680a5c0dd4482b09aa7f8e837234bed0b7cfa  package.json\n>> 040000 tree 39a4d45669addfb1e8f0a499deebc5b97b4edfa0  test\n>>\n>> It seems that the table is stored in order by blob's name.\n>\n> Yes, the entries in the tree are alpha-sorted. The exception are trees,\n> where you have to pretend that there is a trailing slash. In other\n> words, the order is the same as you'd see in the index (as there, the\n> test/ directory in your example would be stored with a slash and the\n> name of the subdirs and files in it.\n>\n>>\n>> If it is true, what happens if it is not ordered?\n>\n> fsck complains for one.\n>\n>>\n>> Does that cause any troubles to users to use a git repository created\n>> and managed by my Git implementation?\n>\n> How does your implementation store things? You haven't said (maybe\n> hinted that you may be writing trees with the wrong order). Depending on\n> the particular implementation of whatever is reading the git repository,\n> it might not be able to find an entry in your tree, as it's wrongly\n> sorted, but that depends on the exact implementation and possibly luck.\n>\n> Do you need to write this in pure js? There are some bindings for\n> node.js[0] already for libgit2 so you don't need to redo the low-level\n> work.\n>\n> Cheers,\n>   cmn\n>\n> [0] https://github.com/libgit2/node-gitteh\n>\n"},{"id":"188801","messageId":"7vobr0wyml.fsf@alter.siamese.dyndns.org","threadId":"30183","inReplyTo":"CAFT+Tg-+s5=pFNwY7ZMxem4z6YHu53kyOs0B_rkmphq=mEtpTg@mail.gmail.com","subject":"Re: In tree object, Must the","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-09T18:25:54Z","receivedAt":"2012-04-09T18:25:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Yi, EungJun\" writes:\n\n> If it is true, what happens if it is not ordered?\n\n\"git diff-tree\" and \"git diff-index\" (hence \"git diff\" frontend when it\nwalks the tree for comparison) will fail.\n"},{"id":"188803","messageId":"CAJo=hJv==GrxLH6U9MAwckcEXiYtKeMEpEMNVTJLcSKro2QV_w@mail.gmail.com","threadId":"30183","inReplyTo":"7vobr0wyml.fsf@alter.siamese.dyndns.org","subject":"Re: In tree object, Must the","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-09T18:29:46Z","receivedAt":"2012-04-09T18:29:46Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Apr 9, 2012 at 11:25, Junio C Hamano wrote:\n> \"Yi, EungJun\" writes:\n>\n>> If it is true, what happens if it is not ordered?\n>\n> \"git diff-tree\" and \"git diff-index\" (hence \"git diff\" frontend when it\n> walks the tree for comparison) will fail.\n\nAnd JGit and any JGit derived tool (e.g. EGit, Gerrit Code Review)\nwill fail horribly and refuse to process that tree, or worse, will\nproduce incorrect results when fed garbage like an unsorted or\nincorrectly sorted tree.\n\nTree ordering matters. And that niggly bit about subtrees sorting as\nthough their names end in '/' even though they don't really matters.\n"},{"id":"188815","messageId":"7vhawsvffn.fsf@alter.siamese.dyndns.org","threadId":"30183","inReplyTo":"CAJo=hJv==GrxLH6U9MAwckcEXiYtKeMEpEMNVTJLcSKro2QV_w@mail.gmail.com","subject":"Re: In tree object, Must the","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-04-09T20:05:48Z","receivedAt":"2012-04-09T20:05:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> ... And that niggly bit about subtrees sorting as\n> though their names end in '/' even though they don't really matters.\n\nYeah, in older and buggier unpack-trees it might have made the code\nsimpler while walking the index and the tree in parallel, but when we have\nto deal with D/F conflicts, we have to find a entry with matching name\nanyway, so it turned out not to be a win at all.\n"},{"id":"188818","messageId":"CAJo=hJsh6DyUA3gV1Yiho5bwCdi99aMkBHepy-VVnFwJPeWYOg@mail.gmail.com","threadId":"30183","inReplyTo":"7vhawsvffn.fsf@alter.siamese.dyndns.org","subject":"Re: In tree object, Must the","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-09T21:03:06Z","receivedAt":"2012-04-09T21:03:06Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Apr 9, 2012 at 13:05, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>> ... And that niggly bit about subtrees sorting as\n>> though their names end in '/' even though they don't really matters.\n>\n> Yeah, in older and buggier unpack-trees it might have made the code\n> simpler while walking the index and the tree in parallel, but when we have\n> to deal with D/F conflicts, we have to find a entry with matching name\n> anyway, so it turned out not to be a win at all.\n\nJGit still waks the trees in parallel. We handle the D/F conflict\nstuff using a small amount of look-ahead and sometimes rescan back\nfrom the start. In practice that works out really well, it catches\nmost forms of D/F conflict with little overhead, and almost no\noverhead when there is no D/F conflict, which is common.\n"}]}