Softwaremetrik: Zyklomatische Komplexität

Ich hatte es ja letzte Woche angekündigt, dass wir in den nächsten Wochen ab und zu mal eine Softwaremetrik besprechen wollen. Und heute soll es schon damit losgehen. Als erstes kommt natürlich die am häufigsten angewendete Metrik dran. Zyklomatische Komplexität (ZK) oder auch Cyclomatic Complexity oder auch McCabe Metrik. Wir nennen es aber Zyklomatische Komplexität, da ich ich ein Freund der deutschen Sprache bin (auch wenn ich sie nicht immer beherrsche).

Erinnern wir uns noch mal kurz an die Definition. Eine Softwaremetrik bildet eine Eigenschaft von Software in einen Zahlenwert ab. Bei der ZK geht es darum herauszufinden, wie komplex und damit auch wie wartbar eine Funktion ist. Wir gehen also davon aus, dass eine Funktion, je komplexer sie wird, desto eher Probleme bereiten wird. Was ich mit meiner Erfahrung auch bestätigen kann und ihr sicherlich auch.

Das Problem ist jetzt natürlich herauszufinden, wie Komplexität zu definieren ist. Für McCabe, den Erfinder dieser Metrik, war es die Anzahl der linear unabhängigen Pfaden durch die Funktion. Also wie viele Wege gibt es durch eine Methode. Nehmen wir ein einfaches Beispiel:

function not( $boolVal )
{
  if ( $boolVal == true ) {
    $result = false;
  } else {
    $result = true;
  }
  return $result;
}

Kann ich eine Funktion überhaupt not nennen? Egal. Mir zumindest. Schauen wir uns die Methode an, dann fallen uns zwei Wege durch diese auf. Einmal den true Fall und einmal den false Fall. Damit wäre der ZC Wert für diese Funktion 2. Aber wie berechnet man das automatisiert für jede x-beliebige Funktion.

Der formelle Ansatz, der aus der Graphentheorie stammt, ist nicht so wirklich einfach. Jede Methode kann durch einen Kontrollflußgraphen (Beispiel) dargestellt werden (gehen wir mal wann anders drauf ein, versprochen). Die Zyklomatische Komplexitätszahl (ZKZ) wird dann durch folgende Funktion dargestellt:

ZKZ=e−n+2

Wobei e die Anzahl der Kanten ist und n die Anzahl der Knoten. Nach Andre’s wunderbarer Einführung in die Graphentheorie sollte das für euch ja ziemlich einfach sein. Um das automatisiert zu berechnen könnte man jetzt komplexe Algorithmen aufstellen. Muss man aber gar nicht. Denn wie der Zufall es will, gibt es eine viel einfache Funktion, die diesen Wert berechnet. Wir müssen nämlich nur alle bedingte Anweisungen aufeinander addieren, eins drauf addieren und schon haben wir den gleichen Wert. In PHP wäre es also die Anzahl aller IF, CASE, DEFAULT, CATCH, FOR, FOREACH, WHILE, DO und ELSEIF. Das zu berechnen sollte uns doch gelingen. Zählen wir schnell unser Beispiel durch. Eins + Eins = Zwei. Juhu, alles bewiesen. Wir haben jetzt also eine einfache Formel zum Berechnen der Zyklomatischen Komplexität.

Natürlich müssen wir das nicht mehr selbst berechnen. Der PHP_CodeSniffer hat bereits einen solchen Sniff integriert und auch pDepends von Manuel Pichler kann diese Zahl berechnen. Einen Wert, den man immer wieder hört, den die Komplexität nicht überschreiten soll ist 10. Meiner Meinung ist der Wert schon viel zu hoch, aber die Allgemeinheit scheint da anders zu denken. Eine Methode mit 5 FOR-Schleifen und 5 IF-Bedingungen schreit doch förmlich umgeschrieben zu werden. Den Wert kann man aber für sich selbst definieren.

So das war der erste Teil meiner Metriken Reihe. Ist doch länger geworden als gedacht, deswegen schicke ich morgen nochmal kurz was nach. Als nächstes kommt die n-Path Complexity, die ich nächste Woche angehen will. Bis dahin muss ich mir aber nochmal ein paar Dinge durchlesen. Was mich aber noch interessieren würde, wäre der Wert, den ihr als Limit setzen würdet. Ab welchem Wert würdet ihr euch eine Funktion noch einmal anschauen?

9 Comments

