4
\$\begingroup\$

This question is related to my previous two questions, in which I have implemented HashTable, and also SortedListMap and BinarySearchTree. Since the three types of mappings have similar interfaces, if I wrote three separate tests for them there would be lots of boilerplate codes. Instead I decided to write a single test script (using pytest) to test all three at once. It was tricky and took me a lot of time to set up the fixtures correctly, but finally I managed it and all tests were passed.

Summary of the three types of mappings and what I want to do in the test code:

  1. All three types of mappings are subclasses of the abstract base class MutableMapping. They all have the methods __len__, __iter__, __getitem__, __setitem__, __delitem__ required by MutableMapping, so I need to write test classes to test these methods on all three of them.
  2. SortedListMap and BinarySearchTree are also sorted mappings. Although I didn't make SortedMapping into an explicit abstract base class, as sorted mappings they both have the minimum, maximum, predecessor and successor methods, which needs separate test classes than those mentioned in 1.
  3. I want to test on a small number of fixed inputs as well as a large number of random inputs.
  4. In total I need four test classes: unsorted maps and fixed inputs, unsorted maps and random inputs, sorted maps and fixed inputs, sorted maps and random inputs.

Below is my test code:

import collections
import random
from string import ascii_lowercase
from itertools import product

import pytest
from hash_table import HashTable
from sorted_list_map import SortedListMap
from binary_search_tree import BinarySearchTree

"""Map Classes that we are testing."""

UNSORTED_MAPS = [HashTable, SortedListMap, BinarySearchTree]
SORTED_MAPS = [SortedListMap, BinarySearchTree]


"""Constants and a fixture for testing small fixed inputs.
The keys are deliberately repeated to test whether the maps contain repeated keys.
"""

KEYS = ['A', 'B', 'C', 'C', 'A', 'D', 'E', 'F',
        'G', 'G', 'G', 'H', 'E', 'I', 'A', 'J',
        'K', 'L', 'D', 'J', 'F', 'L', 'B', 'K']

KEY_SET = set(KEYS)
SORTED_KEYS = sorted(KEY_SET)
ITEMS = [(key, i) for i, key in enumerate(KEYS)]
DICT_ITEMS = dict(ITEMS).items()
SORTED_ITEMS = sorted(DICT_ITEMS)


@pytest.fixture(scope='class')
def fixed_input_map(request):
    """Return a map of the requested map class with the given fixed items."""
    my_map = request.param(ITEMS)
    return my_map


"""Constants, fixtures and helper functions for testing large random inputs.
The keys are drawn at random from the list of all strings of 3 lowercase letters.
"""

KEY_LEN = 3
POSSIBLE_KEYS = [''.join(chars) for chars in product(ascii_lowercase,
                                                     repeat=KEY_LEN)]


@pytest.fixture(scope='class')
def map_pair(request):
    """Return a map of the requested map class and also a python dictionary.
    In the tests, we would compare our maps with the python dicts.
    Since the scope is 'class', this fixture actually return the same
    my_map and python_dict instances for every test within the same test class.
    This means all modifications to my_map and python_dict done by previous tests
    are carried over to later tests.
    """
    my_map = request.param()
    python_dict = {}
    return my_map, python_dict


def random_setitem(my_map, python_dict):
    """Helper function for adding random items into my_map and python_dict.
    Number of added items equals number of possible keys.
    But since there are repeated added keys, not all possible keys are added.
    """
    added_keys = random.choices(POSSIBLE_KEYS, k=len(POSSIBLE_KEYS))
    for i, key in enumerate(added_keys):
        my_map[key] = i
        python_dict[key] = i
    return my_map, python_dict


def random_delitem(my_map, python_dict):
    """Helper function for removing random items from my_map and python_dict.
    Number of removed items is chosen to be 2/3 of the existing items.
    """
    num_dels = len(python_dict) * 2 // 3
    removed_keys = random.sample(python_dict.keys(), k=num_dels)
    for key in removed_keys:
        del my_map[key]
        del python_dict[key]
    return my_map, python_dict


"""Test classes"""


