As regressões são um grande problema na indústria do software. Mas é difícil colocar alguns números reais por trás desta afirmação.

Existem alguns números sobre os erros em geral, como um estudo do NIST em 2002 [1] que dizia:

E depois:

Eventualmente, a conclusão começou com:

Existem outras estimativas dizendo que 80% do custo relacionado ao software é relacionado com a manutenção[2].

Porém, de acordo com a Wikipedia [3]:

Porém podemos adivinhar que o aprimoramento do software existente é muito caro porque é preciso estar atento às regressões. Pelo menos isso tornaria os estudos acima consistentes entre si.

É claro que algum tipo de software é desenvolvido, usado durante algum tempo sem ser muito aprimorado e finalmente, jogado fora. Nesse caso, é claro, as regressões podem não ser um grande problema. Por outro lado, há muitos softwares grandes que são continuamente desenvolvidos e mantidos durante anos ou mesmo dezenas de anos por muitas pessoas. E como muitas vezes existem muitas pessoas que dependem (às vezes de maneira crítica) deste software, as regressões são realmente um grande problema.

Um destes softwares é o kernel do Linux. E se olharmos para o kernel Linux, podemos ver que muito tempo e esforço são gastos para combater as regressões. O ciclo de lançamento começa com uma janela de mesclagem de duas semanas. Em seguida, o candidato do primeiro lançamento (rc) é marcado. E depois disso, cerca de 7 ou 8 versões de candidatos aparecerão com cerca de uma semana de espaço entre cada uma delas, antes do lançamento final.

O tempo entre a primeira versão rc (release candidate = versão de lançamento) e a versão final deve ser utilizado para testar as versões rc, resolver os bugs e especialmente as regressões. Mais de 80% deste tempo gira em torno do ciclo de lançamento. Mas este ainda não é o fim da batalha, pois é óbvio que ele continua após o seu lançamento.

E é isso que o Ingo Molnar (um informado desenvolvedor de kernel do Linux) diz sobre o uso do git bisect:

Portanto, as regressões são combatidas o tempo todo pelos desenvolvedores e de fato, é sabido que os bugs devem ser corrigidos o mais rápido possível, tão logo sejam encontrados. É por isso que é importante ter boas ferramentas para este fim.

Então, quais são as ferramentas utilizadas para combater as regressões? Eles são quase os mesmos daqueles utilizados para combater os bugs tradicionais. As únicas ferramentas específicas são pacotes de testes e as ferramentas similares ao "git bisect".

Os conjuntos de teste são muito legais. Mas quando eles são utilizados sozinhos, eles devem ser usados para que todos os testes sejam verificados após cada commit. Isto significa que eles não são muito eficientes, porque muitos testes são realizados sem resultados interessantes e sofrem com explosões combinatórias.

De fato, o problema é que um software grande geralmente possui muitas opções de configuração diferentes e que cada caso de teste deve passar para cada configuração após cada commit. Portanto, caso tenha para cada release: N configurações, M commits e T casos de teste, execute:

onde N, M e T estão crescendo com o tamanho do seu software.

Logo, não será possível testar completamente tudo.

E caso alguns erros passarem pelo seu conjunto de testes, você poderá adicionar um teste ao seu conjunto de testes. Porém caso queira utilizar o seu novo conjunto aprimorado de testes para descobrir onde o erro ocorreu, será necessário emular um processo de bisseção ou talvez você teste cada commit sem rodeios de forma inversa a partir do commit "ruim" que você possa ter, sendo um total desperdício.

O primeiro subcomando "git bisect" que será usado é "git bisect start" para iniciar a pesquisa. Em seguida, os limites devem ser definidos para limitar o espaço dos commits. Isso geralmente é feito com um commit "ruim" e pelo menos um commit "bom". Eles podem ser passados na chamada inicial para o comando "git bisect start" assim:

ou eles podem ser definidos usando:

e:

onde BAD, GOOD e COMMIT são todos os nomes que podem ser resolvidos para um commit.

Então, o comando "git bisect" fará a averiguação de um commit de sua escolha e solicitará que o usuário o teste, assim:

