Stress-tester

Часто возникает проблема, что не хочется дебажить решение, а постресстестить с гарантированно правильным. Проект позволяет сгенерировать рандомные тесты и сравнить два решения, возможно на разных языка программирования.

Запуск

Для запуска необходимо иметь установленную Java версии выше 17 (т.е. утилиты javac, java, jar), а также инструменты для запуска на языке ваших решений.

./stress-test.sh <config-file> <good-solution> <bad-solution>

где good-solution -- решение, которое гарантированно работает, bad-solution -- тестируемое решение, config-file -- файл специального вида, описывающий конфигурацию входного файла.

Обратите внимание, что здесь рассчитывается на то, что ваше решение помещается в один файл. Иначе можно отправить проект, например, в Make (когда будет реализована его поддержка).

Поддерживаемые языки

В данный момент поддерживаются языки C++ и Java. Следите за обновлениями!

Остановка

Попытка остановить скрипт через ^C не всегда может завершиться успехом. Теперь рассмотрим остановки, вызванные окончанием работы тестера:

1. Нашелся тест, на котором ответы двух решений не совпали. В таком случае в папке, из которой вы запускались, появится файл failed_test_input, в котором и будет лежать этот тест.
2. На экране выведено сообщение о том, что все тесты пройдены. Из этого не следует, что решения идентичны, просто тестер не смог попасть в подходящий тест. В таком случае советуется либо повысить количество тестов, либо увеличить параметры входных данных.
3. Скрипт закончил работу с ошибкой на одном из тестов. Тогда тестер выведет сообщение об ошибке, и продолжит запускать программы на других тестах. Поведение в этом случается объявляется UB, и крайне рекомендуется не допускать такого рода ошибок.
4. Bad-solution упало с ошибкой. Аналогично п.1, в соответствующий файлик выведен тест. Если с ошибкой упало good-solution, то такой тест объявляется невалидным, и не учитывается в тестировании.

Config-file

Объявление переменных происходит по схеме: <name-of-var>: <Declaration>. Имя может состоять только из букв латинского алфавита и нижнего подчеркивания. Про объявления см. ниже. Если вы не хотите указывать имя переменной, вы можете оставить имя пустым: : <Declaration>. На именнованную переменную можно будет ссылаться в дальнейшем.

При описании будет использоваться одно общее правило: одна значимая строка конфига == одна строка генерируемого файла. Т.е. если вы хотите сгенерировать на разных строках числа n, m, то необходимо писать их объявления на разных строках конфига.

Под значимой понимается непустая строка, не являющаяся комментарием, и не описывающая арифметическое выражение.

Если же вы хотите сгенерировать их в одной строке, то необходимо писать объявления в одной строке через запятую:

n: <Declaration-for-n>, m: <Declaration-for-m>

Описание целочисленных примитивов

Для описания char'ов, int'ов и long'ов используется следующий синтаксис:

<name-of-var>: char in [<left-bound>; <right-bound>]
<name-of-var>: char in ['<left-as-ascii>'; '<right-as-ascii>']
<name-of-var>: int in [<left-bound>; <right-bound>]
<name-of-var>: long in [<left-bound>; <right-bound>]

Разумеется, левая граница должна быть не больше правой, и они должны быть в том типе, в котором указана переменная.

Описание дробных примитивов

Синтаксис аналогичен целым типам.

<name-of-var>: float in [<left-bound>; <right-bound>]
<name-of-var>: double in [<left-bound>; <right-bound>]

При возможности не использовать дробные типы, старайтесь их не использовать.

Описание массивов

Есть два способа задать массив:

<name-of-var>: array len in [<left>; <right>] of {<Type>}
<name-of-var>: array len is <name-of-len-var> of {<Type>}

Ясно, что в Type описывается хранимый в массиве тип. В первом случае длина массива будет генерироваться в указанных пределах, во втором случае --- будет использоваться значение, сгенерированное <name-of-len-var>.

Описание строк

<name-of-var>: string len in [<left>; <right>] of [<left-char>; <right-char>]
<name-of-var>: string len is <name-of-len-var> of [<left-char>; <right-char>]

Описание строк в таком виде синтаксически эквивалентно объявлению массива символов:

<name-of-var>: array len in [<left>; <right>] of {char in [<left-char>; <right-char>]}

Описание рандомных групп

В случае, когда хочется сгенерировать случайное значение из указанного списка, следует использовать конструкцию rnd: пример приведенный ниже выдает каждую из строчек равновероятно

: rnd in {"abc", "abs", "bcd"}

Обратите внимание, что разрешены списки численных типов или строк.

Арифметические выражения

Доступны арифметические операции min, max, +, -, *, /, unary -, abs. Обратите внимание, что операции возможны только над типом int, при использовании других численных примитивов -- UB, при использовании нечисленных -- ClassCastException.

