Понимание цикломатической сложности

Недавно я столкнулся с Cyclomatic Complexity, и я хотел бы попытаться понять это лучше.

Каковы некоторые практические примеры кодирования различных факторов, влияющих на вычисление сложности? В частности, для уравнения Википедии M = E − N + 2Pя хочу лучше понять, что означает каждый из следующих терминов:

• E = количество ребер графа
• N = количество узлов графа
• P = количество подключенных компонентов

Я подозреваю, что либо E, либо N может быть числом точек принятия решения (если, иначе, если, for, foreach и т. Д.) В блоке кода, но я не совсем уверен, что означает, что или что означает другое. Я также предполагаю, что P относится к вызовам функций и экземплярам классов, но нет четкого определения, которое я вижу. Если бы кто-то мог пролить немного света на несколько примеров кода, это помогло бы.

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

Наконец, влияют ли регулярные выражения на цикломатическую сложность, и если да, то как?

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

Если у вас есть оператор ветвления ( ifнапример) - тогда у вас будет два выходных узла, потому что состояние может измениться двумя способами.

Другой способ вычисления числа цикломатической сложности (CCN) - это подсчет количества «областей» в графе выполнения (где «независимая область» - это круг, не содержащий других кругов). В этом случае CCN будет числом независимых регионов плюс 1 (которое будет точно таким же, как и в предыдущей формуле).

CCN используется для покрытия ветвления или покрытия пути , которое является одинаковым. CCN равно количеству различных путей ветвления, теоретически возможных в однопоточном приложении (которые могут включать в себя ветки типа " if x < 2 and x > 5 then", но это должно быть воспринято хорошим компилятором как недоступный код). Необходимо иметь как минимум такое количество различных тестовых случаев (может быть больше, поскольку некоторые тестовые примеры могут повторять пути, покрытые предыдущими, но не менее, если предположить, что каждый случай охватывает один путь). Если вы не можете покрыть путь каким-либо возможным тестовым примером - вы нашли недоступный код (хотя вам нужно будет доказать себе, почему он недоступен, возможно, x < 2 and x > 5где-то скрывается где- то вложенный ).

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

Некоторые замечания по этому поводу, которые я праздно пишу ...

В частности, для уравнения Википедии M = E - N + 2P

Это уравнение очень неправильно .

По какой-то причине МакКейб действительно использует его в своей первоначальной работе («Мера сложности», IEEE Transactions по программной инженерии, Vo .. SE-2, № 4, декабрь 1976 г.), но без обоснования и после фактического цитирования правильной формула на первой странице, которая

V (G) = E - V + P

(Здесь элементы формулы были перемаркированы)

В частности, МакКейб ссылается на книгу C.Berge, Графики и Гиперграфы (сокращенно G & HG). Прямо из этой книги :

Определение (стр. 27 внизу G & HG):

Цикломатическое число v (G) (неориентированного) графа G (который может иметь несколько несвязных компонент) определяется как:

V (G) = E - V + P

где e = количество ребер, v = количество вершин, p = количество связанных компонентов

Теорема (стр. 29 вверху G & HG) (не используется МакКейбом):

Цикломатическое число v (G) графа G равно максимальному числу независимых циклов

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

Интуитивно понятно, что набор циклов является независимым, если ни один из циклов не может быть построен из других путем наложения обходов.

Теорема (середина страницы G & HG) (используется МакКейбом):

В сильно связном графе G цикломатическое число равно максимальному числу линейно независимых цепей.

Схема является циклом, без повторений вершин и ребер , разрешенных.

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

Обратите внимание, что здесь мы перешли от неориентированных графов к сильно связным графам (которые ориентированы ... Берге не дает понять это полностью)

Теперь МакКейб применяет приведенную выше теорему, чтобы вывести простой способ вычисления «числа цикломатической сложности МакКейба» (CCN) следующим образом:

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

