t1512: correct leftover constants from earlier edition

The earliest iteration of this test script used a magic string
110282 as the common prefix for ambiguous object names, but the
final edition switched the common prefix to 0000000000 (10 "0"s).

Unfortunately, instances of the original prefix were left in the
comments and a few tests.  Replace them with the correct constants.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
get_short_sha1(): correctly disambiguate type-limited abbreviation

One test in t1512 that expects a failure incorrectly passed.  The
test prepares a commit whose object name begins with ten "0"s, and
also prepares a tag that points at the commit.  The object name of
the tag also begins with ten "0"s.  There is no other commit-ish
object in the repository whose name begins with such a prefix.

Ideally, in such a repository:

    $ git rev-parse --verify 0000000000^{commit}

should yield that commit.  If 0000000000 is taken as the commit
0000000000e4f, peeling it to a commmit yields that commit itself,
and if 0000000000 is taken as the tag 0000000000f8f, peeling it to a
commit also yields the same commit, so in that twisted sense, the
extended SHA-1 expression 0000000000^{commit} is unambigous.  The
test that expects a failure is to check the above command.

The reason the test expects a failure is that we did not implement
such a "unification" of two candidate objects.  What we did (or at
least, meant to) implement was to recognise that a commit-ish is
required to expand 0000000000, and notice that there are two succh
commit-ish, and diagnose the request as ambiguous.

However, there was a bug in the logic to check the candidate
objects.  When the code saw 0000000000f8f (a tag) that shared the
shortened prefix (ten "0"s), it tried to make sure that the tag is a
commit-ish by looking at the tag object.  Because it incorrectly
used lookup_object() when the tag has not been parsed, however, we
incorrectly declared that the tag is _not_ a commit-ish, leaving the
sole commit in the repository, 0000000000e4f, that has the required
prefix as "unique match", causing the test to pass when it shouldn't.

This fixes the logic to inspect the type of the object a tag refers
to, to make the test that is expected to fail correctly fail.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
fetch-pack: avoid quadratic list insertion in mark_complete

We insert the commit pointed to by each ref one-by-one into
the "complete" commit_list using insert_by_date. Because
each insertion is O(n), we end up with O(n^2) behavior.

This typically doesn't matter, because the number of refs is
reasonably small. And even if there are a lot of refs, they
often point to a smaller set of objects (in which case the
optimization in commit ea5f220 keeps our "n" small).

However, in pathological repositories (hundreds of thousands
of refs, each pointing to a unique commit), this quadratic
behavior can make a difference. Since we do not care about
the list order until we have finished building it, we can
simply keep it unsorted during the insertion phase, then
sort it afterwards.

On a repository like the one described above, this dropped
the time to do a no-op fetch from 2.0s to 1.7s. On normal
repositories, it probably does not matter at all, but it
does not hurt to protect ourselves from pathological cases.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
commit.c: make compare_commits_by_commit_date global

This helper function was introduced as a prio_queue
comparator to help topological sorting. However, other users
of prio_queue who want to replace commit_list_insert_by_date
will want to use it, too. So let's make it public.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
fetch-pack: avoid quadratic behavior in rev_list_push

When we call find_common to start finding common ancestors
with the remote side of a fetch, the first thing we do is
insert the tip of each ref into our rev_list linked list. We
keep the list sorted the whole time with
commit_list_insert_by_date, which means our insertion ends
up doing O(n^2) timestamp comparisons.

We could teach rev_list_push to use an unsorted list, and
then sort it once after we have added each ref. However, in
get_rev, we process the list by popping commits off the
front and adding parents back in timestamp-sorted order. So
that procedure would still operate on the large list.

Instead, we can replace the linked list with a heap-based
priority queue, which can do O(log n) insertion, making the
whole insertion procedure O(n log n).

