[PATCHv4 00/21] git notes merge

@@ -19,6 +19,7 @@ SYNOPSIS
 'git notes' merge --reset [-v | -q]
 'git notes' remove [<object>]
 'git notes' prune [-n | -v]
+'git notes' get-ref
 
 
 DESCRIPTION

@@ -109,6 +110,10 @@ remove::
 prune::
 	Remove all notes for non-existing/unreachable objects.
 
+get-ref::
+	Print the current notes ref. This provides an easy way to
+	retrieve the current notes ref (e.g. from scripts).
+
 OPTIONS
 -------
 -f::

@@ -31,6 +31,7 @@ static const char * const git_notes_usage[] = {
 	"git notes merge --reset [-v | -q]",
 	"git notes [--ref <notes_ref>] remove [<object>]",
 	"git notes [--ref <notes_ref>] prune [-n | -v]",
+	"git notes [--ref <notes_ref>] get-ref",
 	NULL
 };
 

@@ -82,6 +83,11 @@ static const char * const git_notes_prune_usage[] = {
 	NULL
 };
 
+static const char * const git_notes_get_ref_usage[] = {
+	"git notes get-ref",
+	NULL
+};
+
 static const char note_template[] =
 	"\n"
 	"#\n"

@@ -1002,6 +1008,21 @@ static int prune(int argc, const char **argv, const char *prefix)
 	return 0;
 }
 
