[PATCH v3 0/3] Help merging when text has been normalized

[PATCH v3 0/3] Help merging when text has been normalized

[Eyvind Bernhardsen]

Here's a slightly expanded series based on my ll-merge normalization
patch.  I've been working in a repository that uses "* text=auto" at
$dayjob, and this series helps a lot when merging older,
pre-normalization branches.

The first commit is a cleaned-up version of the previous patch.  I
borrowed Finn Arne's explanation for why it's useful for my commit
message, ASCII art and all.  The idea is pretty simple: normalization
might differ between branches, so renormalization is required to prevent
(or at least reduce) conflicts.

The second fixes a similar problem, but for delete/modify conflicts.  If
a file is normalized on a branch but deleted in another, merging the
branches will cause a conflict even though the actual content of the
file hasn't changed at all.

If the merge-base version of the file and the modified file differ they
are both normalized, and if either was changed by normalization they are
compared.  If they compare equal, the file is considered unmodified and
is deleted.

The third patch prevents normalization from expanding and then
collapsing CRLFs, saving time and memory when core.autocrlf=true or
core.eol=crlf.

- Eyvind

Eyvind Bernhardsen (3):
  Avoid conflicts when merging branches with mixed normalization
  Try normalizing files to avoid delete/modify conflicts when merging
  Don't expand CRLFs when normalizing text during merge

 cache.h                    |    1 +
 convert.c                  |   27 ++++++++++++++++----
 ll-merge.c                 |   12 +++++++++
 merge-recursive.c          |   42 ++++++++++++++++++++++++++++++-
 t/t6038-merge-text-auto.sh |   58 ++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 133 insertions(+), 7 deletions(-)
 create mode 100755 t/t6038-merge-text-auto.sh

-- 
1.7.1.575.g383de

[PATCH v3 1/3] Avoid conflicts when merging branches with mixed normalization

[Eyvind Bernhardsen]

Currently, merging across changes in line ending normalization is
painful since files containing CRLF will conflict with normalized files,
even if the only difference between the two versions is the line
endings.  Additionally, any "real" merge conflicts that exist are
obscured because every line in the file has a conflict.

Assume you start out with a repo that has a lot of text files with CRLF
checked in (A):

      o---C
     /     \
    A---B---D

B: Add "* text=auto" to .gitattributes and normalize all files to
   LF-only

C: Modify some of the text files

D: Try to merge C

You will get a ridiculous number of LF/CRLF conflicts when trying to
merge C into D, since the repository contents for C are "wrong" wrt the
new .gitattributes file.

Fix ll-merge so that the "base", "theirs" and "ours" stages are passed
through convert_to_worktree() and convert_to_git() before a three-way
merge.  This ensures that all three stages are normalized in the same
way, removing from consideration differences that are only due to
normalization.

Signed-off-by: Eyvind Bernhardsen <eyvind.bernhardsen@gmail.com>
---
 cache.h                    |    1 +
 convert.c                  |   11 +++++++-
 ll-merge.c                 |   12 +++++++++
 t/t6038-merge-text-auto.sh |   58 ++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 81 insertions(+), 1 deletions(-)
 create mode 100755 t/t6038-merge-text-auto.sh

diff --git a/cache.h b/cache.h
index ff4a7c2..5db89f9 100644
--- a/cache.h
+++ b/cache.h
@@ -1043,6 +1043,7 @@ extern void trace_argv_printf(const char **argv, const char *format, ...);
 extern int convert_to_git(const char *path, const char *src, size_t len,
                           struct strbuf *dst, enum safe_crlf checksafe);
 extern int convert_to_working_tree(const char *path, const char *src, size_t len, struct strbuf *dst);