As a result of switching to the prio_queue struct, we fix
two minor bugs:

  1. When we "pop" a commit in get_rev, and when we clear
     the rev_list in find_common, we do not take care to
     free the "struct commit_list", and just leak its
     memory. With the prio_queue implementation, the memory
     management is handled for us.

  2. In get_rev, we look at the head commit of the list,
     possibly push its parents onto the list, and then "pop"
     the front of the list off, assuming it is the same
     element that we just peeked at. This is typically going
     to be the case, but would not be in the face of clock
     skew: the parents are inserted by date, and could
     potentially be inserted at the head of the list if they
     have a timestamp newer than their descendent. In this
     case, we would accidentally pop the parent, and never
     process it at all.

     The new implementation pulls the commit off of the
     queue as we examine it, and so does not suffer from
     this problem.

With this patch, a fetch of a single commit into a
repository with 50,000 refs went from:

  real    0m7.984s
  user    0m7.852s
  sys     0m0.120s

to:

  real    0m2.017s
  user    0m1.884s
  sys     0m0.124s

Before this patch, a larger case with 370K refs still had
not completed after tens of minutes; with this patch, it
completes in about 12 seconds.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Do not ignore merge options in interactive rebase

Merge strategy and its options can be specified in `git rebase`,
but with `--interactive`, they were completely ignored.

Signed-off-by: Arnaud Fontaine <arnau@debian.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
merge: handle --ff/--no-ff/--ff-only as a tri-state option

These three options mean "favor fast-forwarding when possible,
without creating an unnecessary merge", "never fast-forward and
always create a merge commit even when the commit being merged is a
strict descendant", and "we do not want to create any merge commit;
update only when the merged commit is a strict descendant".

They are "pick one out of these three possibilities" options, and
correspond to "merge.ff" configuration that is tri-state (yes, no
and only).

However, the implementation did not follow the usual convention for
the command line options (later one wins, and command line overrides
what is in the configuration).

Fix this by consolidating two variables (fast_forward_only and
allow_fast_forward) used in the implementation into one enum that
can take one of the three possible values.

Signed-off-by: Miklos Vajna <vmiklos@suse.cz>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
submodule update: allow custom command to update submodule working tree

Users can set submodule.$name.update to '!command' which will cause
'command' to be run instead of checkout/merge/rebase.  This allows the
user finer-grained control over how the update is done.

The primary motivation for this was interoperability with stgit,
however being able to intercept the submodule update process may
prove useful for integrating or extending other tools.

Signed-off-by: Chris Packham <judge.packham@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'tr/test-v-and-v-subtest-only' into jch

Allows N instances of tests run in parallel, each running 1/N parts
of the test suite under Valgrind, to speed things up.

* tr/test-v-and-v-subtest-only:
  perf-lib: fix start/stop of perf tests
  test-lib: support running tests under valgrind in parallel
  test-lib: allow prefixing a custom string before "ok N" etc.
  test-lib: valgrind for only tests matching a pattern
  test-lib: verbose mode for only tests matching a pattern
  test-lib: self-test that --verbose works
  test-lib: rearrange start/end of test_expect_* and test_skip
  test-lib: refactor $GIT_SKIP_TESTS matching
  test-lib: enable MALLOC_* for the actual tests
Merge branch 'jc/triangle-push-fixup' into jch

Earlier remote.pushdefault (and per-branch branch.*.pushremote)
were introduced as an additional mechanism to choose what
repository to push into when "git push" did not say it from the
command line, to help people who push to a repository that is
different from where they fetch from.  This attempts to finish that
topic by teaching the default mechanism to choose branch in the
remote repository to be updated by such a push.

The 'current', 'matching' and 'nothing' modes (specified by the
push.default configuration variable) extend to such a "triangular"
workflow naturally, but 'upstream' and 'simple' have to be updated.

. 'upstream' is about pushing back to update the branch in the
remote repository that the current branch fetches from and
integrates with, it errors out in a triangular workflow.

. 'simple' is meant to help new people by avoiding mistakes, and
will be the safe default in Git 2.0.  In a non-triangular
workflow, it will continue to act as a cross between 'upstream'
and 'current' in that it pushes to the current branch's
@{upstream} only when it is set to the same name as the current
branch (e.g. your 'master' forks from the 'master' from the
central repository).  In a triangular workflow, this series
tentatively defines it as the same as 'current', but we may have
to tighten it to avoid surprises in some way.

