Для получения триального ключа
заполните форму ниже
Team License (базовая версия)
Enterprise License (расширенная версия)
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
GBP
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Бесплатная лицензия PVS-Studio для специалистов Microsoft MVP
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

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

Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

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

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

09 Дек 2010

Я занимаюсь разработкой статического анализатор кода 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 Foo();
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 оказался внимательнее, чем три с половиной программиста

Дата: 22 Окт 2018

Автор: Андрей Карпов

PVS-Studio, как и другие статические анализаторы кода, часто выдаёт ложные срабатывания. Но не стоит спешить считать странные срабатывания ложными. Это короткая история о том, как PVS-Studio вновь ок…
Зло живёт в функциях сравнения

Дата: 19 Май 2017

Автор: Андрей Карпов

Возможно, читатели помнят мою статью под названием "Эффект последней строки". В ней идёт речь о замеченной мной закономерности: ошибка чаще всего допускается в последней строке однотипных блоков текс…
Эффект последней строки

Дата: 31 Май 2014

Автор: Андрей Карпов

Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в последнем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого …
Как и почему статические анализаторы борются с ложными срабатываниями

Дата: 20 Мар 2017

Автор: Андрей Карпов

В своей предыдущей статье я писал, что мне не нравится подход, при котором статические анализаторы кода оцениваются с помощью синтетических тестов. В статье приводился пример, воспринимаемый анализат…
Главный вопрос программирования, рефакторинга и всего такого

Дата: 14 Апр 2016

Автор: Андрей Карпов

Вы угадали, ответ - "42". Здесь приводится 42 рекомендации по программированию, которые помогут избежать множества ошибок, сэкономить время и нервы. Автором рекомендаций выступает Андрей Карпов - тех…
Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей

Дата: 21 Ноя 2018

Автор: Андрей Карпов

Краткое описание технологий, используемых в инструменте PVS-Studio, которые позволяют эффективно обнаруживать большое количество паттернов ошибок и потенциальных уязвимостей. Статья описывает реализа…
Статический анализ как часть процесса разработки Unreal Engine

Дата: 27 Июн 2017

Автор: Андрей Карпов

Проект Unreal Engine развивается - добавляется новый код и изменятся уже написанный. Неизбежное следствие развития проекта - появление в коде новых ошибок, которые желательно выявлять как можно раньш…
PVS-Studio для Java

Дата: 17 Янв 2019

Автор: Андрей Карпов

В седьмой версии статического анализатора PVS-Studio мы добавили поддержку языка Java. Пришло время немного рассказать, как мы начинали делать поддержку языка Java, что у нас получилось и какие дальн…
Любите статический анализ кода!

Дата: 16 Окт 2017

Автор: Андрей Карпов

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

Дата: 22 Дек 2018

Автор: Андрей Карпов

В канун празднования нового 2019 года команда PVS-Studio решила сделать приятный подарок всем контрибьюторам open-source проектов, хостящихся на GitHub, GitLab или Bitbucket. Им предоставляется возмо…

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

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