src/couch/test/eunit/couch_key_tree_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_key_tree_tests).

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

-define(DEPTH, 10).

key_tree_merge_test_() ->
    {
        "Key tree merge",
        [
            should_merge_with_empty_tree(),
            should_merge_reflexive(),
            should_merge_prefix_of_a_tree_with_tree(),
            should_produce_conflict_on_merge_with_unrelated_branch(),
            should_merge_reflexive_for_child_nodes(),
            should_merge_tree_to_itself(),
            should_merge_tree_of_odd_length(),
            should_merge_tree_with_stem(),
            should_merge_with_stem_at_deeper_level(),
            should_merge_with_stem_at_deeper_level_with_deeper_paths(),
            should_merge_single_tree_with_deeper_stem(),
            should_merge_tree_with_large_stem(),
            should_merge_stems(),
            should_create_conflicts_on_merge(),
            should_create_no_conflicts_on_merge(),
            should_ignore_conflicting_branch()
        ]
    }.

key_tree_missing_leaves_test_() ->
    {
        "Missing tree leaves",
        [
            should_not_find_missing_leaves(),
            should_find_missing_leaves()
        ]
    }.

key_tree_remove_leaves_test_() ->
    {
        "Remove tree leaves",
        [
            should_have_no_effect_on_removing_no_leaves(),
            should_have_no_effect_on_removing_non_existant_branch(),
            should_remove_leaf(),
            should_produce_empty_tree_on_removing_all_leaves(),
            should_have_no_effect_on_removing_non_existant_node(),
            should_produce_empty_tree_on_removing_last_leaf()
        ]
    }.

key_tree_get_leaves_test_() ->
    {
        "Leaves retrieving",
        [
            should_extract_subtree(),
            should_extract_subsubtree(),
            should_gather_non_existant_leaf(),
            should_gather_leaf(),
            shoul_gather_multiple_leaves(),
            should_gather_single_leaf_for_multiple_revs(),
            should_gather_multiple_for_multiple_revs(),
            should_retrieve_full_key_path(),
            should_retrieve_full_key_path_for_node(),
            should_retrieve_leaves_with_parent_node(),
            should_retrieve_all_leaves()
        ]
    }.

key_tree_leaf_counting_test_() ->
    {
        "Leaf counting",
        [
            should_have_no_leaves_for_empty_tree(),
            should_have_single_leaf_for_tree_with_single_node(),
            should_have_two_leaves_for_tree_with_chindler_siblings(),
            should_not_affect_on_leaf_counting_for_stemmed_tree()
        ]
    }.

key_tree_stemming_test_() ->
    {
        "Stemming",
        [
            should_have_no_effect_for_stemming_more_levels_than_exists(),
            should_return_one_deepest_node(),
            should_return_two_deepest_nodes()
        ]
    }.

should_merge_with_empty_tree() ->
    One = {1, {"1", "foo", []}},
    ?_assertEqual(
        {[One], new_leaf},
        merge_and_stem([], One)
    ).

should_merge_reflexive() ->
    One = {1, {"1", "foo", []}},
    ?_assertEqual(
        {[One], internal_node},
        merge_and_stem([One], One)
    ).

should_merge_prefix_of_a_tree_with_tree() ->
    One = {1, {"1", "foo", []}},
    TwoSibs = [
        {1, {"1", "foo", []}},
        {1, {"2", "foo", []}}
    ],
    ?_assertEqual(
        {TwoSibs, internal_node},
        merge_and_stem(TwoSibs, One)
    ).

should_produce_conflict_on_merge_with_unrelated_branch() ->
    TwoSibs = [
        {1, {"1", "foo", []}},
        {1, {"2", "foo", []}}
    ],
    Three = {1, {"3", "foo", []}},
    ThreeSibs = [
        {1, {"1", "foo", []}},
        {1, {"2", "foo", []}},
        {1, {"3", "foo", []}}
    ],
    ?_assertEqual(
        {ThreeSibs, new_branch},
        merge_and_stem(TwoSibs, Three)
    ).