* jc/triangle-push-fixup:
  t/t5528-push-default: test pushdefault workflows
  t/t5528-push-default: generalize test_push_*
  push: change `simple` to accommodate triangular workflows
  config doc: rewrite push.default section
  t/t5528-push-default: remove redundant test_config lines
Merge branch 'jx/clean-interactive' (early part) into jch

* 'jx/clean-interactive' (early part):
  git-clean: refactor git-clean into two phases
  write_name{_quoted_relative,}(): remove redundant parameters
  quote_path_relative(): remove redundant parameter
  quote.c: substitute path_relative with relative_path
  path.c: refactor relative_path(), not only strip prefix
  test: add test cases for relative_path
Merge branch 'rr/rebase-checkout-reflog' into jch

Invocations of "git checkout" used internally by "git rebase" were
counted as "checkout", and affected later "git checkout -" to the
the user to an unexpected place.

The "bugfix" bits of the series is here.  The follow-up part to
reword reflog messages for steps in "rebase" are split to another
topic.

* rr/rebase-checkout-reflog:
  checkout: respect GIT_REFLOG_ACTION
  status: do not depend on rebase reflog messages
  t/t2021-checkout-last: "checkout -" should work after a rebase finishes
  wt-status: remove unused field in grab_1st_switch_cbdata
  t7512: test "detached from" as well
Merge branch 'as/log-output-encoding-in-user-format' into jch

"log --format=" did not honor i18n.logoutputencoding configuration
and this is a beginning of the series that attempts to fix it.

* as/log-output-encoding-in-user-format:
  t4205: replace .\+ with ..* in sed commands
  pretty: --format output should honor logOutputEncoding
  pretty: Add failing tests: --format output should honor logOutputEncoding
  t4205 (log-pretty-formats): don't hardcode SHA-1 in expected outputs
  t7102 (reset): don't hardcode SHA-1 in expected outputs
  t6006 (rev-list-format): don't hardcode SHA-1 in expected outputs
Merge branch 'jk/bash-completion' into jch

* jk/bash-completion:
  completion: learn about --man-path
  completion: handle unstuck form of base git options
### match next
Merge branch 'jg/status-config' into jch

"git status" learned status.branch and status.short configuration
variables to use --branch and --short options by default (override
with --no-branch and --no-short options from the command line).

The bottom two has been graduated to 'master' but then reverted.
The tip two are quick attempts to fix the fallout.  The one for
status.short looks correct; the other one, while it is correct,
is unfortunately overly complex in order not to introduce an
unnecessary regression.

* jg/status-config:
  status/commit: make sure --porcelain is not affected by user-facing config
  commit: make it work with status.short
  status: introduce status.branch to enable --branch by default
  status: introduce status.short to enable --short by default
Merge branch 'jc/reflog-doc' into jch

Document rules to use GIT_REFLOG_ACTION variable in the scripted
Porcelain.  git-rebase--interactive locally violates this, but it
is a leaf user that does not call out to or dot-sources other
scripts, so fixing it is not all that urgent.

* jc/reflog-doc:
  setup_reflog_action: document the rules for using GIT_REFLOG_ACTION
Merge branch 'mh/ref-races-optim-invalidate-cached' into jch

This requires the platform lstat() to be correct to avoid false
negatives.

* mh/ref-races-optim-invalidate-cached:
  refs: do not invalidate the packed-refs cache unnecessarily
Merge branch 'jk/fast-import-empty-ls' into jch

$gmane/228741

* jk/fast-import-empty-ls:
  fast-import: allow moving the root tree
  fast-import: allow ls or filecopy of the root tree
  fast-import: set valid mode on root tree in "ls"
  t9300: document fast-import empty path issues
Merge branch 'jc/maint-diff-core-safecrlf' into jch

"git diff" refused to even show difference when core.safecrlf is
set to true (i.e. error out) and there are offending lines in the
working tree files.

* jc/maint-diff-core-safecrlf:
  diff: demote core.safecrlf=true to core.safecrlf=warn