Re: [PATCH v4 10/10] rebase -i: rearrange fixup/squash lines using the rebase--helper

[Johannes Schindelin]

Hi Liam,

On Thu, 25 May 2017, Liam Beguin wrote:

> Johannes Schindelin  writes:
> [...]
> > +   if (rearranged) {
> > +   struct strbuf buf = STRBUF_INIT;
> > +
> > +   for (i = 0; i < todo_list.nr; i++) {
> > +   enum todo_command command = todo_list.items[i].command;
> > +   int cur = i;
> > +
> > +   /*
> > +* Initially, all commands are 'pick's. If it is a
> > +* fixup or a squash now, we have rearranged it.
> > +*/
> > +   if (is_fixup(command))
> > +   continue;
> > +
> > +   while (cur >= 0) {
> > +   int offset = todo_list.items[cur].offset_in_buf;
> > +   int end_offset = cur + 1 < todo_list.nr ?
> > +   todo_list.items[cur + 1].offset_in_buf :
> > +   todo_list.buf.len;
> > +   char *bol = todo_list.buf.buf + offset;
> > +   char *eol = todo_list.buf.buf + end_offset;
> 
> I got a little confused with these offsets. I know it was part of a
> previous series, but maybe we could add a description to the fields
> of `struct todo_list` and `struct todo_item`.

You mean "offset_in_buf"?

Sure, I can add a comment there. I would like to keep it out of this patch
series, though, as the purpose of it is to accelerate rebase -i by moving
logic from the (slow) shell script code to the (decently fast) C code.

Ciao,
Johannes

[PATCH v4 10/10] rebase -i: rearrange fixup/squash lines using the rebase--helper

[Liam Beguin]

Hi Johannes,

Johannes Schindelin  writes:
> This operation has quadratic complexity, which is especially painful
> on Windows, where shell scripts are *already* slow (mainly due to the
> overhead of the POSIX emulation layer).
>
> Let's reimplement this with linear complexity (using a hash map to
> match the commits' subject lines) for the common case; Sadly, the
> fixup/squash feature's design neglected performance considerations,
> allowing arbitrary prefixes (read: `fixup! hell` will match the
> commit subject `hello world`), which means that we are stuck with
> quadratic performance in the worst case.
>
> The reimplemented logic also happens to fix a bug where commented-out
> lines (representing empty patches) were dropped by the previous code.
>
> While at it, clarify how the fixup/squash feature works in `git rebase
> -i`'s man page.
>
> Signed-off-by: Johannes Schindelin 
> ---
>  Documentation/git-rebase.txt |  16 ++--
>  builtin/rebase--helper.c |   6 +-
>  git-rebase--interactive.sh   |  90 +---
>  sequencer.c  | 195 
> +++
>  sequencer.h  |   1 +
>  t/t3415-rebase-autosquash.sh |   2 +-
>  6 files changed, 212 insertions(+), 98 deletions(-)
>
> diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
> index 53f4e14..c5464aa5365 100644
> --- a/Documentation/git-rebase.txt
> +++ b/Documentation/git-rebase.txt
> @@ -430,13 +430,15 @@ without an explicit `--interactive`.
>  --autosquash::
>  --no-autosquash::
>   When the commit log message begins with "squash! ..." (or
> - "fixup! ..."), and there is a commit whose title begins with
> - the same ..., automatically modify the todo list of rebase -i
> - so that the commit marked for squashing comes right after the
> - commit to be modified, and change the action of the moved
> - commit from `pick` to `squash` (or `fixup`).  Ignores subsequent
> - "fixup! " or "squash! " after the first, in case you referred to an
> - earlier fixup/squash with `git commit --fixup/--squash`.
> + "fixup! ..."), and there is already a commit in the todo list that
> + matches the same `...`, automatically modify the todo list of rebase
> + -i so that the commit marked for squashing comes right after the
> + commit to be modified, and change the action of the moved commit
> + from `pick` to `squash` (or `fixup`).  A commit matches the `...` if
> + the commit subject matches, or if the `...` refers to the commit's
> + hash. As a fall-back, partial matches of the commit subject work,
> + too.  The recommended way to create fixup/squash commits is by using
> + the `--fixup`/`--squash` options of linkgit:git-commit[1].
>  +
>  This option is only valid when the `--interactive` option is used.
>  +
> diff --git a/builtin/rebase--helper.c b/builtin/rebase--helper.c
> index de3ccd9bfbc..e6591f01112 100644
> --- a/builtin/rebase--helper.c
> +++ b/builtin/rebase--helper.c
> @@ -14,7 +14,7 @@ int cmd_rebase__helper(int argc, const char **argv, const 
> char *prefix)
>   int keep_empty = 0;
>   enum {
>   CONTINUE = 1, ABORT, MAKE_SCRIPT, SHORTEN_SHA1S, EXPAND_SHA1S,
> - CHECK_TODO_LIST, SKIP_UNNECESSARY_PICKS
> + CHECK_TODO_LIST, SKIP_UNNECESSARY_PICKS, REARRANGE_SQUASH
>   } command = 0;
>   struct option options[] = {
>   OPT_BOOL(0, "ff", _ff, N_("allow fast-forward")),
> @@ -33,6 +33,8 @@ int cmd_rebase__helper(int argc, const char **argv, const 
> char *prefix)
>   N_("check the todo list"), CHECK_TODO_LIST),
>   OPT_CMDMODE(0, "skip-unnecessary-picks", ,
>   N_("skip unnecessary picks"), SKIP_UNNECESSARY_PICKS),
> + OPT_CMDMODE(0, "rearrange-squash", ,
> + N_("rearrange fixup/squash lines"), REARRANGE_SQUASH),
>   OPT_END()
>   };
>  
> @@ -59,5 +61,7 @@ int cmd_rebase__helper(int argc, const char **argv, const 
> char *prefix)
>   return !!check_todo_list();
>   if (command == SKIP_UNNECESSARY_PICKS && argc == 1)
>   return !!skip_unnecessary_picks();
> + if (command == REARRANGE_SQUASH && argc == 1)
> + return !!rearrange_squash();
>   usage_with_options(builtin_rebase_helper_usage, options);
>  }
> diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
> index 92e3ca1de3b..84c6e62518f 100644
> --- a/git-rebase--interactive.sh
> +++ b/git-rebase--interactive.sh
> @@ -721,94 +721,6 @@ collapse_todo_ids() {
>   git rebase--helper --shorten-sha1s
>  }
>  
> -# Rearrange the todo list that has both "pick sha1 msg" and
> -# "pick sha1 fixup!/squash! msg" appears in it so that the latter
> -# comes immediately after the former, and change "pick" to
> -# "fixup"/"squash".
> -#
> -# Note that if the config has specified a 

