test/couch_btree_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(couch_btree_tests).

-include_lib("couch/include/couch_eunit.hrl").
-include_lib("couch/include/couch_db.hrl").

-define(ROWS, 1000).


setup() ->
    {ok, Fd} = couch_file:open(?tempfile(), [create, overwrite]),
    {ok, Btree} = couch_btree:open(nil, Fd, [{compression, none},
                                             {reduce, fun reduce_fun/2}]),
    {Fd, Btree}.

setup_kvs(_) ->
    setup().

setup_red() ->
    {_, EvenOddKVs} = lists:foldl(
        fun(Idx, {Key, Acc}) ->
            case Key of
                "even" -> {"odd", [{{Key, Idx}, 1} | Acc]};
                _ -> {"even", [{{Key, Idx}, 1} | Acc]}
            end
        end, {"odd", []}, lists:seq(1, ?ROWS)),
    {Fd, Btree} = setup(),
    {ok, Btree1} = couch_btree:add_remove(Btree, EvenOddKVs, []),
    {Fd, Btree1}.
setup_red(_) ->
    setup_red().

teardown(Fd) when is_pid(Fd) ->
    ok = couch_file:close(Fd);
teardown({Fd, _}) ->
    teardown(Fd).
teardown(_, {Fd, _}) ->
    teardown(Fd).


kvs_test_funs() ->
    [
        fun should_set_fd_correctly/2,
        fun should_set_root_correctly/2,
        fun should_create_zero_sized_btree/2,
        fun should_set_reduce_option/2,
        fun should_fold_over_empty_btree/2,
        fun should_add_all_keys/2,
        fun should_continuously_add_new_kv/2,
        fun should_continuously_remove_keys/2,
        fun should_insert_keys_in_reversed_order/2,
        fun should_add_every_odd_key_remove_every_even/2,
        fun should_add_every_even_key_remove_every_old/2
    ].

red_test_funs() ->
    [
        fun should_reduce_whole_range/2,
        fun should_reduce_first_half/2,
        fun should_reduce_second_half/2
    ].


btree_open_test_() ->
    {ok, Fd} = couch_file:open(?tempfile(), [create, overwrite]),
    {ok, Btree} = couch_btree:open(nil, Fd, [{compression, none}]),
    {
        "Ensure that created btree is really a btree record",
        ?_assert(is_record(Btree, btree))
    }.

sorted_kvs_test_() ->
    Funs = kvs_test_funs(),
    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, ?ROWS)],
    {
        "BTree with sorted keys",
        {
            setup,
            fun() -> test_util:start(?MODULE, [ioq]) end, fun test_util:stop/1,
            {
                foreachx,
                fun setup_kvs/1, fun teardown/2,
                [{Sorted, Fun} || Fun <- Funs]
            }
        }
    }.

rsorted_kvs_test_() ->
    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, ?ROWS)],
    Funs = kvs_test_funs(),
    Reversed = Sorted,
    {
        "BTree with backward sorted keys",
        {
            setup,
            fun() -> test_util:start(?MODULE, [ioq]) end, fun test_util:stop/1,
            {
                foreachx,
                fun setup_kvs/1, fun teardown/2,
                [{Reversed, Fun} || Fun <- Funs]
            }
        }
    }.

shuffled_kvs_test_() ->
    Funs = kvs_test_funs(),
    Sorted = [{Seq, random:uniform()} || Seq <- lists:seq(1, ?ROWS)],
    Shuffled = shuffle(Sorted),
    {
        "BTree with shuffled keys",
        {
            setup,
            fun() -> test_util:start(?MODULE, [ioq]) end, fun test_util:stop/1,
            {
                foreachx,
                fun setup_kvs/1, fun teardown/2,
                [{Shuffled, Fun} || Fun <- Funs]
            }
        }
    }.

