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>
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.  The most important one is the second from the tip
done by Thomas.

Will merge to 'next'.

* jc/merge-bases:
  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