Re: [PATCH v2 3/3] index-pack: eliminate unlimited recursion in get_delta_base()

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 9, 2012, 22:51 UTC
Message-ID: <7vvcokcwvt.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1326081546-29320-4-git-send-email-pclouds@gmail.com>

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

Show 6 quoted lines

> Revert the order of delta applying so that by the time a delta is
> applied, its base is either non-delta or already inflated.
>
> get_delta_base() is still recursive, but because base's data is always
> ready, the inner get_delta_base() call never has any chance to call
> itself again.

I suspect s/Revert/Reverse/ here, but I have a feeling that the structure of the resulting code is a bit too complex and subtle.

In parse_pack_objects(), we have two passes. The first pass scans to enumerate the objects that appear in the pack and sift them into base and delta objects, and the second one starts from a base object, resolves its immediate children with find_unresolved_daltas(), but that function recurses many times, bound only by the number of objects in the pack, which is the issue you are trying to address with this series.

I wonder if a cleaner approach is to change the loop in the second pass in such a way that (1) the function it calls resolves _only_ the immediate children of the object we know its final shape (either because the object was recorded in the deflated form in the pack, or we have already resolved it in earlier iteration), and (2) the loop goes over the objects[] array not just once, but until we stopped making progress.

It would require us to be able to tell, by looking at objects[i], if the object itself has already been handled (perhaps you can look at its idx.sha1 field for this purpose) and if we have already handled its immediate delta children (you may need to add a bit to struct object_entry for this).