Re: force deterministic trees on git push - exact sort-order of filenames

From: René Scharfe <l.s.r@web.de>
Date: Oct 15, 2021, 17:47 UTC
Message-ID: <dab8ce58-fef6-7988-f494-c096e1265aa2@web.de>
In-Reply-To: <CAGiEHCtdjA+cVXjN43NPbSZfrDtr-kDtPMN4x_VTGSJuPZ8bcg@mail.gmail.com>

Am 15.10.21 um 18:04 schrieb milan hauth:

> fact: the sort-order of filenames in a tree is not strictly regulated

Actually it is.

> proposal: enforce the exact sort-order of tree-items,
> to make trees deterministic and reproducible.

That's a good idea. It was implemented in e83c516331 (Initial revision of "git", the information manager from hell, 2005-04-07), whose README says:

  "A tree object is a list of permission/name/blob data, sorted by name.
   In other words the tree object is uniquely determined by the set
   contents, and so two separate but identical trees will always share
   the exact same object."

> the git server could refuse a 'git push',
> when the tree is invalid

It should.

Show 9 quoted lines

> sample trees from [1] and [2]:
>
> git cat-file -p 2b75a7dbb76138587dbe50a5a6af8a6eedbaf66b | grep id_ed25519
> 100644 blob f914b3f712fc56ab212b53cb9055e1291b5c77a2    id_ed25519
> 100644 blob 40de4a8ac6027f64ac85f687bea7049467b428a2    id_ed25519.pub
>
> git cat-file -p c8a72e628d0ca0a174a1a4241e6c7314a4660f0f | grep example
> 100644 blob fde6f3cbd19addb8ce84ffe32ab4d040e8b09c18    example.pem
> 040000 tree 6b0ee97865059ac965590e0ff5272fb76b6fd2c8    example

Tree entries are sorted by name, except that the names of a sub-trees (like "example" above) get an implicit slash (/) appended. Slash (ASCII character 47) sorts after dot (ASCII character 46).

Are you able to generate and push different trees objects that reference the same entries (same names, hashes, modes) in different order?

René