Re: A rebase regression in Git 2.18.0

Elijah Newren [off-list ref] writes:

  - Add a flag to turn off directory rename detection, and set the
flag for every call from am.c in order to avoid problems like this.

I'd say this is the only practical solution, before you deprecate
the "pipe format-patch output to am -3" style of "git rebase" (and
optionally replace with something else).

The whole point of "am -3" is to do _better_ than just "patch" with
minimum amount of information available on the pre- and post- image
blobs, without knowing the remainder of the tree that the patch did
not touch.  It is not surprising that the heuristics that look at
the unchanging part of the tree to infer renames that may or may not
exist guesses incorrectly, either with false positive or negative.
In the context of "rebase", we always have all the trees that are
involved.  We should be able to do better than "am -3".

On Tue, Aug 28, 2018 at 9:58 AM Junio C Hamano [off-list ref] wrote:

Elijah Newren [off-list ref] writes:

quoted

  - Add a flag to turn off directory rename detection, and set the
flag for every call from am.c in order to avoid problems like this.

I'd say this is the only practical solution, before you deprecate
the "pipe format-patch output to am -3" style of "git rebase" (and
optionally replace with something else).

The whole point of "am -3" is to do _better_ than just "patch" with
minimum amount of information available on the pre- and post- image
blobs, without knowing the remainder of the tree that the patch did
not touch.  It is not surprising that the heuristics that look at
the unchanging part of the tree to infer renames that may or may not
exist guesses incorrectly, either with false positive or negative.
In the context of "rebase", we always have all the trees that are
involved.  We should be able to do better than "am -3".

Here are patches to do so; they are built on the top of
en/rebase-consistency, since I wanted to re-use some test code and the
testfile introduced in that series, and to keep similar tests
together.

Elijah Newren (3):
  t3401: add another directory rename testcase for rebase and am
  merge-recursive: add ability to turn off directory rename detection
  am: avoid directory rename detection when calling recursive merge
    machinery

 builtin/am.c                    |   1 +
 merge-recursive.c               |  18 ++++--
 merge-recursive.h               |   1 +
 t/t3401-rebase-and-am-rename.sh | 110 +++++++++++++++++++++++++++++++-
 4 files changed, 124 insertions(+), 6 deletions(-)

-- 
2.18.0.12.g97a29da30a

