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>
sequencer: remove useless indentation

By using good ol' goto.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sequencer: avoid leaking message buffer when refusing to create an empty commit

We should free objects before leaving.

Signed-off-by: Felipe Contreras <felipe.contreras@gmail.com>
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>
finish_copy_notes_for_rewrite(): Let caller provide commit message

When copying notes for a rewritten object, the resulting notes commit
would have the following hardcoded commit message:

  Notes added by 'git notes copy'

This is obviously bogus when the notes rewriting is performed by
'git commit --amend'.

Therefore, let the caller specify an appropriate notes commit message
instead of hardcoding it. The above message is used for 'git notes copy',
but when calling finish_copy_notes_for_rewrite() from builtin/commit.c,
we use the following message instead:

  Notes added by 'git commit --amend'

Cc: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Move copy_note_for_rewrite + friends from builtin/notes.c to notes-utils.c

This is a pure code movement of the machinery for copying notes to
rewritten objects. This code was located in builtin/notes.c for
historical reasons. In order to make it available to builtin/commit.c
it was declared in builtin.h. This was more of an accident of history
than a concious design, and we now want to make this machinery more
widely available.

Hence, this patch moves the code into the new notes-utils.[hc] files
which are included into libgit.a. Except for adjusting #includes
accordingly, this patch merely moves the relevant functions verbatim
into the new files.

Cc: Thomas Rast <trast@inf.ethz.ch>
Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Move create_notes_commit() from notes-merge.c into notes-utils.c

create_notes_commit() is needed by both the notes-merge code, and by
commit_notes() in notes-utils. Since it is generally useful, and not
bound to the notes-merge machinery, we move it from (the more specific)
notes-merge to (the more general) notes-utils.

Signed-off-by: Johan Herland <johan@herland.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add--interactive: respect diff.algorithm

When staging hunks interactively it is sometimes useful to use an
alternative diff algorithm which splits the changes into hunks in a more
logical manner.  This is not possible because the plumbing commands
called by add--interactive ignore the "diff.algorithm" configuration
option (as they should).

Since add--interactive is a porcelain command it should respect this
configuration variable.  To do this, make it read diff.algorithm and
pass its value to the underlying diff-index and diff-files invocations.

At this point, do not add options to "git add", "git reset" or "git
checkout" (all of which can call git-add--interactive).  If a user
wants to override the value on the command line they can use:

	git -c diff.algorithm=$ALGO ...

Signed-off-by: John Keeping <john@keeping.me.uk>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rm: better error message on failure for multiple files

When 'git rm' fails, it now displays a single message
with the list of files involved, instead of displaying
a list of messages with one file each.

As an example, the old message:
	error: 'foo.txt' has changes staged in the index
	(use --cached to keep the file, or -f to force removal)
	error: 'bar.txt' has changes staged in the index
	(use --cached to keep the file, or -f to force removal)

would now be displayed as:
	error: the following files have changes staged in the index:
	    foo.txt
	    bar.txt
	(use --cached to keep the file, or -f to force removal)

Signed-off-by: Mathieu Lienard--Mayor <Mathieu.Lienard--Mayor@ensimag.imag.fr>
Signed-off-by: Jorge Juan Garcia Garcia <Jorge-Juan.Garcia-Garcia@ensimag.imag.fr>
Signed-off-by: Matthieu Moy <Matthieu.Moy@grenoble-inp.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rm: introduce advice.rmHints to shorten messages

Introduce advice.rmHints to choose whether to display advice or not
when git rm fails. Defaults to true, in order to preserve current behavior.

As an example, the message:
	error: 'foo.txt' has changes staged in the index
	(use --cached to keep the file, or -f to force removal)

would look like, with advice.rmHints=false:
	error: 'foo.txt' has changes staged in the index

Signed-off-by: Mathieu Lienard--Mayor <Mathieu.Lienard--Mayor@ensimag.imag.fr>
Signed-off-by: Jorge Juan Garcia Garcia <Jorge-Juan.Garcia-Garcia@ensimag.imag.fr>
Signed-off-by: Matthieu Moy <Matthieu.Moy@grenoble-inp.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
handle multibyte characters in name

Many "git submodule" operations do not work on a submodule at a path whose
name is not in ASCII.

This is because "git ls-files" is used to find which paths are bound to
submodules to the current working tree, and the output is C-quoted by default
for non ASCII pathnames.

Tell "git ls-files" to not C-quote its output, which is easier than unwrapping
C-quote ourselves.

Signed-off-by: Fredrik Gustafsson <iveqy@iveqy.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/rebase: add failing tests for a peculiar revision

The following commands fail, even if :/quuxery and :/foomery resolve to
perfectly valid commits:

  $ git rebase [-i] --onto :/quuxery :/foomery

This is because rebase [-i] attempts to rev-parse ${REV}^0 to verify
that the given revision resolves to a commit.  Add tests to document
these failures.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
sh-setup: add new peel_committish() helper

The normal way to check whether a certain revision resolves to a valid
commit is:

  $ git rev-parse --verify $REV^0

Unfortunately, this does not work when $REV is of the type :/quuxery.
Write a helper to work around this limitation.

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rebase: use peel_committish() where appropriate

The revisions specified on the command-line as <onto> and <upstream>
arguments could be of the form :/quuxery; so, use peel_committish() to
resolve them.  The failing tests in t/rebase and t/rebase-interactive
now pass.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
am: handle stray $dotest directory

The following bug has been observed:

  $ git am  # no input file
  ^C
  $ git am --abort
  Resolve operation not in progress, we are not resuming.

This happens because the following test fails:

  test -d "$dotest" && test -f "$dotest/last" && test -f "$dotest/next"

and the codepath for an "am in-progress" is not executed.  It falls back
to the codepath that treats this as a "fresh execution".  Before
rr/rebase-autostash, this condition was

  test -d "$dotest"

It would incorrectly execute the "normal" am --abort codepath:

  git read-tree --reset -u HEAD ORIG_HEAD
  git reset ORIG_HEAD

by incorrectly assuming that an am is "in progress" (i.e. ORIG_HEAD
etc. was written during the previous execution).

Notice that

  $ git am
  ^C

executes nothing of significance, is equivalent to

  $ mkdir .git/rebase-apply

Therefore, the correct solution is to treat .git/rebase-apply as a
"stray directory" and remove it on --abort in the fresh-execution
codepath.  Also ensure that we're not called with --rebasing from
git-rebase--am.sh; in that case, it is the responsibility of the caller
to handle and stray directories.

While at it, tell the user to run "git am --abort" to get rid of the
stray $dotest directory, if she attempts anything else.

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