should_merge_reflexive_for_child_nodes() ->
    TwoChild = {1, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
    ?_assertEqual(
        {[TwoChild], internal_node},
        merge_and_stem([TwoChild], TwoChild)
    ).

should_merge_tree_to_itself() ->
    TwoChildSibs =
        {1,
            {"1", "foo", [
                {"1a", "bar", []},
                {"1b", "bar", []}
            ]}},
    Leafs = couch_key_tree:get_all_leafs([TwoChildSibs]),
    Paths = lists:map(fun leaf_to_path/1, Leafs),
    FinalTree = lists:foldl(
        fun(Path, TreeAcc) ->
            {NewTree, internal_node} = merge_and_stem(TreeAcc, Path),
            NewTree
        end,
        [TwoChildSibs],
        Paths
    ),
    ?_assertEqual([TwoChildSibs], FinalTree).

leaf_to_path({Value, {Start, Keys}}) ->
    [Branch] = to_branch(Value, lists:reverse(Keys)),
    {Start - length(Keys) + 1, Branch}.

to_branch(Value, [Key]) ->
    [{Key, Value, []}];
to_branch(Value, [Key | RestKeys]) ->
    [{Key, [], to_branch(Value, RestKeys)}].

should_merge_tree_of_odd_length() ->
    TwoChild = {1, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
    TwoChildSibs =
        {1,
            {"1", "foo", [
                {"1a", "bar", []},
                {"1b", "bar", []}
            ]}},
    TwoChildPlusSibs =
        {1,
            {"1", "foo", [
                {"1a", "bar", [{"1aa", "bar", []}]},
                {"1b", "bar", []}
            ]}},
    ?_assertEqual(
        {[TwoChildPlusSibs], new_leaf},
        merge_and_stem([TwoChildSibs], TwoChild)
    ).

should_merge_tree_with_stem() ->
    Stemmed = {2, {"1a", "bar", []}},
    TwoChildSibs =
        {1,
            {"1", "foo", [
                {"1a", "bar", []},
                {"1b", "bar", []}
            ]}},

    ?_assertEqual(
        {[TwoChildSibs], internal_node},
        merge_and_stem([TwoChildSibs], Stemmed)
    ).

should_merge_with_stem_at_deeper_level() ->
    Stemmed = {3, {"1bb", "boo", []}},
    TwoChildSibs =
        {1,
            {"1", "foo", [
                {"1a", "bar", []},
                {"1b", "bar", [{"1bb", "boo", []}]}
            ]}},
    ?_assertEqual(
        {[TwoChildSibs], internal_node},
        merge_and_stem([TwoChildSibs], Stemmed)
    ).

should_merge_with_stem_at_deeper_level_with_deeper_paths() ->
    Stemmed = {3, {"1bb", "boo", []}},
    StemmedTwoChildSibs = [
        {2, {"1a", "bar", []}},
        {2, {"1b", "bar", [{"1bb", "boo", []}]}}
    ],
    ?_assertEqual(
        {StemmedTwoChildSibs, internal_node},
        merge_and_stem(StemmedTwoChildSibs, Stemmed)
    ).

should_merge_single_tree_with_deeper_stem() ->
    Stemmed = {3, {"1aa", "bar", []}},
    TwoChild = {1, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
    ?_assertEqual(
        {[TwoChild], internal_node},
        merge_and_stem([TwoChild], Stemmed)
    ).

should_merge_tree_with_large_stem() ->
    Stemmed = {2, {"1a", "bar", [{"1aa", "bar", []}]}},
    TwoChild = {1, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
    ?_assertEqual(
        {[TwoChild], internal_node},
        merge_and_stem([TwoChild], Stemmed)
    ).

should_merge_stems() ->
    StemmedA = {2, {"1a", "bar", [{"1aa", "bar", []}]}},
    StemmedB = {3, {"1aa", "bar", []}},
    ?_assertEqual(
        {[StemmedA], internal_node},
        merge_and_stem([StemmedA], StemmedB)
    ).

should_create_conflicts_on_merge() ->
    OneChild = {1, {"1", "foo", [{"1a", "bar", []}]}},
    Stemmed = {3, {"1aa", "bar", []}},
    ?_assertEqual(
        {[OneChild, Stemmed], new_branch},
        merge_and_stem([OneChild], Stemmed)
    ).

should_create_no_conflicts_on_merge() ->
    OneChild = {1, {"1", "foo", [{"1a", "bar", []}]}},
    Stemmed = {3, {"1aa", "bar", []}},
    TwoChild = {1, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}},
    ?_assertEqual(
        {[TwoChild], new_leaf},
        merge_and_stem([OneChild, Stemmed], TwoChild)
    ).

should_ignore_conflicting_branch() ->
    %% this test is based on couch-902-test-case2.py
    %% foo has conflicts from replication at depth two
    %% foo3 is the current value
    Foo =
        {1,
            {"foo", "val1", [
                {"foo2", "val2", []},
                {"foo3", "val3", []}
            ]}},
    %% foo now has an attachment added, which leads to foo4 and val4
    %% off foo3
    Bar = {1, {"foo", [], [{"foo3", [], [{"foo4", "val4", []}]}]}},
    %% this is what the merge returns
    %% note that it ignore the conflicting branch as there's no match
    FooBar =
        {1,
            {"foo", "val1", [
                {"foo2", "val2", []},
                {"foo3", "val3", [{"foo4", "val4", []}]}
            ]}},
    {
        "COUCHDB-902",
        ?_assertEqual(
            {[FooBar], new_leaf},
            merge_and_stem([Foo], Bar)
        )
    }.

should_not_find_missing_leaves() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        [],
        couch_key_tree:find_missing(
            TwoChildSibs,
            [{0, "1"}, {1, "1a"}]
        )
    ).

should_find_missing_leaves() ->
    Stemmed1 = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
    Stemmed2 = [{2, {"1aa", "bar", []}}],
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    [
        ?_assertEqual(
            [{0, "10"}, {100, "x"}],
            couch_key_tree:find_missing(
                TwoChildSibs,
                [{0, "1"}, {0, "10"}, {1, "1a"}, {100, "x"}]
            )
        ),
        ?_assertEqual(
            [{0, "1"}, {100, "x"}],
            couch_key_tree:find_missing(
                Stemmed1,
                [{0, "1"}, {1, "1a"}, {100, "x"}]
            )
        ),
        ?_assertEqual(
            [{0, "1"}, {1, "1a"}, {100, "x"}],
            couch_key_tree:find_missing(
                Stemmed2,
                [{0, "1"}, {1, "1a"}, {100, "x"}]
            )
        )
    ].

should_have_no_effect_on_removing_no_leaves() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {TwoChildSibs, []},
        couch_key_tree:remove_leafs(
            TwoChildSibs,
            []
        )
    ).

should_have_no_effect_on_removing_non_existant_branch() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {TwoChildSibs, []},
        couch_key_tree:remove_leafs(
            TwoChildSibs,
            [{0, "1"}]
        )
    ).

