src/mem3/test/eunit/mem3_ring_prop_tests.erl

% Licensed under the Apache License, Version 2.0 (the "License"); you may not
% use this file except in compliance with the License. You may obtain a copy of
% the License at
%
%   http://www.apache.org/licenses/LICENSE-2.0
%
% Unless required by applicable law or agreed to in writing, software
% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
% License for the specific language governing permissions and limitations under
% the License.

-module(mem3_ring_prop_tests).

-ifdef(WITH_PROPER).

-include_lib("couch/include/couch_eunit_proper.hrl").

property_test_() ->
    ?EUNIT_QUICKCHECK(60).

% Properties

prop_get_ring_with_connected_intervals() ->
    ?FORALL(
        {Start, End},
        oneof(ranges()),
        ?FORALL(
            Intervals,
            g_connected_intervals(Start, End),
            mem3_util:get_ring(Intervals, Start, End) =:= lists:sort(Intervals)
        )
    ).

prop_get_ring_connected_plus_random_intervals() ->
    ?FORALL(
        {Intervals, Extra},
        {g_connected_intervals(1, 100), g_random_intervals(1, 100)},
        ?IMPLIES(
            sets:is_disjoint(endpoints(Intervals), endpoints(Extra)),
            begin
                AllInts = Intervals ++ Extra,
                Ring = mem3_util:get_ring(AllInts, 1, 100),
                Ring =:= lists:sort(Intervals)
            end
        )
    ).

prop_get_ring_connected_with_sub_intervals() ->
    ?FORALL(
        Intervals,
        g_connected_intervals(1, 100),
        ?FORALL(
            SubIntervals,
            g_subintervals(Intervals),
            begin
                AllInts = Intervals ++ SubIntervals,
                Ring = mem3_util:get_ring(AllInts, 1, 100),
                Ring =:= lists:sort(Intervals)
            end
        )
    ).

prop_get_ring_with_disconnected_intervals() ->
    ?FORALL(
        {Start, End},
        oneof(ranges()),
        ?FORALL(
            Intervals,
            g_disconnected_intervals(Start, End),
            mem3_util:get_ring(Intervals, Start, End) =:= []
        )
    ).

% Generators

ranges() ->
    [{1, 10}, {0, 2 bsl 31 - 1}, {2 bsl 31 - 10, 2 bsl 31 - 1}].

g_connected_intervals(Begin, End) ->
    ?SIZED(Size, g_connected_intervals(Begin, End, 5 * Size)).

g_connected_intervals(Begin, End, Split) when Begin =< End ->
    ?LET(
        N,
        choose(0, Split),
        begin
            if
                N == 0 ->
                    [{Begin, End}];
                N > 0 ->
                    Ns = lists:seq(1, N - 1),
                    Bs = lists:usort([rand_range(Begin, End) || _ <- Ns]),
                    Es = [B - 1 || B <- Bs],
                    test_util:shuffle(lists:zip([Begin] ++ Bs, Es ++ [End]))
            end
        end
    ).

g_non_trivial_connected_intervals(Begin, End, Split) ->
    ?SUCHTHAT(
        Connected,
        g_connected_intervals(Begin, End, Split),
        length(Connected) > 1
    ).

g_disconnected_intervals(Begin, End) ->
    ?SIZED(Size, g_disconnected_intervals(Begin, End, Size)).

g_disconnected_intervals(Begin, End, Split) when Begin =< End ->
    ?LET(
        Connected,
        g_non_trivial_connected_intervals(Begin, End, Split),
        begin
            I = rand:uniform(length(Connected)) - 1,
            {Before, [_ | After]} = lists:split(I, Connected),
            Before ++ After
        end
    ).

g_subintervals(Intervals) ->
    lists:foldl(fun(R, Acc) -> split_interval(R) ++ Acc end, [], Intervals).

split_interval({B, E}) when E - B >= 2 ->
    E1 = rand_range(B, E) - 1,
    B1 = E1 + 1,
    [{B, E1}, {B1, E}];
split_interval(_Range) ->
    [].

g_random_intervals(Start, End) ->
    ?LET(
        N,
        choose(1, 10),
        begin
            [
                begin
                    B = rand_range(Start, End),
                    E = rand_range(B, End),
                    {B, E}
                end
             || _ <- lists:seq(1, N)
            ]
        end
    ).

rand_range(B, B) ->
    B;
rand_range(B, E) ->
    B + rand:uniform(E - B).

endpoints(Ranges) ->
    {Begins, Ends} = lists:unzip(Ranges),
    sets:from_list(Begins ++ Ends).

-endif.