{"thread":{"id":"64230","subject":"[RFC PATCH 0/1] Extended tree format for mixed submodules and conflicts","startedAt":"2025-10-01T00:58:21Z","lastAt":"2025-10-01T23:00:44Z","messageCount":10,"participants":["brian m. carlson","Junio C Hamano","Jeff King","Elijah Newren"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"527668","messageId":"20251001005814.846992-1-sandals@crustytoothpaste.net","threadId":"64230","inReplyTo":null,"subject":"[RFC PATCH 0/1] Extended tree format for mixed submodules and conflicts","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-10-01T00:58:13Z","receivedAt":"2025-10-01T00:58:21Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"Today at the Contributor Summit we discussed two different proposals\nthat might benefit from some extensions to trees: submodules of a\ndifferent hash algorithm and first-class conflicts.\n\nPeff suggested that we could do something hideous to the tree format to\nallow for extensions to submodules of different algorithms.  In the\ninterests of prototyping things to see how much people like or hate the\nidea, I've written up an example spec and included a script below so we\ncan see how current Git implementations handle this.  (This was part of\nmy lunchtime activity.)\n\nGit itself handles this data as a submodule, which seems to be the least\nbad option for a new mode type.  `git fsck` complains about the mode, as\nexpected.\n\nI don't intend to actually implement this proposal or do anything\nserious with it, but I offer it as a discussion piece about what we\ncould do if we wanted in a minimally incompatible way.  If you really\nhate it, that's okay; I agree it's a little gross.\n\n----\n#!/bin/sh -e\n\n# This script requires a printf that supports hex escapes because I'm too lazy\n# to convert things into octal.\n\nrm -fr test-repo\ngit init --object-format=sha1 -b dev test-repo\ncd test-repo\ntree_oid=$(/usr/bin/printf '130000 \\x91\\x82\\x80s256\\x01\\xdf\\xac\\xbf\\xee\\xdf\\xac\\xbf\\xee\\xdf\\xac\\xbf\\xeesubmodule\\x00\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef' | git hash-object -t tree -w --literally --stdin)\ncommit_oid=$(git commit-tree -m + \"$tree_oid\")\ngit reset --hard \"$commit_oid\"\ngit show HEAD\n----\n\nbrian m. carlson (1):\n  Define an extended tree format\n\n Documentation/Makefile                     |  1 +\n Documentation/gitformat-extended-tree.adoc | 77 ++++++++++++++++++++++\n Documentation/meson.build                  |  1 +\n 3 files changed, 79 insertions(+)\n create mode 100644 Documentation/gitformat-extended-tree.adoc\n\n"},{"id":"527669","messageId":"20251001005814.846992-2-sandals@crustytoothpaste.net","threadId":"64230","inReplyTo":"20251001005814.846992-1-sandals@crustytoothpaste.net","subject":"[RFC PATCH 1/1] Define an extended tree format","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-10-01T00:58:14Z","receivedAt":"2025-10-01T00:58:21Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"There are some cases in which we want to encode additional information\nin a tree but there is currently no possible way to do so.  Define a\nformat for extended trees that uses mode 130000 plus some additional\nnonzero bytes in the file name to encode additional data in a mostly\nbackwards compatible way.\n\nSigned-off-by: brian m. carlson <sandals@crustytoothpaste.net>\n---\n Documentation/Makefile                     |  1 +\n Documentation/gitformat-extended-tree.adoc | 77 ++++++++++++++++++++++\n Documentation/meson.build                  |  1 +\n 3 files changed, 79 insertions(+)\n create mode 100644 Documentation/gitformat-extended-tree.adoc\n\ndiff --git a/Documentation/Makefile b/Documentation/Makefile\nindex 6fb83d0c6e..6d8ad220ed 100644\n--- a/Documentation/Makefile\n+++ b/Documentation/Makefile\n@@ -33,6 +33,7 @@ MAN5_TXT += gitattributes.adoc\n MAN5_TXT += gitformat-bundle.adoc\n MAN5_TXT += gitformat-chunk.adoc\n MAN5_TXT += gitformat-commit-graph.adoc\n+MAN5_TXT += gitformat-extended-tree.adoc\n MAN5_TXT += gitformat-index.adoc\n MAN5_TXT += gitformat-pack.adoc\n MAN5_TXT += gitformat-signature.adoc\ndiff --git a/Documentation/gitformat-extended-tree.adoc b/Documentation/gitformat-extended-tree.adoc\nnew file mode 100644\nindex 0000000000..fc28bb16c9\n--- /dev/null\n+++ b/Documentation/gitformat-extended-tree.adoc\n@@ -0,0 +1,77 @@\n+Extended Tree Format\n+====================\n+\n+Rationale\n+---------\n+\n+Git needs to store some additional types of data in repositories that we had\n+previously not considered.  Unfortunately, we lack a good way to extend tree\n+formats in a backwards compatible way.\n+\n+This document proposes an approach that adds an extended tree format that is\n+backwards compatible with earlier versions of Git except that it will appear\n+that the tree is improperly sorted.  This is done by encoding additional bytes\n+that are guaranteed to be nonzero and that earlier versions of Git will\n+consider part of the file name.\n+\n+Format\n+------\n+:ber: footnote:[This is the format used by the `w` pack format in Perl and Ruby.]\n+\n+An extended tree format consists of an entry that has mode 130000.\n+\n+A modified BER-encoded integer is a BER-encoded integer{ber} with the top bits\n+of each byte flipped.  That is, values 0x00 through 0x7f are encoded as 0x80\n+through 0xff, and larger values are encoded such that the bottom 7 bits of each\n+byte include the value and the top bit is 0 if there is a subsequent byte of\n+data and 1 if this is the last byte.  The shortest possible encoding must be\n+used.  Note that the byte 0x00 is not valid in the encoded value.\n+\n+The first part of what is traditionally the file name consists of a modified\n+BER-encoded integer representing the number of bytes in the extended\n+information section not including this length itself; that is, the number of\n+bytes which must be skipped to reach the file name.  This allows parsing\n+unknown values in a graceful way.\n+\n+Following that is a modified BER-encoded integer representing the type of\n+object and a modified BER-encoded integer consisting of flags.\n+\n+The object type is one of the following:\n+\n+0:: invalid\n+1:: conflict tree (only valid at top level)\n+2:: extended submodule\n+\n+The following flags are defined:\n+\n+1 (bit 0):: This entry is critical and failure to handle this object should be fatal.\n+2 (bit 1):: Flags in this entry are critical and failure to understand them should be fatal.\n+\n+A conflict tree then has a modified BER-encoded integer representing the stage.\n+\n+Conflict trees are used to store a conflicted state.  The top-level tree\n+contains only entries called stageN, where N is a decimal representation of the\n+stage integer.  Resolved entries are always stored as stage 0.  The contents of\n+each tree are those of the root tree at that stage.\n+\n+An extended submodule then has a 32-bit format ID representing the algorithm in\n+question, followed by a nonzero byte called an offset.  If the object ID for\n+the selected algorithm is longer than the algorithm for the tree, the remaining\n+bytes of the object ID are encoded such that each one is XORed with the offset.\n+The offset must be the smallest nonzero byte value such that all of the encoded\n+bytes are also nonzero; an entry is malformed if this value is incorrect.\n+\n+If the object ID for the selected algorithm is shorter than the algorithm for\n+the tree, the main object ID field is padded with zeros.\n+\n+Examples\n+--------\n+\n+An extended submodule of a SHA-256 submodule in a SHA-1 repository might look\n+like this if the submodule object name is\n+deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef and the name\n+is `submodule`:\n+\n+----\n+130000 \\x91\\x82\\x80s256\\x01\\xdf\\xac\\xbf\\xee\\xdf\\xac\\xbf\\xee\\xdf\\xac\\xbf\\xeesubmodule\\x00\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\\xde\\xad\\xbe\\xef\n+----\ndiff --git a/Documentation/meson.build b/Documentation/meson.build\nindex e34965c5b0..e2257050e8 100644\n--- a/Documentation/meson.build\n+++ b/Documentation/meson.build\n@@ -172,6 +172,7 @@ manpages = {\n   'gitformat-bundle.adoc' : 5,\n   'gitformat-chunk.adoc' : 5,\n   'gitformat-commit-graph.adoc' : 5,\n+  'gitformat-extended-tree.adoc' : 5,\n   'gitformat-index.adoc' : 5,\n   'gitformat-pack.adoc' : 5,\n   'gitformat-signature.adoc' : 5,\n"},{"id":"527702","messageId":"xmqqldlu37ej.fsf@gitster.g","threadId":"64230","inReplyTo":"20251001005814.846992-2-sandals@crustytoothpaste.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-10-01T16:37:24Z","receivedAt":"2025-10-01T16:37:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n\n> +The first part of what is traditionally the file name consists of a modified\n> +BER-encoded integer representing the number of bytes in the extended\n> +information section not including this length itself; that is, the number of\n> +bytes which must be skipped to reach the file name.  This allows parsing\n> +unknown values in a graceful way.\n\nIn short, you prepend extra bytes that contain no NUL in front of\nthe pathname part of the tree entry, but that extra bytes begins\nwith the length to allow skipping.  \n\nThe tree entries must be in sorted order, but I presume that this\nextra information merely happens to be encoded inside pathname\nfield, but does not contribute to the ordering of the entries?\n\nFor debuggability, I am not sure if modified BER is the best format\n(it is essentially binary gibberish).\n\nFor extensibility, I wonder if we should allow more than (type,\nflags) to be given in the future?  I guess a new <type> will allow\nextra things after <flags> (like conflict tree takes stage number),\nso the format is already extensible (we do not want to see people\nwilly-nilly add extended stuff to the tree object anyway, since it\nwould allow the logically same object represented by multiple byte\nstreams that are not bit-for-bit identical, so extensibility is a\ndouble-edged sword, but still necessary).\n\nWhen we have more than one stage #1 entries (can happen in a\ncriss-cross merge) or multiple stage #3 entries (octopus), what sort\norder do we apply to them for conflict tree entries?\n\nAs you said, it does look ugly ;-)\n"},{"id":"527709","messageId":"20251001174110.GA137600@peff.net","threadId":"64230","inReplyTo":"20251001005814.846992-2-sandals@crustytoothpaste.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-01T17:41:10Z","receivedAt":"2025-10-01T17:41:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 01, 2025 at 12:58:14AM +0000, brian m. carlson wrote:\n\n> There are some cases in which we want to encode additional information\n> in a tree but there is currently no possible way to do so.  Define a\n> format for extended trees that uses mode 130000 plus some additional\n> nonzero bytes in the file name to encode additional data in a mostly\n> backwards compatible way.\n\nThanks for writing this up. This was along the lines I was thinking, but\nI have a few variant suggestions to consider.\n\nYour proposal here covers a very general extension format which can be\nused for solving several possible problems. But if we constrain\nourselves just to the gitlink question, it does open up some more\npossibilities. Here you're using a custom mode to mark the entry, and\nthe downside is that the mode will be somewhat confusing to old versions\nof Git. They won't recognize a gitlink as such, and their fsck will\ncomplain about it. It also leaves the question of what goes into the\nhash/object-id field of the entry. We can't represent the true hash\n(that is the whole problem we are trying to solve). You could put in the\nnull sha1, but that is another fsck landmine. So probably we have some\ndummy hash. But old versions, not knowing it's a submodule, will expect\nthat hash to be reachable and will complain that it's missing!\n\nWhat if instead, we leave the mode as S_IFGITLINK, but use a dummy hash\nto recognize the extended submodule? Let's say 0000...1. We risk\ncolliding with a real hash, but the chances are quite unlikely, and it's\na risk we already take with the null oid. With this scheme, the old\nversions will still realize it's a submodule, and that we do not need to\nhave access to that hash. If an old version checks it out without\nsubmodule recursion, we'll never even try to access that hash. And if it\ndoes, it will try to clone the appropriate gitmodule and say \"oops, we\ndon't have that hash\". Which is probably the best outcome we can hope\nfor.\n\nThe obvious downside is that this does nothing to help the\nstored-conflict case. _If_ we are going to come up with a solution for\nthat, I agree it might make sense to piggy-back on it for submodules.\nBut I do think what I outlined above degrades a bit more gracefully. And\nthe compatibility scenarios for these two use cases may be different.\nAlternate-hash submodule entries will be buried in old history and seen\nmany people. Conflict markers are probably shorter-lived and less likely\nto be seen by people who aren't using modern versions of Git to work\nwith them.\n\n\nThe other way in which your proposal differs from what I was thinking is\nin the use of BER in the filename. It is nice that it can unambiguously\nencode a chunk of data, but the fact that it contains binary bytes makes\nme worried about a few things:\n\n  1. When users see it, does it look like junk? It is nice, IMHO, if the\n     name does leak out to the user for it to be a bit more\n     self-explanatory.\n\n  2. When a filesystem sees it, can it handle it? I didn't think hard on\n     it, but I'd guess BER generally isn't valid UTF-8. What will HFS+\n     do with such a filename?\n\n  3. To what degree can BER encoded bytes conflict with meaningful\n     path names? In particular I wonder if \"/\" can appear, which will\n     cause confusion (both in git-fsck, but also when we try to work in\n     a directory that does not exist). Or worse, if you can sneak\n     \".git/\" into a name in a way that is interpreted by _some_ versions\n     of Git but not others.\n\nSo I was thinking instead of something more ASCII-ish. Something like\n\"<link_type>-<link_data>-<pathname>\". So in a sha256 tree, an entry for\na sha1 submodule might look like (as shown by ls-tree):\n\n  160000 00000000000000000000000000000001 sha1-12345abcde12345abcde12345abcde12345abcde-the-real-path\n\nThe sentinel sha256 oid \"000...1\" would be binary in the tree, of\ncourse, but the sha1 in the filename would be hex. It's not as\nefficient, but I don't think that submodules are common enough for this\nto be a real issue.\n\nI was vague about \"link_data\" above. But I think if it is interpreted in\na manner specific to link_type, then this scheme could also eventually\nenable non-git submodules. E.g., for the true masochist, you could\nimagine svn-<url>-foo (with <url> percent-encoded to avoid dashes and\nslashes). I'm not sure if anyone would ever find that useful, and it's\nnot something I'd plan to look into myself, but maybe it's a bonus?\n\n\nThe other issue of concern is sorting. If sha1-...-foo sorts as \"foo\",\nthen older versions will complain the tree is wrongly sorted. And\nprobably will produce slightly wrong diffs. I think modern Git would\nJust Work in most spots, though, provided the handling is done in\ndecode_tree_entry() or similar.\n\nSorting the other way, as \"sha1-\", is mostly going to be a nightmare for\nmodern Git. If we want it to truly show \"foo\" in a diff, for example, it\nwould have to scan forward for any instance of \"sha1-...-aaa\" before\nshowing \"aab\". Yuck.\n\nBut what if we accepted that these entries were a bit more user-visible?\nThat is, the diff itself would not do anything special at all, and you\nreally would get a delete/add for:\n\n  -sha1-12345abcde12345abcde12345abcde12345abcde-foo\n  +sha1-67890fedcb67890fedcb67890fedcb67890fedcb-foo\n\ninstead of the more correct path-changing diff. And then either we\naccept that ugliness, or we fix up the diff for display via diffcore or\nsimilar (dropping those ugly entries and replacing them with a single\ndiff_filepair of \"foo\").\n\nAnd likewise the submodule code would leave these ugly entries until the\nmoment it is ready to act on them, when it would realize that we want to\ntouch \"foo\" in the checkout (and both here and in a diff, obviously it\nis an error if there is a \"foo\" already, but that is true already for\nany tree with duplicate entries).\n\nMy gut feeling is that would keep the gross-ness confined to a few bits\nof code, and you could still operate on these natively with tools like\nmktree, ls-tree, and so on. The ugly names will leak out to the user\nsometimes, but most porcelain flows would do the right thing.\n\n-Peff\n"},{"id":"527726","messageId":"20251001211140.GA140550@peff.net","threadId":"64230","inReplyTo":"20251001174110.GA137600@peff.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-01T21:11:40Z","receivedAt":"2025-10-01T21:11:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 01, 2025 at 01:41:10PM -0400, Jeff King wrote:\n\n> My gut feeling is that would keep the gross-ness confined to a few bits\n> of code, and you could still operate on these natively with tools like\n> mktree, ls-tree, and so on. The ugly names will leak out to the user\n> sometimes, but most porcelain flows would do the right thing.\n\nI was hoping make a proof-of-concept patch to get more familiar with\nexactly what it would look like for various commands. So the scenario I\ncame up with was this:\n\n-- >8 --\n#!/bin/sh\n\n# you can have a sha256 module in a sha1 repo or vice versa\nsup_algo=$1; shift\nsub_algo=$1; shift\n\nrm -rf sub super clone\n\n# a boring sub-project with one commit\ngit init --object-format=$sub_algo sub &&\n(\n\tcd sub &&\n\techo content >file &&\n\tgit add file &&\n\tgit commit -m msg\n) &&\n\n# the superproject includes it\ngit init --object-format=$sup_algo super &&\n(\n\tcd super &&\n\tgit -c protocol.file.allow=always submodule add \"$PWD/../sub\" foo &&\n\tgit commit -m 'add sub'\n) &&\n\n# and then in theory we can clone it and check out the submodule\ngit -c protocol.file.allow=always clone --recurse-submodules super clone\n-- >8 --\n\nBut there were two unexpected bits. The first is that the above doesn't\njust need a way to store the foreign-hash oid in a tree. It needs to be\nin the index, too.\n\nWe could perhaps use the same hackery there, storing sha1-...-foo in the\nindex with the sentinel hash. Or perhaps we could extend the index to\nsupport holding foreign hashes. I'm not sure which would be less\nannoying. If the index and trees don't match, then tree-to-index\ncomparisons get weird. If the index and filesystem don't match, then\nindex to filesystem comparisons get weird. My gut feeling is that making\nindex-to-filesystem comparisons weird (so putting the hacked name into\nthe index) is probably going to be better, just because the filesystem\nis already out of our control. So we can do sorted comparisons between\nthe index and trees, but filesystem operations are inherently asking\nabout paths one by one. But I'd have to dig deeper to get more confident\nin that opinion.\n\nThe other unexpected thing is that the sequence above works today! I\nthink it is mostly accidental, though. When we read the head of the\nsubmodule, we get a \"struct object_id\" with a different algo field. But\nwe never pay attention to that field, and just treat it as if it is\nusing our native algorithm.\n\nSo if I use a sha256 submodule in a sha1 repo, the final part of the\noutput (in the recursive clone) looks like this:\n\n  Submodule path 'foo': checked out 'db8b8f8006f4564e7862b246c4d57100790e2196'\n\nWe've truncated the sha256 to 20 bytes (40 hex) and used that instead of\nthe full oid. But Git is flexible enough that it is happy to find the\nobject by its abbreviated hash, and checks it out without complaining.\n\nIf we go the other way, with a sha1 submodule in a sha256 repo, we get\nthis final line:\n\n  Submodule path 'foo': checked out '03f08992d562b03e2af5b4256e17b82be8eafa98000000000000000000000000'\n\nI expected to get random garbage at the end, since we only copied in the\nfirst 20 bytes, but since c98d762ed9 (global: ensure that object IDs are\nalways padded, 2024-06-14) we zero-pad all oids. The intent there was\nmaking internal comparisons fast, but it happens to help us out here. I\nam a little puzzled that Git is willing to check out the zero-padded\nname, but I wonder if we simply parse it into an object_id struct and\nthen only look at the first algo->raw_size bytes.\n\nSo it all works as expected, but I feel like it's mostly by accident. My\ngut feeling is that we probably wanted something like this to protect us\nfrom confusion:\n\nindex 06ad74db22..295b0c6318 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -719,6 +719,8 @@ int add_to_index(struct index_state *istate, const char *path, struct stat *st,\n \tif (S_ISDIR(st_mode)) {\n \t\tif (repo_resolve_gitlink_ref(the_repository, path, \"HEAD\", &oid) < 0)\n \t\t\treturn error(_(\"'%s' does not have a commit checked out\"), path);\n+\t\tif (oid.algo != hash_algo_by_ptr(the_repository->hash_algo))\n+\t\t\treturn error(_(\"object format %s of '%s' is incompatible with this repository (%s)\"), hash_algos[oid.algo].name, path, the_repository->hash_algo->name);\n \t\twhile (namelen && path[namelen-1] == '/')\n \t\t\tnamelen--;\n \t}\n\nOf course that is strictly worse for somebody who is relying on the\ncurrent accidental behavior. ;) And in the long run, I think this is the\nspot we'd want to hook to do whatever massaging we need (whether\nconverting to the equivalent in-repo algorithm, or hacking up the name\nto store the foreign hash).\n\nI also won't be at all surprised if you've run across this already in\nyour interop work.\n\n-Peff\n"},{"id":"527728","messageId":"xmqqy0puz5f6.fsf@gitster.g","threadId":"64230","inReplyTo":"20251001211140.GA140550@peff.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-10-01T21:19:09Z","receivedAt":"2025-10-01T21:19:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The other unexpected thing is that the sequence above works today! I\n> think it is mostly accidental, though. When we read the head of the\n> submodule, we get a \"struct object_id\" with a different algo field. But\n> we never pay attention to that field, and just treat it as if it is\n> using our native algorithm.\n\nYeah, I recall that there was a discussion about this exact \"yes, we\nget by fine with SHA-1 commit object name 0-padded to the right,\nwhen embedding SHA-1 submodule inside SHA-256 superproject\",\ncountered by brian's \"no, it may happen to work but you shouldn't\nrely on it\" recently.\n\n> So it all works as expected, but I feel like it's mostly by accident. My\n> gut feeling is that we probably wanted something like this to protect us\n> from confusion:\n>\n> index 06ad74db22..295b0c6318 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -719,6 +719,8 @@ int add_to_index(struct index_state *istate, const char *path, struct stat *st,\n>  \tif (S_ISDIR(st_mode)) {\n>  \t\tif (repo_resolve_gitlink_ref(the_repository, path, \"HEAD\", &oid) < 0)\n>  \t\t\treturn error(_(\"'%s' does not have a commit checked out\"), path);\n> +\t\tif (oid.algo != hash_algo_by_ptr(the_repository->hash_algo))\n> +\t\t\treturn error(_(\"object format %s of '%s' is incompatible with this repository (%s)\"), hash_algos[oid.algo].name, path, the_repository->hash_algo->name);\n>  \t\twhile (namelen && path[namelen-1] == '/')\n>  \t\t\tnamelen--;\n>  \t}\n>\n> Of course that is strictly worse for somebody who is relying on the\n> current accidental behavior. ;) And in the long run, I think this is the\n> spot we'd want to hook to do whatever massaging we need (whether\n> converting to the equivalent in-repo algorithm, or hacking up the name\n> to store the foreign hash).\n>\n> I also won't be at all surprised if you've run across this already in\n> your interop work.\n\n"},{"id":"527729","messageId":"CABPp-BEAawZgDz+bBizUVz1=9XHE_g3vWGV17JooUes=JSmkwA@mail.gmail.com","threadId":"64230","inReplyTo":"20251001005814.846992-2-sandals@crustytoothpaste.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-10-01T21:21:45Z","receivedAt":"2025-10-01T21:21:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Sep 30, 2025 at 5:58 PM brian m. carlson\n<sandals@crustytoothpaste.net> wrote:\n>\n> +Following that is a modified BER-encoded integer representing the type of\n> +object and a modified BER-encoded integer consisting of flags.\n> +\n> +The object type is one of the following:\n> +\n> +0:: invalid\n> +1:: conflict tree (only valid at top level)\n\nI think there may have been some miscommunication.  There was\ndiscussion around \"at the toplevel\" and \"trees,\" but I believe \"at the\ntoplevel\" was meant to refer to the commit itself -- specifically, for\neach commit, at the highest level of the objects it references (i.e.,\nthe commit object).  The idea is that conflict information would be\nrepresented by multiple traditional toplevel trees (or possibly even\ncommits?) recorded in the commit object, with no conflicts recorded\nwithin any individual tree.  Instead, the existence of multiple\ndistinct toplevel trees is what would signal a conflict.\n\nRecording conflict information in trees rather than commits, as this\nproposal suggests (even if only at the toplevel tree), introduces a\nproblem similar to what Martin mentioned yesterday regarding blobs.\nIn particular, doing so would require every `git log` operation --\nwhich wants to determine if a commit is conflicted so it can highlight\nit for users -- to walk not only the commits but also additional\nobjects.  Even if limited to just one extra level for toplevel trees,\nit effectively doubles the objects traversed for non-diffing log\noperations, impacting performance for everyone, not just those using\nconflict headers.  I’d prefer to avoid imposing a performance penalty\non users who don’t use any new features associated with first-class\nconflicts.\n\nAdditionally, I believe this approach would diverge from how jj and\nGitButler record conflicted commits.  I’d rather follow the path they\npaved to benefit from their expertise and minimize (if not eliminate)\nany possible rework they need for continued interoperability with Git\nversions that gain features they first implemented.\n\nWe may find reason to revisit this as things progress, but for now, I\ndon’t conflicted trees needs to be included in your modified tree\nproposal.\n"},{"id":"527733","messageId":"aN2g-RCLVuUYD7h2@fruit.crustytoothpaste.net","threadId":"64230","inReplyTo":"20251001211140.GA140550@peff.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-10-01T21:45:29Z","receivedAt":"2025-10-01T21:45:31Z","isPatch":true,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2025-10-01 at 21:11:40, Jeff King wrote:\n> So it all works as expected, but I feel like it's mostly by accident. My\n> gut feeling is that we probably wanted something like this to protect us\n> from confusion:\n> \n> index 06ad74db22..295b0c6318 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -719,6 +719,8 @@ int add_to_index(struct index_state *istate, const char *path, struct stat *st,\n>  \tif (S_ISDIR(st_mode)) {\n>  \t\tif (repo_resolve_gitlink_ref(the_repository, path, \"HEAD\", &oid) < 0)\n>  \t\t\treturn error(_(\"'%s' does not have a commit checked out\"), path);\n> +\t\tif (oid.algo != hash_algo_by_ptr(the_repository->hash_algo))\n> +\t\t\treturn error(_(\"object format %s of '%s' is incompatible with this repository (%s)\"), hash_algos[oid.algo].name, path, the_repository->hash_algo->name);\n>  \t\twhile (namelen && path[namelen-1] == '/')\n>  \t\t\tnamelen--;\n>  \t}\n> \n> Of course that is strictly worse for somebody who is relying on the\n> current accidental behavior. ;) And in the long run, I think this is the\n> spot we'd want to hook to do whatever massaging we need (whether\n> converting to the equivalent in-repo algorithm, or hacking up the name\n> to store the foreign hash).\n\nI think sending in this patch is a good first step right now.  The\nintention of the transition document is that the code is in one and only\none hash algorithm at a time and it would be better to reject this case\nuntil we're ready to wire it up correctly than end up with data that's\ncorrupt down the line.\n\n> I also won't be at all surprised if you've run across this already in\n> your interop work.\n\nI have not, since it's primarily involved working with the testsuite and\nsome test repositories.  I know that submodules are broken in interop\nmode; I didn't need to test that until I was writing code to make them\nnot-broken.\n-- \nbrian m. carlson (they/them)\nToronto, Ontario, CA\n"},{"id":"527741","messageId":"20251001225951.GA142037@peff.net","threadId":"64230","inReplyTo":"20251001211140.GA140550@peff.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-01T22:59:51Z","receivedAt":"2025-10-01T22:59:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 01, 2025 at 05:11:40PM -0400, Jeff King wrote:\n\n> But there were two unexpected bits. The first is that the above doesn't\n> just need a way to store the foreign-hash oid in a tree. It needs to be\n> in the index, too.\n> \n> We could perhaps use the same hackery there, storing sha1-...-foo in the\n> index with the sentinel hash. Or perhaps we could extend the index to\n> support holding foreign hashes. I'm not sure which would be less\n> annoying. If the index and trees don't match, then tree-to-index\n> comparisons get weird. If the index and filesystem don't match, then\n> index to filesystem comparisons get weird. My gut feeling is that making\n> index-to-filesystem comparisons weird (so putting the hacked name into\n> the index) is probably going to be better, just because the filesystem\n> is already out of our control. So we can do sorted comparisons between\n> the index and trees, but filesystem operations are inherently asking\n> about paths one by one. But I'd have to dig deeper to get more confident\n> in that opinion.\n\nI know everybody was on the edge of their seats, so here's how far I got\n(I will probably be offline for travel for a day or two after this).\n\nThis patch generates the hacked-up index entry when you do a \"submodule\nadd\" (or even a regular \"git add\"). I suspect it is missing some corner\ncases (in particular, I doubt that it would correctly update with \"git\nadd -u\" because the actual filesystem path appears untracked from the\nnaive perspective of the index).\n\nIt is not too ugly, I think:\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 06ad74db22..77072df2f7 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -708,6 +708,7 @@ int add_to_index(struct index_state *istate, const char *path, struct stat *st,\n \t\t\t  (intent_only ? ADD_CACHE_NEW_ONLY : 0));\n \tunsigned hash_flags = pretend ? 0 : INDEX_WRITE_OBJECT;\n \tstruct object_id oid;\n+\tstruct strbuf submodule_foreign_path = STRBUF_INIT;\n \n \tif (flags & ADD_CACHE_RENORMALIZE)\n \t\thash_flags |= INDEX_RENORMALIZE;\n@@ -719,6 +720,16 @@ int add_to_index(struct index_state *istate, const char *path, struct stat *st,\n \tif (S_ISDIR(st_mode)) {\n \t\tif (repo_resolve_gitlink_ref(the_repository, path, \"HEAD\", &oid) < 0)\n \t\t\treturn error(_(\"'%s' does not have a commit checked out\"), path);\n+\t\tif (oid.algo != hash_algo_by_ptr(the_repository->hash_algo)) {\n+\t\t\t/* XXX maybe need to remove entry for \"path\"? */\n+\t\t\tstrbuf_addf(&submodule_foreign_path, \"%s-%s-%s\",\n+\t\t\t\t    hash_algos[oid.algo].name,\n+\t\t\t\t    oid_to_hex(&oid),\n+\t\t\t\t    path);\n+\t\t\tpath = submodule_foreign_path.buf;\n+\t\t\tnamelen = submodule_foreign_path.len;\n+\t\t}\n+\n \t\twhile (namelen && path[namelen-1] == '/')\n \t\t\tnamelen--;\n \t}\n@@ -768,7 +779,20 @@ int add_to_index(struct index_state *istate, const char *path, struct stat *st,\n \t\t}\n \t}\n \tif (!intent_only) {\n-\t\tif (index_path(istate, &ce->oid, path, st, hash_flags)) {\n+\t\t/*\n+\t\t * We actually re-resolve submodules a second time in\n+\t\t * index_path(). That's perhaps something we should\n+\t\t * avoid in general (because it's racy), but it's\n+\t\t * particularly important for our submodule name\n+\t\t * hackery, since \"path\" is no longer something exists\n+\t\t * in the filesystem at all, and we want to override it with\n+\t\t * our fake sentinel OID anyway.\n+\t\t */\n+\t\tif (submodule_foreign_path.len) {\n+\t\t\t/* probably a constant would be less horrific */\n+\t\t\toidclr(&ce->oid, the_repository->hash_algo);\n+\t\t\tce->oid.hash[the_repository->hash_algo->rawsz - 1] = 1;\n+\t\t} else if (index_path(istate, &ce->oid, path, st, hash_flags)) {\n \t\t\tdiscard_cache_entry(ce);\n \t\t\treturn error(_(\"unable to index file '%s'\"), path);\n \t\t}\n\n\nBut then I took a look at the reading side, and it gets pretty ugly.\nOften we have just a submodule name, and we end up referencing it in the\nindex. But of course we don't know if we need to use the hacked-up name\nto do the lookup or not, because it depends on the sentinel hash, but we\ndon't always have a hash yet! So you'd have to speculatively look up\nboth names in lots of places.\n\nSo I think I do lean more towards the index having the full, correct\ninformation, and just doing this hack at the tree level (and munging as\nwe read/write the trees).\n\nOr of course deciding it's all too horrible and abandoning it. All of\nthis was meant to be an exploration. I do think it makes a lot of\npotential problems and hassles go away if we can intermix submodules of\ndifferent hash algorithms. I'm undecided on whether the solution is\nworth than the problem, though.\n\n-Peff\n"},{"id":"527742","messageId":"20251001230043.GB142037@peff.net","threadId":"64230","inReplyTo":"aN2g-RCLVuUYD7h2@fruit.crustytoothpaste.net","subject":"Re: [RFC PATCH 1/1] Define an extended tree format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-01T23:00:43Z","receivedAt":"2025-10-01T23:00:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 01, 2025 at 09:45:29PM +0000, brian m. carlson wrote:\n\n> > Of course that is strictly worse for somebody who is relying on the\n> > current accidental behavior. ;) And in the long run, I think this is the\n> > spot we'd want to hook to do whatever massaging we need (whether\n> > converting to the equivalent in-repo algorithm, or hacking up the name\n> > to store the foreign hash).\n> \n> I think sending in this patch is a good first step right now.  The\n> intention of the transition document is that the code is in one and only\n> one hash algorithm at a time and it would be better to reject this case\n> until we're ready to wire it up correctly than end up with data that's\n> corrupt down the line.\n\nOK. I'll try to clean it up and add some tests, but it may not be until\nnext week.\n\n-Peff\n"}]}