Re: [PATCH] sha1_file: remove recursion in packed_object_info

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

Thomas Rast <trast@student.ethz.ch> writes:

> So here's a nonrecursive version.  Dijkstra is probably turning over
> in his grave as we speak.
>
> I *think* I actually got it right.

You seem to have lost the "if we cannot get delta base, this object
is BAD" check where you measure the size of a deltified object,
which would correspond to this check:

> -static int packed_delta_info(struct packed_git *p,
> -			     struct pack_window **w_curs,
> -			     off_t curpos,
> -			     enum object_type type,
> -			     off_t obj_offset,
> -			     unsigned long *sizep)
> -{
> -	off_t base_offset;
> -
> -	base_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);
> -	if (!base_offset)
> -		return OBJ_BAD;

The following comment is also lost but...

> -	/* We choose to only get the type of the base object and
> -	 * ignore potentially corrupt pack file that expects the delta
> -	 * based on a base with a wrong size.  This saves tons of
> -	 * inflate() calls.
> -	 */
> -	if (sizep) {
> -		*sizep = get_size_from_delta(p, w_curs, curpos);
> -		if (*sizep == 0)
> -			type = OBJ_BAD;

... is this check correct?  There is an equivalent check at the
beginning of the new packed_object_info() to error out a deltified
result.  Why is an object whose size is 0 bad?

This comes from 3d77d8774fc1 (make packed_object_info() resilient to
pack corruptions, 2008-10-29), and I tend to trust Nico more than I
do myself. I must be missing something obvious, but it appears to me
that the only thing that keeps us from triggering a false positive
is that we do not even attempt to deltify anything smaller than 50
bytes, and create_delta() refuses to create a delta to produce an
empty data.  But a hand-crafted packfile could certainly record such
a delta, no?

> The task of the two functions is not all that hard to describe without
> any recursion, however.  It proceeds in three steps:
>
> - determine the representation type and size, based on the outermost
>   object (delta or not)
>
> - follow through the delta chain, if any
>
> - determine the object type from what is found at the end of the delta
>   chain

The stack/recursion is used _only_ for error recovery, no?  If we do
not care about retrying with a different copy of an object we find
in the delta chain, we can just update obj_offset with base_offset
and keep digging.  It almost makes me wonder if a logical follow-up
to this patch may be to do so, and rewrite the error recovery
codepath to just mark the bad copy and jump back to the very top,
retrying everything from scratch.  Eventually we would run out
bad copies of the problematic object and would report an error, or
find a good copy and return the type.