Инструмент, который выводит самую длинную цепочку звонков

Question

Контекст: я выполняю процедуру анализа, описанную здесь: подход.

Точкой блокировки является нахождение "самой длинной цепочки вызовов" для проекта под наблюдением. Какой инструмент можно использовать для поиска этого? Я предполагаю, что это будет инструмент статического анализа.

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

Answer 1

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

Учитывая такой график вызовов: начните с графика вызовов с пустыми значениями длины пути вызова для каждого узла. Отметьте корень (и) [ваш граф вызовов может быть DAG] значением длины пути вызова 0. Для каждого немаркированного дочернего элемента, для которого были определены все родители, пометьте этого дочернего элемента максимальным значением от родителей, плюс 1. Повторяйте, пока все дети не будут помечены. [Если у вас есть цикл в графе вызовов, вы должны решить игнорировать его или рассматривать его как некоторое постоянное дополнение к длине пути.] Самый длинный путь легко извлекается, начиная с узла с наибольшим значением и идя назад самым дорогим родителям, пока не достигнут корень.

[РЕДАКТИРОВАТЬ], если вы вернете листовые значения родителям, вы можете получить график с каждым узлом, помеченным как далеко он достигает.

Вы уверены, что хотите длинную цепь? Или вы хотите время выполнения худшего дела?