From 9dfee1dbbd7f6cbb255094db860f836c79ace274 Mon Sep 17 00:00:00 2001 From: Adam Kocoloski Date: Wed, 8 Dec 2010 15:48:59 +0000 Subject: 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 --- src/couchdb/couch_db.erl | 2 +- src/couchdb/couch_db_updater.erl | 6 +-- src/couchdb/couch_key_tree.erl | 36 +++++++++--------- test/etap/060-kt-merging.t | 81 +++++++++++++++++----------------------- 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." ), -- cgit v1.2.3