Comprendre la complexité cyclomatique

J'ai récemment rencontré la complexité cyclomatique et j'aimerais essayer de mieux la comprendre.

Quels sont les exemples pratiques de codage des différents facteurs qui entrent dans le calcul de la complexité? Plus précisément, pour l'équation Wikipedia de M = E − N + 2P, je veux mieux comprendre ce que chacun des termes suivants signifie:

• E = le nombre d'arêtes du graphique
• N = le nombre de nœuds du graphique
• P = le nombre de composants connectés

Je soupçonne que E ou N peut être le nombre de points de décision (si, sinon si, pour, foreach, etc.) dans un bloc de code, mais je ne sais pas trop qui est lequel ou ce que l'autre signifie. Je suppose également que P fait référence aux appels de fonction et aux instanciations de classe, mais il n'y a pas de définition claire étant donné que je peux voir. Si quelqu'un pouvait apporter un peu plus de lumière avec des exemples de code clair pour chacun, cela aiderait.

À titre de suivi, la complexité cyclomatique est-elle directement liée au nombre de tests unitaires nécessaires pour une couverture à 100% du chemin ? À titre d'exemple, une méthode d'une complexité de 4 indique-t-elle que 4 tests unitaires sont nécessaires pour couvrir cette méthode?

Enfin, les expressions régulières affectent-elles la complexité cyclomatique, et si oui, comment?

Concernant la formule: les nœuds représentent les états, les arêtes représentent les changements d'état. Dans chaque programme, les instructions entraînent des changements dans l'état du programme. Chaque instruction consécutive est représentée par un bord, et l'état du programme après (ou avant ...) l'exécution de l'instruction est le nœud.

Si vous avez une instruction de branchement ( ifpar exemple) - alors vous avez deux nœuds qui sortent, car l'état peut changer de deux manières.

Une autre façon de calculer le nombre de complexité cyclomatique (CCN) est de calculer le nombre de "régions" dans le graphique d'exécution que vous avez (où "région indépendante" est un cercle qui ne contient pas d'autres cercles). Dans ce cas, le CCN sera le nombre de régions indépendantes plus 1 (qui serait exactement le même nombre que la formule précédente vous donne).

Le CCN est utilisé pour la couverture de branchement ou la couverture de chemin , qui est la même. Le CCN est égal au nombre de chemins de branchement différents théoriquement possibles dans une application unique (qui peut inclure des branches comme " if x < 2 and x > 5 then", mais qui devrait être capturé par un bon compilateur comme un code inaccessible). Vous devez avoir au moins ce nombre de cas de test différents (peut être plus car certains cas de test peuvent être des chemins répétitifs couverts par les précédents, mais pas moins en supposant que chaque cas couvre un seul chemin). Si vous ne pouvez pas couvrir un chemin avec un cas de test possible - vous avez trouvé du code inaccessible (même si vous devrez réellement vous prouver pourquoi il est inaccessible, probablement quelques imbriqués x < 2 and x > 5qui se cachent quelque part).

Quant aux expressions régulières - elles affectent bien sûr, comme tout autre morceau de code. Cependant, le CCN de la construction regex est probablement trop élevé pour être couvert dans un seul test unitaire, et vous pouvez supposer que le moteur regex a été testé et ignorer le potentiel de branchement des expressions pour vos besoins de test (sauf si vous testez votre moteur regex, bien sûr).

Quelques remarques à ce sujet que j'écris paresseusement ...

Plus précisément, pour l'équation de Wikipedia de M = E - N + 2P

Cette équation est très fausse .

Pour une raison quelconque, McCabe l'utilise en effet dans son article original ("A Complexity Measure", IEEE Transactions on Software Engineering, Vo .. SE-2, n ° 4, décembre 1976), mais sans le justifier et après avoir cité la bonne formule sur la première page, qui est

v (G) = e - v + p

(Ici, les éléments de formule ont été renommés)

Plus précisément, McCabe fait référence au livre C.Berge, Graphs and Hypergraphs (abrégé ci-dessous pour G&HG). Directement à partir de ce livre :

Définition (page 27 en bas de G&HG):

Le nombre cyclomatique v (G) d'un graphe G (non orienté) (qui peut avoir plusieurs composantes déconnectées) est défini comme:

v (G) = e - v + p

où e = nombre d'arêtes, v = nombre de sommets, p = nombre de composants connectés

Théorème (page 29 en haut de G&HG) (non utilisé par McCabe):

Le nombre cyclomatique v (G) d'un graphe G est égal au nombre maximum de cycles indépendants

Un cycle est une séquence de sommets commençant et se terminant au même sommet, chacun des deux sommets consécutifs de la séquence étant adjacents l'un à l'autre dans le graphique.

Intuitivement, un ensemble de cycles est indépendant si aucun des cycles ne peut être construit à partir des autres en superposant les marches.