reductions_test_() ->
    {
        "BTree reductions",
        {
            setup,
            fun() -> test_util:start(?MODULE, [ioq]) end, fun test_util:stop/1,
            [
                {
                    "Common tests",
                    {
                        foreach,
                        fun setup_red/0, fun teardown/1,
                        [
                            fun should_reduce_without_specified_direction/1,
                            fun should_reduce_forward/1,
                            fun should_reduce_backward/1
                        ]
                    }
                },
                {
                    "Range requests",
                    [
                        {
                            "Forward direction",
                            {
                                foreachx,
                                fun setup_red/1, fun teardown/2,
                                [{fwd, F} || F <- red_test_funs()]
                            }
                        },
                        {
                            "Backward direction",
                            {
                                foreachx,
                                fun setup_red/1, fun teardown/2,
                                [{rev, F} || F <- red_test_funs()]
                            }
                        }
                    ]
                }
            ]
        }
    }.


should_set_fd_correctly(_, {Fd, Btree}) ->
    ?_assertMatch(Fd, Btree#btree.fd).

should_set_root_correctly(_, {_, Btree}) ->
    ?_assertMatch(nil, Btree#btree.root).

should_create_zero_sized_btree(_, {_, Btree}) ->
    ?_assertMatch(0, couch_btree:size(Btree)).

should_set_reduce_option(_, {_, Btree}) ->
    ReduceFun = fun reduce_fun/2,
    Btree1 = couch_btree:set_options(Btree, [{reduce, ReduceFun}]),
    ?_assertMatch(ReduceFun, Btree1#btree.reduce).

should_fold_over_empty_btree(_, {_, Btree}) ->
    {ok, _, EmptyRes} = couch_btree:foldl(Btree, fun(_, X) -> {ok, X+1} end, 0),
    ?_assertEqual(EmptyRes, 0).

should_add_all_keys(KeyValues, {Fd, Btree}) ->
    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
    [
        should_return_complete_btree_on_adding_all_keys(KeyValues, Btree1),
        should_have_non_zero_size(Btree1),
        should_have_lesser_size_than_file(Fd, Btree1),
        should_keep_root_pointer_to_kp_node(Fd, Btree1),
        should_remove_all_keys(KeyValues, Btree1)
    ].

should_return_complete_btree_on_adding_all_keys(KeyValues, Btree) ->
    ?_assert(test_btree(Btree, KeyValues)).

should_have_non_zero_size(Btree) ->
    ?_assert(couch_btree:size(Btree) > 0).

should_have_lesser_size_than_file(Fd, Btree) ->
    ?_assert((couch_btree:size(Btree) =< couch_file:bytes(Fd))).

should_keep_root_pointer_to_kp_node(Fd, Btree) ->
    ?_assertMatch({ok, {kp_node, _}},
                  couch_file:pread_term(Fd, element(1, Btree#btree.root))).

should_remove_all_keys(KeyValues, Btree) ->
    Keys = keys(KeyValues),
    {ok, Btree1} = couch_btree:add_remove(Btree, [], Keys),
    {
        "Should remove all the keys",
        [
            should_produce_valid_btree(Btree1, []),
            should_be_empty(Btree1)
        ]
    }.

should_continuously_add_new_kv(KeyValues, {_, Btree}) ->
    {Btree1, _} = lists:foldl(
        fun(KV, {BtAcc, PrevSize}) ->
            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
            ?assert(couch_btree:size(BtAcc2) > PrevSize),
            {BtAcc2, couch_btree:size(BtAcc2)}
        end, {Btree, couch_btree:size(Btree)}, KeyValues),
    {
        "Should continuously add key-values to btree",
        [
            should_produce_valid_btree(Btree1, KeyValues),
            should_not_be_empty(Btree1)
        ]
    }.

should_continuously_remove_keys(KeyValues, {_, Btree}) ->
    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
    {Btree2, _} = lists:foldl(
        fun({K, _}, {BtAcc, PrevSize}) ->
            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
            ?assert(couch_btree:size(BtAcc2) < PrevSize),
            {BtAcc2, couch_btree:size(BtAcc2)}
        end, {Btree1, couch_btree:size(Btree1)}, KeyValues),
    {
        "Should continuously remove keys from btree",
        [
            should_produce_valid_btree(Btree2, []),
            should_be_empty(Btree2)
        ]
    }.

should_insert_keys_in_reversed_order(KeyValues, {_, Btree}) ->
    KeyValuesRev = lists:reverse(KeyValues),
    {Btree1, _} = lists:foldl(
        fun(KV, {BtAcc, PrevSize}) ->
            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
            ?assert(couch_btree:size(BtAcc2) > PrevSize),
            {BtAcc2, couch_btree:size(BtAcc2)}
        end, {Btree, couch_btree:size(Btree)}, KeyValuesRev),
    should_produce_valid_btree(Btree1, KeyValues).

should_add_every_odd_key_remove_every_even(KeyValues, {_, Btree}) ->
    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
    {_, Rem2Keys0, Rem2Keys1} = lists:foldl(fun(X, {Count, Left, Right}) ->
        case Count rem 2 == 0 of
            true -> {Count + 1, [X | Left], Right};
            false -> {Count + 1, Left, [X | Right]}
        end
                                            end, {0, [], []}, KeyValues),
    ?_assert(test_add_remove(Btree1, Rem2Keys0, Rem2Keys1)).

should_add_every_even_key_remove_every_old(KeyValues, {_, Btree}) ->
    {ok, Btree1} = couch_btree:add_remove(Btree, KeyValues, []),
    {_, Rem2Keys0, Rem2Keys1} = lists:foldl(fun(X, {Count, Left, Right}) ->
        case Count rem 2 == 0 of
            true -> {Count + 1, [X | Left], Right};
            false -> {Count + 1, Left, [X | Right]}
        end
                                            end, {0, [], []}, KeyValues),
    ?_assert(test_add_remove(Btree1, Rem2Keys1, Rem2Keys0)).


should_reduce_without_specified_direction({_, Btree}) ->
    ?_assertMatch(
        {ok, [{{"odd", _}, ?ROWS div 2}, {{"even", _}, ?ROWS div 2}]},
        fold_reduce(Btree, [])).

should_reduce_forward({_, Btree}) ->
    ?_assertMatch(
        {ok, [{{"odd", _}, ?ROWS div 2}, {{"even", _}, ?ROWS div 2}]},
        fold_reduce(Btree, [{dir, fwd}])).

should_reduce_backward({_, Btree}) ->
    ?_assertMatch(
        {ok, [{{"even", _}, ?ROWS div 2}, {{"odd", _}, ?ROWS div 2}]},
        fold_reduce(Btree, [{dir, rev}])).

should_reduce_whole_range(fwd, {_, Btree}) ->
    {SK, EK} = {{"even", 0}, {"odd", ?ROWS - 1}},
    [
        {
            "include endkey",
            ?_assertMatch(
                {ok, [{{"odd", 1}, ?ROWS div 2},
                      {{"even", 2}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, fwd},
                                    {start_key, SK},
                                    {end_key, EK}]))
        },
        {
            "exclude endkey",
            ?_assertMatch(
                {ok, [{{"odd", 1}, (?ROWS div 2) - 1},
                      {{"even", 2}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, fwd},
                                    {start_key, SK},
                                    {end_key_gt, EK}]))
        }
    ];
should_reduce_whole_range(rev, {_, Btree}) ->
    {SK, EK} = {{"odd", ?ROWS - 1}, {"even", 2}},
    [
        {
            "include endkey",
            ?_assertMatch(
                {ok, [{{"even", ?ROWS}, ?ROWS div 2},
                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, rev},
                                    {start_key, SK},
                                    {end_key, EK}]))
        },
        {
            "exclude endkey",
            ?_assertMatch(
                {ok, [{{"even", ?ROWS}, (?ROWS div 2) - 1},
                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, rev},
                                    {start_key, SK},
                                    {end_key_gt, EK}]))
        }
    ].

should_reduce_first_half(fwd, {_, Btree}) ->
    {SK, EK} = {{"even", 0}, {"odd", (?ROWS div 2) - 1}},
    [
        {
            "include endkey",
            ?_assertMatch(
                {ok, [{{"odd", 1}, ?ROWS div 4},
                      {{"even", 2}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, fwd},
                                    {start_key, SK}, {end_key, EK}]))
        },
        {
            "exclude endkey",
            ?_assertMatch(
                {ok, [{{"odd", 1}, (?ROWS div 4) - 1},
                      {{"even", 2}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, fwd},
                                    {start_key, SK},
                                    {end_key_gt, EK}]))
        }
    ];
should_reduce_first_half(rev, {_, Btree}) ->
    {SK, EK} = {{"odd", ?ROWS - 1}, {"even", ?ROWS div 2}},
    [
        {
            "include endkey",
            ?_assertMatch(
                {ok, [{{"even", ?ROWS}, (?ROWS div 4) + 1},
                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, rev},
                                    {start_key, SK},
                                    {end_key, EK}]))
        },
        {
            "exclude endkey",
            ?_assertMatch(
                {ok, [{{"even", ?ROWS}, ?ROWS div 4},
                      {{"odd", ?ROWS - 1}, ?ROWS div 2}]},
                fold_reduce(Btree, [{dir, rev},
                                    {start_key, SK},
                                    {end_key_gt, EK}]))
        }
    ].

should_reduce_second_half(fwd, {_, Btree}) ->
    {SK, EK} = {{"even", ?ROWS div 2}, {"odd", ?ROWS - 1}},
    [
        {
            "include endkey",
            ?_assertMatch(
                {ok, [{{"odd", 1}, ?ROWS div 2},
                      {{"even", ?ROWS div 2}, (?ROWS div 4) + 1}]},
                fold_reduce(Btree, [{dir, fwd},
                                    {start_key, SK},
                                    {end_key, EK}]))
        },
        {
            "exclude endkey",
            ?_assertMatch(
                {ok, [{{"odd", 1}, (?ROWS div 2) - 1},
                      {{"even", ?ROWS div 2}, (?ROWS div 4) + 1}]},
                fold_reduce(Btree, [{dir, fwd},
                                    {start_key, SK},
                                    {end_key_gt, EK}]))
        }
    ];
should_reduce_second_half(rev, {_, Btree}) ->
    {SK, EK} = {{"odd", (?ROWS div 2) + 1}, {"even", 2}},
    [
        {
            "include endkey",
            ?_assertMatch(
                {ok, [{{"even", ?ROWS}, ?ROWS div 2},
                      {{"odd", (?ROWS div 2) + 1}, (?ROWS div 4) + 1}]},
                fold_reduce(Btree, [{dir, rev},
                                    {start_key, SK},
                                    {end_key, EK}]))
        },
        {
            "exclude endkey",
            ?_assertMatch(
                {ok, [{{"even", ?ROWS}, (?ROWS div 2) - 1},
                      {{"odd", (?ROWS div 2) + 1}, (?ROWS div 4) + 1}]},
                fold_reduce(Btree, [{dir, rev},
                                    {start_key, SK},
                                    {end_key_gt, EK}]))
        }
    ].

should_produce_valid_btree(Btree, KeyValues) ->
    ?_assert(test_btree(Btree, KeyValues)).

should_be_empty(Btree) ->
    ?_assertEqual(couch_btree:size(Btree), 0).

should_not_be_empty(Btree) ->
    ?_assert(couch_btree:size(Btree) > 0).

fold_reduce(Btree, Opts) ->
    GroupFun = fun({K1, _}, {K2, _}) ->
        K1 == K2
    end,
    FoldFun = fun(GroupedKey, Unreduced, Acc) ->
        {ok, [{GroupedKey, couch_btree:final_reduce(Btree, Unreduced)} | Acc]}
    end,
    couch_btree:fold_reduce(Btree, FoldFun, [],
                            [{key_group_fun, GroupFun}] ++ Opts).


keys(KVs) ->
    [K || {K, _} <- KVs].

reduce_fun(reduce, KVs) ->
    length(KVs);
reduce_fun(rereduce, Reds) ->
    lists:sum(Reds).


shuffle(List) ->
    randomize(round(math:log(length(List)) + 0.5), List).

randomize(1, List) ->
    randomize(List);
randomize(T, List) ->
    lists:foldl(
        fun(_E, Acc) ->
            randomize(Acc)
        end, randomize(List), lists:seq(1, (T - 1))).

randomize(List) ->
    D = lists:map(fun(A) -> {random:uniform(), A} end, List),
    {_, D1} = lists:unzip(lists:keysort(1, D)),
    D1.

test_btree(Btree, KeyValues) ->
    ok = test_key_access(Btree, KeyValues),
    ok = test_lookup_access(Btree, KeyValues),
    ok = test_final_reductions(Btree, KeyValues),
    ok = test_traversal_callbacks(Btree, KeyValues),
    true.

test_add_remove(Btree, OutKeyValues, RemainingKeyValues) ->
    Btree2 = lists:foldl(
        fun({K, _}, BtAcc) ->
            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [], [K]),
            BtAcc2
        end, Btree, OutKeyValues),
    true = test_btree(Btree2, RemainingKeyValues),

    Btree3 = lists:foldl(
        fun(KV, BtAcc) ->
            {ok, BtAcc2} = couch_btree:add_remove(BtAcc, [KV], []),
            BtAcc2
        end, Btree2, OutKeyValues),
    true = test_btree(Btree3, OutKeyValues ++ RemainingKeyValues).

test_key_access(Btree, List) ->
    FoldFun = fun(Element, {[HAcc|TAcc], Count}) ->
        case Element == HAcc of
            true -> {ok, {TAcc, Count + 1}};
            _ -> {ok, {TAcc, Count + 1}}
        end
    end,
    Length = length(List),
    Sorted = lists:sort(List),
    {ok, _, {[], Length}} = couch_btree:foldl(Btree, FoldFun, {Sorted, 0}),
    {ok, _, {[], Length}} = couch_btree:fold(Btree, FoldFun,
                                             {Sorted, 0}, [{dir, rev}]),
    ok.

test_lookup_access(Btree, KeyValues) ->
    FoldFun = fun({Key, Value}, {Key, Value}) -> {stop, true} end,
    lists:foreach(
        fun({Key, Value}) ->
            [{ok, {Key, Value}}] = couch_btree:lookup(Btree, [Key]),
            {ok, _, true} = couch_btree:foldl(Btree, FoldFun,
                                              {Key, Value}, [{start_key, Key}])
        end, KeyValues).

test_final_reductions(Btree, KeyValues) ->
    KVLen = length(KeyValues),
    FoldLFun = fun(_X, LeadingReds, Acc) ->
        CountToStart = KVLen div 3 + Acc,
        CountToStart = couch_btree:final_reduce(Btree, LeadingReds),
        {ok, Acc + 1}
    end,
    FoldRFun = fun(_X, LeadingReds, Acc) ->
        CountToEnd = KVLen - KVLen div 3 + Acc,
        CountToEnd = couch_btree:final_reduce(Btree, LeadingReds),
        {ok, Acc + 1}
    end,
    {LStartKey, _} = case KVLen of
        0 -> {nil, nil};
        _ -> lists:nth(KVLen div 3 + 1, lists:sort(KeyValues))
    end,
    {RStartKey, _} = case KVLen of
        0 -> {nil, nil};
        _ -> lists:nth(KVLen div 3, lists:sort(KeyValues))
    end,
    {ok, _, FoldLRed} = couch_btree:foldl(Btree, FoldLFun, 0,
                                          [{start_key, LStartKey}]),
    {ok, _, FoldRRed} = couch_btree:fold(Btree, FoldRFun, 0,
                                         [{dir, rev}, {start_key, RStartKey}]),
    KVLen = FoldLRed + FoldRRed,
    ok.

test_traversal_callbacks(Btree, _KeyValues) ->
    FoldFun = fun
        (visit, _GroupedKey, _Unreduced, Acc) ->
            {ok, Acc andalso false};
        (traverse, _LK, _Red, Acc) ->
            {skip, Acc andalso true}
    end,
    % With 250 items the root is a kp. Always skipping should reduce to true.
    {ok, _, true} = couch_btree:fold(Btree, FoldFun, true, [{dir, fwd}]),
    ok.