should_remove_leaf() ->
    OneChild = [{0, {"1", "foo", [{"1a", "bar", []}]}}],
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {OneChild, [{1, "1b"}]},
        couch_key_tree:remove_leafs(
            TwoChildSibs,
            [{1, "1b"}]
        )
    ).

should_produce_empty_tree_on_removing_all_leaves() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[], [{1, "1b"}, {1, "1a"}]},
        couch_key_tree:remove_leafs(
            TwoChildSibs,
            [{1, "1b"}, {1, "1a"}]
        )
    ).

should_have_no_effect_on_removing_non_existant_node() ->
    Stemmed = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
    ?_assertEqual(
        {Stemmed, []},
        couch_key_tree:remove_leafs(
            Stemmed,
            [{1, "1a"}]
        )
    ).

should_produce_empty_tree_on_removing_last_leaf() ->
    Stemmed = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
    ?_assertEqual(
        {[], [{2, "1aa"}]},
        couch_key_tree:remove_leafs(
            Stemmed,
            [{2, "1aa"}]
        )
    ).

should_extract_subtree() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[{"foo", {0, ["1"]}}], []},
        couch_key_tree:get(TwoChildSibs, [{0, "1"}])
    ).

should_extract_subsubtree() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[{"bar", {1, ["1a", "1"]}}], []},
        couch_key_tree:get(TwoChildSibs, [{1, "1a"}])
    ).

should_gather_non_existant_leaf() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[], [{0, "x"}]},
        couch_key_tree:get_key_leafs(TwoChildSibs, [{0, "x"}])
    ).