Ich versuche es mal zu rekapitulieren, damit ich weiß, ob ich den Sinn dahinter verstanden habe: Die ZKZ gibt die Anzahl der vom „linearen Fluss“ abweichenden Pfade minus Eins an – Null wäre in der Hinsicht sinnvoller gewesen. Denn in einem linearen Programmfluss hat jeder Knoten, mit Ausnahme des letzten Knotens, nur eine ausgehende Kante, weshalb man durch Subtraktion dieser Kanten auf (n-(e+1)) = (n-e-1) = (e-n+1) kommt und durch die Tatsache, dass der kleinste Wert der ZKZ Eins betragen soll, letztendlich zu (e-n+2) gelangt.
Beim Veranschaulichen der Kontrollstrukturen stellt man fest, dass jede genau zwei ausgehende Kanten hat, weshalb das Zählen dieser Strukturen tatsächlich ausreichend ist.

Da ich gerne Higher-Order-Functions, wie z.B. array_map, verwende, frage ich mich, inwiefern Funktionsaufrufe in die ZKZ integriert werden. Denn ein „$array = array_map($f, $array)“ ist semantisch äquivalent zu „foreach($array as $k => $v) $array[$k] = $f($v)“, was die ZKZ um Eins erhöhen würde, es aber nach obiger Definition nicht tut. Ist das also nur ein Trick um die ZKZ herabzusetzen oder ist es eine für McCabe gewollte Methode, um eine Funktion wartbarer zu machen?

Ich denke es gibt noch ein Problem mit der Do-While Schleife.
Da in der einen Schleife schon zwei Schlüsselwörter vorkommen, würde diese Schleife auch zwei mal gezählt(Angenommen die Do-While Schleife wird nicht gesondert Behandelt).

Daher könnte man das DO als Schlüsselwort weglassen.

Eine do-while-Schleife hat eine andere Semantik als eine while-Schleife, weshalb die beiden Schleifen vom Parser unterschiedlich gehandhabt werden. D.h. diese Unterscheidung wird von den Tools, sofern sie auf PHP-internen Erweiterungen (z.B. bytekit) beruhen, bereits getroffen.

@Andre: McCabe verbindet den End- und den Startknoten miteinander, ich denke, da kommt die fehlende Kante her und die Formel stimmt wieder?
Was die Higher-Order angeht, da bin ich überfragt, müsste man mal schauen, was im Kontrollflussgraphen dabei rauskommt. Damit die Formel aber „einfach“ bleibt, könnte ich mir vorstellen, dass man es einfach weglässt und wie eine normale Funktion behandelt, besonders, da sie ja auch ausgelagert ist).

>Da ich gerne Higher-Order-Functions, wie z.B. array_map, verwende, frage >ich mich, inwiefern Funktionsaufrufe in die ZKZ integriert werden. Denn >ein “$array = array_map($f, $array)” ist semantisch äquivalent zu >“foreach($array as $k => $v) $array[$k] = $f($v)”, was die ZKZ um Eins >erhöhen würde, es aber nach obiger Definition nicht tut.

Ist auch korrekt so, auch higher order functions sind eine Art der Kapselung. Daher wird der Kontrollflussgraph hier auch nicht groesser.

Ich fand schon im Eingangsbeitrag, dass es sehr schwer ist ein so komplexes Thema in isolierte Bestandteile aufzusplitten und zu betrachten. Andererseits ist es ziemlich interessant und wenn man sich damit nicht in kurzen Häppchen befassen kann, ist es eigentlich sehr schlecht für den Einsatz in der Praxis.

Zunächst: CC ist eine der älteren Metriken (Haarspalter würden an dieser Stelle darauf hinweisen, dass nach gängiger Definition CC kein Maß ist, aber das ist unerheblich) die immer wieder zitierten Aussagen bzgl. bestimmter Grenz- oder Zielwerte haben ihren Ursprung in der Messung von FORTRAN Progammen (die Älteren werden sich an die Programmiersprache noch erinnern).
Im Laufe der Zeit wurden verschiedene Ansätze verfolgt, um den Ansatz an neue Anforderungen anzupassen (z.B. Fenton-Whitty-Theory mit Sequencing und Nesting Beschreibungen).

Aber nun zur eigentlichen Frage: Wenn man nach einem absoluten, kontextunabhängigen Schwellwert führt ist der Wert 10 sicher zu nennen. In Zeiten von verteilten Applikationen stellt sich aber eher die Frage: Ist ein System mit 15 Klassen im Bereich CC 6-8 komplexer als ein System mit 25 Klassen im Bereich CC 4-5?
Um diese Fragen nach der Systemkomplexität beantworten zu können, kommt man mit CC nicht sehr weit. Obgleich es natürlich ein guter Startpunkt ist und einige Aussagen erlaubt (wenn auch keine rationalen Aussagen so doch zumindest ordinale aussagen).

Pingback: Wieso Code Kopieren gut ist : Gjero Krsteski

Pingback: PHP bekommt frischen CRAP | PHP hates me - Der PHP Blog