Refactor revision merging

 * Refactor couch_key_tree:merge/3 and helper functions

 * Rewrite couch_key_tree tests for new merge/3 functionality

 * Remove merging logic from couch_db_udpater:merge_rev_trees/6

 * Introduce couch_doc:merge/3 to handling revision merging

This patch does not change any outwardly visible behavior of CouchDB.

The old revision merging code was split across a couple functions with
important merging logic mixed into couch_db_udpater:merge_rev_trees/6.
This is important because couch_db_updater:merge_rev_trees/6 is also the
same code responsible for handling update_seq updates.

This patch factors out the revision merging and conflict detection into
couch_doc:merge/3 with the left over update_seq logic remaining in
couch_db_udpater:merge_rev_trees/6.

This approach is being taken so that we can reuse the revision merging
for other parts of CouchDB, notably the _local docs btree.

4 files changed, 264 insertions, 228 deletions

diff --git a/src/couchdb/couch_db_updater.erl b/src/couchdb/couch_db_updater.erl
index 54531db39..0bfe951a2 100644
--- a/src/couchdb/couch_db_updater.erl
+++ b/src/couchdb/couch_db_updater.erl
@@ -572,82 +572,37 @@ send_result(Client, Ref, NewResult) ->
     % used to send a result to the client
     catch(Client ! {result, self(), {Ref, NewResult}}).
 
-merge_rev_trees(_Limit, _Merge, [], [], AccNewInfos, AccRemoveSeqs, AccSeq) ->
+merge_rev_trees([], [], AccNewInfos, AccRemoveSeqs, AccSeq, _Opts) ->
     {ok, lists:reverse(AccNewInfos), AccRemoveSeqs, AccSeq};
