Tree issues: invalid but working (except not?)

[xmo-odoo]

I stumbled upon a possible issue with trees in git-objects (and possibly downstream subcrates), but I'm not quite sure what consideration it should get: currently, Tree::entries has a documentary note indicating that it must be sorted, and WriteTo for Tree has debug assertions ensuring this is to be so.

I wondered what'd happen if I replaced the Vec by a BTreeSet (which are naturally sorted so the constraint would not be an issue anymore), but aside from nom::multi::many0 returning Vec (so this would require a heavy conversion during parsing) it led me to find a few potential issues / incompatibilities with Git:

• the note indicating that the entries must be sorted dates back to d94f84c however it's not clear what the consequences would be, and git will happily generate trees with mis-ordered or duplicate entries, these will be warned about by git fsck but but at best git-mktree(1) will protect ordering issues (it automatically reorders its input, but does not deduplicate)
• git does not use a lexicographic ordering for tree object, instead it uses "path ordering" meaning tree names have an implicit trailing /, this means regular fsck-valid git objects will break gitoxide's assumptions, per git's own comments:

  a directory called "a" is ordered after a file called "a.c", because "a/" sorts after "a.c".

(1) seems like it could be a minor issue at any time, however in trying to understand these cases it seemed like not all hosting sites will accept them (however it also seems like people routinely unwittingly create such objects).

However (2) seems like it could be a pretty major issue depending on the reason for the note, and whether it hinges on the ordering of the entries in the object, or only on the entries being sorted according to Entry::cmp (in the latter case fixing Ord should do the trick). Is the issue here the tree diffing? Or is it something else? Or is it both tree diffing and other concerns?

A secondary concern is API-wise: given the original note and the failure of my BTreeSet scheme I figured providing a newtype for tree entries which would always uphold the invariants, but of course this is an issue if they're not actually invariant. Though I guess "undefined behaviour" is fine in that case. Related: binary_search definitely misbehaves when given mis-ordered sequences but select_nth_unstable is only in 1.49, what rustc version is gitoxide bound to? Though binary_search would have issues deduplicating blob/tree entries, and select_nth_unstable would be of no help at all there (aside from looking around the newly moved entry if one of its siblings has a colliding name I guess, but again that'd be defeated by git's somewhat strange ordering predicate).

[xmo-odoo]

Also more of an idle curiosity thing: why do Entry::cmp (and EntryRef::cmp) slice to the shortest of the two lengths before comparing? It doesn't seem like it should do anything useful.

[Byron]

Is the issue here the tree diffing? Or is it something else? Or is it both tree diffing and other concerns?

Indeed, tree-diffing immediately comes to mind when proper sorting according to Entry::cmp is assumed.

however it also seems like people routinely unwittingly create such objects

That would be interesting to learn how that's possible. Any API allowing the creation of trees should assure these are sorted properly, at least that's my assumption. If trees are created from an index file, these are properly sorted as well. All that is most certainly done to avoid having to check for sorting before using trees, for diffing usually, which is vital to performance.

Also more of an idle curiosity thing: why do Entry::cmp (and EntryRef::cmp) slice to the shortest of the two lengths before comparing? It doesn't seem like it should do anything useful.

That's how git does it, and it should be possible to play around with this while running tests to see if there is a more idiomatic way of doing it maybe.

A secondary concern is API-wise: given the original note and the failure of my BTreeSet scheme I figured providing a newtype for tree entries which would always uphold the invariants, but of course this is an issue if they're not actually invariant. Though I guess "undefined behaviour" is fine in that case. Related: binary_search definitely misbehaves when given mis-ordered sequences but select_nth_unstable is only in 1.49, what rustc version is gitoxide bound to? Though binary_search would have issues deduplicating blob/tree entries, and select_nth_unstable would be of no help at all there (aside from looking around the newly moved entry if one of its siblings has a colliding name I guess, but again that'd be defeated by git's somewhat strange ordering predicate).

