Re: invalid tree and commit object

[Junio C Hamano <gitster@pobox.com>]

René Scharfe <l.s.r@web.de> writes:

> So I got curious if such trees might be in popular repos, wrote the patch
> below and checked around a bit, but couldn't find any.
>
> Is there a smarter way to check for duplicates?  One that doesn't need
> allocations?  Perhaps by having a version of tree_entry_extract() that
> seeks backwards somehow?

I've never looked into seeking backwards in a tree object, but in
unpack-trees, I had to deal with this exact problem that a blob
'hello' sorts before 'hello.c' which in turn sorts after a tree
'hello' because of the "implicit slash after the name for an entry
for a tree object" rule by introducing the "cache_bottom" hack in
the traversal logic to limit how far we must scan back.

We may be able to limit the list of "seen recently" names in a
similar way.

If the tree we are scanning has 'hello' (blob), 'hello.c' and
'hellp', the bottom pointer initially would be at 'hello' (blob),
then stay there when we see 'hello.c' (because the next entry might
be 'hello' (tree) that would crash with 'hello'), and when we see
the entry 'hellp', we know that the entry at the bottom pointer
'hello' (blob) cannot crash with any entry that comes later in the
tree object we are scanning, so we can advance the bottom pointer
forward.  To decide if we can advance the bottom pointer beyond
'hello.c' (blob), we see if 'hello.c' (tree) can appear after the
current entry we are looking at (i.e. 'hellp'), and we know it
cannot without violating the sort order.  So the bottom would move
to point at 'hellp' we just saw.

If we had 'hello' (tree) instead of 'hellp', when we look at it
after looking at 'hello' (blob) and 'hello.c', we scan from the
bottom pointer up to the previous entry, which is still pointing at
'hello' (blob), and notice the crash.