Complejidad NPath
| Sigla | NPATH |
| Aspecto | «Complejidad» |
| Se mide en | método |
| Tipo de valor | recuento (entero, mínimo 1 en las herramientas; puede ser muy grande) |
| Dirección | más alto es peor |
| Umbrales de referencia | 200: límite informal del grupo de Nejmeh y valor por defecto de Checkstyle y PMD |
| Origen | Brian A. Nejmeh, 1988 |
| Stau Metro | no la calcula |
En pocas palabras
Cuenta de cuántas formas distintas se puede recorrer un método de principio a fin sin dar vueltas en un bucle. Un
if ofrece dos caminos; dos if seguidos ofrecen cuatro, porque cada camino del primero se puede combinar con
cada camino del segundo. Por eso el número crece muy deprisa: diez if seguidos dan más de mil caminos.
Qué mide
Mide la cantidad de combinaciones de decisiones que puede tomar un método en una ejecución. Es la diferencia esencial con la «complejidad ciclomática»:
- la complejidad ciclomática suma las decisiones: cuenta los caminos independientes, los que bastan para pasar por cada rama al menos una vez;
- NPath multiplica las decisiones que van en secuencia: cuenta los caminos completos, todas las combinaciones posibles de ramas.
Le importa a quien prueba el código. Pasar por cada rama exige como mucho tests; recorrer cada combinación
de ramas exige tantos tests como caminos. Un método con cinco if en fila tiene , y dos tests (todas las
condiciones ciertas, todas falsas) ya pasan por todas sus ramas, pero tiene 32 caminos completos: si las decisiones
interactúan entre sí (la tercera usa un valor que cambió la primera), los errores pueden estar en combinaciones que
esos tests no recorren.
Un camino acíclico es un recorrido del método desde la entrada hasta una salida que no repite ninguna vuelta de un bucle. Se excluyen las repeticiones porque, con ellas, cualquier bucle daría un número infinito de caminos: el bucle se trata como «se entra en el cuerpo» o «no se entra».
Para quien empieza. Imagina un formulario con tres casillas que se pueden marcar o no. Hay tres decisiones, pero formas de rellenarlo. La complejidad ciclomática ve las tres casillas; NPath ve las ocho combinaciones.
Cómo se calcula
Nejmeh no definió NPath sobre el grafo de control, como hizo McCabe, sino sobre la sintaxis: una regla por cada tipo de sentencia, aplicada de dentro afuera. La idea es:
- una secuencia de sentencias vale el producto de lo que vale cada una;
- una decisión vale la suma de lo que valen sus alternativas;
- una sentencia sin decisiones vale 1, con una excepción que se ve más abajo.
Las reglas del artículo original, tal como las reproducen Bagnara y otros (2016) para un lenguaje como C, son estas:
| Construcción | Valor |
|---|---|
secuencia S1 S2 … |
producto de los valores de cada sentencia |
sentencia de expresión E; |
valor de E |
if (E) S1 |
valor de S1 + 1 + valor de E |
if (E) S1 else S2 |
valor de S1 + valor de S2 + valor de E |
while (E) S y do S while (E) |
valor de S + valor de E + 1 |
for (E1; E2; E3) S |
valor de S + valores de E1, E2 y E3 + 1 |
switch (E) |
suma de los valores de cada case y del default + valor de E |
return E |
el mayor entre 1 y el valor de E |
return, break, continue |
1 |
bloque { S } |
valor de S |
| cualquier otra sentencia | 1 |
expresión E1 ? E2 : E3 |
valores de E1, E2 y E3 + 2 |
expresión E1 && E2 o E1 || E2 |
valores de E1 y E2 + 1 |
| cualquier otra expresión | suma de los valores de sus partes; una variable o una constante vale 0 |
Fíjate en el + 1 del if sin else: es el camino que no entra en el cuerpo. Y en que cada && o || añade un
camino, porque el cortocircuito hace que la condición pueda fallar de una forma más.
Una expresión sin &&, || ni ?: vale 0, y por eso, en la definición original, una sentencia como x = 1;
también vale 0 (ver «Para profundizar»). Checkstyle y PMD dan 1 a toda sentencia que no sea de control, y los
ejemplos de esta página siguen ese criterio. Con él, decisiones simples en secuencia valen , mientras que
vale : diez if sin else en fila dan caminos frente a una complejidad ciclomática
de 11.
Ejemplo
Con el criterio de Checkstyle y PMD, que cuentan 1 por cada sentencia simple:
enum Priority { HIGH, LOW, NORMAL }
record Order(boolean isPaid, boolean isLate, Priority priority) { }
static String label(Order o, boolean verbose) {
String s; // sentencia simple: 1
if (o.isPaid()) { // if-else: 1 + 1 + 0 = 2
s = "paid";
} else {
s = "pending";
}
if (o.isLate() && verbose) { // if sin else: 1 + 1 + 1 (&&) = 3
s += " (late)";
}
switch (o.priority()) { // switch: 1 + 1 + 1 + 0 = 3
case HIGH -> s = "!" + s;
case LOW -> s = s + ".";
default -> { }
}
return s; // return: 1
}
El cuerpo es una secuencia de cinco sentencias, así que se multiplican:
Aquí el número coincide con la realidad: hay 2 formas de pasar el primer if, 3 de pasar el segundo (isLate
falso; isLate cierto y verbose falso; los dos ciertos) y 3 de pasar el switch.
La complejidad ciclomática del mismo método, contando como Stau Metro, es (dos if, un
&& y dos reglas case que no son default). La prueba estructurada de McCabe pide 6 tests; recorrer todas las
combinaciones pide 18.
Cómo interpretarla
El único umbral con historia es 200. La documentación de Checkstyle recoge que, según Nejmeh, su grupo usaba
un límite informal de 200 por rutina, que las que lo superaban eran candidatas a descomponerse y que el valor
procede de estudios de AT&T Bell Laboratories. Checkstyle (max) y PMD (reportLevel) traen 200 como valor por
defecto; la propia documentación de Checkstyle pide no aplicarlo con fanatismo.
- Un valor bajo (decenas) indica un método con pocas decisiones o con decisiones anidadas, que se excluyen entre sí.
- Un valor alto indica muchas decisiones en secuencia dentro del mismo método. Cada bloque
ifque se añade al final de un método multiplica el total. - Un valor desorbitado (miles o millones) aparece con facilidad en métodos largos de validación o de transformación con muchos pasos opcionales. No significa que haya que escribir millones de tests, sino que nadie va a probar todas las combinaciones, y que el método debería partirse.
Qué hacer con un valor alto. Lo más eficaz es extraer métodos: si un método con tres bloques de 6 caminos cada uno () pasa cada bloque a un método propio, el original vale 1 en cada llamada y cada método nuevo vale 6. Las combinaciones siguen existiendo en ejecución, pero ya no viven en un solo método, y cada pieza se prueba por separado. Si los bloques no comparten estado, eso es exactamente lo que se quiere.
Cuándo un valor alto es aceptable. Cuando las decisiones en secuencia son de verdad independientes (cada una toca un campo distinto y no influye en las demás), la mayoría de las combinaciones no esconden nada, y cubrir cada rama basta. NPath no distingue decisiones independientes de decisiones que interactúan.
Ojo. NPath no es una medida de lo difícil que es leer un método. Un método con 20 comprobaciones de
nullindependientes en fila vale más de un millón y se lee en un minuto.
Para profundizar
NPath no penaliza el anidamiento; lo premia. Se dice a menudo que NPath «tiene en cuenta el anidamiento» que la complejidad ciclomática ignora. Lo cierto es que lo distingue, pero en sentido contrario al que mide la «complejidad cognitiva»:
if (a) X; if (b) Y;(en secuencia) vale ;if (a) { if (b) Y; }(anidados) vale .
Las dos formas tienen . NPath da menos a la anidada porque tiene menos caminos: si a es falso, b ni se
evalúa. Lo que NPath castiga es la secuencia, no la profundidad.
No siempre cuenta caminos acíclicos. Bagnara, Bagnara, Benedetti y Hill (2016) demostraron que, pese a su definición, NPath no cuenta los caminos acíclicos ni siquiera en programas sencillos. Uno de sus ejemplos, escrito en C en el original y traducido aquí a Java:
static int f(boolean a, boolean b, boolean c, boolean d, boolean e) {
if (a && b && c) return d ? 0 : 1;
else return e ? 0 : 1;
}
Con las reglas de Nejmeh vale (2 por los dos operadores de la condición y 2 por cada return con
?:). Pero hay
tres formas de que la condición sea falsa (falla a; falla b; falla c) y una de que sea cierta, y cada una
continúa por dos ramas del ?:: caminos. El error está en sumar la condición y las ramas
del if en lugar de multiplicarlas. Los autores muestran también que NPath no cuenta los caminos que entran en el
cuerpo de un bucle y salen en la siguiente evaluación de la condición, que ignora la caída de un case al
siguiente y que trata break, continue y return como sentencias normales. Proponen una métrica alternativa,
ACPATH, que estima el número de caminos acíclicos y es exacta en las funciones sin goto hacia atrás ni saltos
que entren en un bucle desde fuera.
Puede dar cero. En la definición original una sentencia de expresión vale lo que su expresión, y por tanto 0 si
no tiene &&, || ni ?:; como la secuencia es un producto, un solo 0 anula el bloque que la contiene, y el
método entero si está en su cuerpo. Anderson (2021) lo cuenta entre los defectos de la definición original, que
según él reproducen Checkstyle, PMD y PDepend. El cero, al menos, lo evitan Checkstyle y PMD, que dan 1 a cualquier
sentencia que no sea de control.
Crece sin límite práctico. Un método de unas decenas de líneas puede valer millones. Para comparar o agregar valores, su logaritmo es más manejable que el número.
Relación con los tests. Ni NPath ni son «el número de tests necesario»: depende del criterio de cobertura. es el número de tests de la prueba estructurada de McCabe y una cota inferior del número de caminos; los caminos acíclicos, que NPath intenta contar, son lo que pediría recorrer todos los caminos sin repetir vueltas de bucle.
Relación con otras métricas
- «Complejidad ciclomática» (
v(G)): cuenta caminos independientes; NPath, caminos completos. es una cota inferior del número de caminos. Se leen juntas: si NPath es muy superior a , el método encadena muchas decisiones en secuencia. - «Complejidad cognitiva» (
CogC): mira la legibilidad y penaliza el anidamiento, justo lo que NPath no penaliza. - «Profundidad de anidamiento» (
NBD): a igualdad de decisiones, más anidamiento da menos caminos NPath. - «Número de sentencias de control» (
CONTROL): el recuento de los ingredientes; NPath dice cómo se combinan. - «Cobertura de código»: NPath intenta estimar los tests de una cobertura de caminos, aunque no es ni su número exacto ni una cota; acota los de la cobertura de ramas.
En las herramientas
Stau Metro no calcula NPath. Las métricas más cercanas son la
«complejidad ciclomática» (CyclomaticComplexity), que suma 1 por cada decisión en lugar
de multiplicar, y la «complejidad cognitiva» (CognitiveComplexity), que suma 1 por cada
ruptura del flujo y otro tanto por cada nivel de anidamiento. Ninguna de las dos crece de forma multiplicativa.
Checkstyle (NPathComplexity). Aplica reglas como las de la tabla de «Cómo se calcula»: el if, los bucles y
el switch suman sus partes; el ?: suma sus tres expresiones más 2; una expresión vale su número de && y ||;
cualquier otra sentencia, una llamada y un bloque vacío valen 1; un método o un bloque, el producto de sus
sentencias. Añade una regla para las guardas when de un case: el valor de la guarda más 1. El máximo por defecto
es 200.
PMD (regla NPathComplexity, del conjunto de diseño). Define NPath como el número de caminos de ejecución
acíclicos de un método y la calcula para cualquier operación no abstracta. Los bloques valen el producto de sus
sentencias y un bloque vacío vale 1; el ?: cuenta como un if … else equivalente; un try … catch suma el bloque
try y cada catch. El umbral de aviso por defecto (reportLevel) es 200.
Referencias
- Nejmeh, B. A. (1988). «NPATH: A Measure of Execution Path Complexity and Its Applications». Communications of the ACM, 31(2), 188-200. https://doi.org/10.1145/42372.42379
- Bagnara, R., Bagnara, A., Benedetti, A. y Hill, P. M. (2016). «The ACPATH Metric: Precise Estimation of the Number of Acyclic Paths in C-like Languages». arXiv:1610.07914. https://arxiv.org/abs/1610.07914
- Anderson, P. (2021). «Why NPATH is a Terrible Code Metric». GrammaTech. https://www.grammatech.com/learn/why-npath-is-a-terrible-code-metric/
- McCabe, T. J. (1976). «A Complexity Measure». IEEE Transactions on Software Engineering, SE-2(4), 308-320.
- Checkstyle, comprobación
NPathComplexity: https://checkstyle.org/checks/metrics/npathcomplexity.html - PMD, reglas de diseño para Java: https://docs.pmd-code.org/latest/pmd_rules_java_design.html
- PMD 6, índice de métricas de Java: https://docs.pmd-code.org/pmd-doc-6.55.0/pmd_java_metrics_index.html