couchdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dam...@apache.org
Subject svn commit: r741844 [2/2] - in /couchdb/branches/rep_security: ./ etc/couchdb/ share/www/script/ src/couchdb/
Date Sat, 07 Feb 2009 05:23:04 GMT
Modified: couchdb/branches/rep_security/src/couchdb/couch_key_tree.erl
URL: http://svn.apache.org/viewvc/couchdb/branches/rep_security/src/couchdb/couch_key_tree.erl?rev=741844&r1=741842&r2=741844&view=diff
==============================================================================
--- couchdb/branches/rep_security/src/couchdb/couch_key_tree.erl (original)
+++ couchdb/branches/rep_security/src/couchdb/couch_key_tree.erl Sat Feb  7 05:23:02 2009
@@ -13,7 +13,8 @@
 -module(couch_key_tree).
 
 -export([merge/2, find_missing/2, get_key_leafs/2, get_full_key_paths/2, get/2]).
--export([map/2, get_all_leafs/1, get_leaf_keys/1, count_leafs/1, remove_leafs/2,get_all_leafs_full/1]).
+-export([map/2, get_all_leafs/1, count_leafs/1, remove_leafs/2,
+    get_all_leafs_full/1,test/0]).
 
 % a key tree looks like this:
 % Tree -> [] or [{Key, Value, ChildTree} | SiblingTree]
@@ -22,70 +23,176 @@
 % And each Key < SiblingKey
 
 
+% partial trees arranged by how much they are cut off.
 
-% key tree functions
+merge(A0, B0) ->
+    % convert to canonical
+    A = make_canonical(A0),
+    B = make_canonical(B0),
+    {Merged, HasConflicts} = 
+    lists:foldl(
+        fun(InsertTree, {AccTrees, AccConflicts}) ->
+            case merge_one(AccTrees, InsertTree, [], false) of
+            {ok, Merged, Conflicts} ->
+                {Merged, Conflicts or AccConflicts};
+            no ->
+                {[InsertTree | AccTrees], true} 
+            end
+        end,
+        {A, false}, B),
+    if HasConflicts or 
+            ((length(Merged) /= length(A)) and (length(Merged) /= length(B))) ->
+        Conflicts = conflicts;
+    true ->
+        Conflicts = no_conflicts
+    end,
+    {lists:sort(Merged), Conflicts}.
 
-% When the same key is found in the trees, the value in tree B is discarded.
-merge([], B) ->
-    B;
-merge(A, []) ->
-    A;
-merge([ATree | ANextTree], [BTree | BNextTree]) ->
+make_canonical([{_Start, _Tree} | _] = Can) ->
+    Can; % already canonical
+make_canonical(Trees) ->
+    [{0, Tree} || Tree <- Trees].
+
+merge_one([], Insert, OutAcc, ConflictsAcc) ->
+    {ok, [Insert | OutAcc], ConflictsAcc};
+merge_one([{Start, Tree}|Rest], {StartInsert, TreeInsert}, OutAcc, ConflictsAcc) ->
+    if Start =< StartInsert ->
+        StartA = Start,
+        StartB = StartInsert,
+        TreeA = Tree,
+        TreeB = TreeInsert;
+    true ->
+        StartB = Start,
+        StartA = StartInsert,
+        TreeB = Tree,
+        TreeA = TreeInsert
+    end,
+    case merge_at([TreeA], StartB - StartA, TreeB) of
+    {ok, [CombinedTrees], Conflicts} ->
+        merge_one(Rest, {StartA, CombinedTrees}, OutAcc, Conflicts or ConflictsAcc);
+    no ->
+        merge_one(Rest, {StartB, TreeB}, [{StartA, TreeA} | OutAcc], ConflictsAcc)
+    end.
+    
+merge_at([], _Place, _Insert) ->
+    no;
+merge_at([{Key, Value, SubTree}|Sibs], 0, {InsertKey, InsertValue, InsertSubTree}) ->
+    if Key == InsertKey ->
+        {Merge, Conflicts} = merge_simple(SubTree, InsertSubTree),
+        {ok, [{Key, Value, Merge} | Sibs], Conflicts};
+    true ->
+        case merge_at(Sibs, 0, {InsertKey, InsertValue, InsertSubTree}) of
+        {ok, Merged, Conflicts} ->
+            {ok, [{Key, Value, SubTree} | Merged], Conflicts};
+        no ->
+            no
+        end
+    end;
+merge_at([{Key, Value, SubTree}|Sibs], Place, Insert) ->
+    case merge_at(SubTree, Place - 1,Insert) of
+    {ok, Merged, Conflicts} ->
+        {ok, [{Key, Value, Merged} | Sibs], Conflicts};
+    no ->
+        case merge_at(Sibs, Place, Insert) of
+        {ok, Merged} ->
+            [{Key, Value, SubTree} | Merged];
+        no ->
+            no
+        end
+    end.
+
+% key tree functions
+merge_simple([], B) ->
+    {B, false};
+merge_simple(A, []) ->
+    {A, false};
+merge_simple([ATree | ANextTree], [BTree | BNextTree]) ->
     {AKey, AValue, ASubTree} = ATree,
     {BKey, _BValue, BSubTree} = BTree,
     if
     AKey == BKey ->
         %same key
