Re: fix git-pack-redundant crashing sometimes

[Junio C Hamano <junkio@cox.net>]

Linus Torvalds <torvalds@osdl.org> writes:

> On Tue, 15 Nov 2005, Alex Riesen wrote:
>> 
>> Sorry, it doesn't. The code loops here:
>> 
>> 401             /* find the permutations which contain all missing objects */
>> 402             perm_all = perm = get_all_permutations(non_unique);
>
> Looks like the whole thing is exponential.

This reminds me of one thing I have been meaning to remove.

The $GIT_OBJECT_DIRECTORY/info/pack file produced by
update-server-info records not just the packs (P lines), but its
dependencies (D lines) and top objects (T lines).  If there are
more than one packs, D lines are meant to help the downloader to
figure out what other packs are needed to complete.

"meant to" is the keyword here.  The original heuristics was
very bad (still correct but way suboptimal) and it has never
been updated.  I do not use that information myself in http
fetch, and I do not think any Porcelain uses it.

Top objects are tags and commits in the pack that are not
reachable from any other object in the same pack.  This can be
useful if you obtain just a packfile -- you can run server-info
to produce info/pack file, and resurrect the branch heads and
tags by using them --- you would not know what they are called,
though.  I have been thinking it may be worthwhile to also
record bottom objects (B lines, naturally) --- tags and commits
in the pack that refer to tags or commits not present in the
same pack.  This would help commit walkers to decide which pack
is more efficient to slurp when faced with multiple choices.  If
you see a pack all whose bottom objects you have in your
repository, fetching that would complete the commit walking, so
the choice would become the matter of choosing such a pack among
multiple that has smallest number of objects you do not have
locally -- you would have the index file for each pack at that
point.