patchrebase --merge: optionally skip upstreamed commits

> When rebasing against an upstream that has had many commits since the
> original branch was created:
>
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
>
> because "git rebase" attempts to exclude commits that are duplicates of
> upstream ones, it must read the contents of every novel upstream commit,
> in addition to the tip of the upstream and the merge base.

> This can be a significant performance hit, especially in a partial
> clone, wherein a read of an object may end up being a fetch.
>
> Add a flag to "git rebase" to allow suppression of this feature. This
> flag only works when using the "merge" backend.
>
> This flag changes the behavior of sequencer_make_script(), called from
> do_interactive_rebase() <- run_rebase_interactive() <-
> run_specific_rebase() <- cmd_rebase(). With this flag, limit_list()
> (indirectly called from sequencer_make_script() through
> prepare_revision_walk()) will no longer call cherry_pick_list(), and
> thus PATCHSAME is no longer set. Refraining from setting PATCHSAME both
> means that the intermediate commits in upstream are no longer read (as
> shown by the test) and means that no PATCHSAME-caused skipping of
> commits is done by sequencer_make_script(), either directly or through
> make_script_with_merges().

> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
> More improvements for partial clone, but this is a benefit for
> non-partial-clone as well, hence the way I wrote the commit message (not
> focusing too much on partial clone) and the documentation.
>
> I've chosen --skip-already-present and --no-skip-already-present to
> reuse the language already existing in the documentation and to avoid a
> double negative (e.g. --avoid-checking-if-already-present and
> --no-avoid-checking-if-already-present) but this causes some clumsiness
> in the documentation and in the code. Any suggestions for the name are
> welcome.
>
> I've only implemented this for the "merge" backend since I think that
> there is an effort to migrate "rebase" to use the "merge" backend by
> default, and also because "merge" uses diff internally which already has
> the (per-commit) blob batch prefetching.

> ---
>  Documentation/git-rebase.txt | 12 +++++-
>  builtin/rebase.c             | 10 ++++-
>  sequencer.c                  |  3 +-
>  sequencer.h                  |  2 +-
>  t/t3402-rebase-merge.sh      | 77 ++++++++++++++++++++++++++++++++++++
>  5 files changed, 100 insertions(+), 4 deletions(-)
>
> diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
> index 0c4f038dd6..f73a82b4a9 100644
> --- a/Documentation/git-rebase.txt
> +++ b/Documentation/git-rebase.txt
> @@ -318,6 +318,15 @@ See also INCOMPATIBLE OPTIONS below.
>  +
>  See also INCOMPATIBLE OPTIONS below.
>
> +--skip-already-present::
> +--no-skip-already-present::
> +	Skip commits that are already present in the new upstream.
> +	This is the default.

> ++
> +If the skip-if-already-present feature is unnecessary or undesired,
> +`--no-skip-already-present` may improve performance since it avoids
> +the need to read the contents of every commit in the new upstream.
> +
>  --rerere-autoupdate::
>  --no-rerere-autoupdate::
>  	Allow the rerere mechanism to update the index with the
> @@ -866,7 +875,8 @@ Only works if the changes (patch IDs based on the diff contents) on
>  'subsystem' did.
>
>  In that case, the fix is easy because 'git rebase' knows to skip
> -changes that are already present in the new upstream.  So if you say
> +changes that are already present in the new upstream (unless
> +`--no-skip-already-present` is given). So if you say

