[RFC PATCH] rebase: implement --rewind

[RFC PATCH] rebase: implement --rewind

[Oswald Buddenhagen]

This is fundamentally --edit-todo, except that we first prepend the
already applied commits and reset back to `onto`. This is useful when
one finds that a prior change needs (further) modifications.

This patch implements "flat" rewind, that is, once the todo edit has
been committed, one can abort only the complete rebase. The pre-rewind
position is marked with a `break` command (these pile up when rewinding
multiple times; the user is expected to clean them up as necessary).

An alternative to that would be "nested" rewind, where one can return to
the pre-rewind state even after committing the todo edit. However, this:
- would add somewhat significant complexity due to having to maintain a
  stack of todos and HEADs
- would be mildly confusing to use due to needing to track the state of
  the stack. One could simplify this somewhat by hiding the rest of the
  previous todo before nesting, but this would be somewhat limiting in
  turn (one might want to defer a factored out hunk, and stashing it is
  not necessarily the most elegant way to do it).
- would be of somewhat limited usefulness, speaking from experience

This patch leaves transitive resolution of rewritten-list to the
consumer. This is probably a bad idea.
Somewhat related to that, --update-refs isn't properly handled yet.

Reference: <YhPiqlM81XCjNWpk@ugly>
Signed-off-by: Oswald Buddenhagen <oswald.buddenhagen@gmx.de>
---
 Documentation/git-rebase.txt  |  14 ++++-
 builtin/rebase.c              |  98 ++++++++++++++++++++++++++++--
 rebase-interactive.c          |  34 ++++++++++-
 rebase-interactive.h          |   2 +
 sequencer.c                   |  37 +++++++++---
 sequencer.h                   |   3 +
 t/t3404-rebase-interactive.sh | 111 ++++++++++++++++++++++++++++++++++
 7 files changed, 281 insertions(+), 18 deletions(-)

diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 9a295bcee4..f736131a6c 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -12,7 +12,8 @@ SYNOPSIS
 	[--onto <newbase> | --keep-base] [<upstream> [<branch>]]
 'git rebase' [-i | --interactive] [<options>] [--exec <cmd>] [--onto <newbase>]
 	--root [<branch>]
-'git rebase' (--continue | --skip | --abort | --quit | --edit-todo | --show-current-patch)
+'git rebase' (--continue | --skip | --abort | --quit | --edit-todo | --rewind |
+	--show-current-patch)
 
 DESCRIPTION
 -----------
@@ -215,7 +216,8 @@ The options in this section cannot be used with any other option,
 including not with each other:
 
 --continue::
-	Restart the rebasing process after having resolved a merge conflict.
+	Restart the rebasing process after an interruption, e.g. having
+	resolved a merge conflict.
 
 --skip::
 	Restart the rebasing process by skipping the current patch.
@@ -236,6 +238,10 @@ including not with each other:
 --edit-todo::
 	Edit the todo list during an interactive rebase.
 
+--rewind::
+	Edit the todo list during an interactive rebase, but first
+	prepend the commits on top of the new base and reset to it.
+
 --show-current-patch::
 	Show the current patch in an interactive rebase or when rebase
 	is stopped because of conflicts. This is the equivalent of
@@ -975,6 +981,10 @@ pick f4593f9 four
 exec make test
 --------------------
 
+If during editing a commit you notice that an ancestor commit should be
+actually edited first, you may use `git rebase --rewind` to restart the
+interactive rebase without starting from scratch.
+
 SPLITTING COMMITS
 -----------------
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index 61e5363ac7..3a14ac1a4f 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -36,7 +36,8 @@ static char const * const builtin_rebase_usage[] = {
 		"[--onto <newbase> | --keep-base] [<upstream> [<branch>]]"),
 	N_("git rebase [-i] [options] [--exec <cmd>] [--onto <newbase>] "
 		"--root [<branch>]"),
-	"git rebase --continue | --abort | --skip | --edit-todo",
+	"git rebase --continue | --abort | --quit | --skip | --edit-todo | "
+		"--rewind",
 	NULL
 };
 
@@ -65,6 +66,8 @@ static const char *action_names[] = {
 	"abort",
 	"quit",
 	"edit_todo",
+	"rewind",
+	"resume_rewind",
 	"show_current_patch"
 };
 
@@ -183,17 +186,21 @@ static int edit_todo_file(unsigned flags)
 	const char *todo_file = rebase_path_todo();
 	struct todo_list todo_list = TODO_LIST_INIT,
 		new_todo = TODO_LIST_INIT;
+	enum rebase_action action = file_exists(rebase_path_todo_orig()) ?
+				ACTION_RESUME_REWIND : ACTION_EDIT_TODO;
 	int res = 0;
 
 	if (strbuf_read_file(&todo_list.buf, todo_file, 0) < 0)
 		return error_errno(_("could not read '%s'."), todo_file);
 
 	strbuf_stripspace(&todo_list.buf, 1);
 	res = edit_todo_list(the_repository, &todo_list, &new_todo, NULL, NULL, flags,
-			     ACTION_EDIT_TODO);
-	if (!res && todo_list_write_to_file(the_repository, &new_todo, todo_file,
-					    NULL, NULL, -1, flags & ~(TODO_LIST_SHORTEN_IDS),
-					    ACTION_EDIT_TODO))
+			     action);
+	if (res == EDIT_TODO_ABORT)
+		res = error(_("rewind aborted; state restored"));
+	else if (!res && todo_list_write_to_file(the_repository, &new_todo, todo_file,
+						 NULL, NULL, -1,
+						 flags & ~(TODO_LIST_SHORTEN_IDS), action))
 		res = error_errno(_("could not write '%s'"), todo_file);
 
 	todo_list_release(&todo_list);
@@ -301,6 +308,64 @@ static int do_interactive_rebase(struct rebase_options *opts, unsigned flags)
 	return ret;
 }
 