-        MergedSubTree = merge(ASubTree, BSubTree),
-        MergedNextTree = merge(ANextTree, BNextTree),
-        [{AKey, AValue, MergedSubTree} | MergedNextTree];
+        {MergedSubTree, Conflict1} = merge_simple(ASubTree, BSubTree),
+        {MergedNextTree, Conflict2} = merge_simple(ANextTree, BNextTree),
+        {[{AKey, AValue, MergedSubTree} | MergedNextTree], Conflict1 or Conflict2};
     AKey < BKey ->
-        [ATree | merge(ANextTree, [BTree | BNextTree])];
+        {MTree, _} = merge_simple(ANextTree, [BTree | BNextTree]),
+        {[ATree | MTree], true};
     true ->
-        [BTree | merge([ATree | ANextTree], BNextTree)]
+        {MTree, _} = merge_simple([ATree | ANextTree], BNextTree),
+        {[BTree | MTree], true}
     end.
 
 find_missing(_Tree, []) ->
     [];
-find_missing([], Keys) ->
-    Keys;
-find_missing([{Key, _, SubTree} | RestTree], Keys) ->
-    SrcKeys2 = Keys -- [Key],
-    SrcKeys3 = find_missing(SubTree, SrcKeys2),
-    find_missing(RestTree, SrcKeys3).
-
-
-get_all_key_paths_rev([], KeyPathAcc) ->
-    KeyPathAcc;
-get_all_key_paths_rev([{Key, Value, SubTree} | RestTree], KeyPathAcc) ->
-    get_all_key_paths_rev(SubTree, [{Key, Value} | KeyPathAcc]) ++
-        get_all_key_paths_rev(RestTree, KeyPathAcc).
-        
+find_missing([], SeachKeys) ->
+    SeachKeys;
+find_missing([{Start, {Key, Value, SubTree}} | RestTree], SeachKeys) ->
+    PossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos >=
Start],
+    ImpossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos <
Start],
+    Missing = find_missing_simple(Start, [{Key, Value, SubTree}], PossibleKeys),
+    find_missing(RestTree, ImpossibleKeys ++ Missing).
+    
+find_missing_simple(_Pos, _Tree, []) ->
+    [];
+find_missing_simple(_Pos, [], SeachKeys) ->
+    SeachKeys;
+find_missing_simple(Pos, [{Key, _, SubTree} | RestTree], SeachKeys) ->
+    PossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos >=
Pos],
+    ImpossibleKeys = [{KeyPos, KeyValue} || {KeyPos, KeyValue} <- SeachKeys, KeyPos <
Pos],
+    
+    SrcKeys2 = PossibleKeys -- [{Pos, Key}],
+    SrcKeys3 = find_missing_simple(Pos + 1, SubTree, SrcKeys2),
+    ImpossibleKeys ++ find_missing_simple(Pos, RestTree, SrcKeys3).
+
+
+get_all_key_paths_reverse_simple(Pos, [], KeyPathAcc) ->
+    [{Pos - 1, KeyPathAcc}];
+get_all_key_paths_reverse_simple(Pos, [{Key, Value, SubTree} | RestTree], KeyPathAcc) ->
+    SubLists = get_all_key_paths_reverse_simple(Pos + 1, SubTree, [{Key, Value} | KeyPathAcc]),
+    SiblingLists =
+        if RestTree /= [] ->
+            get_all_key_paths_reverse_simple(Pos, RestTree, KeyPathAcc);
+        true ->
+            []
+        end,
+    SiblingLists ++ SubLists.
+
+get_all_key_paths_reverse([], PathsAcc) ->
+    PathsAcc;
+get_all_key_paths_reverse([{Start, Tree}|Rest], PathsAcc) ->
+    get_all_key_paths_reverse(Rest, get_all_key_paths_reverse_simple(Start, [Tree], []) ++
PathsAcc).
+
+
+filter_leafs([], _Keys, FilteredAcc, RemovedKeysAcc) ->
+    {FilteredAcc, RemovedKeysAcc};
+filter_leafs([{Pos, [{LeafKey, _}|_]} = Path |Rest], Keys, FilteredAcc, RemovedKeysAcc) ->
+    FilteredKeys = lists:delete({Pos, LeafKey}, Keys),
+    if FilteredKeys == Keys ->
+        % this leaf is not a key we are looking to remove
+        filter_leafs(Rest, Keys, [Path | FilteredAcc], RemovedKeysAcc);
+    true ->
+        % this did match a key, remove both the node and the input key
+        filter_leafs(Rest, FilteredKeys, FilteredAcc, [{Pos, LeafKey} | RemovedKeysAcc])
+    end.
     
 % Removes any branches from the tree whose leaf node(s) are in the Keys
