This is an automated email from the ASF dual-hosted git repository.

nickva pushed a commit to branch repair-tree-fold-first
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit ae208a411f10a2ad54754ad36b5bc9237bf3c5ff
Author: Nick Vatamaniuc <[email protected]>
AuthorDate: Mon Oct 26 16:38:04 2026 -0400

    Collapse duplicate revs before stemming
    
    When we get duplicates in the rev tree stemming repairs the tree by 
rebuilding
    it from paths. Repair used to apply the revs_limit first, and then mergedthe
    fragments. If the duplicates were far enough appart from each other (source 
dbs
    with different revs_limits were pushing to a target) the fragments might 
not be
    fold and the shorter one could stay around as an extra leaf. Since #6168 it
    would be even worse since a leaf could end up with nothing stored for it, 
which
    would be a broken rev tree. So instead we should fold the paths first then 
stem
    the result.
    
    This was noticed when fixing the property tests to avoid discarding so many
    generating cases and in this case we never actually tested this 
multi-fragment
    merge scenario. Move to use numbers for revisions so we don't have to 
generate
    random revs then reject them with ?IMPLIES any longer. Also increase the 
number
    of runs to 500 from a default of 100.
    
    Issue: #6170
---
 src/couch/src/couch_key_tree.erl                   |  15 +-
 src/couch/test/eunit/couch_key_tree_prop_tests.erl | 235 ++++++++++++++-------
 2 files changed, 173 insertions(+), 77 deletions(-)

diff --git a/src/couch/src/couch_key_tree.erl b/src/couch/src/couch_key_tree.erl
index 6a3dffc04..901f58429 100644
--- a/src/couch/src/couch_key_tree.erl
+++ b/src/couch/src/couch_key_tree.erl
@@ -546,14 +546,20 @@ check_key(Key, Seen) ->
     end.
 
 repair_tree(Trees, Limit) ->
+    % Handle duplicates first with their full paths then stem. If we stem we
+    % could cut off duplicates from descendentsand end up with extra leafs
+    FullPaths = merge_paths(get_all_leafs_full(Trees), infinity),
+    merge_paths(get_all_leafs_full(FullPaths), Limit).
+
+merge_paths(LeafPaths, Limit) ->
     % flatten each branch in a tree into a tree path, sort by starting rev #
     Paths = lists:sort(
         lists:map(
             fun({Pos, Path}) ->
-                StemmedPath = lists:sublist(Path, Limit),
+                StemmedPath = stem_path(Path, Limit),
                 {Pos + 1 - length(StemmedPath), StemmedPath}
             end,
-            get_all_leafs_full(Trees)
+            LeafPaths
         )
     ),
 
@@ -570,6 +576,11 @@ repair_tree(Trees, Limit) ->
         Paths
     ).
 
+stem_path(Path, infinity) ->
+    Path;
+stem_path(Path, Limit) ->
+    lists:sublist(Path, Limit).
+
 value_pref(Tuple, _) when
     is_tuple(Tuple),
     (tuple_size(Tuple) == 3 orelse tuple_size(Tuple) == 4)
diff --git a/src/couch/test/eunit/couch_key_tree_prop_tests.erl 
b/src/couch/test/eunit/couch_key_tree_prop_tests.erl
index d6ed26553..4ed1a9543 100644
--- a/src/couch/test/eunit/couch_key_tree_prop_tests.erl
+++ b/src/couch/test/eunit/couch_key_tree_prop_tests.erl
@@ -15,6 +15,7 @@
 -ifdef(WITH_PROPER).
 
 -include_lib("couch/include/couch_eunit_proper.hrl").
+-include_lib("couch/include/couch_db.hrl").
 
 % How much to reduce size with tree depth.
 -define(SIZE_REDUCTION, 3).
@@ -23,70 +24,53 @@
 -define(RAND_SIZE, 1 bsl 64).
 
 property_test_() ->
-    ?EUNIT_QUICKCHECK(60).
+    ?EUNIT_QUICKCHECK(120, 500).
 
 %
 % Properties
 %
 
