24.10.2019 20:51
lany 25 7800 Источник

Не так давно я изучал вывод статического анализатора IntelliJ IDEA для Java-кода и наткнулся на интересный случай. Так как соответствующий фрагмент кода не является open source, я его анонимизировал и отвязал от внешних зависимостей. Будем считать, что он выглядел так:


private static List<Integer> process(Map<String, Integer> options, List<String> inputs) {
    List<Integer> res = new ArrayList<>();
    int cur = -1;
    for (String str : inputs) {
        if (str.startsWith("-"))
            if (options.containsKey(str)) {
                if (cur == -1) cur = options.get(str);
            }
            else if (options.containsKey("+" + str)) {
                if (cur == -1) cur = res.isEmpty() ? -1 :
                        res.remove(res.size() - 1);
                if (cur != -1) res.add(cur + str.length());
            }
    }
    return res;
}

Код как код, что-то преобразуется, что-то делается, но статическому анализатору он не понравился. Здесь мы видим целых два предупреждения:


Code screenshot


На выражении res.isEmpty() IDE говорит, что условие всегда истинно, а на cur выдается, что присваивание бессмысленно, так как то же самое значение уже лежит в этой переменной. Нетрудно видеть, что проблема с присваиванием — прямое следствие первой проблемы. Если res.isEmpty() действительно всегда истинно, то строка редуцируется до


if (cur == -1) cur = -1;

Это и в самом деле излишне. Вот только почему выражение всегда истинно? Ведь res — это список, он заполняется в этом же цикле. Количество итераций цикла и то, в какие ветки мы зайдем, зависит от входных параметров, которых IDE знать не может. Мы же могли добавить элемент в res на предыдущей итерации, и тогда список не будет пустым.


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


Для начала пометим все строчки, где меняется состояние метода. Это изменение переменной cur или изменение списка res:


private static List<Integer> process(Map<String, Integer> options, List<String> inputs) {
    List<Integer> res = new ArrayList<>();
    int cur = -1;
    for (String str : inputs) {
        if (str.startsWith("-"))
            if (options.containsKey(str)) {
                if (cur == -1) cur = options.get(str); // A
            }
            else if (options.containsKey("+" + str)) {
                if (cur == -1) cur = res.isEmpty() ? -1 : // B 
                        res.remove(res.size() - 1); // C
                if (cur != -1) res.add(cur + str.length()); // D
            }
    }
    return res;
}

Строки 'A' и 'B' ('B' — это первая ветка условного оператора) изменяют переменную cur, 'D' изменяет список, а 'C' (вторая ветка условного оператора) изменяет и список, и переменную cur. Для нас существенно, лежит ли в cur -1 и является ли список пустым. То есть надо следить за четырьмя состояниями:



Строка 'A' меняет cur, если там до этого было -1. Причем мы не знаем, будет в результате -1 или нет. Поэтому возможны два варианта:



Строка 'B' тоже работает, только если cur равно -1. При этом, как мы уже заметили, она в принципе ничего не делает. Но отметим все-таки это ребро для полноты картины:



Строка 'C', как и предыдущие, работает при cur == -1 и меняет его произвольно (как и 'A'). Но при этом она еще может непустой список res превратить в пустой, или оставить непустым, если там было больше одного элемента.



Наконец, строка 'D' увеличивает размер списка: пустой она может превратить в непустой, либо непустой увеличить. Непустой в пустой она превратить не может:



Что это нам дает? Ровным счетом ничего. Совершенно непонятно, почему условие res.isEmpty() всегда истинно.


На самом деле, мы начали неправильно. В этом случае недостаточно отслеживать состояние каждой переменной отдельно. Тут играют важную роль коррелированные состояния. К счастью, в связи с тем, что 2+2 = 2*2, у нас их тоже только четыре:



Двойной рамкой я отметил начальное состояние, которое мы имеем при входе в метод. Что ж, пробуем все заново. 'A' меняет либо сохраняет cur при любом res, res при этом не меняется:



'B' работает только при cur == -1 && res.isEmpty() и ничего не делает. Добавляем:



'C' работает только при cur == -1 && !res.isEmpty(). При этом и cur, и res меняются произвольно: после 'C' мы попадаем в любое состояние:



Наконец, 'D' может начаться в cur != -1 && res.isEmpty() и сделать список непустым, либо начаться в cur != -1 && !res.isEmpty() и там же и остаться:



На первый взгляд кажется, что стало только хуже: граф стал сложнее, и непонятно, как его использовать. Но на самом деле мы близки к разгадке. Стрелочки теперь показывают весь возможный поток исполнения нашего метода. Так как мы знаем, из какого состояния мы начали, давайте прогуляемся по стрелочкам:



И тут обнаруживается весьма любопытная вещь. Мы не можем попасть в левый нижний угол. А раз мы в него попасть не можем, значит, мы не можем пройтись ни по одной стрелке 'C'. То есть строчка 'C' действительно недостижима, а 'B' при этом может выполняться. Это возможно, только если условие res.isEmpty() действительно всегда истинно! Анализатор IntelliJ IDEA полностью прав. Извини, анализатор, зря я думал, что ты глючный. Просто ты настолько умный, что мне, простому человеку, трудно за тобой успеть.


В нашем анализаторе нет никаких “хайповых” технологий искусственного интеллекта, а используются подходы control flow analysis и data flow analysis, которым уже не менее полувека. Тем не менее он действительно порой делает весьма нетривиальные выводы. Впрочем, это и понятно: строить графы и гулять по ним у машин давно получается лучше, чем у людей. Тут есть важная нерешенная задача: недостаточно просто сказать человеку, что у него в программе ошибка. Кремниевый мозг должен объяснить биологическому, почему он так решил, причем так чтобы биологический мозг понял. Если у кого-то есть гениальные идеи, как это сделать, я буду рад вас выслушать. Если же вы готовы сами реализовать ваши идеи, наша команда не откажется с вами посотрудничать!


Один из acceptance-тестов перед вами: для этого примера объяснение должно генерироваться автоматически. Это может быть текст, граф, дерево, картинка с котиками — все что угодно, лишь бы человеку было понятно.


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