+static int get_ref(int argc, const char **argv, const char *prefix)
+{
+	struct option options[] = { OPT_END() };
+	argc = parse_options(argc, argv, prefix, options,
+			     git_notes_get_ref_usage, 0);
+
+	if (argc) {
+		error("too many parameters");
+		usage_with_options(git_notes_get_ref_usage, options);
+	}
+
+	puts(default_notes_ref());
+	return 0;
+}
+
 int cmd_notes(int argc, const char **argv, const char *prefix)
 {
 	int result;

@@ -1040,6 +1061,8 @@ int cmd_notes(int argc, const char **argv, const char *prefix)
 		result = remove_cmd(argc, argv, prefix);
 	else if (!strcmp(argv[0], "prune"))
 		result = prune(argc, argv, prefix);
+	else if (!strcmp(argv[0], "get-ref"))
+		result = get_ref(argc, argv, prefix);
 	else {
 		result = error("Unknown subcommand: %s", argv[0]);
 		usage_with_options(git_notes_usage, options);

@@ -1058,4 +1058,23 @@ test_expect_success 'git notes copy diagnoses too many or too few parameters' '
 	test_must_fail git notes copy one two three
 '
 
+test_expect_success 'git notes get-ref (no overrides)' '
+	git config --unset core.notesRef &&
+	unset GIT_NOTES_REF &&
+	test "$(git notes get-ref)" = "refs/notes/commits"
+'
+
+test_expect_success 'git notes get-ref (core.notesRef)' '
+	git config core.notesRef refs/notes/foo &&
+	test "$(git notes get-ref)" = "refs/notes/foo"
+'
+
+test_expect_success 'git notes get-ref (GIT_NOTES_REF)' '
+	test "$(GIT_NOTES_REF=refs/notes/bar git notes get-ref)" = "refs/notes/bar"
+'
+
+test_expect_success 'git notes get-ref (--ref)' '
+	test "$(GIT_NOTES_REF=refs/notes/bar git notes --ref=baz get-ref)" = "refs/notes/baz"
+'
+
 test_done

@@ -0,0 +1,436 @@
+#!/bin/sh
+#
+# Copyright (c) 2010 Johan Herland
+#
+
+test_description='Test notes merging at various fanout levels'
+
+. ./test-lib.sh
+
+verify_notes () {
+	notes_ref="$1"
+	commit="$2"
+	if test -f "expect_notes_$notes_ref"
+	then
+		git -c core.notesRef="refs/notes/$notes_ref" notes |
+			sort >"output_notes_$notes_ref" &&
+		test_cmp "expect_notes_$notes_ref" "output_notes_$notes_ref" ||
+			return 1
+	fi &&
+	git -c core.notesRef="refs/notes/$notes_ref" log --format="%H %s%n%N" \
+		"$commit" >"output_log_$notes_ref" &&
+	test_cmp "expect_log_$notes_ref" "output_log_$notes_ref"
+}
+
+verify_fanout () {
+	notes_ref="$1"
+	# Expect entire notes tree to have a fanout == 1
+	git rev-parse --quiet --verify "refs/notes/$notes_ref" >/dev/null &&
+	git ls-tree -r --name-only "refs/notes/$notes_ref" |
+	while read path
+	do
+		case "$path" in
+		??/??????????????????????????????????????)
+			: true
+			;;
+		*)
+			echo "Invalid path \"$path\"" &&
+			return 1
+			;;
+		esac
+	done
+}
+
+verify_no_fanout () {
+	notes_ref="$1"
+	# Expect entire notes tree to have a fanout == 0
+	git rev-parse --quiet --verify "refs/notes/$notes_ref" >/dev/null &&
+	git ls-tree -r --name-only "refs/notes/$notes_ref" |
+	while read path
+	do
+		case "$path" in
+		????????????????????????????????????????)
+			: true
+			;;
+		*)
+			echo "Invalid path \"$path\"" &&
+			return 1
+			;;
+		esac
+	done
+}
+
+# Set up a notes merge scenario with different kinds of conflicts
+test_expect_success 'setup a few initial commits with notes (notes ref: x)' '
+	git config core.notesRef refs/notes/x &&
+	for i in 1 2 3 4 5
+	do
+		test_commit "commit$i" >/dev/null &&
+		git notes add -m "notes for commit$i" || return 1
+	done
+'
+
+commit_sha1=$(git rev-parse commit1^{commit})
+commit_sha2=$(git rev-parse commit2^{commit})
+commit_sha3=$(git rev-parse commit3^{commit})
+commit_sha4=$(git rev-parse commit4^{commit})
+commit_sha5=$(git rev-parse commit5^{commit})
+
+cat <<EOF | sort >expect_notes_x
+aed91155c7a72c2188e781fdf40e0f3761b299db $commit_sha5
+99fab268f9d7ee7b011e091a436c78def8eeee69 $commit_sha4
+953c20ae26c7aa0b428c20693fe38bc687f9d1a9 $commit_sha3
+6358796131b8916eaa2dde6902642942a1cb37e1 $commit_sha2
+b02d459c32f0e68f2fe0981033bb34f38776ba47 $commit_sha1
+EOF
+
+cat >expect_log_x <<EOF
+$commit_sha5 commit5
+notes for commit5
+
+$commit_sha4 commit4
+notes for commit4
+
+$commit_sha3 commit3
+notes for commit3
+
+$commit_sha2 commit2
+notes for commit2
+
+$commit_sha1 commit1
+notes for commit1
+
+EOF
+
+test_expect_success 'sanity check (x)' '
+	verify_notes x commit5 &&
+	verify_no_fanout x
+'
+
+num=300
+
+cp expect_log_x expect_log_y
+
+test_expect_success 'Add a few hundred commits w/notes to trigger fanout (x -> y)' '
+	git update-ref refs/notes/y refs/notes/x &&
+	git config core.notesRef refs/notes/y &&
+	i=5 &&
+	while test $i -lt $num
+	do
+		i=$(($i + 1)) &&
+		test_commit "commit$i" >/dev/null &&
+		git notes add -m "notes for commit$i" || return 1
+	done &&
+	test "$(git rev-parse refs/notes/y)" != "$(git rev-parse refs/notes/x)" &&
+	# Expected number of commits and notes
+	test "$(git rev-list HEAD | wc -l)" = "$num" &&
+	test "$(git notes list | wc -l)" = "$num" &&
+	# 5 first notes unchanged
+	verify_notes y commit5
+'
+
+test_expect_success 'notes tree has fanout (y)' 'verify_fanout y'
+
+test_expect_success 'No-op merge (already included) (x => y)' '
+	git update-ref refs/notes/m refs/notes/y &&
+	git config core.notesRef refs/notes/m &&
+	git notes merge x &&
+	test "$(git rev-parse refs/notes/m)" = "$(git rev-parse refs/notes/y)"
+'
+
+test_expect_success 'Fast-forward merge (y => x)' '
+	git update-ref refs/notes/m refs/notes/x &&
+	git notes merge y &&
+	test "$(git rev-parse refs/notes/m)" = "$(git rev-parse refs/notes/y)"
+'
+
+cat <<EOF | sort >expect_notes_z
+9f506ee70e20379d7f78204c77b334f43d77410d $commit_sha3
+23a47d6ea7d589895faf800752054818e1e7627b $commit_sha2
+b02d459c32f0e68f2fe0981033bb34f38776ba47 $commit_sha1
+EOF
+
+cat >expect_log_z <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+
+$commit_sha3 commit3
+notes for commit3
+
+appended notes for commit3
+
+$commit_sha2 commit2
+new notes for commit2
+
+$commit_sha1 commit1
+notes for commit1
+
+EOF
+
+test_expect_success 'change some of the initial 5 notes (x -> z)' '
+	git update-ref refs/notes/z refs/notes/x &&
+	git config core.notesRef refs/notes/z &&
+	git notes add -f -m "new notes for commit2" commit2 &&
+	git notes append -m "appended notes for commit3" commit3 &&
+	git notes remove commit4 &&
+	git notes remove commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree has no fanout (z)' 'verify_no_fanout z'
+
+cp expect_log_z expect_log_m
+
+test_expect_success 'successful merge without conflicts (y => z)' '
+	git update-ref refs/notes/m refs/notes/z &&
+	git config core.notesRef refs/notes/m &&
+	git notes merge y &&
+	verify_notes m commit5 &&
+	# x/y/z unchanged
+	verify_notes x commit5 &&
+	verify_notes y commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+cat >expect_log_w <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+other notes for commit4
+
+$commit_sha3 commit3
+other notes for commit3
+
+$commit_sha2 commit2
+notes for commit2
+
+$commit_sha1 commit1
+other notes for commit1
+
+EOF
+
+test_expect_success 'introduce conflicting changes (y -> w)' '
+	git update-ref refs/notes/w refs/notes/y &&
+	git config core.notesRef refs/notes/w &&
+	git notes add -f -m "other notes for commit1" commit1 &&
+	git notes add -f -m "other notes for commit3" commit3 &&
+	git notes add -f -m "other notes for commit4" commit4 &&
+	git notes remove commit5 &&
+	verify_notes w commit5
+'
+
+cat >expect_log_m <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+other notes for commit4
+
+$commit_sha3 commit3
+other notes for commit3
+
+$commit_sha2 commit2
+new notes for commit2
+
+$commit_sha1 commit1
+other notes for commit1
+
+EOF
+
+test_expect_success 'successful merge using "ours" strategy (z => w)' '
+	git update-ref refs/notes/m refs/notes/w &&
+	git config core.notesRef refs/notes/m &&
+	git notes merge -s ours z &&
+	verify_notes m commit5 &&
+	# w/x/y/z unchanged
+	verify_notes w commit5 &&
+	verify_notes x commit5 &&
+	verify_notes y commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+cat >expect_log_m <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+
+$commit_sha3 commit3
+notes for commit3
+
+appended notes for commit3
+
+$commit_sha2 commit2
+new notes for commit2
+
+$commit_sha1 commit1
+other notes for commit1
+
+EOF
+
+test_expect_success 'successful merge using "theirs" strategy (z => w)' '
+	git update-ref refs/notes/m refs/notes/w &&
+	git notes merge -s theirs z &&
+	verify_notes m commit5 &&
+	# w/x/y/z unchanged
+	verify_notes w commit5 &&
+	verify_notes x commit5 &&
+	verify_notes y commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+cat >expect_log_m <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+other notes for commit4
+
+$commit_sha3 commit3
+other notes for commit3
+
+notes for commit3
+
+appended notes for commit3
+
+$commit_sha2 commit2
+new notes for commit2
+
+$commit_sha1 commit1
+other notes for commit1
+
+EOF
+
+test_expect_success 'successful merge using "union" strategy (z => w)' '
+	git update-ref refs/notes/m refs/notes/w &&
+	git notes merge -s union z &&
+	verify_notes m commit5 &&
+	# w/x/y/z unchanged
+	verify_notes w commit5 &&
+	verify_notes x commit5 &&
+	verify_notes y commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+cat >expect_log_m <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+other notes for commit4
+
+$commit_sha3 commit3
+appended notes for commit3
+notes for commit3
+other notes for commit3
+
+$commit_sha2 commit2
+new notes for commit2
+
+$commit_sha1 commit1
+other notes for commit1
+
+EOF
+
+test_expect_success 'successful merge using "cat_sort_uniq" strategy (z => w)' '
+	git update-ref refs/notes/m refs/notes/w &&
+	git notes merge -s cat_sort_uniq z &&
+	verify_notes m commit5 &&
+	# w/x/y/z unchanged
+	verify_notes w commit5 &&
+	verify_notes x commit5 &&
+	verify_notes y commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+# We're merging z into w. Here are the conflicts we expect:
+#
+# commit | x -> w    | x -> z    | conflict?
+# -------|-----------|-----------|----------
+# 1      | changed   | unchanged | no, use w
+# 2      | unchanged | changed   | no, use z
+# 3      | changed   | changed   | yes (w, then z in conflict markers)
+# 4      | changed   | deleted   | yes (w)
+# 5      | deleted   | deleted   | no, deleted
+
+test_expect_success 'fails to merge using "manual" strategy (z => w)' '
+	git update-ref refs/notes/m refs/notes/w &&
+	test_must_fail git notes merge z
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+cat <<EOF | sort >expect_conflicts
+$commit_sha3
+$commit_sha4
+EOF
+
+cat >expect_conflict_$commit_sha3 <<EOF
+<<<<<<< refs/notes/m
+other notes for commit3
+=======
+notes for commit3
+
+appended notes for commit3
+>>>>>>> refs/notes/z
+EOF
+
+cat >expect_conflict_$commit_sha4 <<EOF
+other notes for commit4
+EOF
+
+test_expect_success 'verify conflict entries (with no fanout)' '
+	ls .git/NOTES_MERGE_WORKTREE >output_conflicts &&
+	test_cmp expect_conflicts output_conflicts &&
+	( for f in $(cat expect_conflicts); do
+		test_cmp "expect_conflict_$f" ".git/NOTES_MERGE_WORKTREE/$f" ||
+		exit 1
+	done ) &&
+	# Verify that current notes tree (pre-merge) has not changed (m == w)
+	test "$(git rev-parse refs/notes/m)" = "$(git rev-parse refs/notes/w)"
+'
+
+cat >expect_log_m <<EOF
+$commit_sha5 commit5
+
+$commit_sha4 commit4
+other notes for commit4
+
+$commit_sha3 commit3
+other notes for commit3
+
+appended notes for commit3
+
+$commit_sha2 commit2
+new notes for commit2
+
+$commit_sha1 commit1
+other notes for commit1
+
+EOF
+
+test_expect_success 'resolve and finalize merge (z => w)' '
+	cat >.git/NOTES_MERGE_WORKTREE/$commit_sha3 <<EOF &&
+other notes for commit3
+
+appended notes for commit3
+EOF
+	git notes merge --commit &&
+	verify_notes m commit5 &&
+	# w/x/y/z unchanged
+	verify_notes w commit5 &&
+	verify_notes x commit5 &&
+	verify_notes y commit5 &&
+	verify_notes z commit5
+'
+
+test_expect_success 'notes tree still has fanout after merge (m)' 'verify_fanout m'
+
+test_done

