Нахождение входных зависимостей выходов функций

Question

Я работал над программой на python с pycparser, который должен генерировать JSON-файл с зависимостями данной функции и ее выходных данных. Для примера функции:

int Test(int testInput)
{
    int b = testInput;
    return b;
}

Здесь я ожидал бы, что b будет зависеть от testInput. Но, конечно, с структурами, операторами if и т. Д. Все может быть намного сложнее. У файлов, которые я тестирую, также есть функции в определенной форме, которые рассматриваются как входные и выходные данные, как в:

int Test(int testInput)
{
    int anotherInput = DatabaseRead(VariableInDatabase);
    int b = testInput;
    int c;

    c = anotherInput + 1;
    DatabaseWrite(c);
    return b;
}

Здесь c будет зависеть от VariableInDatabase и b будет таким же, как и раньше. Я столкнулся со стеной с этим анализом в pycparser, так как в основном мне сложно справиться со структурами и указателями, и кажется, что есть лучший способ. Я читал об AST, CFG и других инструментах анализа, таких как Frama-C, но не могу найти четкого ответа, если это вообще что-то.

Есть ли известный способ провести такой анализ, и если да, то на что мне обратить внимание? Он предназначен для тысяч файлов и может выводить эти зависимости в JSON, поэтому плагины для редакторов не похожи на то, что я ищу.

Answer 1

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

Это называется программной нарезкой в литературе.

Вычислить потоки данных довольно сложно, особенно если у вас сложный язык (C забавно: вы можете получать потоки данных через косвенно вызываемые функции, которые читают значения; теперь вам нужен косвенный анализ точек для поддержки вашего потока данных и наоборот),

Вот забавный пример:

 // ocean of functions:
 ...
 int a(){ return b; }
 ...
 int p(){ return q; }
 ...
  void foo( int()* x )
 {  return (*x)(); }

Зависит ли foo от b? на д? Вы не можете знать, если не знаете, что foo вызывает a или b. Но foo передается указатель на функцию... и на что это может указывать?

Использование только AST и CFG необходимо, но недостаточно; алгоритмы анализа потока данных сложны, особенно если у вас есть масштаб (как вы предлагаете); для этого нужно много оборудования, которое нелегко построить [Мы сделали это на C-программах с 16 миллионами строк]. Смотрите мое эссе о жизни после разбора.