Главная » Хабрахабр » Статический анализ и property-based тестирование: вместе мы сила

Статический анализ и property-based тестирование: вместе мы сила

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

Я разрабатываю Java-инспекции в IntelliJ IDEA, которая большей частью написана на Java. В некотором смысле я нахожусь в привилегированном положении по сравнению с другими программистами: доработать статический анализатор IDE, чтобы находить новый класс ошибок — это моя прямая рабочая обязанность, которая при этом же позволяет найти и обезвредить баги в этой же самой IDE. Хочу поделиться одной такой историей успеха.

В начале октября коллега мне скинул отчёт с зависшим property-based-тестом. Этот тест делает примерно следующее: открывает случайный Java-файл из исходников IDEA, делает некоторые случайные правки, ставит курсор в случайное место, применяет какой-нибудь случайный quick-fix, который в данном месте доступен и тому подобное. Такую штуку коллеги сделали на летнем хакатоне и благодаря ей удалось выловить и обезвредить много багов в инспекциях до того как о них сообщили пользователи. Также воспроизвелись ошибки, о которых когда-то сообщали пользователи, но они почему-то не воспроизводились у нас. В общем, очень полезная штука. Если кому-то интересно, исходники все доступны в community-версии IDEA на GitHub.

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

PsiElement parent = PsiUtil.skipParenthesizedExprUp(expression.getParent());
while (parent instanceof PsiTypeCastExpression || parent instanceof PsiConditionalExpression) { parent = PsiUtil.skipParenthesizedExprUp(expression.getParent());
}

Давайте я расскажу, зачем нужен этот цикл. Конкатенация строк в цикле, как известно, вредна, и часто заменима на StringBuilder. Однако в некоторых случаях предупреждать о такой конкатенации смысла нет. Например, если после каждой конкатенации текущий результат используется:

String dots = "";
for(int i=0; i<10; i++) { dots += "."; pacman.eatSomeDots(dots);
}

Никакого смысла заменять на StringBuilder здесь нет, так как каждая промежуточная строка нужна для передачи в метод. Оптимизировать если и можно, то нетривиально. Вот тут (а точнее чуть ниже) мы и проверяем, как используются вхождения ссылок на строковую переменную. Здесь expression — это очередная ссылка на строку в исходном тексте анализируемой программы (в нашем примере — параметр метода eatSomeDots). Понятно, если мы вызовем eatSomeDots((dots)), или eatSomeDots((String)(dots)), или даже eatSomeDots(flag ? dots : "***"), то строку dots всё равно стоит считать всегда используемой. Поэтому мы и поднимаемся по иерархии выражений вверх, пропуская возможные скобки, приведения типов (PsiTypeCastExpression) и условные операторы (PsiConditionalExpression).

Однако в цикл вкралась банальная опечатка: внутри должно быть не parent = PsiUtil.skipParenthesizedExprUp(expression.getParent());, а parent = PsiUtil.skipParenthesizedExprUp(parent.getParent());. Получилась неприятная ситуация: если всё-таки условие цикла истинно, то parent переприсваивается тому же значению, которое и так имел, в результате чего цикл становится бесконечным.

Иронично, что код, предназначение которого — бороться с проблемами производительности в циклах, сам содержит проблему в цикле, хоть и совсем иного толка. Это не заметили на ревью и почему-то оказалось, что такой случай не покрыт юнит-тестом. Это неприятно. Код я, конечно, исправил и юнит-тест написал. Стоит ли на этом остановиться? Нет, каждую ошибку надо проанализировать на предмет того, почему она возникла, почему оставалась незамеченной и что мы можем сделать, чтобы ситуация не повторилась.

Не было подходящего юнит-теста, значит, в тестах в тело цикла никогда не заходили — это плохо. Следили бы регулярно за code coverage, такой проблемы вероятно удалось бы избежать сразу. Но просто так начать требовать 100% покрытия тестами тоже дорога в никуда. Ревью было, это хорошо, но такую ошибку легко проморгать, возлагать вину на ревьювера тоже неправильно. То что property-based-тест отловил это, причём раньше пользователей — вообще отлично. Значит, такие тесты действительно полезная штука и мы не зря их сделали. Но меня, как автора IDE, обеспокоил другой вопрос: почему ни одна из наших инспекций не могла предупредить о такой ошибке? Можно ли написать инспекцию, которая пометит этот код? Или может улучшить существующую?

У нас имеется несколько инспекций, которые позволяют обнаружить бесконечные циклы. Например, если бы переменная parent не присваивалась в цикле, то могла бы сработать инспекция «Loop variable is not updated inside loop». Но она присваивается. Если бы условие было заведомо всегда истинным, сработала бы инспекция «Constant conditions & exceptions». Но оно может быть и ложным, если мы ни разу не войдём в цикл. Интересно, что методы skipParenthesizedExprUp и getParent не имеют видимых побочных эффектов, и анализатор знает об этом, потому что они помечены аннотацией @Contract(pure = true). Также условие цикла не имеет побочного эффекта. Выходит, что весь побочный эффект одной итерации цикла — это присваивание в локальную переменную parent.

