commit: allow associating auxiliary info on-demand

The "indegree" field in the commit object is only used while sorting
a list of commits in topological order, and wasting memory otherwise.

We would prefer to shrink the size of individual commit objects,
which we may have to hold thousands of in-core. We could eject
"indegree" field out from the commit object and represent it as a
dynamic table based on the decoration infrastructure, but the
decoration is meant for sparse annotation and is not a good match.

Instead, let's try a different approach.

 - Assign an integer (commit->index) to each commit we keep in-core
   (reuse the space of "indegree" field for it);

 - When running the topological sort, allocate an array of integers
   in bulk (called "slab"), use the commit->index as an index into
   this array, and store the "indegree" information there.

This does _not_ reduce the memory footprint of a commit object, but
the commit->index can be used as the index to dynamically associate
commits with other kinds of information as needed.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-slab: avoid large realloc

Instead of using a single "slab" and keep reallocating it as we find
that we need to deal with commits with larger values of commit->index,
make a "slab" an array of many "slab_piece"s. Each access may need
two levels of indirections, but we only need to reallocate the first
level array of pointers when we have to grow the table this way.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit-slab: introduce a macro to define a slab for new type

Introduce a header file to define a macro that can define the struct
type, initializer, accessor and cleanup functions to manage a commit
slab.  Update the "indegree" topological sort facility using it.

To associate 32 flag bits with each commit, you can write:

	define_commit_slab(flag32, uint32);

to declare "struct flag32" type, define an instance of it with

	struct flag32 flags;

and initialize it by calling

	init_flag32(&flags);

After that, a call to flag32_at() function

	uint32 *fp = flag32_at(&flags, commit);

will return a pointer pointing at a uint32 for that commit.  Once
you are done with these flags, clean them up with

	clear_flag32(&flags);

Callers that cannot hard-code how wide the data to be associated
with the commit be at compile time can use the "_with_stride"
variant to initialize the slab.

Suppose you want to give one bit per existing ref, and paint commits
down to find which refs are descendants of each commit.  Saying

	typedef uint32 bits320[5];
	define_commit_slab(flagbits, bits320);

at compile time will still limit your code with hard-coded limit,
because you may find that you have more than 320 refs at runtime.

The code can declare a commit slab "struct flagbits" like this
instead:

	define_commit_slab(flagbits, unsigned char);
	struct flagbits flags;

and initialize it by:

	nrefs = ... count number of refs ...
	init_flagbits_with_stride(&flags, (nrefs + 7) / 8);

so that

	unsigned char *fp = flagbits_at(&flags, commit);

will return a pointer pointing at an array of 40 "unsigned char"s
associated with the commit, once you figure out nrefs is 320 at
runtime.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
toposort: rename "lifo" field

The primary invariant of sort_in_topological_order() is that a
parent commit is not emitted until all children of it are.  When
traversing a forked history like this with "git log C E":

    A----B----C
     \
      D----E

we ensure that A is emitted after all of B, C, D, and E are done, B
has to wait until C is done, and D has to wait until E is done.

In some applications, however, we would further want to control how
these child commits B, C, D and E on two parallel ancestry chains
are shown.

Most of the time, we would want to see C and B emitted together, and
then E and D, and finally A (i.e. the --topo-order output).  The
"lifo" parameter of the sort_in_topological_order() function is used
to control this behaviour.  We start the traversal by knowing two
commits, C and E.  While keeping in mind that we also need to
inspect E later, we pick C first to inspect, and we notice and
record that B needs to be inspected.  By structuring the "work to be
done" set as a LIFO stack, we ensure that B is inspected next,
before other in-flight commits we had known that we will need to
inspect, e.g. E.

When showing in --date-order, we would want to see commits ordered
by timestamps, i.e. show C, E, B and D in this order before showing
A, possibly mixing commits from two parallel histories together.
When "lifo" parameter is set to false, the function keeps the "work
to be done" set sorted in the date order to realize this semantics.
After inspecting C, we add B to the "work to be done" set, but the
next commit we inspect from the set is E which is newer than B.

The name "lifo", however, is too strongly tied to the way how the
function implements its behaviour, and does not describe what the
behaviour _means_.

Replace this field with an enum rev_sort_order, with two possible
values: REV_SORT_IN_GRAPH_ORDER and REV_SORT_BY_COMMIT_DATE, and
update the existing code.  The mechanical replacement rule is:

  "lifo == 0" is equivalent to "sort_order == REV_SORT_BY_COMMIT_DATE"
  "lifo == 1" is equivalent to "sort_order == REV_SORT_IN_GRAPH_ORDER"

Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: priority queue of pointers to structs

Traditionally we used a singly linked list of commits to hold a set
of in-flight commits while traversing history.  The most typical use
of the list is to add commits that are newly discovered to it, keep
the list sorted by commit timestamp, pick up the newest one from the
list, and keep digging.  The cost of keeping the singly linked list
sorted is nontrivial, and this typical use pattern better matches a
priority queue.

Introduce a prio-queue structure, that can be used either as a LIFO
stack, or a priority queue.  This will be used in the next patch to
hold in-flight commits during sort-in-topological-order.

Tests and the idea to make it usable for any "void *" pointers to
"things" are by Jeff King.  Bugs are mine.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
sort-in-topological-order: use prio-queue