Similar to commit 16346883ab ("t3401: add directory rename testcases for
rebase and am", 2018-06-27), add another testcase for directory rename
detection.  This new testcase differs in that it showcases a situation
where no directory rename was performed, but which some backends
incorrectly detect.

As with the other testcase, run this in conjunction with each of the
types of rebases:
  git-rebase--interactive
  git-rebase--am
  git-rebase--merge
and also use the same testcase for
  git am --3way

Reported-by: Nikolay Kasyanov <redacted>
Signed-off-by: Elijah Newren <redacted>
---
 t/t3401-rebase-and-am-rename.sh | 110 +++++++++++++++++++++++++++++++-
 1 file changed, 109 insertions(+), 1 deletion(-)

diff --git a/t/t3401-rebase-and-am-rename.sh b/t/t3401-rebase-and-am-rename.sh
index 8f832957fc..a87df9e675 100755
--- a/t/t3401-rebase-and-am-rename.sh
+++ b/t/t3401-rebase-and-am-rename.sh

@@ -5,7 +5,7 @@ test_description='git rebase + directory rename tests'
 . ./test-lib.sh
 . "$TEST_DIRECTORY"/lib-rebase.sh
 
-test_expect_success 'setup testcase' '
+test_expect_success 'setup testcase where directory rename should be detected' '
 	test_create_repo dir-rename &&
 	(
 		cd dir-rename &&

@@ -102,4 +102,112 @@ test_expect_failure 'am: directory rename detected' '
 	)
 '
 
+test_expect_success 'setup testcase where directory rename should NOT be detected' '
+	test_create_repo no-dir-rename &&
+	(
+		cd no-dir-rename &&
+
+		mkdir x &&
+		test_seq  1 10 >x/a &&
+		test_seq 11 20 >x/b &&
+		test_seq 21 30 >x/c &&
+		echo original >project_info &&
+		git add x project_info &&
+		git commit -m "Initial" &&
+
+		git branch O &&
+		git branch A &&
+		git branch B &&
+
+		git checkout A &&
+		echo v2 >project_info &&
+		git add project_info &&
+		git commit -m "Modify project_info" &&
+
+		git checkout B &&
+		mkdir y &&
+		git mv x/c y/c &&
+		echo v1 >project_info &&
+		git add project_info &&
+		git commit -m "Rename x/c to y/c, modify project_info"
+	)
+'
+
+test_expect_success 'rebase --interactive: NO directory rename' '
+	test_when_finished "git -C no-dir-rename rebase --abort" &&
+	(
+		cd no-dir-rename &&
+
+		git checkout B^0 &&
+
+		set_fake_editor &&
+		FAKE_LINES="1" test_must_fail git rebase --interactive A &&
+
+		git ls-files -s >out &&
+		test_line_count = 6 out &&
+
+		test_path_is_file x/a &&
+		test_path_is_file x/b &&
+		test_path_is_missing x/c
+	)
+'
+
+test_expect_failure 'rebase (am): NO directory rename' '
+	test_when_finished "git -C no-dir-rename rebase --abort" &&
+	(
+		cd no-dir-rename &&
+
+		git checkout B^0 &&
+
+		set_fake_editor &&
+		FAKE_LINES="1" test_must_fail git rebase A &&
+
+		git ls-files -s >out &&
+		test_line_count = 6 out &&
+
+		test_path_is_file x/a &&
+		test_path_is_file x/b &&
+		test_path_is_missing x/c
+	)
+'
+
+test_expect_success 'rebase --merge: NO directory rename' '
+	test_when_finished "git -C no-dir-rename rebase --abort" &&
+	(
+		cd no-dir-rename &&
+
+		git checkout B^0 &&
+
+		set_fake_editor &&
+		FAKE_LINES="1" test_must_fail git rebase --merge A &&
+
+		git ls-files -s >out &&
+		test_line_count = 6 out &&
+
+		test_path_is_file x/a &&
+		test_path_is_file x/b &&
+		test_path_is_missing x/c
+	)
+'
+
+test_expect_failure 'am: NO directory rename' '
+	test_when_finished "git -C no-dir-rename am --abort" &&
+	(
+		cd no-dir-rename &&
+
+		git checkout A^0 &&
+
+		git format-patch -1 B &&
+
+		test_must_fail git am --3way 0001*.patch &&
+
+		git ls-files -s >out &&
+		test_line_count = 6 out &&
+
+		test_path_is_file x/a &&
+		test_path_is_file x/b &&
+		test_path_is_missing x/c
+	)
+'
+
 test_done

-- 
2.18.0.12.g97a29da30a

Signed-off-by: Elijah Newren <redacted>
---
 merge-recursive.c | 18 +++++++++++++-----
 merge-recursive.h |  1 +
 2 files changed, 14 insertions(+), 5 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index f110e1c5ec..bf3cb03d3a 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c

@@ -2843,12 +2843,19 @@ static int handle_renames(struct merge_options *o,
 	head_pairs = get_diffpairs(o, common, head);
 	merge_pairs = get_diffpairs(o, common, merge);
 
-	dir_re_head = get_directory_renames(head_pairs, head);
-	dir_re_merge = get_directory_renames(merge_pairs, merge);
+	if (o->detect_directory_renames) {
+		dir_re_head = get_directory_renames(head_pairs, head);
+		dir_re_merge = get_directory_renames(merge_pairs, merge);
 
-	handle_directory_level_conflicts(o,
-					 dir_re_head, head,
-					 dir_re_merge, merge);
+		handle_directory_level_conflicts(o,
+						 dir_re_head, head,
+						 dir_re_merge, merge);
+	} else {
+		dir_re_head  = xmalloc(sizeof(*dir_re_head));
+		dir_re_merge = xmalloc(sizeof(*dir_re_merge));
+		dir_rename_init(dir_re_head);
+		dir_rename_init(dir_re_merge);
+	}
 
 	ri->head_renames  = get_renames(o, head_pairs,
 					dir_re_merge, dir_re_head, head,

@@ -3541,6 +3548,7 @@ void init_merge_options(struct merge_options *o)
 	o->renormalize = 0;
 	o->diff_detect_rename = -1;
 	o->merge_detect_rename = -1;
+	o->detect_directory_renames = 1;
 	merge_recursive_config(o);
 	merge_verbosity = getenv("GIT_MERGE_VERBOSITY");
 	if (merge_verbosity)

diff --git a/merge-recursive.h b/merge-recursive.h
index fa7bc6b683..e39ee5d78b 100644
--- a/merge-recursive.h
+++ b/merge-recursive.h

@@ -18,6 +18,7 @@ struct merge_options {
 	unsigned renormalize : 1;
 	long xdl_opts;
 	int verbosity;
+	int detect_directory_renames;
 	int diff_detect_rename;
 	int merge_detect_rename;
 	int diff_rename_limit;

-- 
2.18.0.12.g97a29da30a

Let's say you have the following three trees, where Base is from one commit
behind either master or branch:

   Base  : bar_v1, foo/{file1, file2, file3}
   branch: bar_v2, foo/{file1, file2},       goo/file3
   master: bar_v3, foo/{file1, file2, file3}

Using git-am (or am-based rebase) to apply the changes from branch onto
master results in the following tree:

   Result: bar_merged, goo/{file1, file2, file3}

This is not what users want; they did not rename foo/ -> goo/, they only
renamed one file within that directory.  The reason this happens is am
constructs fake trees (via build_fake_ancestor()) of the following form:

   Base_bfa  : bar_v1, foo/file3
   branch_bfa: bar_v2, goo/file3

Combining these two trees with master's tree:

   master: bar_v3, foo/{file1, file2, file3},

You can see that merge_recursive_generic() would see branch_bfa as renaming
foo/ -> goo/, and master as just adding both foo/file1 and foo/file2.  As
such, it ends up with goo/{file1, file2, file3}

The core problem is that am does not have access to the original trees; it
can only construct trees using the blobs involved in the patch.  As such,
it is not safe to perform directory rename detection within am -3.

Signed-off-by: Elijah Newren <redacted>
---
 builtin/am.c                    | 1 +
 t/t3401-rebase-and-am-rename.sh | 4 ++--
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/builtin/am.c b/builtin/am.c
index 2fc2d1e82c..1494a9be84 100644
--- a/builtin/am.c
+++ b/builtin/am.c

@@ -1596,6 +1596,7 @@ static int fall_back_threeway(const struct am_state *state, const char *index_pa
 	o.branch1 = "HEAD";
 	their_tree_name = xstrfmt("%.*s", linelen(state->msg), state->msg);
 	o.branch2 = their_tree_name;
+	o.detect_directory_renames = 0;
 
 	if (state->quiet)
 		o.verbosity = 0;

diff --git a/t/t3401-rebase-and-am-rename.sh b/t/t3401-rebase-and-am-rename.sh
index a87df9e675..94bdfbd69c 100755
--- a/t/t3401-rebase-and-am-rename.sh
+++ b/t/t3401-rebase-and-am-rename.sh

@@ -152,7 +152,7 @@ test_expect_success 'rebase --interactive: NO directory rename' '
 	)
 '
 
-test_expect_failure 'rebase (am): NO directory rename' '
+test_expect_success 'rebase (am): NO directory rename' '
 	test_when_finished "git -C no-dir-rename rebase --abort" &&
 	(
 		cd no-dir-rename &&

@@ -190,7 +190,7 @@ test_expect_success 'rebase --merge: NO directory rename' '
 	)
 '
 
-test_expect_failure 'am: NO directory rename' '
+test_expect_success 'am: NO directory rename' '
 	test_when_finished "git -C no-dir-rename am --abort" &&
 	(
 		cd no-dir-rename &&

-- 
2.18.0.12.g97a29da30a

Hi Elijah,

On Wed, 29 Aug 2018, Elijah Newren wrote:

Let's say you have the following three trees, where Base is from one commit
behind either master or branch:

   Base  : bar_v1, foo/{file1, file2, file3}
   branch: bar_v2, foo/{file1, file2},       goo/file3
   master: bar_v3, foo/{file1, file2, file3}

Using git-am (or am-based rebase) to apply the changes from branch onto
master results in the following tree:

   Result: bar_merged, goo/{file1, file2, file3}

This is not what users want; they did not rename foo/ -> goo/, they only
renamed one file within that directory.  The reason this happens is am
constructs fake trees (via build_fake_ancestor()) of the following form:

   Base_bfa  : bar_v1, foo/file3
   branch_bfa: bar_v2, goo/file3

Combining these two trees with master's tree:

   master: bar_v3, foo/{file1, file2, file3},

You can see that merge_recursive_generic() would see branch_bfa as renaming
foo/ -> goo/, and master as just adding both foo/file1 and foo/file2.  As
such, it ends up with goo/{file1, file2, file3}

The core problem is that am does not have access to the original trees; it
can only construct trees using the blobs involved in the patch.  As such,
it is not safe to perform directory rename detection within am -3.

I read through all three patches, and they look fine to me!

Ciao,
Dscho

Hi Elijah,

On Wed, 29 Aug 2018, Elijah Newren wrote:

This is not a suggestion to change anything, but a genuine question out of
curiosity: would it make sense to put the `dir_re_head` and `dir_re_merge`
structures into `struct merge_options` to avoid these extra `malloc()`s?
Or would that cause issues with the recursive nature of the recursive
merge?

Ciao,
Dscho

On Wed, Aug 29, 2018 at 5:54 AM Johannes Schindelin
[off-list ref] wrote:

Hi Elijah,

On Wed, 29 Aug 2018, Elijah Newren wrote:

quoted

Signed-off-by: Elijah Newren <redacted>
---
 merge-recursive.c | 18 +++++++++++++-----
 merge-recursive.h |  1 +
 2 files changed, 14 insertions(+), 5 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index f110e1c5ec..bf3cb03d3a 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c

@@ -2843,12 +2843,19 @@ static int handle_renames(struct merge_options *o,
      head_pairs = get_diffpairs(o, common, head);
      merge_pairs = get_diffpairs(o, common, merge);

-     dir_re_head = get_directory_renames(head_pairs, head);
-     dir_re_merge = get_directory_renames(merge_pairs, merge);
+     if (o->detect_directory_renames) {
+             dir_re_head = get_directory_renames(head_pairs, head);
+             dir_re_merge = get_directory_renames(merge_pairs, merge);

-     handle_directory_level_conflicts(o,
-                                      dir_re_head, head,
-                                      dir_re_merge, merge);
+             handle_directory_level_conflicts(o,
+                                              dir_re_head, head,
+                                              dir_re_merge, merge);
+     } else {
+             dir_re_head  = xmalloc(sizeof(*dir_re_head));
+             dir_re_merge = xmalloc(sizeof(*dir_re_merge));

This is not a suggestion to change anything, but a genuine question out of
curiosity: would it make sense to put the `dir_re_head` and `dir_re_merge`
structures into `struct merge_options` to avoid these extra `malloc()`s?
Or would that cause issues with the recursive nature of the recursive
merge?

That would work to avoid the extra `malloc()`s, and be inline with the
current usage of merge_options.  However, I'm not sure I like the
current usage of merge_options. That struct is supposed to be public
API, but it's got a lot of private internal-only use stuff (and
putting dir_re_head and dir_re_merge there would add more).  I'm
tempted to go the other way and eject some of the other internal-only
stuff from merge_options (or wrap it inside an opaque struct
merge_options_internal* internal field, or something like that).

On Tue, Aug 28, 2018 at 9:58 AM Junio C Hamano [off-list ref] wrote:

Elijah Newren [off-list ref] writes:

quoted

  - Add a flag to turn off directory rename detection, and set the
flag for every call from am.c in order to avoid problems like this.

I'd say this is the only practical solution, before you deprecate
the "pipe format-patch output to am -3" style of "git rebase" (and
optionally replace with something else).

I posted a patch a while back to add an --am flag to "git rebase",
make "--am" be implied by options which are still am-specific
(--whitespace, --committer-date-is-author-date, and -C), and change
--merge to be the default.

I'll post it as an RFC again after the various rebase-rewrite series
have settled and merged down...along with my other rebase cleanups
that I was waiting on to avoid conflicts with GSoC stuff.

The whole point of "am -3" is to do _better_ than just "patch" with
minimum amount of information available on the pre- and post- image
blobs, without knowing the remainder of the tree that the patch did
not touch.  It is not surprising that the heuristics that look at
the unchanging part of the tree to infer renames that may or may not
exist guesses incorrectly, either with false positive or negative.
In the context of "rebase", we always have all the trees that are
involved.  We should be able to do better than "am -3".

Hi Elijah,

On Thu, 30 Aug 2018, Elijah Newren wrote:

On Tue, Aug 28, 2018 at 9:58 AM Junio C Hamano [off-list ref] wrote:

quoted

Elijah Newren [off-list ref] writes:

quoted

  - Add a flag to turn off directory rename detection, and set the
flag for every call from am.c in order to avoid problems like this.

I'd say this is the only practical solution, before you deprecate
the "pipe format-patch output to am -3" style of "git rebase" (and
optionally replace with something else).

I posted a patch a while back to add an --am flag to "git rebase",
make "--am" be implied by options which are still am-specific
(--whitespace, --committer-date-is-author-date, and -C), and change
--merge to be the default.

Didn't you also post a patch to fold --merge into the --interactive
backend? What's your current state of thinking about this?

As to switching from --am as the default: I still think that --am has
serious speed advantages over --merge (or for that matter, --interactive).
I have no numbers to back that up, though, and I am currently really busy
with working on the CI, so I won't be able to measure these numbers,
either...

Also please note: I converted the `am` backend to pure C (it is waiting at
https://github.com/gitgitgadget/git/pull/24, to be submitted after the
v2.19.0 RC period). Switching to `--merge` as the default would force me
to convert that backend, too ;-)

I'll post it as an RFC again after the various rebase-rewrite series
have settled and merged down...along with my other rebase cleanups
that I was waiting on to avoid conflicts with GSoC stuff.

Thanks for waiting! Please note that I am interested, yet I will be on
vacation for a couple of weeks in September. Don't let that stop you,
though!

quoted

The whole point of "am -3" is to do _better_ than just "patch" with
minimum amount of information available on the pre- and post- image
blobs, without knowing the remainder of the tree that the patch did
not touch.  It is not surprising that the heuristics that look at
the unchanging part of the tree to infer renames that may or may not
exist guesses incorrectly, either with false positive or negative.
In the context of "rebase", we always have all the trees that are
involved.  We should be able to do better than "am -3".

Right. I think that Elijah's right, and --merge is that "do better"
solution.

Ciao,
Dscho

Hi Dscho,

On Fri, Aug 31, 2018 at 3:12 AM Johannes Schindelin
[off-list ref] wrote:

On Thu, 30 Aug 2018, Elijah Newren wrote:

quoted

On Tue, Aug 28, 2018 at 9:58 AM Junio C Hamano [off-list ref] wrote:

quoted

Elijah Newren [off-list ref] writes:

...

quoted

quoted

I'd say this is the only practical solution, before you deprecate
the "pipe format-patch output to am -3" style of "git rebase" (and
optionally replace with something else).

I posted a patch a while back to add an --am flag to "git rebase",
make "--am" be implied by options which are still am-specific
(--whitespace, --committer-date-is-author-date, and -C), and change
--merge to be the default.

Didn't you also post a patch to fold --merge into the --interactive
backend? What's your current state of thinking about this?

Yes.  I updated it once or twice, but it had conflicts with the GSoC
projects each time, so I decided to just hold off on it a bit longer.
I'm still planning to resubmit this once the GSoC projects merge down.

As to switching from --am as the default: I still think that --am has
serious speed advantages over --merge (or for that matter, --interactive).
I have no numbers to back that up, though, and I am currently really busy
with working on the CI, so I won't be able to measure these numbers,
either...

Yep, we talked about this before and you mentioned that the rewrite in
C should bring some performance improvements, and we agreed that
merge-recursive is probably the next issue performance-wise.  I think
it's at least worth measuring what the approximate performance
differences are with the rewrite of rebase in C, and posting an RFC
with that info.  If the answer comes back that we need to do more
optimization before we switch the default, that's fine.

Also please note: I converted the `am` backend to pure C (it is waiting at
https://github.com/gitgitgadget/git/pull/24, to be submitted after the
v2.19.0 RC period). Switching to `--merge` as the default would force me
to convert that backend, too ;-)

Not if git-rebase--merge is deleted and --merge is implemented on top
of the interactive backend as an implicitly_interactive case.  In
fact, that's probably the simplest way to "convert" that backend to C.
Anyway, since I plan to submit that change first, we should be good.

quoted

I'll post it as an RFC again after the various rebase-rewrite series
have settled and merged down...along with my other rebase cleanups
that I was waiting on to avoid conflicts with GSoC stuff.

Thanks for waiting! Please note that I am interested, yet I will be on
vacation for a couple of weeks in September. Don't let that stop you,
though!

Enjoy your vacation!

quoted

quoted

The whole point of "am -3" is to do _better_ than just "patch" with
minimum amount of information available on the pre- and post- image
blobs, without knowing the remainder of the tree that the patch did
not touch.  It is not surprising that the heuristics that look at
the unchanging part of the tree to infer renames that may or may not
exist guesses incorrectly, either with false positive or negative.
In the context of "rebase", we always have all the trees that are
involved.  We should be able to do better than "am -3".

Right. I think that Elijah's right, and --merge is that "do better"
solution.

Cool, good to see others seem to agree on the direction I'd like to
see things move.