You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@couchdb.apache.org by GitBox <gi...@apache.org> on 2022/06/11 16:18:12 UTC
[GitHub] [couchdb] jaydoane commented on a diff in pull request #4059: Reduce complexity of "possible_ancestors" from quadratic to linear.
jaydoane commented on code in PR #4059:
URL: https://github.com/apache/couchdb/pull/4059#discussion_r895038761
##########
src/couch/src/couch_db.erl:
##########
@@ -2102,28 +2102,12 @@ possible_ancestors(_FullInfo, []) ->
possible_ancestors(FullInfo, MissingRevs) ->
#doc_info{revs = RevsInfo} = couch_doc:to_doc_info(FullInfo),
LeafRevs = [Rev || #rev_info{rev = Rev} <- RevsInfo],
- % Find the revs that are possible parents of this rev
- lists:foldl(
- fun({LeafPos, LeafRevId}, Acc) ->
- % this leaf is a "possible ancenstor" of the missing
- % revs if this LeafPos lessthan any of the missing revs
- case
- lists:any(
- fun({MissingPos, _}) ->
- LeafPos < MissingPos
- end,
- MissingRevs
- )
- of
- true ->
- [{LeafPos, LeafRevId} | Acc];
- false ->
- Acc
- end
- end,
- [],
- LeafRevs
- ).
+ % Find the revs that are possible parents of this rev. A leaf is a possible
+ % ancestor if the leaf position is less than any of the missing revs, and
Review Comment:
In the first line you use "possible parents", but in the second line you use "possible ancestor". Are those different concepts (which could be elaborated on), or do they mean the same thing?
##########
src/chttpd/test/eunit/chttpd_revs_diff_tests.erl:
##########
@@ -124,18 +124,23 @@ t_revs_diff_some_missing_some_not({Top, Db}) ->
},
{Code, Res} = req(post, Top ++ Db ++ "/_revs_diff", Body),
?assertEqual(200, Code),
- ?assertEqual(
- #{
- ?DOC1 => #{
- <<"missing">> => [<<"1-xyz">>, <<"2-def">>, <<"3-klm">>],
- <<"possible_ancestors">> => [<<"2-revb">>, <<"2-revc">>]
- },
- ?DOC2 => #{
- <<"missing">> => [<<"1-pqr">>]
- }
- },
- Res
- ).
+
+ ?assert(maps:is_key(?DOC1, Res)),
+ ?assert(maps:is_key(?DOC2, Res)),
+ #{?DOC1 := Doc1, ?DOC2 := Doc2} = Res,
+
+ ?assert(maps:is_key(<<"missing">>, Doc1)),
+ ?assert(maps:is_key(<<"missing">>, Doc2)),
+ #{<<"missing">> := Missing1} = Doc1,
+ #{<<"missing">> := Missing2} = Doc2,
+ ?assertEqual([<<"1-xyz">>, <<"2-def">>, <<"3-klm">>], lists:sort(Missing1)),
+ ?assertEqual([<<"1-pqr">>], Missing2),
+
+ ?assert(maps:is_key(<<"possible_ancestors">>, Doc1)),
+ ?assert(not maps:is_key(<<"possible_ancestors">>, Doc2)),
+
+ #{<<"possible_ancestors">> := PAs1} = Doc1,
+ ?assertEqual([<<"2-revb">>, <<"2-revc">>], lists:sort(PAs1)).
Review Comment:
It would be nice if there were a way to canonicalize a structure like this so such contortions for testing equality would not be necessary. Would `maps:to_list` be helpful here?
##########
src/couch/src/couch_db.erl:
##########
@@ -2102,28 +2102,12 @@ possible_ancestors(_FullInfo, []) ->
possible_ancestors(FullInfo, MissingRevs) ->
#doc_info{revs = RevsInfo} = couch_doc:to_doc_info(FullInfo),
LeafRevs = [Rev || #rev_info{rev = Rev} <- RevsInfo],
- % Find the revs that are possible parents of this rev
- lists:foldl(
- fun({LeafPos, LeafRevId}, Acc) ->
- % this leaf is a "possible ancenstor" of the missing
- % revs if this LeafPos lessthan any of the missing revs
- case
- lists:any(
- fun({MissingPos, _}) ->
- LeafPos < MissingPos
- end,
- MissingRevs
- )
- of
- true ->
- [{LeafPos, LeafRevId} | Acc];
- false ->
- Acc
- end
- end,
- [],
- LeafRevs
- ).
+ % Find the revs that are possible parents of this rev. A leaf is a possible
+ % ancestor if the leaf position is less than any of the missing revs, and
+ % if it's less than the any, it means it's also less than the maximum
Review Comment:
"less than the any" <- seems like a typo. Can you clarify this?
##########
src/couch/src/couch_db.erl:
##########
@@ -2102,28 +2102,12 @@ possible_ancestors(_FullInfo, []) ->
possible_ancestors(FullInfo, MissingRevs) ->
#doc_info{revs = RevsInfo} = couch_doc:to_doc_info(FullInfo),
LeafRevs = [Rev || #rev_info{rev = Rev} <- RevsInfo],
- % Find the revs that are possible parents of this rev
- lists:foldl(
- fun({LeafPos, LeafRevId}, Acc) ->
- % this leaf is a "possible ancenstor" of the missing
- % revs if this LeafPos lessthan any of the missing revs
- case
- lists:any(
- fun({MissingPos, _}) ->
- LeafPos < MissingPos
- end,
- MissingRevs
- )
- of
- true ->
- [{LeafPos, LeafRevId} | Acc];
- false ->
- Acc
- end
- end,
- [],
- LeafRevs
- ).
+ % Find the revs that are possible parents of this rev. A leaf is a possible
+ % ancestor if the leaf position is less than any of the missing revs, and
+ % if it's less than the any, it means it's also less than the maximum
+ % missing rev so we just compare against that.
+ {MaxMissingPos, _} = lists:max(MissingRevs),
+ lists:filter(fun({Pos, _}) -> Pos < MaxMissingPos end, LeafRevs).
Review Comment:
So much simpler!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscribe@couchdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org