On 07/12/2012 10:57 AM, MasterZiv wrote:

> Встречались. Любая программа сложнее Hello word уже такая.

Во, код.

[src C++]
caddr_t
bif_concatenate_2_narrow_strings (caddr_t * qst, caddr_t * err_ret, state_slot_t
** args)
{
caddr_t a, b, src;
int len = 0;
caddr_t res;
int n_args;

n_args = BOX_ELEMENTS (args);
if (n_args > 2)
GPF_T;

a = bif_string_or_uname_or_wide_or_null_arg (qst, args, 0, "concat");
b = (n_args == 2) ? bif_string_or_uname_or_wide_or_null_arg (qst, args, 1,
"concat") : NULL;

if (IS_WIDE_STRING_DTP (DV_TYPE_OF (a)) || IS_WIDE_STRING_DTP (DV_TYPE_OF (b)))
GPF_T;

if (a && b)
{
len = strlen(a) + strlen(b);
res = dk_try_alloc_box (len + 1, DV_LONG_STRING);
strcpy(res,a);
strcat(res,b);
}
else
{
src = a ? a : b;
len = src ? strlen(src) : 0;
res = dk_try_alloc_box ( len ? len + 1 : 0, len ? DV_LONG_STRING : DV_NULL);
strcpy(res,src);
}
return res;
}

[/src]

Простой, примитивный.
А посчитай-ка пути ?

Столкнулся с необходимостью написания генерации тестов для покрытия кода (язык программирования — некоторое подмножестве Java: есть доступ только к БД, никакого другого ввода-вывода (включая доступ к таймеру и Random); приложение строго однопоточное).

Решено покрывать пути выполнения. Но в той же Википедии написано, что проблема полного покрытия кода аналогична проблеме остановки. Но посмотрите на проблему остановки, как там сформулировано доказательство -- ведь это весьма сложная программа, получается.

Создается впечатление, что проблема надумана. Ну да, для 0.00...001% программ, встречающихся на практике, нельзя будет определить, останавливаются ли они (и покрыть их на 100% тестами). Но для остальных 99.9999...9% явно это можно сделать.

Так вот вопрос: встречались ли вам программы, у которых нельзя было бы покрыть все трассы выполнения? Можете ли привести пример таких программ?

Здравствуйте, malphunction, Вы писали:

День добрый,

Вам дисертацию нужно написать на эту тему или покрыть тестами конкретную программу?

В первом случае вам лучше в http://rsdn.ru/forum/philosophy/

Во втором же, берите и покрывайте. Нудно, возможно долго, но реально.
Можете на PEX глянуть.

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


СУВ, Aikin

> Так вот вопрос: встречались ли вам программы, у которых нельзя было бы покрыть
> все трассы выполнения? Можете ли привести пример таких программ?

Встречались. Любая программа сложнее Hello word уже такая.
Каждый if умножает пути в два раза. Каждый цикл -- в число выполнений
цикла. Очень быстро дойдёшь до очень больших чисел.
Ван-Тассела почитай, ещё у него было это всё подробно расписано.

А тестами покрывать нужно не пути выполнения в программе,
а результаты её работы. С уделением внимания характерным точкам,
особым случаям.

Из всего этого следует только одно — coverage не дает 100% гарантии, но он таки нужен, чтобы хоть раз пробежать пути, не используемые в продукте.

Сорри. Не "не используемые в продукте", а "используемые в редких хитрых случаях".

Требование coverage стимулирует писать юнит-тесты именно для этих закоулков.

Как минимум coverage надо сочетать с тестированием крайних случаев входных данных и крайних случаев внутренних полуконстант типа "количество блоков, обрабатываемых за один раз".

А если задача многотредовая — то стресс-тест просто обязателен.

Здравствуйте, Aikin, Вы писали:

A>Вам дисертацию нужно написать на эту тему или покрыть тестами конкретную программу?

Я действительно пишу диссертацию, которая касается данной темы.

Но ещё я веду несколько промышленных проектов, где автоиматическое тестирование имеет место.
Поэтому тема интересует с двух сторон.

Спасибо за ответ!

A>Во втором же, берите и покрывайте. Нудно, возможно долго, но реально.
A>Можете на PEX глянуть.

Ага, тоже хорошо.

A>Но я, все же, советовал бы покрывать бизнесс сценариями, а не добиваться искуственного 100% покрытия.

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

Здравствуйте, MasterZiv, Вы писали:

MZ>On 07/12/2012 10:57 AM, MasterZiv wrote:

>> Встречались. Любая программа сложнее Hello word уже такая.

MZ>Во, код.

