[PATCH 1/3] patch-id: make it stable against hunk reordering

[PATCH 1/3] patch-id: make it stable against hunk reordering

[Michael S. Tsirkin]

Patch id changes if you reorder hunks in a diff.
As the result is functionally equivalent, this is surprising to many
people.
In particular, reordering hunks is helpful to make patches
more readable (e.g. API header diff before implementation diff).

Change patch-id behaviour making it stable against
hunk reodering:
	- prepend header to each hunk (if not there)
	- calculate SHA1 hash for each hunk separately
	- sum all hashes to get patch id

Add a new flag --unstable to get the historical behaviour.

Add --stable which is a nop, for symmetry.

Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
---
 builtin/patch-id.c | 71 ++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 55 insertions(+), 16 deletions(-)

diff --git a/builtin/patch-id.c b/builtin/patch-id.c
index 3cfe02d..253ad87 100644
--- a/builtin/patch-id.c
+++ b/builtin/patch-id.c
@@ -1,17 +1,14 @@
 #include "builtin.h"
 
-static void flush_current_id(int patchlen, unsigned char *id, git_SHA_CTX *c)
+static void flush_current_id(int patchlen, unsigned char *id, unsigned char *result)
 {
-	unsigned char result[20];
 	char name[50];
 
 	if (!patchlen)
 		return;
 
-	git_SHA1_Final(result, c);
 	memcpy(name, sha1_to_hex(id), 41);
 	printf("%s %s\n", sha1_to_hex(result), name);
-	git_SHA1_Init(c);
 }
 
 static int remove_space(char *line)
@@ -56,10 +53,30 @@ static int scan_hunk_header(const char *p, int *p_before, int *p_after)
 	return 1;
 }
 
-static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct strbuf *line_buf)
+static void flush_one_hunk(unsigned char *result, git_SHA_CTX *ctx)
 {
-	int patchlen = 0, found_next = 0;
+	unsigned char hash[20];
+	unsigned short carry = 0;
+	int i;
+
+	git_SHA1_Final(hash, ctx);
+	git_SHA1_Init(ctx);
+	/* 20-byte sum, with carry */
+	for (i = 0; i < 20; ++i) {
+		carry += result[i] + hash[i];
+		result[i] = carry;
+		carry >>= 8;
+	}
+}
+static int get_one_patchid(unsigned char *next_sha1, unsigned char *result,
+			   struct strbuf *line_buf, int stable)
+{
+	int patchlen = 0, found_next = 0, hunks = 0;
 	int before = -1, after = -1;
+	git_SHA_CTX ctx, header_ctx;
+
+	git_SHA1_Init(&ctx);
+	hashclr(result);
 
 	while (strbuf_getwholeline(line_buf, stdin, '\n') != EOF) {
 		char *line = line_buf->buf;
@@ -99,6 +116,18 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st
 			if (!memcmp(line, "@@ -", 4)) {
 				/* Parse next hunk, but ignore line numbers.  */
 				scan_hunk_header(line, &before, &after);
+				if (stable) {
+					if (hunks) {
+						flush_one_hunk(result, &ctx);
+						memcpy(&ctx, &header_ctx,
+						       sizeof ctx);
+					} else {
+						/* Save ctx for next hunk.  */
+						memcpy(&header_ctx, &ctx,
+						       sizeof ctx);
+					}
+				}
+				hunks++;
 				continue;
 			}
 
@@ -107,7 +136,10 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st
 				break;
 
 			/* Else we're parsing another header.  */
+			if (stable && hunks)
+				flush_one_hunk(result, &ctx);
 			before = after = -1;
+			hunks = 0;
 		}
 
 		/* If we get here, we're inside a hunk.  */
@@ -119,39 +151,46 @@ static int get_one_patchid(unsigned char *next_sha1, git_SHA_CTX *ctx, struct st
 		/* Compute the sha without whitespace */
 		len = remove_space(line);
 		patchlen += len;
-		git_SHA1_Update(ctx, line, len);
+		git_SHA1_Update(&ctx, line, len);
 	}
 
 	if (!found_next)
 		hashclr(next_sha1);
 
+	flush_one_hunk(result, &ctx);
+
 	return patchlen;
 }
 
-static void generate_id_list(void)
+static void generate_id_list(int stable)
 {
-	unsigned char sha1[20], n[20];
-	git_SHA_CTX ctx;
+	unsigned char sha1[20], n[20], result[20];
 	int patchlen;
 	struct strbuf line_buf = STRBUF_INIT;
 
-	git_SHA1_Init(&ctx);
 	hashclr(sha1);
 	while (!feof(stdin)) {
-		patchlen = get_one_patchid(n, &ctx, &line_buf);
-		flush_current_id(patchlen, sha1, &ctx);
+		patchlen = get_one_patchid(n, result, &line_buf, stable);
+		flush_current_id(patchlen, sha1, result);
 		hashcpy(sha1, n);
 	}
 	strbuf_release(&line_buf);
 }
 