+
 % Merge random paths from a revtree into itself. Check that no revisions have
-% been lost in the process and that result is one of the 3 expected values.
+% been lost in the process and that result we never create new leafs or
+% branches.
 %
 prop_revtree_merge_with_subset_of_own_nodes() ->
     ?FORALL(
-        Revs,
-        g_revs(),
-        ?FORALL(
-            {RevTree, Branch},
-            {g_revtree(Revs), g_revtree(Revs, 1)},
-            ?IMPLIES(
-                length(Branch) > 0 andalso repeating_revs(levels(RevTree ++ 
Branch)) == [],
-                begin
-                    {Merged, Result} = couch_key_tree:merge(RevTree, 
hd(Branch)),
-                    lists:member(Result, [new_leaf, new_branch, 
internal_node]) andalso
-                        same_keys(RevTree ++ Branch, Merged) andalso
-                        valid_revtree(Merged)
-                end
-            )
-        )
+        {RevTree, Start, Revs},
+        g_revtree_with_path(),
+        begin
+            {Merged, Result} = couch_key_tree:merge(RevTree, path(Start, 
Revs)),
+            Result == internal_node andalso Merged == RevTree
+        end
     ).
 
 % Merge random trees into revtree.
 %
 prop_revtree_merge_random_nodes() ->
     ?FORALL(
-        {RevTree, Branch},
-        {g_revtree(), g_revtree([], 1)},
-        ?IMPLIES(
-            length(Branch) > 0,
-            begin
-                {Merged, _} = couch_key_tree:merge(RevTree, hd(Branch)),
-                valid_revtree(Merged)
-            end
-        )
+        {RevTree, [Path]},
+        {g_revtree(), g_path(1, 20)},
+        begin
+            {Merged, _} = couch_key_tree:merge(RevTree, Path),
+            valid_revtree(Merged)
+        end
     ).
 
-% Merge mix or random and existing revtree paths into revtree
+% Extend rev tree with new revisions. Expect to not lose anything and get
+% either new leafs or branches.
 %
 prop_revtree_merge_some_existing_some_new() ->
     ?FORALL(
-        RevTree,
-        g_revtree(),
-        ?FORALL(
-            Branch,
-            begin
-                KeyList = keylist(RevTree),
-                Half = lists:sublist(KeyList, length(KeyList) div 2),
-                g_revtree(Half, 1)
-            end,
-            ?IMPLIES(
-                length(Branch) > 0 andalso repeating_revs(levels(RevTree ++ 
Branch)) == [],
-                begin
-                    {Merged, _} = couch_key_tree:merge(RevTree, hd(Branch)),
-                    valid_revtree(Merged)
-                end
-            )
-        )
+        {{RevTree, Start, Revs}, NewRevs},
+        {g_revtree_with_path(), ?LET(N, choose(1, 5), rand_list(N))},
+        begin
+            Path = path(Start, Revs ++ [{Rev, x} || Rev <- NewRevs]),
+            {Merged, Result} = couch_key_tree:merge(RevTree, Path),
+            lists:member(Result, [new_leaf, new_branch]) andalso
+                same_keys(RevTree ++ [Path], Merged) andalso
+                valid_revtree(Merged)
+        end
     ).
 
 % Stem deeper than the current max level. Expect no changes to the revtree
@@ -129,20 +113,14 @@ prop_stemming_results_in_same_or_less_total_revs() ->
 prop_stem_path_expect_size_to_get_smaller() ->
     ?FORALL(
         {RevTree, StemDepth},
-        {
-            ?SIZED(Size, g_revtree(Size * 10, [], 1)),
-            choose(1, 3)
-        },
-        ?IMPLIES(
-            real_depth(RevTree) > 3,
-            begin
-                Stemmed = couch_key_tree:stem(RevTree, StemDepth),
-                StemmedKeys = lists:usort(keylist(Stemmed)),
-                InputKeys = lists:usort(keylist(RevTree)),
-                length(InputKeys) > length(StemmedKeys) andalso
-                    real_depth(Stemmed) == StemDepth
-            end
-        )
+        {g_path(4, 30), choose(1, 3)},
+        begin
+            Stemmed = couch_key_tree:stem(RevTree, StemDepth),
+            StemmedKeys = lists:usort(keylist(Stemmed)),
+            InputKeys = lists:usort(keylist(RevTree)),
+            length(InputKeys) > length(StemmedKeys) andalso
+                real_depth(Stemmed) == StemDepth
+        end
     ).
 
 % After stemming all leaves are still present