[PATCH v4 10/10] rebase -i: rearrange fixup/squash lines using the rebase--helper

[Johannes Schindelin]

This operation has quadratic complexity, which is especially painful
on Windows, where shell scripts are *already* slow (mainly due to the
overhead of the POSIX emulation layer).

Let's reimplement this with linear complexity (using a hash map to
match the commits' subject lines) for the common case; Sadly, the
fixup/squash feature's design neglected performance considerations,
allowing arbitrary prefixes (read: `fixup! hell` will match the
commit subject `hello world`), which means that we are stuck with
quadratic performance in the worst case.

The reimplemented logic also happens to fix a bug where commented-out
lines (representing empty patches) were dropped by the previous code.

While at it, clarify how the fixup/squash feature works in `git rebase
-i`'s man page.

Signed-off-by: Johannes Schindelin 
---
 Documentation/git-rebase.txt |  16 ++--
 builtin/rebase--helper.c |   6 +-
 git-rebase--interactive.sh   |  90 +---
 sequencer.c  | 195 +++
 sequencer.h  |   1 +
 t/t3415-rebase-autosquash.sh |   2 +-
 6 files changed, 212 insertions(+), 98 deletions(-)

diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 53f4e14..c5464aa5365 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -430,13 +430,15 @@ without an explicit `--interactive`.
 --autosquash::
 --no-autosquash::
