company_banner

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

    • +21
    • 4,1k
    • 6
    JetBrains 128,92
    Делаем эффективные инструменты для разработчиков
    Поделиться публикацией
    Похожие публикации
    Комментарии 6
    • 0
      а почему код новой инспекции написан не на Kotlin? :)
      • +3

        Я пока не особо оценил Котлин. Кроме того, я занимаюсь поддержкой языка Java, поэтому для догфудинга разумно самому писать на этом же языке.

        • 0
          Эта инспекция будет работать только для java-кода? Для того же Kotlin или Scala нужно писать отдельно? Есть ли в принципе какие-то кросс-языковые инспекции?
          • +1

            Да, эта будет только для джавы. Кросс-языковые инспекции (Java-Kotlin) есть, но пока очень мало. Там же не только синтаксис, но и семантика существенно различна. Например, в Java мы всегда считаем, что плюс не создаст побочных эффектов (строго говоря, может, если вызовется странный toString), а в Котлине плюс может быть перегружен. Тонкостей множество даже между такими близкими языками.

      • 0
        parent instanceof PsiTypeCastExpression || parent instanceof PsiConditionalExpression

        А когда появятся еще какие-то выражения (например, switch-expression), придется перелопачивать код всех инспекций?

        • +2

          Ну сами они волшебным образом не заработают, конечно. Но я бы не сказал, что прямо всех инспекций. Вот с лямбдами до сих пор попадаются недоработки. Например, раньше если в поддереве искался return, то только классы надо было игнорировать, а теперь ещё и лямбды. Некоторые инспекции могут быть не обновлены и принять return внутри лямбды за выход из неё. Хотя их уже мало осталось. А есть способ лучше?

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

        Самое читаемое