patch-id: make it stable against hunk reordering

index 312c3b1..fa562d3 100644
@@ -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 file diffs 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,33 @@ This can be used to make a mapping from patch ID to commit ID.
 
 OPTIONS
 -------
+
+--stable::
+	Use a "stable" sum of hashes as the patch ID. With this option:
+	 - Reordering file diffs that make up a patch does not affect the ID.
+	   In particular, two patches produced by comparing the same two trees
+	   with two different settings for "-O<orderfile>" result in the same
+	   patch ID signature, thereby allowing the computed result to be used
+	   as a key to index some meta-information about the change between
+	   the two trees;
+	 
+	 - Result is different from the value produced by git 1.9 and older
+	   or produced when an "unstable" hash (see --unstable below) is
+	   configured - even when used on a diff output taken without any use
+	   of "-O<orderfile>", thereby making existing databases storing such
+	   "unstable" or historical patch-ids unusable.
+
+	This is the default if patchid.stable is set to true.
+
+--unstable::
+	Use an "unstable" hash as the patch ID. With this option,
+	the result produced is compatible with the patch-id value produced
+	by git 1.9 and older.  Users with pre-existing databases storing
+	patch-ids produced by git 1.9 and older (who do not deal with reordered
+	patches) may want to use this option.
+
+	This is the default.
+
 <patch>::
 	The diff to create the ID of.
 

index caeeb9d..2d6232f 100644
@@ -596,6 +596,28 @@ library for your script to use.
 		...
 	'
 
+ - test_write_lines <text>
+
+   Split <text> to white-space separated words and write it out on standard
+   output, one word per line.
+   Useful to prepare multi-line files in a compact form.
+
+   Example:
+
+	test_write_lines "a b c d e f g" >foo
+
+   Is a more compact equivalent of:
+	cat >foo <<-EOF
+	a
+	b
+	c
+	d
+	e
+	f
+	g
+	EOF
+
+
  - test_pause
 
 	This command is useful for writing and debugging tests and must be

index 158e10a..f581535 100644
@@ -717,6 +717,11 @@ test_ln_s_add () {
 	fi
 }
 
+# This function writes out its parameters, one per line
+test_write_lines () {
+	printf "%s\n" "$@"
+}
+
 perl () {
 	command "$PERL_PATH" "$@"
 }

index d2c930d..7732370 100755
@@ -5,27 +5,44 @@ test_description='git patch-id'
 . ./test-lib.sh
 
 test_expect_success 'setup' '
-	test_commit initial foo a &&
-	test_commit first foo b &&
-	git checkout -b same HEAD^ &&
-	test_commit same-msg foo b &&
-	git checkout -b notsame HEAD^ &&
-	test_commit notsame-msg foo c
+	as="a a a a a a a a" && # eight a
+	test_write_lines $as >foo &&
+	test_write_lines $as >bar &&
+	git add foo bar &&
+	git commit -a -m initial &&
+	test_write_lines $as b >foo &&
+	test_write_lines $as b >bar &&
+	git commit -a -m first &&
+	git checkout -b same master &&
+	git commit --amend -m same-msg &&
+	git checkout -b notsame master &&
+	echo c >foo &&
+	echo c >bar &&
+	git commit --amend -a -m notsame-msg &&
+	test_write_lines bar foo >bar-then-foo &&
+	test_write_lines foo bar >foo-then-bar
 '
 
 test_expect_success 'patch-id output is well-formed' '
-	git log -p -1 | git patch-id > output &&
+	git log -p -1 | git patch-id >output &&
 	grep "^[a-f0-9]\{40\} $(git rev-parse HEAD)$" output
 '
 
+#calculate patch id. Make sure output is not empty.
 calc_patch_id () {
-	git patch-id |
-		sed "s# .*##" > patch-id_"$1"
+	name="$1"
+	shift
+	git patch-id "$@" |
+	sed "s/ .*//" >patch-id_"$name" &&
+	test_line_count -gt 0 patch-id_"$name"
+}
+
+get_top_diff () {
+	git log -p -1 "$@" -O bar-then-foo --
 }
 
 get_patch_id () {
-	git log -p -1 "$1" | git patch-id |
-		sed "s# .*##" > patch-id_"$1"
+	get_top_diff "$1" | calc_patch_id "$@"
 }
 
 test_expect_success 'patch-id detects equality' '

@@ -56,6 +73,69 @@ test_expect_success 'whitespace is irrelevant in footer' '
 	test_cmp patch-id_master patch-id_same
 '
 
+cmp_patch_id () {
+	if
+		test "$1" = "relevant"
+	then
+		! test_cmp patch-id_"$2" patch-id_"$3"
+	else
+		test_cmp patch-id_"$2" patch-id_"$3"
+	fi
+}
+
+test_patch_id_file_order () {
+	relevant="$1"
+	shift
+	name="order-${1}-$relevant"
+	shift
+	get_top_diff "master" | calc_patch_id "$name" "$@" &&
+	git checkout same &&
+	git format-patch -1 --stdout -O foo-then-bar |
+		calc_patch_id "ordered-$name" "$@" &&
+	cmp_patch_id $relevant "$name" "ordered-$name"
+		
+}
+
+# combined test for options: add more tests here to make them
+# run with all options
+test_patch_id () {
+	test_patch_id_file_order "$@"
+}
+
+# small tests with detailed diagnostic for basic options.
+test_expect_success 'file order is irrelevant with --stable' '
+	test_patch_id_file_order irrelevant --stable --stable
+'
+
+test_expect_success 'file order is relevant with --unstable' '
+	test_patch_id_file_order relevant --unstable --unstable
+'
+
+#Now test various option combinations.
+test_expect_success 'default is unstable' '
+	test_patch_id relevant default
+'
+
+test_expect_success 'patchid.stable = true is stable' '
+	test_config patchid.stable true &&
+	test_patch_id irrelevant patchid.stable=true
+'
+
+test_expect_success 'patchid.stable = false is unstable' '
+	test_config patchid.stable false &&
+	test_patch_id relevant patchid.stable=false
+'
+
+test_expect_success '--unstable overrides patchid.stable = true' '
+	test_config patchid.stable true &&
+	test_patch_id relevant patchid.stable=true--unstable --unstable
+'
+
+test_expect_success '--stable overrides patchid.stable = false' '
+	test_config patchid.stable false &&
+	test_patch_id irrelevant patchid.stable=false--stable --stable
+'
+
 test_expect_success 'patch-id supports git-format-patch MIME output' '
 	get_patch_id master &&
 	git checkout same &&

index fa562d3..1e2ca75 100644
@@ -43,7 +43,7 @@ OPTIONS
 	   of "-O<orderfile>", thereby making existing databases storing such
 	   "unstable" or historical patch-ids unusable.
 
-	This is the default if patchid.stable is set to true.
+	This is the default.
 
 --unstable::
 	Use an "unstable" hash as the patch ID. With this option,

@@ -52,7 +52,7 @@ OPTIONS
 	patch-ids produced by git 1.9 and older (who do not deal with reordered
 	patches) may want to use this option.
 
-	This is the default.
+	This is the default if patchid.stable is set to false.
 
 <patch>::
 	The diff to create the ID of.

index 7732370..a8b0c2c 100755
@@ -112,8 +112,8 @@ test_expect_success 'file order is relevant with --unstable' '
 '
 
 #Now test various option combinations.
-test_expect_success 'default is unstable' '
-	test_patch_id relevant default
+test_expect_success 'default is stable' '
+	test_patch_id irrelevant default
 '
 
 test_expect_success 'patchid.stable = true is stable' '