@@ -940,7 +940,7 @@ void init_notes(struct notes_tree *t, const char *notes_ref,
 		return;
 	if (get_tree_entry(object_sha1, "", sha1, &mode))
 		die("Failed to read notes tree referenced by %s (%s)",
-		    notes_ref, object_sha1);
+		    notes_ref, sha1_to_hex(object_sha1));
 
 	hashclr(root_tree.key_sha1);
 	hashcpy(root_tree.val_sha1, sha1);

@@ -14,6 +14,7 @@ SYNOPSIS
 'git notes' append [-F <file> | -m <msg> | (-c | -C) <object>] [<object>]
 'git notes' edit [<object>]
 'git notes' show [<object>]
+'git notes' merge [-v | -q] [-s <strategy> ] <notes_ref>
 'git notes' remove [<object>]
 'git notes' prune [-n | -v]
 

@@ -83,6 +84,16 @@ edit::
 show::
 	Show the notes for a given object (defaults to HEAD).
 
+merge::
+	Merge the given notes ref into the current notes ref.
+	This will try to merge the changes made by the given
+	notes ref (called "remote") since the merge-base (if
+	any) into the current notes ref (called "local").
++
+If conflicts arise and a strategy for automatically resolving
+conflicting notes (see the -s/--strategy option) is not given,
+the merge fails (TODO).
+
 remove::
 	Remove the notes for a given object (defaults to HEAD).
 	This is equivalent to specifying an empty note message to