-remove_leafs(Tree, Keys) ->
+remove_leafs(Trees, Keys) ->
     % flatten each branch in a tree into a tree path
-    Paths = get_all_key_paths_rev(Tree, []),
+    Paths = get_all_key_paths_reverse(make_canonical(Trees), []),
     
     % filter out any that are in the keys list.
-    {FoundKeys, FilteredPaths} = lists:mapfoldl(
-        fun(Key, PathsAcc) ->
-            case [Path || [{LeafKey,_}|_]=Path <- PathsAcc, LeafKey /= Key] of
-            PathsAcc ->
-                {nil, PathsAcc};
-            PathsAcc2 ->
-                {Key, PathsAcc2}
-            end
-        end, Paths, Keys),
-        
+    {FilteredPaths, RemovedKeys} = filter_leafs(Paths, Keys, [], []),
+            
     % convert paths back to trees
     NewTree = lists:foldl(
-        fun(Path,TreeAcc) ->
-            SingleTree = lists:foldl(
+        fun({PathPos, Path},TreeAcc) ->
+            [SingleTree] = lists:foldl(
                 fun({K,V},NewTreeAcc) -> [{K,V,NewTreeAcc}] end, [], Path),
-            merge(TreeAcc, SingleTree)
+            {NewTrees, _} = merge(TreeAcc, [{PathPos + 1 - length(Path), SingleTree}]),
+            NewTrees
         end, [], FilteredPaths),
-    {NewTree, FoundKeys}.
+    {NewTree, RemovedKeys}.
 
 
 % get the leafs in the tree matching the keys. The matching key nodes can be
@@ -94,87 +201,195 @@
 get_key_leafs(Tree, Keys) ->
     get_key_leafs(Tree, Keys, []).
     
-get_key_leafs(_Tree, [], _KeyPathAcc) ->
+get_key_leafs(_, [], Acc) ->
+    {Acc, []};
+get_key_leafs([], Keys, Acc) ->
+    {Acc, Keys};
+get_key_leafs([{Pos, Tree}|Rest], Keys, Acc) ->
+    {Gotten, RemainingKeys} = get_key_leafs_simple(Pos, [Tree], Keys, []),
+    get_key_leafs(Rest, RemainingKeys, Gotten ++ Acc).
+        
+get_key_leafs_simple(_Pos, _Tree, [], _KeyPathAcc) ->
     {[], []};
-get_key_leafs([], KeysToGet, _KeyPathAcc) ->
+get_key_leafs_simple(_Pos, [], KeysToGet, _KeyPathAcc) ->
     {[], KeysToGet};
-get_key_leafs([{Key, _Value, SubTree}=Tree | RestTree], KeysToGet, KeyPathAcc) ->
-    case KeysToGet -- [Key] of
+get_key_leafs_simple(Pos, [{Key, _Value, SubTree}=Tree | RestTree], KeysToGet, KeyPathAcc)
->
+    case lists:delete({Pos, Key}, KeysToGet) of
     KeysToGet -> % same list, key not found    
-        {LeafsFound, KeysToGet2} = get_key_leafs(SubTree, KeysToGet, [Key | KeyPathAcc]),
-        {RestLeafsFound, KeysRemaining} = get_key_leafs(RestTree, KeysToGet2, KeyPathAcc),
+        {LeafsFound, KeysToGet2} = get_key_leafs_simple(Pos + 1, SubTree, KeysToGet, [Key
| KeyPathAcc]),
+        {RestLeafsFound, KeysRemaining} = get_key_leafs_simple(Pos, RestTree, KeysToGet2,
KeyPathAcc),
         {LeafsFound ++ RestLeafsFound, KeysRemaining};
     KeysToGet2 ->
-        LeafsFound = get_all_leafs([Tree], KeyPathAcc),
+        LeafsFound = get_all_leafs_simple(Pos, [Tree], KeyPathAcc),
         LeafKeysFound = [LeafKeyFound || {LeafKeyFound, _, _} <- LeafsFound],
         KeysToGet2 = KeysToGet2 -- LeafKeysFound,
-        {RestLeafsFound, KeysRemaining} = get_key_leafs(RestTree, KeysToGet2, KeyPathAcc),
+        {RestLeafsFound, KeysRemaining} = get_key_leafs_simple(Pos, RestTree, KeysToGet2,
KeyPathAcc),
         {LeafsFound ++ RestLeafsFound, KeysRemaining}
     end.
 
 get(Tree, KeysToGet) ->
     {KeyPaths, KeysNotFound} = get_full_key_paths(Tree, KeysToGet),
-    FixedResults = [ {Key, Value, [Key0 || {Key0, _} <- Path]} || [{Key, Value}|_] = Path
<- KeyPaths],
+    FixedResults = [ {Value, {Pos, [Key0 || {Key0, _} <- Path]}} || {Pos, [{_Key, Value}|_]=Path}
<- KeyPaths],
     {FixedResults, KeysNotFound}.
     
 get_full_key_paths(Tree, Keys) ->
     get_full_key_paths(Tree, Keys, []).
     
-get_full_key_paths(_Tree, [], _KeyPathAcc) ->
+get_full_key_paths(_, [], Acc) ->
+    {Acc, []};
+get_full_key_paths([], Keys, Acc) ->
+    {Acc, Keys};
+get_full_key_paths([{Pos, Tree}|Rest], Keys, Acc) ->
+    {Gotten, RemainingKeys} = get_full_key_paths(Pos, [Tree], Keys, []),
+    get_full_key_paths(Rest, RemainingKeys, Gotten ++ Acc).
+    
+    
+get_full_key_paths(_Pos, _Tree, [], _KeyPathAcc) ->
     {[], []};
-get_full_key_paths([], KeysToGet, _KeyPathAcc) ->
+get_full_key_paths(_Pos, [], KeysToGet, _KeyPathAcc) ->
     {[], KeysToGet};
-get_full_key_paths([{KeyId, Value, SubTree} | RestTree], KeysToGet, KeyPathAcc) ->
-    KeysToGet2 = KeysToGet -- [KeyId],
+get_full_key_paths(Pos, [{KeyId, Value, SubTree} | RestTree], KeysToGet, KeyPathAcc) ->
+    KeysToGet2 = KeysToGet -- [{Pos, KeyId}],
     CurrentNodeResult =
     case length(KeysToGet2) == length(KeysToGet) of
     true -> % not in the key list.
         [];
     false -> % this node is the key list. return it
-        [[{KeyId, Value} | KeyPathAcc]]
+        [{Pos, [{KeyId, Value} | KeyPathAcc]}]
     end,
-    {KeysGotten, KeysRemaining} = get_full_key_paths(SubTree, KeysToGet2, [{KeyId, Value}
| KeyPathAcc]),
-    {KeysGotten2, KeysRemaining2} = get_full_key_paths(RestTree, KeysRemaining, KeyPathAcc),
+    {KeysGotten, KeysRemaining} = get_full_key_paths(Pos + 1, SubTree, KeysToGet2, [{KeyId,
Value} | KeyPathAcc]),
+    {KeysGotten2, KeysRemaining2} = get_full_key_paths(Pos, RestTree, KeysRemaining, KeyPathAcc),
     {CurrentNodeResult ++ KeysGotten ++ KeysGotten2, KeysRemaining2}.
 
 get_all_leafs_full(Tree) ->
     get_all_leafs_full(Tree, []).
     
-get_all_leafs_full([], _KeyPathAcc) ->
+get_all_leafs_full([], Acc) ->
+    Acc;
+get_all_leafs_full([{Pos, Tree} | Rest], Acc) ->
+    get_all_leafs_full(Rest, get_all_leafs_full_simple(Pos, [Tree], []) ++ Acc).
+    
+get_all_leafs_full_simple(_Pos, [], _KeyPathAcc) ->
     [];
-get_all_leafs_full([{KeyId, Value, []} | RestTree], KeyPathAcc) ->
-    [[{KeyId, Value} | KeyPathAcc] | get_all_leafs_full(RestTree, KeyPathAcc)];
-get_all_leafs_full([{KeyId, Value, SubTree} | RestTree], KeyPathAcc) ->
-    get_all_leafs_full(SubTree, [{KeyId, Value} | KeyPathAcc]) ++ get_all_leafs_full(RestTree,
KeyPathAcc).
-
-get_all_leafs(Tree) ->
-    get_all_leafs(Tree, []).
+get_all_leafs_full_simple(Pos, [{KeyId, Value, []} | RestTree], KeyPathAcc) ->
+    [{Pos, [{KeyId, Value} | KeyPathAcc]} | get_all_leafs_full_simple(Pos, RestTree, KeyPathAcc)];
+get_all_leafs_full_simple(Pos, [{KeyId, Value, SubTree} | RestTree], KeyPathAcc) ->
+    get_all_leafs_full_simple(Pos + 1, SubTree, [{KeyId, Value} | KeyPathAcc]) ++ get_all_leafs_full_simple(Pos,
RestTree, KeyPathAcc).
+
+get_all_leafs(Trees) ->
+    get_all_leafs(Trees, []).
+
+get_all_leafs([], Acc) ->
+    Acc;
+get_all_leafs([{Pos, Tree}|Rest], Acc) ->
+    get_all_leafs(Rest, get_all_leafs_simple(Pos, [Tree], []) ++ Acc).
     
-get_all_leafs([], _KeyPathAcc) ->
+get_all_leafs_simple(_Pos, [], _KeyPathAcc) ->
     [];
-get_all_leafs([{KeyId, Value, []} | RestTree], KeyPathAcc) ->
-    [{KeyId, Value, [KeyId | KeyPathAcc]} | get_all_leafs(RestTree, KeyPathAcc)];
-get_all_leafs([{KeyId, _Value, SubTree} | RestTree], KeyPathAcc) ->
-    get_all_leafs(SubTree, [KeyId | KeyPathAcc]) ++ get_all_leafs(RestTree, KeyPathAcc).
+get_all_leafs_simple(Pos, [{KeyId, Value, []} | RestTree], KeyPathAcc) ->
+    [{Value, {Pos, [KeyId | KeyPathAcc]}} | get_all_leafs_simple(Pos, RestTree, KeyPathAcc)];
+get_all_leafs_simple(Pos, [{KeyId, _Value, SubTree} | RestTree], KeyPathAcc) ->
+    get_all_leafs_simple(Pos + 1, SubTree, [KeyId | KeyPathAcc]) ++ get_all_leafs_simple(Pos,
RestTree, KeyPathAcc).
+
 
-get_leaf_keys([]) ->
-    [];
-get_leaf_keys([{Key, _Value, []} | RestTree]) ->
-    [Key | get_leaf_keys(RestTree)];
-get_leaf_keys([{_Key, _Value, SubTree} | RestTree]) ->
-    get_leaf_keys(SubTree) ++ get_leaf_keys(RestTree).
-    
 count_leafs([]) ->
     0;
-count_leafs([{_Key, _Value, []} | RestTree]) ->
-    1 + count_leafs(RestTree);
-count_leafs([{_Key, _Value, SubTree} | RestTree]) ->
-    count_leafs(SubTree) + count_leafs(RestTree).
+count_leafs([{_Pos,Tree}|Rest]) ->
+    count_leafs_simple([Tree]) + count_leafs(Rest).
     
+count_leafs_simple([]) ->
+    0;
+count_leafs_simple([{_Key, _Value, []} | RestTree]) ->
+    1 + count_leafs_simple(RestTree);
+count_leafs_simple([{_Key, _Value, SubTree} | RestTree]) ->
+    count_leafs_simple(SubTree) + count_leafs_simple(RestTree).
 
+    
 map(_Fun, []) ->
     [];
-map(Fun, [{Key, Value, SubTree} | RestTree]) ->
-    Value2 = Fun(Key, Value),
-    [{Key, Value2, map(Fun, SubTree)} | map(Fun, RestTree)].
+map(Fun, [{Pos, Tree}|Rest]) ->
+    [NewTree] = map_simple(Fun, Pos, [Tree]),
+    [{Pos, NewTree} | map(Fun, Rest)].
+
+map_simple(_Fun, _Pos, []) ->
+    [];
+map_simple(Fun, Pos, [{Key, Value, SubTree} | RestTree]) ->
+    Value2 = Fun({Pos, Key}, Value),
+    [{Key, Value2, map_simple(Fun, Pos + 1, SubTree)} | map_simple(Fun, Pos, RestTree)].
+
 
+
+test() ->
+    EmptyTree = [],
+    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", []}]}}],
+    Stemmed1a = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
+    Stemmed1aa = [{2, {"1aa", "bar", []}}],
+    
+    {EmptyTree, no_conflicts} = merge(EmptyTree, EmptyTree),
+    {One, no_conflicts} = merge(EmptyTree, One),
+    {One, no_conflicts} = merge(One, EmptyTree),
+    {TwoSibs, no_conflicts} = merge(One, TwoSibs),
+    {One, no_conflicts} = merge(One, One),
+    {TwoChild, no_conflicts} = merge(TwoChild, TwoChild),
+    {TwoChildSibs, no_conflicts} = merge(TwoChildSibs, TwoChildSibs),
+    {TwoChild, no_conflicts} = merge(TwoChild, Stemmed1aa),
+    {TwoChild, no_conflicts} = merge(TwoChild, Stemmed1a),
+    {Stemmed1a, no_conflicts} = merge(Stemmed1a, Stemmed1aa),
+    Expect1 = OneChild ++ Stemmed1aa,
+    {Expect1, conflicts} = merge(OneChild, Stemmed1aa),
+    {TwoChild, no_conflicts} = merge(Expect1, TwoChild),
+    
+    []=find_missing(TwoChildSibs, [{0,"1"}, {1,"1a"}]),
+    [{0, "10"}, {100, "x"}]=find_missing(TwoChildSibs, [{0,"1"}, {0, "10"}, {1,"1a"}, {100,
"x"}]),
+    [{0, "1"}, {100, "x"}]=find_missing(Stemmed1a, [{0,"1"}, {1,"1a"}, {100, "x"}]),
+    [{0, "1"}, {1,"1a"}, {100, "x"}]=find_missing(Stemmed1aa, [{0,"1"}, {1,"1a"}, {100, "x"}]),
+    
+    {TwoChildSibs, []} = remove_leafs(TwoChildSibs, []),
+    {TwoChildSibs, []} = remove_leafs(TwoChildSibs, [{0, "1"}]),
+    {OneChild, [{1, "1b"}]} = remove_leafs(TwoChildSibs, [{1, "1b"}]),
+    {[], [{1, "1a"},{1, "1b"}]} = remove_leafs(TwoChildSibs, [{1, "1a"}, {1, "1b"}]),
+    {Stemmed1a, []} = remove_leafs(Stemmed1a, [{1, "1a"}]),
+    {[], [{2, "1aa"}]} = remove_leafs(Stemmed1a, [{2, "1aa"}]),
+    {TwoChildSibs, []} = remove_leafs(TwoChildSibs, []),
+    
+    {[],[{0,"x"}]} = get_key_leafs(TwoChildSibs, [{0, "x"}]),
+    
+    {[{"bar", {1, ["1a","1"]}}],[]} = get_key_leafs(TwoChildSibs, [{1, "1a"}]),
+    {[{"bar", {1, ["1a","1"]}},{"bar",{1, ["1b","1"]}}],[]} = get_key_leafs(TwoChildSibs,
[{0, "1"}]),
+    
+    {[{"foo", {0, ["1"]}}],[]} = get(TwoChildSibs, [{0, "1"}]),
+    {[{"bar", {1, ["1a", "1"]}}],[]} = get(TwoChildSibs, [{1, "1a"}]),
+
+    {[{0,[{"1", "foo"}]}],[]} = get_full_key_paths(TwoChildSibs, [{0, "1"}]),
+    {[{1,[{"1a", "bar"},{"1", "foo"}]}],[]} = get_full_key_paths(TwoChildSibs, [{1, "1a"}]),
+    
+    [{2, [{"1aa", "bar"},{"1a", "bar"}]}] = get_all_leafs_full(Stemmed1a),
+    [{1, [{"1a", "bar"},{"1", "foo"}]}, {1, [{"1b", "bar"},{"1", "foo"}]}] = get_all_leafs_full(TwoChildSibs),
+    
+    [{"bar", {2, ["1aa","1a"]}}] = get_all_leafs(Stemmed1a),
+    [{"bar", {1, ["1a", "1"]}}, {"bar", {1, ["1b","1"]}}] = get_all_leafs(TwoChildSibs),
+    
+    0 = count_leafs(EmptyTree),
+    1 = count_leafs(One),
+    2 = count_leafs(TwoChildSibs),
+    1 = count_leafs(Stemmed1a),
+    
+    
+    ok.
+    
+    
+    
+    
+    
+    
+    
+    
+    
+    
+    
\ No newline at end of file

Modified: couchdb/branches/rep_security/src/couchdb/couch_rep.erl
URL: http://svn.apache.org/viewvc/couchdb/branches/rep_security/src/couchdb/couch_rep.erl?rev=741844&r1=741842&r2=741844&view=diff
==============================================================================
--- couchdb/branches/rep_security/src/couchdb/couch_rep.erl (original)
+++ couchdb/branches/rep_security/src/couchdb/couch_rep.erl Sat Feb  7 05:23:02 2009
@@ -71,8 +71,11 @@
     
     ReplicationStartTime = httpd_util:rfc1123_date(),
     
-    {ok, SrcInstanceStartTime} = get_db_info(DbSrc),
-    {ok, TgtInstanceStartTime} = get_db_info(DbTgt),
+    {ok, InfoSrc} = get_db_info(DbSrc),
+    {ok, InfoTgt} = get_db_info(DbTgt),
+    
+    SrcInstanceStartTime = proplists:get_value(instance_start_time, InfoSrc),
+    TgtInstanceStartTime = proplists:get_value(instance_start_time, InfoTgt),
     
     case proplists:get_value(full, Options, false)
         orelse proplists:get_value("full", Options, false) of
@@ -125,7 +128,6 @@
         
         {ok, SrcInstanceStartTime2} = ensure_full_commit(DbSrc),
         {ok, TgtInstanceStartTime2} = ensure_full_commit(DbTgt),
-        
         RecordSeqNum =
         if SrcInstanceStartTime2 == SrcInstanceStartTime andalso
                 TgtInstanceStartTime2 == TgtInstanceStartTime ->
@@ -210,7 +212,7 @@
 save_docs_buffer(DbTarget, DocsBuffer, []) ->
     receive
     {Src, shutdown} ->
-        ok = update_docs(DbTarget, lists:reverse(DocsBuffer), [], false),
+        ok = update_docs(DbTarget, lists:reverse(DocsBuffer), [], replicated_changes),
         Src ! {done, self(), [{<<"docs_written">>, length(DocsBuffer)}]}
     end;
 save_docs_buffer(DbTarget, DocsBuffer, UpdateSequences) ->
@@ -224,14 +226,14 @@
         case couch_util:should_flush() of
             true ->
                 ok = update_docs(DbTarget, lists:reverse(Docs++DocsBuffer), [], 
-                    false),
+                    replicated_changes),
                 save_docs_buffer(DbTarget, [], Rest);
             false ->
                 save_docs_buffer(DbTarget, Docs++DocsBuffer, Rest)
         end;
         {Src, shutdown} ->
         ?LOG_ERROR("received shutdown while waiting for more update_seqs", []),