@pytest.mark.parametrize('fixed_input_map', UNSORTED_MAPS, indirect=True)
class TestUnsortedMapFixedInput:
    """Test class for unsorted maps with small fixed inputs."""

    def test_len(self, fixed_input_map):
        """Test the __len__ method."""
        assert len(fixed_input_map) == len(KEY_SET)

    def test_iter(self, fixed_input_map):
        """Test the __iter__method.
        Since we don't care about the ordering, we cast the iterator into a set.
        """
        assert set(key for key in fixed_input_map) == KEY_SET

    @pytest.mark.parametrize('key, value', DICT_ITEMS)
    def test_getitem(self, fixed_input_map, key, value):
        """Test the __getitem__ method for all (key, value) pair."""
        assert fixed_input_map[key] == value

    @pytest.mark.parametrize('key', KEY_SET)
    def test_delitem(self, fixed_input_map, key):
        """Test the __delitem__ method for all keys. After deleting a key,
        getting and deleting the same key should raise a KeyError.
        """
        del fixed_input_map[key]
        with pytest.raises(KeyError):
            fixed_input_map[key]
        with pytest.raises(KeyError):
            del fixed_input_map[key]

    def test_empty(self, fixed_input_map):
        """After deleting all items, the map should be empty."""
        assert len(fixed_input_map) == 0


@pytest.mark.parametrize('map_pair', UNSORTED_MAPS, indirect=True)
class TestUnsortedMapRandomInput:
    """Test class for unsorted maps with large random inputs.
    We added a large number of random items to each map and assert that the length
    of the map and the set of items are correct, then we randomly remove 2/3 of
    the items and assert again. The process is repeated three times.
    """

    def test_first_setitem(self, map_pair):
        my_map, python_dict = random_setitem(*map_pair)
        assert len(my_map) == len(python_dict)
        assert set(my_map.items()) == set(python_dict.items())

    def test_first_delitem(self, map_pair):
        my_map, python_dict = random_delitem(*map_pair)
        assert len(my_map) == len(python_dict)
        assert set(my_map.items()) == set(python_dict.items())

    def test_second_setitem(self, map_pair):
        my_map, python_dict = random_setitem(*map_pair)
        assert len(my_map) == len(python_dict)
        assert set(my_map.items()) == set(python_dict.items())

    def test_second_delitem(self, map_pair):
        my_map, python_dict = random_delitem(*map_pair)
        assert len(my_map) == len(python_dict)
        assert set(my_map.items()) == set(python_dict.items())

    def test_third_setitem(self, map_pair):
        my_map, python_dict = random_setitem(*map_pair)
        assert len(my_map) == len(python_dict)
        assert set(my_map.items()) == set(python_dict.items())

    def test_third_delitem(self, map_pair):
        my_map, python_dict = random_delitem(*map_pair)
        assert len(my_map) == len(python_dict)
        assert set(my_map.items()) == set(python_dict.items())


@pytest.mark.parametrize('fixed_input_map', SORTED_MAPS, indirect=True)
class TestSortedMapFixedInput:
    """Test class for sorted maps with small fixed inputs."""

    def test_minimum(self, fixed_input_map):
        """Test the minimum method."""
        assert fixed_input_map.minimum() == SORTED_ITEMS[0]

    def test_maximum(self, fixed_input_map):
        """Test the maximum method."""
        assert fixed_input_map.maximum() == SORTED_ITEMS[-1]

    def test_no_predecessor(self, fixed_input_map):
        """Test the predecessor method for the smallest key,
        which results in a KeyError."""
        with pytest.raises(KeyError):
            fixed_input_map.predecessor(SORTED_KEYS[0])

    def test_no_successor(self, fixed_input_map):
        """Test the successor method for the largest key,
        which results in a KeyError."""
        with pytest.raises(KeyError):
            fixed_input_map.successor(SORTED_KEYS[-1])

    @pytest.mark.parametrize('key', SORTED_KEYS[1:])
    def test_predecessor(self, fixed_input_map, key):
        """Test the predecessor method for all but the smallest key."""
        prev_item = SORTED_ITEMS[SORTED_KEYS.index(key) - 1]
        assert fixed_input_map.predecessor(key) == prev_item

    @pytest.mark.parametrize('key', SORTED_KEYS[:-1])
    def test_successor(self, fixed_input_map, key):
        """Test the successor method for all but the largest key."""
        next_item = SORTED_ITEMS[SORTED_KEYS.index(key) + 1]
        assert fixed_input_map.successor(key) == next_item


