rebase: use a better reflog message

Now that the "checkout" invoked internally from "rebase" knows to
honor GIT_REFLOG_ACTION, we can start to use it to write a better
reflog message when "rebase anotherbranch", "rebase --onto branch",
etc. internally checks out the new fork point.  We will write:

  rebase: checkout master

instead of the old

  rebase

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rebase -i: use a better reflog message

Now that the "checkout" invoked internally from "rebase -i" knows to
honor GIT_REFLOG_ACTION, we can start to use it to write a better
reflog message when "rebase anotherbranch", "rebase --onto branch",
etc. internally checks out the new fork point.  We will write:

  rebase -i: checkout master

instead of the old

  rebase -i

As all the calls git-rebase--interactive make to underlying git
commands that leave reflog messages are preceded by the internal
comment_for_reflog helper function, which uses the original value of
the GIT_REFLOG_ACTION variable it saw when it first started, the new
assignments to GIT_REFLOG_ACTION actively contaminate the value of
the variable, knowing that it will be reset to a sane value before
it is used again.  This does not generally hold true but it should
suffice for now.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test: add test cases for relative_path

Add subcommand "relative_path" in test-path-utils, and add test cases
in t0060.

Johannes tested an earlier version of this patch on Windows, and
found that some relative_path tests should be skipped on
Windows. This is because the bash on Windows rewrites arguments of
regular Windows programs, such as git and the test helpers, if the
arguments look like absolute POSIX paths. As a consequence, the
actual tests performed are not what the tests scripts expect.

The tests that need *not* be skipped are those where the two paths passed
to 'test-path-utils relative_path' have the same prefix and the result is
expected to be a relative path. This is because the rewriting changes
"/a/b" to "D:/Src/MSysGit/a/b", and when both inputs are extended the same
way, this just cancels out in the relative path computation.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Helped-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
path.c: refactor relative_path(), not only strip prefix

Original design of relative_path() is simple, just strip the prefix
(*base) from the absolute path (*abs).

In most cases, we need a real relative path, such as: ../foo,
../../bar.  That's why there is another reimplementation
(path_relative()) in quote.c.

Borrow some codes from path_relative() in quote.c to refactor
relative_path() in path.c, so that it could return real relative
path, and user can reuse this function without reimplementing
his/her own.  The function path_relative() in quote.c will be
substituted, and I would use the new relative_path() function when
implementing the interactive git-clean later.

Different results for relative_path() before and after this refactor:

    abs path  base path  relative (original)  relative (refactor)
    ========  =========  ===================  ===================
    /a/b      /a/b       .                    ./
    /a/b/     /a/b       .                    ./
    /a        /a/b/      /a                   ../
    /         /a/b/      /                    ../../
    /a/c      /a/b/      /a/c                 ../c
    /x/y      /a/b/      /x/y                 ../../x/y

    a/b/      a/b/       .                    ./
    a/b/      a/b        .                    ./
    a         a/b        a                    ../
    x/y       a/b/       x/y                  ../../x/y
    a/c       a/b        a/c                  ../c

    (empty)   (null)     (empty)              ./
    (empty)   (empty)    (empty)              ./
    (empty)   /a/b       (empty)              ./
    (null)    (null)     (null)               ./
    (null)    (empty)    (null)               ./
    (null)    /a/b       (segfault)           ./

You may notice that return value "." has been changed to "./".
It is because:

 * Function quote_path_relative() in quote.c will show the relative
   path as "./" if abs(in) and base(prefix) are the same.

 * Function relative_path() is called only once (in setup.c), and
   it will be OK for the return value as "./" instead of ".".

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
quote.c: substitute path_relative with relative_path

Substitute the function path_relative in quote.c with the function
relative_path. Function relative_path can be treated as an enhanced
and more robust version of path_relative.