-        ok = update_docs(DbTarget, lists:reverse(DocsBuffer), [], false),
+        ok = update_docs(DbTarget, lists:reverse(DocsBuffer), [], replicated_changes),
         Src ! {done, self(), [{<<"docs_written">>, length(DocsBuffer)}]}
     end.
 
@@ -338,12 +340,12 @@
         {RowValueProps} = proplists:get_value(<<"value">>, RowInfoList),
         #doc_info{
             id=proplists:get_value(<<"id">>, RowInfoList),
-            rev=proplists:get_value(<<"rev">>, RowValueProps),
+            rev=couch_doc:parse_rev(proplists:get_value(<<"rev">>, RowValueProps)),
             update_seq = proplists:get_value(<<"key">>, RowInfoList),
             conflict_revs =
-                proplists:get_value(<<"conflicts">>, RowValueProps, []),
+                couch_doc:parse_revs(proplists:get_value(<<"conflicts">>, RowValueProps,
[])),
             deleted_conflict_revs =
-                proplists:get_value(<<"deleted_conflicts">>, RowValueProps, []),
+                couch_doc:parse_revs(proplists:get_value(<<"deleted_conflicts">>,
RowValueProps, [])),
             deleted = proplists:get_value(<<"deleted">>, RowValueProps, false)
         }
     end, proplists:get_value(<<"rows">>, Results));