>  (assuming you're on 'topic')
>  ------------
>      $ git rebase subsystem
> diff --git a/builtin/rebase.c b/builtin/rebase.c
> index 6154ad8fa5..943211e5bb 100644
> --- a/builtin/rebase.c
> +++ b/builtin/rebase.c
> @@ -88,13 +88,15 @@ struct rebase_options {
>  	struct strbuf git_format_patch_opt;
>  	int reschedule_failed_exec;
>  	int use_legacy_rebase;
> +	int skip_already_present;
>  };
>
>  #define REBASE_OPTIONS_INIT {			  	\
>  		.type = REBASE_UNSPECIFIED,	  	\
>  		.flags = REBASE_NO_QUIET, 		\
>  		.git_am_opts = ARGV_ARRAY_INIT,		\
> -		.git_format_patch_opt = STRBUF_INIT	\
> +		.git_format_patch_opt = STRBUF_INIT,	\
> +		.skip_already_present =	1		\
>  	}
>
>  static struct replay_opts get_replay_opts(const struct rebase_options *opts)
> @@ -373,6 +375,7 @@ static int run_rebase_interactive(struct rebase_options *opts,
>  	flags |= opts->rebase_cousins > 0 ? TODO_LIST_REBASE_COUSINS : 0;
>  	flags |= opts->root_with_onto ? TODO_LIST_ROOT_WITH_ONTO : 0;
>  	flags |= command == ACTION_SHORTEN_OIDS ? TODO_LIST_SHORTEN_IDS : 0;
> +	flags |= opts->skip_already_present ? TODO_LIST_SKIP_ALREADY_PRESENT : 0;
>
>  	switch (command) {
>  	case ACTION_NONE: {
> @@ -1507,6 +1510,8 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>  		OPT_BOOL(0, "reschedule-failed-exec",
>  			 &reschedule_failed_exec,
>  			 N_("automatically re-schedule any `exec` that fails")),
> +		OPT_BOOL(0, "skip-already-present", &options.skip_already_present,
> +			 N_("skip changes that are already present in the new upstream")),

>  		OPT_END(),
>  	};
>  	int i;
> @@ -1840,6 +1845,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>  			      "interactive or merge options"));
>  	}
>
> +	if (!options.skip_already_present && !is_interactive(&options))
> +		die(_("--no-skip-already-present does not work with the 'am' backend"));
> +
>  	if (options.signoff) {
>  		if (options.type == REBASE_PRESERVE_MERGES)
>  			die("cannot combine '--signoff' with "
> diff --git a/sequencer.c b/sequencer.c
> index ba90a513b9..752580c017 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -4797,12 +4797,13 @@ int sequencer_make_script(struct repository *r, struct strbuf *out, int argc,
>  	int keep_empty = flags & TODO_LIST_KEEP_EMPTY;
>  	const char *insn = flags & TODO_LIST_ABBREVIATE_CMDS ? "p" : "pick";
>  	int rebase_merges = flags & TODO_LIST_REBASE_MERGES;
> +	int skip_already_present = !!(flags & TODO_LIST_SKIP_ALREADY_PRESENT);
>
>  	repo_init_revisions(r, &revs, NULL);
>  	revs.verbose_header = 1;
>  	if (!rebase_merges)
>  		revs.max_parents = 1;
> -	revs.cherry_mark = 1;
> +	revs.cherry_mark = skip_already_present;

>  	revs.limited = 1;
>  	revs.reverse = 1;
>  	revs.right_only = 1;
> diff --git a/sequencer.h b/sequencer.h
> index 393571e89a..39bb12f624 100644
> --- a/sequencer.h
> +++ b/sequencer.h
> @@ -149,7 +149,7 @@ int sequencer_remove_state(struct replay_opts *opts);
>   * `--onto`, we do not want to re-generate the root commits.
>   */
>  #define TODO_LIST_ROOT_WITH_ONTO (1U << 6)
> -
> +#define TODO_LIST_SKIP_ALREADY_PRESENT (1U << 7)

>  int sequencer_make_script(struct repository *r, struct strbuf *out, int argc,
>  			  const char **argv, unsigned flags);
> diff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh
> index a1ec501a87..9b52739a10 100755
> --- a/t/t3402-rebase-merge.sh
> +++ b/t/t3402-rebase-merge.sh
> @@ -162,4 +162,81 @@ test_expect_success 'rebase --skip works with two conflicts in a row' '
>  	git rebase --skip
>  '
>
> +test_expect_success '--no-skip-already-present' '
> +	git init repo &&
> +
> +	# O(1-10) -- O(1-11) -- O(0-10) master
> +	#        \
> +	#         -- O(1-11) -- O(1-12) otherbranch
> +
> +	printf "Line %d\n" $(test_seq 1 10) >repo/file.txt &&
> +	git -C repo add file.txt &&
> +	git -C repo commit -m "base commit" &&
> +
> +	printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> +	git -C repo commit -a -m "add 11" &&
> +
> +	printf "Line %d\n" $(test_seq 0 10) >repo/file.txt &&
> +	git -C repo commit -a -m "add 0 delete 11" &&
> +
> +	git -C repo checkout -b otherbranch HEAD^^ &&
> +	printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> +	git -C repo commit -a -m "add 11 in another branch" &&
> +
> +	printf "Line %d\n" $(test_seq 1 12) >repo/file.txt &&
> +	git -C repo commit -a -m "add 12 in another branch" &&
> +
> +	# Regular rebase fails, because the 1-11 commit is deduplicated
> +	test_must_fail git -C repo rebase --merge master 2> err &&
> +	test_i18ngrep "error: could not apply.*add 12 in another branch" err &&
> +	git -C repo rebase --abort &&
> +
> +	# With --no-skip-already-present, it works
> +	git -C repo rebase --merge --no-skip-already-present master
> +'
> +
> +test_expect_success '--no-skip-already-present refrains from reading unneeded blobs' '
> +	git init server &&
> +
> +	# O(1-10) -- O(1-11) -- O(1-12) master
> +	#        \
> +	#         -- O(0-10) otherbranch
> +
> +	printf "Line %d\n" $(test_seq 1 10) >server/file.txt &&
> +	git -C server add file.txt &&
> +	git -C server commit -m "merge base" &&
> +
> +	printf "Line %d\n" $(test_seq 1 11) >server/file.txt &&
> +	git -C server commit -a -m "add 11" &&
> +
> +	printf "Line %d\n" $(test_seq 1 12) >server/file.txt &&
> +	git -C server commit -a -m "add 12" &&
> +
> +	git -C server checkout -b otherbranch HEAD^^ &&
> +	printf "Line %d\n" $(test_seq 0 10) >server/file.txt &&
> +	git -C server commit -a -m "add 0" &&
> +
> +	test_config -C server uploadpack.allowfilter 1 &&
> +	test_config -C server uploadpack.allowanysha1inwant 1 &&
> +
> +	git clone --filter=blob:none "file://$(pwd)/server" client &&
> +	git -C client checkout origin/master &&
> +	git -C client checkout origin/otherbranch &&
> +
> +	# Sanity check to ensure that the blobs from the merge base and "add
> +	# 11" are missing
> +	git -C client rev-list --objects --all --missing=print >missing_list &&
> +	MERGE_BASE_BLOB=$(git -C server rev-parse master^^:file.txt) &&
> +	ADD_11_BLOB=$(git -C server rev-parse master^:file.txt) &&
> +	grep "\\?$MERGE_BASE_BLOB" missing_list &&
> +	grep "\\?$ADD_11_BLOB" missing_list &&
> +
> +	git -C client rebase --merge --no-skip-already-present origin/master &&
> +
> +	# The blob from the merge base had to be fetched, but not "add 11"
> +	git -C client rev-list --objects --all --missing=print >missing_list &&
> +	! grep "\\?$MERGE_BASE_BLOB" missing_list &&
> +	grep "\\?$ADD_11_BLOB" missing_list
> +'
> +
>  test_done
> --
> 2.25.1.481.gfbce0eb801-goog

> Hi Jonathan,
> 
> This patch makes good sense to me. I left a few notes below, but they
> are relatively minor, and this seems to be all in a good direction.
> 
> As a (somewhat) interesting aside, this feature would be useful to me
> outside of partial clones, since I often have this workflow in my local
> development wherein 'git rebase' spends quite a bit of time comparing
> patches on my branch to everything new upstream.

> This sentence is a little confusing if you skip over the graph, since it
> reads: "When rebasing against an because ... because ...". It may be
> clearer if you swap the order of the last two clauses to instead be:
> 
>   it must read the contents of every novel upstream commit, in addition to
>   the tip of the upstream and the merge base, because "git rebase"
>   attempts to exclude commits that are duplicates of upstream ones.

> > +--skip-already-present::
> > +--no-skip-already-present::
> > +	Skip commits that are already present in the new upstream.
> > +	This is the default.
> 
> I believe that you mean '--skip-already-present' is the default, here,
> but the placement makes it ambiguous, since it is in a paragraph with a
> header that contains both the positive and negated version of this flag.
> 
> Maybe this could changed to: s/This/--skip-already-present/'.

> >  In that case, the fix is easy because 'git rebase' knows to skip
> > -changes that are already present in the new upstream.  So if you say
> > +changes that are already present in the new upstream (unless
> > +`--no-skip-already-present` is given). So if you say
> 
> Extremely minor nit: there is a whitespace change on this line where the
> original has two spaces between the '.' and 'So', and the new version
> has only one.

> > diff --git a/sequencer.h b/sequencer.h
> > index 393571e89a..39bb12f624 100644
> > --- a/sequencer.h
> > +++ b/sequencer.h
> > @@ -149,7 +149,7 @@ int sequencer_remove_state(struct replay_opts *opts);
> >   * `--onto`, we do not want to re-generate the root commits.
> >   */
> >  #define TODO_LIST_ROOT_WITH_ONTO (1U << 6)
> > -
> > +#define TODO_LIST_SKIP_ALREADY_PRESENT (1U << 7)
> 
> This was another spot that I thought could maybe be turned into an enum,
> but it's clearly not the fault of your patch, and could easily be turned
> into #leftoverbits.

> When rebasing against an upstream that has had many commits since the
> original branch was created:
>
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
>
> because "git rebase" attempts to exclude commits that are duplicates of
> upstream ones, it must read the contents of every novel upstream commit,
> in addition to the tip of the upstream and the merge base. This can be a
> significant performance hit, especially in a partial clone, wherein a
> read of an object may end up being a fetch.
>
> Add a flag to "git rebase" to allow suppression of this feature. This
> flag only works when using the "merge" backend.

> I wonder whether we can make this a bit more user-friendly by defaulting
> to `--right-only` if there are no promised objects in the symmetric range,
> and if there _are_ promised objects, to skip `--right-only`, possibly with
> an advice that we did that and how to force it to download the promised
> objects?

>
> When rebasing against an upstream that has had many commits since the
> original branch was created:
>
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
>
> because "git rebase" attempts to exclude commits that are duplicates of
> upstream ones, it must read the contents of every novel upstream commit,
> in addition to the tip of the upstream and the merge base. This can be a
> significant performance hit, especially in a partial clone, wherein a
> read of an object may end up being a fetch.

> This flag changes the behavior of sequencer_make_script(), called from
> do_interactive_rebase() <- run_rebase_interactive() <-
> run_specific_rebase() <- cmd_rebase(). With this flag, limit_list()
> (indirectly called from sequencer_make_script() through
> prepare_revision_walk()) will no longer call cherry_pick_list(), and
> thus PATCHSAME is no longer set. Refraining from setting PATCHSAME both
> means that the intermediate commits in upstream are no longer read (as
> shown by the test) and means that no PATCHSAME-caused skipping of
> commits is done by sequencer_make_script(), either directly or through
> make_script_with_merges().
>
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> ---
> More improvements for partial clone, but this is a benefit for
> non-partial-clone as well, hence the way I wrote the commit message (not
> focusing too much on partial clone) and the documentation.

> I've chosen --skip-already-present and --no-skip-already-present to
> reuse the language already existing in the documentation and to avoid a
> double negative (e.g. --avoid-checking-if-already-present and
> --no-avoid-checking-if-already-present) but this causes some clumsiness
> in the documentation and in the code. Any suggestions for the name are
> welcome.

> ---
>  Documentation/git-rebase.txt | 12 +++++-
>  builtin/rebase.c             | 10 ++++-
>  sequencer.c                  |  3 +-
>  sequencer.h                  |  2 +-
>  t/t3402-rebase-merge.sh      | 77 ++++++++++++++++++++++++++++++++++++
>  5 files changed, 100 insertions(+), 4 deletions(-)
>
> diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
> index 0c4f038dd6..f73a82b4a9 100644
> --- a/Documentation/git-rebase.txt
> +++ b/Documentation/git-rebase.txt
> @@ -318,6 +318,15 @@ See also INCOMPATIBLE OPTIONS below.
>  +
>  See also INCOMPATIBLE OPTIONS below.
>
> +--skip-already-present::
> +--no-skip-already-present::
> +       Skip commits that are already present in the new upstream.
> +       This is the default.
> ++
> +If the skip-if-already-present feature is unnecessary or undesired,
> +`--no-skip-already-present` may improve performance since it avoids
> +the need to read the contents of every commit in the new upstream.
> +

>  --rerere-autoupdate::
>  --no-rerere-autoupdate::
>         Allow the rerere mechanism to update the index with the
> @@ -866,7 +875,8 @@ Only works if the changes (patch IDs based on the diff contents) on
>  'subsystem' did.
>
>  In that case, the fix is easy because 'git rebase' knows to skip
> -changes that are already present in the new upstream.  So if you say
> +changes that are already present in the new upstream (unless
> +`--no-skip-already-present` is given). So if you say
>  (assuming you're on 'topic')
>  ------------
>      $ git rebase subsystem
> diff --git a/builtin/rebase.c b/builtin/rebase.c
> index 6154ad8fa5..943211e5bb 100644
> --- a/builtin/rebase.c
> +++ b/builtin/rebase.c
> @@ -88,13 +88,15 @@ struct rebase_options {
>         struct strbuf git_format_patch_opt;
>         int reschedule_failed_exec;
>         int use_legacy_rebase;
> +       int skip_already_present;
>  };
>
>  #define REBASE_OPTIONS_INIT {                          \
>                 .type = REBASE_UNSPECIFIED,             \
>                 .flags = REBASE_NO_QUIET,               \
>                 .git_am_opts = ARGV_ARRAY_INIT,         \
> -               .git_format_patch_opt = STRBUF_INIT     \
> +               .git_format_patch_opt = STRBUF_INIT,    \
> +               .skip_already_present = 1               \
>         }
>
>  static struct replay_opts get_replay_opts(const struct rebase_options *opts)
> @@ -373,6 +375,7 @@ static int run_rebase_interactive(struct rebase_options *opts,
>         flags |= opts->rebase_cousins > 0 ? TODO_LIST_REBASE_COUSINS : 0;
>         flags |= opts->root_with_onto ? TODO_LIST_ROOT_WITH_ONTO : 0;
>         flags |= command == ACTION_SHORTEN_OIDS ? TODO_LIST_SHORTEN_IDS : 0;
> +       flags |= opts->skip_already_present ? TODO_LIST_SKIP_ALREADY_PRESENT : 0;
>
>         switch (command) {
>         case ACTION_NONE: {
> @@ -1507,6 +1510,8 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>                 OPT_BOOL(0, "reschedule-failed-exec",
>                          &reschedule_failed_exec,
>                          N_("automatically re-schedule any `exec` that fails")),
> +               OPT_BOOL(0, "skip-already-present", &options.skip_already_present,
> +                        N_("skip changes that are already present in the new upstream")),
>                 OPT_END(),
>         };
>         int i;
> @@ -1840,6 +1845,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>                               "interactive or merge options"));
>         }
>
> +       if (!options.skip_already_present && !is_interactive(&options))
> +               die(_("--no-skip-already-present does not work with the 'am' backend"));
> +

>         if (options.signoff) {
>                 if (options.type == REBASE_PRESERVE_MERGES)
>                         die("cannot combine '--signoff' with "
> diff --git a/sequencer.c b/sequencer.c
> index ba90a513b9..752580c017 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -4797,12 +4797,13 @@ int sequencer_make_script(struct repository *r, struct strbuf *out, int argc,
>         int keep_empty = flags & TODO_LIST_KEEP_EMPTY;
>         const char *insn = flags & TODO_LIST_ABBREVIATE_CMDS ? "p" : "pick";
>         int rebase_merges = flags & TODO_LIST_REBASE_MERGES;
> +       int skip_already_present = !!(flags & TODO_LIST_SKIP_ALREADY_PRESENT);
>
>         repo_init_revisions(r, &revs, NULL);
>         revs.verbose_header = 1;
>         if (!rebase_merges)
>                 revs.max_parents = 1;
> -       revs.cherry_mark = 1;
> +       revs.cherry_mark = skip_already_present;
>         revs.limited = 1;
>         revs.reverse = 1;
>         revs.right_only = 1;
> diff --git a/sequencer.h b/sequencer.h
> index 393571e89a..39bb12f624 100644
> --- a/sequencer.h
> +++ b/sequencer.h
> @@ -149,7 +149,7 @@ int sequencer_remove_state(struct replay_opts *opts);
>   * `--onto`, we do not want to re-generate the root commits.
>   */
>  #define TODO_LIST_ROOT_WITH_ONTO (1U << 6)
> -
> +#define TODO_LIST_SKIP_ALREADY_PRESENT (1U << 7)
>
>  int sequencer_make_script(struct repository *r, struct strbuf *out, int argc,
>                           const char **argv, unsigned flags);
> diff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh
> index a1ec501a87..9b52739a10 100755
> --- a/t/t3402-rebase-merge.sh
> +++ b/t/t3402-rebase-merge.sh
> @@ -162,4 +162,81 @@ test_expect_success 'rebase --skip works with two conflicts in a row' '
>         git rebase --skip
>  '
>
> +test_expect_success '--no-skip-already-present' '
> +       git init repo &&
> +
> +       # O(1-10) -- O(1-11) -- O(0-10) master
> +       #        \
> +       #         -- O(1-11) -- O(1-12) otherbranch
> +
> +       printf "Line %d\n" $(test_seq 1 10) >repo/file.txt &&
> +       git -C repo add file.txt &&
> +       git -C repo commit -m "base commit" &&
> +
> +       printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> +       git -C repo commit -a -m "add 11" &&
> +
> +       printf "Line %d\n" $(test_seq 0 10) >repo/file.txt &&
> +       git -C repo commit -a -m "add 0 delete 11" &&
> +
> +       git -C repo checkout -b otherbranch HEAD^^ &&
> +       printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> +       git -C repo commit -a -m "add 11 in another branch" &&
> +
> +       printf "Line %d\n" $(test_seq 1 12) >repo/file.txt &&
> +       git -C repo commit -a -m "add 12 in another branch" &&
> +
> +       # Regular rebase fails, because the 1-11 commit is deduplicated
> +       test_must_fail git -C repo rebase --merge master 2> err &&
> +       test_i18ngrep "error: could not apply.*add 12 in another branch" err &&
> +       git -C repo rebase --abort &&
> +
> +       # With --no-skip-already-present, it works
> +       git -C repo rebase --merge --no-skip-already-present master
> +'
> +
> +test_expect_success '--no-skip-already-present refrains from reading unneeded blobs' '
> +       git init server &&
> +
> +       # O(1-10) -- O(1-11) -- O(1-12) master
> +       #        \
> +       #         -- O(0-10) otherbranch
> +
> +       printf "Line %d\n" $(test_seq 1 10) >server/file.txt &&
> +       git -C server add file.txt &&
> +       git -C server commit -m "merge base" &&
> +
> +       printf "Line %d\n" $(test_seq 1 11) >server/file.txt &&
> +       git -C server commit -a -m "add 11" &&
> +
> +       printf "Line %d\n" $(test_seq 1 12) >server/file.txt &&
> +       git -C server commit -a -m "add 12" &&
> +
> +       git -C server checkout -b otherbranch HEAD^^ &&
> +       printf "Line %d\n" $(test_seq 0 10) >server/file.txt &&
> +       git -C server commit -a -m "add 0" &&
> +
> +       test_config -C server uploadpack.allowfilter 1 &&
> +       test_config -C server uploadpack.allowanysha1inwant 1 &&
> +
> +       git clone --filter=blob:none "file://$(pwd)/server" client &&
> +       git -C client checkout origin/master &&
> +       git -C client checkout origin/otherbranch &&
> +
> +       # Sanity check to ensure that the blobs from the merge base and "add
> +       # 11" are missing
> +       git -C client rev-list --objects --all --missing=print >missing_list &&
> +       MERGE_BASE_BLOB=$(git -C server rev-parse master^^:file.txt) &&
> +       ADD_11_BLOB=$(git -C server rev-parse master^:file.txt) &&
> +       grep "\\?$MERGE_BASE_BLOB" missing_list &&
> +       grep "\\?$ADD_11_BLOB" missing_list &&
> +
> +       git -C client rebase --merge --no-skip-already-present origin/master &&
> +
> +       # The blob from the merge base had to be fetched, but not "add 11"
> +       git -C client rev-list --objects --all --missing=print >missing_list &&
> +       ! grep "\\?$MERGE_BASE_BLOB" missing_list &&
> +       grep "\\?$ADD_11_BLOB" missing_list
> +'
> +
>  test_done
> --
> 2.25.1.481.gfbce0eb801-goog

> On Mon, Mar 9, 2020 at 1:58 PM Jonathan Tan <jonathantanmy@google.com> wrote:
> >
> > When rebasing against an upstream that has had many commits since the
> > original branch was created:
> >
> >  O -- O -- ... -- O -- O (upstream)
> >   \
> >    -- O (my-dev-branch)
> >
> > because "git rebase" attempts to exclude commits that are duplicates of
> > upstream ones, it must read the contents of every novel upstream commit,
> > in addition to the tip of the upstream and the merge base. This can be a
> > significant performance hit, especially in a partial clone, wherein a
> > read of an object may end up being a fetch.
> 
> Does this suggest that the cherry-pick detection is suboptimal and
> needs to be improved?  When rebasing, it is typical that you are just
> rebasing a small number of patches compared to how many exist
> upstream.  As such, any upstream patch modifying files outside the set
> of files modified on the rebased side is known to not be PATCHSAME
> without looking at those new files.

> Or is the issue just the sheer
> number of upstream commits that modify only the files also modified on
> the rebased side is large?
> 
> > Add a flag to "git rebase" to allow suppression of this feature. This
> > flag only works when using the "merge" backend.
> 
> Interesting.  A little over a year ago we discussed not only making
> such a change in behavior, but making it the default; see
> https://public-inbox.org/git/nycvar.QRO.7.76.6.1901211635080.41@tvgsbejvaqbjf.bet/
> (from "Ooh, that's interesting" to "VFS for Git").

> Yes, I've wanted to kill that performance overhead too even without
> partial clones, though I was slightly worried about cases of a known
> cherry-pick no longer cleanly applying and thus forcing the user to
> detect that it has become empty.  I guess that's why it's a flag
> instead of the new default, but there's something inside of me that
> asks why this special case is detected for the user when other
> conflict cases aren't...  Not sure if I'm just pigeonholing on
> performance too much.

> > I've only implemented this for the "merge" backend since I think that
> > there is an effort to migrate "rebase" to use the "merge" backend by
> > default, and also because "merge" uses diff internally which already has
> > the (per-commit) blob batch prefetching.
> 
> I understand the first half of your reason here, but I don't follow
> the second half.  The apply backend uses diff to generate the patches,
> but diff isn't the relevant operation here; it's the rev-list walking,
> and both call the exact same rev-list walk the last time I checked so
> I'm not sure what the difference is here.  Am I misunderstanding one
> or more things?

> > +--skip-already-present::
> > +--no-skip-already-present::
> > +       Skip commits that are already present in the new upstream.
> > +       This is the default.
> > ++
> > +If the skip-if-already-present feature is unnecessary or undesired,
> > +`--no-skip-already-present` may improve performance since it avoids
> > +the need to read the contents of every commit in the new upstream.
> > +
> 
> I'm afraid the naming might be pretty opaque and confusing to users.
> Even if we do keep the names, it might help to be clearer about the
> ramifications.  And there's a missing reference to the option
> incompatibility.  Perhaps something like:
> 
> --skip-cherry-pick-detection
> --no-skip-cherry-pick-detection
> 
>     Whether rebase tries to determine if commits are already present
> upstream, i.e. if there are commits which are cherry-picks.  If such
> detection is done, any commits being rebased which are cherry-picks
> will be dropped, since those commits are already found upstream.  If
> such detection is not done, those commits will be re-applied, which
> most likely will result in no new changes (as the changes are already
> upstream) and result in the commit being dropped anyway.  cherry-pick
> detection is the default, but can be expensive in repos with a large
> number of upstream commits that need to be read.
> 
> See also INCOMPATIBLE OPTIONS below.

> > +       if (!options.skip_already_present && !is_interactive(&options))
> > +               die(_("--no-skip-already-present does not work with the 'am' backend"));
> > +
> 
> with the *apply* backend, not the 'am' one (the backend was renamed in
> commit 10cdb9f38a ("rebase: rename the two primary rebase backends",
> 2020-02-15))

> > Does this suggest that the cherry-pick detection is suboptimal and
> > needs to be improved?  When rebasing, it is typical that you are just
> > rebasing a small number of patches compared to how many exist
> > upstream.  As such, any upstream patch modifying files outside the set
> > of files modified on the rebased side is known to not be PATCHSAME
> > without looking at those new files.
> 
> That's true - and this would drastically reduce the fetches necessary in
> partial clone, perhaps enough that we no longer need this check.
> 
> In the absence of partial clone, this also might improve performance
> sufficiently, such that we no longer need my new option. (Or it might
> not.)

>
> > > Does this suggest that the cherry-pick detection is suboptimal and
> > > needs to be improved?  When rebasing, it is typical that you are just
> > > rebasing a small number of patches compared to how many exist
> > > upstream.  As such, any upstream patch modifying files outside the set
> > > of files modified on the rebased side is known to not be PATCHSAME
> > > without looking at those new files.
> >
> > That's true - and this would drastically reduce the fetches necessary in
> > partial clone, perhaps enough that we no longer need this check.
> >
> > In the absence of partial clone, this also might improve performance
> > sufficiently, such that we no longer need my new option. (Or it might
> > not.)
>
> I took a further look at this. patch-ids.c and its caller
> (cherry_pick_list() in revision.c) implement duplicate checking by first
> generating full diff outputs for the commits in the shorter side,
> putting them in a hashmap keyed by the SHA-1 of the diff output (and
> values being the commit itself), and then generating full diff outputs
> for the commits in the longer side and checking them against the
> hashmap. When processing the shorter side, we could also generate
> filename-only diffs and put their hashes into a hashset; so when
> processing the longer side, we could generate the filename-only diff
> first (without reading any blobs) and checking them against our new
> hashset, and only if it appears in our new hashset, then do we generate
> the full diff (thus reading blobs).
>
> One issue with this is unpredictability to the user (since which blobs
> get read depend on which side is longer), but that seems resolvable by
> not doing any length checks but always reading the blobs on the right
> side (that is, the non-upstream side).
>
> So I would say that yes, the cherry-pick detection is suboptimal and
> could be improved.

> So the question is...what to do with my patch? An
> argument could be made that my patch should be dropped because an
> improvement in cherry-pick detection would eliminate the need for the
> option I'm introducing in my patch, but after some thought, I think that
> this option will still be useful even with cherry-pick detection.

>  And even if
> a user is not using partial clone at all, I think it is still useful to
> suppress both the filtering of commits (e.g. when upstream has a commit
> then revert, it would be reasonable to cherry-pick the same commit on
> top) and reduce disk reads (although I don't know if this will be the
> case in practice).

>
>  On Thu, Mar 12, 2020 at 11:04 AM Jonathan Tan <jonathantanmy@google.com> wrote:
> >
> > > > Does this suggest that the cherry-pick detection is suboptimal and
> > > > needs to be improved?  When rebasing, it is typical that you are just
> > > > rebasing a small number of patches compared to how many exist
> > > > upstream.  As such, any upstream patch modifying files outside the set
> > > > of files modified on the rebased side is known to not be PATCHSAME
> > > > without looking at those new files.
> > >
> > > That's true - and this would drastically reduce the fetches necessary in
> > > partial clone, perhaps enough that we no longer need this check.
> > >
> > > In the absence of partial clone, this also might improve performance
> > > sufficiently, such that we no longer need my new option. (Or it might
> > > not.)
> >
> > I took a further look at this. patch-ids.c and its caller
> > (cherry_pick_list() in revision.c) implement duplicate checking by first
> > generating full diff outputs for the commits in the shorter side,
> > putting them in a hashmap keyed by the SHA-1 of the diff output (and
> > values being the commit itself), and then generating full diff outputs
> > for the commits in the longer side and checking them against the
> > hashmap. When processing the shorter side, we could also generate
> > filename-only diffs and put their hashes into a hashset; so when
> > processing the longer side, we could generate the filename-only diff
> > first (without reading any blobs) and checking them against our new
> > hashset, and only if it appears in our new hashset, then do we generate
> > the full diff (thus reading blobs).
> >
> > One issue with this is unpredictability to the user (since which blobs
> > get read depend on which side is longer), but that seems resolvable by
> > not doing any length checks but always reading the blobs on the right
> > side (that is, the non-upstream side).
> >
> > So I would say that yes, the cherry-pick detection is suboptimal and
> > could be improved.
>
> Sweet, thanks for doing this investigative work!  Sounds promising.
>
> > So the question is...what to do with my patch? An
> > argument could be made that my patch should be dropped because an
> > improvement in cherry-pick detection would eliminate the need for the
> > option I'm introducing in my patch, but after some thought, I think that
> > this option will still be useful even with cherry-pick detection.
>
> The option may be totally justified here, but can I go on a possible
> tangent and vent for a little bit?  We seem to introduce options an
> awful lot.  While options can be valuable they also have a cost, and I
> think we tend not to acknowledge that.  Some of the negatives:
>
> - Developers add options when they run into bugs instead of fixing
> bugs (usually they don't realize that the behavior in question is a
> bug, but that's exacerbated by a willingness to add options and not
> consider costs)
> - Developers add options without considering combinations of options
> and what they mean (though it's hard to fault them because considering
> combinations becomes harder and harder with the more options we have;
> it's a negative feedback cycle)
> - Growth in number of options leads to code that is hard or impossible
> to refactor based on a maze of competing options with myriad edge and
> corner cases that are fundamentally broken
> - Users get overloaded by the sheer number of options and minor distinctions
>
> The fourth case is probably obvious, so let me just include some
> examples of the first three cases above:
> * Commits b00bf1c9a8 ("git-rebase: make --allow-empty-message the
> default", 2018-06-27), 22a69fda19 ("git-rebase.txt: update description
> of --allow-empty-message", 2020-01-16), and d48e5e21da ("rebase
> (interactive-backend): make --keep-empty the default", 2020-02-15)
> noted that options that previously existed were just workarounds to
> buggy behavior and the flags should have been always on.
> * Commit e86bbcf987 ("clean: disambiguate the definition of -d",
> 2019-09-17) showed a pretty hairy case where the combination of
> options led to cases where I not only didn't know how to implement
> correct behavior, I didn't even know how to state what the desired
> behavior for end-users was.  Despite a few different reports over a
> year and a half that I had a series that fixed some known issues for
> users the series languished because I couldn't get an answer on what
> was right.  See also
> https://lore.kernel.org/git/20190905154735.29784-1-newren@gmail.com/
> * See the huge "Behavioral differences" section of the git-rebase
> manpage, and a combination of rants from me on dir.c:
>   - https://lore.kernel.org/git/20190905154735.29784-1-newren@gmail.com/
>   - https://lore.kernel.org/git/CABPp-BFG3FkTkC=L1v97LUksndkOmCN8ZhNJh5eoNdquE7v9DA@mail.gmail.com/
>   - https://lore.kernel.org/git/pull.676.v3.git.git.1576571586.gitgitgadget@gmail.com/
>   - The commit message of
> https://lore.kernel.org/git/d3136ef52f3306d465a5a6004cdc9ba5b1ae4148.1580495486.git.gitgitgadget@gmail.com/
>
> >  If we
> > move in a direction where not only blobs but also trees (or even
> > commits) are omitted, we'll definitely want this new option.
>
> Why would this new option be needed if we omitted trees?   If trees
> are omitted based on something like sparse-checkouts, then they are
> omitted based on path; shouldn't we be able to avoid walking trees
> just by noting they modified some path outside a requested sparse
> checkout?
>
> I want grep, log, etc. to behave within the cone of a sparse checkout,
> which means that I need trees of upstream branches within the relevant
> paths anyway.  But theoretically I should certainly be able to avoid
> walking trees outside those paths.
>
> >  And even if
> > a user is not using partial clone at all, I think it is still useful to
> > suppress both the filtering of commits (e.g. when upstream has a commit
> > then revert, it would be reasonable to cherry-pick the same commit on
> > top) and reduce disk reads (although I don't know if this will be the
> > case in practice).
>
> That sounds like yet another argument that the behavior you're arguing
> for should be the default, not a flag we make the users pick to
> workaround bugs.  Yes, sometimes weird behaviors beget usecases (cue
> link to xkcd's comic on emacs spacebar overheating) and we need to
> provide transition plans, but I think this might be a case where
> transitioning makes sense.  From a high level, here's my guess
> (emphasis on guess) at the history:
>
> * am checked for upstream patches, because apply would get confused
> trying to apply an already applied patch
> * legacy-interactive-rebase would check for upstream patches as a
> performance optimization because having to shell out to a separate
> cherry-pick process for each commit is slow (and may have also been
> done partially to match am, even though am did it as a workaround)

> And now we're in the state where:
> * The check-for-upstream bits hurt performance, significantly enough
> that we have three different reports of folks not liking it (you, me,
> and Taylor)
> * It actively does the wrong thing in cases such as revert + re-apply
> sequences, which exist in practice (and exist a lot more than they
> should, but they absolutely do exist)

> > We've made changes in other places (e.g. opening an editor for merge
> > or rebase, push.default, etc.); is there any reason a similar change
> > wouldn't be justified here?
> 
> After another day of thought, and my attempt to figure out the reason
> above, perhaps my assumptions about the reason behind the original
> behavior, any my assumptions about the sanity of switching the default
> might not be as grounded as I thought.  Thus, my worries about yet
> another flag may be overstated as well, at least in this case.

> >  If we
> > move in a direction where not only blobs but also trees (or even
> > commits) are omitted, we'll definitely want this new option.
> 
> Why would this new option be needed if we omitted trees?   If trees
> are omitted based on something like sparse-checkouts, then they are
> omitted based on path; shouldn't we be able to avoid walking trees
> just by noting they modified some path outside a requested sparse
> checkout?
> 
> I want grep, log, etc. to behave within the cone of a sparse checkout,
> which means that I need trees of upstream branches within the relevant
> paths anyway.  But theoretically I should certainly be able to avoid
> walking trees outside those paths.

> When rebasing against an upstream that has had many commits since the
> original branch was created:
>
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
>
> it must read the contents of every novel upstream commit, in addition to
> the tip of the upstream and the merge base, because "git rebase"
> attempts to exclude commits that are duplicates of upstream ones. This
> can be a significant performance hit, especially in a partial clone,
> wherein a read of an object may end up being a fetch.

> Jonathan Tan <jonathantanmy@google.com> writes:
> 
> > When rebasing against an upstream that has had many commits since the
> > original branch was created:
> >
> >  O -- O -- ... -- O -- O (upstream)
> >   \
> >    -- O (my-dev-branch)
> >
> > it must read the contents of every novel upstream commit, in addition to
> > the tip of the upstream and the merge base, because "git rebase"
> > attempts to exclude commits that are duplicates of upstream ones. This
> > can be a significant performance hit, especially in a partial clone,
> > wherein a read of an object may end up being a fetch.
> 
> OK.  I presume that we do this by comparing patch IDs?

> Total disabling would of course is OK as a feature, especially for
> the first cut, but I wonder if it would be a reasonable idea to use
> some heuristic to keep the current "filter the same change" feature
> as much as possible but optimize it by filtering the novel upstream
> commits without hitting their trees and blobs (I am assuming that
> you at least are aware of and have the commit objects on the
> upstream side).
> 
> The most false-negative-prone approach is just to compare the
> <author ident, author timestamp> of a candidate upstream commit with
> what you have---if that author does not appear on my-dev-branch, it
> is very unlikely that your change has been accepted upstream.  Of
> course, two people who independently discover the same solution is
> not all that rare, so it does risk false-negative to take too little
> clue from the commits to compare, but at least it is not worse than
> what you are proposing here ;-)  And if one of your commits on
> my-dev-branch _might_ be identical to one of the novel upstream ones,
> at that point, we could dig deeper to actually compute the patch ID
> by fetching the upstream's tree.

> > New in V2: changed parameter name, used Taylor's commit message
> > suggestions, and used Elijah's documentation suggestions.
> 
> Hmph, what was it called earlier?  My gut reaction without much
> thinking finds --no-skip-* a bit confusing double-negation and
> suspect "--[no-]detect-cherry-pick" (which defaults to true for
> backward compatibility) may feel more natural, but I suspect (I do
> not recall details of the discussion on v1) it has been already
> discussed and people found --no-skip-* is OK (in which case I won't
> object)?

> I also wonder if --detect-cherry-pick=(yes|no|auto) may give a
> better end-user experience, with "auto" meaning "do run patch-ID
> based filtering, but if we know it will be expensive (e.g. the
> repository is sparsely cloned), please skip it".  That way, there
> may appear other reasons that makes patch-ID computation expensive
> now or in the fiture, and the users are automatically covered.

>> Hmph, what was it called earlier?  My gut reaction without much
>> thinking finds --no-skip-* a bit confusing double-negation and
>> suspect "--[no-]detect-cherry-pick" (which defaults to true for
>> backward compatibility) may feel more natural, but I suspect (I do
>> not recall details of the discussion on v1) it has been already
>> discussed and people found --no-skip-* is OK (in which case I won't
>> object)?
>
> It was earlier called "--{,no-}skip-already-present" (with the opposite
> meaning, and thus, --skip-already-present is the default), so the double
> negative has always existed. "--detect-cherry-pick" might be a better
> idea...I'll wait to see if anybody else has an opinion.

>> I also wonder if --detect-cherry-pick=(yes|no|auto) may give a
>> better end-user experience, with "auto" meaning "do run patch-ID
>> based filtering, but if we know it will be expensive (e.g. the
>> repository is sparsely cloned), please skip it".  That way, there
>> may appear other reasons that makes patch-ID computation expensive
>> now or in the fiture, and the users are automatically covered.
>
> It might be better to have predictability, and for "auto", I don't know
> if we can have a simple and explainable set of rules as to when to use
> patch-ID-based filtering - for example, in a partial clone with no
> blobs, I would normally want no patch-ID-based filtering, but in a
> partial clone with only a blob size limit, I probably will still want
> patch-ID-based filtering.

>
> Jonathan Tan <jonathantanmy@google.com> writes:
>
> >> Hmph, what was it called earlier?  My gut reaction without much
> >> thinking finds --no-skip-* a bit confusing double-negation and
> >> suspect "--[no-]detect-cherry-pick" (which defaults to true for
> >> backward compatibility) may feel more natural, but I suspect (I do
> >> not recall details of the discussion on v1) it has been already
> >> discussed and people found --no-skip-* is OK (in which case I won't
> >> object)?
> >
> > It was earlier called "--{,no-}skip-already-present" (with the opposite
> > meaning, and thus, --skip-already-present is the default), so the double
> > negative has always existed. "--detect-cherry-pick" might be a better
> > idea...I'll wait to see if anybody else has an opinion.
>
> While "--[no-]detect-cherry-pick" is much better in avoiding double
> negation, it is a horrible name---we do not tell the users what we
> do after we detect cherry pick ("--[no-]skip-cherry-pick-detection"
> does not tell us, either).

> >> I also wonder if --detect-cherry-pick=(yes|no|auto) may give a
> >> better end-user experience, with "auto" meaning "do run patch-ID
> >> based filtering, but if we know it will be expensive (e.g. the
> >> repository is sparsely cloned), please skip it".  That way, there
> >> may appear other reasons that makes patch-ID computation expensive
> >> now or in the fiture, and the users are automatically covered.
> >
> > It might be better to have predictability, and for "auto", I don't know
> > if we can have a simple and explainable set of rules as to when to use
> > patch-ID-based filtering - for example, in a partial clone with no
> > blobs, I would normally want no patch-ID-based filtering, but in a
> > partial clone with only a blob size limit, I probably will still want
> > patch-ID-based filtering.
>
> Perhaps.  You could have something more specific than "auto".  The
> main point was instead of "--[no-]$knob", "--$knob=(yes|no|...)" is
> much easier to extend.  I simply do not know if we will see need to
> extend the vocabulary in the near future (to which you guys who are
> more interested in sparse clones would have much better insight than
> I do).

>
> Elijah Newren <newren@gmail.com> writes:
>
> > 4) Jonathan provided some good examples of cases where the
> > --keep-cherry-pick behavior isn't just slow, but leads to actually
> > wrong answers (a revert followed by an un-revert).
>
> That one cuts both ways, doesn't it?  If your change that upstream
> once thought was good (and got accepted) turned out to be bad and
> they reverted, you do not want to blindly reapply it to break the
> codebase again, and with the "drop duplicate" logic, it would lead
> to a wrong answer silently.
>
> So from correctness point of view, I do not think you can make any
> argument either way.

> @@ -1840,6 +1844,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>  			      "interactive or merge options"));
>  	}
>  
> +	if (options.skip_cherry_pick_detection && !is_interactive(&options))
> +		die(_("--skip-cherry-pick-detection does not work with the 'apply' backend"));
> +

>
> > New in V2: changed parameter name, used Taylor's commit message
> > suggestions, and used Elijah's documentation suggestions.
>
> I think the discussion has shifted away from whether this functionality
> is desirable (or desirable and we should implement this functionality
> without any CLI option) to the name and nature of the CLI option. Before
> I send out a new version, what do you think of using this name and
> documenting it this way:
>
>   --keep-cherry-pick=(always|never)::
>           Control rebase's behavior towards commits in the working
>           branch that are already present upstream, i.e. cherry-picks.
>   +
>   If 'never', these commits will be dropped. Because this necessitates
>   reading all upstream commits, this can be expensive in repos with a
>   large number of upstream commits that need to be read.
>   +
>   If 'always', all commits (including these) will be re-applied. This
>   allows rebase to forgo reading all upstream commits, potentially
>   improving performance.
>   +
>   The default is 'never'.
>   +
>   See also INCOMPATIBLE OPTIONS below.
>
> I've tried to use everyone's suggestions: Junio's suggestions to use the
> "keep" name (instead of "detect", so that we also communicate what we do
> with the result of our detection) and the non-boolean option (for
> extensibility later if we need it), and Elijah's suggestion to use
> "cherry-pick" instead of "duplicate". If this sounds good, I'll update
> the patch and send out a new version.

>> New in V2: changed parameter name, used Taylor's commit message
>> suggestions, and used Elijah's documentation suggestions.
>
> I think the discussion has shifted away from whether this functionality
> is desirable (or desirable and we should implement this functionality
> without any CLI option) to the name and nature of the CLI option. Before
> I send out a new version, what do you think of using this name and
> documenting it this way:
>
>   --keep-cherry-pick=(always|never)::
>   ...
>   The default is 'never'.
>   +
>   See also INCOMPATIBLE OPTIONS below.

> When rebasing against an upstream that has had many commits since the
> original branch was created:
>
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
>
> it must read the contents of every novel upstream commit, in addition to
> the tip of the upstream and the merge base, because "git rebase"
> attempts to exclude commits that are duplicates of upstream ones. This
> can be a significant performance hit, especially in a partial clone,
> wherein a read of an object may end up being a fetch.
>
> Add a flag to "git rebase" to allow suppression of this feature. This
> flag only works when using the "merge" backend.
>
> This flag changes the behavior of sequencer_make_script(), called from
> do_interactive_rebase() <- run_rebase_interactive() <-
> run_specific_rebase() <- cmd_rebase(). With this flag, limit_list()
> (indirectly called from sequencer_make_script() through
> prepare_revision_walk()) will no longer call cherry_pick_list(), and
> thus PATCHSAME is no longer set. Refraining from setting PATCHSAME both
> means that the intermediate commits in upstream are no longer read (as
> shown by the test) and means that no PATCHSAME-caused skipping of
> commits is done by sequencer_make_script(), either directly or through
> make_script_with_merges().
>
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
> This commit contains Junio's sign-off because I based it on
> jt/rebase-allow-duplicate.
>
> This does not include the fix by Đoàn Trần Công Danh. If we want all
> commits to pass all tests (whether run by Busybox or not) it seems like
> we should squash that patch instead of having it as a separate commit.
> If we do squash, maybe include a "Helped-by" with Đoàn Trần Công Danh's
> name.

> When rebasing against an upstream that has had many commits since the
> original branch was created:
> 
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
> 
> it must read the contents of every novel upstream commit, in addition to
> the tip of the upstream and the merge base, because "git rebase"
> attempts to exclude commits that are duplicates of upstream ones. This
> can be a significant performance hit, especially in a partial clone,
> wherein a read of an object may end up being a fetch.
> 
> Add a flag to "git rebase" to allow suppression of this feature. This
> flag only works when using the "merge" backend.
> 
> This flag changes the behavior of sequencer_make_script(), called from
> do_interactive_rebase() <- run_rebase_interactive() <-
> run_specific_rebase() <- cmd_rebase(). With this flag, limit_list()
> (indirectly called from sequencer_make_script() through
> prepare_revision_walk()) will no longer call cherry_pick_list(), and
> thus PATCHSAME is no longer set. Refraining from setting PATCHSAME both
> means that the intermediate commits in upstream are no longer read (as
> shown by the test) and means that no PATCHSAME-caused skipping of
> commits is done by sequencer_make_script(), either directly or through
> make_script_with_merges().
> 
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
> This commit contains Junio's sign-off because I based it on
> jt/rebase-allow-duplicate.
> 
> This does not include the fix by Đoàn Trần Công Danh. If we want all
> commits to pass all tests (whether run by Busybox or not) it seems like
> we should squash that patch instead of having it as a separate commit.
> If we do squash, maybe include a "Helped-by" with Đoàn Trần Công Danh's
> name.

> When rebasing against an upstream that has had many commits since the
> original branch was created:
> 
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
> 
> it must read the contents of every novel upstream commit, in addition to
> the tip of the upstream and the merge base, because "git rebase"
> attempts to exclude commits that are duplicates of upstream ones. This
> can be a significant performance hit, especially in a partial clone,
> wherein a read of an object may end up being a fetch.
> 
> Add a flag to "git rebase" to allow suppression of this feature. This
> flag only works when using the "merge" backend.

> This flag changes the behavior of sequencer_make_script(), called from
> do_interactive_rebase() <- run_rebase_interactive() <-
> run_specific_rebase() <- cmd_rebase(). With this flag, limit_list()
> (indirectly called from sequencer_make_script() through
> prepare_revision_walk()) will no longer call cherry_pick_list(), and
> thus PATCHSAME is no longer set. Refraining from setting PATCHSAME both
> means that the intermediate commits in upstream are no longer read (as
> shown by the test) and means that no PATCHSAME-caused skipping of
> commits is done by sequencer_make_script(), either directly or through
> make_script_with_merges().
> 
> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
> This commit contains Junio's sign-off because I based it on
> jt/rebase-allow-duplicate.
> 
> This does not include the fix by Đoàn Trần Công Danh. If we want all
> commits to pass all tests (whether run by Busybox or not) it seems like
> we should squash that patch instead of having it as a separate commit.
> If we do squash, maybe include a "Helped-by" with Đoàn Trần Công Danh's
> name.
> 
> Junio wrote [1]:
> 
>> Sounds much better to me.  I do not mind --[no-]keep-cherry-pick,
>> either, by the way.  I know I raised the possibility of having to
>> make it non-bool later, but since then I haven't thought of a good
>> third option myself anyway, so...
> 
> In that case, I think it's better to stick to bool. This also means that
> the change from the version in jt/rebase-allow-duplicate is very small,
> hopefully aiding reviewers - mostly a replacement of
> --skip-cherry-pick-detection with --keep-cherry-pick (which mean the
> same thing).
> 
> [1] https://lore.kernel.org/git/xmqq4kuakjcn.fsf@gitster.c.googlers.com/
> ---
>  Documentation/git-rebase.txt | 21 +++++++++-
>  builtin/rebase.c             |  7 ++++
>  sequencer.c                  |  3 +-
>  sequencer.h                  |  2 +-
>  t/t3402-rebase-merge.sh      | 77 ++++++++++++++++++++++++++++++++++++
>  5 files changed, 107 insertions(+), 3 deletions(-)
> 
> diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
> index 0c4f038dd6..f4f8afeb9a 100644
> --- a/Documentation/git-rebase.txt
> +++ b/Documentation/git-rebase.txt
> @@ -318,6 +318,21 @@ See also INCOMPATIBLE OPTIONS below.
>  +
>  See also INCOMPATIBLE OPTIONS below.
>  
> +--keep-cherry-pick::
> +--no-keep-cherry-pick::

>  --rerere-autoupdate::
>  --no-rerere-autoupdate::
>  	Allow the rerere mechanism to update the index with the
> @@ -568,6 +583,9 @@ In addition, the following pairs of options are incompatible:
>   * --keep-base and --onto
>   * --keep-base and --root
>  
> +Also, the --keep-cherry-pick option requires the use of the merge backend
> +(e.g., through --merge).
> +

>  BEHAVIORAL DIFFERENCES
>  -----------------------
>  
> @@ -866,7 +884,8 @@ Only works if the changes (patch IDs based on the diff contents) on
>  'subsystem' did.
>  
>  In that case, the fix is easy because 'git rebase' knows to skip
> -changes that are already present in the new upstream.  So if you say
> +changes that are already present in the new upstream (unless
> +`--keep-cherry-pick` is given). So if you say
>  (assuming you're on 'topic')
>  ------------
>      $ git rebase subsystem
> diff --git a/builtin/rebase.c b/builtin/rebase.c
> index 8081741f8a..626549b0b2 100644
> --- a/builtin/rebase.c
> +++ b/builtin/rebase.c
> @@ -88,6 +88,7 @@ struct rebase_options {
>  	struct strbuf git_format_patch_opt;
>  	int reschedule_failed_exec;
>  	int use_legacy_rebase;
> +	int keep_cherry_pick;
>  };
>  
>  #define REBASE_OPTIONS_INIT {			  	\
> @@ -381,6 +382,7 @@ static int run_rebase_interactive(struct rebase_options *opts,
>  	flags |= opts->rebase_cousins > 0 ? TODO_LIST_REBASE_COUSINS : 0;
>  	flags |= opts->root_with_onto ? TODO_LIST_ROOT_WITH_ONTO : 0;
>  	flags |= command == ACTION_SHORTEN_OIDS ? TODO_LIST_SHORTEN_IDS : 0;
> +	flags |= opts->keep_cherry_pick ? TODO_LIST_KEEP_CHERRY_PICK : 0;

>  
>  	switch (command) {
>  	case ACTION_NONE: {
> @@ -1515,6 +1517,8 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>  		OPT_BOOL(0, "reschedule-failed-exec",
>  			 &reschedule_failed_exec,
>  			 N_("automatically re-schedule any `exec` that fails")),
> +		OPT_BOOL(0, "keep-cherry-pick", &options.keep_cherry_pick,
> +			 N_("apply all changes, even those already present upstream")),
>  		OPT_END(),
>  	};
>  	int i;
> @@ -1848,6 +1852,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>  			      "interactive or merge options"));
>  	}
>  
> +	if (options.keep_cherry_pick && !is_interactive(&options))
> +		die(_("--keep-cherry-pick does not work with the 'apply' backend"));
> +

>  	if (options.signoff) {
>  		if (options.type == REBASE_PRESERVE_MERGES)
>  			die("cannot combine '--signoff' with "
> diff --git a/sequencer.c b/sequencer.c
> index b9dbf1adb0..7bbb63f444 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -4800,12 +4800,13 @@ int sequencer_make_script(struct repository *r, struct strbuf *out, int argc,
>  	int keep_empty = flags & TODO_LIST_KEEP_EMPTY;
>  	const char *insn = flags & TODO_LIST_ABBREVIATE_CMDS ? "p" : "pick";
>  	int rebase_merges = flags & TODO_LIST_REBASE_MERGES;
> +	int keep_cherry_pick = flags & TODO_LIST_KEEP_CHERRY_PICK;
>  
>  	repo_init_revisions(r, &revs, NULL);
>  	revs.verbose_header = 1;
>  	if (!rebase_merges)
>  		revs.max_parents = 1;
> -	revs.cherry_mark = 1;
> +	revs.cherry_mark = !keep_cherry_pick;
>  	revs.limited = 1;
>  	revs.reverse = 1;
>  	revs.right_only = 1;
> diff --git a/sequencer.h b/sequencer.h
> index 9f9ae291e3..298b7de1c8 100644
> --- a/sequencer.h
> +++ b/sequencer.h
> @@ -148,7 +148,7 @@ int sequencer_remove_state(struct replay_opts *opts);
>   * `--onto`, we do not want to re-generate the root commits.
>   */
>  #define TODO_LIST_ROOT_WITH_ONTO (1U << 6)
> -
> +#define TODO_LIST_KEEP_CHERRY_PICK (1U << 7)
>  
>  int sequencer_make_script(struct repository *r, struct strbuf *out, int argc,
>  			  const char **argv, unsigned flags);
> diff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh
> index a1ec501a87..64200c5f20 100755
> --- a/t/t3402-rebase-merge.sh
> +++ b/t/t3402-rebase-merge.sh
> @@ -162,4 +162,81 @@ test_expect_success 'rebase --skip works with two conflicts in a row' '
>  	git rebase --skip
>  '
>  
> +test_expect_success '--keep-cherry-pick' '
> +	git init repo &&
> +
> +	# O(1-10) -- O(1-11) -- O(0-10) master
> +	#        \
> +	#         -- O(1-11) -- O(1-12) otherbranch
> +
> +	printf "Line %d\n" $(test_seq 1 10) >repo/file.txt &&
> +	git -C repo add file.txt &&
> +	git -C repo commit -m "base commit" &&
> +
> +	printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> +	git -C repo commit -a -m "add 11" &&
> +
> +	printf "Line %d\n" $(test_seq 0 10) >repo/file.txt &&
> +	git -C repo commit -a -m "add 0 delete 11" &&
> +
> +	git -C repo checkout -b otherbranch HEAD^^ &&
> +	printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> +	git -C repo commit -a -m "add 11 in another branch" &&
> +
> +	printf "Line %d\n" $(test_seq 1 12) >repo/file.txt &&
> +	git -C repo commit -a -m "add 12 in another branch" &&
> +
> +	# Regular rebase fails, because the 1-11 commit is deduplicated
> +	test_must_fail git -C repo rebase --merge master 2> err &&
> +	test_i18ngrep "error: could not apply.*add 12 in another branch" err &&
> +	git -C repo rebase --abort &&

> +
> +	# With --keep-cherry-pick, it works
> +	git -C repo rebase --merge --keep-cherry-pick master
> +'
> +
> +test_expect_success '--keep-cherry-pick refrains from reading unneeded blobs' '
> +	git init server &&
> +
> +	# O(1-10) -- O(1-11) -- O(1-12) master
> +	#        \
> +	#         -- O(0-10) otherbranch
> +
> +	printf "Line %d\n" $(test_seq 1 10) >server/file.txt &&
> +	git -C server add file.txt &&
> +	git -C server commit -m "merge base" &&
> +
> +	printf "Line %d\n" $(test_seq 1 11) >server/file.txt &&
> +	git -C server commit -a -m "add 11" &&
> +
> +	printf "Line %d\n" $(test_seq 1 12) >server/file.txt &&
> +	git -C server commit -a -m "add 12" &&
> +
> +	git -C server checkout -b otherbranch HEAD^^ &&
> +	printf "Line %d\n" $(test_seq 0 10) >server/file.txt &&
> +	git -C server commit -a -m "add 0" &&
> +
> +	test_config -C server uploadpack.allowfilter 1 &&
> +	test_config -C server uploadpack.allowanysha1inwant 1 &&
> +
> +	git clone --filter=blob:none "file://$(pwd)/server" client &&
> +	git -C client checkout origin/master &&
> +	git -C client checkout origin/otherbranch &&
> +
> +	# Sanity check to ensure that the blobs from the merge base and "add
> +	# 11" are missing
> +	git -C client rev-list --objects --all --missing=print >missing_list &&
> +	MERGE_BASE_BLOB=$(git -C server rev-parse master^^:file.txt) &&
> +	ADD_11_BLOB=$(git -C server rev-parse master^:file.txt) &&
> +	grep "\\?$MERGE_BASE_BLOB" missing_list &&
> +	grep "\\?$ADD_11_BLOB" missing_list &&
> +
> +	git -C client rebase --merge --keep-cherry-pick origin/master &&
> +
> +	# The blob from the merge base had to be fetched, but not "add 11"
> +	git -C client rev-list --objects --all --missing=print >missing_list &&
> +	! grep "\\?$MERGE_BASE_BLOB" missing_list &&
> +	grep "\\?$ADD_11_BLOB" missing_list
> +'

>> +--keep-cherry-pick::
>> +--no-keep-cherry-pick::
>
> I noticed that this _could_ have been simplified to
>
> 	--[no-]keep-cherry-pick::
>
> but I also see several uses of either in our documentation. Do we
> have a preference? By inspecting the lines before a "no-" string,
> I see that some have these two lines, some use the [no-] pattern,
> and others highlight the --no-<option> flag completely separately.

> > Add a flag to "git rebase" to allow suppression of this feature. This
> > flag only works when using the "merge" backend.
> 
> So this is the behavior that already exists, and you are providing a way
> to suppress it. However, you also change the default in this patch, which
> may surprise users expecting this behavior to continue.

> > +--keep-cherry-pick::
> > +--no-keep-cherry-pick::
> 
> I noticed that this _could_ have been simplified to
> 
> 	--[no-]keep-cherry-pick::
> 
> but I also see several uses of either in our documentation. Do we
> have a preference? By inspecting the lines before a "no-" string,
> I see that some have these two lines, some use the [no-] pattern,
> and others highlight the --no-<option> flag completely separately.

> > +	Control rebase's behavior towards commits in the working
> > +	branch that are already present upstream, i.e. cherry-picks.
> 
> I think the "already present upstream" is misleading. We don't rebase
> things that are _reachable_ already, but this is probably better as
> 
> 	Specify if rebase should include commits in the working branch
> 	that have diffs equivalent to other commits upstream. For example,
> 	a cherry-picked commit has an equivalent diff.

> > +By default, these commits will be dropped. Because this necessitates
> > +reading all upstream commits, this can be expensive in repos with a
> > +large number of upstream commits that need to be read.
> 
> Now I'm confused. Are they dropped by default? Which option does what?
> --keep-cherry-pick makes me think that cherry-picked commits will come
> along for the rebase, so we will not check for them. But you have documented
> that --no-keep-cherry-pick is the default.

> > +re-applied. This allows rebase to forgo reading all upstream commits,
> > +potentially improving performance.
> 
> This reasoning is good. Could you also introduce a config option to make
> --keep-cherry-pick the default? I would like to enable that option by
> default in Scalar, but could also see partial clones wanting to enable that
> by default, too.

> > +See also INCOMPATIBLE OPTIONS below.
> > +
> 
> Could we just say that his only applies with the --merge option? Why require
> the jump to the end of the options section? (After writing this, I go look
> at the rest of the doc file and see this is a common pattern.)

> > +Also, the --keep-cherry-pick option requires the use of the merge backend
> > +(e.g., through --merge).
> > +
> 
> Will the command _fail_ if someone says --keep-cherry-pick without the merge
> backend, or just have no effect? Also, specify the option with ticks and
> 
> 	`--[no-]keep-cherry-pick`
> 
> It seems that none of the options in this section are back-ticked, which I think
> is a doc bug.

> > @@ -381,6 +382,7 @@ static int run_rebase_interactive(struct rebase_options *opts,
> >  	flags |= opts->rebase_cousins > 0 ? TODO_LIST_REBASE_COUSINS : 0;
> >  	flags |= opts->root_with_onto ? TODO_LIST_ROOT_WITH_ONTO : 0;
> >  	flags |= command == ACTION_SHORTEN_OIDS ? TODO_LIST_SHORTEN_IDS : 0;
> > +	flags |= opts->keep_cherry_pick ? TODO_LIST_KEEP_CHERRY_PICK : 0;
> 
> Since opts->keep_cherry_pick is initialized as zero, did you change the default
> behavior? 

> > +	if (options.keep_cherry_pick && !is_interactive(&options))
> > +		die(_("--keep-cherry-pick does not work with the 'apply' backend"));
> > +
> 
> I see you are failing here. Is this the right decision?
> 
> The apply backend will "keep" cherry-picks because it will not look for them upstream.
> If anything, shouldn't it be that "--no-keep-cherry-pick" is incompatible?

> > +test_expect_success '--keep-cherry-pick' '
> > +	git init repo &&
> > +
> > +	# O(1-10) -- O(1-11) -- O(0-10) master
> > +	#        \
> > +	#         -- O(1-11) -- O(1-12) otherbranch
> > +
> > +	printf "Line %d\n" $(test_seq 1 10) >repo/file.txt &&
> > +	git -C repo add file.txt &&
> > +	git -C repo commit -m "base commit" &&
> > +
> > +	printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> > +	git -C repo commit -a -m "add 11" &&
> > +
> > +	printf "Line %d\n" $(test_seq 0 10) >repo/file.txt &&
> > +	git -C repo commit -a -m "add 0 delete 11" &&
> > +
> > +	git -C repo checkout -b otherbranch HEAD^^ &&
> > +	printf "Line %d\n" $(test_seq 1 11) >repo/file.txt &&
> > +	git -C repo commit -a -m "add 11 in another branch" &&
> > +
> > +	printf "Line %d\n" $(test_seq 1 12) >repo/file.txt &&
> > +	git -C repo commit -a -m "add 12 in another branch" &&
> > +
> > +	# Regular rebase fails, because the 1-11 commit is deduplicated
> > +	test_must_fail git -C repo rebase --merge master 2> err &&
> > +	test_i18ngrep "error: could not apply.*add 12 in another branch" err &&
> > +	git -C repo rebase --abort &&
> 
> OK. So here you are demonstrating that the --no-keep-cherry-pick is the
> new default. Just trying to be sure that this was intended.

>>> Add a flag to "git rebase" to allow suppression of this feature. This
>>> flag only works when using the "merge" backend.
>>
>> So this is the behavior that already exists, and you are providing a way
>> to suppress it. However, you also change the default in this patch, which
>> may surprise users expecting this behavior to continue.
> 
> First of all, thanks for looking at this.
> 
> I'm not changing the default - was there anything in the commit message
> that made you believe it? If yes, I could change it.

> When rebasing against an upstream that has had many commits since the
> original branch was created:
> 
>  O -- O -- ... -- O -- O (upstream)
>   \
>    -- O (my-dev-branch)
> 
> it must read the contents of every novel upstream commit, in addition to
> the tip of the upstream and the merge base, because "git rebase"
> attempts to exclude commits that are duplicates of upstream ones. This
> can be a significant performance hit, especially in a partial clone,
> wherein a read of an object may end up being a fetch.

> This flag changes the behavior of sequencer_make_script(), called from
> do_interactive_rebase() <- run_rebase_interactive() <-
> run_specific_rebase() <- cmd_rebase(). With this flag, limit_list()
> (indirectly called from sequencer_make_script() through
> prepare_revision_walk()) will no longer call cherry_pick_list(), and
> thus PATCHSAME is no longer set. Refraining from setting PATCHSAME both
> means that the intermediate commits in upstream are no longer read (as
> shown by the test) and means that no PATCHSAME-caused skipping of
> commits is done by sequencer_make_script(), either directly or through
> make_script_with_merges().

> diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
> index 0c4f038dd6..f4f8afeb9a 100644
> --- a/Documentation/git-rebase.txt
> +++ b/Documentation/git-rebase.txt
> @@ -318,6 +318,21 @@ See also INCOMPATIBLE OPTIONS below.
>  +
>  See also INCOMPATIBLE OPTIONS below.
>
> +--keep-cherry-pick::
> +--no-keep-cherry-pick::

> +       Control rebase's behavior towards commits in the working
> +       branch that are already present upstream, i.e. cherry-picks.
> ++
> +By default, these commits will be dropped. Because this necessitates
> +reading all upstream commits, this can be expensive in repos with a
> +large number of upstream commits that need to be read.
> ++
> +If `--keep-cherry-pick is given`, all commits (including these) will be
> +re-applied. This allows rebase to forgo reading all upstream commits,
> +potentially improving performance.

> ++
> +See also INCOMPATIBLE OPTIONS below.
> +
>  --rerere-autoupdate::
>  --no-rerere-autoupdate::
>         Allow the rerere mechanism to update the index with the
> @@ -568,6 +583,9 @@ In addition, the following pairs of options are incompatible:
>   * --keep-base and --onto
>   * --keep-base and --root
>
> +Also, the --keep-cherry-pick option requires the use of the merge backend
> +(e.g., through --merge).

> +
>  BEHAVIORAL DIFFERENCES
>  -----------------------
>
> @@ -866,7 +884,8 @@ Only works if the changes (patch IDs based on the diff contents) on
>  'subsystem' did.
>
>  In that case, the fix is easy because 'git rebase' knows to skip
> -changes that are already present in the new upstream.  So if you say
> +changes that are already present in the new upstream (unless
> +`--keep-cherry-pick` is given). So if you say
>  (assuming you're on 'topic')
>  ------------
>      $ git rebase subsystem
> diff --git a/builtin/rebase.c b/builtin/rebase.c

> @@ -1848,6 +1852,9 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
>                               "interactive or merge options"));
>         }
>
> +       if (options.keep_cherry_pick && !is_interactive(&options))

> +               die(_("--keep-cherry-pick does not work with the 'apply' backend"));
> +
>         if (options.signoff) {
>                 if (options.type == REBASE_PRESERVE_MERGES)
>                         die("cannot combine '--signoff' with "

>> +--keep-cherry-pick::
>> +--no-keep-cherry-pick::
> ...
> I'm slightly worried that "keep" is setting up an incorrect
> expectation for users; in most cases, a reapplied cherry-pick will
> result in the merge machinery applying no new changes (they were
> already applied) and then rebase's default of dropping commits which
> become empty will kick in and drop the commit.

> Maybe the name is fine and we just need to be more clear in the text
> on the expected behavior and advantages and disadvantages of this
> option:
>
> If `--keep-cherry-picks` is given, all commits (including these) will be
> re-applied.  Note that cherry picks are likely to result in no changes
> when being reapplied and thus are likely to be dropped anyway (assuming
> the default --empty=drop behavior).  The advantage of this option, is it
> allows rebase to forgo reading all upstream commits, potentially
> improving performance.  The disadvantage of this option is that in some
> cases, the code has drifted such that reapplying a cherry-pick is not
> detectable as a no-op, and instead results in conflicts for the user to
> manually resolve (usually via `git rebase --skip`).

> True.  So instead of letting the machine match commits on the both
> sides up, the end-user who is rebasing will find matches (or near
> matches) and manually handle them.  It would be a good idea to
> describe the pros and cons for the option (which I think has already
> been written fairly clearly in the proposed patch).

> > +If `--keep-cherry-pick is given`, all commits (including these) will be
> > +re-applied. This allows rebase to forgo reading all upstream commits,
> > +potentially improving performance.
> 
> I'm slightly worried that "keep" is setting up an incorrect
> expectation for users; in most cases, a reapplied cherry-pick will
> result in the merge machinery applying no new changes (they were
> already applied) and then rebase's default of dropping commits which
> become empty will kick in and drop the commit.
> 
> Maybe the name is fine and we just need to be more clear in the text
> on the expected behavior and advantages and disadvantages of this
> option:
> 
> If `--keep-cherry-picks` is given, all commits (including these) will be
> re-applied.  Note that cherry picks are likely to result in no changes
> when being reapplied and thus are likely to be dropped anyway (assuming
> the default --empty=drop behavior).  The advantage of this option, is it
> allows rebase to forgo reading all upstream commits, potentially
> improving performance.  The disadvantage of this option is that in some
> cases, the code has drifted such that reapplying a cherry-pick is not
> detectable as a no-op, and instead results in conflicts for the user to
> manually resolve (usually via `git rebase --skip`).
> 
> It may also be helpful to prevent users from making a false inference
> by renaming these options to --[no-]reapply-cherry-pick[s].  Sorry to
> bring this up so late after earlier saying --[no-]keep-cherry-pick[s]
> was fine; didn't occur to me then.  If you want to keep the name, the
> extended paragraph should be good enough.

> > @@ -568,6 +583,9 @@ In addition, the following pairs of options are incompatible:
> >   * --keep-base and --onto
> >   * --keep-base and --root
> >
> > +Also, the --keep-cherry-pick option requires the use of the merge backend
> > +(e.g., through --merge).
> 
> Why not just list --keep-cherry-pick[s] in the list of options that
> require use of the merge backend (i.e. the list containing '--merge')
> instead of adding another sentence here?

>
> > > +If `--keep-cherry-pick is given`, all commits (including these) will be
> > > +re-applied. This allows rebase to forgo reading all upstream commits,
> > > +potentially improving performance.
> >
> > I'm slightly worried that "keep" is setting up an incorrect
> > expectation for users; in most cases, a reapplied cherry-pick will
> > result in the merge machinery applying no new changes (they were
> > already applied) and then rebase's default of dropping commits which
> > become empty will kick in and drop the commit.
> >
> > Maybe the name is fine and we just need to be more clear in the text
> > on the expected behavior and advantages and disadvantages of this
> > option:
> >
> > If `--keep-cherry-picks` is given, all commits (including these) will be
> > re-applied.  Note that cherry picks are likely to result in no changes
> > when being reapplied and thus are likely to be dropped anyway (assuming
> > the default --empty=drop behavior).  The advantage of this option, is it
> > allows rebase to forgo reading all upstream commits, potentially
> > improving performance.  The disadvantage of this option is that in some
> > cases, the code has drifted such that reapplying a cherry-pick is not
> > detectable as a no-op, and instead results in conflicts for the user to
> > manually resolve (usually via `git rebase --skip`).
> >
> > It may also be helpful to prevent users from making a false inference
> > by renaming these options to --[no-]reapply-cherry-pick[s].  Sorry to
> > bring this up so late after earlier saying --[no-]keep-cherry-pick[s]
> > was fine; didn't occur to me then.  If you want to keep the name, the
> > extended paragraph should be good enough.
>
> Sorry for getting back to this so late. After some thought, I'm liking
> --reapply-cherry-picks too. Perhaps documented like this:
>
>   Reapply all clean cherry-picks of any upstream commit instead of
>   dropping them. (If these commits then become empty after rebasing,
>   because they contain a subset of already upstream changes, the
>   behavior towards them is controlled by the `--empty` flag.)

>   By default (or if `--noreapply-cherry-picks` is given), these commits
>   will be automatically dropped. Because this necessitates reading all
>   upstream commits, this can be expensive in repos with a large number
>   of upstream commits that need to be read.
>
>   `--reapply-cherry-picks` allows rebase to forgo reading all upstream
>   commits, potentially improving performance.
>
>   See also INCOMPATIBLE OPTIONS below.

> This also makes me realize that we probably need to change the "--empty"
> documentation too. Maybe:
>
>    --empty={drop,keep,ask}::
>   -       How to handle commits that are not empty to start and are not
>   -       clean cherry-picks of any upstream commit, but which become
>   +       How to handle commits that become
>           empty after rebasing (because they contain a subset of already
>           upstream changes).  With drop (the default), commits that
>           become empty are dropped.  With keep, such commits are kept.
>           With ask (implied by --interactive), the rebase will halt when
>           an empty commit is applied allowing you to choose whether to
>           drop it, edit files more, or just commit the empty changes.
>           Other options, like --exec, will use the default of drop unless
>           -i/--interactive is explicitly specified.
>    +
>   -Note that commits which start empty are kept, and commits which are
>   -clean cherry-picks (as determined by `git log --cherry-mark ...`) are
>   -always dropped.
>   +Commits that start empty are always kept.
>   ++
>   +Commits that are clean cherry-picks of any upstream commit (as determined by
>   +`git log --cherry-mark ...`) are always dropped, unless
>   +`--reapply-cherry-picks`, is set, in which case they are reapplied. If they
>   +become empty after rebasing, `--empty` determines what happens to them.
>    +
>    See also INCOMPATIBLE OPTIONS below.
>
> If this works, I'll send out a new version containing Elijah's patches
> and mine in whatever branch my patch shows up in [1].
>
> [1] https://lore.kernel.org/git/xmqqd08fhvx5.fsf@gitster.c.googlers.com/

> > > @@ -568,6 +583,9 @@ In addition, the following pairs of options are incompatible:
> > >   * --keep-base and --onto
> > >   * --keep-base and --root
> > >
> > > +Also, the --keep-cherry-pick option requires the use of the merge backend
> > > +(e.g., through --merge).
> >
> > Why not just list --keep-cherry-pick[s] in the list of options that
> > require use of the merge backend (i.e. the list containing '--merge')
> > instead of adding another sentence here?
>
> My reading of the list containing "--merge" is that they *trigger* the
> merge backend, not require the merge backend. My new option requires but
> does not trigger it (unless we want to change it to do so, which I'm
> fine with).

> >   Reapply all clean cherry-picks of any upstream commit instead of
> >   dropping them. (If these commits then become empty after rebasing,
> >   because they contain a subset of already upstream changes, the
> >   behavior towards them is controlled by the `--empty` flag.)
> 
> Perhaps add "preemptively" in there, so that it reads "...instead of
> preemptively dropping them..."?

> > If this works, I'll send out a new version containing Elijah's patches
> > and mine in whatever branch my patch shows up in [1].
> >
> > [1] https://lore.kernel.org/git/xmqqd08fhvx5.fsf@gitster.c.googlers.com/
> 
> Yeah, I was making changes to this exact same area in my series to
> reference your flags.[2]
> 
> [2] https://lore.kernel.org/git/e15c599c874956f1a297424c68fe28e04c71807b.1586541094.git.gitgitgadget@gmail.com/
> 
> Would you mind if I took your proposed changes, put them in your
> patch, and then rebased your patch on top of my series and touched up
> the wording in the manpage to have the options reference each other?

> > > Why not just list --keep-cherry-pick[s] in the list of options that
> > > require use of the merge backend (i.e. the list containing '--merge')
> > > instead of adding another sentence here?
> >
> > My reading of the list containing "--merge" is that they *trigger* the
> > merge backend, not require the merge backend. My new option requires but
> > does not trigger it (unless we want to change it to do so, which I'm
> > fine with).
> 
> Interesting; what part of the man page comes across that way?  That
> may just be poor wording.

> However, if an option requires a certain backend, is there a reason
> why we would want to require the user to manually specify that backend
> for their chosen option to work?  We know exactly which backend they
> need, so we could just trigger it.  For every other case in rebase I
> can think of, whenever a certain backend was required for an option we
> always made the option trigger that backend (or throw an error if a
> different backend had already been requested).

>
> > >   Reapply all clean cherry-picks of any upstream commit instead of
> > >   dropping them. (If these commits then become empty after rebasing,
> > >   because they contain a subset of already upstream changes, the
> > >   behavior towards them is controlled by the `--empty` flag.)
> >
> > Perhaps add "preemptively" in there, so that it reads "...instead of
> > preemptively dropping them..."?
>
> Sounds good. Yes I can do this.
>
> > > If this works, I'll send out a new version containing Elijah's patches
> > > and mine in whatever branch my patch shows up in [1].
> > >
> > > [1] https://lore.kernel.org/git/xmqqd08fhvx5.fsf@gitster.c.googlers.com/
> >
> > Yeah, I was making changes to this exact same area in my series to
> > reference your flags.[2]
> >
> > [2] https://lore.kernel.org/git/e15c599c874956f1a297424c68fe28e04c71807b.1586541094.git.gitgitgadget@gmail.com/
> >
> > Would you mind if I took your proposed changes, put them in your
> > patch, and then rebased your patch on top of my series and touched up
> > the wording in the manpage to have the options reference each other?
>
> Go ahead! Thanks.

> > > > Why not just list --keep-cherry-pick[s] in the list of options that
> > > > require use of the merge backend (i.e. the list containing '--merge')
> > > > instead of adding another sentence here?
> > >
> > > My reading of the list containing "--merge" is that they *trigger* the
> > > merge backend, not require the merge backend. My new option requires but
> > > does not trigger it (unless we want to change it to do so, which I'm
> > > fine with).
> >
> > Interesting; what part of the man page comes across that way?  That
> > may just be poor wording.
>
> "--merge" is documented as "Use merging strategies to rebase", which I
> interpret as triggering the merge backend. There are other things in the
> list like "--strategy" and "--interactive", which seem to be things that
> trigger the merge backend too, so I concluded that the list is about
> triggering the merge backend, not requiring it.
>
> > However, if an option requires a certain backend, is there a reason
> > why we would want to require the user to manually specify that backend
> > for their chosen option to work?  We know exactly which backend they
> > need, so we could just trigger it.  For every other case in rebase I
> > can think of, whenever a certain backend was required for an option we
> > always made the option trigger that backend (or throw an error if a
> > different backend had already been requested).
>
> I guess I wanted to leave open the option to have the same feature in
> the "apply" (formerly "am") backend. The use cases I am thinking of
> won't need that in the near future (for partial clone to make use of it
> in the "apply" backend, the "apply" backend would have to be further
> improved to batch fetching of missing blobs), though, so it might be
> best to just require and trigger "merge" (like the other cases you
> mention). I'll do that in the next version.