[RFC PATCH 1/1] Define an extended tree format

From

brian m. carlson <sandals@crustytoothpaste.net>

Date

Oct 1, 2025, 00:58 UTC

Message-ID

<20251001005814.846992-2-sandals@crustytoothpaste.net>

In-Reply-To

<20251001005814.846992-1-sandals@crustytoothpaste.net>

Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
---
 Documentation/Makefile                     |  1 +
 Documentation/gitformat-extended-tree.adoc | 77 ++++++++++++++++++++++
 Documentation/meson.build                  |  1 +
 3 files changed, 79 insertions(+)
 create mode 100644 Documentation/gitformat-extended-tree.adoc

diff --git a/Documentation/Makefile b/Documentation/Makefile
index 6fb83d0c6e..6d8ad220ed 100644
--- a/Documentation/Makefile
+++ b/Documentation/Makefile
@@ -33,6 +33,7 @@ MAN5_TXT += gitattributes.adoc
 MAN5_TXT += gitformat-bundle.adoc
 MAN5_TXT += gitformat-chunk.adoc
 MAN5_TXT += gitformat-commit-graph.adoc
+MAN5_TXT += gitformat-extended-tree.adoc
 MAN5_TXT += gitformat-index.adoc
 MAN5_TXT += gitformat-pack.adoc
 MAN5_TXT += gitformat-signature.adoc
diff --git a/Documentation/gitformat-extended-tree.adoc b/Documentation/gitformat-extended-tree.adoc
new file mode 100644
index 0000000000..fc28bb16c9
--- /dev/null
+++ b/Documentation/gitformat-extended-tree.adoc
@@ -0,0 +1,77 @@
+Extended Tree Format
+====================
+
+Rationale
+---------
+
+Git needs to store some additional types of data in repositories that we had
+previously not considered.  Unfortunately, we lack a good way to extend tree
+formats in a backwards compatible way.
+
+This document proposes an approach that adds an extended tree format that is
+backwards compatible with earlier versions of Git except that it will appear
+that the tree is improperly sorted.  This is done by encoding additional bytes
+that are guaranteed to be nonzero and that earlier versions of Git will
+consider part of the file name.
+
+Format
+------
+:ber: footnote:[This is the format used by the `w` pack format in Perl and Ruby.]
+
+An extended tree format consists of an entry that has mode 130000.
+
+A modified BER-encoded integer is a BER-encoded integer{ber} with the top bits
+of each byte flipped.  That is, values 0x00 through 0x7f are encoded as 0x80
+through 0xff, and larger values are encoded such that the bottom 7 bits of each
+byte include the value and the top bit is 0 if there is a subsequent byte of
+data and 1 if this is the last byte.  The shortest possible encoding must be
+used.  Note that the byte 0x00 is not valid in the encoded value.
+
+The first part of what is traditionally the file name consists of a modified
+BER-encoded integer representing the number of bytes in the extended
+information section not including this length itself; that is, the number of
+bytes which must be skipped to reach the file name.  This allows parsing
+unknown values in a graceful way.
+
+Following that is a modified BER-encoded integer representing the type of
+object and a modified BER-encoded integer consisting of flags.
+
+The object type is one of the following:
+
+0:: invalid
+1:: conflict tree (only valid at top level)
+2:: extended submodule
+
+The following flags are defined:
+
+1 (bit 0):: This entry is critical and failure to handle this object should be fatal.
+2 (bit 1):: Flags in this entry are critical and failure to understand them should be fatal.
+
+A conflict tree then has a modified BER-encoded integer representing the stage.
+
+Conflict trees are used to store a conflicted state.  The top-level tree
+contains only entries called stageN, where N is a decimal representation of the
+stage integer.  Resolved entries are always stored as stage 0.  The contents of
+each tree are those of the root tree at that stage.
+
+An extended submodule then has a 32-bit format ID representing the algorithm in
+question, followed by a nonzero byte called an offset.  If the object ID for
+the selected algorithm is longer than the algorithm for the tree, the remaining
+bytes of the object ID are encoded such that each one is XORed with the offset.
+The offset must be the smallest nonzero byte value such that all of the encoded
+bytes are also nonzero; an entry is malformed if this value is incorrect.
+
+If the object ID for the selected algorithm is shorter than the algorithm for
+the tree, the main object ID field is padded with zeros.
+
+Examples
+--------
+
+An extended submodule of a SHA-256 submodule in a SHA-1 repository might look
+like this if the submodule object name is
+deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef and the name
+is `submodule`:
+
+----
+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
+----
diff --git a/Documentation/meson.build b/Documentation/meson.build
index e34965c5b0..e2257050e8 100644
--- a/Documentation/meson.build
+++ b/Documentation/meson.build
@@ -172,6 +172,7 @@ manpages = {
   'gitformat-bundle.adoc' : 5,
   'gitformat-chunk.adoc' : 5,
   'gitformat-commit-graph.adoc' : 5,
+  'gitformat-extended-tree.adoc' : 5,
   'gitformat-index.adoc' : 5,
   'gitformat-pack.adoc' : 5,
   'gitformat-signature.adoc' : 5,