@@ -399,10 +401,12 @@
     end.
 
 get_missing_revs(#http_db{uri=DbUrl, headers=Headers}, DocIdRevsList) ->
+    DocIdRevsList2 = [{Id, couch_doc:to_rev_strs(Revs)} || {Id, Revs} <- DocIdRevsList],
     {ResponseMembers} = do_http_request(DbUrl ++ "_missing_revs", post, Headers,
-            {DocIdRevsList}),
+            {DocIdRevsList2}),
     {DocMissingRevsList} = proplists:get_value(<<"missing_revs">>, ResponseMembers),
-    {ok, DocMissingRevsList};
+    DocMissingRevsList2 = [{Id, couch_doc:parse_revs(MissingRevStrs)} || {Id, MissingRevStrs}
<- DocMissingRevsList],
+    {ok, DocMissingRevsList2};
 get_missing_revs(Db, DocId) ->
     couch_db:get_missing_revs(Db, DocId).
 
@@ -412,22 +416,23 @@
     Url = DbUrl ++ url_encode(DocId),
     {ResponseMembers} = do_http_request(Url, put, Headers,
             couch_doc:to_json_obj(Doc, [revs,attachments])),
-    RevId = proplists:get_value(<<"_rev">>, ResponseMembers),
-    {ok, RevId};
+    Rev = proplists:get_value(<<"rev">>, ResponseMembers),
+    {ok, couch_doc:parse_rev(Rev)};
 update_doc(Db, Doc, Options) ->
     couch_db:update_doc(Db, Doc, Options).
 
 update_docs(_, [], _, _) ->
     ok;