+extern int renormalize_buffer(const char *path, const char *src, size_t len, struct strbuf *dst);
 
 /* add */
 /*
diff --git a/convert.c b/convert.c
index e41a31e..e1561a9 100644
--- a/convert.c
+++ b/convert.c
@@ -693,7 +693,7 @@ static int git_path_check_ident(const char *path, struct git_attr_check *check)
 	return !!ATTR_TRUE(value);
 }
 
-enum action determine_action(enum action text_attr, enum eol eol_attr) {
+static enum action determine_action(enum action text_attr, enum eol eol_attr) {
 	if (text_attr == CRLF_BINARY)
 		return CRLF_BINARY;
 	if (eol_attr == EOL_LF)
@@ -773,3 +773,12 @@ int convert_to_working_tree(const char *path, const char *src, size_t len, struc
 	}
 	return ret | apply_filter(path, src, len, dst, filter);
 }
+
+int renormalize_buffer(const char *path, const char *src, size_t len, struct strbuf *dst) {
+	int ret = convert_to_working_tree(path, src, len, dst);
+	if (ret) {
+		src = dst->buf;
+		len = dst->len;
+	}
+	return ret | convert_to_git(path, src, len, dst, 0);
+}
diff --git a/ll-merge.c b/ll-merge.c
index 3764a1a..bdaa580 100644
--- a/ll-merge.c
+++ b/ll-merge.c
@@ -321,6 +321,15 @@ static int git_path_check_merge(const char *path, struct git_attr_check check[2]
 	return git_checkattr(path, 2, check);
 }
 
+static void normalize_file(mmfile_t *mm, const char *path) {
+	struct strbuf strbuf = STRBUF_INIT;
+	if (renormalize_buffer(path, mm->ptr, mm->size, &strbuf)) {
+		free(mm->ptr);
+		mm->size = strbuf.len;
+		mm->ptr = strbuf_detach(&strbuf, NULL);
+	}
+}
+
 int ll_merge(mmbuffer_t *result_buf,
 	     const char *path,
 	     mmfile_t *ancestor, const char *ancestor_label,
@@ -334,6 +343,9 @@ int ll_merge(mmbuffer_t *result_buf,
 	const struct ll_merge_driver *driver;
 	int virtual_ancestor = flag & 01;
 
+	normalize_file(ancestor, path);
+	normalize_file(ours, path);
+	normalize_file(theirs, path);
 	if (!git_path_check_merge(path, check)) {
 		ll_driver_name = check[0].value;
 		if (check[1].value) {
diff --git a/t/t6038-merge-text-auto.sh b/t/t6038-merge-text-auto.sh
new file mode 100755
index 0000000..44e6003
--- /dev/null
+++ b/t/t6038-merge-text-auto.sh
@@ -0,0 +1,58 @@
+#!/bin/sh
+
+test_description='CRLF merge conflict across text=auto change'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	git config core.autocrlf false &&
+	echo first line | append_cr >file &&
+	git add file &&
+	git commit -m "Initial" &&
+	git tag initial &&
+	git branch side &&
+	echo "* text=auto" >.gitattributes &&
+	touch file &&
+	git add .gitattributes file &&
+	git commit -m "normalize file" &&
+	echo same line | append_cr >>file &&
+	git add file &&
+	git commit -m "add line from a" &&
+	git tag a &&
+	git rm .gitattributes &&
+	rm file &&
+	git checkout file &&
+	git commit -m "remove .gitattributes" &&
+	git tag c &&
+	git checkout side &&
+	echo same line | append_cr >>file &&
+	git commit -m "add line from b" file &&
+	git tag b &&
+	git checkout master
+'
+
+test_expect_success 'Check merging after setting text=auto' '
+	git reset --hard a &&
+	git merge b &&
+	cat file | remove_cr >file.temp &&
+	test_cmp file file.temp
+'
+
+test_expect_success 'Check merging addition of text=auto' '
+	git reset --hard b &&
+	git merge a &&
+	cat file | remove_cr >file.temp &&
+	test_cmp file file.temp
+'
+
+test_expect_failure 'Test delete/normalize conflict' '
+	git checkout side &&
+	git reset --hard initial &&
+	git rm file &&
+	git commit -m "remove file" &&
+	git checkout master &&
+	git reset --hard a^ &&
+	git merge side
+'
+
+test_done
-- 
1.7.1.575.g383de

[PATCH v3 2/3] Try normalizing files to avoid delete/modify conflicts when merging

[Eyvind Bernhardsen]

If a file is modified due to normalization on one branch, and deleted on
another, a merge of the two branches will result in a delete/modify
conflict for that file even if it is otherwise unchanged.

Try to avoid the conflict by normalizing and comparing the "base" file
and the modified file when their sha1s differ.  If they compare equal,
the file is considered unmodified and is deleted.

Signed-off-by: Eyvind Bernhardsen <eyvind.bernhardsen@gmail.com>
---
 merge-recursive.c          |   42 ++++++++++++++++++++++++++++++++++++++++--
 t/t6038-merge-text-auto.sh |    2 +-
 2 files changed, 41 insertions(+), 3 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 206c103..95edc3e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1056,6 +1056,42 @@ static unsigned char *stage_sha(const unsigned char *sha, unsigned mode)
 	return (is_null_sha1(sha) || mode == 0) ? NULL: (unsigned char *)sha;
 }
 
+static int read_sha1_strbuf(const unsigned char *sha, const char *path,
+			    struct strbuf *dst) {
+	void *buf;
+	enum object_type type;
+	unsigned long size;
+	buf = read_sha1_file(sha, &type, &size);
+	if (!buf)
+		return 0;
+	if (type != OBJ_BLOB) {
+		free(buf);
+		return 0;
+	}
+	strbuf_attach(dst, buf, size, size + 1);
+	return 1;
+}
+
+static int normalized_eq(const unsigned char *a_sha,
+			 const unsigned char *b_sha,
+			 const char *path) {
+	struct strbuf a = STRBUF_INIT;
+	struct strbuf b = STRBUF_INIT;
+	int ret = 0;
+	if (a_sha && b_sha &&
+	    read_sha1_strbuf(a_sha, path, &a) &&
+	    read_sha1_strbuf(b_sha, path, &b)) {
+		/* Both files must be normalized, so we can't use || */
+		if ((renormalize_buffer(path, a.buf, a.len, &a) |
+		     renormalize_buffer(path, b.buf, b.len, &b)) &&
+		    (a.len == b.len))
+			ret = memcmp(a.buf, b.buf, a.len) == 0;
+	}
+	strbuf_release(&a);
+	strbuf_release(&b);
+	return ret;
+}
+
 /* Per entry merge function */
 static int process_entry(struct merge_options *o,
 			 const char *path, struct stage_data *entry)
