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>
Merge branch 'er/doc-fast-import-done' into pu

Parked in 'pu' in case ESR responds with "Sorry, forgot to sign-off".

* er/doc-fast-import-done:
  fast-import: document the --done option
Merge branch 'jx/test-real-path' into pu

Running tests with the "trash" directory elsewhere with the "--root"
option did not work well if the directory was specified by a symbolic
link pointing at it.

Seems broken as it makes $(pwd) and TRASH_DIRECTORY inconsistent.
Needs rerolling.

* jx/test-real-path:
  test: set the realpath of CWD as TRASH_DIRECTORY
Merge branch 'jc/add-delete-default' into pu

"git add dir/" updated modified files and added new files, but does
not notice removed files, which may be "Huh?" to some users.  They
can of course use "git add -A dir/", but why should they?

Resurrected from graveyard, as I thought it was a worthwhile thing
to do in the longer term; waiting for comments.

* jc/add-delete-default:
  git add: notice removal of tracked paths by default
Merge branch 'tx/relative-in-the-future' into pu

Not my itch; rewritten an earlier submission by Tom Xue into
somewhat more maintainable form, though it breaks existing i18n.

Anybody interested in fixing it up?  Otherwise may discard.

* tx/relative-in-the-future:
  date: show relative dates in the future
  date: refactor the relative date logic from presentation
Merge branch 'jk/no-more-pre-exec-callback' into pu

(Originally merged to 'next' on 2012-07-23)

Will defer until the end of the 2012.
while waiting for older "less" to go extinct.

* jk/no-more-pre-exec-callback:
  pager: drop "wait for output to run less" hack
Merge branch 'jc/maint-push-refs-all' into pu

Allows pushing and fetching refs/stash.

