Re: invalid tree and commit object

["René Scharfe" <l.s.r@web.de>]

Am 09.05.20 um 19:28 schrieb Junio C Hamano:
> 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.
>

Hmm, this could lead to quadratic behavior in the worst case, can't it?
Imagine you have:

  a
  a.b
  a.b.c
  ...
  a.b.c/
  a.b/
  a/

If you have a single bottom pointer, it needs to stay at "a" the whole
time, so that you can detect the d/f conflict with "a/" at the end.
And for all entries in between you need to scan from "a" on and compare
each entry -- quadratic.  The blobs "a.b" and "a.b.c" don't need to
actually be present, but we need to scan all entries to determine
"a.b/" and "a.b.c/" are not conflicting anyway.  Right?

We could, however, reduce the names we add to the string_list to
those that are possible candidates for conflict -- blobs followed by an
entry whose name starts with the blob name followed by a dot and trees
that follow an entry whose name matches in the same way.

René