MZ>[src C++]
MZ>caddr_t
MZ>bif_concatenate_2_narrow_strings (caddr_t * qst, caddr_t * err_ret, state_slot_t
MZ>** args)
MZ>{
MZ> caddr_t a, b, src;
MZ> int len = 0;
MZ> caddr_t res;
MZ> int n_args;

MZ> n_args = BOX_ELEMENTS (args);

// Это два пути (точнее, два множества путей, первое множество путей, где n_args > 2,
// второе -- где n_args <= 2)

MZ> if (n_args > 2)
MZ> GPF_T;

// Тут вызов вложенной функции, допустим, даёт n1 путей

MZ> a = bif_string_or_uname_or_wide_or_null_arg (qst, args, 0, "concat");

// Тут 2 * n1 (где n1 -- пути в функции bif_string_or_uname_or_wide_or_null_arg)

MZ> b = (n_args == 2) ? bif_string_or_uname_or_wide_or_null_arg (qst, args, 1,
MZ>"concat") : NULL;

// Пусть макрос IS_WIDE_STRING_DTP раскрывается в функцию, которая даёт n2 путей
// А макрос DV_TYPE_OF -- в n3 путей
// Итого этот вызов -- n2*n3*n2*n3

MZ> if (IS_WIDE_STRING_DTP (DV_TYPE_OF (a)) || IS_WIDE_STRING_DTP (DV_TYPE_OF (b)))
MZ> GPF_T;

// Тут три пути:
// 1: a = False, b = любое
// 2: a = True, b = False
// 3: a = True, b = True

MZ> if (a && b)
MZ> {
// strlen как встроенная функция не увеличивает количество путей
MZ> len = strlen(a) + strlen(b);
// dk_try_alloc_box -- n4 путей.
MZ> res = dk_try_alloc_box (len + 1, DV_LONG_STRING);
MZ> strcpy(res,a);
MZ> strcat(res,b);
MZ> }
MZ> else
MZ> {
MZ> src = a ? a : b;
MZ> len = src ? strlen(src) : 0;
MZ> res = dk_try_alloc_box ( len ? len + 1 : 0, len ? DV_LONG_STRING : DV_NULL);
MZ> strcpy(res,src);
MZ> }

// Итого, после блока if(a&&b) -- 3 * n3 путей

MZ> return res;
MZ>}
MZ>[/src]

MZ>Простой, примитивный.
MZ>А посчитай-ка пути ?

Итого: 2 * n1 * 2 * n1 * n2 * n3 * n2 * n3 * 3 * n3 = 12 * (n1 * n2 * n3) ^ 2 путей.

Возьмем (с потолка) n1 = n2 = n3 = 100 путей; тогда получится 12 000 000 000 000 путей.

Предположим, за секунду выполняется 10000 прогонов. И гоняем на восьми ядрах.
Тогда получится ~5 лет на полное покрытие.

Так что ли?

Тогда да, много

Здравствуйте, MasterZiv, Вы писали:

>> Так вот вопрос: встречались ли вам программы, у которых нельзя было бы покрыть
>> все трассы выполнения? Можете ли привести пример таких программ?

MZ>Встречались. Любая программа сложнее Hello word уже такая.
MZ>Каждый if умножает пути в два раза. Каждый цикл -- в число выполнений
MZ>цикла. Очень быстро дойдёшь до очень больших чисел.

Так в формулировке теоремы идея-то не в больших числах, а, как я понял,
в принципиальной неперичеслимости всех путей.

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

MZ>Ван-Тассела почитай, ещё у него было это всё подробно расписано.

Вы имеете ввиду книгу "СТИЛЬ, РАЗРАБОТКА, ЭФФЕКТИВНОСТЬ, ОТЛАДКА И ИСПЫТАНИЕ ПРОГРАММ" ?
Спасибо за наводку, почитаю.

MZ>А тестами покрывать нужно не пути выполнения в программе,
MZ>а результаты её работы. С уделением внимания характерным точкам,
MZ>особым случаям.

Ну это-то понятно. Интересовал универсальный подход.

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Из всего этого следует только одно — coverage не дает 100% гарантии, но он таки нужен, чтобы хоть раз пробежать пути, не используемые в продукте.

Вопрос был не про нужность coverage, а про существование промышленных программ, принципиально не покрываемых тестами.

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Сорри. Не "не используемые в продукте", а "используемые в редких хитрых случаях".
MSS>Требование coverage стимулирует писать юнит-тесты именно для этих закоулков.
MSS>Как минимум coverage надо сочетать с тестированием крайних случаев входных данных и крайних случаев внутренних полуконстант типа "количество блоков, обрабатываемых за один раз".
MSS>А если задача многотредовая — то стресс-тест просто обязателен.

Я спрашивал не про философию, а про пример программы, принципиально не поддающейся coverage.

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

Приведённая выше MasterZiv программа тоже даёт огромное количество путей, но и оно конечно и перечислимо,
так что если задаться целью 100%-покрыть приведенный им фрагмент, то любая современная фирма средней руки
сделает это за приемлемое время (хоть и потратит кучу денег на кластер. Но всё же сделает это).

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

Здравствуйте, malphunction, Вы писали:

