Re: invalid tree and commit object

From: Junio C Hamano <gitster@pobox.com>
Date: May 9, 2020, 20:27 UTC
Message-ID: <xmqqh7wovoop.fsf@gitster.c.googlers.com>
In-Reply-To: <938f0818-7e57-b883-009f-01db88ef8f65@web.de>

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

> Hmm, this could lead to quadratic behavior in the worst case, can't it?

Oh, absolutely. But as you have shown, you'd need a specially crafted tree with early entries that are prefixes of later ones, which would rather be rare, and most of the time the bottom pointer would advance by one every time we consume one path.

So it is trading (hopefully rare) worst-case runtime with reduced storage cost.

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

Yes, that is a valid solution that strikes a different balance between allocation and runtime.

We may want to survey how commonly "bad" trees appear in real projects. Depending on the result, we might want to update the "limit re-scanning using the bottom pointer" hack we have been using in the unpack-trees code.

Thanks.