Статический анализ и 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, поэтому вы можете попробовать её уже сейчас. Программируйте с удовольствием!