Use the prio-queue data structure to implement a priority queue of
commits sorted by committer date, when handling --date-order.  The
structure can also be used as a simple LIFO stack, which is a good
match for --topo-order processing.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
log: --author-date-order

Sometimes people would want to view the commits in parallel
histories in the order of author dates, not committer dates.

Teach "topo-order" sort machinery to do so, using a commit-info slab
to record the author dates of each commit, and prio-queue to sort
them.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/lib-t6000: style fixes

Mostly fixes to initial indentation with 8-SP (they should be HT)
and wrapping long lines.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
topology tests: teach a helper to take abbreviated timestamps

The on_committer_date helper in t/lib-t6000 is used in t6002 and
t6003 with timestamps on a single day within a single minute
(i.e. 1971-08-16 00:00) and the tests repeat this over and over.

The actual value of the timestamp, however, does not matter very
much; only their relative ordering does.

Introduce another helper to expand only the suffix of the timestamp
to a full timestamp to make the lines shorter, and use it in this
helper.  Also, because all the commits in the test are made with
specific GIT_COMMITTER_DATE, stop unsetting it at the end of the
helper.

We'll be specifying the author timestamp to these test commits in a
later patch, which will be helped with this change.

Also remove a test that was commented-out from t6003; it used to
test a commit with the same parent listed twice, which was allowed
by mistake but was fixed long time ago.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
t6003: add --date-order test

The "--date-order" output is a slight twist of "--topo-order" in
that commits from parallel histories are shown in their committer
date order without an attempt to clump commits from a single line
of history together like --topo-order does.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
topology tests: teach a helper to set author dates as well

Introduce on_dates helper that is similar to on_committer_date but
also sets the author date, not just the committer date.

At this step, just set the same timestamp to the author date as the
committer date, as no test looks at author date yet.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
t6003: add --author-date-order test

Tweak the --topo/date-order test vector a bit and mark the author
dates of two commits (a2 and a3) earlier than their own committer
dates, making them much older than other commits that are made on
parallel branches to simulate the case where a long running topic
was rebased recently.

They will show up as recent in the --date-order output due to their
timestamps, but they appear a lot later in the --author-date-order
output, even though their committer timestamp says otherwise.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
doc/clone: Remove the '--bare -l -s' example

There are other examples in git-clone.txt demonstrating both '--bare'
and '-l -s'.

Signed-off-by: W. Trevor King <wking@tremily.us>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
doc/clone: Pick more compelling paths for the --reference example

There may be times when using one of your local repositories as a
reference for a new clone make sense, but the implied version-bump in
the old example isn't one of them.  I think a more intuitive example
is multi-user system with a central reference clone, and the new paths
hint at this use case.

Signed-off-by: W. Trevor King <wking@tremily.us>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation: Update the NFS remote examples to use the staging repo

linux-nfs.org seems to have restructured their repository layout since
8391c60 (git-remote.txt: fix example url, 2007-11-02), and Bruce's
repo is now at git://git.linux-nfs.org/projects/bfields/linux.git.
Bruce also has a more richer internal branch structure (master,
everything, for-3.1, ...), so updating the existing example to use his
current repo may be confusing.

To simplify, I've replaced the NFS repo with Greg's staging repo.
I've also updated the output of the surrounding commands to match the
output of a current run through.

Signed-off-by: W. Trevor King <wking@tremily.us>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation: Update 'linux-2.6.git' -> 'linux.git'

The 3.x tree has been out for a while now.  The -2.6 repository name
survived the initial release [1], but kernel.org now only lists
'linux.git' (for aegl as well as torvalds) [2].

[1]: http://article.gmane.org/gmane.linux.kernel/1147422
  On 2011-05-30 01:47:57 GMT, Linus Torvalds wrote:
  > ... yes, that means that my git tree is still called
  > "linux-2.6.git" on kernel.org.
[2]: http://git.kernel.org/cgit/

Signed-off-by: W. Trevor King <wking@tremily.us>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/t5505-remote: modernize style

Modernize the style of all tests throughout the file:

 - Remove spurious blank lines.

 - Indent the test body.

 - Make sure that all lines end with &&, to make it easier to spot
   breaks in the chain.

 - When executing something in a subshell, put the parenthesis on
   separate lines and indent the body.  Also make sure that the
   first statement in the subshell is a 'cd'.

 - When redirecting input or output, do not use SP between
   redirection operator and the target filename.

 - Use the <<-\EOF and <<-EOF forms of heredoc, not <<EOF, when the
   command is indented and the heredoc text itself does not have to
   have a leading tab.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/t5505-remote: test push-refspec in branches-file

The test "migrate a remote from named file in $GIT_DIR/branches" reads
the branches-file, but only checks that the url and fetch-refspec are
set correctly.  Check that the push-refspec is also set correctly.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/t5505-remote: use test_path_is_missing

Replace instances of ! test -f with test_path_is_missing.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
remote: remove dead code in read_branches_file()

The first line of the function checks that the remote-name contains a
slash ('/'), and sets the "slash" variable accordingly.  The only caller
of read_branches_file() is remote_get_1(); the calling codepath is
guarded by valid_remote_nick(), which checks that the remote does not
contain a slash.  Therefore, the "slash" variable can never be set:
remove the dead code that assumes otherwise.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>