Théorème (page 29 au milieu de G&HG) (tel qu'utilisé par McCabe):

Dans un graphe G fortement connecté, le nombre cyclomatique est égal au nombre maximum de circuits linéairement indépendants.

Un circuit est un cycle sans répétition de sommets et d'arêtes autorisée.

Un graphe orienté est dit fortement connecté si chaque sommet est accessible à partir de chaque autre sommet en passant par les bords dans leur direction désignée.

Notez qu'ici nous sommes passés de graphes non orientés à des graphes fortement connectés (qui sont dirigés ... Berge ne le rend pas tout à fait clair)

McCabe applique maintenant le théorème ci-dessus pour dériver un moyen simple de calculer un «nombre de complexité cyclomatique McCabe» (CCN) ainsi:

Étant donné un graphique dirigé représentant la «topologie de saut» d'une procédure (le graphique de flux d'instructions), avec un sommet désigné représentant le point d'entrée unique et un sommet désigné représentant le point de sortie unique (le sommet du point de sortie peut devoir être «construit» en l'ajoutant en cas de retours multiples), créez un graphe fortement connecté en ajoutant une arête dirigée du sommet du point de sortie au sommet du point d'entrée, rendant ainsi le sommet du point d'entrée accessible à partir de tout autre sommet.

McCabe postule maintenant (je dirais plutôt confus) que le nombre cyclomatique du graphe d'instructions modifié "est conforme à notre notion intuitive de" nombre minimum de chemins "", et nous utiliserons donc ce nombre comme mesure de complexité.

Cool, donc:

Le nombre de complexité cyclomatique du graphe de flux d'instructions modifié peut être déterminé en comptant les "plus petits" circuits dans le graphe non orienté. Ce n'est pas particulièrement difficile à faire par l'homme ou la machine, mais l'application du théorème ci-dessus nous permet de le déterminer encore plus facilement:

v (G) = e - v + p

si l'on ne tient pas compte de la directionnalité des bords.

Dans tous les cas, nous considérons une seule procédure, il n'y a donc qu'un seul composant connecté dans tout le graphe, et donc:

v (G) = e - v + 1.

Dans le cas où l'on considère le graphe d'origine sans le bord "sortie-entrée" ajouté , on obtient simplement:

ṽ (G) = ẽ - v + 2

comme ẽ = e - 1

Illustrons en utilisant l'exemple de McCabe tiré de son article:

Ici nous avons:

• e = 10
• v = 6
• p = 1 (un composant)
• v (G) = 5 (nous comptons clairement 5 cycles)

La formule du nombre cyclomatique dit:

v (G) = e - v + p

ce qui donne 5 = 10 - 6 + 1 et donc correct!

Le "nombre de complexité cyclomatique McCabe" tel qu'il est donné dans son article est

5 = 9 - 6 + 2 (aucune autre explication n'est donnée dans le document sur la façon dont)

qui se trouve être correct (il donne v (G)) mais pour les mauvaises raisons, c'est à dire que nous utilisons:

ṽ (G) = ẽ - v + 2

et donc ṽ (G) = v (G) ... ouf!

Mais cette mesure est-elle bonne?

En deux mots: pas très

• Il n'est pas entièrement clair comment établir le "graphe de flux d'instructions" d'une procédure, en particulier si la gestion des exceptions et la récursivité entrent dans l'image. Notez que McCabe a appliqué son idée au code écrit en FORTRAN 66 , un langage sans récursivité, sans exception et une structure d'exécution simple.
• Le fait qu'une procédure avec décision et une procédure avec boucle produisent le même CCN n'est pas bon signe.

• Encore moins bon est le fait que les forboucles et les whileboucles sont gérées de la même manière (notez qu'en C, on peut abuser du forpour exprimer une whileautre manière; ici je parle de la for (int i=0;i<const_val;i++)boucle stricte ). Nous savons par l'informatique théorique que ces deux constructions produisent des puissances de calcul totalement différentes: fonctions primitives-récursives si vous n'en êtes équipé que for, fonctions μ-récursives partielles si vous en êtes équipé while.
• Une expérience ayant des experts jugent la complexité du code montre que NCF ne capture pas l'idée de « la complexité du code », ainsi que d' autres mesures, en particulier la science du logiciel de Halstead et la taille fonctionnelle cognitive de Shao et Wangs (ce dernier étant apparemment le gagnant), voir Applicabilité de trois métriques de complexité cognitive, Conférence internationale de 2012 sur les progrès des TIC pour les régions émergentes, 12-15 décembre 2012
• La vérification empirique montre que (au moins pour le code mature), CCN est fortement linéairement corrélé avec LOC (lignes de code), c'est-à-dire que le CCN augmente naturellement avec la longueur de la procédure et vous pourriez aussi bien utiliser le nombre LOC pour exprimer la complexité. Une meilleure mesure que le CCN absolu pourrait être CCN / LOC. Voir en particulier: Les métriques de complexité cyclomatique revisitées - DSpace @ MIT et Le rôle de l'empirisme dans l'amélioration de la fiabilité des futurs logiciels

À titre de suivi, la complexité cyclomatique est-elle directement liée au nombre de tests unitaires nécessaires pour une couverture à 100% du chemin?

Oui, fondamentalement. C'est aussi une bonne idée d'utiliser la complexité cyclomatique comme indicateur du moment de la refactorisation. D'après mon expérience, la testabilité et la réutilisabilité augmentent considérablement pour un CC inférieur (bien que vous devriez être pratique - ne pas trop refactoriser, et certaines méthodes auront un CC élevé en raison de leur nature - il n'est pas toujours logique d'essayer de le forcer inférieur).

Enfin, les expressions régulières affectent-elles la complexité cyclomatique, et si oui, comment?

Oui, si vous voulez être précis, bien que la plupart des outils d'analyse de code ne semblent pas les prendre en considération de cette manière. Les expressions régulières ne sont que des machines à états finis, donc je suppose que leur CC pourrait être calculé à partir du graphique FSM, mais ce serait un nombre assez important.