Комментарии (25)


  1. tsypanov
    25.10.2019 00:15
    #20800960

    private static List<Integer> process(Map<String, Integer> options, List<String> inputs) {
    List<Integer> res = new ArrayList<>();
    int cur = -1;
    for (String str : inputs) {
        if (str.startsWith("-"))
            if (options.containsKey(str)) {
                if (cur == -1) cur = options.get(str);
            }
            else if (options.containsKey("+" + str)) {
                if (cur == -1) cur = res.isEmpty() ? -1 :
                        res.remove(res.size() - 1);
                if (cur != -1) res.add(cur + str.length());
            }
    }
    return res;
}

    Ояэбу! Без 100 грамм не разобраться.


    Вот тут ещё НПЕ можно выхватить:



    public class ChildServiceImpl1Test  {
    @Test
    public void name() {
        final String key = "-azaza";
        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put(key, null);

        final List<String> inputs = Collections.singletonList(key);
        process(map, inputs);

    }

    private static List<Integer> process(Map<String, Integer> options, List<String> inputs) {
        List<Integer> res = new ArrayList<>();
        int cur = -1;
        for (String str : inputs) {
            if (str.startsWith("-"))
                if (options.containsKey(str)) {
                    if (cur == -1) cur = options.get(str);
                }
                else if (options.containsKey("+" + str)) {
                    if (cur == -1) cur = res.isEmpty() ? -1 :
                            res.remove(res.size() - 1);
                    if (cur != -1) res.add(cur + str.length());
                }
        }
        return res;
    }
}


    1. lany Автор
      25.10.2019 06:45
      #20801428

      Это натянуто. Ты в каждом методе, принимающем коллекцию, ожидаешь увидеть в ней null? Я вот нет. Иногда метод вправе ожидать каких-то гарантий относительно аргументов. Особенно приватный метод.


      1. tsypanov
        25.10.2019 11:10
        #20802076

        Иногда метод вправе ожидать каких-то гарантий относительно аргументов.

        Согласен. Любопытно, зачем его сделали статическим? Неужто компилятору помочь хотели?


        1. lany Автор
          25.10.2019 11:11
          #20802080

          А зачем делать метод нестатическим, когда он может быть статическим?


          1. tsypanov
            25.10.2019 11:29
            #20802136

            Насколько я понимаю, в ООП статика считается плохим тоном. Здесь я вижу в статике только один смысл — облегчение работы компилятору.


            1. lany Автор
              25.10.2019 11:32
              #20802148

              Егора наслушался что ли? :-)


              1. tsypanov
                25.10.2019 11:43
                #20802204

                Смотрел пару его доклады, ИМХО, не взлетит. Сейчас проде у него новые великие мысли:
                1) вместо толкового разработчика должен быть тугой пайплайн, который нужно закармливать кодом, а он там разберёт, пущать или не пущать
                2) "если у тебя нет последователей на гитхабе — ты не разработчик" (с)


          1. elegorod
            25.10.2019 18:37
            #20804578

            Я вот тоже не пойму, зачем делать статическим какой-то метод сервиса (спринг бина), если вдруг так совпало, что он не вызывает другие сервисы? Сегодня не вызывает, а завтра будет вызывать. Ну и я не собираюсь вызывать метод в статическом контексте (MyService.method()), это даже хорошо запретить. Правильно вызывать через экземпляр бина.

            Поэтому раздражает инспекция «Method may be static», и я её отключил.


            1. sergey-b
              26.10.2019 12:09
              #20806690

              Это просто дополнительная проверка, позволяющая заметить потенциальную проблему. Довольно часто она срабатывает тогда, когда метод действительно работает не так, как задумано. Я в таких случаях разбираюсь, почему так получилось, и почти всегда решаю порефакторить код.


            1. lany Автор
              28.10.2019 11:47
              #20812750

              Если завтра будет вызывать, завтра и поменяете. Давайте сразу добавим методу тридцать дополнительных параметров, ведь они завтра могут пригодиться. Получатель невиртуального метода — это просто один из его параметров.


              Правильно вызывать через экземпляр бина.

              Ну если вы придумали себе надуманные правила, то тогда да, правильно.


  1. bm13kk
    25.10.2019 00:27
    #20800986

    Я конечно понимаю что статья вообще не про это, но.

    Но стилизировать бы код. И почему исользуется второй иф вместо елса


    1. multiadmin
      25.10.2019 04:55
      #20801366

      И почему исользуется второй иф вместо елса

      Потому что в первом if значение cur меняется.


      1. bm13kk
        25.10.2019 12:42
        #20802526

        а ну да, спасибо


  1. dex131
    25.10.2019 09:13
    #20801610
    +1

    Прочитал как детектив с разгадкой в конце


    1. tsypanov
      25.10.2019 11:09
      #20802072
      +1

      Из таких примеров можно сделать доклад в духе "Приключения сеньора Холмся и Джуниора Ватсона", который делали Борисов и Барух. Жеглов и Шарапов ловят неуловимую ООМЕ в Идее :)


  1. adruzh
    25.10.2019 09:57
    #20801762

    На выражении res.isEmpty() IDE говорит, что условие всегда истинно

    Почему бы не говорить, что оно истинно при условии (cur == -1)? Т.е. указать, что условие всегда истинно именно в этой ветке.
    Для человека, после такой подсказки, будет проще понять предмет недовольства анализатора.


    1. lany Автор
      25.10.2019 09:58
      #20801770

      Кажется, в этом нет смысла. Эта строчка совершенно очевидно выполняется только при cur == -1. Или сообщить, что "если бы это условие было не под if (cur == -1), оно не было бы всегда истинно"?


  1. Throwable
    25.10.2019 13:17
    #20802726

    Код как код, что-то преобразуется, что-то делается, но статическому анализатору он не понравился.

    Если честно, то и мне этот код не особо нравится :)
    Вообще, я иногда сталкиваюсь с подобными случаями, когда анализатор предлагает оптимизировать код в ущерб понятности и читаемости. Он, конечно, на 100% прав, но при последующей ревьюхе человекообразным существом у последнего могут возникнуть вопросы по поводу подобной оптимизации. К сожалению анализатор не предоставляет подробное теоретическое обоснование эквивалентности обоих вариантов, да и ревьюер в них особо вникать не будет — просто попросит: "оставь как раньше — так понятней".


  1. atamur
    25.10.2019 14:27
    #20803162
    +3

    То есть строчка 'C' действительно недостижима, а 'B' при этом может выполняться. Это возможно, только если условие res.isEmpty() действительно всегда истинно!

    Не совсем так, на самом деле всегда истинно cur =! -1 || res.isEmpty(), т.е. как только список перестает быть пустым cur никогда не становится -1, а пока он -1 список пуст.


    Хорошо, что статический анализатор находит ошибку в плохом коде, плохо что после исправления ошибки код остается плохим.


    1. lany Автор
      27.10.2019 11:31
      #20809496

      Не очень понял, что конкретно "не совсем так". Да, можно объяснять по-другому, но что не совсем так то?


  1. tmaxx
    25.10.2019 22:40
    #20805522

    По-моему без графов проще если честно. Список может стать непустым только после срабатывания этого условия:

    if (cur != -1) res.add(cur + str.length());

    А как только cur != -1, большая часть веток перестаёт работать и cur не может стать обратно -1.

    Следовательно !res.isEmpty => cur != -1

    Что эквивалентно cur == -1 => res.isEmpty


  1. SMAX1
    25.10.2019 23:22
    #20805638

    Жаль, что аналогичный код на Котлине идея не смогла подсветить


    1. lany Автор
      25.10.2019 23:24
      #20805646

      У Котлина качество статического анализа существенно ниже, да.


  1. dougrinch
    27.10.2019 19:27
    #20810816

    Вообще мне кажется, что отображение ты сам отличное и предложил. Последняя картинка из этого поста (естественно, с расшифровкой A, B, C и D) — это топ. Более того, предположу, что внутри анализатора примерно такой граф и находится, так что достаточно его просто отобразить.


  1. webmascon
    28.10.2019 02:05
    #20811724
    +1

    Пожалуйста прячьте код под кат. Вы поломали всю rss ленту по ширине