When the commit log message begins with "squash! ..." (or
-   "fixup! ..."), and there is a commit whose title begins with
-   the same ..., automatically modify the todo list of rebase -i
-   so that the commit marked for squashing comes right after the
-   commit to be modified, and change the action of the moved
-   commit from `pick` to `squash` (or `fixup`).  Ignores subsequent
-   "fixup! " or "squash! " after the first, in case you referred to an
-   earlier fixup/squash with `git commit --fixup/--squash`.
+   "fixup! ..."), and there is already a commit in the todo list that
+   matches the same `...`, automatically modify the todo list of rebase
+   -i so that the commit marked for squashing comes right after the
+   commit to be modified, and change the action of the moved commit
+   from `pick` to `squash` (or `fixup`).  A commit matches the `...` if
+   the commit subject matches, or if the `...` refers to the commit's
+   hash. As a fall-back, partial matches of the commit subject work,
+   too.  The recommended way to create fixup/squash commits is by using
+   the `--fixup`/`--squash` options of linkgit:git-commit[1].
 +
 This option is only valid when the `--interactive` option is used.
 +
diff --git a/builtin/rebase--helper.c b/builtin/rebase--helper.c
index de3ccd9bfbc..e6591f01112 100644
--- a/builtin/rebase--helper.c
+++ b/builtin/rebase--helper.c
@@ -14,7 +14,7 @@ int cmd_rebase__helper(int argc, const char **argv, const 
char *prefix)
int keep_empty = 0;
enum {
CONTINUE = 1, ABORT, MAKE_SCRIPT, SHORTEN_SHA1S, EXPAND_SHA1S,
-   CHECK_TODO_LIST, SKIP_UNNECESSARY_PICKS
+   CHECK_TODO_LIST, SKIP_UNNECESSARY_PICKS, REARRANGE_SQUASH
} command = 0;
struct option options[] = {
OPT_BOOL(0, "ff", _ff, N_("allow fast-forward")),
@@ -33,6 +33,8 @@ int cmd_rebase__helper(int argc, const char **argv, const 
char *prefix)
N_("check the todo list"), CHECK_TODO_LIST),
OPT_CMDMODE(0, "skip-unnecessary-picks", ,
N_("skip unnecessary picks"), SKIP_UNNECESSARY_PICKS),
+   OPT_CMDMODE(0, "rearrange-squash", ,
+   N_("rearrange fixup/squash lines"), REARRANGE_SQUASH),
OPT_END()
};
 
@@ -59,5 +61,7 @@ int cmd_rebase__helper(int argc, const char **argv, const 
char *prefix)
return !!check_todo_list();
if (command == SKIP_UNNECESSARY_PICKS && argc == 1)
return !!skip_unnecessary_picks();
+   if (command == REARRANGE_SQUASH && argc == 1)
+   return !!rearrange_squash();
usage_with_options(builtin_rebase_helper_usage, options);
 }
diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 92e3ca1de3b..84c6e62518f 100644
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -721,94 +721,6 @@ collapse_todo_ids() {
git rebase--helper --shorten-sha1s
 }
 
-# Rearrange the todo list that has both "pick sha1 msg" and
-# "pick sha1 fixup!/squash! msg" appears in it so that the latter
-# comes immediately after the former, and change "pick" to
-# "fixup"/"squash".
-#
-# Note that if the config has specified a custom instruction format
-# each log message will be re-retrieved in order to normalize the
-# autosquash arrangement
-rearrange_squash () {
-   format=$(git config --get