Change key_tree merge to take path as 2nd arg, add type specs

git-svn-id: https://svn.apache.org/repos/asf/couchdb/branches/1.1.x@1043462 13f79535-47bb-0310-9956-ffa450edef68

4 files changed, 56 insertions, 69 deletions

diff --git a/src/couchdb/couch_db.erl b/src/couchdb/couch_db.erl
index 03341bdd..4e945ad4 100644
--- a/src/couchdb/couch_db.erl
+++ b/src/couchdb/couch_db.erl
@@ -555,7 +555,7 @@ prep_and_validate_replicated_updates(Db, [Bucket|RestBuckets], [OldInfo|RestOldI
     {ok, #full_doc_info{rev_tree=OldTree}} ->
         NewRevTree = lists:foldl(
             fun(NewDoc, AccTree) ->
-                {NewTree, _} = couch_key_tree:merge(AccTree, [couch_db:doc_to_tree(NewDoc)]),
+                {NewTree, _} = couch_key_tree:merge(AccTree, couch_db:doc_to_tree(NewDoc)),
                 NewTree
             end,
             OldTree, Bucket),
diff --git a/src/couchdb/couch_db_updater.erl b/src/couchdb/couch_db_updater.erl
index 8630ff4e..bd404c64 100644
--- a/src/couchdb/couch_db_updater.erl
+++ b/src/couchdb/couch_db_updater.erl
@@ -498,7 +498,7 @@ merge_rev_trees(Limit, MergeConflicts, [NewDocs|RestDocsList],
     NewRevTree0 = lists:foldl(
         fun({Client, #doc{revs={Pos,[_Rev|PrevRevs]}}=NewDoc}, AccTree) ->
             if not MergeConflicts ->
-                case couch_key_tree:merge(AccTree, [couch_db:doc_to_tree(NewDoc)]) of
+                case couch_key_tree:merge(AccTree, couch_db:doc_to_tree(NewDoc)) of
                 {_NewTree, conflicts} when (not OldDeleted) ->
                     send_result(Client, Id, {Pos-1,PrevRevs}, conflict),
                     AccTree;
@@ -529,7 +529,7 @@ merge_rev_trees(Limit, MergeConflicts, [NewDocs|RestDocsList],
                                 NewDoc#doc{revs={OldPos, [OldRev]}}),
                         NewDoc2 = NewDoc#doc{revs={OldPos + 1, [NewRevId, OldRev]}},
                         {NewTree2, _} = couch_key_tree:merge(AccTree,
-                                [couch_db:doc_to_tree(NewDoc2)]),
+                                couch_db:doc_to_tree(NewDoc2)),
                         % we changed the rev id, this tells the caller we did
                         send_result(Client, Id, {Pos-1,PrevRevs},
                                 {ok, {OldPos + 1, NewRevId}}),
@@ -543,7 +543,7 @@ merge_rev_trees(Limit, MergeConflicts, [NewDocs|RestDocsList],
                 end;
             true ->
                 {NewTree, _} = couch_key_tree:merge(AccTree,
-                            [couch_db:doc_to_tree(NewDoc)]),
+                            couch_db:doc_to_tree(NewDoc)),
                 NewTree
             end
         end,
diff --git a/src/couchdb/couch_key_tree.erl b/src/couchdb/couch_key_tree.erl
index bc3775c4..2e3b3e3c 100644
--- a/src/couchdb/couch_key_tree.erl
+++ b/src/couchdb/couch_key_tree.erl
@@ -16,31 +16,27 @@
 -export([map/2, get_all_leafs/1, count_leafs/1, remove_leafs/2,
     get_all_leafs_full/1,stem/2,map_leafs/2]).
 
-% a key tree looks like this:
-% Tree -> [] or [{Key, Value, ChildTree} | SiblingTree]
-% ChildTree -> Tree
-% SiblingTree -> [] or [{SiblingKey, Value, Tree} | Tree]
-% And each Key < SiblingKey
-
+% Tree::term() is really a tree(), but we don't want to require R13B04 yet
+-type branch() :: {Key::term(), Value::term(), Tree::term()}.
+-type path() :: {Start::pos_integer(), branch()}.
+-type tree() :: [branch()]. % sorted by key
 
 % partial trees arranged by how much they are cut off.
 
-merge(A, B) ->
-    {Merged, HasConflicts} =
-    lists:foldl(
-        fun(InsertTree, {AccTrees, AccConflicts}) ->
-            {ok, Merged, Conflicts} = merge_one(AccTrees, InsertTree, [], false),
-            {Merged, Conflicts or AccConflicts}
-        end,
-        {A, false}, B),
-    if HasConflicts or
-            ((length(Merged) =/= length(A)) and (length(Merged) =/= length(B))) ->
+-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) ->
@@ -53,6 +49,8 @@ merge_one([{Start, Tree}|Rest], {StartInsert, TreeInsert}, Acc, HasConflicts) ->
         merge_one(Rest, {StartInsert, TreeInsert}, AccOut, HasConflicts)
     end.
 
+-spec merge_at(tree(), Place::integer(), tree()) ->
+    {ok, Merged::tree(), HasConflicts::boolean()} | no.
 merge_at(_Ours, _Place, []) ->
     no;
 merge_at([], _Place, _Insert) ->
@@ -93,6 +91,8 @@ merge_at([Tree | Sibs], 0, InsertTree) ->
     end.
 
 % key tree functions
+
+-spec merge_simple(tree(), tree()) -> {Merged::tree(), NewConflicts::boolean()}.
 merge_simple([], B) ->
     {B, false};
 merge_simple(A, []) ->
@@ -156,7 +156,7 @@ remove_leafs(Trees, Keys) ->
         fun({PathPos, Path},TreeAcc) ->
             [SingleTree] = lists:foldl(
                 fun({K,V},NewTreeAcc) -> [{K,V,NewTreeAcc}] end, [], Path),
-            {NewTrees, _} = merge(TreeAcc, [{PathPos + 1 - length(Path), SingleTree}]),
+            {NewTrees, _} = merge(TreeAcc, {PathPos + 1 - length(Path), SingleTree}),
             NewTrees
         end, [], FilteredPaths),
     {NewTree, RemovedKeys}.
@@ -318,7 +318,7 @@ stem(Trees, Limit) ->
         fun({PathPos, Path},TreeAcc) ->
             [SingleTree] = lists:foldl(
                 fun({K,V},NewTreeAcc) -> [{K,V,NewTreeAcc}] end, [], Path),
-            {NewTrees, _} = merge(TreeAcc, [{PathPos + 1 - length(Path), SingleTree}]),
+            {NewTrees, _} = merge(TreeAcc, {PathPos + 1 - length(Path), SingleTree}),
             NewTrees
         end, [], Paths2).
 
diff --git a/test/etap/060-kt-merging.t b/test/etap/060-kt-merging.t
index 73744e52..5a8571ac 100755
--- a/test/etap/060-kt-merging.t
+++ b/test/etap/060-kt-merging.t
@@ -15,7 +15,7 @@
 
 main(_) ->
     test_util:init_code_path(),
-    etap:plan(14),
+    etap:plan(12),
     case (catch test()) of
         ok ->
             etap:end_tests();
@@ -26,101 +26,88 @@ main(_) ->
     ok.
 
 test() ->
-    EmptyTree = [],
-    One = [{0, {"1","foo",[]}}],
+    One = {0, {"1","foo",[]}},
     TwoSibs = [{0, {"1","foo",[]}},
                {0, {"2","foo",[]}}],
-    OneChild = [{0, {"1","foo",[{"1a", "bar", []}]}}],
-    TwoChild = [{0, {"1","foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}}],
-    TwoChildSibs = [{0, {"1","foo", [{"1a", "bar", []},
-                                     {"1b", "bar", []}]}}],
-    TwoChildSibs2 = [{0, {"1","foo", [{"1a", "bar", []},
-                                     {"1b", "bar", [{"1bb", "boo", []}]}]}}],
-    Stemmed1b = [{1, {"1a", "bar", []}}],
-    Stemmed1a = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
-    Stemmed1aa = [{2, {"1aa", "bar", []}}],
-    Stemmed1bb = [{2, {"1bb", "boo", []}}],
+    OneChild = {0, {"1","foo",[{"1a", "bar", []}]}},
+    TwoChild = {0, {"1","foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
+    TwoChildSibs = {0, {"1","foo", [{"1a", "bar", []},
+                                     {"1b", "bar", []}]}},
+    TwoChildSibs2 = {0, {"1","foo", [{"1a", "bar", []},
+                                     {"1b", "bar", [{"1bb", "boo", []}]}]}},
+    Stemmed1b = {1, {"1a", "bar", []}},
+    Stemmed1a = {1, {"1a", "bar", [{"1aa", "bar", []}]}},
+    Stemmed1aa = {2, {"1aa", "bar", []}},
+    Stemmed1bb = {2, {"1bb", "boo", []}},
 
     etap:is(
-        {EmptyTree, no_conflicts},
-        couch_key_tree:merge(EmptyTree, EmptyTree),
-        "Merging two empty trees yields an empty tree."
-    ),
-
-    etap:is(
-        {One, no_conflicts},
-        couch_key_tree:merge(EmptyTree, One),
+        {[One], no_conflicts},
+        couch_key_tree:merge([], One),
         "The empty tree is the identity for merge."
     ),
 
     etap:is(
-        {One, no_conflicts},
-        couch_key_tree:merge(One, EmptyTree),
-        "Merging is commutative."
-    ),
-
-    etap:is(
         {TwoSibs, no_conflicts},
-        couch_key_tree:merge(One, TwoSibs),
+        couch_key_tree:merge(TwoSibs, One),
         "Merging a prefix of a tree with the tree yields the tree."
     ),
 
     etap:is(
-        {One, no_conflicts},
-        couch_key_tree:merge(One, One),
+        {[One], no_conflicts},
+        couch_key_tree:merge([One], One),
         "Merging is reflexive."
     ),
 
     etap:is(
-        {TwoChild, no_conflicts},
-        couch_key_tree:merge(TwoChild, TwoChild),
+        {[TwoChild], no_conflicts},
+        couch_key_tree:merge([TwoChild], TwoChild),
         "Merging two children is still reflexive."
     ),
 
     etap:is(
-        {TwoChildSibs, no_conflicts},
-        couch_key_tree:merge(TwoChildSibs, TwoChildSibs),
+        {[TwoChildSibs], no_conflicts},
+        couch_key_tree:merge([TwoChildSibs], TwoChildSibs),
         "Merging a tree to itself is itself."),
 
     etap:is(
-        {TwoChildSibs, no_conflicts},
-        couch_key_tree:merge(TwoChildSibs, Stemmed1b),
+        {[TwoChildSibs], no_conflicts},
+        couch_key_tree:merge([TwoChildSibs], Stemmed1b),
         "Merging a tree with a stem."
     ),
 
     etap:is(
-        {TwoChildSibs2, no_conflicts},
-        couch_key_tree:merge(TwoChildSibs2, Stemmed1bb),
+        {[TwoChildSibs2], no_conflicts},
+        couch_key_tree:merge([TwoChildSibs2], Stemmed1bb),
         "Merging a stem at a deeper level."
     ),
 
     etap:is(
-        {TwoChild, no_conflicts},
-        couch_key_tree:merge(TwoChild, Stemmed1aa),
+        {[TwoChild], no_conflicts},
+        couch_key_tree:merge([TwoChild], Stemmed1aa),
         "Merging a single tree with a deeper stem."
     ),
 
     etap:is(
-        {TwoChild, no_conflicts},
-        couch_key_tree:merge(TwoChild, Stemmed1a),
+        {[TwoChild], no_conflicts},
+        couch_key_tree:merge([TwoChild], Stemmed1a),
         "Merging a larger stem."
     ),
 
     etap:is(
-        {Stemmed1a, no_conflicts},
-        couch_key_tree:merge(Stemmed1a, Stemmed1aa),
+        {[Stemmed1a], no_conflicts},
+        couch_key_tree:merge([Stemmed1a], Stemmed1aa),
         "More merging."
     ),
 
-    Expect1 = OneChild ++ Stemmed1aa,
+    Expect1 = [OneChild, Stemmed1aa],
     etap:is(
         {Expect1, conflicts},
-        couch_key_tree:merge(OneChild, Stemmed1aa),
+        couch_key_tree:merge([OneChild], Stemmed1aa),
         "Merging should create conflicts."
     ),
 
     etap:is(
-        {TwoChild, no_conflicts},
+        {[TwoChild], no_conflicts},
         couch_key_tree:merge(Expect1, TwoChild),
         "Merge should have no conflicts."
     ),