@@ -207,26 +185,40 @@ prop_get_leafs() ->
         end
     ).
 
+% We could get revision history as two fragments 1..N and then S..T with a gap
+% in between (say if we have sources with different revs_limit values). Then if
+% also get a full path from another source, then the first two fragments could
+% connect and collapse into a single path. After merging and stemming we'd like
+% to still assert these properties:
+%  - every leaf has a value (no REV_MISSING in a leaf)
+%  - the only leaf should be the one from the full path connected path
+%
+prop_stem_connect_fragments() ->
+    ?FORALL(
+        {RevTree, Tip, Leaf},
+        g_fragments(),
+        begin
+            Cases = [{V, D} || V <- [stored, new], D <- lists:seq(1, Leaf + 
1)],
+            Failed = [C || C <- Cases, not connect_fragments(RevTree, Tip, 
Leaf, C)],
+            ?WHENFAIL(
+                io:format("failed for {Val, Depth}: ~p~n", [Failed]),
+                Failed == []
+            )
+        end
+    ).
+
 %
 % Generators
 %
 
-% Generate a full rev tree. Most of the forms are just there to set up default
-% parameters, _revtree/3 does all heavy lifting.
+% Generate a full rev tree. g_revtree/3 does all the heavy lifting.
 %
 
 g_revtree() ->
     ?SIZED(Size, g_revtree(Size)).
 
-g_revtree(Size) when is_integer(Size) ->
-    g_revtree(Size, [], ?MAX_BRANCHES);
-g_revtree(Revs) when is_list(Revs) ->
-    ?SIZED(Size, g_revtree(Size, Revs, ?MAX_BRANCHES)).
-
-g_revtree(Size, Revs) when is_integer(Size), is_list(Revs) ->
-    g_revtree(Size, Revs, ?MAX_BRANCHES);
-g_revtree(Revs, MaxBranches) when is_list(Revs), is_integer(MaxBranches) ->
-    ?SIZED(Size, g_revtree(Size, Revs, MaxBranches)).
+g_revtree(Size) ->
+    g_revtree(Size, [], ?MAX_BRANCHES).
 
 g_revtree(0, _Revs, _MaxBranches) ->
     [];
@@ -270,6 +262,64 @@ g_nodes(Size, ChildCount, Revs, MaxBranches) ->
         ordered_nodes(ChildNodes)
     ).
 