-merge_rev_trees(Limit, MergeConflicts, [NewDocs|RestDocsList],
-        [OldDocInfo|RestOldInfo], AccNewInfos, AccRemoveSeqs, AccSeq) ->
-    #full_doc_info{id=Id,rev_tree=OldTree,deleted=OldDeleted0,update_seq=OldSeq}
-            = OldDocInfo,
-    {NewRevTree, _} = lists:foldl(
-        fun({Client, {#doc{revs={Pos,[_Rev|PrevRevs]}}=NewDoc, Ref}}, {AccTree, OldDeleted}) ->
-            if not MergeConflicts ->
-                case couch_key_tree:merge(AccTree, couch_doc:to_path(NewDoc),
-                    Limit) of
-                {_NewTree, conflicts} when (not OldDeleted) ->
-                    send_result(Client, Ref, conflict),
-                    {AccTree, OldDeleted};
-                {NewTree, conflicts} when PrevRevs /= [] ->
-                    % Check to be sure if prev revision was specified, it's
-                    % a leaf node in the tree
-                    Leafs = couch_key_tree:get_all_leafs(AccTree),
-                    IsPrevLeaf = lists:any(fun({_, {LeafPos, [LeafRevId|_]}}) ->
-                            {LeafPos, LeafRevId} == {Pos-1, hd(PrevRevs)}
-                        end, Leafs),
-                    if IsPrevLeaf ->
-                        {NewTree, OldDeleted};
-                    true ->
-                        send_result(Client, Ref, conflict),
-                        {AccTree, OldDeleted}
-                    end;
-                {NewTree, no_conflicts} when  AccTree == NewTree ->
-                    % the tree didn't change at all
-                    % meaning we are saving a rev that's already
-                    % been editted again.
-                    if (Pos == 1) and OldDeleted ->
-                        % this means we are recreating a brand new document
-                        % into a state that already existed before.
-                        % put the rev into a subsequent edit of the deletion
-                        #doc_info{revs=[#rev_info{rev={OldPos,OldRev}}|_]} =
-                                couch_doc:to_doc_info(OldDocInfo),
-                        NewRevId = couch_db:new_revid(
-                                NewDoc#doc{revs={OldPos, [OldRev]}}),
-                        NewDoc2 = NewDoc#doc{revs={OldPos + 1, [NewRevId, OldRev]}},
-                        {NewTree2, _} = couch_key_tree:merge(AccTree,
-                                couch_doc:to_path(NewDoc2), Limit),
-                        % we changed the rev id, this tells the caller we did
-                        send_result(Client, Ref, {ok, {OldPos + 1, NewRevId}}),
-                        {NewTree2, OldDeleted};
-                    true ->
-                        send_result(Client, Ref, conflict),
-                        {AccTree, OldDeleted}
-                    end;
-                {NewTree, _} ->
-                    {NewTree, NewDoc#doc.deleted}
-                end;
-            true ->
-                {NewTree, _} = couch_key_tree:merge(AccTree,
-                            couch_doc:to_path(NewDoc), Limit),
-                {NewTree, OldDeleted}
-            end
-        end,
-        {OldTree, OldDeleted0}, NewDocs),
-    if NewRevTree == OldTree ->
-        % nothing changed
-        merge_rev_trees(Limit, MergeConflicts, RestDocsList, RestOldInfo,
-            AccNewInfos, AccRemoveSeqs, AccSeq);
-    true ->
-        % we have updated the document, give it a new seq #
-        NewInfo = #full_doc_info{id=Id,update_seq=AccSeq+1,rev_tree=NewRevTree},
-        RemoveSeqs = case OldSeq of
-            0 -> AccRemoveSeqs;
-            _ -> [OldSeq | AccRemoveSeqs]
-        end,
-        merge_rev_trees(Limit, MergeConflicts, RestDocsList, RestOldInfo,
-            [NewInfo|AccNewInfos], RemoveSeqs, AccSeq+1)
+merge_rev_trees([NewDocs|RestDocsList], [OldDocInfo|RestOldInfo],
+        AccNewInfos, AccRemoveSeqs, AccSeq, Opts) ->
+    NewDocInfo = lists:foldl(fun({Client, {NewDoc, Ref}}, AccDocInfo) ->
+        case couch_doc:merge(AccDocInfo, NewDoc, Opts) of
+            {ok, NewInfo} ->
+                NewInfo;
+            {ok, NewInfo, NewRev} ->
+                send_result(Client, Ref, {ok, NewRev}),
+                NewInfo;
+            conflict ->
+                send_result(Client, Ref, conflict),
+                AccDocInfo
+        end
+    end, OldDocInfo, NewDocs),
+    case NewDocInfo#full_doc_info.update_seq of
+        increment ->
+            RemSeqs = case OldDocInfo#full_doc_info.update_seq of
+                0 -> AccRemoveSeqs;
+                N -> [N | AccRemoveSeqs]
+            end,
+            NewDocInfo1 = NewDocInfo#full_doc_info{update_seq=AccSeq + 1},
+            merge_rev_trees(RestDocsList, RestOldInfo,
+                [NewDocInfo1 | AccNewInfos], RemSeqs, AccSeq + 1, Opts);
+        _ ->
+            merge_rev_trees(RestDocsList, RestOldInfo,
+                [NewDocInfo | AccNewInfos], AccRemoveSeqs, AccSeq, Opts)
     end.
 
 
-
 new_index_entries([], AccById, AccBySeq, AccDDocIds) ->
     {AccById, AccBySeq, AccDDocIds};
 new_index_entries([FullDocInfo|RestInfos], AccById, AccBySeq, AccDDocIds) ->
@@ -687,8 +642,9 @@ update_docs_int(Db, DocsList, NonRepDocs, MergeConflicts, FullCommit) ->
         end,
         Ids, OldDocLookups),
     % Merge the new docs into the revision trees.
-    {ok, NewFullDocInfos, RemoveSeqs, NewSeq} = merge_rev_trees(RevsLimit,
-            MergeConflicts, DocsList, OldDocInfos, [], [], LastSeq),
+    Options = [{merge_conflicts, MergeConflicts}, {revs_limit, RevsLimit}],
+    {ok, NewFullDocInfos, RemoveSeqs, NewSeq} = merge_rev_trees(DocsList,
+            OldDocInfos, [], [], LastSeq, Options),
 
     % All documents are now ready to write.
 
diff --git a/src/couchdb/couch_doc.erl b/src/couchdb/couch_doc.erl
index 7b7233ed8..801b1d3d5 100644
--- a/src/couchdb/couch_doc.erl
+++ b/src/couchdb/couch_doc.erl
@@ -13,6 +13,7 @@
 -module(couch_doc).
 
 -export([to_doc_info/1,to_doc_info_path/1,parse_rev/1,parse_revs/1,rev_to_str/1,revs_to_strs/1]).
+-export([merge/3]).
 -export([att_foldl/3,range_att_foldl/5,att_foldl_decode/3,get_validate_doc_fun/1]).
 -export([from_json_obj/1,to_json_obj/2,has_stubs/1, merge_stubs/2]).
 -export([validate_docid/1]).
@@ -25,6 +26,69 @@
 
 -include("couch_db.hrl").
 
+
+merge(#full_doc_info{}=OldDoc, #doc{revs={NewPos, _}}=NewDoc, Options) ->
+    #full_doc_info{
+        rev_tree=OldTree,
+        deleted=OldDeleted
+    } = OldDoc,
+    #doc{
+        revs={NewPos, _}
+    } = NewDoc,
+    RevsLimit = couch_util:get_value(revs_limit, Options, 1000),
+    MergeConflicts = couch_util:get_value(merge_conflicts, Options, false),
+    case couch_key_tree:merge(OldTree, to_path(NewDoc), RevsLimit) of
+    {NewTree, new_leaf} ->
+        % Happy case created a new leaf
+        {ok, OldDoc#full_doc_info{
+            rev_tree=NewTree,
+            deleted=NewDoc#doc.deleted,
+            update_seq=increment
+        }};
+    {_, internal_node} when OldDeleted, not MergeConflicts ->
+        % Recreating a deleted document into a state that
+        % previously existed. Create a new revision and
+        % carry on.
+        #doc_info{
+            revs=[#rev_info{rev={OldPos, OldRev}} | _]
+        } = couch_doc:to_doc_info(OldDoc),
+        NewRevId = couch_db:new_revid(NewDoc#doc{revs={OldPos, [OldRev]}}),
+        NewDoc1 = NewDoc#doc{revs={OldPos + 1, [NewRevId, OldRev]}},
+        {Tree, _} = couch_key_tree:merge(OldTree, to_path(NewDoc1), RevsLimit),
+        {ok, OldDoc#full_doc_info{
+            rev_tree=Tree,
+            deleted=NewDoc#doc.deleted,
+            update_seq=increment
+        }, {OldPos + 1, NewRevId}};
+    {NewTree, new_branch} when OldDeleted, not MergeConflicts, NewPos == 1 ->
+        % Recreating a deleted document into a new state.
+        {ok, OldDoc#full_doc_info{
+            rev_tree=NewTree,
+            deleted=NewDoc#doc.deleted,
+            update_seq=increment
+        }};
+    {NewTree, internal_node} when MergeConflicts ->
+        % Replication gave us something we already had so
+        % just update the rev tree and carry on. We keep
+        % the new revision tree in case we're recovering
+        % from COUCHDB-968 and friends but deletion and
+        % update_seqs should not be affected.
+        {ok, OldDoc#full_doc_info{
+            rev_tree=NewTree
+        }};
+    {NewTree, _} when MergeConflicts ->
+        % Replication gave us a new leaf or branch
+        % so we need to bump the update_seq and
+        % deletion status.
+        {ok, OldDoc#full_doc_info{
+            rev_tree=NewTree,
+            deleted=OldDeleted and NewDoc#doc.deleted,
+            update_seq=increment
+        }};
+    _ ->
+        conflict
+    end.
+
 -spec to_path(#doc{}) -> path().
 to_path(#doc{revs={Start, RevIds}}=Doc) ->
     [Branch] = to_branch(Doc, lists:reverse(RevIds)),
diff --git a/src/couchdb/couch_key_tree.erl b/src/couchdb/couch_key_tree.erl
index ce45ab81b..20683e6b9 100644
--- a/src/couchdb/couch_key_tree.erl
+++ b/src/couchdb/couch_key_tree.erl
@@ -54,8 +54,6 @@
 -include("couch_db.hrl").
 
 %% @doc Merge a path with a list of paths and stem to the given length.
--spec merge([path()], path(), pos_integer()) -> {[path()],
-    conflicts | no_conflicts}.
 merge(Paths, Path, Depth) ->
     {Merged, Conflicts} = merge(Paths, Path),
     {stem(Merged, Depth), Conflicts}.
@@ -63,93 +61,80 @@ merge(Paths, Path, Depth) ->
 %% @doc Merge a path with an existing list of paths, returning a new list of
 %% paths. A return of conflicts indicates a new conflict was discovered in this
 %% merge. Conflicts may already exist in the original list of paths.
--spec merge([path()], path()) -> {[path()], conflicts | no_conflicts}.
 merge(Paths, Path) ->
-    {ok, Merged, HasConflicts} = merge_one(Paths, Path, [], false),
-    if HasConflicts ->
-        Conflicts = conflicts;
-    (length(Merged) =/= length(Paths)) and (length(Merged) =/= 1) ->
-        Conflicts = conflicts;
-    true ->
-        Conflicts = no_conflicts
-    end,
-    {lists:sort(Merged), Conflicts}.
-
--spec merge_one(Original::[path()], Inserted::path(), [path()], boolean()) ->
-    {ok, Merged::[path()], NewConflicts::boolean()}.
-merge_one([], Insert, OutAcc, ConflictsAcc) ->
-    {ok, [Insert | OutAcc], ConflictsAcc};
-merge_one([{Start, Tree}|Rest], {StartInsert, TreeInsert}, Acc, HasConflicts) ->
-    case merge_at([Tree], StartInsert - Start, [TreeInsert]) of
-    {ok, [Merged], Conflicts} ->
-        MergedStart = lists:min([Start, StartInsert]),
-        {ok, Rest ++ [{MergedStart, Merged} | Acc], Conflicts or HasConflicts};
-    no ->
-        AccOut = [{Start, Tree} | Acc],
-        merge_one(Rest, {StartInsert, TreeInsert}, AccOut, HasConflicts)
+    {Merged, Status} = merge_one(Paths, Path, []),
+    {lists:sort(Merged), Status}.
+
+merge_one([], Path, []) ->
+    % Special case when the doc is created and has
+    % no revisions to merge with
+    {[Path], new_leaf};
+merge_one([], Path, Acc) ->
+    % Merge created a new top-level branch
+    {[Path | Acc], new_branch};
+merge_one([{Start, Tree} | Rest], {PathStart, PathVals}, Acc) ->
+    try
+        {[Merged], Status} = merge_at([Tree], PathStart - Start, [PathVals]),
+        MergedStart = lists:min([Start, PathStart]),
+        {Rest ++ [{MergedStart, Merged} | Acc], Status}
+    catch throw:no_merge ->
+        merge_one(Rest, {PathStart, PathVals}, [{Start, Tree} | Acc])
     end.
 
--spec merge_at(tree(), Place::integer(), tree()) ->
-    {ok, Merged::tree(), HasConflicts::boolean()} | no.
-merge_at(_Ours, _Place, []) ->
-    no;
-merge_at([], _Place, _Insert) ->
-    no;
-merge_at([{Key, Value, SubTree}|Sibs], Place, InsertTree) when Place > 0 ->
-    % inserted starts later than committed, need to drill into committed subtree
-    case merge_at(SubTree, Place - 1, InsertTree) of
-    {ok, Merged, Conflicts} ->
-        {ok, [{Key, Value, Merged} | Sibs], Conflicts};
-    no ->
+merge_at([], _Depth, _Path) ->
+    throw(no_merge);
+merge_at([{Key, Value, SubTree} | Sibs], Depth, Path) when Depth > 0 ->
+    % inserted starts later than committed,
+    % need to drill into committed subtree
+    try
+        {Merged0, Status0} = merge_at(SubTree, Depth - 1, Path),
+        {[{Key, Value, Merged0} | Sibs], Status0}
+    catch throw:no_merge ->
         % first branch didn't merge, move to next branch
-        case merge_at(Sibs, Place, InsertTree) of
-        {ok, Merged, Conflicts} ->
-            {ok, [{Key, Value, SubTree} | Merged], Conflicts};
-        no ->
-            no
-        end
-    end;
-merge_at(OurTree, Place, [{Key, Value, SubTree}]) when Place < 0 ->
-    % inserted starts earlier than committed, need to drill into insert subtree
-    case merge_at(OurTree, Place + 1, SubTree) of
-    {ok, Merged, Conflicts} ->
-        {ok, [{Key, Value, Merged}], Conflicts};
-    no ->
-        no
+        {Merged1, Status1} = merge_at(Sibs, Depth, Path),
+        {[{Key, Value, SubTree} | Merged1], Status1}
     end;
-merge_at([{Key, V1, SubTree}|Sibs], 0, [{Key, V2, InsertSubTree}]) ->
-    {Merged, Conflicts} = merge_simple(SubTree, InsertSubTree),
-    {ok, [{Key, value_pref(V1, V2), Merged} | Sibs], Conflicts};
+merge_at(OurTree, Depth, [{Key, Value, SubPath}]) when Depth < 0 ->
+    % inserted starts earlier than committed,
+    % need to drill into insert subtree
+    {Merged, Status} = merge_at(OurTree, Depth + 1, SubPath),
+    {[{Key, Value, Merged}], Status};
+merge_at([{Key, V1, SubTree} | Sibs], 0, [{Key, V2, SubPath}]) ->
+    {Merged, Status} = merge_simple(SubTree, SubPath),
+    {[{Key, value_pref(V1, V2), Merged} | Sibs], Status};
 merge_at([{OurKey, _, _} | _], 0, [{Key, _, _}]) when OurKey > Key ->
     % siblings keys are ordered, no point in continuing
-    no;
+    throw(no_merge);
 merge_at([Tree | Sibs], 0, InsertTree) ->
-    case merge_at(Sibs, 0, InsertTree) of
-    {ok, Merged, Conflicts} ->
-        {ok, [Tree | Merged], Conflicts};
-    no ->
-        no
-    end.
-
-% key tree functions
+    {Merged, Status} = merge_at(Sibs, 0, InsertTree),
+    {[Tree | Merged], Status}.
 
--spec merge_simple(tree(), tree()) -> {Merged::tree(), NewConflicts::boolean()}.
+merge_simple([], []) ->
+    % Inserted path lands on a leaf
+    {[], internal_node};
 merge_simple([], B) ->
-    {B, false};
+    % Inserted path extends a leaf
+    {B, new_leaf};
 merge_simple(A, []) ->
-    {A, false};
-merge_simple([{Key, V1, SubA} | NextA], [{Key, V2, SubB} | NextB]) ->
-    {MergedSubTree, Conflict1} = merge_simple(SubA, SubB),
-    {MergedNextTree, Conflict2} = merge_simple(NextA, NextB),
-    Value = value_pref(V1, V2),
-    {[{Key, Value, MergedSubTree} | MergedNextTree], Conflict1 or Conflict2};
-merge_simple([{A, _, _} = Tree | Next], [{B, _, _} | _] = Insert) when A < B ->
-    {Merged, Conflict} = merge_simple(Next, Insert),
-    % if Merged has more branches than the input we added a new conflict
-    {[Tree | Merged], Conflict orelse (length(Merged) > length(Next))};
-merge_simple(Ours, [Tree | Next]) ->
-    {Merged, Conflict} = merge_simple(Ours, Next),
-    {[Tree | Merged], Conflict orelse (length(Merged) > length(Next))}.
+    % Ran out of insertion path at an internal node
+    {A, internal_node};
+merge_simple([{Key, V1, SubTree} | NextTree], [{Key, V2, SubPath}]) ->
+    % Keys match, continue descending along this branch
+    {Merged, Status} = merge_simple(SubTree, SubPath),
+    {[{Key, value_pref(V1, V2), Merged} | NextTree], Status};
+merge_simple([{A, _, _} = Tree | Siblings], [{B, _, _}] = Path) when A < B ->
+    % Keep trying siblings until we run out or find a
+    % key A > B
+    {Merged, Status0} = merge_simple(Siblings, Path),
+    Status = case length(Merged) == length(Siblings) of
+        true -> Status0;
+        false -> new_branch
+    end,
+    {[Tree | Merged], Status};
+merge_simple(Tree, [Path]) ->
+    % Sorted keys means we know the rest of the path
+    % is a new branch
+    {[Path | Tree], new_branch}.
 
 find_missing(_Tree, []) ->
     [];
diff --git a/test/etap/060-kt-merging.t b/test/etap/060-kt-merging.t
index efbdbf695..f44e40d9d 100755
--- a/test/etap/060-kt-merging.t
+++ b/test/etap/060-kt-merging.t
@@ -26,123 +26,154 @@ main(_) ->
     ok.
 
 test() ->
-    One = {1, {"1","foo",[]}},
 
-    etap:is(
-        {[One], no_conflicts},
-        couch_key_tree:merge([], One, 10),
-        "The empty tree is the identity for merge."
+    Simple = {1, {"1","foo",[]}},
+    TwoDeep0 = {1, {"1", "foo", [{"2_0", "bar", []}]}},
+    TwoDeep1 = {1, {"1", "foo", [{"2_1", "baz", []}]}},
+    NewLeaf = {2, {"2_0", "bar", [{"3", "bing", []}]}},
+    WithNewLeaf = {1, {"1", "foo", [{"2_0", "bar", [{"3", "bing", []}]}]}},
+    NewBranch = {1, {"1", "foo", [{"2_0", "bar", []}, {"2_1", "baz", []}]}},
+    NewDeepBranch = {2, {"2_0", "bar", [{"3_1", "bang", []}]}},
+
+    StemmedEdit = {3, {"3", "bing", []}},
+    StemmedConflicts = [Simple, StemmedEdit],
+
+    NewBranchLeaf = {1,
+        {"1", "foo", [
+            {"2_0", "bar", [
+                {"3", "bing", []}
+            ]},
+            {"2_1", "baz", []}
+        ]}
+    },
+
+    NewBranchLeafBranch = {1,
+        {"1", "foo", [
+            {"2_0", "bar", [
+                {"3", "bing", []},
+                {"3_1", "bang", []}
+            ]},
+            {"2_1", "baz", []}
+        ]}
+    },
+
+    Stemmed2 = [
+        {1, {"1", "foo", [
+            {"2_1", "baz", []}
+        ]}},
+        {2, {"2_0", "bar", [
+            {"3", "bing", []},
+            {"3_1", "bang", []}
+        ]}}
+    ],
+
+    Stemmed3 = [
+        {2, {"2_1", "baz", []}},
+        {3, {"3", "bing", []}},
+        {3, {"3_1", "bang", []}}
+    ],
+
+    PartialRecover = [
+        {1, {"1", "foo", [
+            {"2_0", "bar", [
+                {"3", "bing", []}
+            ]}
+        ]}},
+        {2, {"2_1", "baz", []}},
+        {3, {"3_1", "bang", []}}
+    ],
+
+    etap:is(
+        couch_key_tree:merge([], Simple, 10),
+        {[Simple], new_leaf},
+        "Merging a path into an empty tree is the path"
     ),
+
     etap:is(
-        {[One], no_conflicts},
-        couch_key_tree:merge([One], One, 10),
-        "Merging is reflexive."
+        couch_key_tree:merge([Simple], Simple, 10),
+        {[Simple], internal_node},
+        "Remerge path into path is reflexive"
     ),
 
-    TwoSibs = [{1, {"1","foo",[]}},
-               {1, {"2","foo",[]}}],
-
     etap:is(
-        {TwoSibs, no_conflicts},
-        couch_key_tree:merge(TwoSibs, One, 10),
-        "Merging a prefix of a tree with the tree yields the tree."
+        couch_key_tree:merge([], TwoDeep0, 10),
+        {[TwoDeep0], new_leaf},
+        "Merging a path with multiple entries is the path"
     ),
 
-    Three = {1, {"3","foo",[]}},
-    ThreeSibs = [{1, {"1","foo",[]}},
-                 {1, {"2","foo",[]}},
-                 {1, {"3","foo",[]}}],
-
     etap:is(
-        {ThreeSibs, conflicts},
-        couch_key_tree:merge(TwoSibs, Three, 10),
-        "Merging a third unrelated branch leads to a conflict."
+        couch_key_tree:merge([TwoDeep0], TwoDeep0, 10),
+        {[TwoDeep0], internal_node},
+        "Merging a path with multiple entries is reflexive"
     ),
 
-
-    TwoChild = {1, {"1","foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
-
     etap:is(
-        {[TwoChild], no_conflicts},
-        couch_key_tree:merge([TwoChild], TwoChild, 10),
-        "Merging two children is still reflexive."
+        couch_key_tree:merge([TwoDeep0], Simple, 10),
+        {[TwoDeep0], internal_node},
+        "Merging a subpath into a path results in the path"
     ),
 
-    TwoChildSibs = {1, {"1","foo", [{"1a", "bar", []},
-                                     {"1b", "bar", []}]}},
     etap:is(
-        {[TwoChildSibs], no_conflicts},
-        couch_key_tree:merge([TwoChildSibs], TwoChildSibs, 10),
-        "Merging a tree to itself is itself."),
-
-    TwoChildPlusSibs =
-        {1, {"1","foo", [{"1a", "bar", [{"1aa", "bar", []}]},
-                         {"1b", "bar", []}]}},
+        couch_key_tree:merge([TwoDeep0], NewLeaf, 10),
+        {[WithNewLeaf], new_leaf},
+        "Merging a new leaf gives us a new leaf"
+    ),
 
     etap:is(
-        {[TwoChildPlusSibs], no_conflicts},
-        couch_key_tree:merge([TwoChild], TwoChildSibs, 10),
-        "Merging tree of uneven length at node 2."),
+        couch_key_tree:merge([TwoDeep0], TwoDeep1, 10),
+        {[NewBranch], new_branch},
+        "Merging a new branch returns a proper tree"
+    ),
 
-    Stemmed1b = {2, {"1a", "bar", []}},
     etap:is(
-        {[TwoChildSibs], no_conflicts},
-        couch_key_tree:merge([TwoChildSibs], Stemmed1b, 10),
-        "Merging a tree with a stem."
+        couch_key_tree:merge([TwoDeep1], TwoDeep0, 10),
+        {[NewBranch], new_branch},
+        "Order of merging does not affect the resulting tree"
     ),
 
-    TwoChildSibs2 = {1, {"1","foo", [{"1a", "bar", []},
-                                     {"1b", "bar", [{"1bb", "boo", []}]}]}},
-    Stemmed1bb = {3, {"1bb", "boo", []}},
     etap:is(
-        {[TwoChildSibs2], no_conflicts},
-        couch_key_tree:merge([TwoChildSibs2], Stemmed1bb, 10),
-        "Merging a stem at a deeper level."
+        couch_key_tree:merge([NewBranch], NewLeaf, 10),
+        {[NewBranchLeaf], new_leaf},
+        "Merging a new_leaf doesn't return new_branch when branches exist"
     ),
 
-    StemmedTwoChildSibs2 = [{2,{"1a", "bar", []}},
-                            {2,{"1b", "bar", [{"1bb", "boo", []}]}}],
-
     etap:is(
-        {StemmedTwoChildSibs2, no_conflicts},
-        couch_key_tree:merge(StemmedTwoChildSibs2, Stemmed1bb, 10),
-        "Merging a stem at a deeper level against paths at deeper levels."
+        couch_key_tree:merge([NewBranchLeaf], NewDeepBranch, 10),
+        {[NewBranchLeafBranch], new_branch},
+        "Merging a deep branch with branches works"
     ),
 
-    Stemmed1aa = {3, {"1aa", "bar", []}},
     etap:is(
-        {[TwoChild], no_conflicts},
-        couch_key_tree:merge([TwoChild], Stemmed1aa, 10),
-        "Merging a single tree with a deeper stem."
+        couch_key_tree:merge(StemmedConflicts, WithNewLeaf, 10),
+        {[WithNewLeaf], new_leaf},
+        "New information reconnects steming induced conflicts"
     ),
 
-    Stemmed1a = {2, {"1a", "bar", [{"1aa", "bar", []}]}},
     etap:is(
-        {[TwoChild], no_conflicts},
-        couch_key_tree:merge([TwoChild], Stemmed1a, 10),
-        "Merging a larger stem."
+        couch_key_tree:merge([TwoDeep0], NewLeaf, 2),
+        {[NewLeaf], new_leaf},
+        "Simple stemming works"
     ),
 
     etap:is(
-        {[Stemmed1a], no_conflicts},
-        couch_key_tree:merge([Stemmed1a], Stemmed1aa, 10),
-        "More merging."
+        couch_key_tree:merge([NewBranchLeafBranch], Simple, 2),
+        {Stemmed2, internal_node},
+        "Merge with stemming works correctly for branches"
     ),
 
-    OneChild = {1, {"1","foo",[{"1a", "bar", []}]}},
-    Expect1 = [OneChild, Stemmed1aa],
     etap:is(
-        {Expect1, conflicts},
-        couch_key_tree:merge([OneChild], Stemmed1aa, 10),
-        "Merging should create conflicts."
+        couch_key_tree:merge([NewBranchLeafBranch], Simple, 1),
+        {Stemmed3, internal_node},
+        "Merge with stemming to leaves works fine"
     ),
 
     etap:is(
-        {[TwoChild], no_conflicts},
-        couch_key_tree:merge(Expect1, TwoChild, 10),
-        "Merge should have no conflicts."
+        couch_key_tree:merge(Stemmed3, WithNewLeaf, 10),
+        {PartialRecover, internal_node},
+        "Merging unstemmed recovers as much as possible without losing info"
     ),
 
+
     %% this test is based on couch-902-test-case2.py
     %% foo has conflicts from replication at depth two
     %% foo3 is the current value
@@ -168,7 +199,7 @@ test() ->
                ]}},
 
     etap:is(
-      {[FooBar], no_conflicts},
+      {[FooBar], new_leaf},
       couch_key_tree:merge([Foo],Bar,10),
       "Merging trees with conflicts ought to behave."
     ),