Observe que o exemplo que usaremos é realmente um exemplo de brinquedo; procuraremos o primeiro commit que possui uma versão como "2.6.26-alguma-coisa", ou seja, o commit que possua uma linha "SUBLEVEL = 26" no nível mais alto do Makefile. Este é um exemplo de um brinquedo, porque existem maneiras melhores para encontrar este commit com o Git em vez de utilizar o "git bisect" (por exemplo, "git blame" ou "git log -S<texto>").

Neste ponto, existem basicamente duas maneiras de conduzir a pesquisa. Pode ser acionado manualmente através do usuário ou automaticamente através de um script ou comando.

Caso o usuário esteja conduzindo, em cada etapa da pesquisa, o usuário terá que testar a confirmação atual e dizer se é "bom" ou "ruim" utilizando os comandos git bisect good or git bisect bad respectivamente, como foram descritos acima. Por exemplo:

E após mais algumas etapas como essa, o comando "git bisect" acabará por encontrar um primeiro commit incorreto:

Neste ponto, podemos ver o que o commit faz, dar uma olhada (se ainda não tiver feito a averiguação) ou mexer com ele, por exemplo:

E quando terminarmos, podemos usar o comando "git bisect reset" para voltar ao ramo em que estávamos antes de começarmos a dividir:

A outra maneira de conduzir o processo de bisseção é dizer ao git bisect para lançar um script ou comando a cada etapa da bisseção para saber se o compromisso atual é "bom" ou "ruim". Para fazer isso, nós usamos o comando "git bisect run". Por exemplo:

Neste exemplo, passamos "grep ^SUBLEVEL = 25 Makefile" como parâmetro para o comando git bisect run. Isso significa que, a cada passo, o comando grep que encaminhamos será iniciado. E caso encerre com o código 0 (que significa sucesso), o comando git bisect marcará a condição atual como "bom". Caso encerre com o código 1 (ou qualquer código entre 1 e incluindo o 127, exceto o código especial 125), a condição atual será marcado como "ruim".

O código de saída entre 128 e 255 é especial para o comando "git bisect run". Eles fazem parar imediatamente o processo de bisseção. É útil por exemplo, caso o comando encaminhado demorar muito para ser concluído, por é possível encerrá-lo com um sinal que interromperá o processo de bisseção.

Também pode ser útil nos scripts encaminhados para o comando "git bisect run" para "exit 255" Caso alguma situação muito anormal seja detectada.

Às vezes, acontece que a condição atual não possa ser testada, por exemplo, caso ele não seja compilado porque houve um erro que o impedia naquele momento. É para isso que serve o código de encerramento especial 125. Diz ao comando "git bisect run" que o commit atual deve ser marcado como não testável e que outro deve ser selecionado e averiguado.

Caso o processo de bisseção tenha sido conduzido manualmente, será possível utilizar o comando "git bisect skip" para realizar a mesma coisa. (De fato, o código de saída especial 125 faz o comando "git bisect run" utilizar "git bisect skip" em segundo plano.)

Ou, caso queira mais controle, poderá inspecionar a condição atual usando, por exemplo, o comando "git bisect visualize". Ele iniciará o gitk (ou o comando "git log" caso a variável de ambiente DISPLAY não estiver configurada) para ajudá-lo a encontrar um melhor ponto de bisseção.

De qualquer forma, caso você tenha uma sequência de commits não testáveis, pode acontecer que a regressão que você está procurando tenha sido introduzido por um destes commits não testáveis. Nesse caso, não é possível saber com certeza qual o commit introduziu a regressão.

Portanto, tenha utilizado o comando "git bisect skip" (ou o script de execução encerrou com o código especial 125), poderá obter um resultado como este:

Caso queira exibir para outras pessoas o seu processo de bisseção, é possível obter um registro log utilizando, por exemplo:

E é possível reproduzi-lo utilizando:

Como o commit do Git forma um grafo acíclico direcionado (DAG), encontrar o melhor commit de bisseção para testar em cada etapa não é tão simples. De qualquer forma, Linus encontrou e implementou um algoritmo "de forama verdadeiramente estúpida", posteriormente aprimorado por Junio Hamano, que funciona muito bem.