+% Generate a revtree and the history of one of its revisions: the start
+% position and the root-first [{Rev, Value}] list of the path from the root of
+% the revision's branch down to it.
+%
+g_revtree_with_path() ->
+    ?LET(
+        RevTree,
+        g_revtree(),
+        ?LET(
+            {{LeafPos, LeafPath}, Drop},
+            ?LET(
+                LP,
+                elements(couch_key_tree:get_all_leafs_full(RevTree)),
+                {LP, choose(0, length(element(2, LP)) - 1)}
+            ),
+            {RevTree, LeafPos - length(LeafPath) + 1, 
lists:reverse(lists:nthtail(Drop, LeafPath))}
+        )
+    ).
+
+% Generate a path (revtree with no branches) of a given depth range
+%
+g_path(MinDepth, MaxDepth) ->
+    ?LET(
+        {Depth, Start},
+        {choose(MinDepth, MaxDepth), choose(1, 5)},
+        [path(Start, revs(Depth, []), x)]
+    ).
+
+% Generate the two fragments of length N1 (1..N1) and length N2 (S...T) from a
+% rev history with a gap in between.
+%
+% Fragment1:  1 .. N1
+% Fragment2:          S=N1+Gap+1 .. T=S+N2-1
+%
+% For example:
+%  [
+%          {1, [1,2]},
+%          {5,        [5,6,7]}
+%  ]
+% N1=2, N2=3. S=5, T=7, gap=2 (where 3 and 4 are)
+%
+% Also return the revision in the second fragment that we be used for sending
+% as the full path which should end up merging the fragments into one path.
+%
+g_fragments() ->
+    ?LET(
+        {N1, Gap, N2, TipOffset},
+        {choose(1, 4), choose(0, 3), choose(1, 5), choose(0, 4)},
+        begin
+            S = N1 + Gap + 1,
+            T = S + N2 - 1,
+            Fragment1 = path(1, lists:seq(1, N1), x),
+            Fragment2 = path(S, lists:seq(S, T), x),
+            RevTree = [Fragment1, Fragment2],
+            {RevTree, S + min(TipOffset, N2 - 1), T}
+        end
+    ).
+
 % Generate each subtree's stem depth
 %
 
@@ -296,12 +346,6 @@ g_shuffled_sublists(L, N) ->
 
 % Generate revision lists.
 %
-g_revs() ->
-    ?SIZED(Size, g_revs(Size)).
-
-g_revs(Size) when is_integer(Size) ->
-    g_revs(Size, []).
-
 g_revs(Size, Existing) when is_integer(Size), is_list(Existing) ->
     Expected = keys_needed(Size, ?SIZE_REDUCTION, ?MAX_BRANCHES),
     Revs = revs(Expected, Existing),
@@ -344,6 +388,47 @@ revs(Expected, Existing) when is_integer(Expected), 
is_list(Existing) ->
     Need = Expected - length(Existing),
     lists:usort(lists:append(Existing, rand_list(Need))).
 
+% Build a path starting at position Start from a [{rev,val}] position list with
+% root value first.
+%
+path(Start, RevVals) ->
+    [{Leaf, LeafValue} | Ancestors] = lists:reverse(RevVals),
+    Node = lists:foldl(
+        fun({R, V}, Child) -> {R, V, [Child]} end,
+        {Leaf, LeafValue, []},
+        Ancestors
+    ),
+    {Start, Node}.
+
+% Build a path start at position Start from revs list with empty (REV_MISSING)
+% internal values and the values as the leaf.
+%
+path(Start, Revs, Value) ->
+    Empty = [{Rev, ?REV_MISSING} || Rev <- lists:droplast(Revs)],
+    path(Start, Empty ++ [{lists:last(Revs), Value}]).
+
+% Empty leafs. We should never have these. This a broken rev tree shape.
+%
+leaves_without_value(RevTree) ->
+    [Rev || {?REV_MISSING, {_Pos, [Rev | _]}} <- 
couch_key_tree:get_all_leafs(RevTree)].
+
+% Merge rev 1...Tip into a rev tree made of fragments and stem. Then do a bunch
+% of validity check on on the result.
+%
+connect_fragments(RevTree, Tip, Leaf, {ValType, StemDepth}) ->
+    Value =
+        case ValType of
+            new -> x;
+            stored when Tip == Leaf -> x;
+            stored -> ?REV_MISSING
+        end,
+    Path = path(1, lists:seq(1, Tip), Value),
+    {Merged, _} = couch_key_tree:merge(RevTree, Path),
+    Stemmed = couch_key_tree:stem(Merged, StemDepth),
+    valid_revtree(Stemmed) andalso
+        leaves_without_value(Stemmed) == [] andalso
+        leaves(Stemmed) == [Leaf].
+
 % Get the list of all the keys in a revision tree. The input can also be a
 % an individual tree (tagged with the depth to virtual root) or a node.
 % Yes, this is not tail recursive but the idea is to keep it simple.

Reply via email to