This is an automated email from the ASF dual-hosted git repository.
nickva pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/couchdb.git
The following commit(s) were added to refs/heads/main by this push:
new 6e9dd86fd Stem rev trees with duplicates the same as a tree without
them
6e9dd86fd is described below
commit 6e9dd86fd045c4baa4fd8d3f9f70a4532c15b297
Author: Nick Vatamaniuc <[email protected]>
AuthorDate: Mon Nov 2 17:36:30 2026 -0500
Stem rev trees with duplicates the same as a tree without them
Stemming is done in essentially two ways: normally we walk the tree and
keep a
revision if any leaf under is below the revs limit, or, if the tree has
duplicates (say we a fragment connect two other path fragments)
repair_tree/2
rebuilds the tree from all leaf paths and in the process cuts each path to
fits
the revs limit.
Previously, those two ways of stemming could have disagreed on results. The
repair procedure could have cut-off a leaf form the ancestor, even if the
ancestor would survive anyway (due to having another, shorter branch). Then
we
could end up with one tree shape in one or as multiple paths in another
case.
To fix it, let repair_tree/2 collapse duplicate by re-merging the full leaf
path as it did since #6179, and then walk the result like any other tree. If
duplicates cannot be collapsed (same rev id at a different position)
re-throw
and do the cut-per-path as before.
(This issue was reported by Will Holley)
---
src/couch/src/couch_key_tree.erl | 40 +++++++++++++-------
src/couch/test/eunit/couch_key_tree_prop_tests.erl | 44 ++++++++++++++++++++++
2 files changed, 71 insertions(+), 13 deletions(-)
diff --git a/src/couch/src/couch_key_tree.erl b/src/couch/src/couch_key_tree.erl
index 901f58429..06e5d2041 100644
--- a/src/couch/src/couch_key_tree.erl
+++ b/src/couch/src/couch_key_tree.erl
@@ -476,20 +476,25 @@ mapfold_simple(Fun, Acc, Pos, [{Key, Value, SubTree} |
RestTree]) ->
stem(Trees, Limit) ->
try
- {_, Branches} = lists:foldl(
- fun(Tree, {Seen, TreeAcc}) ->
- {NewSeen, NewBranches} = stem_tree(Tree, Limit, Seen),
- {NewSeen, NewBranches ++ TreeAcc}
- end,
- {#{}, []},
- Trees
- ),
- lists:sort(Branches)
+ stem_trees(Trees, Limit)
catch
throw:dupe_keys ->
repair_tree(Trees, Limit)
end.
+% Stem each tree by walking it. Throws dupe_keys if a key is found more than
+% once across all the trees.
+stem_trees(Trees, Limit) ->
+ {_, Branches} = lists:foldl(
+ fun(Tree, {Seen, TreeAcc}) ->
+ {NewSeen, NewBranches} = stem_tree(Tree, Limit, Seen),
+ {NewSeen, NewBranches ++ TreeAcc}
+ end,
+ {#{}, []},
+ Trees
+ ),
+ lists:sort(Branches).
+
stem_tree({Depth, Child}, Limit, Seen) ->
case stem_tree(Depth, Child, Limit, Seen) of
{NewSeen, _, NewChild, NewBranches} ->
@@ -546,10 +551,19 @@ 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).
+ % We could have duplicate keys when merge/2 extends a branch that also
+ % covers a fragment that may have come in earlier, maybe from a source with
+ % a different revs_limit setting or after a purge. To properly collapse the
+ % duplicates, merge again all the full path, then stem the result like any
+ % other tree. If that fails, fall back to stem each leaf separately
+ % anyway.
+ Collapsed = merge_paths(get_all_leafs_full(Trees), infinity),
+ try
+ stem_trees(Collapsed, Limit)
+ catch
+ throw:dupe_keys ->
+ lists:sort(merge_paths(get_all_leafs_full(Collapsed), Limit))
+ end.
merge_paths(LeafPaths, Limit) ->
% flatten each branch in a tree into a tree path, sort by starting rev #
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 03c3c4aba..6fe3127a1 100644
--- a/src/couch/test/eunit/couch_key_tree_prop_tests.erl
+++ b/src/couch/test/eunit/couch_key_tree_prop_tests.erl
@@ -206,6 +206,24 @@ prop_stem_connect_fragments() ->
end
).
+% If we rebuild the tree from paths (and fix dupes) we should end up with the
+% same shape. Also if we keep stemming the tree with the same revs limit it
+% should stay unchanged.
+%
+prop_stem_with_dupes_same_as_without() ->
+ ?FORALL(
+ {{RevTree, Fragment}, Depth},
+ {g_revtree_with_fragment(), choose(1, 20)},
+ begin
+ Stemmed = couch_key_tree:stem(RevTree, Depth),
+ WithDup = couch_key_tree:stem(RevTree ++ [Fragment], Depth),
+ ?WHENFAIL(
+ io:format("frag: ~p~nno dups: ~p~nwith dups: ~p~n", [Fragment,
Stemmed, WithDup]),
+ Stemmed == WithDup andalso couch_key_tree:stem(WithDup, Depth)
== WithDup
+ )
+ end
+ ).
+
%
% Generators
%
@@ -280,6 +298,32 @@ g_revtree_with_path() ->
)
).
+% Generate a revtree and a fragment from the tree. The idea is if we merge the
+% fragment back in it will create duplicates which we then should handle
+% properly.
+%
+g_revtree_with_fragment() ->
+ ?LET(
+ RevTree,
+ g_revtree(),
+ ?LET(
+ {LeafPos, LeafPath},
+ elements(couch_key_tree:get_all_leafs_full(RevTree)),
+ ?LET(
+ {I, J},
+ {choose(1, length(LeafPath)), choose(1, length(LeafPath))},
+ begin
+ First = min(I, J),
+ Len = max(I, J) - First + 1,
+ Revs = [Rev || {Rev, _} <- lists:reverse(LeafPath)],
+ Start = LeafPos - length(LeafPath) + First,
+ Fragment = path(Start, lists:sublist(Revs, First, Len), x),
+ {RevTree, Fragment}
+ end
+ )
+ )
+ ).
+
% Generate a path (revtree with no branches) of a given depth range
%
g_path(MinDepth, MaxDepth) ->