Просмотр отдельных изменений

''''Цикломати́ческая сло́жность програ́ммы''' ({{lang-en|Cyclomatic complexity of a program}}) — структурная (или топологическая) [[Качество программного обеспечения|мера сложности программ]], используемая для измерения качества [[программное обеспечение|программного обеспечения]], основанная на методах статического анализа кода. ЦСП равна увеличенному на единицу [[Цикломатическое число|цикломатическому числу]] графа программы. Она была разработана Томасом Дж. Мак-Кейбом в [[1976 год]]у; он использовал эти показатели сложности для программ. Он производил непосредственные численные измерения для линейно независимых путей в [[Исходный код|исходных кодах]] программ. Концепция, но не метод, отчасти похож на измерение сложности с помощью [[:en:Flesch–Kincaid readability test|теста удобочитаемости Флеша-Кинкейда]]{{ref-en}} для общего текста. При вычислении цикломатической сложности используется [[control flow graph|граф потока управления]] программы: [[Узел (граф)|узлы]] [[Граф (математика)|графа]] соответствуют неделимым группам команд программы и [[Ориентированный граф|ориентированным]] [[Ребро (теория графов)|рёбрам]], каждый из которых соединяет два узла и соответствует двум командам, вторая из которых может быть выполнена сразу после первой. Цикломатическая сложность может также быть применена для отдельных [[Функция (программирование)|функций]], [[Модульность (программирование)|модулей]], [[Метод (языки программирования)|методов]] или [[Класс (программирование)|классов]] в пределах программы. Эта стратегия [[Тестирование программного обеспечения|тестирования]] называется ''основным [[:Категория:Управление потоком|маршрутом]] тестирования'' Мак-Кейба, который первым предложил его. Это тестирование каждого линейного независимого маршрута через программу; в этом случае, число тестов должно быть равно цикломатической сложности программы.<ref>{{cite web | url = http://users.csc.calpoly.edu/~jdalbey/206/Lectures/BasisPathTutorial/index.html | title = Основной маршрут тестирования | author = A J Sobey | archiveurl = http://www.webcitation.org/67CusdjXN | archivedate = 2012-04-26 }}</ref> == Описание == [[Файл:Control flow graph of function with loop and an if statement without loop back.svg|thumb|250px|right|Граф управления потоком простой программы. Программа начинает выполняться с красного узла, затем идут циклы (после красного узла идут две группы по три узла). Выход из цикла осуществляется через условный оператор (нижняя группа узлов) и конечный выход из программы в синем узле. Для этого графа E = 9, N = 8 и P = 1, цикломатическая сложность программы равна 3.]] Цикломатическая сложность части программного кода — счётное число линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек решений, таких, как указания <code>IF</code> или циклы <code>FOR</code>, то сложность равна единице, поскольку, есть только единственный маршрут через код. Если код имеет единственный оператор <code>IF</code>, содержащий простое условие, то должно быть два пути через код: один путь через оператор <code>IF</code> с оценкой как <code>TRUE</code> и один — как <code>FALSE</code>. Математически, цикломатическая сложность [[Структурное программирование|структурного программирования]]<ref>Here «structured» means in particular «with a single exit ([[return statement]]) per function».</ref> — определение с помощью ссылок от [[Базовый блок|базового блока]]{{ref-en}} программы на [[Ориентированный граф|ориентированный граф]] и с помощью рёбер между двумя основными блоками, если управление может переходить с первого на второй граф управления потоком программы. Тогда сложность определяется как:<ref name="mccabe76">{{cite journal| last=McCabe| year=1976|month=December| journal=IEEE Transactions on Software Engineering| pages=308–320| title=A Complexity Measure| url=http://classes.cecs.ucf.edu/eel6883/berrios/notes/Paper%204%20(Complexity%20Measure).pdf| format={{dead link|date=May 2010}}}}</ref>: : ''M'' = ''E'' &minus; ''N'' + 2''P'', где: : ''M'' = цикломатическая сложность, : ''E'' = количество рёбер в графе, : ''N'' = количество узлов в графе, : ''P'' = количество [[Компонента связности графа|компонент связности]]. [[Файл:Control flow graph of function with loop and an if statement.svg|thumb|250px|right|''Сильносвязанный'' граф управления потоком той же функции, использующийся для вычисления альтернативным путём. Для этого графа E = 10, N = 8 и P = 1, следовательно, цикломатическая сложность программы всё ещё равна 3.]] В другой формулировке используется граф, в котором каждая точка выхода соединена с обратной — точкой входа. В этом случае говорят, что граф будет сильносвязанным и цикломатическая сложность программы будет равняться [[цикломатическое число|цикломатическому числу]] этого графа (также известному как [[:en:Betti_number#Example:_the_first_Betti_number_in_graph_theory|first Betti number]]{{ref-en}}), которое определяется как:<ref name="mccabe76" /> : ''M'' = ''E'' &minus; ''N'' + ''P'' Это может рассматриваться как вычисление числа [[Линейная независимость|линейно независимых]] циклов, которые существуют в графе, то есть тех циклов, которые не содержат в себе других циклов. Надо учитывать, что каждая точка выхода из цикла становится точкой входа в него, то есть по крайней мере одна [[итерация]] его для каждой точки выхода. Для простой программы, или подпрограммы, или метода <code>P</code> всегда эквивалентно <code>1</code>. Цикломатическая сложность может, тем не менее, применяться к некоторым таким программам или подпрограммам (например, ко всем методам в [[Класс (программирование)|классе]]), в таком случае <code>P</code> эквивалентен числу программ, о которых идёт речь, как о каждой подпрограмме, проявляющейся как разрозненное подмножество графа. Может быть показано, что цикломатическая сложность любой структурированной программы с только одной точкой входа и одной точкой выхода эквивалентна числу точек решения (то есть, <code>if</code> операторных или условного циклов), содержащихся в этой программе, плюс один.<ref name="mccabe76"/><ref name="ecst">{{cite book| title=Encyclopedia of Computer Science and Technology| author=Belzer, Kent, Holzman and Williams| publisher=CRC Press|year=1992| pages=367–368}}</ref> Цикломатическая сложность может быть распространена на программу с многочисленными точками выхода; в этом случае она равна:<ref name="ecst" /><ref name="harrison">{{cite journal| journal=Software: Practice and Experience| title=Applying Mccabe's complexity measure to multiple-exit programs| author=Harrison| date=October 1984| publisher=J Wiley & Sons}}</ref> : &pi; &minus; s + 2 где: : &pi; — число точек решения в программе, : s — число точек выхода. === Формальное определение === Формально, цикломатическая сложность может быть определена, как относительное [[число Бетти]], как размер [[:en:relative homology|относительнооднородной]] группы: : <math>M := b_1(G,t) := \operatorname{rank}\,H_1(G,t) </math> Это читается, как «первый однородный граф ''G'', относительно терминального узла ''t''». Этот технический путь произносится, как «число линейно независимых маршрутов через граф от входа к выходу», где: * «линейно независимый» соответствует однородности и означает, что один не возвращается в исходное состояние двойного счета; * «маршрут» соответствует ''нальной'' однородности: маршруту соответствует одномерный объект; * «относительно» означает, что путь должен начаться и закончится в точке входа или выхода, соответственно. Это соответствие интуитивно понятно как цикломатическая вложенность, и может быть вычислено как указанно выше. Кроме того, его можно вычислить через абсолютное [[число Бетти]] (абсолютно однородное — не относительное) определяющее все терминальные узлы данного компонента (или равно, получение маршрутов соединяющих входы с выходами), в этом случае (вызов нового, расширенного графа <math>\tilde G</math>, которым он является) получаем: : <math>M = b_1(\tilde G) = \operatorname{rank}\,H_1(\tilde G)</math> Это соответствие характеризуется цикломатической сложностью как «количество циклов плюс количество компонентов». === Этимология (происхождение названия) === Название ''цикломатическая сложность'' может попервоначалу показаться не являющимся целостным, но это не так, так как эта метрика не только считает циклы в программе. Она должна быть первостепенно заинтересована в подсчёте количества других циклов, тех, которые контролируются по построенному по программе графу, которые заключаются в присутствии веток возврата (ветки от выходного узла к входному), которые выявляются при построении графа.<ref name="mccabe76" /> == Применение == === Ограничение сложности при разработке === Одно из оригинальных предложений Мак-Кейба в том, что необходимо ограничивать сложность программ в течение их разработки; он рекомендует, чтобы программистов обязывали считать сложность разрабатываемых ими модулей, и разделять модули на более мелкие всякий раз, когда цикломатическая сложность этих модулей превысит десяти.<ref name="mccabe76" /> Эта практика была адаптирована [[Национальный институт стандартов и технологий (США)|НИСТ]]-ом для методологии [[Структурное тестирование|структурного тестирования]]. С помощью этих наблюдений, со времени исходной публикации Мак-Кейба, счёт от десяти считается, что преемственная надёжность подтверждена. В некоторых случаях может быть более целесообразны ослабленные ограничения и разрешить модули со сложностью выше, чем 15. Методологически признано, что существуют случайные причины, выводящие за рамки согласованного лимита, и это сформулировано как рекомендация: "Для каждого модуля, либо ограничивать цикломатическую сложность до согласованных пределов, либо предоставить письменное объяснение того, почему лимит был превышен". {{начало цитаты|источник = Мак-Кейб<ref>{{cite web | author = Мак-Кейб | authorlink = | coauthors = | date = | url = http://hissa.nist.gov/HHRFdata/Artifacts/ITLdoc/235/title.htm | title = Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric | format = | work = | publisher = | accessdate = 2010-06-03 | lang = en | description = | archiveurl = http://www.webcitation.org/67CutLsR9 | archivedate = 2012-04-26 }}</ref>}} Для каждого модуля, либо ограничивай цикломатическую сложность (до оговоренного предела), либо предоставляй запись, поясняющую, почему ограничение должно быть превышено. {{oq|en|For each module, either limit cyclomatic complexity to [the agreed-upon limit] or provide a written explanation of why the limit was exceeded.}} {{конец цитаты}} === Применение при тестировании программного обеспечения === Другое применение цикломатической сложности — при [[детерминизм|детерминизме]] числа проведённых тестов, необходимых для достижения тщательного покрытия тестированием модуля. Он полезен, поскольку цикломатическая сложность ''M'' имеет два свойства, для конкретного [[Модуль (программирование)|модуля]]: * ''M'' — верхняя граница для числа произведённых тестов, которые необходимо достичь для полного [[Покрытие кода|покрытия ветки]]; * ''M'' — пониженная граница для числа маршрутов через контролируемый поток графа (КПГ). Допустим, тест применяется каждый раз для единственного маршрута, тогда необходимое количество раз применений теста определяется [[Покрытие кода|числом покрытия]], равного числу путей, которые действительно могут быть использованы при работе программы. Но некоторые пути могут быть невозможными, так что, число путей через КПГ — это, несомненно, верхняя граница числа тестов, для обеспечения покрытия пути (''возможного'' пути), чей номер идёт последним, которое иногда может быть меньше чем ''M''. Все три вышеуказанные числа могут быть равны: покрытие ветки <math>\leq</math> cyclomatic complexity <math>\leq</math> количества путей. Для примера рассмотрим нижеприведённую программу, состоящую из последовательного применения двух операторов ''if-then-else''. <source lang="c"> if( c1() ) f1(); else f2(); if( c2() ) f3(); else f4(); </source> [[Файл:Control flow graph of function with two if else statements.svg|thumb|250px|right|В вышеуказанном графе управления потоком исходного кода красный кружок обозначает точку входа в функцию, синий кружок — точку выхода. Выход соединён со входом, что делает граф сильносвязанным.]] === Связность === {{Заготовка раздела}} === Корреляция числа дефектов === {{Заготовка раздела}} * Сложность больше 50 означает очень высокий риск и практически не тестируемый код.<ref>[http://pyobject.ru/blog/2006/07/10/cyclomatic-complexity/ Цикломатическая сложность]</ref> == См. также == == Примечания == {{reflist}} == Ссылки == * [http://www.viva64.com/terminology/Cyclomatic_complexity_rus.html Цикломатическая сложность] {{Computer-sci-stub}} {{rq|translate|style}} [[Категория:Качество программного обеспечения]]'