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>
test-lib: enable MALLOC_* for the actual tests

1b3185f (MALLOC_CHECK: various clean-ups, 2012-09-14) moved around the
MALLOC_CHECK_ and MALLOC_PERTURB_ assignments, intending to limit
their effect to only the test runs.  However, they were actually
enabled only during test cleanup.  Call setup/teardown_malloc_check
also around the evaluation of the actual test snippet.

Signed-off-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t7401: make indentation consistent

Only leading whitespace is changed in this patch.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t7403: modernize style

Change the indentation to use tabs consistently and start content on the
line after the paren opening a subshell.

Also don't put a space in ">file" and remove ":" from ": >file" to be
consistent with the majority of tests elsewhere.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t7403: add missing && chaining

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
submodule: show full path in error message

When --recursive was added to "submodule foreach" in commit 15fc56a (git
submodule foreach: Add --recursive to recurse into nested submodules,
2009-08-19), the error message when the script returns a non-zero status
was not updated to contain $prefix to show the full path.  Fix this.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rev-parse: add --prefix option

This makes 'git rev-parse' behave as if it were invoked from the
specified subdirectory of a repository, with the difference that any
file paths which it prints are prefixed with the full path from the top
of the working tree.

This is useful for shell scripts where we may want to cd to the top of
the working tree but need to handle relative paths given by the user on
the command line.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
submodule: drop the top-level requirement

Use the new rev-parse --prefix option to process all paths given to the
submodule command, dropping the requirement that it be run from the
top-level of the repository.

Since the interpretation of a relative submodule URL depends on whether
or not "remote.origin.url" is configured, explicitly block relative URLs
in "git submodule add" when not at the top level of the working tree.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test-lib: refactor $GIT_SKIP_TESTS matching

It's already used twice, and we will have more of the same kind of
matching in a minute.

Helped-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test-lib: rearrange start/end of test_expect_* and test_skip

This moves

* the early setup part from test_skip to a new function test_start_

* the final common parts of test_expect_* to a new function
  test_finish_

to make the next commit more obvious.

Signed-off-by: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
name-rev: allow to specify a subpath for --refs option

When an user wants to filter specific ref using the --refs option,
the pattern needs to match the full ref, e.g. --refs=refs/tags/v1.*.

It'd be convenient to specify a subpath of ref pattern.  For
example, --refs=origin/* can find refs/remotes/origin/master by
searching the pattern against its substrings in turn:

  refs/remotes/origin/master
  remotes/origin/master
  origin/master

If it finds a match in a subpath, unambigous part of the ref path will
be removed in the output.

Signed-off-by: Namhyung Kim <namhyung.kim@lge.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
resolve_ref_unsafe(): extract function handle_missing_loose_ref()

The nesting was getting a bit out of hand, and it's about to get
worse.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
resolve_ref_unsafe(): handle the case of an SHA-1 within loop

There is only one "break" statement within the loop, which jumps to
the code after the loop that handles the case of a file that holds a
SHA-1.  So move that code from below the loop into the if statement
where the break was previously located.  This makes the logic flow
more local.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
resolve_ref_unsafe(): close race condition reading loose refs

We read loose references in two steps.  The code is roughly:

    lstat()
    if error ENOENT:
        loose ref is missing; look for corresponding packed ref
    else if S_ISLNK:
        readlink()
        if error:
            report failure
    else if S_ISDIR:
        report failure
    else
        open()
        if error:
            report failure
        read()

The problem is that the first filesystem call, to lstat(), is not
atomic with the second filesystem call, to readlink() or open().
Therefore it is possible for another process to change the file
between our two calls, for example:

* If the other process deletes the file, our second call will fail
  with ENOENT, which we *should* interpret as "loose ref is missing;
  look for corresponding packed ref".  This can arise if the other
  process is pack-refs; it might have just written a new packed-refs
  file containing the old contents of the reference then deleted the
  loose ref.

* If the other process changes a symlink into a plain file, our call
  to readlink() will fail with EINVAL, which we *should* respond to by
  trying to open() and read() the file.

The old code treats the reference as missing in both of these cases,
which is incorrect.

So instead, handle errors more selectively: if the result of
readline()/open() is a failure that is inconsistent with the result of
the previous lstat(), then something is fishy.  In this case jump back
and start over again with a fresh call to lstat().

One race is still possible and undetected: another process could
change the file from a regular file into a symlink between the call to
lstat and the call to open().  The open() call would silently follow
the symlink and not know that something is wrong.  This situation
could be detected in two ways:

* On systems that support O_NOFOLLOW, pass that option to the open().

* On other systems, call fstat() on the fd returned by open() and make
  sure that it agrees with the stat info from the original lstat().

However, we don't use symlinks anymore, so this situation is unlikely.
Moreover, it doesn't appear that treating a symlink as a regular file
would have grave consequences; after all, this is exactly how the code
handles non-relative symlinks.  So this commit leaves that race
unaddressed.

Note that this solves only the part of the race within
resolve_ref_unsafe. In the situation described above, we may still be
depending on a cached view of the packed-refs file; that race will be
dealt with in a future patch.

This problem was reported and diagnosed by Jeff King <peff@peff.net>,
and this solution is derived from his patch.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>