m> Лет через 10 квантовые компы будут в каждом утюге,
Скорость работы компов ограничена хотя бы физически, а сложность задач — только полётом фантазии. Какова фантазия практических очередных систем документообора — другой вопрос. Тема "Проблема остановки на практике" не говорит об этом ничего толком... так что как только задашь формальные требования — так и появится ответ насколько это "проблема".

Здравствуйте, ., Вы писали:

.>Здравствуйте, malphunction, Вы писали:

m>> Лет через 10 квантовые компы будут в каждом утюге,
.>Скорость работы компов ограничена хотя бы физически, а сложность задач — только полётом фантазии. Какова фантазия практических очередных систем документообора — другой вопрос. Тема "Проблема остановки на практике" не говорит об этом ничего толком... так что как только задашь формальные требования — так и появится ответ насколько это "проблема".

Полёт фантазии тоже ограничен физически. Шибко нафантазированные программы просто работать не будут, поэтому и не являются промышленными, практичными.

Что же касается этих ваших систем документооборота -- см. http://habrahabr.ru/post/128503/ -- там описывается, как при помощи системы KLEE было покрыто 94% coreutils, в котором нашли, в результате такого покрытия, новых 10 ошибок. Так что не так уж сложно промышленные системы покрывать.

Здравствуйте, malphunction, Вы писали:

Всё-таки не очень правильный рассчет. Я считал, что вызовы функций дают много путей (n1, n2 и n3).
Но давайте протестируем и отладим эти функции отдельно. Окей, теперь каждая из них будет давать только
один путь. Тогда формула 12 * (n1 * n2 * n3) ^ 2 путей даст нам только 12 путей. Уж их-то без проблем
можно покрыть даже на современном, маломощном, не квантовом, железе.

M>Здравствуйте, MasterZiv, Вы писали:

MZ>>On 07/12/2012 10:57 AM, MasterZiv wrote:

>>> Встречались. Любая программа сложнее Hello word уже такая.

MZ>>Во, код.

MZ>>[src C++]
MZ>>caddr_t
MZ>>bif_concatenate_2_narrow_strings (caddr_t * qst, caddr_t * err_ret, state_slot_t
MZ>>** args)
MZ>>{
MZ>> caddr_t a, b, src;
MZ>> int len = 0;
MZ>> caddr_t res;
MZ>> int n_args;

MZ>> n_args = BOX_ELEMENTS (args);

M>// Это два пути (точнее, два множества путей, первое множество путей, где n_args > 2,
M>// второе -- где n_args <= 2)

MZ>> if (n_args > 2)
MZ>> GPF_T;

M>// Тут вызов вложенной функции, допустим, даёт n1 путей

MZ>> a = bif_string_or_uname_or_wide_or_null_arg (qst, args, 0, "concat");

M>// Тут 2 * n1 (где n1 -- пути в функции bif_string_or_uname_or_wide_or_null_arg)

MZ>> b = (n_args == 2) ? bif_string_or_uname_or_wide_or_null_arg (qst, args, 1,
MZ>>"concat") : NULL;

M>// Пусть макрос IS_WIDE_STRING_DTP раскрывается в функцию, которая даёт n2 путей
M>// А макрос DV_TYPE_OF -- в n3 путей
M>// Итого этот вызов -- n2*n3*n2*n3

MZ>> if (IS_WIDE_STRING_DTP (DV_TYPE_OF (a)) || IS_WIDE_STRING_DTP (DV_TYPE_OF (b)))
MZ>> GPF_T;

M>// Тут три пути:
M>// 1: a = False, b = любое
M>// 2: a = True, b = False
M>// 3: a = True, b = True

MZ>> if (a && b)
MZ>> {
M>// strlen как встроенная функция не увеличивает количество путей
MZ>> len = strlen(a) + strlen(b);
M>// dk_try_alloc_box -- n4 путей.
MZ>> res = dk_try_alloc_box (len + 1, DV_LONG_STRING);
MZ>> strcpy(res,a);
MZ>> strcat(res,b);
MZ>> }
MZ>> else
MZ>> {
MZ>> src = a ? a : b;
MZ>> len = src ? strlen(src) : 0;
MZ>> res = dk_try_alloc_box ( len ? len + 1 : 0, len ? DV_LONG_STRING : DV_NULL);
MZ>> strcpy(res,src);
MZ>> }

M>// Итого, после блока if(a&&b) -- 3 * n3 путей

MZ>> return res;
MZ>>}
MZ>>[/src]

MZ>>Простой, примитивный.
MZ>>А посчитай-ка пути ?

M>Итого: 2 * n1 * 2 * n1 * n2 * n3 * n2 * n3 * 3 * n3 = 12 * (n1 * n2 * n3) ^ 2 путей.

M>Возьмем (с потолка) n1 = n2 = n3 = 100 путей; тогда получится 12 000 000 000 000 путей.

M>Предположим, за секунду выполняется 10000 прогонов. И гоняем на восьми ядрах.
M>Тогда получится ~5 лет на полное покрытие.

M>Так что ли?

M>Тогда да, много