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,

	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 "stride" variant.

Suppose you want to give one bit per existing ref and paint commits
down to find which refs are descendants of each commit. You find
that you have 320 refs only at runtime.

The code can declare a commit slab "struct flagbits"

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

and initialize it by:

	nrefs = ... count number of refs that returns say 320 ...
	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.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
doc/http-backend: match query-string in apache half-auth example

When setting up a "half-auth" repository in which reads can
be done anonymously but writes require authentication, it is
best if the server can require authentication for both the
ref advertisement and the actual receive-pack POSTs. This
alleviates the need for the admin to set http.receivepack in
the repositories, and means that the client is challenged
for credentials immediately, instead of partway through the
push process (and git clients older than v1.7.11.7 had
trouble handling these challenges).

Since detecting a push during the ref advertisement requires
matching the query string, and this is non-trivial to do in
Apache, we have traditionally punted and instructed users to
just protect "/git-receive-pack$".  This patch provides the
mod_rewrite recipe to actually match the ref advertisement,
which is preferred.

While we're at it, let's add the recipe to our test scripts
so that we can be sure that it works, and doesn't get broken
(either by our changes or by changes in Apache).

Signed-off-by: Jeff King <peff@peff.net>
Acked-by: Jakub Narębski <jnareb@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add public function read_blob_data_from_index_path()

* Make the read_index_data() function public, rename it to
  read_blob_data_from_index_path() and move it from attr.c to
  read-cache.c.

* Add a use_index parameter to specify a custom index_state since we are
  no longer enable to access the static use_index variable from attr.c.

This allows for reusing the function in convert.c later.

Signed-off-by: Lukas Fleischer <git@cryptocrack.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'tr/packed-object-info-wo-recursion' into jch

Attempts to reduce the stack footprint of sha1_object_info()
and unpack_entry() codepaths.

* tr/packed-object-info-wo-recursion:
  sha1_file: remove recursion in unpack_entry
  Refactor parts of in_delta_base_cache/cache_or_unpack_entry
  sha1_file: remove recursion in packed_object_info
Merge branch 'tr/line-log' (early part) into jch

* 'tr/line-log' (early part):
  log -L: fix overlapping input ranges
  log -L: check range set invariants when we look it up
  Speed up log -L... -M
  log -L: :pattern:file syntax to find by funcname
  Implement line-history search (git log -L)
  Export rewrite_parents() for 'log -L'
  Refactor parse_loc

Conflicts:
	log-tree.c
Merge branch 'kb/status-ignored-optim' into jch

"git status --ignored" had many corner case bugs.  Also the command
has been optimized by taking advantage of the fact that paths that
are already known to the index do not have to be checked against
the .gitignore mechanism most of the time.

This codepath is used not only by status but also in add and clean,
so a bug in it can result in lost data.  Extra sets of eyeballs are
very much appreciated.

* kb/status-ignored-optim:
  dir.c: git-status: avoid is_excluded checks for tracked files
  dir.c: replace is_path_excluded with now equivalent is_excluded API
  dir.c: unify is_excluded and is_path_excluded APIs
  dir.c: move prep_exclude and factor out parts of last_exclude_matching
  dir.c: git-status --ignored: don't list empty directories as ignored
  dir.c: git-status --ignored: don't list empty ignored directories
  dir.c: git-status --ignored: don't list files in ignored directories
  dir.c: git-status --ignored: don't drop ignored directories
Merge branch 'jc/push-2.0-default-to-simple' (early part) into jch

* 'jc/push-2.0-default-to-simple' (early part):
  t5570: do not assume the "matching" push is the default
  t5551: do not assume the "matching" push is the default
  t5550: do not assume the "matching" push is the default
  t9401: do not assume the "matching" push is the default
  t9400: do not assume the "matching" push is the default
  t7406: do not assume the "matching" push is the default
  t5531: do not assume the "matching" push is the default
  t5519: do not assume the "matching" push is the default
  t5517: do not assume the "matching" push is the default
  t5516: do not assume the "matching" push is the default
  t5505: do not assume the "matching" push is the default
  t5404: do not assume the "matching" push is the default