Обратите внимание, что слева от знака = должна стоять "свежая переменная" -- та, что ранее не была объявлена.

КС-грамматика, описывающая синтаксис

STRT -> (Line)*
Line -> Decl(, Decl)*
Decl -> Type
Decl -> Name: Type
Line -> next Name lines {Line(;Line)*}
Line -> $(Name = Expr)

Type -> char in [Char; Char]
Type -> int in [IInt; IInt]
Type -> long in [IInt; IInt]
Type -> float in [DInt; DInt]
Type -> double in [DInt; DInt]
Type -> string len in [UInt; UInt] of [Char; Char]
Type -> string len is Name of [Char; Char]
Type -> array len in [UInt; UInt] of { Type }
Type -> array len is Name of { Type }
Type -> rnd in {CnsV(, CnsV)*}

Expr -> Trm1 max Expr | Trm1 min Expr | Trm1
Trm1 -> Trm2 + Trm1 | Trm2 - Trm1 | Trm2
Trm2 -> Trm3 * Trm2 | Trm3 / Trm2 | Trm3
Trm3 -> abs Trm3 | -Trm3 | Trm4
Trm4 -> IInt | Name | (Expr)

Name -> [a-zA-Z_]+
UInt -> [1-9][0-9]*
BInt -> -?UInt
IInt -> BInt | Name
DInt -> BInt(.[0-9]*)? | Name
Char -> 'ascii char'
Char -> BInt | Name
CnsV -> "Name" | IInt | DInt

Примеры конфигураций

Генерация случайной двоичной матрицы N x M.

n: int in [1; 100], m: int in [1; 100]
a: array len is n of {array len is m of {int in [0; 1]}}

Генерация случайной строки из строчных букв латинского алфавита (приведены три эквивалентных способа задания).

s1 : string len in [1; 100] of ['a'; 'z']

s2 : string len in [1; 100] of [97; 122]

n: int in [1; 100]
s3 : string len is n of ['a'; 'z']

Генерация массива длины 2N.

n: int in [1; 100]
$(n = 2 * n)
a: array len is n of {int in [-100; 100]}

Обратите внимание!

Иногда для "вынесения копипасты" вам захочется вынести одинаковые объявления в одну переменную. Это ошибка!

Следующие два кода не эквивалентны:

// правильный код
n: int in [1; 100]
a: array len is n of {int in [1; 100]}

// неправильный код
n: int in [1; 100]
a: array len is n of {n}

Дело в том, что генератор "кешируют" свое последнее сгенерированное значение, а массивы вытягивают из генераторов длины именно закешированное значение.

Напоминание

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

Некоторые ограничения

Поскольку проект еще находится в разработке, возникают некоторые ограничения, любое их нарушение -- UB:

1. Хорошее решение не должно вылетать с ошибкой на любом входном значении, сгенерированном по заданному конфигу.
2. Конфиг должен парситься правильно. Также стоит передавать в типы длины массива только беззнаковые типы не больше int'а (т.е. int или char с левой границей >= 0)
3. Следите за форматом вывода решений. Если одно выводит \n в конце, а другое нет, то вам скажут, что решение не равны именно на этом тесте.
4. Также касаемо формата вывода: поскольку ответы сравниваются посимвольно, то если ответ будет в типе double, то возникнут проблемы вида 0.03 != 0.030. В связи с чем настойчиво рекомендуется указывать количество символов после запятой.
5. Не советуется иметь папки с именами tests, OUT, файлы с именами .out1, .out2, failed_test_input, stress-test.jar, MANIFEST.MF, т.к. по завершении работы тестера, такие файлы будут удалены.

Обновления

1. (25.05.2023) Добавлена поддержка комментариев. Строки, начинающиеся с '%' будут проигнорированны.

2. (26.06.2023) Добавлена возможность указывания именных переменных в range: теперь разрешены конструкции вида

   n: int in [1; 100], l: int in [1; 3]
   a: array len is n of { int in [0; l] }
   

   При попытке воспользоваться необъявленной переменной будет брошена ошибка. На момент объявления объявления некоторой переменной x объявленными считаются те, что описаны строго раньше x.

3. (29.06.2023) Добавлена поддержка арифметических операций.

4. (29.06.2023) Добавлена обработка исключений в запускающий скрипт.

5. (06.07.2023) Исправлена генерация строк. Добавлена генерация из указанного списка константных значений.

Обратная связь

Понравился проект? Поставь звездочку, в будущем планируется большое количество обновлений и улучшений.

По всем вопросам обращаться в telegram: @mavlyut_e.

Если вы видите какие-то проблемы, то можете сообщить о них, либо открыть Pull Request.