Теперь МакКейб утверждает (довольно смущающе, я бы сказал), что цикломатическое число модифицированного графа потока команд «соответствует нашему интуитивному представлению о« минимальном числе путей »», и поэтому мы будем использовать это число в качестве меры сложности.

Круто, так:

Число цикломатической сложности модифицированного графа потока команд может быть определено путем подсчета «наименьших» цепей в неориентированном графе. Это не особенно трудно сделать человеком или машиной, но применение приведенной выше теоремы дает нам еще более простой способ ее определения:

V (G) = E - V + P

если не обращать внимания на направленность краев.

Во всех случаях мы просто рассматриваем одну процедуру, поэтому во всем графе есть только один связанный компонент, и так:

v (G) = е - v + 1.

В случае, если рассматривать исходный граф без добавленного ребра «от входа к входу» , получается просто:

ṽ (G) = ẽ - v + 2

как ẽ = e - 1

Давайте проиллюстрируем это на примере МакКейба из его статьи:

Здесь мы имеем:

• е = 10
• v = 6
• р = 1 (один компонент)
• v (G) = 5 (мы четко считаем 5 циклов)

Формула для цикломатического числа гласит:

V (G) = E - V + P

что дает 5 = 10 - 6 + 1 и так правильно!

«Число цикломатической сложности МакКейба», приведенное в его статье,

5 = 9 - 6 + 2 (дальнейшие объяснения в статье не приведены)

что оказывается правильным (это дает v (G)), но по неправильным причинам, то есть мы используем:

ṽ (G) = ẽ - v + 2

и, таким образом, ṽ (G) = v (G) ... фу!

Но хороша ли эта мера?

В двух словах: не очень

• Не совсем понятно, как установить «граф потока команд» процедуры, особенно если обработка исключений и рекурсия входят в картину. Обратите внимание, что МакКейб применил свою идею к коду, написанному на FORTRAN 66 , языке без рекурсии, исключений и простой структуры исполнения.
• Тот факт, что процедура с решением и процедура с циклом дают один и тот же CCN, не является хорошим признаком.

• Еще менее хорош тот факт, что forциклы и whileциклы обрабатываются одинаково (обратите внимание, что в C можно злоупотреблять forвыражением a whileпо-другому; здесь я говорю о строгом for (int i=0;i<const_val;i++)цикле). Из теоретической информатики мы знаем, что эти две конструкции дают совершенно разные вычислительные мощности: примитивно-рекурсивные функции, если вы только оснащены for, частично µ-рекурсивные функции, если вы оснащены while.
• Эксперимент , имеющие эксперт судить о сложности кода показывает , что CCN не отражает идею «кода сложности», а также других меры, в частности программного обеспечения науки HALSTEAD в и познавательном функциональном размере Шао и Wangs' (последний , по- видимому победитель), см. Применимость трех показателей когнитивной сложности, 2012 г. Международная конференция по достижениям в области ИКТ для развивающихся регионов, 12-15 декабря 2012 г.
• Эмпирическая проверка показывает, что (по крайней мере, для зрелого кода) CCN сильно линейно коррелирует с LOC (строками кода), т.е. CCN естественным образом увеличивает длину процедуры, и вы также можете использовать счет LOC для выражения сложности. Лучшей мерой, чем абсолютный CCN, может быть CCN / LOC. См., В частности: пересмотр показателей цикломатической сложности - DSpace @ MIT и роль эмпиризма в повышении надежности будущего программного обеспечения

В качестве продолжения, цикломатическая сложность напрямую коррелирует с количеством модульных тестов, необходимых для 100% покрытия пути?

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

Наконец, влияют ли регулярные выражения на цикломатическую сложность, и если да, то как?

Да, если вы хотите быть точным, хотя большинство инструментов анализа кода, похоже, не учитывают их таким образом. Регулярные выражения - это просто конечные автоматы, поэтому я предполагаю, что их CC можно рассчитать по графику FSM, но это будет довольно большое число.