@@ -1075,8 +1111,10 @@ static int process_entry(struct merge_options *o,
 	if (o_sha && (!a_sha || !b_sha)) {
 		/* Case A: Deleted in one */
 		if ((!a_sha && !b_sha) ||
-		    (sha_eq(a_sha, o_sha) && !b_sha) ||
-		    (!a_sha && sha_eq(b_sha, o_sha))) {
+		    (!b_sha && sha_eq(a_sha, o_sha) ||
+		     normalized_eq(a_sha, o_sha, path)) ||
+		    (!a_sha && sha_eq(b_sha, o_sha) ||
+		     normalized_eq(b_sha, o_sha, path))) {
 			/* Deleted in both or deleted in one and
 			 * unchanged in the other */
 			if (a_sha)
diff --git a/t/t6038-merge-text-auto.sh b/t/t6038-merge-text-auto.sh
index 44e6003..5e45256 100755
--- a/t/t6038-merge-text-auto.sh
+++ b/t/t6038-merge-text-auto.sh
@@ -45,7 +45,7 @@ test_expect_success 'Check merging addition of text=auto' '
 	test_cmp file file.temp
 '
 
-test_expect_failure 'Test delete/normalize conflict' '
+test_expect_success 'Test delete/normalize conflict' '
 	git checkout side &&
 	git reset --hard initial &&
 	git rm file &&
-- 
1.7.1.575.g383de

[PATCH v3 3/3] Don't expand CRLFs when normalizing text during merge

[Eyvind Bernhardsen]

There's no need to expand CRLFs when convert_to_working_tree() is called
to normalize text for a merge since the text will be converted back
immediately.  Improves performance of merges with conflicting line
endings when core.eol=crlf or core.autocrlf=true.

Signed-off-by: Eyvind Bernhardsen <eyvind.bernhardsen@gmail.com>
---
 convert.c |   22 +++++++++++++++-------
 1 files changed, 15 insertions(+), 7 deletions(-)

diff --git a/convert.c b/convert.c
index e1561a9..d45d490 100644
--- a/convert.c
+++ b/convert.c
@@ -739,7 +739,9 @@ int convert_to_git(const char *path, const char *src, size_t len,
 	return ret | ident_to_git(path, src, len, dst, ident);
 }
 
-int convert_to_working_tree(const char *path, const char *src, size_t len, struct strbuf *dst)
+static int convert_to_working_tree_internal(const char *path, const char *src,
+					    size_t len, struct strbuf *dst,
+					    int normalizing)
 {
 	struct git_attr_check check[5];
 	enum action action = CRLF_GUESS;
@@ -765,17 +767,23 @@ int convert_to_working_tree(const char *path, const char *src, size_t len, struc
 		src = dst->buf;
 		len = dst->len;
 	}
-	action = determine_action(action, eol_attr);
-	ret |= crlf_to_worktree(path, src, len, dst, action);
-	if (ret) {
-		src = dst->buf;
-		len = dst->len;
+	if (!normalizing) {
+		action = determine_action(action, eol_attr);
+		ret |= crlf_to_worktree(path, src, len, dst, action);
+		if (ret) {
+			src = dst->buf;
+			len = dst->len;
+		}
 	}
 	return ret | apply_filter(path, src, len, dst, filter);
 }
 
+int convert_to_working_tree(const char *path, const char *src, size_t len, struct strbuf *dst) {
+	return convert_to_working_tree_internal(path, src, len, dst, 0);
+}
+
 int renormalize_buffer(const char *path, const char *src, size_t len, struct strbuf *dst) {
-	int ret = convert_to_working_tree(path, src, len, dst);
+	int ret = convert_to_working_tree_internal(path, src, len, dst, 1);
 	if (ret) {
 		src = dst->buf;
 		len = dst->len;
-- 
1.7.1.575.g383de

Re: [PATCH v3 3/3] Don't expand CRLFs when normalizing text during merge

[Johannes Sixt]

Am 6/24/2010 22:44, schrieb Eyvind Bernhardsen:
> There's no need to expand CRLFs when convert_to_working_tree() is called
> to normalize text for a merge since the text will be converted back
> immediately.  Improves performance of merges with conflicting line
> endings when core.eol=crlf or core.autocrlf=true.

Pardon me, first you make a big deal about normalization for merges, only
that you finally omit it? What am I missing?

BTW, most of the new functions you introduced violate the style: they
should have the opening brace on the next line.

-- Hannes

Re: [PATCH v3 3/3] Don't expand CRLFs when normalizing text during merge

[Eyvind Bernhardsen]

On 25. juni 2010, at 07.45, Johannes Sixt wrote:

> Am 6/24/2010 22:44, schrieb Eyvind Bernhardsen:
>> There's no need to expand CRLFs when convert_to_working_tree() is called
>> to normalize text for a merge since the text will be converted back
>> immediately.  Improves performance of merges with conflicting line
>> endings when core.eol=crlf or core.autocrlf=true.
> 
> Pardon me, first you make a big deal about normalization for merges, only
> that you finally omit it? What am I missing?

Sorry, I didn't explain that very well.  I noticed that normalize_buffer() does more work when core.eol=crlf than it does when core.eol=lf: _to_working_tree() converts LF to CRLF, and then _to_git() reverses that conversion.  This patch makes normalization act the same way when core.eol=crlf as it does when core.eol=lf.

That implies a lack of symmetry in the way the crlf_to_git() and crlf_to_worktree() functions are called, but that asymmetry already exists when core.eol=lf since crlf_to_worktree() returns immediately when no output conversion is required.

I considered temporarily setting the "eol" and "auto_crlf" globals in normalize_buffer(), but messing with global variables felt wrong and this gives the same result (almost: it also disables conversion when a file has text=crlf, but that is a further optimization).

> BTW, most of the new functions you introduced violate the style: they
> should have the opening brace on the next line.

Ah, will fix.  Thanks.
-- 
Eyvind Bernhardsen

Re: [PATCH v3 3/3] Don't expand CRLFs when normalizing text during merge

[Finn Arne Gangstad]

On Fri, Jun 25, 2010 at 07:45:28AM +0200, Johannes Sixt wrote:
> Am 6/24/2010 22:44, schrieb Eyvind Bernhardsen:
> > There's no need to expand CRLFs when convert_to_working_tree() is called
> > to normalize text for a merge since the text will be converted back
> > immediately.  Improves performance of merges with conflicting line
> > endings when core.eol=crlf or core.autocrlf=true.
> 
> Pardon me, first you make a big deal about normalization for merges, only
> that you finally omit it? What am I missing?

He calls convert_to_working_tree and then immediately calls
convert_to_git again.  convert_to_git will still convert CRLF to LF
where appropriate, so the end result will be the same. There is no
reason to go through an "expensive" conversion of LF->CRLF in
convert_to_working_tree first.

- Finn Arne

Re: [PATCH v3 3/3] Don't expand CRLFs when normalizing text during merge

[Johannes Sixt]

Am 6/25/2010 9:58, schrieb Eyvind Bernhardsen:
> On 25. juni 2010, at 07.45, Johannes Sixt wrote:
> 
>> Am 6/24/2010 22:44, schrieb Eyvind Bernhardsen:
>>> There's no need to expand CRLFs when convert_to_working_tree() is called
>>> to normalize text for a merge since the text will be converted back
>>> immediately.  Improves performance of merges with conflicting line
>>> endings when core.eol=crlf or core.autocrlf=true.
>>
>> Pardon me, first you make a big deal about normalization for merges, only
>> that you finally omit it? What am I missing?
> 
> Sorry, I didn't explain that very well.  I noticed that normalize_buffer()
> does more work when core.eol=crlf than it does when core.eol=lf:
> _to_working_tree() converts LF to CRLF, and then _to_git() reverses that
> conversion.  This patch makes normalization act the same way when
> core.eol=crlf as it does when core.eol=lf.

Got it: I missed that you are omitting the conversion only on the "way
out" but not on the "way back".

Looking more closely at your patch, I think that you should make this
optimization only if you can prove that the subsequent apply_filter() is a
no-op. Otherwise, you may break a smudge filter that expects CRLFs.

-- Hannes

Re: [PATCH v3 3/3] Don't expand CRLFs when normalizing text during merge

[Eyvind Bernhardsen]

On 25. juni 2010, at 10.17, Johannes Sixt wrote:

> Am 6/25/2010 9:58, schrieb Eyvind Bernhardsen:
>> Sorry, I didn't explain that very well.  I noticed that normalize_buffer()
>> does more work when core.eol=crlf than it does when core.eol=lf:
>> _to_working_tree() converts LF to CRLF, and then _to_git() reverses that
>> conversion.  This patch makes normalization act the same way when
>> core.eol=crlf as it does when core.eol=lf.
> 
> Got it: I missed that you are omitting the conversion only on the "way
> out" but not on the "way back".
> 
> Looking more closely at your patch, I think that you should make this
> optimization only if you can prove that the subsequent apply_filter() is a
> no-op. Otherwise, you may break a smudge filter that expects CRLFs.

Such a smudge filter would break when core.eol=lf, but you're suggesting that someone might be using a picky smudge filter and has set core.eol=crlf to make sure it gets the line endings it expects?

That's a very good catch.  I'll add a test so that the optimization is only done if filter is NULL.
-- 
Eyvind Bernhardsen