Re: [PATCH 2/2] Documentation/gitformat-pack.txt: fix incorrect MIDX documentation

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

Taylor Blau <me@ttaylorr.com> writes:

> diff --git a/Documentation/gitformat-pack.txt b/Documentation/gitformat-pack.txt
> index d7153962d4..54000c9412 100644
> --- a/Documentation/gitformat-pack.txt
> +++ b/Documentation/gitformat-pack.txt
> @@ -392,8 +392,9 @@ CHUNK DATA:
>  	Packfile Names (ID: {'P', 'N', 'A', 'M'})
>  	    Stores the packfile names as concatenated, NUL-terminated strings.

Not a problem this series (neither this or the previous step)
introduces, but I had to read the implementation of
write_midx_pack_names() to find out what "concatenated
NUL-terminated string" really means.  The code has a list of
strings, writes each of them as a NUL-terminated string in sequence,
and to align the beginning of the next chunk, NULs are added to make
the whole thing multiple of MIDX_CHUNK_ALIGNMENT bytes.

A naive reader code might implement a loop like so:

	while (ptr[0] != '\0') {
		endp = strlen(ptr);
		... ptr[0..endp] is one pathname ...
		ptr = endp + 1;
	}
		
expecting that the terminating NUL of the last entry would be
followed by a NUL, but that is buggy.  The sum of the pathname
strings (with one NUL after each) may happen to be multiple of
MIDX_CHUNK_ALIGNMENT bytes, in which case no extra padding NUL bytes
will be there.  So the reader also needs to pay attention to the
chunk size to notice when to stop reading.  It feels somewhat
suboptimal.

>  	    Packfiles must be listed in lexicographic order for fast lookups by
> -	    name. This is the only chunk not guaranteed to be a multiple of four
> -	    bytes in length, so should be the last chunk for alignment reasons.
> +	    name. Individual entries in this chunk are not guarenteed to be
> +	    aligned. The chunk is externally padded with zeros to align
> +	    remaining chunks.

I am not sure what "externally padded" means.

Before write_midx_pack_names() returns, there is a code to pad the
space after it writes those names, which does not look any external
than the bytes used to record the pathnames or NUL bytes used to
terminate these pathnames.

To me, "externally padded" is an appropriate phrase to use if this
function does not bother with the alignment after what it needs to
record, but the caller, i.e., write_chunkfile(), has code to notice
that the number of bytes written by cf->chunks[i].write_fn() it just
called is not a multiple of some required alignment and adds padding
bytes after .write_fn() returned.  I do not think that is what is
going on here.

My observations.

 * The packfile names chunk is used to record N pathnames; N is not
   recorded anywhere explicitly.  To record N pathnames, a single
   chunk with N names in it is used.  It is not like N chunks, each
   with one name is used.

 * Each of these pathname is recorded literally, followed by a NUL,
   in some order, without any extra padding.

 * To keep the size of the chunk multiple of alignment requirement,
   there may be extra NUL bytes after the names.

This data structure does not allow you to binary search or hash
lookup without an extra table of pointers into this table of strings
at runtime, and once you build such a table, the source being sorted
does not help all that much.  So I am not sure how strict the
"lexicographic" requirement needs to be, but of course, starting
strict and loosening later is much easier than starting loose, so
documenting "must be listed" and following that rule is fine.

Thanks.