Outputs of path_relative and it's replacement (relative_path) are the
same for the following cases:

    path      prefix     output of path_relative  output of relative_path
    ========  =========  =======================  =======================
    /a/b/c/   /a/b/      c/                       c/
    /a/b/c    /a/b/      c                        c
    /a/       /a/b/      ../                      ../
    /         /a/b/      ../../                   ../../
    /a/c      /a/b/      ../c                     ../c
    /x/y      /a/b/      ../../x/y                ../../x/y
    a/b/c/    a/b/       c/                       c/
    a/        a/b/       ../                      ../
    x/y       a/b/       ../../x/y                ../../x/y
    /a/b      (empty)    /a/b                     /a/b
    /a/b      (null)     /a/b                     /a/b
    a/b       (empty)    a/b                      a/b
    a/b       (null)     a/b                      a/b

But if both of the path and the prefix are the same, or the returned
relative path should be the current directory, the outputs of both
functions are different. Function relative_path returns "./", while
function path_relative returns empty string.

    path      prefix     output of path_relative  output of relative_path
    ========  =========  =======================  =======================
    /a/b/     /a/b/      (empty)                  ./
    a/b/      a/b/       (empty)                  ./
    (empty)   (null)     (empty)                  ./
    (empty)   (empty)    (empty)                  ./

But the callers of path_relative can handle such cases, or never
encounter this issue at all, because:

 * In function quote_path_relative, if the output of path_relative is
   empty, append "./" to it, like:

       if (!out->len)
           strbuf_addstr(out, "./");

 * Another caller is write_name_quoted_relative, which is only used
   by builtin/ls-files.c. git-ls-files only show files, so path of
   files will never be identical with the prefix of a directory.

The following differences show that path_relative does not handle
extra slashes properly:

    path      prefix     output of path_relative  output of relative_path
    ========  =========  =======================  =======================
    /a//b//c/ //a/b//    ../../../../a//b//c/     c/
    a/b//c    a//b       ../b//c                  c

And if prefix has no trailing slash, path_relative does not work
properly either.  But since prefix always has a trailing slash, it's
not a problem.

    path      prefix     output of path_relative  output of relative_path
    ========  =========  =======================  =======================
    /a/b/c/   /a/b       b/c/                     c/
    /a/b      /a/b       b                        ./
    /a/b/     /a/b       b/                       ./
    /a        /a/b/      ../../a                  ../
    a/b/c/    a/b        b/c/                     c/
    a/b/      a/b        b/                       ./
    a         a/b        ../a                     ../
    x/y       a/b/       ../x/y                   ../../x/y
    a/c       a/b        c                        ../c
    /a/       /a/b       (empty)                  ../
    (empty)   /a/b       ../../                   ./

One tricky part in this conversion is write_name() function in
ls-files.c.  It takes a counted string, <name, len>, that is to be
made relative to <prefix, prefix_len> and then quoted.  Because
write_name_quoted_relative() still takes these two parameters as
counted string, but ignores the count and treat these two as
NUL-terminated strings, this conversion needs to be audited for its
callers:

 - For <name, len>, all three callers of write_name() passes a
   NUL-terminated string and its true length, so this patch makes
   "len" unused.

 - For <prefix, prefix_len>, prefix could be a string that is longer
   than empty while prefix_len could be 0 when "--full-name" option
   is used.  This is fixed by checking prefix_len in write_name()
   and calling write_name_quoted_relative() with NULL when
   prefix_len is set to 0.  Again, this makes "prefix_len" given to
   write_name_quoted_relative() unused, without introducing a bug.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
quote_path_relative(): remove redundant parameter

quote_path_relative() used to take a counted string as its parameter
(the string to be quoted).  With an earlier change, it now uses
relative_path() that does not take a counted string, and we have
been passing only the pointer to the string since then.

Remove the length parameter from quote_path_relative() to show that
this parameter was redundant.  All the changed lines show that the
caller passed either -1 (to ask the function run strlen() on the
string), or the length of the string, so the earlier conversion was
safe.

