Este é o Superfície Reflexiva. Ainda movido por uma contradição em termos

Este é o quarto artigo em uma série sobre conceitos de programação. Os demais artigos podem ser encontrados na página de resumo sobre a série. Como nos demais artigos, um aviso: o tratamento dado aos assuntos aqui é informativo e podem existir erros nos mesmos. Como nos demais artigos neste blog, comentários e correções são sempre bem-vindos.

Complexidade Ciclomática

Neste quarto artigo, vamos tratar um pouco de complexidade ciclomática. Apesar do nome esdrúxulo, complexidade ciclomática (também conhecida como complexidade condicional) é uma métrica simples para determinar, como o próprio nome sugere, a complexidade de um programa estruturado (cíclico).

Essa métrica foi desenvolvida em 1976 por Thomas J. McCabe e reflete diretamente o número de caminhos independentes que um programa pode tomar durante a sua execução.

Qualquer desenvolvedor que já tenha testado código em sua vida, sabe que a quantidade de testes necessária para exercitar um determinado trecho de código é diretamente proporcional à sua árvore decisória. Em outras palavras, quanto mais caminhos o código puder tomar (seja por meios de condicionais ou loops), maior a quantidade de testes necessários. E como veremos abaixo, há realmente uma relação direta entre a complexidade ciclomática e a cobertura de um código.

Calculando a complexidade ciclomática

Antes de mostrar exatamente como o cálculo pode ser feito, vamos observar algumas coisas em relação a um programa qualquer. Digamos que você esteja desenvolvendo um programa que lhe dê o maior divisor comum entre dois números. Uma fórmula simples é o algoritmo de Euclides que pode ser descrito da seguinte forma:

Dados dois números naturais a e b, verifique se b é zero. Se sim, a é o maior divisor comum entre os mesmos; caso contrário, repita o processo usando b e o resto da divisão de a por b.

Esse algoritmo pode ser expresso pelo seguinte programa em Ruby (note que ele não está em Ruby idiomático):

require "test/unit"

def euclid(m, n)
  if n > m
    r = m
    m = n
    n = r
  end
  r = m % n
  while r != 0
    m = n
    n = r
    r = m % n
  end
  n
end

class EuclidTest < Test::Unit::TestCase
  
  SETS = [[5, 10,  5], [2,  6,  2], [11,  7,  1], 
    [80, 64, 16], [2, 2, 2]]
  
  def test_euclid
    SETS.each do |set|
      assert_equal set[2], euclid(set[0], set[1])
    end
  end
  
end

Se o programa acima for executado, ele rodará o caso de teste logo abaixo da função que verificará se a mesma está correta. Você pode adicionar mais casos ao conjunto SETS se desejar.

A função euclid pode ser descrita por um grafo simples que conecta os caminhos entre as várias declarações que a mesma contém. Esse grafo é o mostrado abaixo (clique para expandir):

Com base nesse grafo, podemos definir a complexidade ciclomática de um programa da seguinte forma:

CC = A - N + 2C

Nessa fórmula:

• CC é a complexidade ciclomática
• A é o número de arestas do grafo
• N é o número de nós do grafo
• C é o número de componentes conectados

Como se trata de uma função simples com um único ponto de entrada e saída, o número de componentes é 1 e a fórmula pode ser reduzida para:

CC = A - N + 2

Se a função possuísse múltiplos pontos de saída, entretanto, a complexidade ciclomática seria definida como:

CC = A - N + C + R

Nessa fórmula, R é o número de declarações de saída (em Ruby, o número de returns).

Voltando ao grafo mostra na figura, vemos que o mesmo possui 11 nós e 12 arestas, o que nós dá uma complexidade ciclomática de 12 - 11 + 2, ou seja, 3.

Uma outra maneira bem simples de descobrir a complexidade ciclomática é contar o número de loops fechados no grafo (que são formados por condicionais e loops) e somar ao número de pontos de saída. No grafo acima, temos 2 loops fechados (os if e while) e um ponto de saída, resultando no mesmo valor 3 para a complexidade da função.

Uma coisa interessante é que a complexidade permanece a mesma quando a sintaxe de uma linguagem é levada em questão sem alterar a semântica do programa. Tome por exemplo a versão idiomática do algoritmo em Ruby:

def euclid(m, n)
  m, n = n, m if n > m
  m, n = n, m % n while m % n != 0
  n
end

O grafo gerado nesse caso é (clique para expandir):

Node que embora o número de nós e arestas tenha mudado, a relação entre eles não mudou e a complexidade permanece a mesma.

Testando

De uma forma geral, o valor da complexidade ciclomática define um limite superior para a quantidade de testes necessários para cobrir todos os caminhos decisórios no código em questão. Esse é um limite superior já que nem todos os caminhos são necessariamente realizáveis.

Disso se infere que quanto menor a complexidade, menor a quantidade de testes necessários para o método em questão. Esse fato implica em outro curioso: quebra um método em vários reduz a complexidade dos métodos mas aumenta a complexidade geral do código e, de forma geral, mantém a testabilidade do programa completo no mesmo nível.

Referências

Obviamente, já que a complexidade é um valor específico, é possível extrair da mesma uma referência. Baseado no trabalho de McCabe, esses valores de referência são:

• 1-10, métodos simples, sem muito risco
• 11-20, métodos medianamente complexos, com risco moderado
• 21-50, métodos complexos, com risco alto
• 51 ou mais, métodos instáveis de altíssimo risco

Conclusão

Essa foi uma pequena introdução ao assunto com o objetivo de abrir o caminho para artigos posteriores mostrando ferramentas de apoio ao cálculo e monitoramento da complexidade ciclomática. Como de usual, sugestões e correções são bem vindos.