Тестирование и отладка

Тестирование тем важнее для проекта, чем проект сложнее, чем большее программистов над ним работает и чем больше времени занимает разработка. Тем не менее и для олимпиадных задач (из-за их сложности и нестандатности) тестирование очень актуально.

Тестирование отнимает много времени на олимпиадах, и часто "почти правильные" решения не получается сдоделать и сдать из-за сложностей с отладкой.

Виды тестирования:

Главный недостаток ручного тестирования: нужно тестировать каждый раз когда программа меняется, даже если изменился кусок кода от другого разработчика, наша часть могла перестать работать. При росте размера проекта количество практически одновременных изменений в различных кусках кода непрерывно возрастает, и количество тестов, которые нужно сделать чтобы убедиться что "мы ничего не сломали"  тоже возрастает. Начиная с некоторого объема проекта такое ручное тестирование становится слишком трудоёмким,  а следовательно, этим тестированием  пожертвуют в первую очередь и не будут выполнять. Именно по этой причине лучше сразу же делать модульные тесты.

Любая технология тестирования не позволяет гарантировать безошибочность программы (не позволяет гарантированно отловить все ошибки). Т.к. невозможно проверить все пути исполнения программы за исключением простейших случаев.

Тестирование циклов

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

Ошибка на единицу (off-by-one) — цикл выполняется на одну итерацию больше или меньше нужного. Типичные случаи: условие i <= n вместо i < n (лишняя итерация и обращение к элементу a[n] за границами массива); условие i < n - 1 вместо i < n (пропущен последний элемент); начало цикла с 1 вместо 0 (пропущен первый элемент). Такая ошибка видна не на всех тестах: например, на пустом массиве программа с ошибкой на единицу может дать правильный ответ.

Тестирование цикла с инвариантом. Инвариант цикла — утверждение о значениях переменных, которое верно перед первым шагом, остаётся верным после каждого шага и вместе с условием выхода даёт нужный результат. Для суммы инвариант такой: перед шагом с номером i в переменной s записана сумма a[0] + ... + a[i-1]. Проверяются три свойства:

Инвариант удобно проверять прямо в тесте: после цикла проверяется условие i = n. В ошибочной версии ниже инвариант выполняется на каждом шаге, потому что каждый учтённый элемент прибавлен правильно. Нарушается только условие завершения: для непустого массива цикл останавливается на i = n - 1. Поэтому такой тест находит ошибку даже тогда, когда сумма случайно совпала с правильной, как в тесте «все нули».

Пример ниже содержит ошибку на единицу (условие i < n - 1) и набор тестов, который её находит. Тест проверяет и сумму, и условие завершения: число обработанных элементов должно равняться n. Программа не останавливается на первой ошибке, а печатает все проваленные тесты и итог для каждой версии.

Реализация на C++

// Тестирование цикла: сумма всех n элементов массива.
// Инвариант цикла: перед шагом с номером i в s лежит сумма a[0] + ... + a[i-1].
// На выходе из цикла должно быть i = n, то есть обработаны все элементы.
#include <cstdio>
#include <iterator>
#include <vector>

// Результат: сумма и значение i на выходе из цикла
struct SumResult {
  int sum;
  int processed;
};

// Ошибка на единицу: условие i < n - 1 пропускает последний элемент
SumResult sum_buggy(const std::vector<int>& a) {
  int n = static_cast<int>(a.size());
  int s = 0;
  int i = 0;
  for (; i < n - 1; ++i) {
    s += a[i];
  }
  return {s, i};
}

// Исправленная версия: условие i < n
SumResult sum_fixed(const std::vector<int>& a) {
  int n = static_cast<int>(a.size());
  int s = 0;
  int i = 0;
  for (; i < n; ++i) {
    s += a[i];
  }
  return {s, i};
}

// Эталон: сумма по определению
int sum_reference(const std::vector<int>& a) {
  int s = 0;
  for (int x : a) {
    s += x;
  }
  return s;
}

struct TestCase {
  const char* name;
  std::vector<int> input;
};

const TestCase kTests[] = {
    {"пустой массив", {}},
    {"один элемент", {7}},
    {"последний элемент ненулевой", {1, 2, 5}},
    {"все нули", {0, 0, 0}},
};

using SumFunction = SumResult (*)(const std::vector<int>&);

// Печатает проваленные тесты и итог.
// Тест проваливается, если неверна сумма или цикл обработал не все n элементов.
void run_tests(const char* version, SumFunction sum) {
  int failed = 0;
  for (const TestCase& t : kTests) {
    int n = static_cast<int>(t.input.size());
    int expected = sum_reference(t.input);
    SumResult r = sum(t.input);
    if (r.sum != expected || r.processed != n) {
      ++failed;
      std::printf("  %s: сумма %d (ожидалось %d), обработано %d из %d\n", t.name, r.sum, expected, r.processed, n);
    }
  }
  std::printf("%s: провалено тестов %d из %zu\n", version, failed, std::size(kTests));
}

int main() {
  run_tests("ошибочная версия", sum_buggy);
  run_tests("исправленная версия", sum_fixed);
  return 0;
}

Результат работы программы:

  один элемент: сумма 0 (ожидалось 7), обработано 0 из 1
  последний элемент ненулевой: сумма 3 (ожидалось 8), обработано 2 из 3
  все нули: сумма 0 (ожидалось 0), обработано 2 из 3
ошибочная версия: провалено тестов 3 из 4
исправленная версия: провалено тестов 0 из 4

Тест «пустой массив» ошибку не находит: при n = 0 условие i < n - 1 ложно сразу, и сумма, и число обработанных элементов совпадают с ожидаемыми. Тест «один элемент» находит ошибку и по сумме (0 вместо 7), и по условию завершения (0 элементов вместо 1). Тест «все нули» проходит по сумме, но не проходит по условию завершения: обработано 2 элемента из 3. Исправленная версия с условием i < n проходит все тесты.