Назовём побочный эффект, который изменяет только локальные переменные (сами переменные, а не, например, поля объектов, на которые ссылаются эти переменные) «локальным побочным эффектом», а всякий прочий побочный эффект — нелокальным. Локальный побочный эффект может повлиять только на поведение текущего метода. Если у цикла есть только локальный побочный эффект, а его условие побочных эффектов не имеет вовсе, соберём все переменные, в которые осуществляется запись за время одной итерации цикла. В нашем случае это только переменная parent. Напомню, тело цикла выглядит так:

parent = PsiUtil.skipParenthesizedExprUp(expression.getParent());

Теперь посмотрим, используется ли значение этой переменной до факта присваивания. Это мы умеем делать с помощью простого анализа потока управления. Это вообще необходимая операция для выдачи правильных сообщений об ошибках в Java: если локальная переменная используется до первого присваивания, такая Java-программа считается некорректной. Но мы можем этот анализ применить только к телу нашего цикла. Если записываемая в теле переменная используется до присваивания, значит, значение с прошлой итерации влияет на следующую итерацию. Иначе следующая итерация сделает то же самое, что и предыдущая, и новых эффектов от последующих итераций мы не получим!

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

PsiExpression immediateParent = null;
while (parent instanceof PsiTypeCastExpression || parent instanceof PsiConditionalExpression) { immediateParent = expression.getParent(); parent = PsiUtil.skipParenthesizedExprUp(immediateParent);
}

Теперь мы записываем две переменные и одну из них во время итерации читаем. Но читаем гарантированно после того она была записана, а значит, значение с предыдущей итерации мы всё равно никогда не используем.

Как охарактеризовать такой цикл? Цикл без побочных эффектов? Но побочный эффект есть. Проблема в том, что этот эффект после первой итерации всегда одинаков. То есть либо мы в цикл не зайдём вообще, либо выполним одну итерацию. Если же после первой итерации условие цикла останется истинным, то ничего нового на последующих итерациях не произойдёт, и мы зациклимся. Тут у меня в голове всплыло слово «идемпотентность». Тело такого цикла идемпотентно: повторное выполнение тела не даёт никакого эффекта. Так и появилась новая инспекция «Idempotent loop body».

Мы убедились, что инспекция подсвечивает изначальный ошибочный цикл. Однако стоит проверить, что ещё она подсвечивает и не даёт ли ложных сработок. Ложные сработки могут свести на нет всю пользу инспекции, такая инспекция будет только раздражать, и её выключат. На исходном коде IDEA Ultimate нашлось ещё четыре сработки и оказалось, что они все правильные: это действительно четыре потенциально бесконечных цикла. Вот такая тривиальная ошибка, например, обнаружилась в рефакторинге, конвертирующем Groovy в Java:

private static String getNewFileName(GroovyFile file) { ... String prefix = FileUtil.getNameWithoutExtension(file.getName()); String fileName = prefix + ".java"; int index = 1; while (fileNames.contains(fileName)) { fileName = prefix + index + ".java"; } return fileName;
}

Довольно стандартный код для генерации уникального имени файла. Вообще странно, что он написан прямо в коде рефакторинга. По хорошему для этого должно быть переиспользуемое утилитное решение. Кстати, ещё один способ избегать багов — не изобретать велосипеды. Лучше отладить единственный эталонный велосипед и всем на нём ездить.

В коде, очевидно, ошибка, которая как раз описывается нашим сценарием. Если файла с именем prefix + ".java" нет, то это имя и будет использовано. Если файл с таким именем есть, то будет сгенерировано имя prefix + "1.java". А вот если и такой файл есть, то у нас случится бесконечный цикл, потому что последующие итерации не дадут новых эффектов (здесь эффект — это изменение fileName). Вероятно первые два случая протестировали, а третий пропустили. Исправление довольно простое — надо увеличивать переменную index в цикле.

Эта история показала, как важно анализировать найденную ошибку. Property-based-тест выявил один бесконечный цикл, это хорошо. Но такие тесты тоже покрывают не всё. В данном случае оказалось, что ошибку можно также находить статически и после соответствующей доработки статического анализатора мы нашли ещё четыре подобных ошибки. Значит ли это, что статический анализ в пять раз лучше property-based-тестов? Нет, ведь без теста мы бы вообще не узнали об этой проблеме (по крайней мере, пока пользователи на неё не наткнулись). Кроме того, property-based-тест может найти ошибки, которые вообще не опишешь статическими правилами. Различные методики поиска и предотвращения ошибок сильны, когда они работают вместе. Если задуматься, как обнаружить найденную ошибку статически, можно сэкономить много времени и сил в будущем. Конечно, не каждый может легко доработать статический анализатор. Но простые случаи можно искать в IDEA с помощью Structural search (вы можете и инспекцию настроить, чтобы она вам ваш собственный шаблон подсвечивала). Если же вы напоролись на более сложную, но потенциально формализуемую ситуацию, вы всегда можете подкинуть идею в официальный баг-трекер вашей IDE.

Инспекция «Idempotent loop body» доступна в EAP-версиях IDEA 2018.1, поэтому вы можете попробовать её уже сейчас. Программируйте с удовольствием!


x

Ещё Hi-Tech Интересное!

Python-установщик Android-сборок из TeamCity своими руками

Аудитория QA-инженеры, тестировщики мобильных приложений, автоматизаторы. Проблема Этот процесс отнимает время и силы, которые эффективнее потратить на поиск багов. Во время тестирования приложений под Android (не только, но далее речь пойдет только про данную платформу), приходится устанавливать множество сборок тестируемого ...

Карьерный Rush

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