Статический анализ и регулярные выражения

    Я занимаюсь разработкой статического анализатор кода PVS-Studio для анализа программ на языке Си/Си++. После появления в PVS-Studio 4.00 анализа общего назначения мы получили множество откликов, как положительных, так и отрицательных. Кстати, предлагаю скачать новую версию PVS-Studio, в которой благодаря откликам людей было поправлено большое количество ошибок и недочетов.

    В ходе обсуждения PVS-Studio 4.00 вновь встал вопрос, можно ли реализовывать большинство проверок, используя регулярные выражения, и не переусложняем ли мы, говоря, что обязательно необходимо строить и работать с деревом разбора. Вот пример комментария на эту тему. Подобный вопрос возникает уже не в первый раз, и я решил написать статью, чтобы объяснить, почему пытаться использовать регулярные выражения для анализа Си/Си++ кода — эта очень плохая идея.

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


    Сразу скажу, что-то искать регулярными выражениями можно. И даже есть ряд статических анализаторов работающих подобных образом. Но их возможности очень и очень ограничены и сводятся в основном к сообщениям, что используется функция «strcpy» и следует заменить её на более безопасную.

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

    Диагностика 0


    Как только я начал описывать V501, то сразу вспомнил, что любой анализ мало что даст, пока не раскрыты #define. Ошибка может вполне прятаться внутри макроса, но от этого она не перестанет быть ошибкой. Создать препроцессированный файл относительно просто. Представим, что мы уже имеем i-файлы. И теперь нас ждет первая сложность, так как требуется отличить участки кода, относящиеся к системным файлам и к пользовательскому коду. Если мы будем анализировать библиотечные функции системы, это существенно снизит скорость работы и даст массу совершенно неинтересных диагностических сообщений. Таким образом, надо на основе регулярных выражений и какой-то матери разобрать строки вида:

    #line 27 "C:\\Program Files (x86)\\Microsoft Visual Studio 8\\VC\\atlmfc\\include\\afx.h"
    #line 1008 ".\\mytestfile.cpp"


    И понять, что относится к нашей программе, а что к Visual Studio. Но это еще не все. Надо научиться делать относительный отсчет строк внутри i-файлов. Ведь нам надо выдать не абсолютный номер строки с ошибкой в препроцессироанном i-файле. Нам нужен номер строки в нашем родном c/cpp-файле, который мы анализируем.

    Итого, мы еще не приступили к сути дела, а уже получили кучу сложностей.

    Диагностика 1


    V501. There are identical sub-expressions to the left and to the right of the 'foo' operator.

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

    if (X > 0 && X > 0)

    На первый взгляд регулярным выражением вполне можно найти конструкции, когда слева и справа от операторов &&, ||, == и так далее расположены одинаковые выражения. Например, так. Ищем оператор &&. Если слева и справа от && находится что-то одинаковое ограниченное скобками, то беда. Но не выйдет, ведь можно написать так:

    if (A == A && B)

    Ошибка есть, но слева и справа от '==' находится разные выражения. Значит надо вводить понятие приоритет операций. И смотреть, если это '==', то отсекать границы по более низкоприоритетным операциям, таким как '&&'. А если это будет &&, то наоборот надо захватить операции '==', чтобы выявить ошибку для вот этого случая, дойдя до ограничивающих скобок:

    if (A == 0 && A == 0)

    И так надо предусмотреть логику для всех вариантов операций с разными приоритетами. Да, кстати на скобки полагаться тоже нельзя. Могут быть такие случаи:

    if ( '(' == A && '(' == B )
    b = X > 0 && X > 0;

    Феерический геморрой. Очень сложно рассматривать все варианты различными регулярными ворожениями. Их будет уйма с множеством исключений. И все равно будет не надежно, так как не будет ощущения, что мы вспомнили про все возможные конструкции.

    А теперь сравните с той элегантностью, с какой я могу обнаружить эту ошибку, имея синтаксическое дерево. Если я нашел оператор &&, ==, || и так далее, мне только остается сравнить левую и правую ветку дерева. Я делаю это так:

    if (Equal(left, right))
    {
      // Беда!
    }

    И всё. Не надо думать про приоритеты операций. Не надо ожидать подвоха, что встретится скобка в тексте: b = '(' == x && x == ')';. Можно просто сравнить левую и правую ветку дерева.

    Диагностика 2


    V502. Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the 'foo' operator.

    Правило ищет путаницу, связанную с приоритетом операций (подробности смотрите в описании ошибки). Нам надо выявить нечто вида:

    int a;
    bool b;
    int c = a + b ? 0 : 1;

    Оставим пока в стороне вопрос с приоритетом операция. С этим вопросом при работе с регулярными выражениями все плохо. Но еще хуже то, что для этого и многих других правил надо знать ТИП ПЕРЕМЕННОЙ.

    Необходимо вывести (раскрыть) тип каждой переменной. Нужно уметь продраться сквозь дебри typedef. Нужно уметь заглянуть в классы, что бы понять, что такое vector<int>::size_type. Нужно уметь учесть области видимости и разные using namespace std;. И даже уметь вывести тип переменной X из выражения: «auto X = 1 + 2;» в случае C++0x.

    Теперь вопрос, как это сделать, используя регулярные выражения? Ответ — никак. Регулярные выражения перпендикулярны к этой задаче. Нужно или писать сложный механизм выведения типа, то есть фактически написать синтаксический анализатор кода. Или остаться с регулярными выражениями, но не иметь представления о типах переменных и выражений.

    Итог: работая на регулярных выражениях с Си/Си++ программой, мы не знаем тип переменных и выражений. Запомним это существенно ограничение.

    Диагностика 3


    V503. This is a nonsensical comparison: pointer < 0.

    Очень простое правило. Подозрительно сравнивать указатель с помощью <, > с нулем. Пример:

    CMeshBase *pMeshBase = getCutMesh(Idx);
    if (pMeshBase < 0)
      return NULL;

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

    Для диагностики всего-навсего надо знать тип переменной pMeshBase. А почему это невозможно было объяснено чуть выше.

    Данная диагностика не реализуема на основе регулярных выражений.

    Диагностика 4


    V504. It is highly probable that the semicolon ';' is missing after 'return' keyword.

    void Foo2(int *ptr)
    {
      if (ptr == NULL)
        return
      Foo();
      ...
    }

    Диагностировать конструкции данного вида вполне можно и регулярными выражениями. Но будет слишком много ложных срабатываний. Нас интересуют только те случаи, когда функция возвращает void. В принципе и это можно узнать, используя только регулярные выражения. Только будет весьма не просто понять, где начинается и кончается функция. Сами попробуйте придумать регулярное выражение, чтобы найти начало функции. Уверяю, это будет очень интересная задачка. Особенно если вспомнить, что никто не мешает написать что-то такое:

    int Foo()
    {
       ...
      char c[] = 
      "void MyFoo(int x) {"
      ;
      ...
    }

    Если мы имеем полноценное синтаксическое дерево с различной информацией, то всё гораздо проще. Тип возвращаемой функции можно узнать так (взято прямо из PVS-Studio):

    SimpleType funcReturnType;
    EFunctionReturnType fType;
    if (!env->LookupFunctionReturnType(fType, funcReturnType))
      return;
    if (funcReturnType != ST_VOID)
      return;


    Диагностика 5


    V505. The 'alloca' function is used inside the loop. This can quickly overflow stack.

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

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

    {
      for (int i = 0; i < 10; i++)
      {
        //Прикольный комментарий. Вот вам { - мучайтесь теперь. :)
        char *x = "Здесь тоже надо держать ухо в остро :-{";
      }
      p = _alloca(10); // Мы внутри цикла или нет?
    }


    Диагностика 6


    V506. Pointer to local variable 'X' is stored outside the scope of this variable. Such a pointer will become invalid.

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

    Данная диагностика не реализуема на основе регулярных выражений.

    Диагностика 7


    V507. Pointer to local array 'X' is stored outside the scope of this array. Such a pointer will become invalid.

    Данная диагностика не реализуема на основе регулярных выражений.

    Диагностика 8


    V508. The use of 'new type(n)' pattern was detected. Probably meant: 'new type[n]'.

    Полезно находить опечатки вида:

    float *p = new float(10);

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

    typedef float MyReal;
    ...
    MyReal *p = new MyReal(10);

    Данная диагностика не реализуема на основе регулярных выражений.

    Диагностика 9


    V509. The 'throw' operator inside the destructor should be placed within the try..catch block. Raising exception inside the destructor is illegal.

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

    Вот только немало попотеть придется в регулярных выражениях, чтобы найти функцию деструктор, ее начало и конец, есть ли там throw и не перехватывается ли он в catch. Представили весь объем работ? Слабо?

    А мне нет. Вот как я изящно написал в PVS-Studio (правило целиком):

    void ApplyRuleG_509(VivaWalker &walker, Environment *env,
      const Ptree *srcPtree)
    {
      SimpleType returnType;
      EFunctionReturnType fType;
      bool res = env->LookupFunctionReturnType(fType, returnType);
      if (res == false || returnType != ST_UNKNOWN)
        return;
      if (fType != DESTRUCTOR)
        return;
    
      ptrdiff_t tryLevel = OmpUtil::GetLevel_TRY(env);
      if (tryLevel != -1)
        return;
      string error = VivaErrors::V509();
      walker.AddError(error, srcPtree, 509, DATE_1_SEP_2010(), Level_1);
    }
    


    Диагностика 10


    V510. The 'Foo' function is not expected to receive class-type variable as 'N' actual argument.

    Это правило на тему передачи в функции вида printf в качестве аргумента классов типа std::string и так далее. Нужны типы. Так что опять данная диагностика не реализуема на основе регулярных выражений.

    Заключение


    Надеюсь, я прояснил ситуацию с регулярными выражениями, синтаксическими деревьями и статическим анализом кода. Всем спасибо за внимание. Еще раз приглашаю скачивать и пробовать PVS-Studio. Также готов ответить на ваши вопросы, но вдаваться в споры, что позволяют регулярные выражения, а что нет — не намерен. Это не интересно. Они многое позволяют, но не позволяют еще больше. Си++ можно нормально разбирать только с использованием математического аппарата грамматик.
    PVS-Studio
    Статический анализ кода для C, C++, C# и Java

    Комментарии 37

      +1
      Хоть в целом я полностью согласен с тем, что регулярки для полноценного анализа — инструмент никоим образом не подходящий, всё же нельзя не отметить, что возможность расширять анализ собственными правилами, построенными на регулярках, всё же могут оказаться полезны. Возьмём такой элементарный фантастический пример: пусть ни компилятор, ни PVS не обнаруживают опечатку вида if (a = b), и пользователь хочет добавить её распознавание сам. Если в PVS были бы регулярки, он бы запросто написал такое правило:
      if\s*\(\w+\s*=\s*\w+\)
      Что имеем в результате? Новую проверку. Естественно, я первый могу указать на тучу недостатков этой проверки: она крайне слабая, отлавливает далеко не все возможные ситуации, не поддерживает лишние скобки, массивы, операции, вызовы функций и сотни других вещей. Но ведь статический анализ никогда и не сможет поддерживать абсолютно все мыслимые навороты. Его задача — отловить то, что он сможет отловить. А эта дополнительная проверка, как она ни слаба, как ни ограниченна, всё же работает и вылавливает довольно-таки существенный процент новых, ранее не отлавливавшихся ошибок. Это плюс? Несомненный плюс!

      PS: Отдельно стоит вопрос о ложных срабатываниях внутри строк и комментариев, но тут уже не должно быть проблемой заставить PVS при прогоне пользовательских регулярок подсовывать им только реальный код. Если другие правила хотят анализировать строки, то можно добавить опции, говорящие, какие структуры включать в анализ данным конкретным правилом, а какие — нет.
        +12
        С ветряными мельницами бороться бесполезно, а заблуждение, что разобрать нерегулярный текст можно с помощью регулярных выражений, является как раз такой мельницей. Корни этого заблуждения очень просты:

        1. регулярные выражения встроены как DSL практически в каждый язык программирования (порог входа явно ниже, чем, например, у yacc)
        2. регулярные выражения кажутся сложными, поэтому, их применение ко всему подряд, дает автору +1 к ЧСВ


        Кстати, funboy регулярных выражений может запросто с вами спорить, логика тут бесполезна. Их излюбленные способы: апелляция к слухам («я слышал, что в Perl регулярные выражения настолько мощные, что там это возможно „) и “добавить чуть-чуть кода». Под добавлением чуть-чуть кода они имеют ввиду создание парсера вручную поверх частично разобранных регулярными выражениями фрагментами текста (по сути, регулярки используются только как часть лексера).
          0
          Что-то мне подсказывает, что сделать нормальный анализатор можно лишь на Тьюринг полном языке программирования. А я что-то не слышал, чтобы регулярки у нас вдруг стали Тьюринг полными.
            0
            В перле внутрь регулярок можно куски перлового кода совать, так они Тьюринг-«полными» получаются :)
            Боюсь даже подумать, чтобы мне когда-нибудь пришлось разбирать творение какого-нибудь оголтелого фаната регулярок с использованием таких наворотов.
              0
              В регулярку или в шаблон замены?
              +6
              –1
              И тем не менее, возвращаясь к возможности написания своих правил, думаю при такой продуманной архитектуре, как у вас, можно реализовать механизм подключения плагинов с собственными правилами.
                +1
                > Те, кто знаком с теорией компиляции, конечно же понимают, что язык Си++ можно разбирать только на основе грамматик, а не регулярных выражений.

                Существует мнение что даже просто грамматик не достаточно: users.livejournal.com/_winnie/13725.html
                  +3
                  Насколько было проще, если бы все программисты дружили с лингвистами :)
                  ru.wikipedia.org/wiki/Иерархия_Хомского
                    +6
                    Лично мне кажется что это вообще must know. Для любого программиста, даже прикладника. И старперское брюзжание что «каждый программист должен написать свой ЯП и свою ОС» мне не кажется столь безосновательным.

                    В первую очередь потому, что банальнейший парсер, писанный руками, мгновенно открывает глаза разные вещи. Например то, что if не всесилен. И не любую программу можно «чуток подкрутить».

                    Когда человек начинает сталкиваться с ситуацией, что добавить «еще одну запятую» с точки зрения функциональности может вылиться в 3 страницы кода… то после таких граблей невольно начнешь думать как сразу сделать по уму. Вне зависимости от текущей задачи. Просто при написании парсеров это проявляется наиболее полно и быстро :)
                      +2
                      Абсолютно согласен. Кажется, попытка иронизировать была в очередной раз столь тонкой, что умерла от истощения. My bad.

                      Я это к тому, на само деле, что ответ на вопрос «а почему не регулярные выражения» должен быть коротким: «потому что грамматика С/С++ контекстно-зависима». Если этого спрашивающему недостаточно, то нужно решать проблему пробелов в знаниях куда более фундаментальную, чем задано вопросом.

                      И тема, на самом деле, страшная. Тем, что в ней возникает необходимость. Это я как человек-без-образования-у-которого-молоко-на-губах-обсохло™ говорю :(
                      +3
                      Вообще говоря любой программист с академическим образованием (читай: не самоучка) обязан это знать, потому как Теория Языков Программирования, в которую все это входит, в университетах преподается. И стало быть будущих программистов которые этот курс не освоили, выпускать из университета можно только вперед ногами, но это в идеале, а мы к сожалению в реальной жизни.
                        +2
                        Well, по-моему, самоучка знать это обязан ещё более. Иначе отсутствию у него академического образования нет вообще никаких оправданий.
                      0
                      Есть ли планы на создание такого рода анализатора для linux? Консольная тулза была бы очень кстати.
                        0
                        Консольная тулза уже есть.
                          0
                          У меня возникает ощущение, что если вы выделите ядро системы в библиотеку (что-то мне подсказывает, что так и есть), компилируемую под линуксом, и выложите исходники GUI и CLI интерфейсов, то найдутся энтузиасты, которые их сами перепишут :-)
                            +2
                            Сто тысяч лет наша библиотека VivaCore (http://www.viva64.com/ru/vivacore-library/) является открытым опубликованным проектом с исходниками.

                              0
                              Понимаю, что вас уже достали за последние сутки :-) Да, я её видел, потому и предположил такую возможность. Вот если бы вы распространяли набор правил общего назначения не только как часть PVS-Studio в виде установщика для Win, но и как библиотеку (в том числе для nix)…
                                +1
                                >> Понимаю, что вас уже достали за последние сутки

                                Ни-чё, работа такая…

                                >> Вот если бы вы

                                И что бы изменилось? :-)
                                  0
                                  Тогда интерфейс к ним мог бы реализовать кто-то заинтересованный в этом продукте под linux.
                                    0
                                    И сколько людей из кричащих на форумах умеют что-то делать? :-)

                                    Я в этом (ой, нет, в соседнем, но Вы его легко найдете) топике уже писал, что скомпилировать exe-шник и выпустить программный продукт определенного качества — это разные действия.
                                      0
                                      Мало, но по крайней мере это не даст им повода задавать глупые вопросы из соседнего топика.

                                      Прочитал ветку про качество, чтож, понимаю. Видимо не стоит ожидать от вас linux-версии библиотек в ближайшее время :-(
                                        0
                                        >> Мало, но по крайней мере это не даст им повода задавать глупые вопросы из соседнего топика.

                                        Да пусть задают. Просто дома софт никто не пишет (ой) для Линукса. Его пишут в рабочее время и за это платит работодатель. А работодателю лучше нам заплатить и мы все сделаем в лучшем виде.

                                        >> Видимо не стоит ожидать от вас linux-версии библиотек в ближайшее время :-(

                                        Отчего же, поучавствуйте финансово в разработке — будет linux-версия.
                                          0
                                          Я как раз предлагаю вариант, который уменьшит издержки :-) Тем более, что судя по цене конечного продукта под финансовым участием подразумевается > $10k.
                                      0
                                      На тему PVS-Studio Standalone и Linux, возможно будет интересна вот эта новая заметка — "PVS-Studio теперь работает и без среды Visual Studio или C++Builder – проверяем препроцессированные файлы от чего угодно".
                            0
                            Свершилось: PVS-Studio для Linux.
                            +6
                            Я рад прежде всего что российский стартап, из города Тулы стал таким… Мощным старапом! Очень хочется чтобы основной офис так и остался бы в Туле, чтобы другие города смотря на это, также не стесняясь выдавали сверхпродукты :)
                              +7
                              А нам очень хочется, чтобы офис был в Лас-Вегасе или Калифорнии :-).

                              Но спасибо Вам за поддержку.
                              0
                              Рапортую о проблеме. Раньше свой проект я компилировал gcc, ради Вашего анализатора я убил несколько часов и теперь проект на ура компилируется студией (отдельное спасибо, наконец заставил себя сделать это). Тем не менее запуск анализатора (PVS-Studio->Check Solution) ничего не дает. Мой проект использует Qt, в логах анализатора я вижу только:
                              02 ../SomeFile.h(11): fatal error C1083: Cannot open include file: 'QWidget': No such file or directory moc_SomeFile.cpp 1 False

                              Всего 269 ошибок о том что невозможно открыть файл относящейся к сырцам Qt (мне не понятно зачем это) и больше никакой ошибки или предупреждения. Беглый осмотр настроек PVS не выявил возможности задать/отключить инклюды. Возможно я не попадаю под use case. Внесите ясность ;)
                                0
                                Для того, чтобы выполнить анализ кода, необходимо сначала осуществить препроцессирование — раскрыть все инклуды и дефайны. Это мы делаем препроцессором от Visual C++ (который есть часть cl.exe). Ошибку выдает именно препроцессор — он не может найти заголовочный файл QWidget. Странно, что при этом проект компилируется студией.

                                Тем не менее проверьте, добавлен ли путь до заголовков Qt в Additional Include Directories в настройках проекта или настройках Visual C++ (см. VC++ Directories в настройках Visual C++).

                                Если не заработает, скажите — будем разбираться, что еще могло быть не так.
                                  0
                                  Не заработало. Я прописал в VC++ Directories C:\Qt\src\include. В сообщениях об ошибках он пишет что не может обнаружить файл QWidget или QObject. Но ведь это не совсем верно, инклюд в исходниках выглядит так #include или #include . Т.е. на самом деле QWidget это не файл, он должен ссылаться например на QtGui\QWidget.h который естественно есть в C:\Qt\src\include\QtGui\QWidget.h. Мне кажется в этом проблема. С новыми изменениями студия по прежнему успешно компилит проект. Будет свободное время — попробую на qt example запустить анализатор, может все же у меня проблема.
                                    0
                                    Поищите поиском файл QWidget (именно так, без ".h") и сделайте «включение» той папки. Явно проблема в том, что не включена она в include directories. Но VS почему-то видит, а PVS-Studio — нет. Возможно какие-то специальные переменные окружения QT используются, которые мы игнорируем.
                                      0
                                      Вы были правы, после добавления полных путей (к каждой под паке из папки include) все завелось. Запустил жду эффекта, уже парочка варнингов есть. Спасибо Вам.
                                        0
                                        Опишите потом здесь свои впечатления, пожалуйста.
                                          +1
                                          Анализ займет некоторую часть времени неделю наверное. По результатам отпишусь либо сюда, либо статью создам (правда боюсь заминусуют).

                                          Анализ занял (непосредственно анализ PVS) 3 часа. Было выявлено 120 — Level 1 Warning, 159 — Level 2, 280 — Level 3. Многие ошибки повторяются — одна и та же ошибка расслаивается на несколько строчек (т.е. ошибка одна, но в логе выдается что их несколько). Анализировать очень сложно из-за триальности нет навигации по коду, конкретное место ошибки не подсвечивается. В Level 3 Warning львиная доля V001 ошибок — не возможно анализировать исходник.

                                          Напишите что Вам особенно интересно от меня, постараюсь учесть в своем отчете.
                                            +1
                                            >> либо статью создам (правда боюсь заминусуют).

                                            Не бойтесь, мы поддержим плюсиками :-).

                                            >> Анализировать очень сложно из-за триальности.
                                            Сейчас пока еще General Analysis бесплатно. 64-битные ошибки можно выключить просто.

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

                                            >> Напишите что Вам особенно интересно от меня

                                            Чтобы Вы купили. :-)
                                            +2
                                            Вот мой отчет habrahabr.ru/blogs/cpp/110515/

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

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