@@ -133,9 +144,23 @@ OPTIONS
 	Do not remove anything; just report the object names whose notes
 	would be removed.
 
+-s <strategy>::
+--strategy=<strategy>::
+	When merging notes, resolve notes conflicts using the given
+	strategy. The following strategies are recognized: "manual"
+	(default), "ours", "theirs" and "union".
+	See the "NOTES MERGE STRATEGIES" section below for more
+	information on each notes merge strategy.
+
+-q::
+--quiet::
+	When merging notes, operate quietly.
+
 -v::
 --verbose::
-	Report all object names whose notes are removed.
+	When merging notes, be more verbose.
+	When pruning notes, report all object names whose notes are
+	removed.
 
 
 DISCUSSION

@@ -163,6 +188,23 @@ object, in which case the history of the notes can be read with
 `git log -p -g <refname>`.
 
 
+NOTES MERGE STRATEGIES
+----------------------
+
+The default notes merge strategy is "manual", which is not yet
+implemented (TODO).
+
+"ours" automatically resolves conflicting notes in favor of the local
+version (i.e. the current notes ref).
+
+"theirs" automatically resolves notes conflicts in favor of the remote
+version (i.e. the given notes ref being merged into the current notes
+ref).
+
+"union" automatically resolves notes conflicts by concatenating the
+local and remote versions.
+
+
 EXAMPLES
 --------
 

@@ -155,7 +155,7 @@ OPTIONS
 --strategy=<strategy>::
 	When merging notes, resolve notes conflicts using the given
 	strategy. The following strategies are recognized: "manual"
-	(default), "ours", "theirs" and "union".
+	(default), "ours", "theirs", "union" and "cat_sort_uniq".
 	See the "NOTES MERGE STRATEGIES" section below for more
 	information on each notes merge strategy.
 

@@ -230,6 +230,16 @@ ref).
 "union" automatically resolves notes conflicts by concatenating the
 local and remote versions.
 
+"cat_sort_uniq" is similar to "union", but in addition to concatenating
+the local and remote versions, this strategy also sorts the resulting
+lines, and removes duplicate lines from the result. This is equivalent
+to applying the "cat | sort | uniq" shell pipeline to the local and
+remote versions. This strategy is useful if the notes follow a line-based
+format where one wants to avoid duplicated lines in the merge result.
+Note that if either the local or remote version contain duplicate lines
+prior to the merge, these will also be removed by this notes merge
+strategy.
+
 
 EXAMPLES
 --------

@@ -324,6 +324,8 @@ combine_notes_fn parse_combine_notes_fn(const char *v)
 		return combine_notes_ignore;
 	else if (!strcasecmp(v, "concatenate"))
 		return combine_notes_concatenate;
+	else if (!strcasecmp(v, "cat_sort_uniq"))
+		return combine_notes_cat_sort_uniq;
 	else
 		return NULL;
 }

