{"thread":{"id":"56722","subject":"force deterministic trees on git push - exact sort-order of filenames","startedAt":"2021-10-15T16:05:00Z","lastAt":"2021-10-18T05:38:10Z","messageCount":6,"participants":["milan hauth","René Scharfe","Junio C Hamano","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"438859","messageId":"CAGiEHCtdjA+cVXjN43NPbSZfrDtr-kDtPMN4x_VTGSJuPZ8bcg@mail.gmail.com","threadId":"56722","inReplyTo":null,"subject":"force deterministic trees on git push - exact sort-order of filenames","fromName":"milan hauth","fromEmail":"milahu@gmail.com","sentAt":"2021-10-15T16:04:57Z","receivedAt":"2021-10-15T16:05:00Z","isPatch":false,"sender":{"key":"milahu@gmail.com","avatar":"https://gravatar.com/avatar/68beefdc29b5666a84773ff8094481ddd56ff3d2f997948c05dedb586574afa9?d=mp&s=160"},"body":"fact: the sort-order of filenames in a tree is not strictly regulated\n\nproposal: enforce the exact sort-order of tree-items,\nto make trees deterministic and reproducible.\nthe git server could refuse a 'git push',\nwhen the tree is invalid\n\nuse case: reconstruct a git tree only from files.\n\ncurrent situation:\nblobs are deterministic, trees are non-deterministic\n\nbackward compatibility:\nrewriting git history is usually not desired.\nso this new rule would apply only to new commits\nafter a certain 'deadline', set by the git server\n\n\n\nsample trees from [1] and [2]:\n\ngit cat-file -p 2b75a7dbb76138587dbe50a5a6af8a6eedbaf66b | grep id_ed25519\n100644 blob f914b3f712fc56ab212b53cb9055e1291b5c77a2 id_ed25519\n100644 blob 40de4a8ac6027f64ac85f687bea7049467b428a2 id_ed25519.pub\n\ngit cat-file -p c8a72e628d0ca0a174a1a4241e6c7314a4660f0f | grep example\n100644 blob fde6f3cbd19addb8ce84ffe32ab4d040e8b09c18 example.pem\n040000 tree 6b0ee97865059ac965590e0ff5272fb76b6fd2c8 example\n\n\n\nthe first tree is sorted as expected\n\nprintf 'id_ed25519\\nid_ed25519.pub\\n' | sort\nid_ed25519\nid_ed25519.pub\n\n\n\nthe expected sort-order for the second tree:\n\nprintf 'example.pem\\nexample\\n' | sort\nexample\nexample.pem\n\nthe \"unexpected\" sort-order can be produced with [3]:\n\n```py\nimport functools\ndef cmp(s, t):\n \"\"\"\n Alter lexicographic sort order\n to make longer keys go *before* any of their prefixes\n \"\"\"\n for p, q in zip(s, t):\n if p < q: return -1\n if q < p: return 1\n if len(s) > len(t): return -1\n elif len(t) > len(s): return 1\n return 0\n\narr = [ 'example', 'example.pem' ]\nprint(\"\\n\".join(sorted(arr, key=functools.cmp_to_key(cmp))))\n```\n\nresult:\n\nexample.pem\nexample\n\n\n\n[1] sample tree 1\nhttps://api.github.com/repos/NixOS/nixpkgs/git/trees/2b75a7dbb76138587dbe50a5a6af8a6eedbaf66b\n\n[2] sample tree 2\nhttps://api.github.com/repos/NixOS/nixpkgs/git/trees/c8a72e628d0ca0a174a1a4241e6c7314a4660f0f\n\n[3] python impl of unexpected sort\nhttps://stackoverflow.com/questions/42899405/sort-a-list-with-longest-items-first\n\n[4] related issue (wontfix)\nhttps://github.com/dulwich/dulwich/issues/905\n"},{"id":"438885","messageId":"dab8ce58-fef6-7988-f494-c096e1265aa2@web.de","threadId":"56722","inReplyTo":"CAGiEHCtdjA+cVXjN43NPbSZfrDtr-kDtPMN4x_VTGSJuPZ8bcg@mail.gmail.com","subject":"Re: force deterministic trees on git push - exact sort-order of filenames","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-10-15T17:47:06Z","receivedAt":"2021-10-15T17:47:10Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 15.10.21 um 18:04 schrieb milan hauth:\n> fact: the sort-order of filenames in a tree is not strictly regulated\n\nActually it is.\n\n> proposal: enforce the exact sort-order of tree-items,\n> to make trees deterministic and reproducible.\n\nThat's a good idea. It was implemented in e83c516331 (Initial revision\nof \"git\", the information manager from hell, 2005-04-07), whose README\nsays:\n\n \"A tree object is a list of permission/name/blob data, sorted by name.\n In other words the tree object is uniquely determined by the set\n contents, and so two separate but identical trees will always share\n the exact same object.\"\n\n> the git server could refuse a 'git push',\n> when the tree is invalid\n\nIt should.\n\n> sample trees from [1] and [2]:\n>\n> git cat-file -p 2b75a7dbb76138587dbe50a5a6af8a6eedbaf66b | grep id_ed25519\n> 100644 blob f914b3f712fc56ab212b53cb9055e1291b5c77a2 id_ed25519\n> 100644 blob 40de4a8ac6027f64ac85f687bea7049467b428a2 id_ed25519.pub\n>\n> git cat-file -p c8a72e628d0ca0a174a1a4241e6c7314a4660f0f | grep example\n> 100644 blob fde6f3cbd19addb8ce84ffe32ab4d040e8b09c18 example.pem\n> 040000 tree 6b0ee97865059ac965590e0ff5272fb76b6fd2c8 example\n\nTree entries are sorted by name, except that the names of a sub-trees\n(like \"example\" above) get an implicit slash (/) appended. Slash\n(ASCII character 47) sorts after dot (ASCII character 46).\n\nAre you able to generate and push different trees objects that\nreference the same entries (same names, hashes, modes) in different\norder?\n\nRené\n"},{"id":"438889","messageId":"xmqq1r4m6u84.fsf@gitster.g","threadId":"56722","inReplyTo":"CAGiEHCtdjA+cVXjN43NPbSZfrDtr-kDtPMN4x_VTGSJuPZ8bcg@mail.gmail.com","subject":"Re: force deterministic trees on git push - exact sort-order of filenames","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-15T18:03:39Z","receivedAt":"2021-10-15T18:03:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"milan hauth writes:\n\n> fact: the sort-order of filenames in a tree is not strictly regulated\n\nUntrue, sorry.\n\nThe rule is \"a tree entry that describes a tree object sorts as if\nits pathname component has a trailing slash '/'\". All your sample\ntrees should satisify that rule (or the implementation of Git that\ncreated such a tree is broken).\n\nIn hindsight, if we used the collation order that puts '/' before\nall other bytes when sorting the index entries and the tree entries,\nit would have made a lot of implemenentation details clean and easier\nto work with, but that would have been feasible in early 2005, and\nnot now.\n\n"},{"id":"438892","messageId":"CAGiEHCsY_xQ8RECiX_+HFRrSL509TZEuaq6J2ZejC0Qrsj1p9Q@mail.gmail.com","threadId":"56722","inReplyTo":"xmqq1r4m6u84.fsf@gitster.g","subject":"Re: force deterministic trees on git push - exact sort-order of filenames","fromName":"milan hauth","fromEmail":"milahu@gmail.com","sentAt":"2021-10-15T18:26:42Z","receivedAt":"2021-10-15T18:26:44Z","isPatch":false,"sender":{"key":"milahu@gmail.com","avatar":"https://gravatar.com/avatar/68beefdc29b5666a84773ff8094481ddd56ff3d2f997948c05dedb586574afa9?d=mp&s=160"},"body":"aah!\n\nthanks for clarifying this implementation detail\n\nso git trees are deterministic already.\nthis makes my life much easier : )\n"},{"id":"438970","messageId":"87ilxvd3uw.fsf@evledraar.gmail.com","threadId":"56722","inReplyTo":"CAGiEHCtdjA+cVXjN43NPbSZfrDtr-kDtPMN4x_VTGSJuPZ8bcg@mail.gmail.com","subject":"Re: force deterministic trees on git push - exact sort-order of filenames","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-10-17T16:10:27Z","receivedAt":"2021-10-17T16:16:09Z","isPatch":false,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Oct 15 2021, milan hauth wrote:\n\n> backward compatibility:\n> rewriting git history is usually not desired.\n> so this new rule would apply only to new commits\n> after a certain 'deadline', set by the git server\n\nOthers have commented on the status quo, but just on this: \"git fsck\"\nwill report these, and if it doesn't that's a bug. Grep for\n\"TREE_NOT_SORTED\" in git.git for the code.\n\nBut in general this sort of plan for disallowing \"bad\" data doesn't\nreally work all that well. People want to e.g. switch hosting providers,\nand will need to re-push old bad data with a new push.\n\nI suppose there could be more strictures in the fsck code to allow for\nthat use-case, but still make some things that are mere warnings now\nhard errors (or \"fatal\").\n\nE.g. allowing it based on a more thorough inspection of the history, or\ntreat commits differently if their envelope timestamp is past some\ncut-off (which right now we don't care about).\n\nFor a self-hosted installation with some specific old bad data I was\nalso able to turn on tighter strictures and whitelist specific OIDs with\nfsck.skipList, I don't know if any of the big providers use that.\n"},{"id":"438979","messageId":"xmqq7deazydf.fsf@gitster.g","threadId":"56722","inReplyTo":"87ilxvd3uw.fsf@evledraar.gmail.com","subject":"Re: force deterministic trees on git push - exact sort-order of filenames","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-10-18T05:38:04Z","receivedAt":"2021-10-18T05:38:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n\n> I suppose there could be more strictures in the fsck code to allow for\n> that use-case, but still make some things that are mere warnings now\n> hard errors (or \"fatal\").\n\nThere is a group of configuration variables fsck.* to let you pass\nspecific types of errors go without erroring out on them, and also\nfsck.skiplist lets you ignore errors on specific objects, but both\nneed to ask people on the other side to flip them on.\n\nI'd imagine that hosting providers can make it self-service for\nrepository owners, though, but if they employ shared object store\nacross repositories, it might become a bit cumbersome to implement\ncorrectly.\n"}]}