# Test Coverage and Test Case generation

## Test vector

Test Vector - набор входов, которые мы подаем на вход тестируемой системе. Подробнее см [тут](https://en.wikipedia.org/wiki/Test_vector).
Мы включаем в test vector те параметры, которые влияют на тестируемую систему. Или могут/должны влиять. Хотя, если это делать по полной программе, то test vector будет очень сложный, поэтому часто мы вводим ограничения (игнорируем те или иные параметры/пути влияния на тестируемую систему).

### **NB** Static fields and external state

В принципе, static fields в Java могут быть доступны (прямо или косвенно) из любого кода, и, таким образом, влияеть на его поведение. Т.е. в идеале нам надо включать чуть ли не все статические поля в test vector.
Однако, все же они используются не так часто, да и влияние может ограничиться одним/двумя полями.
Поэтому по умолчанию, мы не включаем статические поля в тестовые вектора, кроме случаев, когда нам известно, что они оказывают влияние и мы решили, что это нужно тестировать.

Аналогично, внешнее состояние - например, файлы на диски, записи в БД, сокеты/порты - также влияют на тестируемую систему. Если мы открываем файл с тем или иным именем, то поведение зависит от того, существует такой файл или нет, прав доступа и т.д.
По аналогии, мы не включаем внешнее состояние в test vectors, без необходимости.

### Unit testing

В случае Unit testing, у нас есть два основных случая:
* static methods. Для них test vector будет набор параметров этого метода.
* member methods. В данном случае, test vector помимо параметров метода будет включать в себя еще и неявный параметр this.

## Test coverage

Исключая тривиальные случаи, обычно кол-во всевозможных вариантов test vectors настолько велико, что мы не сможем перебрать их за разумное время. Поэтому нам так или иначе нужна какая-то стратегия выбора конечного ограниченного набора тестовых случаев (будем считать что каждому тестовому случаю соответствует test vector и наоборот, test vector задает тот или иной тестовый случай).

Обычно, стратегии выбора тест кейсов опираются на тот или иной критерий тестового покрытия (test coverage). Я также буду использовать термин Генерация Тесткейсов (test vectors) для обозначения систематического подхода к формированию того или иного набора тесткейсов (тестовых векторов) для достижения тех или иных целей (тестового покрытия).

### Code coverage

Один из вариантов, это когда test coverage определяется исходя из того, какие куски кода (методы, инструкцим, строчкм, бранчи) были задействованы при исполнении/применении test vector'а (или набора оных).
Соответственно, полный набор тестов (full coverage) это когда набор тестовых случаев (test vectors) в совокупности задействует весь код, согласно тому или иному критерию (классы, методы, строчки, бранчи, инструкции).
При юнит тестировании мы как правило опираемся на покрытие кода тестируемого юнита. Но не забываем и про документацию/спецификацию.

### Specification coverage

При функциональном тестировании, при генерации тестовых случаев обычно исходят из спецификации, ибо код может меняться или отстутствовать. Также может быть несколько реализаций одной спецификации.
Поэтому и критерий покрытия должен быть основан на спецификации. Однако, чтобы был какой-то вычислимый критерий (как в случае кода), нам нужна формальная спецификация. Тогда можно говорить о формальном покрытии спецификации тестовыми случаями (векторами).
Зачастую даже неформальная документация отсутствует. Поэтому разработаны методы неформальной генерации тестовых случаев.
Также можно разработать формальные модели, специиально для генерации тестовых случаев.

## Test generation methods

Я знаю 4 базовых подхода к генерации тестовых случаев (векторов) по неформальной документации:
* Assertion testing. Заводим (по крайней мере, один) тестовый случай на каждое утверждение, которое мы встречается в документации/спецификации. Либо, на утверждение, которое следует неявно из документации/кода. К примеру, аннотация @NonNull намекает что метод ведет себя по разному, в зависимости от того, передали ли ему null или non-null значение в данном параметре.
* Equivalence class partitioning. Разбиваем всевозможные варианты test vectors на набор эквивалентныеъх классов, и включаем в тестовый набор, по крайней мере, по одному представителю каждого класса. См подробнее [Equivalence class partitioning](https://en.wikipedia.org/wiki/Equivalence_partitioning)
* [Boundary value analysis](https://en.wikipedia.org/wiki/Boundary-value_analysis).
* Cause and Effect. Не знаю что такое, но оно существует :).

## Пример ECP для XorKeyDatabase

Рассмотрим ECP для XorKeyDatabase#createStorage(name) метода.
Это не-статические метод, т.е. у нас в тестовом векторе будут две компоненты:
* this (типа XorKeyDatabase)
* storageName (типа String)

Рассмотрим для начала разбиение на классы "эквивалентности" для отдельных компонентов тестового вектора.
Я использую кавычки, чтобы подчеркнуть что вообще говоря это не совсем классы эквивалентности. Ибо последние определяются для всего тест вектора. Однако, для удобства мы сперва рассматриваем что-то типа классов эквивалентности для отдельных параметров (компонетов тестового вектора).

### Классы "эквивалентности" для this

В принципе, это может быть любой инстанс XorKeyDatabase включая подклассы. Но для целей юнит-тестирования мы ограничиваемся только инстансами самого класса XorKeyDatabase. Но так как это абстрактный класс, то надо взять существующий подкласс, либо создать свой, специально для целей тестирования.
У конструктора XorKeyDatabase два параметра, т.е. два под-компонента тестового вектора:
* backingDataSource
* sourceNameHasher

#### backingDataSource
В контексте юнит-тестов, первый напрямую не используется, лишь передается другим юнитам. Т.е. при юнит тестировании нам нет необходимости как-то его покрывать тестами. Поэтому можно использовать любой удобны DataSource, например, HashMapDataSource.

Но вот содержимое backingDS (кол-во записей, ключи, значения и т.д.) будет иметь значение с точки зрения тестирования функциональности. Ведь один и тот же backingDS используется для хранения содержимого разных сториджей. Поэтому типовый набор классов "эквивалентности" тут такой:
* null
* empty DS
* DS with one storage
* no entries (if possible)
* one entry
* many entries
* DS with two (or more) storages
* empty
* one entry
* etc

#### sourceNameHasher
А вот sourceNameHasher используется в коде тестируемого юнита, но использование его довольно прямолинейное. Поэтому я бы предложил такие классы "эквивалентности":
* null
* identity
* non-identity function (injective)

В данном случае, не вижу особой необходимости использовать какие-то более сложные случаи.

### Классы эквивалентности для (storage) name

Поскольку это просто строчка, неинтерпретируемая в контексте ДБ, то я бы предложил стандартный набор:
* null
* пустая строчка
* непустая строчка

Однако, важно учитывать, что так как для разных сториджей используется один и тот же бэкинг, то ключи могут клэшиться. И именно сторидж name играет роль в предотвращении этого. Поэтому пустая строчка или слишком короткая строчка, возможно, должна считаться неправильным вариантом, ибо плохо предотвращает clashes.

### Классы эквивалентности test vectors

Итак у нас test vector фактически состоит из трех компонентов:
* backingDS
* sourceNameHasher
* storageName

Рассмотрим теперь (истинные) классы эквивалентности для полных test vectors. Которые получаются комбинированием и уточнением ранее рассмотренных классов эквивалентности для отдельных компонентов.

#### Invalid parameters group
Типовый набор классов эквивалентности - это когда один параметр или их комбинация не валидные, т.е. должны приводить к эксепшену или к другому abnormal поведению.
Обычно имеет смысл завести отдельный класс эквивалентности на каждый кривой вариант каждого параметра.
Например, в случае backingDS и sourceNameHasher кривой вариант всего один - null. В случае storageName это тоже null, но возможно пустую строчку тоже можно рассматривать как invalid (в зависимости от спецификации, документации и проч).
Поэтому в данной группе будут такие эквивалентные классы test vectors:
* backingDS==null, остальные компоненты вектора - любые валидные значения
* sourceNameHasher==null, остальные компоненты - любые валидные значения
* storageName==null, остальные компоненты - любые валидные значения
* опционально, storageName="", остальные компоненты - любые валидные значения

В принципе, можно тестировать и комбинации инвалидных значений. Но важно, чтобы были тестовые кейсы, когда в тестовом векторе ровно один параметр не валиден. Ибо наличие второго инвалидного значения может "замаскировать" отсутствие проверки для первого инвалидного значения (если такая ошибка допущена в коде, к примеру).

#### Valid parameters group

Отметим что sourceNameHasher можно тестировать независимо от остальных компонентов, ибо он просто преобразует storageName. А вот между backingDS и storageName есть зависимость: например backingDS может содержать storageName, а может не содержать.
Поэтому у нас тут две подгруппы эквивалентных классов: для sourceNameHasher и для пары (backingDS, storageName).

#### sourceNameHasher

Тут все просто:
* sourceNameHasher==identity
* sourceNameHasher==non_identity

Остальные могут быть какие-то валидные параметры по вкусу. Наличие невалидных параметров означает что это тестовый вектор из другого класса эквивалентности (из невалидной группы).

#### BackingDS and storageName interaction

* empty backingDS
* some nonempty storageName
* DS with one storage (мы создали XorDB и вызвали метод createStorage в рамках test set up), no entries
* storageName with the same name
* storageName with some other name
* DS with one storage and some entries
* storageName with the same name
* storageName with some other name
* DS with two storages (создали пустой, и вызвали два раза createStorage с разными именами), both are empty
* storageName with one of the existing names
* storage with some other name
* DS with two storages, one empty, another with entries
* similar cases
* DS with two storages, both with entries

Довольно много вариантов, но они дают более менее полноценное тестирование.
В принципе, возможны еще варианты - например, если два непустых сториджа, то у них могут быть entries с одинаковыми ключами (потенцильный клэш), а могут - с разными.

### Дополнительные проверки

У перечисленных выше классов эквивалентности, тестовый код может сильно различаться. К примеру, для invalid случаев мы ожидаем вылетания эксепшенов. А для валдиных, нам надо проверить, что возвращаемы сториджи рабочие, т.е. туда можно класть значения и получать их обратно, а также удалять.
Но в некоторых случаях проверки будут сложнее. К примеру, у нас DS с двумя сториджами с разными именами. Нам надо проверить, что они изолированы друг от друга, т.е. когда мы кладем или удаляем ключи в один сторидж, то это не влияет на другой сторидж.
К примеру, мы положили в первый сторидж по ключу A значение B, а во второй - по тому же ключу A но другое значение - С. Нужно проверить, что в первом сторидже, по ключу A все также лежит B, а во втором - С.
Аналогично можно удалить из сториджа ключ A и убедиться, что это не повлияло на другой.

ЗЫ понятно, что можно найти случаи когда будут клэши и взаимовлияние, но такова уж идеология XorDB, т.е. мы принимаем такой риск.

### Test Generation Automation

Часто это все нетрудно автоматизировать. Самое главное - сделать ECP (equivalence class parititioning) analysis для отдельных параметров. А также продумать интеракции, и доработать анализ ECP для интеракций.
Ну а потом можно просто в цикле это все перебрать, если вариантов получается не слишком много.
Если получается много, то важно выделить базовые варианты:
* экивалентные классы для test vectors на каждый возможный эквивалентный класс для отдельных параметров - к примеру, если 10 параметров, в каждом по 5 EC, то получается 50 тесткейсов, вместо 5^10.
* эквивалентные классы для самых важных комбинаций

Остальные варианты можно перебирать с помощью случайного перебора (quickcheck, property testig), либо [Pairwise testing](http://www.pairwise.org/), либо каких-то кастомизированных генерилок/перебиракок.