+static int rewind_todo_file(struct rebase_options *opts,
+			    unsigned flags)
+{
+	int ret;
+	char *revisions;
+	const char *todo_file = rebase_path_todo();
+	struct strvec make_script_args = STRVEC_INIT;
+	struct todo_list todo_list = TODO_LIST_INIT;
+	struct replay_opts replay = get_replay_opts(opts);
+	struct string_list commands = STRING_LIST_INIT_DUP;
+
+	require_clean_work_tree(the_repository,
+		N_("rewind rebase"),
+		_("Please commit or stash them."), 1, 0);
+
+	if (file_exists(rebase_path_todo_orig()))
+		return error(_("you are already rewinding a rebase.\n"
+			       "Use rebase --edit-todo to continue."));
+
+	revisions = xstrfmt("%s..HEAD", oid_to_hex(&opts->onto->object.oid));
+	strvec_pushl(&make_script_args, "", revisions, NULL);
+	free(revisions);
+
+	ret = sequencer_make_script(the_repository, &todo_list.buf,
+				    make_script_args.nr, make_script_args.v,
+				    flags);
+	strvec_clear(&make_script_args);
+
+	if (ret)
+		error(_("could not generate todo list"));
+	else {
+		if (flags & TODO_LIST_ABBREVIATE_CMDS)
+			strbuf_addstr(&todo_list.buf, "b\n\n");
+		else
+			strbuf_addstr(&todo_list.buf, "break\n\n");
+
+		if (strbuf_read_file(&todo_list.buf, todo_file, 0) < 0) {
+			strbuf_release(&todo_list.buf);
+			return error_errno(_("could not read '%s'."), todo_file);
+		}
+
+		discard_index(&the_index);
+		if (todo_list_parse_insn_buffer(the_repository, todo_list.buf.buf,
+						&todo_list))
+			BUG("unusable todo list");
+
+		ret = complete_action(the_repository, &replay, flags,
+			NULL, opts->onto_name, &opts->onto->object.oid,
+			&opts->orig_head->object.oid, &opts->exec,
+			opts->autosquash, opts->update_refs, &todo_list,
+			opts->action);
+	}
+
+	todo_list_release(&todo_list);
+
+	return ret;
+}
+
 static int run_sequencer_rebase(struct rebase_options *opts)
 {
 	unsigned flags = 0;
@@ -342,6 +407,9 @@ static int run_sequencer_rebase(struct rebase_options *opts)
 	case ACTION_EDIT_TODO:
 		ret = edit_todo_file(flags);
 		break;
+	case ACTION_REWIND:
+		ret = rewind_todo_file(opts, flags);
+		break;
 	case ACTION_SHOW_CURRENT_PATCH: {
 		struct child_process cmd = CHILD_PROCESS_INIT;
 
@@ -1088,6 +1156,8 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 			    N_("abort but keep HEAD where it is"), ACTION_QUIT),
 		OPT_CMDMODE(0, "edit-todo", &options.action, N_("edit the todo list "
 			    "during an interactive rebase"), ACTION_EDIT_TODO),
+		OPT_CMDMODE(0, "rewind", &options.action, N_("rewind an interactive "
+			    "rebase"), ACTION_REWIND),
 		OPT_CMDMODE(0, "show-current-patch", &options.action,
 			    N_("show the patch file being applied or merged"),
 			    ACTION_SHOW_CURRENT_PATCH),
@@ -1235,6 +1305,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 	if (options.action == ACTION_EDIT_TODO && !is_merge(&options))
 		die(_("The --edit-todo action can only be used during "
 		      "interactive rebase."));
+	else if (options.action == ACTION_REWIND && !is_merge(&options))
+		die(_("The --rewind action can only be used during "
+		      "interactive rebase."));
 
 	if (trace2_is_enabled()) {
 		if (is_merge(&options))
@@ -1339,17 +1412,21 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 	case ACTION_EDIT_TODO:
 		options.dont_finish_rebase = 1;
 		goto run_rebase;
+	case ACTION_REWIND:
+		if (read_basic_state(&options))
+			exit(1);
+		break;
 	case ACTION_SHOW_CURRENT_PATCH:
 		options.dont_finish_rebase = 1;
 		goto run_rebase;
 	case ACTION_NONE:
 		break;
 	default:
 		BUG("action: %d", options.action);
 	}
 
 	/* Make sure no rebase is in progress */
-	if (in_progress) {
+	if (in_progress && options.action != ACTION_REWIND) {
 		const char *last_slash = strrchr(options.state_dir, '/');
 		const char *state_dir_base =
 			last_slash ? last_slash + 1 : options.state_dir;
@@ -1570,6 +1647,15 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 		options.flags |= REBASE_FORCE;
 	}
 
+	// We branch off after handling any option that could usefully
+	// affect the re-creation of the todo list.
+	// The omission of --onto from that is debatable.
+	// Options that will be overwritten by read_basic_state() are
+	// meaningless, so we can branch out before processing these;
+	// though arguably, it should be possible to change some of them.
+	if (options.action == ACTION_REWIND)
+		goto run_rebase;
+
 	if (!options.root) {
 		if (argc < 1) {
 			struct branch *branch;
diff --git a/rebase-interactive.c b/rebase-interactive.c
index a3d8925b06..d72ac7b8d1 100644
--- a/rebase-interactive.c
+++ b/rebase-interactive.c
@@ -87,6 +87,16 @@ void append_todo_help(int command_count, enum rebase_action action,
 			"of an ongoing interactive rebase.\n"
 			"To continue rebase after editing, run:\n"
 			"    git rebase --continue\n\n");
+	else if (action == ACTION_REWIND)
+		msg = _("\nYou are rewinding "
+			"an ongoing interactive rebase.\n"
+			"If you remove everything, "
+			"the todo file will be left unchanged.\n\n");
+	else if (action == ACTION_RESUME_REWIND)
+		msg = _("\nYou are correcting the rewind of "
+			"an ongoing interactive rebase.\n"
+			"If you remove everything, "
+			"the todo file will be restored.\n\n");
 	else
 		msg = _("\nHowever, if you remove everything, "
 			"the rebase will be aborted.\n\n");
@@ -101,9 +111,18 @@ enum edit_todo_result edit_todo_list(
 		   enum rebase_action action)
 {
 	const char *todo_file = rebase_path_todo(),
-		*todo_backup = rebase_path_todo_backup();
+		*todo_backup = rebase_path_todo_backup(),
+		*todo_file_orig = rebase_path_todo_orig(),
+		*done_file = rebase_path_done(),
+		*done_file_orig = rebase_path_done_orig();
 	int incorrect = 0;
 
+	if (action == ACTION_REWIND) {
+		if (rename(todo_file, todo_file_orig) ||
+		    rename(done_file, done_file_orig))
+			return error_errno(_("cannot displace todo file"));
+	}
+
 	/* If the user is editing the todo list, we first try to parse
 	 * it.  If there is an error, we do not return, because the user
 	 * might want to fix it in the first place. */
@@ -127,8 +146,14 @@ enum edit_todo_result edit_todo_list(
 		return EDIT_TODO_FAILED;
 
 	strbuf_stripspace(&new_todo->buf, 1);
-	if (action != ACTION_EDIT_TODO && new_todo->buf.len == 0)
+	if (action != ACTION_EDIT_TODO && new_todo->buf.len == 0) {
+		if (action == ACTION_REWIND || action == ACTION_RESUME_REWIND) {
+			if (rename(todo_file_orig, todo_file) ||
+			    rename(done_file_orig, done_file))
+				return error_errno(_("cannot restore todo file"));
+		}
 		return EDIT_TODO_ABORT;
+	}
 
 	if (todo_list_parse_insn_buffer(r, new_todo->buf.buf, new_todo)) {
 		fprintf(stderr, _(edit_todo_list_advice));
@@ -148,6 +173,11 @@ enum edit_todo_result edit_todo_list(
 		return EDIT_TODO_INCORRECT;
 	}
 
+	if (action == ACTION_REWIND) {
+		unlink(todo_file_orig);
+		unlink(done_file_orig);
+	}
+
 	/*
 	 * See if branches need to be added or removed from the update-refs
 	 * file based on the new todo list.
diff --git a/rebase-interactive.h b/rebase-interactive.h
index 5aa4111b4f..260dc7c53f 100644
--- a/rebase-interactive.h
+++ b/rebase-interactive.h
@@ -12,6 +12,8 @@ enum rebase_action {
 	ACTION_ABORT,
 	ACTION_QUIT,
 	ACTION_EDIT_TODO,
+	ACTION_REWIND,
+	ACTION_RESUME_REWIND,
 	ACTION_SHOW_CURRENT_PATCH,
 	ACTION_LAST
 };
diff --git a/sequencer.c b/sequencer.c
index 0b4d16b8e8..0e1d92b238 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -62,15 +62,17 @@ static GIT_PATH_FUNC(rebase_path, "rebase-merge")
  */
 GIT_PATH_FUNC(rebase_path_todo, "rebase-merge/git-rebase-todo")
 GIT_PATH_FUNC(rebase_path_todo_backup, "rebase-merge/git-rebase-todo.backup")
+GIT_PATH_FUNC(rebase_path_todo_orig, "rebase-merge/git-rebase-todo.orig")
 
 GIT_PATH_FUNC(rebase_path_dropped, "rebase-merge/dropped")
 
 /*
  * The rebase command lines that have already been processed. A line
  * is moved here when it is first handled, before any associated user
  * actions.
  */
-static GIT_PATH_FUNC(rebase_path_done, "rebase-merge/done")
+GIT_PATH_FUNC(rebase_path_done, "rebase-merge/done")
+GIT_PATH_FUNC(rebase_path_done_orig, "rebase-merge/done.orig")
 /*
  * The file to keep track of how many commands were already processed (e.g.
  * for the prompt).
@@ -6113,7 +6115,10 @@ int complete_action(struct repository *r, struct replay_opts *opts, unsigned fla
 	struct strbuf *buf = &todo_list->buf;
 	int res;
 
-	find_unique_abbrev_r(shortonto, onto, DEFAULT_ABBREV);
+	if (action == ACTION_NONE)
+		find_unique_abbrev_r(shortonto, onto, DEFAULT_ABBREV);
+	else if (read_populate_opts(opts))
+		return -1;
 
 	if (buf->len == 0) {
 		struct todo_item *item = append_new_todo(todo_list);
@@ -6143,11 +6148,20 @@ int complete_action(struct repository *r, struct replay_opts *opts, unsigned fla
 	if (res == EDIT_TODO_IOERROR)
 		return -1;
 	else if (res == EDIT_TODO_FAILED) {
+		if (action == ACTION_REWIND)
+			return -1;
+
 		apply_autostash(rebase_path_autostash());
 		sequencer_remove_state(opts);
 
 		return -1;
 	} else if (res == EDIT_TODO_ABORT) {
+		if (action == ACTION_REWIND) {
+			todo_list_release(&new_todo);
+
+			return error(_("rewind aborted; state unchanged"));
+		}
+
 		apply_autostash(rebase_path_autostash());
 		sequencer_remove_state(opts);
 		todo_list_release(&new_todo);
@@ -6239,7 +6253,7 @@ static int skip_fixupish(const char *subject, const char **p) {
 int todo_list_rearrange_squash(struct todo_list *todo_list)
 {
 	struct hashmap subject2item;
-	int rearranged = 0, *next, *tail, i, nr = 0;
+	int rearranged = 0, *next, *tail, i, j, nr = 0;
 	char **subjects;
 	struct commit_todo_item commit_todo;
 	struct todo_item *items = NULL;
@@ -6266,6 +6280,10 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 		int i2 = -1;
 		struct subject2item_entry *entry;
 
+		// When rewinding, process only up to the marker.
+		if (item->command == TODO_BREAK)
+			break;
+
 		next[i] = tail[i] = -1;
 		if (!item->commit || item->command == TODO_DROP) {
 			subjects[i] = NULL;
@@ -6350,9 +6368,9 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 	if (rearranged) {
 		items = ALLOC_ARRAY(items, todo_list->nr);
 
-		for (i = 0; i < todo_list->nr; i++) {
-			enum todo_command command = todo_list->items[i].command;
-			int cur = i;
+		for (j = 0; j < i; j++) {
+			enum todo_command command = todo_list->items[j].command;
+			int cur = j;
 
 			/*
 			 * Initially, all commands are 'pick's. If it is a
@@ -6367,16 +6385,19 @@ int todo_list_rearrange_squash(struct todo_list *todo_list)
 			}
 		}
 
+		for (; j < todo_list->nr; j++)
+			items[nr++] = todo_list->items[j];
+
 		assert(nr == todo_list->nr);
 		todo_list->alloc = nr;
 		FREE_AND_NULL(todo_list->items);
 		todo_list->items = items;
 	}
 
 	free(next);
 	free(tail);
-	for (i = 0; i < todo_list->nr; i++)
-		free(subjects[i]);
+	for (j = 0; j < i; j++)
+		free(subjects[j]);
 	free(subjects);
 	hashmap_clear_and_free(&subject2item, struct subject2item_entry, entry);
 
diff --git a/sequencer.h b/sequencer.h
index 33bcff89e0..84d7c076c0 100644
--- a/sequencer.h
+++ b/sequencer.h
@@ -12,7 +12,10 @@ struct repository;
 const char *git_path_commit_editmsg(void);
 const char *rebase_path_todo(void);
 const char *rebase_path_todo_backup(void);
+const char *rebase_path_todo_orig(void);
 const char *rebase_path_dropped(void);
+const char *rebase_path_done(void);
+const char *rebase_path_done_orig(void);
 
 #define APPEND_SIGNOFF_DEDUP (1u << 0)
 
diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index dd47f0bbce..ef68f4470a 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -2180,6 +2180,117 @@ test_expect_success 'bad labels and refs rejected when parsing todo list' '
 	test_path_is_missing execed
 '
 
+test_expect_success 'rebase --rewind' '
+	git checkout primary^0 &&
+	(
+		set_fake_editor &&
+		FAKE_LINES="1 reword 2 3 break 4" \
+			FAKE_COMMIT_MESSAGE="C_reworded" \
+			git rebase -i HEAD~4 &&
+		FAKE_LINES="reword 1 2 3 6" \
+			FAKE_COMMIT_MESSAGE="B_reworded" \
+			git rebase --rewind >output 2>&1
+	) &&
+	grep -q "Rebasing (4/4)" output &&
+	test "$(git log -1 --format=%B HEAD~3)" = "B_reworded" &&
+	test "$(git log -1 --format=%B HEAD~2)" = "C_reworded"
+'
+
+test_expect_success 'rebase --rewind with initially botched todo' '
+	git checkout primary^0 &&
+	(
+		set_fake_editor &&
+		FAKE_LINES="1 reword 2 3 break 4" \
+			FAKE_COMMIT_MESSAGE="C_reworded" \
+			git rebase -i HEAD~4 &&
+		test_must_fail env FAKE_LINES="reword 1 bad 2 3 6" \
+			git rebase --rewind &&
+		grep -q "rewinding" < .git/rebase-merge/git-rebase-todo.backup &&
+		FAKE_LINES="reword 1 pick 2 3 4" \
+			git rebase --edit-todo &&
+		FAKE_COMMIT_MESSAGE="B_reworded" \
+			git rebase --continue
+	) &&
+	test "$(git log -1 --format=%B HEAD~3)" = "B_reworded" &&
+	test "$(git log -1 --format=%B HEAD~2)" = "C_reworded"
+'
+
+test_expect_success 'recursing rebase --rewind with initially botched todo' '
+	git checkout primary^0 &&
+	cat >expect <<-\EOF &&
+	error: you are already rewinding a rebase.
+	Use rebase --edit-todo to continue.
+	EOF
+	(
+		set_fake_editor &&
+		FAKE_LINES="1 reword 2 3 break 4" \
+			FAKE_COMMIT_MESSAGE="C_reworded" \
+			git rebase -i HEAD~4 &&
+		test_must_fail env FAKE_LINES="reword 1 bad 2 3 6" \
+			git rebase --rewind &&
+		test_must_fail env FAKE_LINES="reword 1 pick 2 3 4" \
+			git rebase --rewind >actual 2>&1  &&
+		test_cmp expect actual &&
+		git rebase --abort
+	)
+'
+
+test_expect_success 'rebase --rewind being aborted' '
+	git checkout primary^0 &&
+	cat >expect <<-\EOF &&
+	error: rewind aborted; state unchanged
+	EOF
+	(
+		set_fake_editor &&
+		FAKE_LINES="1 reword 2 3 break 4" \
+			FAKE_COMMIT_MESSAGE="C_reworded" \
+			git rebase -i HEAD~4 &&
+		test_must_fail env FAKE_LINES="#" \
+			git rebase --rewind >output 2>&1 &&
+		tail -n 1 output >actual &&  # Ignore output about changing todo list
+		test_cmp expect actual &&
+		git rebase --continue
+	) &&
+	test "$(git log -1 --format=%B HEAD~2)" = "C_reworded"
+'
+
+test_expect_success 'rebase --rewind being aborted after initially botched todo' '
+	git checkout primary^0 &&
+	cat >expect <<-\EOF &&
+	error: rewind aborted; state restored
+	EOF
+	(
+		set_fake_editor &&
+		FAKE_LINES="1 reword 2 3 break 4" \
+			FAKE_COMMIT_MESSAGE="C_reworded" \
+			git rebase -i HEAD~4 &&
+		test_must_fail env FAKE_LINES="reword 1 bad 2 3 6" \
+			git rebase --rewind &&
+		test_must_fail env FAKE_LINES="#" \
+			git rebase --edit-todo >output 2>&1 &&
+		tail -n 1 output >actual &&  # Ignore output about changing todo list
+		test_cmp expect actual &&
+		git rebase --continue
+	) &&
+	test "$(git log -1 --format=%B HEAD~2)" = "C_reworded"
+'
+
+test_expect_failure 'rebase --rewind vs. --update-refs' '
+	git checkout primary^0 &&
+	git branch -f first HEAD~3 &&
+	(
+		set_fake_editor &&
+		FAKE_LINES="1 2 reword 4 5 break 6 7" \
+			FAKE_COMMIT_MESSAGE="C_reworded" \
+			git rebase -i --update-refs HEAD~4 &&
+		FAKE_LINES="reword 1 2 3 4 7 8" \
+			FAKE_COMMIT_MESSAGE="B_reworded" \
+			git rebase --rewind
+	) &&
+	test_cmp_rev HEAD~3 refs/heads/first &&
+	test_cmp_rev HEAD refs/heads/primary
+'
+
 # This must be the last test in this file
 test_expect_success '$EDITOR and friends are unchanged' '
 	test_editor_unchanged
-- 
2.40.0.152.g15d061e6df

Re: [RFC PATCH] rebase: implement --rewind

[Johannes Schindelin]

Hi Oswald,

On Thu, 23 Mar 2023, Oswald Buddenhagen wrote:

> This is fundamentally --edit-todo, except that we first prepend the
> already applied commits and reset back to `onto`. This is useful when
> one finds that a prior change needs (further) modifications.
>
> This patch implements "flat" rewind, that is, once the todo edit has
> been committed, one can abort only the complete rebase. The pre-rewind
> position is marked with a `break` command (these pile up when rewinding
> multiple times; the user is expected to clean them up as necessary).
>
> An alternative to that would be "nested" rewind, where one can return to
> the pre-rewind state even after committing the todo edit. However, this:
> - would add somewhat significant complexity due to having to maintain a
>   stack of todos and HEADs
> - would be mildly confusing to use due to needing to track the state of
>   the stack. One could simplify this somewhat by hiding the rest of the
>   previous todo before nesting, but this would be somewhat limiting in
>   turn (one might want to defer a factored out hunk, and stashing it is
>   not necessarily the most elegant way to do it).
> - would be of somewhat limited usefulness, speaking from experience
>
> This patch leaves transitive resolution of rewritten-list to the
> consumer. This is probably a bad idea.
> Somewhat related to that, --update-refs isn't properly handled yet.

This is an interesting idea but I do not think that the concept in its
current form mixes well with being in the middle of a `--rebase-merges`
run. Which is what I would want to see supported because I find myself
wishing for _something_ like this [*1*].

On the other hand, it might often be good enough to redo only the commits
between `onto` and `HEAD`, not the complete rebase script that's now in
`done`. But then it does not strike me so much as "rewinding" but as
"nesting.

In other words, I would then prefer to see support for `git rebase -i
--nested` be added. I wrote up my thoughts about this in
https://github.com/gitgitgadget/git/issues/211 and was tempted several
times to start implementing it already, only for other, more pressing
things to come up and take my attention.

What do you think, would you be amenable to combine efforts?

Ciao,
Johannes

Footnote *1*: I usually find myself adding a temporary worktree with a
detached `HEAD`, performing the nested rebase, and then resetting the
original worktree to the output of `rev-parse HEAD` in the temporary
worktree. Cumbersome, yes, and it works, but yes, I dearly want something
that works without requiring _me_ to keep tabs on the state.

Re: [RFC PATCH] rebase: implement --rewind

[Oswald Buddenhagen]

On Tue, Mar 28, 2023 at 04:53:52PM +0200, Johannes Schindelin wrote:
>I do not think that the concept in its
>current form mixes well with being in the middle of a `--rebase-merges`
>run.
>
fundamentally, it shouldn't pose a problem: the already done part leads 
up to a single commit, from which a complete todo with merges up to that 
point can be built again, while the remainder of the pre-existing todo 
should be unfazed by the fact that you're repeatedly messing with 
whatever branch you stopped in.
i *think* i even tried a few simple cases and found the result adequate, 
but i don't remember for sure (it's been a few months since i authored 
the patch).
just give it a shot.

>On the other hand, it might often be good enough to redo only the 
>commits
>between `onto` and `HEAD`, not the complete rebase script that's now in
>`done`. But then it does not strike me so much as "rewinding" but as
>"nesting.
>
according to the terminology i'm using, this still qualifies as a flat 
rewind, only that it limits itself to --first-parent. we'll see whether 
this turns out to be a necessary simplification, but i don't think so.

true nesting would mean that the rewind itself can be aborted, in case 
you change your mind back. adding that as an option on top of what i'm 
doing isn't a hard problem _per se_. you would need to figure out the 
challenges from my OP, though.
also note the reference in the OP; we discussed this here a while ago 
already.

Re: [RFC PATCH] rebase: implement --rewind

[Johannes Schindelin]

Hi Oswald,

please do reply-to-all on this list.

On Tue, 28 Mar 2023, Oswald Buddenhagen wrote:

> On Tue, Mar 28, 2023 at 04:53:52PM +0200, Johannes Schindelin wrote:
> >I do not think that the concept in its
> >current form mixes well with being in the middle of a `--rebase-merges`
> >run.
>
> fundamentally, it shouldn't pose a problem: the already done part leads up to
> a single commit, from which a complete todo with merges up to that point can
> be built again, while the remainder of the pre-existing todo should be unfazed
> by the fact that you're repeatedly messing with whatever branch you stopped
> in.

I guess the most important question is: What problem is the proposed
`--rewind` option supposed to solve?

If the idea is to let the user re-start the rebase (for whatever reason),
throwing away the current state, then the proposed code really does not
handle the `--rebase-merges` case at all. Instead, it would implicitly
restart the rebase with `--no-rebase-merges`, i.e. the opposite of what
the user asked for.

But a more important concern is: Is this `--rewind` idea even a good one?
This question brings me back to the initial question: What problem do we
try to solve here? (This is a question that try as I might, I cannot see
answered in the proposed commit message.)

Since I do not want to speculate about your motivation, let me explain the
challenges I would like to see addressed with those rewound-or-nested
rebases.

I frequently find myself in _large_ rebases (we're talking about several
thousand commits, with some 100-200 merge commits), where I notice in the
middle that I should have resolved a previous merge conflict in a
different way.

Do I want to start over and redo the whole rebase? Sometimes I do, and
`git rebase --abort` and the Bash history (Ctrl+R -i will get me back to
the start of the interactive rebase) are my friend. No `--rewind`
required. (Which makes me wonder why that same strategy is not good enough
for your scenarios, too.)

However, that's what I need only in a few, rare instances.

What I need much, much, much more often is a way to redo only _part_ of
the rebase. Like, the last 3 commits. And not from scratch, oh no! I do
not want the original commits to be cherry-picked, but the ones that were
already rebased.

In other words, I need a nested rebase.

Now, why do I keep bringing up this idea of a nested rebase, when such a
nested rebase would not be able to perform a rewind as you asked?

The reason is that I am still very much unconvinced that `--rewind` can do
anything that `git rebase --abort` and starting over cannot do. So: no
patches required, right?

However, the use case that _immediately_ comes to mind when you talk about
these rewinds is when a part of a rebase needs to be redone, in the middle
of said rebase. And that _does_ require a nested rebase, and the
`--rewind` would in most cases only throw away too much work.

Ciao,
Johannes

P.S.: Yes, yes, I know, a nested rebase can be simulated via

	git worktree add --detach /tmp/throw-away &&
	git -C /tmp/throw-away rebase -i HEAD~3 &&
	git reset --hard $(git -C /tmp/throw-away rev-parse HEAD) &&
	git worktree remove /tmp/throw-away

but that is of course not only inconvenient, but leaves too much
book-keeping and safe-guarding up to the human user, e.g. to make sure
that the `git reset --hard` does not overwrite uncommitted changes/files.

FWIW I simulate nested rebases in the illustrated way _a lot_.

Re: [RFC PATCH] rebase: implement --rewind

[Oswald Buddenhagen]

On Wed, Apr 05, 2023 at 02:07:29PM +0200, Johannes Schindelin wrote:
>This question brings me back to the initial question: What problem do 
>we try to solve here? (This is a question that try as I might, I cannot 
>see answered in the proposed commit message.)
>
and i, try as i might, don't understand what you're not understanding 
...

>[...] In other words, I need a nested rebase.
>
that's just *your* private terminology. i don't apply the term "nested" 
here, because for me that implies the possibility to "unnest", which my 
patch doesn't implement. instead, it just continues past the point where 
the rewind was initiated. it's the difference between a loop and 
recursion.
but outside this difference in terminology, for all i can tell, my patch 
implements *exactly* what you're asking for, and i don't understand why 
that's not obvious to you, given how well you understand the problem 
space yourself.
please describe what you want with _a few_ words and without introducing 
any new terminology first, i.e., something you'd actually want to see in 
the feature's summary documentation. that should illuminate what 
keywords you find critical.

i just gave rewinding rebasing merges a shot, and it didn't work for the 
simple reason that --rebase-merges is not saved in the state 
(understandably, because that was unnecessary so far) and the 
combination of --rewind --rebase-merges is being rejected. i'll need to 
fix that.

then there is the problem that --rebase-merges only redoes merges rather 
than replaying them. but it seems that the simple case with unmodified 
parents actually does get replayed (or rather, skipped over, just 
incredibly slowly), so rewinding to just the last merge would work fine.  
other than that, i'm declaring the matter out of scope and deferring to 
your "replaying evil merges" sub-thread.

Re: [RFC PATCH] rebase: implement --rewind

[Phillip Wood]

On 05/04/2023 13:07, Johannes Schindelin wrote:
> Hi Oswald,
> 
> please do reply-to-all on this list.
> 
> On Tue, 28 Mar 2023, Oswald Buddenhagen wrote:
> 
>> On Tue, Mar 28, 2023 at 04:53:52PM +0200, Johannes Schindelin wrote:
>>> I do not think that the concept in its
>>> current form mixes well with being in the middle of a `--rebase-merges`
>>> run.

That definitely needs to be addressed, I'd be happy to start with an 
implementation that only rewinds linear history but it must error out if 
it encounters a merge and --rebase-merges was given. I'd also be very 
happy if we could rewind across merges by updating existing labels in 
the new todo list.

> [...] 
> What I need much, much, much more often is a way to redo only _part_ of
> the rebase. Like, the last 3 commits. And not from scratch, oh no! I do
> not want the original commits to be cherry-picked, but the ones that were
> already rebased.

That's what I want most often as well. Oswald's --rewind always rewinds 
to $onto but I think it does use the rebased commits in the new todo 
list. It looks like the new todo list will contain the commits 
$onto..HEAD plus the old todo list

> In other words, I need a nested rebase.

I can see the benefit in being able to checkpoint while rebasing but I'm 
not sure that needs to be tied to rewinding. For example if I'm making a 
change I'm not sure about I'd like to be able to set a checkpoint before 
that change so I can rewind to the previous state. I'd be happy to see 
checkpointing and rewinding added separately.

Best Wishes

Phillip

> Now, why do I keep bringing up this idea of a nested rebase, when such a
> nested rebase would not be able to perform a rewind as you asked?
> 
> The reason is that I am still very much unconvinced that `--rewind` can do
> anything that `git rebase --abort` and starting over cannot do. So: no
> patches required, right?
> 
> However, the use case that _immediately_ comes to mind when you talk about
> these rewinds is when a part of a rebase needs to be redone, in the middle
> of said rebase. And that _does_ require a nested rebase, and the
> `--rewind` would in most cases only throw away too much work.
> 
> Ciao,
> Johannes
> 
> P.S.: Yes, yes, I know, a nested rebase can be simulated via
> 
> 	git worktree add --detach /tmp/throw-away &&
> 	git -C /tmp/throw-away rebase -i HEAD~3 &&
> 	git reset --hard $(git -C /tmp/throw-away rev-parse HEAD) &&
> 	git worktree remove /tmp/throw-away
> 
> but that is of course not only inconvenient, but leaves too much
> book-keeping and safe-guarding up to the human user, e.g. to make sure
> that the `git reset --hard` does not overwrite uncommitted changes/files.
> 
> FWIW I simulate nested rebases in the illustrated way _a lot_.

Re: [RFC PATCH] rebase: implement --rewind

[Ævar Arnfjörð Bjarmason]

On Wed, Apr 05 2023, Oswald Buddenhagen wrote:

> On Wed, Apr 05, 2023 at 02:07:29PM +0200, Johannes Schindelin wrote:
>> This question brings me back to the initial question: What problem
>> do we try to solve here? (This is a question that try as I might, I
>> cannot see answered in the proposed commit message.)
>>
> and i, try as i might, don't understand what you're not understanding
> ...
>
>>[...] In other words, I need a nested rebase.
>>
> that's just *your* private terminology. i don't apply the term
> "nested" here, because for me that implies the possibility to
> "unnest", which my patch doesn't implement. instead, it just continues
> past the point where the rewind was initiated. it's the difference
> between a loop and recursion.
> but outside this difference in terminology, for all i can tell, my
> patch implements *exactly* what you're asking for, and i don't
> understand why that's not obvious to you, given how well you
> understand the problem space yourself.
> please describe what you want with _a few_ words and without
> introducing any new terminology first, i.e., something you'd actually
> want to see in the feature's summary documentation. that should
> illuminate what keywords you find critical.
>
> i just gave rewinding rebasing merges a shot, and it didn't work for
> the simple reason that --rebase-merges is not saved in the state
> (understandably, because that was unnecessary so far) and the
> combination of --rewind --rebase-merges is being rejected. i'll need
> to fix that.
>
> then there is the problem that --rebase-merges only redoes merges
> rather than replaying them. but it seems that the simple case with
> unmodified parents actually does get replayed (or rather, skipped
> over, just incredibly slowly), so rewinding to just the last merge
> would work fine.  other than that, i'm declaring the matter out of
> scope and deferring to your "replaying evil merges" sub-thread.

Not Johannes, but I'd also like to have "nested", but maybe your feature
would also provide that. I haven't had time to test it, sorry.

But isn't the difference noted in this aspect of your commit message:
"where one can return to the pre-rewind state even after committing the
todo edit".

My most common use-case for "nested" is certainly less complex that
Johannes's, and is the following:

 * I've got e.g. a 10 patch series

 * I start rebasing that on "master", solve conflicts with "1..4", and
   am now on a conflict on 5/10.

 * It now becomes obvious to me that the even larger conflict I'm about
   to have on 6/10 would be better handled if I went back to 2/10 or
   whatever, did a change I could do here in 5/10 differently, and then
   proceeded.

I.e. when I'm at 5/10 I'd conceptually like to do another "git rebase -i
HEAD~5" or whatever, use the *already rewritten* commits (otherwise I'd
just abort and restast), re-arrange/rewrite them, and when I'm done
return to 5/10.

Then do another "continue".

From a UX perspective I think just as our $PS1 integration can be made
to show "5/10" it would be ideal if in this case we could show
e.g. "5/10 -> 1/5" or whatever. I.e. I'm in a nested rebase of 1/5,
which started from that 5/10".

Right now I do this sort of thing manually, i.e. note the SHA-1's I've
got so far, --abort at 5/10, then start a rebase for all 10 again, but
manually replace the SHA-1's for 1-5 with the ones I had already.

Which, I suppose I could also do the other way around, i.e. at 5/10 I'd
--edit-todo, wipe away 6/10, "finish" my rebase, then use "git rebase
--onto" later when I'm done to transplant the remaining 6-10/10 on the
1-5/5 I'm now happy with.

But here's the important bit: Sometimes I'm just wrong about my re-edit
to 2/10 being the right thing, and it would actually just make things
worse, as I might discover in my "nested" rebase once I'm at 4/5 or
whatever.

So being able to do an "--abort" ot that point to go back to the
"un-nested" 5/10 (*not* "original" 5/10) and proceed from there would be
nice.

But I think what you've implemented doesn't do that at all, or am I
misunderstanding you?

I think a relatively simple hack to "restart" might still be very nice,
just clarifying.

Re: [RFC PATCH] rebase: implement --rewind

[Oswald Buddenhagen]

On Thu, Apr 06, 2023 at 12:45:02PM +0200, Ævar Arnfjörð Bjarmason wrote:
>My most common use-case for "nested" is certainly less complex that
>Johannes's, and is the following:
>
> * I've got e.g. a 10 patch series
>
> * I start rebasing that on "master", solve conflicts with "1..4", and
>   am now on a conflict on 5/10.
>
> * It now becomes obvious to me that the even larger conflict I'm about
>   to have on 6/10 would be better handled if I went back to 2/10 or
>   whatever, did a change I could do here in 5/10 differently, and then
>   proceeded.
>
>I.e. when I'm at 5/10 I'd conceptually like to do another "git rebase 
>-i
>HEAD~5" or whatever, use the *already rewritten* commits (otherwise I'd
>just abort and restast), re-arrange/rewrite them, and when I'm done
>return to 5/10.
>
yes, this patch addresses this use case - mostly.

i'm generally dealing with an even more benign case, because i'm 
"rebasing" with --keep-base most of the time (and i have the thing 
aliased to 'reshape' - maybe something for upstream?).

the case of rewinding from a conflicted state currently needs manual 
handling. i suppose i should detect the state, re-insert the pick, and 
reset hard out of it, as if --skip was used. the implicit 
destructiveness feels wrong, though. maybe require --force?

>But here's the important bit: Sometimes I'm just wrong about my re-edit
>to 2/10 being the right thing, and it would actually just make things
>worse, as I might discover in my "nested" rebase once I'm at 4/5 or
>whatever.
>
>So being able to do an "--abort" ot that point to go back to the
>"un-nested" 5/10 (*not* "original" 5/10) and proceed from there would be
>nice.
>
yeah, i'm experiencing that sometimes, but not often enough to bother 
automating it. manual recovery by hand-editing the todo after rewinding 
again did the trick so far.

>From a UX perspective I think just as our $PS1 integration can be made
>to show "5/10" it would be ideal if in this case we could show
>e.g. "5/10 -> 1/5" or whatever. I.e. I'm in a nested rebase of 1/5,
>which started from that 5/10".
>
hmm, i think you just pointed out johannes' hangup to me. ^^

you both are assuming a limited rewind, where you explicitly specify the 
affected range, and the todo list editor presents only that. you're 
deriving the term "nested" from the fact that it's an isolated subset of 
the rewritten commits.

however, i see these problems with that aproach:
- as mentioned in the OP, i might want to move hunks out of the nested 
   range. i could stash them, but then i'm dealing with two methods of 
   organizing the history, which gets really messy
- it gets even trickier if i want to move commits *into* the nested 
   range - i'd have to manually insert a pick, and then deal with the 
   possible conflict after unnesting
- who says that the nesting point should be the last chance to change my 
   mind? suppose i stop at 10, get the idea to re-edit 5, but after 
   reaching 15 i notice that re-editing 5 (and thus probably also 10)  
   was a terrible idea, so i want to go back to pre-nest 10

now suppose my approach, where the rebase is rewound right to `onto`, 
and the whole remaining todo is left in place. the nested base is 
implicitly determined by the first modified line of the rewound todo, so 
there is no harm in rewinding the whole rebase (*). and the rebase can 
just continue past the rewind point without anything special happening.  

if we want to be able to undo the rewind, we push HEAD and the todo list 
onto a stack. as phillip said, that's basically just a checkpoint, which 
happens to be automatically created when we are rewinding. that could be 
presented at the prompt as "REBASE 5/10 [1]" to signify the number of 
available checkpoints (and you'd access them with 'git rebase --restore 
[<id>]', quite similarly to stashes).

of course it gets really "interesting" when you want to go back to a 
checkpoint, but also want to salvage some of the rewritten commits. then 
you'll have to manually pick commits from the reflog, etc., but i don't 
see how one could possibly get around the complexity (we could present a 
combined todo file where alternative versions of commits are shown in 
comments, but that's quite some effort for only a slight improvement).

(*) actually, there is:
- firstly, having the entire todo in front of you can be rather annoying 
   when it's more than two dozen commits long and the part you want to 
   edit isn't near the beginning.
- secondly, skipping over merges doesn't appear to be a thing, so 
   johannes' use case would be *insanely* slow. but that's "only" an 
   implementation issue.

given these problems, i can see that it would make sense to accept an 
optional argument that limits the depth of the rewind (without impacting 
the overall approach).

thanks!

Re: [RFC PATCH] rebase: implement --rewind

[Felipe Contreras]

On Thu, Apr 6, 2023 at 7:03 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Wed, Apr 05 2023, Oswald Buddenhagen wrote:

> Right now I do this sort of thing manually, i.e. note the SHA-1's I've
> got so far, --abort at 5/10, then start a rebase for all 10 again, but
> manually replace the SHA-1's for 1-5 with the ones I had already.

Couldn't this be considered a rerebase?

This is what I do most of the time, except I don't even bother saving
and replacing the SHA-1s, rerere reapplies my fixes so it's
straightforward to reach the desired state.

> Which, I suppose I could also do the other way around, i.e. at 5/10 I'd
> --edit-todo, wipe away 6/10, "finish" my rebase, then use "git rebase
> --onto" later when I'm done to transplant the remaining 6-10/10 on the
> 1-5/5 I'm now happy with.

With this approach the reflog wouldn't be an accurate representation
of what happened.

Most of the times I do a rebase I want to see the difference with the
previous state of the branch, so I do `git diff @{1}`, but this won't
work with this frankensteinian rebase which in true is comprised of
multiple subrebases.

> But here's the important bit: Sometimes I'm just wrong about my re-edit
> to 2/10 being the right thing, and it would actually just make things
> worse, as I might discover in my "nested" rebase once I'm at 4/5 or
> whatever.
>
> So being able to do an "--abort" ot that point to go back to the
> "un-nested" 5/10 (*not* "original" 5/10) and proceed from there would be
> nice.

Yes, this is something I often desire.


But I feel you guys are overcomplicating the problem.

Imagine there was a rebase log for each branch, then `git rebase`
could use that information to redo a previous rebase, even if that
rebase was aborted. To restart your current rebase you could do `git
rebase -i --redo 1` (1 being the previous one). If in the middle of
that you decide actually your original approach was better, you just
freely abort, and do `git rebase -i --redo 2`.

Wouldn't that solve all the problems?

The complication comes in trying to do that without the concept of
rebase history.

Cheers.

-- 
Felipe Contreras

Re: [RFC PATCH] rebase: implement --rewind

[Oswald Buddenhagen]

On Thu, Apr 06, 2023 at 07:21:39PM -0500, Felipe Contreras wrote:
>Imagine there was a rebase log for each branch, then `git rebase`
>could use that information to redo a previous rebase, even if that
>rebase was aborted. To restart your current rebase you could do `git
>rebase -i --redo 1` (1 being the previous one). If in the middle of
>that you decide actually your original approach was better, you just
>freely abort, and do `git rebase -i --redo 2`.
>
what exactly would you save to that log?
what comes to my mind is the todo file produced by my --rewind before 
the user edits it: the already rewritten commits (which can of course be 
saved as a single ref), and the remaining todo.
that would make it very much the same thing as the checkpoints phillip 
postulated and i expanded upon.

one difference to what i envisaged would be that one could easily resume 
a rebase one erroneously discarded entirely.

>Wouldn't that solve all the problems?
>
it would, but not necessarily optimally.

consider that after the initial implementation phase, my working branch 
is most of the time inside a 'reshape' (rebase -i --keep-base), and 
since i wrote the initial version of rewind, i initiate new reshapes 
much less often. i basically move freely between the commits in the 
branch.
inserting an additional step of aborting prior to redoing feels just 
clumsy.
at this point i'm actually thinking in the opposite direction: introduce 
commands that let me move by a few commits without even opening the todo 
editor (where have i seen that already? jj?).

the second aspect is performance/resource usage.
the intermediate abort would potentially touch a lot of files each time.  
that costs ssd life and often unneeded recompiles.
and given johannes' use case with *many* merges, rebasing from scratch 
would waste *quite* some time. as i pointed out in the other mail, my 
approach currently suffers from that as well, but it would be rather 
easy to sidestep it. your approach otoh would definitely need a 
fundamental improvement to the skipping algo (*).

(*) this of course sounds like a good idea regardless, but it's not 
necessarily wise to bet on it. i think the problem here is that redoing 
merges is *expected* to be "lossy". if they were marked for replay as 
proposed in https://github.com/gitgitgadget/git/pull/1491 , one could 
also just skip over them.

Re: [RFC PATCH] rebase: implement --rewind

[Phillip Wood]

On 07/04/2023 08:00, Oswald Buddenhagen wrote:

> at this point i'm actually thinking in the opposite direction: introduce 
> commands that let me move by a few commits without even opening the todo 
> editor (where have i seen that already? jj?).

When I'm working on a patch series I use this approach a lot with a "git 
rewrite" script I have. To amend a commit I run "git rewrite amend 
<commit>" and it will start a rebase or rewind the current one. It will 
also take a file, line number pair and use "git diff" to map that line 
onto HEAD and then "git blame" to work out which commit to amend so you 
can run it from your editor and say "amend the commit that added this 
line" which is a great time saver. I'd love to a command like that 
upstream in git but I don't think it covers all the cases that "rebase 
--rewind" does such as dscho rebasing git-for-windows.

Best Wishes

Phillip