-static const char patch_id_usage[] = "git patch-id < patch";
+static const char patch_id_usage[] = "git patch-id [--stable | --unstable] < patch";
 
 int cmd_patch_id(int argc, const char **argv, const char *prefix)
 {
-	if (argc != 1)
+	int stable;
+	if (argc == 2 && !strcmp(argv[1], "--stable"))
+		stable = 1;
+	else if (argc == 2 && !strcmp(argv[1], "--unstable"))
+		stable = 0;
+	else if (argc == 1)
+		stable = 1;
+	else
 		usage(patch_id_usage);
 
-	generate_id_list();
+	generate_id_list(stable);
 	return 0;
 }
-- 
MST

[PATCH 2/3] patch-id: document new behaviour

[Michael S. Tsirkin]

Clarify that patch ID is now a sum of hashes, not a hash.
Document --stable and --unstable flags.

Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
---
 Documentation/git-patch-id.txt | 21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-patch-id.txt b/Documentation/git-patch-id.txt
index 312c3b1..1bc6d52 100644
--- a/Documentation/git-patch-id.txt
+++ b/Documentation/git-patch-id.txt
@@ -8,14 +8,14 @@ git-patch-id - Compute unique ID for a patch
 SYNOPSIS
 --------
 [verse]
-'git patch-id' < <patch>
+'git patch-id' [--stable | --unstable] < <patch>
 
 DESCRIPTION
 -----------
-A "patch ID" is nothing but a SHA-1 of the diff associated with a patch, with
-whitespace and line numbers ignored.  As such, it's "reasonably stable", but at
-the same time also reasonably unique, i.e., two patches that have the same "patch
-ID" are almost guaranteed to be the same thing.
+A "patch ID" is nothing but a sum of SHA-1 of the diff hunks associated with a
+patch, with whitespace and line numbers ignored.  As such, it's "reasonably
+stable", but at the same time also reasonably unique, i.e., two patches that
+have the same "patch ID" are almost guaranteed to be the same thing.
 
 IOW, you can use this thing to look for likely duplicate commits.
 
@@ -27,6 +27,17 @@ This can be used to make a mapping from patch ID to commit ID.
 
 OPTIONS
 -------
+
+--stable::
+	Use a symmetrical sum of hashes, such that order of
+	hunks in the diff does not affect the ID.
+	This is the default.
+
+--unstable::
+	Use a non-symmetrical sum of hashes, such that order of
+	hunks in the diff affects the ID.
+	This was the default value for git 1.9 and older.
+
 <patch>::
 	The diff to create the ID of.
 
-- 
MST

[PATCH 3/3] patch-id-test: test new --stable and --unstable flags

[Michael S. Tsirkin]

Verify that patch ID is now stable against hunk reordering.

Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
---
 t/t4204-patch-id.sh | 68 +++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 63 insertions(+), 5 deletions(-)

diff --git a/t/t4204-patch-id.sh b/t/t4204-patch-id.sh
index d2c930d..75f77ef 100755
--- a/t/t4204-patch-id.sh
+++ b/t/t4204-patch-id.sh
@@ -5,12 +5,27 @@ test_description='git patch-id'
 . ./test-lib.sh
 
 test_expect_success 'setup' '
-	test_commit initial foo a &&
-	test_commit first foo b &&
+	test_commit initial-foo foo a &&
+	test_commit initial-bar bar a &&
+	echo b > foo &&
+	echo b > bar &&
+	git commit -a -m first &&
 	git checkout -b same HEAD^ &&
-	test_commit same-msg foo b &&
+	echo b > foo &&
+	echo b > bar &&
+	git commit -a -m same-msg &&
 	git checkout -b notsame HEAD^ &&
-	test_commit notsame-msg foo c
+	echo c > foo &&
+	echo c > bar &&
+	git commit -a -m notsame-msg &&
+	cat > bar-then-foo <<EOF
+bar
+foo
+EOF
+	cat > foo-then-bar <<EOF
+foo
+bar
+EOF
 '
 
 test_expect_success 'patch-id output is well-formed' '
@@ -23,11 +38,33 @@ calc_patch_id () {
 		sed "s# .*##" > patch-id_"$1"
 }
 
