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>
config: refactor management of color.ui's default value

The meaning of get_colorbool_found and get_diff_color_found is "the
config value if found, and -1 otherwise", but get_color_ui_found had a
slightly different meaning, as it has the value 0 (which corresponds to
the default value from the user point of view) when color.ui is unset.

Make get_color_ui_found default to -1, and make it explicit that 0 is the
default value when nothing else is found.

Signed-off-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Makefile: promote wildmatch to be the default fnmatch implementation

This makes git use wildmatch by default for all fnmatch() calls. Users
who want to use system fnmatch (or compat fnmatch) need to set
NO_WILDMATCH flag.

wildmatch is a drop-in fnmatch replacement with more features. Using
wildmatch gives us a consistent behavior across platforms. The
tentative plan is make it default with an opt-out for about 2 cycles,
then remove NO_WILDMATCH and compat/fnmatch.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test-chmtime: Fix exit code on Windows

MinGW's bash does not recognize an exit code -1 as failure. See also
47e3de0e (MinGW: truncate exit()'s argument to lowest 8 bits) and 2488df84
(builtin run_command: do not exit with -1). Exit code 1 is good enough.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
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>
add simple tests of consistency across rebase types

Helped-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Martin von Zweigbergk <martinvonz@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add tests for rebasing with patch-equivalence present

Signed-off-by: Martin von Zweigbergk <martinvonz@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add tests for rebasing of empty commits

Signed-off-by: Martin von Zweigbergk <martinvonz@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add tests for rebasing root

Signed-off-by: Martin von Zweigbergk <martinvonz@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
add tests for rebasing merged history

Signed-off-by: Martin von Zweigbergk <martinvonz@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t3406: modernize style

Update the following:

 - Quote 'setup'
 - Remove blank lines within test case body
 - Use test_commit instead of custom quick_one
 - Create branch "topic" from tag created by test_commit

Signed-off-by: Martin von Zweigbergk <martinvonz@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: move test for rebase messages from t3400 to t3406

t3406 is supposed to test "messages from rebase operation", so let's
move tests in t3400 that fit that description into 3406. Most of the
functionality they tested, except for the messages, has now been
subsumed by t3420.

Signed-off-by: Martin von Zweigbergk <martinvonz@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>
t3010: modernize style

In particular:

- move test preparations inside test_expect_success

- place test description on the test_expect_success line

- indent with a tab

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: introduce test_ln_s_add

Add a new function that creates a symbolic link and adds it to the index
to be used in cases where a symbolic link is not required on the file
system. We will use it to remove many SYMLINKS prerequisites from test
cases.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: use test_ln_s_add to remove SYMLINKS prerequisite (trivial cases)

There are many instances where the treatment of symbolic links in the
object model and the algorithms are tested, but where it is not
necessary to actually have a symbolic link in the worktree. Make
adjustments to the tests and remove the SYMLINKS prerequisite when
appropriate in trivial cases, where "trivial" means:

- merely a replacement of 'ln -s a b && git add b' by test_ln_s_add
  is needed;

- a test for symbolic link on the file system can be split off (and
  remains protected by SYMLINKS);

- existing code is equivalent to test_ln_s_add.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t0000: use test_ln_s_add to remove SYMLINKS prerequisite

t0000-basic hard-codes many object IDs. To cater to file systems that do
not support symbolic links, different IDs are used depending on the
SYMLINKS prerequisite. But we can observe the symbolic links are only
needed to generate index entries. Use test_ln_s_add to generate the
index entries and get rid of explicit SYMLINKS checks.

This undoes the special casing introduced in this test by 704a3143
(Use prerequisite tags to skip tests that depend on symbolic links,
2009-03-04).

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t3030: use test_ln_s_add to remove SYMLINKS prerequisite

The test cases include many corner-cases of merge-recursive's behavior,
some of them involve type changes and symbolic links. All cases, including
those that are protected by SYMLINKS check only whether the result of
merge-recursive is correctly stored in the database and the index; the
file system is not investigated. Use test_ln_s_add to enter a symbolic
link in the index in the test setup and run the tests without the
SYMLINKS prerequisite.

Notice that one test that has the SYMLINKS protection removed is an
expect_failure. There is a possibility that the test fails differently
depending on whether SYMLINKS is present or not; but this is not the case
presently.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>