Whatever the implementation, it can't be slower than what's there, and a BTreeSet sounds like a lot of additional allocations. You will see that in the interest of speed, diff APIs only iterate entries without actually building a Vec, and the same holds true for looking up the hash at a certain path for simple 'is changed' tests, as that is actually faster than paying for a vec without reuse, despite the lookup then being powered by the faster binary search (I tried that).

Please note that I am probably glossing over or not picking up a few points or details at all, if so, please feel free to highlight them and I will try again.

[xmo-odoo]

however it also seems like people routinely unwittingly create such objects

That would be interesting to learn how that's possible.

Indeed, sadly in all the cases I found the victims were trying to repair the damage when they found about it (either running fsck or trying to migrate to a host which always fsck's and thus rejects duplicates or mis-ordered trees) e.g.

• https://stackoverflow.com/questions/10931954/git-tree-contains-duplicate-file-entries
• https://stackoverflow.com/questions/13178720/tree-contains-duplicate-file-entries
• https://unix.stackexchange.com/questions/570121/git-fsck-fails-with-the-same-error-for-4-different-repositories
• https://unix.stackexchange.com/questions/571256/git-fsck-shows-duplicateentries-but-im-able-to-git-pull-and-push

None of them explains how they arrived there aside from this issue against libgit2 which hints that case-changing renames on CI filesystems could be involved (but ultimately gets closed for lack of resolution).

However I can say for sure that git-mktree(1) will create duplicate entries tree if you give it duplicate entries, whether duplicate blobs or a tree and a blob with the same name.

Any API allowing the creation of trees should assure these are sorted properly, at least that's my assumption.

That's rational, but given how "open" the format is and how many will DIY the thing, it's probably a good idea to not assume all objects are perfectly formed (though ill-formed ones can quite obviously be punted to a slow path if that's an option).

Also more of an idle curiosity thing: why do Entry::cmp (and EntryRef::cmp) slice to the shortest of the two lengths before comparing? It doesn't seem like it should do anything useful.

That's how git does it, and it should be possible to play around with this while running tests to see if there is a more idiomatic way of doing it maybe.

I'd assume that's more of an artifact of using memcmp, though could be worth checking if rust can optimise comparison between same-length strings or if it's just unnecessary and results in the same as different-length strings.

Still, I guess I'll take a look at this mess, adding the path sorting to entries probably should not impact performances too much (hopefully).

A secondary concern is API-wise: given the original note and the failure of my BTreeSet scheme I figured providing a newtype for tree entries which would always uphold the invariants, but of course this is an issue if they're not actually invariant. Though I guess "undefined behaviour" is fine in that case. Related: binary_search definitely misbehaves when given mis-ordered sequences but select_nth_unstable is only in 1.49, what rustc version is gitoxide bound to? Though binary_search would have issues deduplicating blob/tree entries, and select_nth_unstable would be of no help at all there (aside from looking around the newly moved entry if one of its siblings has a colliding name I guess, but again that'd be defeated by git's somewhat strange ordering predicate).

Whatever the implementation, it can't be slower than what's there, and a BTreeSet sounds like a lot of additional allocations. You will see that in the interest of speed, diff APIs only iterate entries without actually building a Vec, and the same holds true for looking up the hash at a certain path for simple 'is changed' tests, as that is actually faster than paying for a vec without reuse, despite the lookup then being powered by the faster binary search (I tried that).

Yeah I was thinking mostly for the "external" API to avoid users constructing "incorrect" entries vectors when creating trees "by hand". I'll definitely have to look at how tree objects are created internally (when they're not just deserialized).

[Byron]

That's rational, but given how "open" the format is and how many will DIY the thing, it's probably a good idea to not assume all objects are perfectly formed (though ill-formed ones can quite obviously be punted to a slow path if that's an option).

Indeed, yet putting users onto a slow path means checking for malformed input. The latter I wouldn't do in release mode, and can imagine a debug assertion to help debugging this along with clear docs. Higher-level crates, namely git-repository will most certainly offer an API that makes creating invalid trees impossible at some cost, but such API still has to manifest, which is in line with:

Yeah I was thinking mostly for the "external" API to avoid users constructing "incorrect" entries vectors when creating trees "by hand". I'll definitely have to look at how tree objects are created internally (when they're not just deserialized).