+calc_patch_id_unstable () {
+	git patch-id --unstable |
+		sed "s# .*##" > patch-id_"$1"
+}
+
+calc_patch_id_stable () {
+	git patch-id --stable |
+		sed "s# .*##" > patch-id_"$1"
+}
+
+
 get_patch_id () {
-	git log -p -1 "$1" | git patch-id |
+	git log -p -1 "$1" -O bar-then-foo -- | git patch-id |
+		sed "s# .*##" > patch-id_"$1"
+}
+
+get_patch_id_stable () {
+	git log -p -1 "$1" -O bar-then-foo | git patch-id --stable |
+		sed "s# .*##" > patch-id_"$1"
+}
+
+get_patch_id_unstable () {
+	git log -p -1 "$1" -O bar-then-foo | git patch-id --unstable |
 		sed "s# .*##" > patch-id_"$1"
 }
 
+
 test_expect_success 'patch-id detects equality' '
 	get_patch_id master &&
 	get_patch_id same &&
@@ -56,6 +93,27 @@ test_expect_success 'whitespace is irrelevant in footer' '
 	test_cmp patch-id_master patch-id_same
 '
 
+test_expect_success 'file order is irrelevant by default' '
+	get_patch_id master &&
+	git checkout same &&
+	git format-patch -1 --stdout -O foo-then-bar | calc_patch_id same &&
+	test_cmp patch-id_master patch-id_same
+'
+
+test_expect_success 'file order is irrelevant with --stable' '
+	get_patch_id_stable master &&
+	git checkout same &&
+	git format-patch -1 --stdout -O foo-then-bar | calc_patch_id_stable same &&
+	test_cmp patch-id_master patch-id_same
+'
+
+test_expect_success 'file order is relevant with --unstable' '
+	get_patch_id_unstable master &&
+	git checkout same &&
+	git format-patch -1 --stdout -O foo-then-bar | calc_patch_id_unstable notsame &&
+	! test_cmp patch-id_master patch-id_notsame
+'
+
 test_expect_success 'patch-id supports git-format-patch MIME output' '
 	get_patch_id master &&
 	git checkout same &&
-- 
MST

Re: [PATCH 3/3] patch-id-test: test new --stable and --unstable flags

[Eric Sunshine]

On Thu, Mar 27, 2014 at 5:25 AM, Michael S. Tsirkin <mst@redhat.com> wrote:
> Verify that patch ID is now stable against hunk reordering.
>
> Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
> ---
>  t/t4204-patch-id.sh | 68 +++++++++++++++++++++++++++++++++++++++++++++++++----
>  1 file changed, 63 insertions(+), 5 deletions(-)
>
> diff --git a/t/t4204-patch-id.sh b/t/t4204-patch-id.sh
> index d2c930d..75f77ef 100755
> --- a/t/t4204-patch-id.sh
> +++ b/t/t4204-patch-id.sh
> @@ -5,12 +5,27 @@ test_description='git patch-id'
>  . ./test-lib.sh
>
>  test_expect_success 'setup' '
> -       test_commit initial foo a &&
> -       test_commit first foo b &&
> +       test_commit initial-foo foo a &&
> +       test_commit initial-bar bar a &&
> +       echo b > foo &&
> +       echo b > bar &&
> +       git commit -a -m first &&
>         git checkout -b same HEAD^ &&
> -       test_commit same-msg foo b &&
> +       echo b > foo &&
> +       echo b > bar &&
> +       git commit -a -m same-msg &&
>         git checkout -b notsame HEAD^ &&
> -       test_commit notsame-msg foo c
> +       echo c > foo &&
> +       echo c > bar &&
> +       git commit -a -m notsame-msg &&
> +       cat > bar-then-foo <<EOF

Broken &&-chain.

If you use -EOF, you can indent the content rather than having to hang
it on the left margin. Better, use -\EOF to indicate that you're not
interested in interpolation within the block.