@@ -846,8 +848,8 @@ static int merge(int argc, const char **argv, const char *prefix)
 		OPT__VERBOSITY(&verbosity),
 		OPT_GROUP("Merge options"),
 		OPT_STRING('s', "strategy", &strategy, "strategy",
-			   "resolve notes conflicts using the given "
-			   "strategy (manual/ours/theirs/union)"),
+			   "resolve notes conflicts using the given strategy "
+			   "(manual/ours/theirs/union/cat_sort_uniq)"),
 		OPT_GROUP("Committing unmerged notes"),
 		{ OPTION_BOOLEAN, 0, "commit", &do_commit, NULL,
 			"finalize notes merge by committing unmerged notes",

@@ -899,6 +901,8 @@ static int merge(int argc, const char **argv, const char *prefix)
 			o.strategy = NOTES_MERGE_RESOLVE_THEIRS;
 		else if (!strcmp(strategy, "union"))
 			o.strategy = NOTES_MERGE_RESOLVE_UNION;
+		else if (!strcmp(strategy, "cat_sort_uniq"))
+			o.strategy = NOTES_MERGE_RESOLVE_CAT_SORT_UNIQ;
 		else {
 			error("Unknown -s/--strategy: %s", strategy);
 			usage_with_options(git_notes_merge_usage, options);

@@ -452,6 +452,12 @@ static int merge_one_change(struct notes_merge_options *o,
 		if (add_note(t, p->obj, p->remote, combine_notes_concatenate))
 			die("confused: combine_notes_concatenate failed");
 		return 0;
+	case NOTES_MERGE_RESOLVE_CAT_SORT_UNIQ:
+		OUTPUT(o, 2, "Concatenating unique lines in local and remote "
+		       "notes for %s", sha1_to_hex(p->obj));
+		if (add_note(t, p->obj, p->remote, combine_notes_cat_sort_uniq))
+			die("confused: combine_notes_cat_sort_uniq failed");
+		return 0;
 	}
 	die("Unknown strategy (%i).", o->strategy);
 }

@@ -17,7 +17,8 @@ struct notes_merge_options {
 		NOTES_MERGE_RESOLVE_MANUAL = 0,
 		NOTES_MERGE_RESOLVE_OURS,
 		NOTES_MERGE_RESOLVE_THEIRS,
-		NOTES_MERGE_RESOLVE_UNION
+		NOTES_MERGE_RESOLVE_UNION,
+		NOTES_MERGE_RESOLVE_CAT_SORT_UNIQ
 	} strategy;
 	unsigned has_worktree:1;
 };

@@ -847,6 +847,82 @@ int combine_notes_ignore(unsigned char *cur_sha1,
 	return 0;
 }
 