* jc/maint-push-refs-all:
  get_fetch_map(): tighten checks on dest refs
  [BROKEN] fetch/push: allow refs/*:refs/*
Merge branch 'ph/credential-gnome-keyring' into pu

The later refactoring of the shared code in the original series may
not be worth the trouble, so it is split into a separate topic that
builds on top of this one, which independently should be useful.

Will merge to 'next'.

* ph/credential-gnome-keyring:
  contrib: add credential helper for GnomeKeyring
Merge branch 'mh/fetch-filter-refs' into pu

Code simplification and clarification.
Waiting for a follow-up patch based on Peff's idea.

* mh/fetch-filter-refs:
  filter_refs(): simplify logic
  fetch_pack(): free matching heads
  cmd_fetch_pack(): simplify computation of return value
  fetch-pack: report missing refs even if no existing refs were received
  cmd_fetch_pack: return early if finish_connect() returns an error
  filter_refs(): compress unmatched refs in heads array
  filter_refs(): do not leave gaps in return_refs
  filter_refs(): simplify by removing optimization
  Pass nr_heads to filter_refs() by reference
  Pass nr_heads to everything_local() by reference
  Pass nr_heads to do_pack_ref() by reference
  Let fetch_pack() inform caller about number of unique heads
  filter_refs(): do not check the same head_pos twice
  fetch-pack.c: name local variables more consistently
  fetch_pack(): reindent function decl and defn
  Rename static function fetch_pack() to http_fetch_pack()
  t5500: add tests of error output for missing refs

Conflicts:
	builtin/fetch-pack.c
Merge branch 'pw/p4-submit-conflicts' into pu

Waiting for the dust to settle.

* pw/p4-submit-conflicts:
  git p4: add submit --prepare-p4-only option
  git p4: add submit --dry-run option
  git p4: accept -v for --verbose
  git p4: revert deleted files after submit cancel
  git p4: rearrange submit template construction
  git p4: test clean-up after failed submit, fix added files
  git p4: standardize submit cancel due to unchanged template
  git p4: move conflict prompt into run, use [c]ontinue and [q]uit
  git p4: remove submit failure options [a]pply and [w]rite
  git p4: gracefully fail if some commits could not be applied
  git p4 test: use p4d -L option to suppress log messages
  git p4 test: remove bash-ism of combined export/assignment
Merge branch 'cn/branch-set-upstream-to' into pu

"git branch --set-upstream origin/master" is a common mistake to
create a local branch 'origin/master' and set it to integrate with
the current branch.  With a plan to deprecate this option, introduce
"git branch (-u|--set-upstream-to) origin/master" that sets the
current branch to integrate with 'origin/master' remote tracking
branch.

Will merge to 'next'.

* cn/branch-set-upstream-to:
  branch: deprecate --set-upstream and show help if we detect possible mistaken use
  branch: add --unset-upstream option
  branch: introduce --set-upstream-to

Conflicts:
	builtin/branch.c
Merge branch 'nd/checkout-option-parsing-fix' into pu

The option parsing of "git checkout" had error checking, dwim and
defaulting missing options, all mixed in the code, and issuing an
appropriate error message with useful context was getting harder.
Reorganize the code and allow giving a proper diagnosis when the
user says "git checkout -b -t foo bar" (e.g. "-t" is not a good name
for a branch).

* nd/checkout-option-parsing-fix:
  checkout: reorder option handling
  checkout: move more parameters to struct checkout_opts
  checkout: pass "struct checkout_opts *" as const pointer

Conflicts:
	builtin/checkout.c
Merge branch 'mz/cherry-pick-cmdline-order' into pu

"git cherry-pick A C B" used to replay changes in A and then B and
then C if these three commits had committer timestamps in that
order, which is not what the user who said "A C B" naturally expects.

Will merge to 'next'.

* mz/cherry-pick-cmdline-order:
  cherry-pick/revert: respect order of revisions to pick
  demonstrate broken 'git cherry-pick three one two'
  teach log --no-walk=unsorted, which avoids sorting

Conflicts:
	Documentation/rev-list-options.txt
Merge branch 'jc/merge-bases' into pu

Optimises the "merge-base" computation a bit, and also updates 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

Conflicts:
	builtin/merge-base.c
Merge branch 'fa/remote-svn' into pu

Waiting for comments from mentors and stakeholders.

* fa/remote-svn:
  Add a test script for remote-svn
  remote-svn: add marks-file regeneration
  Add a svnrdump-simulator replaying a dump file for testing
  remote-svn: add incremental import
  remote-svn: Activate import/export-marks for fast-import
  Create a note for every imported commit containing svn metadata
  vcs-svn: add fast_export_note to create notes
  Allow reading svn dumps from files via file:// urls
  remote-svn, vcs-svn: Enable fetching to private refs
  When debug==1, start fast-import with "--stats" instead of "--quiet"
  Add documentation for the 'bidi-import' capability of remote-helpers
  Connect fast-import to the remote-helper via pipe, adding 'bidi-import' capability
  Add argv_array_detach and argv_array_free_detached
  Add svndump_init_fd to allow reading dumps from arbitrary FDs
  Add git-remote-testsvn to Makefile and .gitignore
  Implement a remote helper for svn in C
Merge branch 'fa/vcs-svn' into pu

Waiting for comments from mentors and stakeholders.

* fa/vcs-svn:
  vcs-svn: remove repo_tree
  vcs-svn/svndump: rewrite handle_node(), begin|end_revision()
  vcs-svn/svndump: restructure node_ctx, rev_ctx handling
  svndump: move struct definitions to .h
Merge branch 'jc/maint-name-rev' into pu

"git name-rev" names the given revision based on a ref that can be
reached in the smallest number of steps from the rev, but that is
not useful when the caller wants to know which tag is the oldest one
that contains the rev.  This teaches a new mode to the command that
uses the oldest ref among those which contain the rev.

I am not sure if this is worth it; for one thing, even with the help
from notes-cache, it seems to make the "describe --contains" even
slower. Also the command will be unusably slow for a user who does
not have a write access (hence unable to create or update the
notes-cache).

* jc/maint-name-rev:
  describe --contains: use "name-rev --weight"
  name-rev --weight: tests and documentation
  name-rev --weight: cache the computed weight in notes
  name-rev: --weight option
  name_rev: clarify the logic to assign a new tip-name to a commit
  name-rev: lose unnecessary typedef

Conflicts:
	builtin/name-rev.c
Merge branch 'jl/submodule-rm' into pu

"git rm submodule" cannot blindly remove a submodule directory as
its working tree may have local changes, and worse yet, it may even
have its repository embedded in it.  Teach it some special cases
where it is safe to remove a submodule, specifically, when there is
no local changes in the submodule working tree, and its repository
is not embedded in its working tree but is elsewhere and uses the
gitfile mechanism to point at it.

* jl/submodule-rm:
  Teach rm to remove submodules unless they contain a git directory
Merge branch 'js/compat-itimer' into pu

Pieces to support compilation on __TANDEM.

* js/compat-itimer:
  Support for setitimer() on platforms lacking it

Conflicts:
	git-compat-util.h
Merge branch 'mb/remote-default-nn-origin' into pu

When the user does not specify what remote to interact with, we
often attempt to use 'origin'.  This can now be customized via a
configuration variable.

Expecting a reroll.

"The first remote becomes the default" bit is better done as a
separate step.

* mb/remote-default-nn-origin:
  Teach get_default_remote to respect remote.default.
  Test that plain "git fetch" uses remote.default when on a detached HEAD.
  Teach clone to set remote.default.
  Teach "git remote" about remote.default.
  Teach remote.c about the remote.default configuration setting.
  Rename remote.c's default_remote_name static variables.

Conflicts:
	builtin/remote.c
	t/t5505-remote.sh