Re: invalid tree and commit object

> 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.
>