Re: [PATCH v4 10/10] rebase -i: rearrange fixup/squash lines using the rebase--helper
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
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", &opts.allow_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", &command, > N_("skip unnecessary picks"), SKIP_UNNECESSARY_PICKS), > + OPT_CMDMODE(0, "rearrange-squash", &command, > + 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 > -#
[PATCH v4 10/10] rebase -i: rearrange fixup/squash lines using the rebase--helper
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", &opts.allow_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", &command, N_("skip unnecessary picks"), SKIP_UNNECESSARY_PICKS), + OPT_CMDMODE(0, "rearrange-squash", &command, + 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 rebase.instructionF