> +bar
> +foo
> +EOF
> +       cat > foo-then-bar <<EOF
> +foo
> +bar
> +EOF
>  '
>
>  test_expect_success 'patch-id output is well-formed' '
> @@ -23,11 +38,33 @@ calc_patch_id () {
>                 sed "s# .*##" > patch-id_"$1"
>  }
>
> +calc_patch_id_unstable () {
> +       git patch-id --unstable |
> +               sed "s# .*##" > patch-id_"$1"
> +}
> +
> +calc_patch_id_stable () {
> +       git patch-id --stable |
> +               sed "s# .*##" > patch-id_"$1"
> +}
> +
> +
>  get_patch_id () {
> -       git log -p -1 "$1" | git patch-id |
> +       git log -p -1 "$1" -O bar-then-foo -- | git patch-id |
> +               sed "s# .*##" > patch-id_"$1"
> +}
> +
> +get_patch_id_stable () {
> +       git log -p -1 "$1" -O bar-then-foo | git patch-id --stable |
> +               sed "s# .*##" > patch-id_"$1"
> +}
> +
> +get_patch_id_unstable () {
> +       git log -p -1 "$1" -O bar-then-foo | git patch-id --unstable |
>                 sed "s# .*##" > patch-id_"$1"
>  }
>
> +
>  test_expect_success 'patch-id detects equality' '
>         get_patch_id master &&
>         get_patch_id same &&
> @@ -56,6 +93,27 @@ test_expect_success 'whitespace is irrelevant in footer' '
>         test_cmp patch-id_master patch-id_same
>  '
>
> +test_expect_success 'file order is irrelevant by default' '
> +       get_patch_id master &&
> +       git checkout same &&
> +       git format-patch -1 --stdout -O foo-then-bar | calc_patch_id same &&
> +       test_cmp patch-id_master patch-id_same
> +'
> +
> +test_expect_success 'file order is irrelevant with --stable' '
> +       get_patch_id_stable master &&
> +       git checkout same &&
> +       git format-patch -1 --stdout -O foo-then-bar | calc_patch_id_stable same &&
> +       test_cmp patch-id_master patch-id_same
> +'
> +
> +test_expect_success 'file order is relevant with --unstable' '
> +       get_patch_id_unstable master &&
> +       git checkout same &&
> +       git format-patch -1 --stdout -O foo-then-bar | calc_patch_id_unstable notsame &&
> +       ! test_cmp patch-id_master patch-id_notsame
> +'
> +
>  test_expect_success 'patch-id supports git-format-patch MIME output' '
>         get_patch_id master &&
>         git checkout same &&
> --
> MST
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 1/3] patch-id: make it stable against hunk reordering

[Junio C Hamano]

"Michael S. Tsirkin" <mst@redhat.com> writes:

> Patch id changes if you reorder hunks in a diff.

If you reorder hunks, the patch should no longer apply [*1*], so a
feature to make patch-id stable across such move would have no
practical use ;-), but I am guessing you meant something else.

Perhaps this is about using "-O <orderfile>" option, even though you
happened to have implemented the id mixing at per-hunk level?


[Footnote]

*1* It has been a long time since I looked at the code, and I do not
know offhand if "git apply" has such a bug not to diagnose a hunk
for a file for an earlier part that comes later in its input stream
after seeing another hunk for the same file as a bug. If it does
not, perhaps we should.

Re: [PATCH 1/3] patch-id: make it stable against hunk reordering

[Michael S. Tsirkin]

On Thu, Mar 27, 2014 at 09:58:41AM -0700, Junio C Hamano wrote:
> "Michael S. Tsirkin" <mst@redhat.com> writes:
> 
> > Patch id changes if you reorder hunks in a diff.
> 
> If you reorder hunks, the patch should no longer apply [*1*], so a
> feature to make patch-id stable across such move would have no
> practical use ;-), but I am guessing you meant something else.
> 
> Perhaps this is about using "-O <orderfile>" option, even though you
> happened to have implemented the id mixing at per-hunk level?

Yes.

> 
> [Footnote]
> 
> *1* It has been a long time since I looked at the code, and I do not
> know offhand if "git apply" has such a bug not to diagnose a hunk
> for a file for an earlier part that comes later in its input stream
> after seeing another hunk for the same file as a bug. If it does
> not, perhaps we should.

Hmm you are right.
For some reason I thought that it does work.
I'll drop this part then, less code this way.

Thanks!

Any more comments before I spin v2?

-- 
MST

Re: [PATCH 1/3] patch-id: make it stable against hunk reordering

[Michael S. Tsirkin]

On Thu, Mar 27, 2014 at 09:58:41AM -0700, Junio C Hamano wrote:
> "Michael S. Tsirkin" <mst@redhat.com> writes:
> 
> > Patch id changes if you reorder hunks in a diff.
> 
> If you reorder hunks, the patch should no longer apply [*1*], so a
> feature to make patch-id stable across such move would have no
> practical use ;-), but I am guessing you meant something else.
> 
> Perhaps this is about using "-O <orderfile>" option, even though you
> happened to have implemented the id mixing at per-hunk level?
> 
> 
> [Footnote]
> 
> *1* It has been a long time since I looked at the code, and I do not
> know offhand if "git apply" has such a bug not to diagnose a hunk
> for a file for an earlier part that comes later in its input stream
> after seeing another hunk for the same file as a bug. If it does
> not, perhaps we should.

