Qual é o número máximo de passos para encontrar um bug usando bissectura?

5

Suponha que um nó A na árvore de commit de um codebase contenha um bug, mas algum ancestral B de A esteja limpo daquele erro. Dada a topologia da árvore de commit [B, A] levando de B para A , podemos prever c o número máximo de etapas necessárias para localizar o commit onde o bug apareceu, em termos de número de vértices, setas, mesclagens ou ciclos e outras invariantes de gráficos simples?

Existem dois casos fáceis:

  1. Se o histórico de B para A for linear, então c é o logaritmo binário do número de nós entre < em> B e A .

  2. Se a história é totalmente paralela, ie uma família de commits independentes A → M → B , então c é o número de tais commits.

Dos dois exemplos, aprendemos que a história linear leva a processos de bissecção mais baratos, mas podemos ser mais precisos do que isso? É fácil escrever um programa para calcular c - o que eu ainda não fiz - mas estou procurando uma fórmula algébrica bem bonita. Se o problema for difícil, pode ser interessante e mais fácil ter o valor esperado de c dado, por exemplo, o número de vértices, setas e mesclagens, ou algo similar.

    
por Michael Le Barbier Grünewald 26.04.2015 / 18:26
fonte

1 resposta

3

Arquivos em vários sistemas de versionamento de código normalmente ganham bugs em um commit e permanecem com bug até serem corrigidos em outro commit. Isso ocorre porque há dois métodos populares para usar o controle de versão: bloqueios de arquivos e mesclagens. No caso de um bloqueio de arquivo, os desenvolvedores bloqueiam os arquivos em que estão trabalhando para que ninguém mais possa fazer alterações. Após o desbloqueio, os outros desenvolvedores devem fazer o checkout do mesmo arquivo, garantindo que essas alterações não sejam perdidas.

Em um sistema de versionamento de código de mesclagem, o ramo principal armazena todos os commits de todos os branches mesclados nele, criando um histórico linear. Isso geralmente funciona nos conceitos de diffs / patches, o que significa que um commit que introduz um bug de um branch não será automaticamente eliminado de um commit em outro branch que é mesclado posteriormente. Em alguns casos raros, ocorrem conflitos e, em seguida, é necessária uma resolução manual. Bugs geralmente sobrevivem a essas fusões também, então eles ainda aparecem continuamente através da linha do tempo da ramificação principal.

Não importa quantas ramificações ou desenvolvedores você tenha trabalhando em um projeto, você pode praticamente garantir que simplesmente identificando o último commit válido conhecido antes do bug, e o último commit conhecido para um bug (geralmente a posição atual do ref), você pode claramente isolar o commit que causou o bug, não importando em qual branch ele ocorreu. Esse é um efeito colateral da natureza linear dos logs e como eles se integram ao branch principal.

Você sempre pode identificar o tempo máximo de pesquisa para encontrar um bug contando o número de confirmações do último bem conhecido até o último commit inválido conhecido e localizando log2 (x). Muitas vezes, você pode pesquisar um histórico inteiro de um repositório em um bug em menos de 20 iterações (16.000 confirmações, por exemplo, são apenas 14 iterações). Se você conhece a versão em que um bug apareceu, geralmente é da ordem de 5 a 10 iterações (sua milhagem pode variar).

Eu só tenho experiência com SVN e Git, mas está claro que qualquer sistema que use algo melhor do que "compactar todos os arquivos no repositório em uma pasta oculta" (por exemplo, usando instantâneos do sistema de arquivos) deve ter aproximadamente o mesmo desempenho logarítmico para encontrar erros. Sempre haverá apenas um log linear que precisa ser lido, ignorando todas as ramificações, mesmo aquelas que foram descartadas ou re-formatadas posteriormente, porque a linha do tempo sempre parecerá linear.

Para um exemplo maluco, dê uma olhada nesta imagem:

Nestaimagem,elesmostramcomooGitfunciona.EenquantoGitestáfazendootrabalhoquefoidado,issonãoéumavisãobonita.Noentanto,vocêperceberácomocadacommitsealinhalinearmente,apesardafusãodeváriasramificaçõesdiferentesemmomentosdiferentes.Claro,existemferramentasparacorrigiressehistórico,demodoqueelesejalegívelnovamente(porexemplo, este artigo sobre como eles acabaram nessa bagunça).

O ponto é, o sistema de versionamento manterá as coisas corretas para você, então uma pesquisa binária simples em um histórico linear simples é realmente tudo o que é necessário.

    
por 21.05.2015 / 09:54
fonte

Tags