in_merge_bases(): support only one "other" commit

In early days of its life, I planned to make it possible to compute
"is a commit contained in all of these other commits?" with this
function, but it turned out that no caller needed it.

Just make it take two commit objects and add a comment to say what
these two functions do.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
receive-pack: use in_merge_bases() for fast-forward check

The original computed merge-base between the old commit and the new
commit and checked if the old commit was a merge base between them,
in order to make sure we are fast-forwarding.

Instead, call in_merge_bases(old, new) which does the same.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
http-push: use in_merge_bases() for fast-forward check

The original computed merge-base between HEAD and the remote ref and
checked if the remote ref is a merge base between them, in order to
make sure that we are fast-forwarding.

Instead, call in_merge_bases(remote, HEAD) which does the same.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
in_merge_bases(): omit unnecessary redundant common ancestor reduction

The function get_merge_bases() needs to postprocess the result from
merge_bases_many() in order to make sure none of the commit is a
true ancestor of another commit, which is expensive.  However, when
checking if a commit is an ancestor of another commit, we only need
to see if the commit is a common ancestor between the two, and do
not have to care if other common ancestors merge_bases_many() finds
are true merge bases or an ancestor of another merge base.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
merge_bases_many(): split out the logic to paint history

Introduce a new helper function paint_down_to_common() that takes
the same parameters as merge_bases_many(), but without the first
optimization of not painting anything when "one" is one of the
"twos" (or vice versa), and the last clean-up of removing the common
ancestor that is known to be an ancestor of another common one.

This way, the caller of the new function could tell if "one" is
reachable from any of the "twos" by simply looking at the flag bits
of "one".  If (and only if) it is painted in PARENT2, it is
reachable from one of the "twos".

Signed-off-by: Junio C Hamano <gitster@pobox.com>
in_merge_bases(): use paint_down_to_common()

With paint_down_to_common(), we can tell if "commit" is reachable
from "reference" by simply looking at its object flag, instead of
iterating over the merge bases.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
get_merge_bases_many(): walk from many tips in parallel

The get_merge_bases_many() function reduces the result returned by
the merge_bases_many() function, which is a set of possible merge
bases, by excluding commits that can be reached from other commits.
We used to do N*(N-1) traversals for this, but we can check if one
commit reaches which other (N-1) commits by a single traversal, and
repeat it for all the candidates to find the answer.

Introduce remove_redundant() helper function to do this painting; we
should be able to use it to reimplement reduce_heads() as well.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
merge-base: "--is-ancestor A B"

In many scripted Porcelain commands, we find this idiom:

    if test "$(git rev-parse --verify A)" = "$(git merge-base A B)"
    then
    	... A is an ancestor of B ...
    fi

But you do not have to compute exact merge-base only to see if A is
an ancestor of B.  Give them a more direct way to use the underlying
machinery.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
reduce_heads(): reimplement on top of remove_redundant()

This is used by "git merge" and "git merge-base --independent" but
used to use a similar N*(N-1) traversals to reject commits that are
ancestors of other commits.

Reimplement it on top of remove_redundant().  Note that the callers
of this function are allowed to pass the same commit more than once,
but remove_redundant() is designed to be fed each commit only once.
The function removes duplicates before calling remove_redundant().

Signed-off-by: Junio C Hamano <gitster@pobox.com>
i18n: mark more index-pack strings for translation

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
split_ident_line(): make best effort when parsing author/committer line

Commits made by ancient version of Git allowed committer without
human readable name, like this (00213b17c in the kernel history):

    tree 6947dba41f8b0e7fe7bccd41a4840d6de6a27079
    parent 352dd1df32e672be4cff71132eb9c06a257872fe
    author Petr Baudis <pasky@ucw.cz> 1135223044 +0100
    committer  <sam@mars.ravnborg.org> 1136151043 +0100

    kconfig: Remove support for lxdialog --checklist

    ...

    Signed-off-by: Petr Baudis <pasky@suse.cz>
    Signed-off-by: Sam Ravnborg <sam@ravnborg.org>

When fed such a commit, --format='%ci' fails to parse it, and gives
back an empty string.  Update the split_ident_line() to be a bit
more lenient when parsing, but make sure the caller that wants to
pick up sane value from its return value does its own validation.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
test-regex: Add a test to check for a bug in the regex routines

Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
argv-array: add pop function

Sometimes we build a set of similar command lines, differing
only in the final arguments (e.g., "fetch --multiple"). To
use argv_array for this, you have to either push the same
set of elements repeatedly, or break the abstraction by
manually manipulating the array's internal members.

Instead, let's provide a sanctioned "pop" function to remove
elements from the end.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
argv-array: fix bogus cast when freeing array

Since the array struct stores a "const char **" argv member
(for compatibility with most of our argv-taking functions),
we have to cast away the const-ness when freeing its
elements.

However, we used the wrong type when doing so.  It doesn't
make a difference since free() take a void pointer anyway,
but it can be slightly confusing to a reader.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fetch: use argv_array instead of hand-building arrays

Fetch invokes itself recursively when recursing into
submodules or handling "fetch --multiple". In both cases, it
builds the child's command line by pushing options onto a
statically-sized array. In both cases, the array is
currently just big enough to handle the largest possible
case. However, this technique is brittle and error-prone, so
let's replace it with a dynamic argv_array.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
submodule: use argv_array instead of hand-building arrays

fetch_populated_submodules() allocates the full argv array it uses to
recurse into the submodules from the number of given options plus the six
argv values it is going to add. It then initializes it with those values
which won't change during the iteration and copies the given options into
it. Inside the loop the two argv values different for each submodule get
replaced with those currently valid.

However, this technique is brittle and error-prone (as the comment to
explain the magic number 6 indicates), so let's replace it with an
argv_array. Instead of replacing the argv values, push them to the
argv_array just before the run_command() call (including the option
separating them) and pop them from the argv_array right after that.

Signed-off-by: Jens Lehmann <Jens.Lehmann@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'nd/i18n-index-pack' into next

* nd/i18n-index-pack:
  i18n: mark more index-pack strings for translation
Merge branch 'jc/merge-bases' into next

Optimise the "merge-base" computation a bit, and also update its
users that do not need the full merge-base information to call a
cheaper subset.

* jc/merge-bases:
  reduce_heads(): reimplement on top of remove_redundant()
  merge-base: "--is-ancestor A B"
  get_merge_bases_many(): walk from many tips in parallel
  in_merge_bases(): use paint_down_to_common()
  merge_bases_many(): split out the logic to paint history
  in_merge_bases(): omit unnecessary redundant common ancestor reduction
  http-push: use in_merge_bases() for fast-forward check
  receive-pack: use in_merge_bases() for fast-forward check
  in_merge_bases(): support only one "other" commit

Conflicts:
	builtin/merge-base.c
Merge branch 'jc/maint-ident-missing-human-name' into next

"git show --format='%ci'" did not give timestamp correctly for
commits created without human readable name on "committer" line.

* jc/maint-ident-missing-human-name:
  split_ident_line(): make best effort when parsing author/committer line
Merge branch 'jk/argv-array' into next

Use argv-array API in "git fetch" implementation.

* jk/argv-array:
  submodule: use argv_array instead of hand-building arrays
  fetch: use argv_array instead of hand-building arrays
  argv-array: fix bogus cast when freeing array
  argv-array: add pop function