I started to remove that code, but then I recalled why I did it like
this.  There is a good reason.  Yes, you can't simply reorder hunks just
like this.  But you can get the same effect by prefixing the header:



--- x.txt	2014-03-27 19:31:18.166115449 +0200
+++ y.txt	2014-03-27 19:31:46.731116998 +0200
@@ -30,8 +31,6 @@ a
 a
 a
 a
-a
-b
 b
 b
 b
@@ -60,6 +59,7 @@ b
 b
 b
 b
+Y
 b
 b
 b
--- x.txt	2014-03-27 19:31:18.166115449 +0200
+++ y.txt	2014-03-27 19:31:46.731116998 +0200
@@ -11,6 +11,7 @@ a
 a
 a
 a
+X
 a
 a
 a


Is equivalent to 

--- x.txt	2014-03-27 19:31:18.166115449 +0200
+++ y.txt	2014-03-27 19:31:46.731116998 +0200
@@ -30,8 +31,6 @@ a
 a
 a
 a
-a
-b
 b
 b
 b
@@ -60,6 +59,7 @@ b
 b
 b
 b
+Y
 b
 b
 b
--- x.txt	2014-03-27 19:31:18.166115449 +0200
+++ y.txt	2014-03-27 19:31:46.731116998 +0200
@@ -11,6 +11,7 @@ a
 a
 a
 a
+X
 a
 a
 a


And this works fine with regular tools like patch
so I think it should work for git too, anything else
would be surprising.


-- 
MST

Re: [PATCH 1/3] patch-id: make it stable against hunk reordering

[Junio C Hamano]

"Michael S. Tsirkin" <mst@redhat.com> writes:

> I started to remove that code, but then I recalled why I did it like
> this.  There is a good reason.  Yes, you can't simply reorder hunks just
> like this.  But you can get the same effect by prefixing the header:

Yes, that is one of the things I personally have on the chopping
block.  Having to deal with more than occurrences of the same
pathname in the input made things in builtin/apply.c unnecessarily
complex and I do not see a real gain for being able to concatenate
two patches and feed it into a single "git apply" invocation.

Re: [PATCH 1/3] patch-id: make it stable against hunk reordering

[Michael S. Tsirkin]

On Thu, Mar 27, 2014 at 11:03:46AM -0700, Junio C Hamano wrote:
> "Michael S. Tsirkin" <mst@redhat.com> writes:
> 
> > I started to remove that code, but then I recalled why I did it like
> > this.  There is a good reason.  Yes, you can't simply reorder hunks just
> > like this.  But you can get the same effect by prefixing the header:
> 
> Yes, that is one of the things I personally have on the chopping
> block.  Having to deal with more than occurrences of the same
> pathname in the input made things in builtin/apply.c unnecessarily
> complex and I do not see a real gain for being able to concatenate
> two patches and feed it into a single "git apply" invocation.

Well - I expect that this will surprise some people: gnu
patch accepts this, and it's a natural assumption
that it works. There could be tools producing such diffs, too.

Anyway - we can drop this from patch-id and git apply at
the same time?

-- 
MST

Re: [PATCH 1/3] patch-id: make it stable against hunk reordering

[Michael S. Tsirkin]

On Thu, Mar 27, 2014 at 08:39:17PM +0200, Michael S. Tsirkin wrote:
> On Thu, Mar 27, 2014 at 11:03:46AM -0700, Junio C Hamano wrote:
> > "Michael S. Tsirkin" <mst@redhat.com> writes:
> > 
> > > I started to remove that code, but then I recalled why I did it like
> > > this.  There is a good reason.  Yes, you can't simply reorder hunks just
> > > like this.  But you can get the same effect by prefixing the header:
> > 
> > Yes, that is one of the things I personally have on the chopping
> > block.  Having to deal with more than occurrences of the same
> > pathname in the input made things in builtin/apply.c unnecessarily
> > complex and I do not see a real gain for being able to concatenate
> > two patches and feed it into a single "git apply" invocation.
> 
> Well - I expect that this will surprise some people: gnu
> patch accepts this, and it's a natural assumption
> that it works. There could be tools producing such diffs, too.

This behaviour also seems to be explicitly required by POSIX:

http://pubs.opengroup.org/onlinepubs/7908799/xcu/patch.html
If the patch file contains more than one patch, patch will attempt to
apply each of them as if they came from separate patch files. (In this
case the name of the patch file must be determinable for each diff
listing.) 

It's better to stick to standards even if it does require
a bit more code, isn't it?

> Anyway - we can drop this from patch-id and git apply at
> the same time?
> 
> -- 
> MST