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

09 Дек 2010

Теги:

#Cpp #Knowledge #StaticAnalysis

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

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. Также готов ответить на ваши вопросы, но вдаваться в споры, что позволяют регулярные выражения, а что нет - не намерен. Это не интересно. Они многое позволяют, но не позволяют еще больше. Си++ можно нормально разбирать только с использованием математического аппарата грамматик.

#Cpp #Knowledge #StaticAnalysis