Реальна ли сложность NPath более шестнадцати октиллионов? Или я сломал инструмент?

13

Я только что измерил большой кусок кода PHP (1153 строки), используя PHPMD ( http://phpmd.org/ ), и он говорит мне, что код NPath имеет сложность 16244818757303403077832757824.

Это выглядит как сумасшедшая цифра для меня, предполагая, что, возможно, PHPMD каким-то образом сломался. Возможно ли, чтобы кусок кода, написанный людьми, имел такую ​​высокую сложность NPath? Цикломатическая сложность 351.

Две, возможно, важные детали -

  1. Это был процедурный код, смешанный с HTML, и PHPMD будет измерять только объектно-ориентированный код. Чтобы обойти это, я обернул весь файл в классе одной функцией - это является показателем того, как он используется.

  2. Файл состоит из серии вложенных операторов switch, и внутри них много операторов if..else - так что это, безусловно, довольно сложно.

редактировать

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

Еж
источник
2
Я не знаю, сломали ли вы инструмент, но № 2 указывает на то, что код, вероятно, может немного измениться.
ЛиндаДжинн
1
@LindaJeanne Я согласен. Мне просто любопытно, сколько именно в этом беспорядка.
Jez
2
WordPress ' WP_Query::get_posts()имел сложность NPath 1,435 квиндециллиона в 2013 году. Это еще хуже в наши дни…
fuxia
@ toscho, это моя новая любимая информация. Благодарность!
Jez

Ответы:

24

Это вполне возможно. Давайте предположим, что у нас есть 35 конструкций переключателей по 10 случаев в каждой, что дало бы нам грубую цикломатическую сложность 350, когда каждое переключение происходит один за другим. Первый переключатель дает нам 10 путей. Второй переключатель дает нам еще 10 независимых путей, так что у нас есть 10 · 10 путей до этого момента. С третьим переключателем мы получаем 10 · 10 · 10 = 10³ путей и так далее, пока не получим 10 35 путей в общей сложности! Это даже выше, чем ваш результат 1,6 · 10 28 путей, что, вероятно, связано с другим фактором ветвления, а также с вложенными операторами потока управления, которые уменьшают количество путей в вашем коде.

В худшем случае для данной цикломатической сложности c мы можем иметь максимум 2 c ациклических пути через код (здесь: 2 351 = 4.6 · 10 105 ).

Решение инструмента ясно: код, с которым вы работаете, представляет собой запутанный, непроверяемый и не поддерживаемый беспорядок. Попробуйте разделить его на более мелкие независимые функции и абстрагироваться от повторения. Например, вы можете отделить генерацию HTML от основной логики вашего PHP-скрипта.

Амон
источник
14
Спасибо за анализ. Я чувствую необходимость указать, что это не мой код ... но, как это часто бывает, мне кажется, это проблема.
Еж
1
@Jez, если это утешит, ты не в уникальном положении.
Даниэль Холлинрейк
5

Согласно этому описанию сложность NPath является экспоненциальной в цикломатической сложности.

Если взять просто простые операторы if, если у вас есть два из этих операторов, это, по сути, 4 маршрута через ваш код, соответствующие четырем возможным комбинациям true / false для двух условий операторов. Добавьте еще одно заявление if, и вы получите 8.

Другими словами, если бы вся ваша цикломатическая сложность и сложность NPath исходили из длинного списка операторов if, то ваше равенство было бы NPath = 2^cyclomatic. Сравнивая это с вашими числами, 2 ^ 351 = 4.6 * 10 ^ 105, намного, намного выше, чем сложность NPath, о которой вы сообщили.

Я не знаю, сколько PHPMD делает, чтобы избежать подсчета путей, которые на самом деле невозможны (например, два взаимоисключающих условия, оба из которых имеют значение true). Возможно, ручной анализ показал бы, что многие пути на самом деле невозможны, поэтому код написан так, что раздувает метрику NPath. В продолжение вышесказанного, если у вас был список из 351 оператора if, но вы могли убедиться, что в действительности был введен только один оператор, вы можете превратить его в цепочку операторов if ... else, снизив сложность NPath с 4.6 * 10. ^ 105 до 353.

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

Бен Ааронсон
источник