Portanto, o algoritmo usado pelo comando "git bisect" para encontrar a melhor bisseção do commit quando não há commits que foram ignorados é o seguinte:

1) mantenha apenas os commits que:

a) são ancestrais do commit "ruim" (incluindo o próprio commit "ruim"), b) não são ancestrais de um commit "bom" (excluindo os commits "bons").

Significa que nos livramos dos commits que não interessam do DAG.

Como por exemplo, caso comecemos com um grafo como este:

onde B é o commit "ruim", o "G" são os commits "bons" e W, X e Y são outros commits, obteremos o seguinte grafo após esta primeira etapa:

Portanto, apenas os commits W e B serão mantidos. Como os commits X e Y serão removidos pelas regras a) e b) respectivamente, e porque os commits G são removidos pela regra b) também.

Nota para os usuários do Git, é equivalente a manter apenas o commit informado por:

Observe também que não exigimos que os commits mantidos sejam descendentes de um "bom" commit. Portanto, no exemplo a seguir, os commits W e Z serão mantidas:

2) a partir das extremidades "boas" do grafo, associe para cada commit a quantidade de ancestrais que possui mais um

Como por exemplo, com o grafo a seguir, onde H é o commit "ruim" e A e o D são alguns parentes de alguns commits "bons":

isto nos dá:

3) associado para cada commit: min(X, N - X)

onde X é o valor associado ao commit na etapa 2) e N é a quantidade total dos commits no grafo.

No exemplo acima, temos N=8, portanto, isso dará:

4) o melhor ponto de bisseção é o commit com o maior número associado a ele

Portanto, no exemplo acima, o melhor ponto de bisseção é o commit C.

5) observe que alguns atalhos são implementados para acelerar o algoritmo

Como conhecemos o "N" desde o início, sabemos que mínimo (X, N - X) não pode ser maior que N/2. Portanto, durante as etapas 2) e 3), se associarmos N/2 a um commit, sabemos que este é o melhor ponto de bisseção. Portanto neste caso, podemos simplesmente parar de processar qualquer outro commit e retorne para o commit atual.

Para qualquer grafo do commit, você pode ver o número associado a cada commit utilizando o comando "git rev-list --bisect-all".

Por exemplo, para o grafo acima, o comando seria:

geraria algo como:

Primeiro vamos definir "melhor ponto de bisseção". Digamos que um commt X é o melhor ponto de bisseção ou um melhor commit de bisseção caso conheça a sua condição ("bom" ou "ruim") fornece o máximo de informações possíveis caso a condição do commit seja "bom" ou "ruim".

Isto significa que as melhores bisseção dos commits são os commits onde a seguinte função seja máxima:

onde information_if_good(X) é a informação que obtemos caso X seja bom e information_if_bad(X) é a informação que obtemos caso X seja ruim.

Agora vamos supor que exista apenas um "primeiro commit ruim". Isto significa que todos os seus descendentes são "ruins" e todos os outros commits são "bons". E iremos supor que todos os commits têm uma probabilidade igual de serem bons ou ruins, ou de serem o primeiro commit incorreto, portanto, conhecer a condição do commit c dá sempre a mesma quantidade de informações onde quer que estes commits c estejam no grafo e independente do que o c seja. (Portanto, supomos que estes commits, seja por exemplo, em um ramo ou próximo a um commit bom ou ruim, não forneçam mais ou menos informações).

Vamos supor também que tenhamos um grafo limpo como um após o outro 1) no algoritmo de bisseção acima. Isso significa que podemos medir as informações que obtemos em termos quantidade dos commits que podemos remover do grafo.

E vamos receber um commit X no grafo.

Caso X seja considerado "bom", sabemos que os seus ancestrais são todos "bons", então queremos dizer que:

E isso é verdade porque na etapa 1) b) removemos os ancestrais dos "bons" commits.

Caso X seja considerado "ruim", sabemos que todos os seus descendentes são "ruins", então queremos dizer que:

Mas é errado, porque na etapa 1) a) mantemos apenas os ancestrais dos commits ruins. Então obtemos mais informações quando um commit é marcado como "ruim", porque também sabemos que os ancestrais do commit "ruim" anterior, não são ancestrais do novo commit "ruim" que não são o primeiro commit incorreto. Não sabemos se eles são bons ou ruins, porém sabemos que eles não são o primeiro commit incorreto porque não são ancestrais do novo commit "ruim".

Portanto, quando um commit é marcado como "ruim", sabemos que podemos remover todos os commit no grafo, exceto aqueles que são os ancestrais do novo commit "ruim". Isto significa que:

onde N é a quantidade de commits no grafo (limpos).

Portanto, no final, isso significa que, para encontrar as melhores bisseções dos commits, devemos maximizar a função:

E isso é bom porque na etapa 2) calculamos a number_of_ancestors(X) e, portanto, na etapa 3) calculamos f(X).

Vamos tomar o seguinte grafo como exemplo:

Caso calculemos a seguinte função não ideal nela:

nós temos:

porém com o algorítimo utilizado pelo git bisect nós temos:

Então escolhemos G, H, K ou L como o melhor ponto de bisseção, que é melhor que F. Porque, por exemplo, o L é ruim, saberemos não apenas que L, M e N são ruins, mas também que o G, H, I e J não são os primeiros commits ruins (pois supomos que haja apenas um primeiro commit ruim e ele deve ser um ancestral do L).

Portanto, o algoritmo atual parece ser o melhor possível, dado o que supomos inicialmente.

Quando alguns commits forem ignoradas (utilizando o comando "git bisect skip"), o algoritmo de bisseção é o mesmo da etapa 1) a 3). Então utilizamos aproximadamente as seguintes etapas:

6) classifique o commit diminuindo o valor associado

7) se o primeiro commit não foi ignorado, podemos retorná-lo e parar aqui

8) caso contrário, filtre todos os commits ignorados da lista

9) use um gerador de número pseudo-aleatório (PRNG) para gerar um número aleatório entre 0 e 1

10) multiplique este número aleatório com a a sua raiz quadrada para enviesá-lo para 0

11) multiplicada o resultado pela quantidade dos commits na lista dos filtrados e obtenha um índice nesta lista

12) retorne o commit ao índice que foi processado

Após a etapa 7) (no algoritmo skip), poderíamos verificar se o segundo commit foi ignorado e retorná-lo, se não for o caso. E de fato, este foi o algoritmo que utilizamos quando o comando "git bisect skip" foi desenvolvido no Git versão 1.5.4 (lançado em 1º de fevereiro de 2008) até o Git versão 1.6.4 (lançado em 29 de julho de 2009).

Porém o Ingo Molnar e o H. Peter Anvin (outro informado desenvolvedor de kernel do linux) reclamaram que às vezes os melhores pontos de bisseção aconteciam em uma área onde todos os commits eram testáveis. E neste caso, o usuário foi solicitado a testar muitos commits onde não são possíveis de serem testados, o que poderia ser muito ineficiente.

Na verdade, os commits não testáveis geralmente não são testáveis porque uma quebra foi introduzida em algum momento, e essa quebra foi corrigida somente depois que muitos outras commits foram introduzidos.

Naturalmente, essa quebra não está relacionada à quebra que estamos tentando localizar no grafo do commit. Porém isso nos impede de saber se o "mau comportamento" que interessa está presente ou não.

Portanto, é fato que os commits próximos de um commit onde o teste não possa ser feito têm uma alta probabilidade de serem elas mesmas as não testáveis. Os melhores commits para bisseção também são frequentemente encontrados juntos (devido ao algoritmo de bisseção).

É por isso que é uma péssima ideia escolher a próxima melhor bisseção do commit que não foi ignorado quando o primeiro tenha sido ignorado.

Descobrimos que a maioria dos commits no grafo pode fornecer muitas informações quando são testadas. E os commits que, em média, não fornecerão muita informação são os próximos commits bons e ruins.

Portanto, ao usar um PRNG com um viés para favorecer os commits longe dos commits bons e ruins parecia ser uma boa escolha.