+static int string_list_add_note_lines(struct string_list *sort_uniq_list,
+				      const unsigned char *sha1)
+{
+	char *data;
+	unsigned long len;
+	enum object_type t;
+	struct strbuf buf = STRBUF_INIT;
+	struct strbuf **lines = NULL;
+	int i, list_index;
+
+	if (is_null_sha1(sha1))
+		return 0;
+
+	/* read_sha1_file NUL-terminates */
+	data = read_sha1_file(sha1, &t, &len);
+	if (t != OBJ_BLOB || !data || !len) {
+		free(data);
+		return t != OBJ_BLOB || !data;
+	}
+
+	strbuf_attach(&buf, data, len, len + 1);
+	lines = strbuf_split(&buf, '\n');
+
+	for (i = 0; lines[i]; i++) {
+		if (lines[i]->buf[lines[i]->len - 1] == '\n')
+			strbuf_setlen(lines[i], lines[i]->len - 1);
+		if (!lines[i]->len)
+			continue; /* skip empty lines */
+		list_index = string_list_find_insert_index(sort_uniq_list,
+							   lines[i]->buf, 0);
+		if (list_index < 0)
+			continue; /* skip duplicate lines */
+		string_list_insert_at_index(sort_uniq_list, list_index,
+					    lines[i]->buf);
+	}
+
+	strbuf_list_free(lines);
+	strbuf_release(&buf);
+	return 0;
+}
+
+static int string_list_join_lines_helper(struct string_list_item *item,
+					 void *cb_data)
+{
+	struct strbuf *buf = cb_data;
+	strbuf_addstr(buf, item->string);
+	strbuf_addch(buf, '\n');
+	return 0;
+}
+
+int combine_notes_cat_sort_uniq(unsigned char *cur_sha1,
+		const unsigned char *new_sha1)
+{
+	struct string_list sort_uniq_list = { NULL, 0, 0, 1 };
+	struct strbuf buf = STRBUF_INIT;
+	int ret = 1;
+
+	/* read both note blob objects into unique_lines */
+	if (string_list_add_note_lines(&sort_uniq_list, cur_sha1))
+		goto out;
+	if (string_list_add_note_lines(&sort_uniq_list, new_sha1))
+		goto out;
+
+	/* create a new blob object from sort_uniq_list */
+	if (for_each_string_list(&sort_uniq_list,
+				 string_list_join_lines_helper, &buf))
+		goto out;
+
+	ret = write_sha1_file(buf.buf, buf.len, blob_type, cur_sha1);
+
+out:
+	strbuf_release(&buf);
+	string_list_clear(&sort_uniq_list, 0);
+	return ret;
+}
+
 static int string_list_add_one_ref(const char *path, const unsigned char *sha1,
 				   int flag, void *cb)
 {

@@ -27,6 +27,7 @@ typedef int (*combine_notes_fn)(unsigned char *cur_sha1, const unsigned char *ne
 int combine_notes_concatenate(unsigned char *cur_sha1, const unsigned char *new_sha1);
 int combine_notes_overwrite(unsigned char *cur_sha1, const unsigned char *new_sha1);
 int combine_notes_ignore(unsigned char *cur_sha1, const unsigned char *new_sha1);
+int combine_notes_cat_sort_uniq(unsigned char *cur_sha1, const unsigned char *new_sha1);
 
 /*
  * Notes tree object

@@ -499,4 +499,149 @@ test_expect_success 'merge z into y with "union" strategy => Non-conflicting 3-w
 	verify_notes y union
 '
 
+test_expect_success 'reset to pre-merge state (y)' '
+	git update-ref refs/notes/y refs/notes/y^1 &&
+	# Verify pre-merge state
+	verify_notes y y
+'
+
+cat <<EOF | sort >expect_notes_union2
+d682107b8bf7a7aea1e537a8d5cb6a12b60135f1 $commit_sha15
+5de7ea7ad4f47e7ff91989fb82234634730f75df $commit_sha14
+3a631fdb6f41b05b55d8f4baf20728ba8f6fccbc $commit_sha13
+a66055fa82f7a03fe0c02a6aba3287a85abf7c62 $commit_sha12
+7e3c53503a3db8dd996cb62e37c66e070b44b54d $commit_sha11
+b8d03e173f67f6505a76f6e00cf93440200dd9be $commit_sha10
+851e1638784a884c7dd26c5d41f3340f6387413a $commit_sha8
+357b6ca14c7afd59b7f8b8aaaa6b8b723771135b $commit_sha5
+e2bfd06a37dd2031684a59a6e2b033e212239c78 $commit_sha4
+5772f42408c0dd6f097a7ca2d24de0e78d1c46b1 $commit_sha3
+283b48219aee9a4105f6cab337e789065c82c2b9 $commit_sha2
+EOF
+
+cat >expect_log_union2 <<EOF
+$commit_sha15 15th
+z notes on 15th commit
+
+y notes on 15th commit
+
+$commit_sha14 14th
+y notes on 14th commit
+
+$commit_sha13 13th
+y notes on 13th commit
+
+$commit_sha12 12th
+y notes on 12th commit
+
+$commit_sha11 11th
+z notes on 11th commit
+
+$commit_sha10 10th
+x notes on 10th commit
+
+$commit_sha9 9th
+
+$commit_sha8 8th
+z notes on 8th commit
+
+$commit_sha7 7th
+
+$commit_sha6 6th
+
+$commit_sha5 5th
+z notes on 5th commit
+
+y notes on 5th commit
+
+$commit_sha4 4th
+y notes on 4th commit
+
+$commit_sha3 3rd
+y notes on 3rd commit
+
+$commit_sha2 2nd
+z notes on 2nd commit
+
+$commit_sha1 1st
+
+EOF
+
+test_expect_success 'merge y into z with "union" strategy => Non-conflicting 3-way merge' '
+	git config core.notesRef refs/notes/z &&
+	git notes merge --strategy=union y &&
+	verify_notes z union2
+'
+
+test_expect_success 'reset to pre-merge state (z)' '
+	git update-ref refs/notes/z refs/notes/z^1 &&
+	# Verify pre-merge state
+	verify_notes z z
+'
+
+cat <<EOF | sort >expect_notes_cat_sort_uniq
+6be90240b5f54594203e25d9f2f64b7567175aee $commit_sha15
+5de7ea7ad4f47e7ff91989fb82234634730f75df $commit_sha14
+3a631fdb6f41b05b55d8f4baf20728ba8f6fccbc $commit_sha13
+a66055fa82f7a03fe0c02a6aba3287a85abf7c62 $commit_sha12
+7e3c53503a3db8dd996cb62e37c66e070b44b54d $commit_sha11
+b8d03e173f67f6505a76f6e00cf93440200dd9be $commit_sha10
+851e1638784a884c7dd26c5d41f3340f6387413a $commit_sha8
+660311d7f78dc53db12ac373a43fca7465381a7e $commit_sha5
+e2bfd06a37dd2031684a59a6e2b033e212239c78 $commit_sha4
+5772f42408c0dd6f097a7ca2d24de0e78d1c46b1 $commit_sha3
+283b48219aee9a4105f6cab337e789065c82c2b9 $commit_sha2
+EOF
+
+cat >expect_log_cat_sort_uniq <<EOF
+$commit_sha15 15th
+y notes on 15th commit
+z notes on 15th commit
+
+$commit_sha14 14th
+y notes on 14th commit
+
+$commit_sha13 13th
+y notes on 13th commit
+
+$commit_sha12 12th
+y notes on 12th commit
+
+$commit_sha11 11th
+z notes on 11th commit
+
+$commit_sha10 10th
+x notes on 10th commit
+
+$commit_sha9 9th
+
+$commit_sha8 8th
+z notes on 8th commit
+
+$commit_sha7 7th
+
+$commit_sha6 6th
+
+$commit_sha5 5th
+y notes on 5th commit
+z notes on 5th commit
+
+$commit_sha4 4th
+y notes on 4th commit
+
+$commit_sha3 3rd
+y notes on 3rd commit
+
+$commit_sha2 2nd
+z notes on 2nd commit
+
+$commit_sha1 1st
+
+EOF
+
+test_expect_success 'merge y into z with "cat_sort_uniq" strategy => Non-conflicting 3-way merge' '
+	git notes merge --strategy=cat_sort_uniq y &&
+	verify_notes z cat_sort_uniq
+'
+
 test_done

@@ -150,6 +150,79 @@ static struct leaf_node *note_tree_find(struct notes_tree *t,
 }
 
 /*
+ * How to consolidate an int_node:
+ * If there are > 1 non-NULL entries, give up and return non-zero.
+ * Otherwise replace the int_node at the given index in the given parent node
+ * with the only entry (or a NULL entry if no entries) from the given tree,
+ * and return 0.
+ */
+static int note_tree_consolidate(struct int_node *tree,
+	struct int_node *parent, unsigned char index)
+{
+	unsigned int i;
+	void *p = NULL;
+
+	assert(tree && parent);
+	assert(CLR_PTR_TYPE(parent->a[index]) == tree);
+
+	for (i = 0; i < 16; i++) {
+		if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
+			if (p) /* more than one entry */
+				return -2;
+			p = tree->a[i];
+		}
+	}
+
+	/* replace tree with p in parent[index] */
+	parent->a[index] = p;
+	free(tree);
+	return 0;
+}
+
+/*
+ * To remove a leaf_node:
+ * Search to the tree location appropriate for the given leaf_node's key:
+ * - If location does not hold a matching entry, abort and do nothing.
+ * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
+ * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
+ */
+static void note_tree_remove(struct notes_tree *t, struct int_node *tree,
+		unsigned char n, struct leaf_node *entry)
+{
+	struct leaf_node *l;
+	struct int_node *parent_stack[20];
+	unsigned char i, j;
+	void **p = note_tree_search(t, &tree, &n, entry->key_sha1);
+
+	assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
+	if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE)
+		return; /* type mismatch, nothing to remove */
+	l = (struct leaf_node *) CLR_PTR_TYPE(*p);
+	if (hashcmp(l->key_sha1, entry->key_sha1))
+		return; /* key mismatch, nothing to remove */
+
+	/* we have found a matching entry */
+	free(l);
+	*p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL);
+
+	/* consolidate this tree level, and parent levels, if possible */
+	if (!n)
+		return; /* cannot consolidate top level */
+	/* first, build stack of ancestors between root and current node */
+	parent_stack[0] = t->root;
+	for (i = 0; i < n; i++) {
+		j = GET_NIBBLE(i, entry->key_sha1);
+		parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]);
+	}
+	assert(i == n && parent_stack[i] == tree);
+	/* next, unwind stack until note_tree_consolidate() is done */
+	while (i > 0 &&
+	       !note_tree_consolidate(parent_stack[i], parent_stack[i - 1],
+				      GET_NIBBLE(i - 1, entry->key_sha1)))
+		i--;
+}
+
+/*
  * To insert a leaf_node:
  * Search to the tree location appropriate for the given leaf_node's key:
  * - If location is unused (NULL), store the tweaked pointer directly there

@@ -229,79 +302,6 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree,
 	note_tree_insert(t, new_node, n + 1, entry, type, combine_notes);
 }
 
-/*
- * How to consolidate an int_node:
- * If there are > 1 non-NULL entries, give up and return non-zero.
- * Otherwise replace the int_node at the given index in the given parent node
- * with the only entry (or a NULL entry if no entries) from the given tree,
- * and return 0.
- */
-static int note_tree_consolidate(struct int_node *tree,
-	struct int_node *parent, unsigned char index)
-{
-	unsigned int i;
-	void *p = NULL;
-
-	assert(tree && parent);
-	assert(CLR_PTR_TYPE(parent->a[index]) == tree);
-
-	for (i = 0; i < 16; i++) {
-		if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
-			if (p) /* more than one entry */
-				return -2;
-			p = tree->a[i];
-		}
-	}
-
-	/* replace tree with p in parent[index] */
-	parent->a[index] = p;
-	free(tree);
-	return 0;
-}
-
-/*
- * To remove a leaf_node:
- * Search to the tree location appropriate for the given leaf_node's key:
- * - If location does not hold a matching entry, abort and do nothing.
- * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
- * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
- */
-static void note_tree_remove(struct notes_tree *t, struct int_node *tree,
-		unsigned char n, struct leaf_node *entry)
-{
-	struct leaf_node *l;
-	struct int_node *parent_stack[20];
-	unsigned char i, j;
-	void **p = note_tree_search(t, &tree, &n, entry->key_sha1);
-
-	assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
-	if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE)
-		return; /* type mismatch, nothing to remove */
-	l = (struct leaf_node *) CLR_PTR_TYPE(*p);
-	if (hashcmp(l->key_sha1, entry->key_sha1))
-		return; /* key mismatch, nothing to remove */
-
-	/* we have found a matching entry */
-	free(l);
-	*p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL);
-
-	/* consolidate this tree level, and parent levels, if possible */
-	if (!n)
-		return; /* cannot consolidate top level */
-	/* first, build stack of ancestors between root and current node */
-	parent_stack[0] = t->root;
-	for (i = 0; i < n; i++) {
-		j = GET_NIBBLE(i, entry->key_sha1);
-		parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]);
-	}
-	assert(i == n && parent_stack[i] == tree);
-	/* next, unwind stack until note_tree_consolidate() is done */
-	while (i > 0 &&
-	       !note_tree_consolidate(parent_stack[i], parent_stack[i - 1],
-				      GET_NIBBLE(i - 1, entry->key_sha1)))
-		i--;
-}
-
 /* Free the entire notes data contained in the given tree */
 static void note_tree_free(struct int_node *tree)
 {

@@ -104,6 +104,10 @@ const unsigned char *get_note(struct notes_tree *t,
  * Copy a note from one object to another in the given notes_tree.
  *
  * Fails if the to_obj already has a note unless 'force' is true.
+ *
+ * IMPORTANT: The changes made by copy_note() to the given notes_tree structure
+ * are not persistent until a subsequent call to write_notes_tree() returns
+ * zero.
  */
 int copy_note(struct notes_tree *t,
 	      const unsigned char *from_obj, const unsigned char *to_obj,

@@ -149,6 +153,7 @@ int copy_note(struct notes_tree *t,
  * notes tree) from within the callback:
  * - add_note()
  * - remove_note()
+ * - copy_note()
  * - free_notes()
  */
 typedef int each_note_fn(const unsigned char *object_sha1,

@@ -503,6 +503,7 @@ LIB_H += mailmap.h
 LIB_H += merge-recursive.h
 LIB_H += notes.h
 LIB_H += notes-cache.h
+LIB_H += notes-merge.h
 LIB_H += object.h
 LIB_H += pack.h
 LIB_H += pack-refs.h

@@ -593,6 +594,7 @@ LIB_OBJS += merge-recursive.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
+LIB_OBJS += notes-merge.o
 LIB_OBJS += object.o
 LIB_OBJS += pack-check.o
 LIB_OBJS += pack-refs.o

@@ -17,6 +17,7 @@
 #include "run-command.h"
 #include "parse-options.h"
 #include "string-list.h"
+#include "notes-merge.h"
 
 static const char * const git_notes_usage[] = {
 	"git notes [--ref <notes_ref>] [list [<object>]]",

@@ -25,6 +26,7 @@ static const char * const git_notes_usage[] = {
 	"git notes [--ref <notes_ref>] append [-m <msg> | -F <file> | (-c | -C) <object>] [<object>]",
 	"git notes [--ref <notes_ref>] edit [<object>]",
 	"git notes [--ref <notes_ref>] show [<object>]",
+	"git notes [--ref <notes_ref>] merge [-v | -q] <notes_ref>",
 	"git notes [--ref <notes_ref>] remove [<object>]",
 	"git notes [--ref <notes_ref>] prune [-n | -v]",
 	NULL

@@ -61,6 +63,11 @@ static const char * const git_notes_show_usage[] = {
 	NULL
 };
 
+static const char * const git_notes_merge_usage[] = {
+	"git notes merge [<options>] <notes_ref>",
+	NULL
+};
+
 static const char * const git_notes_remove_usage[] = {
 	"git notes remove [<object>]",
 	NULL

@@ -772,6 +779,51 @@ static int show(int argc, const char **argv, const char *prefix)
 	return retval;
 }
 
+static int merge(int argc, const char **argv, const char *prefix)
+{
+	struct strbuf remote_ref = STRBUF_INIT, msg = STRBUF_INIT;
+	unsigned char result_sha1[20];
+	struct notes_merge_options o;
+	int verbosity = 0, result;
+	struct option options[] = {
+		OPT__VERBOSITY(&verbosity),
+		OPT_END()
+	};
+
+	argc = parse_options(argc, argv, prefix, options,
+			     git_notes_merge_usage, 0);
+
+	if (argc != 1) {
+		error("Must specify a notes ref to merge");
+		usage_with_options(git_notes_merge_usage, options);
+	}
+
+	init_notes_merge_options(&o);
+	o.verbosity = verbosity + NOTES_MERGE_VERBOSITY_DEFAULT;
+
+	o.local_ref = default_notes_ref();
+	strbuf_addstr(&remote_ref, argv[0]);
+	expand_notes_ref(&remote_ref);
+	o.remote_ref = remote_ref.buf;
+
+	result = notes_merge(&o, result_sha1);
+
+	strbuf_addf(&msg, "notes: Merged notes from %s into %s",
+		    remote_ref.buf, default_notes_ref());
+	if (result == 0) { /* Merge resulted (trivially) in result_sha1 */
+		/* Update default notes ref with new commit */
+		update_ref(msg.buf, default_notes_ref(), result_sha1, NULL,
+			   0, DIE_ON_ERR);
+	} else {
+		/* TODO: */
+		die("'git notes merge' cannot yet handle non-trivial merges!");
+	}
+
+	strbuf_release(&remote_ref);
+	strbuf_release(&msg);
+	return 0;
+}
+
 static int remove_cmd(int argc, const char **argv, const char *prefix)
 {
 	struct option options[] = {

@@ -865,6 +917,8 @@ int cmd_notes(int argc, const char **argv, const char *prefix)
 		result = append_edit(argc, argv, prefix);
 	else if (!strcmp(argv[0], "show"))
 		result = show(argc, argv, prefix);
+	else if (!strcmp(argv[0], "merge"))
+		result = merge(argc, argv, prefix);
 	else if (!strcmp(argv[0], "remove"))
 		result = remove_cmd(argc, argv, prefix);
 	else if (!strcmp(argv[0], "prune"))