should_gather_leaf() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[{"bar", {1, ["1a", "1"]}}], []},
        couch_key_tree:get_key_leafs(TwoChildSibs, [{1, "1a"}])
    ).

shoul_gather_multiple_leaves() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[{"bar", {1, ["1a", "1"]}}, {"bar", {1, ["1b", "1"]}}], []},
        couch_key_tree:get_key_leafs(TwoChildSibs, [{0, "1"}])
    ).

should_gather_single_leaf_for_multiple_revs() ->
    OneChild = [{0, {"1", "foo", [{"1a", "bar", []}]}}],
    ToFind = [{0, "1"}, {1, "1a"}],
    ?_assertEqual(
        {[{"bar", {1, ["1a", "1"]}}], []},
        couch_key_tree:get_key_leafs(OneChild, ToFind)
    ).

should_gather_multiple_for_multiple_revs() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ToFind = [{0, "1"}, {1, "1a"}],
    ?_assertEqual(
        {[{"bar", {1, ["1a", "1"]}}, {"bar", {1, ["1b", "1"]}}], []},
        couch_key_tree:get_key_leafs(TwoChildSibs, ToFind)
    ).

should_retrieve_full_key_path() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[{0, [{"1", "foo"}]}], []},
        couch_key_tree:get_full_key_paths(TwoChildSibs, [{0, "1"}])
    ).

should_retrieve_full_key_path_for_node() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(
        {[{1, [{"1a", "bar"}, {"1", "foo"}]}], []},
        couch_key_tree:get_full_key_paths(TwoChildSibs, [{1, "1a"}])
    ).

should_retrieve_leaves_with_parent_node() ->
    Stemmed = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    [
        ?_assertEqual(
            [{2, [{"1aa", "bar"}, {"1a", "bar"}]}],
            couch_key_tree:get_all_leafs_full(Stemmed)
        ),
        ?_assertEqual(
            [
                {1, [{"1a", "bar"}, {"1", "foo"}]},
                {1, [{"1b", "bar"}, {"1", "foo"}]}
            ],
            couch_key_tree:get_all_leafs_full(TwoChildSibs)
        )
    ].

should_retrieve_all_leaves() ->
    Stemmed = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    [
        ?_assertEqual(
            [{"bar", {2, ["1aa", "1a"]}}],
            couch_key_tree:get_all_leafs(Stemmed)
        ),
        ?_assertEqual(
            [{"bar", {1, ["1a", "1"]}}, {"bar", {1, ["1b", "1"]}}],
            couch_key_tree:get_all_leafs(TwoChildSibs)
        )
    ].

should_have_no_leaves_for_empty_tree() ->
    ?_assertEqual(0, couch_key_tree:count_leafs([])).

should_have_single_leaf_for_tree_with_single_node() ->
    ?_assertEqual(1, couch_key_tree:count_leafs([{0, {"1", "foo", []}}])).

should_have_two_leaves_for_tree_with_chindler_siblings() ->
    TwoChildSibs = [{0, {"1", "foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}],
    ?_assertEqual(2, couch_key_tree:count_leafs(TwoChildSibs)).

should_not_affect_on_leaf_counting_for_stemmed_tree() ->
    ?_assertEqual(1, couch_key_tree:count_leafs([{2, {"1bb", "boo", []}}])).

should_have_no_effect_for_stemming_more_levels_than_exists() ->
    TwoChild = [{0, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}}],
    ?_assertEqual(TwoChild, couch_key_tree:stem(TwoChild, 3)).

should_return_one_deepest_node() ->
    TwoChild = [{0, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}}],
    Stemmed = [{2, {"1aa", "bar", []}}],
    ?_assertEqual(Stemmed, couch_key_tree:stem(TwoChild, 1)).

should_return_two_deepest_nodes() ->
    TwoChild = [{0, {"1", "foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}}],
    Stemmed = [{1, {"1a", "bar", [{"1aa", "bar", []}]}}],
    ?_assertEqual(Stemmed, couch_key_tree:stem(TwoChild, 2)).

merge_and_stem(RevTree, Tree) ->
    {Merged, Result} = couch_key_tree:merge(RevTree, Tree),
    {couch_key_tree:stem(Merged, ?DEPTH), Result}.