replace: cleanup redirection style in tests

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: factor out compare and swap operations

When manipulating the priority queue's heap, we frequently
have to compare and swap heap entries. As we are storing
only void pointers right now, this is quite easy to do
inline in a few lines. However, when we start using a more
complicated heap entry in a future patch, that will get
longer. Factoring out these operations lets us make future
changes in one place. It also makes the code a little
shorter and more readable.

Note that we actually accept indices into the queue array
instead of pointers. This is slightly less flexible than
passing pointers-to-pointers (we could not swap items from
unrelated arrays, but we would not want to), but will make
further refactoring simpler (and lets us avoid repeating
"queue->array" at each callsite, which led to some long
lines).

And finally, note that we are cleaning up an accidental use
of a "struct commit" pointer to hold a temporary entry
during swap. Even though we currently only use this code for
commits, it is supposed to be type-agnostic. In practice
this didn't matter anyway because we never dereferenced the
commit pointer (and on most systems, the pointer values
themselves are interchangeable between types).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
prio-queue: make output stable with respect to insertion

If two items are added to a prio_queue and compare equal,
they currently come out in an apparently random order (this
order is deterministic for a particular sequence of
insertions and removals, but does not necessarily match the
insertion order). This makes it unlike using a date-ordered
commit_list, which is one of the main types we would like to
replace with it (because prio_queue does not suffer from
O(n) insertions).

We can make the priority queue stable by keeping an
insertion counter for each element, and using it to break
ties. This does increase the memory usage of the structure
(one int per element), but in practice it does not seem to
affect runtime. A best-of-five "git rev-list --topo-order"
on linux.git showed less than 1% difference (well within the
run-to-run noise).

In an ideal world, we would offer both stable and unstable
priority queues (the latter to try to maximize performance).
However, given the lack of a measurable performance
difference, it is not worth the extra code.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
paint_down_to_common: use prio_queue

When we are traversing to find merge bases, we keep our
usual commit_list of commits to process, sorted by their
commit timestamp. As we add each parent to the list, we have
to spend "O(width of history)" to do the insertion, where
the width of history is the number of simultaneous lines of
development.

If we instead use a heap-based priority queue, we can do
these insertions in "O(log width)" time. This provides minor
speedups to merge-base calculations (timings in linux.git,
warm cache, best-of-five):

  [before]
  $ git merge-base HEAD v2.6.12
  real    0m3.251s
  user    0m3.148s
  sys     0m0.104s

  [after]
  $ git merge-base HEAD v2.6.12
  real    0m3.234s
  user    0m3.108s
  sys     0m0.128s

That's only an 0.5% speedup, but it does help protect us
against pathological cases.

While we are munging the "interesting" function, we also
take the opportunity to give it a more descriptive name, and
convert the return value to an int (we returned the first
interesting commit, but nobody ever looked at it).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t5539: update a flaky test

The test creates some unrelated commits in two separate repositories,
and then fetches from one to the other. Since the commit creation
happens in a subshell, the first commit in each ends up with the
same test_tick value. When fetch-pack looks at the two root commits
"unrelated1" and "new-too", the exact sequence of ACKs is different
depending on which one it pulls out of the queue first.

With the current code, it happens to be "unrelated1" (though this is not
at all guaranteed by the prio_queue data structure, it is deterministic
for this particular sequence of input). We see the ready-ACK, and the
test succeeds.

With the stable queue, we reliably get "new-too" out (since it is our
local tip, it is added to the queue before we even talk to the remote).
We never see a ready-ACK, and the test fails due to the grep on the
TRACE_PACKET output at the end (the fetch itself succeeds as expected).

I'm really not quite clear on what's supposed to be going on in the
test. I can make it pass with this change.
rebase--am: use --cherry-pick instead of --ignore-if-in-upstream

When using `git format-patch --ignore-if-in-upstream` we are only
allowed to give a single revision range.  In the next commit we will
want to add an additional exclusion revision in order to handle fork
points correctly, so convert `git-rebase--am` to use a symmetric
difference with `--cherry-pick --right-only`.

This does not change the result of the format-patch invocation, just how
we spell the arguments.

Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rebase: omit patch-identical commits with --fork-point

When the `--fork-point` argument was added to `git rebase`, we changed
the value of $upstream to be the fork point instead of the point from
which we want to rebase.  When $orig_head..$upstream is empty this does
not change the behaviour, but when there are new changes in the upstream
we are no longer checking if any of them are patch-identical with
changes in $upstream..$orig_head.

Fix this by introducing a new variable to hold the fork point and using
this to restrict the range as an extra (negative) revision argument so
that the set of desired revisions becomes (in fork-point mode):

	git rev-list --cherry-pick --right-only \
		$upstream...$orig_head ^$fork_point

This allows us to correctly handle the scenario where we have the
following topology:

	    C --- D --- E  <- dev
	   /
	  B  <- master@{1}
	 /
	o --- B' --- C* --- D*  <- master

where:
- B' is a fixed-up version of B that is not patch-identical with B;
- C* and D* are patch-identical to C and D respectively and conflict
  textually if applied in the wrong order;
- E depends textually on D.