All the callers of quote_path_relative() that used to take counted string
have been audited to make sure that they are passing length of the actual
string (or -1 to ask the callee run strlen())

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
write_name{_quoted_relative,}(): remove redundant parameters

After substitute path_relative() in quote.c with relative_path()
from path.c, parameters (such as len and prefix_len) are redundant
in function write_name() and write_name_quoted_relative().  The
callers have already been audited that the strings they pass are
properly NUL terminated and the length they give are the length of
the string (or -1 that asks the length to be counted by the callee).

Remove these now-redundant parameters.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: refactor git-clean into two phases

Before introducing interactive git-clean, refactor git-clean operations
into two phases:

 * hold cleaning items in del_list,
 * and remove them in a separate loop at the end.

We will introduce interactive git-clean between the two phases. The
interactive git-clean will show what would be done and must confirm
before do real cleaning.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: add support for -i/--interactive

Show what would be done and the user must confirm before actually
cleaning.

    Would remove ...
    Would remove ...
    Would remove ...

    Remove [y/n]?

Press "y" to start cleaning, and press "n" if you want to abort.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: show items of del_list in columns

When there are lots of items to be cleaned, it is hard to see them all
in one screen. Show them in columns will solve this problem.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Comments-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: add colors to interactive git-clean

Show header, help, error messages, and prompt in colors for interactive
git-clean. Re-use config variables, such as "color.interactive" and
"color.interactive.<slot>" for command `git-add--interactive`.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Comments-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: use a git-add-interactive compatible UI

Rewrite menu using a new method `list_and_choose`, which is borrowed
from `git-add--interactive.perl`. We will use this framework to add
new actions for interactive git-clean later.

Please NOTE:

 * Method `list_and_choose` return an array of integers, and
 * it is up to you to free the allocated memory of the array.
 * The array ends with EOF.
 * If user pressed CTRL-D (i.e. EOF), no selection returned.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: add filter by pattern interactive action

Add a new action for interactive git-clean: filter by pattern. When the
user chooses this action, user can input space-separated patterns (the
same syntax as gitignore), and each clean candidate that matches with
one of the patterns will be excluded from cleaning. When the user feels
it's OK, presses ENTER and backs to the confirmation dialog.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: add select by numbers interactive action

Draw a multiple choice menu using `list_and_choose` to select items
to be deleted by numbers.

User can input:

 *  1,5-7 : select 1,5,6,7 items to be deleted
 *  *     : select all items to be deleted
 *  -*    : unselect all, nothing will be deleted
 *        : (empty) finish selecting, and return back to main menu

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: add ask each interactive action

Add a new action for interactive git-clean: ask each. It's just like
the "rm -i" command, that the user must confirm one by one for each
file or directory to be cleaned.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-clean: add documentation for interactive git-clean

Add new section "Interactive mode" for documentation of interactive
git-clean.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Helped-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test: add t7301 for git-clean--interactive

Add test cases for git-clean--interactive.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
test: run testcases with POSIX absolute paths on Windows

Some test cases are skipped on Windows by marking with POSIX prereq.
This is because arguments look like absolute paths (such as /a/b)
for regular Windows programs (*.exe executables, no bash scripts)
are changed to Windows paths (like C:/msysgit/a/b).

There is no cygpath nor equivalent on msysGit, but it is easy to
write one. New subcommand "mingw_path" is added in test-path-utils,
so that we can get the expected absolute paths on Windows. E.g.

    COMMAND LINE                        Linux output  Windows output
    ==================================  ============  ===============
    test-path-utils mingw_path /        /             C:/msysgit
    test-path-utils mingw_path /a/b/    /a/b/         C:/msysgit/a/b/

With this utility, most skipped test cases in t0060 can be turned on
to be tested correctly on Windows.

Signed-off-by: Jiang Xin <worldhello.net@gmail.com>
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>