Implement get_missing_revs

3 files changed, 133 insertions, 4 deletions

diff --git a/src/chttpd/src/chttpd_db.erl b/src/chttpd/src/chttpd_db.erl
index c0c7ad3f4..27c1a8a81 100644
--- a/src/chttpd/src/chttpd_db.erl
+++ b/src/chttpd/src/chttpd_db.erl
@@ -674,7 +674,7 @@ db_req(#httpd{path_parts=[_,OP]}=Req, _Db) when ?IS_ALL_DOCS(OP) ->
 db_req(#httpd{method='POST',path_parts=[_,<<"_missing_revs">>]}=Req, Db) ->
     chttpd:validate_ctype(Req, "application/json"),
     {JsonDocIdRevs} = chttpd:json_body_obj(Req),
-    case fabric:get_missing_revs(Db, JsonDocIdRevs) of
+    case fabric2_db:get_missing_revs(Db, JsonDocIdRevs) of
         {error, Reason} ->
             chttpd:send_error(Req, Reason);
         {ok, Results} ->
@@ -691,7 +691,7 @@ db_req(#httpd{path_parts=[_,<<"_missing_revs">>]}=Req, _Db) ->
 db_req(#httpd{method='POST',path_parts=[_,<<"_revs_diff">>]}=Req, Db) ->
     chttpd:validate_ctype(Req, "application/json"),
     {JsonDocIdRevs} = chttpd:json_body_obj(Req),
-    case fabric:get_missing_revs(Db, JsonDocIdRevs) of
+    case fabric2_db:get_missing_revs(Db, JsonDocIdRevs) of
         {error, Reason} ->
             chttpd:send_error(Req, Reason);
         {ok, Results} ->
diff --git a/src/fabric/src/fabric2_db.erl b/src/fabric/src/fabric2_db.erl
index 68de40cb1..a9c17c992 100644
--- a/src/fabric/src/fabric2_db.erl
+++ b/src/fabric/src/fabric2_db.erl
@@ -73,7 +73,7 @@
     %% get_doc_info/2,
     %% get_full_doc_info/2,
     %% get_full_doc_infos/2,
-    %% get_missing_revs/2,
+    get_missing_revs/2,
     %% get_design_doc/2,
     %% get_design_docs/1,
     %% get_design_doc_count/1,
@@ -461,6 +461,38 @@ open_doc_revs(Db, DocId, Revs, Options) ->
     end).
 
 
+get_missing_revs(Db, IdRevs) ->
+    AllRevInfos = fabric2_fdb:transactional(Db, fun(TxDb) ->
+        lists:foldl(fun({Id, _Revs}, Acc) ->
+            case maps:is_key(Id, Acc) of
+                true ->
+                    Acc;
+                false ->
+                    RevInfos = fabric2_fdb:get_all_revs(TxDb, Id),
+                    Acc#{Id => RevInfos}
+            end
+        end, #{}, IdRevs)
+    end),
+    AllMissing = lists:flatmap(fun({Id, Revs}) ->
+        #{Id := RevInfos} = AllRevInfos,
+        Missing = try
+            lists:foldl(fun(RevInfo, RevAcc) ->
+                if RevAcc /= [] -> ok; true ->
+                    throw(all_found)
+                end,
+                filter_found_revs(RevInfo, RevAcc)
+            end, Revs, RevInfos)
+        catch throw:all_found ->
+            []
+        end,
+        if Missing == [] -> []; true ->
+            PossibleAncestors = find_possible_ancestors(RevInfos, Missing),
+            [{Id, Missing, PossibleAncestors}]
+        end
+    end, IdRevs),
+    {ok, AllMissing}.
+
+
 update_doc(Db, Doc) ->
     update_doc(Db, Doc, []).
 
@@ -700,6 +732,54 @@ apply_open_doc_opts(Doc, Revs, Options) ->
     end.
 
 
+filter_found_revs(RevInfo, Revs) ->
+    #{
+        rev_id := {Pos, Rev},
+        rev_path := RevPath
+    } = RevInfo,
+    FullRevPath = [Rev | RevPath],
+    lists:flatmap(fun({FindPos, FindRev} = RevIdToFind) ->
+        if FindPos > Pos -> [RevIdToFind]; true ->
+            % Add 1 because lists:nth is 1 based
+            Idx = Pos - FindPos + 1,
+            case Idx > length(FullRevPath) of
+                true ->
+                    [RevIdToFind];
+                false ->
+                    case lists:nth(Idx, FullRevPath) == FindRev of
+                        true -> [];
+                        false -> [RevIdToFind]
+                    end
+            end
+        end
+    end, Revs).
+
+
+find_possible_ancestors(RevInfos, MissingRevs) ->
+    % Find any revinfos that are possible ancestors
+    % of the missing revs. A possible ancestor is
+    % any rev that has a start position less than
+    % any missing revision. Stated alternatively,
+    % find any revinfo that could theoretically
+    % extended to be one or more of the missing
+    % revisions.
+    %
+    % Since we are looking at any missing revision
+    % we can just compare against the maximum missing
+    % start position.
+    MaxMissingPos = case MissingRevs of
+        [] -> 0;
+        [_ | _] -> lists:max([Start || {Start, _Rev} <- MissingRevs])
+    end,
+    lists:flatmap(fun(RevInfo) ->
+        #{rev_id := {RevPos, _} = RevId} = RevInfo,
+        case RevPos < MaxMissingPos of
+            true -> [RevId];
+            false -> []
+        end
+    end, RevInfos).
+
+
 update_doc_int(#{} = Db, #doc{} = Doc, Options) ->
     IsLocal = case Doc#doc.id of
         <<?LOCAL_DOC_PREFIX, _/binary>> -> true;
diff --git a/src/fabric/test/fabric2_doc_crud_tests.erl b/src/fabric/test/fabric2_doc_crud_tests.erl
index 86dbcc8ce..17e8c3689 100644
--- a/src/fabric/test/fabric2_doc_crud_tests.erl
+++ b/src/fabric/test/fabric2_doc_crud_tests.erl
@@ -52,6 +52,7 @@ doc_crud_test_() ->
                 fun open_doc_revs_basic/1,
                 fun open_doc_revs_all/1,
                 fun open_doc_revs_latest/1,
+                fun get_missing_revs_basic/1,
                 fun open_missing_local_doc/1,
                 fun create_local_doc_basic/1,
                 fun update_local_doc_basic/1,
@@ -347,7 +348,7 @@ delete_doc_basic({Db, _}) ->
     },
     {ok, {Pos2, Rev2}} = fabric2_db:update_doc(Db, Doc2),
     Doc3 = Doc2#doc{revs = {Pos2, [Rev2, Rev1]}},
-    ?assertEqual({ok, Doc3}, fabric2_db:open_doc(Db, Doc2#doc.id)).
+    ?assertEqual({ok, Doc3}, fabric2_db:open_doc(Db, Doc2#doc.id, [deleted])).
 
 
 delete_changes_winner({Db, _}) ->
@@ -566,6 +567,54 @@ open_doc_revs_latest({Db, _}) ->
     ?assert(lists:member({ok, Doc2}, Docs)).
 
 
+get_missing_revs_basic({Db, _}) ->
+    [Rev1, Rev2, Rev3] = lists:sort([
+            fabric2_util:uuid(),
+            fabric2_util:uuid(),
+            fabric2_util:uuid()
+        ]),
+    DocId = fabric2_util:uuid(),
+    Doc1 = #doc{
+        id = DocId,
+        revs = {2, [Rev3, Rev1]},
+        body = {[{<<"foo">>, <<"bar">>}]}
+    },
+    {ok, {2, _}} = fabric2_db:update_doc(Db, Doc1, [replicated_changes]),
+    Doc2 = Doc1#doc{
+        revs = {2, [Rev2, Rev1]},
+        body = {[{<<"bar">>, <<"foo">>}]}
+    },
+    {ok, {2, _}} = fabric2_db:update_doc(Db, Doc2, [replicated_changes]),
+
+    % Check that we can find all revisions
+    AllRevs = [{1, Rev1}, {2, Rev2}, {2, Rev3}],
+    ?assertEqual(
+            {ok, []},
+            fabric2_db:get_missing_revs(Db, [{DocId, AllRevs}])
+        ),
+
+    % Check that a missing revision is found with no possible ancestors
+    MissingRev = {2, fabric2_util:uuid()},
+    ?assertEqual(
+            {ok, [{DocId, [MissingRev], []}]},
+            fabric2_db:get_missing_revs(Db, [{DocId, [MissingRev]}])
+        ),
+
+    % Check that only a missing rev is returned
+    ?assertEqual(
+            {ok, [{DocId, [MissingRev], []}]},
+            fabric2_db:get_missing_revs(Db, [{DocId, [MissingRev | AllRevs]}])
+        ),
+
+    % Check that we can find possible ancestors
+    MissingWithAncestors = {4, fabric2_util:uuid()},
+    PossibleAncestors = [{2, Rev2}, {2, Rev3}],
+    ?assertEqual(
+            {ok, [{DocId, [MissingWithAncestors], PossibleAncestors}]},
+            fabric2_db:get_missing_revs(Db, [{DocId, [MissingWithAncestors]}])
+        ).
+
+
 open_missing_local_doc({Db, _}) ->
     ?assertEqual(
             {not_found, missing},