Conflicts:
	t/t5516-fetch-push.sh
Merge branch 'jc/add-2.0-delete-default' (early part) into jch

* 'jc/add-2.0-delete-default' (early part):
  git add: start preparing for "git add <pathspec>..." to default to "-A"
  builtin/add.c: simplify boolean variables
Merge branch 'jn/add-2.0-u-A-sans-pathspec' (early part) into jch

* 'jn/add-2.0-u-A-sans-pathspec' (early part):
  add -A: only show pathless 'add -A' warning when changes exist outside cwd
  add -u: only show pathless 'add -u' warning when changes exist outside cwd
  add: make warn_pathless_add() a no-op after first call
  add: add a blank line at the end of pathless 'add [-u|-A]' warning
  add: make pathless 'add [-u|-A]' warning a file-global function

Conflicts:
	builtin/add.c
Merge branch 'mc/count-objects-kibibytes' into jch

The command reports the total diskspace used to store loose objects
in kibibytes, but it was labelled as "kilobytes".  The number now
is shown with "KiB", e.g. "6750 objects, 50928 KiB".

If you have scripts that decide when to run "git repack" by parsing
the output from "git count-objects", this release may break them.
Sorry about that.  One of the scripts shipped by git-core itself
also had to be adjusted.  You may want to consider updating such
scripts to always call "git gc --auto" to let it decide when to
repack for you.

* mc/count-objects-kibibytes:
  count-objects: output "KiB" instead of "kilobytes"
Merge branch 'tr/perl-keep-stderr-open' into jch

Closing (not redirecting to /dev/null) the standard error stream is
not a very smart thing to do.  Later open may return file
descriptor #2 for unrelated purpose, and error reporting code may
write into them.

* tr/perl-keep-stderr-open:
  t9700: do not close STDERR
  perl: redirect stderr to /dev/null instead of closing
Merge branch 'jk/diff-algo-finishing-touches' into jch

"git diff --diff-algorithm algo" is also understood as "git diff
--diff-algorithm=algo".

* jk/diff-algo-finishing-touches:
  diff: allow unstuck arguments with --diff-algorithm
  git-merge(1): document diff-algorithm option to merge-recursive
Merge branch 'jk/diff-graph-submodule-summary' into jch

Make "git diff --graph" work better with submodule log output.

* jk/diff-graph-submodule-summary:
  submodule: print graph output next to submodule log
Merge branch 'jk/http-error-messages' into jch

Improve error reporting from the http transfer clients.

* jk/http-error-messages:
  http: drop http_error function
  remote-curl: die directly with http error messages
  http: re-word http error message
  http: simplify http_error helper function
  remote-curl: consistently report repo url for http errors
  remote-curl: always show friendlier 404 message
  remote-curl: let servers override http 404 advice
  remote-curl: show server content on http errors
  http: add HTTP_KEEP_ERROR option
Merge branch 'jk/show-branch-strbuf' into jch

"git show-branch" was not prepared to show a very long run of
ancestor operators e.g. foobar^2~2^2^2^2...^2~4 correctly.

* jk/show-branch-strbuf:
  show-branch: use strbuf instead of static buffer
Merge branch 'lf/bundle-with-tip-wo-message' into jch

"git bundle" did not like a bundle created using a commit without
any message as its one of the prerequistes.

* lf/bundle-with-tip-wo-message:
  bundle: Accept prerequisites without commit messages
Merge branch 'rt/commentchar-fmt-merge-msg' into jch

The new core.commentchar configuration was not applied to a few
places.

* rt/commentchar-fmt-merge-msg:
  fmt-merge-msg: use core.commentchar in tag signatures completely
  fmt-merge-msg: respect core.commentchar in people credits
### match next