You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by da...@apache.org on 2012/01/25 08:20:54 UTC
[1/4] git commit: Refactor revision merging
Updated Branches:
refs/heads/new-security-object [created] 76fff259a
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.
Project: http://git-wip-us.apache.org/repos/asf/couchdb/repo
Commit: http://git-wip-us.apache.org/repos/asf/couchdb/commit/0ab5ebda
Tree: http://git-wip-us.apache.org/repos/asf/couchdb/tree/0ab5ebda
Diff: http://git-wip-us.apache.org/repos/asf/couchdb/diff/0ab5ebda
Branch: refs/heads/new-security-object
Commit: 0ab5ebda993ee9c76ba535369538ad4fd9010257
Parents: 6282b5d
Author: Paul Joseph Davis <da...@apache.org>
Authored: Wed Jan 18 20:04:54 2012 -0600
Committer: Paul Joseph Davis <da...@apache.org>
Committed: Wed Jan 25 01:14:07 2012 -0600
----------------------------------------------------------------------
src/couchdb/couch_db_updater.erl | 104 ++++++-------------
src/couchdb/couch_doc.erl | 64 ++++++++++++
src/couchdb/couch_key_tree.erl | 139 +++++++++++--------------
test/etap/060-kt-merging.t | 183 +++++++++++++++++++--------------
4 files changed, 263 insertions(+), 227 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/couchdb/blob/0ab5ebda/src/couchdb/couch_db_updater.erl
----------------------------------------------------------------------
diff --git a/src/couchdb/couch_db_updater.erl b/src/couchdb/couch_db_updater.erl
index 54531db..0bfe951 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.
http://git-wip-us.apache.org/repos/asf/couchdb/blob/0ab5ebda/src/couchdb/couch_doc.erl
----------------------------------------------------------------------
diff --git a/src/couchdb/couch_doc.erl b/src/couchdb/couch_doc.erl
index 7b7233e..801b1d3 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)),
http://git-wip-us.apache.org/repos/asf/couchdb/blob/0ab5ebda/src/couchdb/couch_key_tree.erl
----------------------------------------------------------------------
diff --git a/src/couchdb/couch_key_tree.erl b/src/couchdb/couch_key_tree.erl
index ce45ab8..20683e6 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, []) ->
[];
http://git-wip-us.apache.org/repos/asf/couchdb/blob/0ab5ebda/test/etap/060-kt-merging.t
----------------------------------------------------------------------
diff --git a/test/etap/060-kt-merging.t b/test/etap/060-kt-merging.t
index efbdbf6..f44e40d 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."
),