-update_docs(#http_db{uri=DbUrl, headers=Headers}, Docs, [], NewEdits) ->
+update_docs(#http_db{uri=DbUrl, headers=Headers}, Docs, [], UpdateType) ->
+    NewEdits = UpdateType == interactive_edit,
     JsonDocs = [couch_doc:to_json_obj(Doc, [revs,attachments]) || Doc <- Docs],
     {Returned} =
         do_http_request(DbUrl ++ "_bulk_docs", post, Headers,
                 {[{new_edits, NewEdits}, {docs, JsonDocs}]}),
     true = proplists:get_value(<<"ok">>, Returned),
     ok;
-update_docs(Db, Docs, Options, NewEdits) ->
-    couch_db:update_docs(Db, Docs, Options, NewEdits).
+update_docs(Db, Docs, Options, UpdateType) ->
+    couch_db:update_docs(Db, Docs, Options, UpdateType).
 
 
 open_doc(#http_db{uri=DbUrl, headers=Headers}, DocId, Options) ->
@@ -442,7 +447,8 @@
     couch_db:open_doc(Db, DocId, Options).
 
 
-open_doc_revs(#http_db{uri=DbUrl, headers=Headers}, DocId, Revs, Options) ->
+open_doc_revs(#http_db{uri=DbUrl, headers=Headers}, DocId, Revs0, Options) ->
+    Revs = couch_doc:to_rev_strs(Revs0),
     QueryOptionStrs =
     lists:map(fun(latest) ->
             % latest is only option right now
@@ -475,7 +481,7 @@
     Results =
     lists:map(
         fun({[{<<"missing">>, Rev}]}) ->
-            {{not_found, missing}, Rev};
+            {{not_found, missing}, couch_doc:parse_rev(Rev)};
         ({[{<<"ok">>, JsonDoc}]}) ->
             {ok, couch_doc:from_json_obj(JsonDoc)}
         end, JsonResults),



Mime
View raw message