@pytest.mark.parametrize('map_pair', SORTED_MAPS, indirect=True)
class TestSortedMapRandomInput:
    """Test class for sorted maps with large random inputs.
    Similar to TestUnsortedMapRandomInput, we randomly add and remove items
    three times, but we test whether the lists of keys are sorted instead.
    """

    def test_first_setitem(self, map_pair):
        my_map, python_dict = random_setitem(*map_pair)
        assert list(my_map) == sorted(python_dict)

    def test_first_delitem(self, map_pair):
        my_map, python_dict = random_delitem(*map_pair)
        assert list(my_map) == sorted(python_dict)

    def test_second_setitem(self, map_pair):
        my_map, python_dict = random_setitem(*map_pair)
        assert list(my_map) == sorted(python_dict)

    def test_second_delitem(self, map_pair):
        my_map, python_dict = random_delitem(*map_pair)
        assert list(my_map) == sorted(python_dict)

    def test_third_setitem(self, map_pair):
        my_map, python_dict = random_setitem(*map_pair)
        assert list(my_map) == sorted(python_dict)

    def test_third_delitem(self, map_pair):
        my_map, python_dict = random_delitem(*map_pair)
        assert list(my_map) == sorted(python_dict)

Questions:

  1. Is using @pytest.mark.parametrize to test different classes with similar interfaces a good idea?
  2. There are tests that depend on the results of previous tests, especially when it comes to deleting items and random inputs. Is this a bad practice?
  3. It is difficult to test __setitem__ separately since all other methods depend on it. How can I write a separate test case for __setitem__?
  4. Did I use too many global constants in the test script?
  5. What else can I improve my test code?
\$\endgroup\$

1 Answer 1

2
+50
\$\begingroup\$

Please consider below as opinions, not the source of truth. I write what 'should' be but read it as 'I think it should...'

As for your questions:

1) It is not a good idea. For me, parametrize decorator means 'those are the inputs to the function you are testing' not 'this is the function that you are testing'.

2) I think it is a bad practice. Unit tests should be designed to be not dependend on anything else except fixture (or any other setup). I've seen E2E tests being done in the way that you desceibe and it always lead to cascading tests which slowed down pipelines for no reason.

Also, by doing dependency like this you are violating an important rule: 'UT should break for one reason', it should not break because some other test broke.

Lastly, you are preventing yourself from running those concurrently which is very important should your codebase ever become very big.

3) I agree it is not convinient but not impossible. For most of the tests you can simply mock this method to return what you want it to return. However, I can imagine that this might be too time consuming and maybe hard to maintain (?). I would let it slide, I don't think it would provide much gain vs cost.

4) I personally would use inheritance to pass the values around, global variables take away a freedom of modyfying input to test one specific thing. However, I think it is personal choice, if you would be working with a team you would probably have some guidelines about that.

5)

a) As I expressed in 1), I would not utilize your approach. I would rather create a base class for all the tests and create one test class per class tested. There are multiple reasons for that however, the most important one is that the classes might diverge in the future and you would have to rewrite your suite. I don't mind duplication a long as it is justified.

b) In general, I would prefer to use self.assert* instead of assert x == y (see unittest.TestCase). It gives much more information than just simple True/False.

c) I would not add any randomness to UT. From my experience, it only provides confusion and heisenbugs. Imagine that you have a pipeline with tests, one test failes, you rerun the pipeline and the test passes. Now, you can do two things: 1. Say it was a transient issue so you will not look into it, maybe some build problems, maybe one of the test servers failed - who knows. 2. Spend time to rerun the test X times until the random generator creates a failing test case.

However, if you would create non-random tests, you could detect the problem locally (you might as well not detect it as well). I prefer reproducibility. Furthermore, it might be the case that you will never randomise a failing sequence because your local setup has a different random sequences than the ones on the server. My opinion on this is strictly for unit tests. For random tests I would use fuzzy testing approach and make it in a different test suite. See this SO question to choose what is the best for you as it all depends.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your advice! Could you give an overview or some pseudocodes of how you would write the tests in this case (testing three types of mappings)? \$\endgroup\$
    – user141240
    Jun 3, 2020 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.