The correct result of `git rebase master dev` is that B is identified as
the fork-point of dev and master, so that C, D, E are the commits that
need to be replayed onto master; but C and D are patch-identical with C*
and D* and so can be dropped, so that the end result is:

	o --- B' --- C* --- D* --- E  <- dev

If the fork-point is not identified, then picking B onto a branch
containing B' results in a conflict and if the patch-identical commits
are not correctly identified then picking C onto a branch containing D
(or equivalently D*) results in a conflict.

This change allows us to handle both of these cases, where previously we
either identified the fork-point (with `--fork-point`) but not the
patch-identical commits *or* (with `--no-fork-point`) identified the
patch-identical commits but not the fact that master had been rewritten.

Reported-by: Ted Felix <ted@tedfelix.com>
Signed-off-by: John Keeping <john@keeping.me.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add --graft option

The usage string for this option is:

git replace [-f] --graft <commit> [<parent>...]

First we create a new commit that is the same as <commit>
except that its parents are [<parents>...]

Then we create a replace ref that replace <commit> with
the commit we just created.

With this new option, it should be straightforward to
convert grafts to replace refs.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add test for --graft

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation: replace: add --graft option

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib: add convert-grafts-to-replace-refs.sh

This patch adds into contrib/ an example script to convert
grafts from an existing grafts file into replace refs using
the new --graft option of "git replace".

While at it let's mention this new script in the
"git replace" documentation for the --graft option.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: remove signature when using --graft

It could be misleading to keep a signature in a
replacement commit, so let's remove it.

Note that there should probably be a way to sign
the replacement commit created when using --graft,
but this can be dealt with in another commit or
patch series.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add test for --graft with signed commit

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: check mergetags when using --graft

When using --graft, with a mergetag in the original
commit, we should check that the commit pointed to by
the mergetag is still a parent of then new commit we
create, otherwise the mergetag could be misleading.

If the commit pointed to by the mergetag is no more
a parent of the new commit, we could remove the
mergetag, but in this case there is a good chance
that the title or other elements of the commit might
also be misleading. So let's just error out and
suggest to use --edit instead on the commit.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
replace: add test for --graft with a mergetag

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jk/stable-prio-queue'

* jk/stable-prio-queue:
  t5539: update a flaky test
  paint_down_to_common: use prio_queue
  prio-queue: make output stable with respect to insertion
  prio-queue: factor out compare and swap operations
Merge branch 'cc/replace-graft'

"git replace" learned a "--graft" option to rewrite parents of a
commit.

* cc/replace-graft:
  replace: add test for --graft with a mergetag
  replace: check mergetags when using --graft
  replace: add test for --graft with signed commit
  replace: remove signature when using --graft
  contrib: add convert-grafts-to-replace-refs.sh
  Documentation: replace: add --graft option
  replace: add test for --graft
  replace: add --graft option
  replace: cleanup redirection style in tests
Merge branch 'jk/rebase-am-fork-point'

"git rebase --fork-point" did not filter out patch-identical
commits correctly.

* jk/rebase-am-fork-point:
  rebase: omit patch-identical commits with --fork-point
  rebase--am: use --cherry-pick instead of --ignore-if-in-upstream
Git 2.1.0-rc0

Signed-off-by: Junio C Hamano <gitster@pobox.com>
pathspec: speed up "vanilla" pathspec access

When we diff two trees with a set of pathspecs, we walk
through the trees linearly, and apply each pathspec to each
entry. This means we do `O(paths * pathspecs)` comparisons
for each tree. If we assume that the number of pathspecs may
approach the number of paths, this is `O(n^2)` in the number
of paths. We have to do it this way in the general case
becaause pathspecs may be arbitrary fnmatch expressions, and
we cannot create any meaningful index.

However, it is common that all of the pathspecs are vanilla
prefixes (e.g., "git.c" or "Documentation/") that do not use
any wildcards or magic features. In such a case, we can
index the pathspec list to give us faster lookups.

This patch automatically detects such a vanilla pathspec,
keeps the list sorted, and teaches the tree-diff machinery
to binary search the sorted list, resulting in `O(n log n)`
comparisons. The speedup is easy to measure if you have a
large number of pathspecs:

    [before]
    $ ps=$(git ls-tree --name-only -r HEAD -- Documentation)
    $ time git log $ps >/dev/null
    real    0m6.809s
    user    0m6.764s
    sys     0m0.044s

    [after]
    $ time git log $ps >/dev/null
    real    0m1.211s
    user    0m1.176s
    sys     0m0.028s

Of course this is a contrived case, but a real script might
do something similar by filtering the ls-tree output and
asking for only a subset of the names.

We could shrink this to `O(n)` by using a constant-time data
structure like a hash table. However, it's slightly tricky
to do so as we are not matching exact strings; we need to
handle matching prefixes, as well as doing the right thing
for pathspecs that have a trailing slash.

Another `O(n)` alternative would be to walk the sorted trees
and pathspec in parallel. This would require a fair bit of
refactoring around the diff_tree code, and it gets hairy as
we deal with the tree's peculiar sorting order.

This patch aims for a simple and reasonably fast
implementation. We only teach the diff_tree to use the
optimization here, but in theory it would be suitable
anywhere that pathspecs are evaluated.

Signed-off-by: Jeff King <peff@peff.net>