Um programa que compara dois textos não lê e julga "o que mudou" como uma pessoa faria. Em vez disso, ele procura a forma de transformar uma lista na outra com o menor número de remoções e inserções. Este guia explica como o diff calcula essa resposta e por que o resultado às vezes não é o que uma pessoa esperaria.
A unidade de comparação: linha, palavra, caractere
Primeiro o diff divide o texto em uma lista de tokens. O diff tradicional e o git tratam cada linha como um token. Por isso, se um único caractere muda dentro de uma linha, a linha inteira aparece como "1 linha removida + 1 linha adicionada".
A comparação por linha é rápida e se encaixa bem na revisão de código, mas em documentos em que um parágrafo longo ocupa uma só linha fica difícil achar o que mudou. Por isso muitas ferramentas comparam em duas etapas.
- Comparam por linha para encontrar as linhas alteradas.
- Pareiam as linhas alteradas e comparam de novo o conteúdo delas por palavra ou por caractere.
Este site usa o mesmo método. A unidade de comparação dentro da linha pode ser palavra, bloco (separado por espaços) ou caractere.
Maior subsequência comum (LCS)
O núcleo matemático do diff é a maior subsequência comum (Longest Common Subsequence, LCS). Uma subsequência é o que se obtém escolhendo alguns elementos sem mudar a ordem. Por exemplo, a maior subsequência comum entre ABCABBA e CBABAC tem comprimento 4; CABA e BABA são exemplos.
Os elementos que entram na LCS são "o que permaneceu"; o resto é "o que foi removido" (só existe à esquerda) ou "o que foi adicionado" (só existe à direita). Quanto mais longa a LCS, menos remoções e inserções. Se as duas listas têm comprimentos N e M e a LCS tem comprimento L, a soma D de remoções e inserções necessárias é:
D = (N - L) + (M - L)No exemplo acima, N=7, M=6 e L=4, então D = 3 + 2 = 5. Esse D se chama distância de edição (quando só inserções e remoções são permitidas), e a lista de remoções e inserções se chama script de edição.
O grafo de edição e o algoritmo de Myers
Calcular a LCS do jeito dos livros-texto (programação dinâmica) exige uma tabela de N×M células. Comparar 10 mil linhas com 10 mil linhas dá 100 milhões de células: lento e com muito uso de memória. Em 1986, Eugene W. Myers apresentou um método mais rápido no artigo "An O(ND) Difference Algorithm and Its Variations", que se tornou a base dos algoritmos padrão do GNU diff e do git atuais.
Myers transforma a comparação em encontrar o caminho mais curto em uma grade.
- Parte-se do canto superior esquerdo (0,0) até o inferior direito (N,M).
- Um passo para a direita = remover um elemento do texto da esquerda; um passo para baixo = adicionar um elemento do texto da direita. Cada um custa 1.
- Onde os dois elementos são iguais, é possível andar na diagonal de graça. Um trecho contínuo dessas diagonais se chama snake.
O caminho de menor custo é o script de edição mais curto. O algoritmo de Myers vai ampliando, em ordem, "o ponto mais distante alcançável com custo 0", "o ponto mais distante alcançável com custo 1"… e para quando chega ao fim. Em cada etapa basta lembrar a posição mais avançada em cada diagonal, então o tempo gasto é aproximadamente proporcional a (N+M)×D. Se os dois textos são quase iguais, D é pequeno e o cálculo é muito rápido; se são totalmente diferentes, fica lento.
Memória linear e middle snake
Para reconstruir o caminho é preciso guardar um registro a cada etapa, e a memória pode crescer na proporção de D². No mesmo artigo, Myers apresentou uma variante que faz a busca para a frente, a partir do início, e a busca para trás, a partir do fim, ao mesmo tempo, até encontrar o trecho diagonal em que as duas se cruzam (middle snake). Dividindo o problema em dois menores a partir desse ponto e repetindo, a memória usada fica proporcional apenas ao tamanho da entrada.
Quando fica caro demais: heurística aproximada
Se as duas entradas têm dezenas de milhares de linhas e são muito diferentes, D também cresce, e (N+M)×D pode chegar a bilhões. Para esses casos, o GNU diff tem uma heurística: quando a busca passa de certo limite, ele corta o problema na diagonal que avançou mais até então. O resultado continua sendo um script de edição correto, mas não há garantia de que seja o mais curto. As opções --minimal do GNU diff e do git fazem a ferramenta buscar o resultado mínimo, mesmo levando mais tempo.
Mínimo nem sempre é o mais legível
Pode haver vários caminhos com a mesma distância de edição. Por exemplo, ao adicionar uma função a um código, há chaves de fechamento } e linhas em branco em vários lugares, e o algoritmo pode acabar pareando "a } da função nova" com "a } de uma função existente". O resultado é mínimo, mas parece estranho para uma pessoa. É por isso que o git usa por padrão uma heurística que desloca as fronteiras olhando a indentação e oferece outros algoritmos, como patience e histogram. A comparação detalhada está em Comparação de algoritmos de diff.
Nesta ferramenta
O mecanismo de comparação deste site implementa em JavaScript a variante de memória linear do algoritmo de Myers e, quando a entrada é grande, passa para uma divisão aproximada no mesmo estilo do GNU diff. O cálculo roda em um Web Worker, então a tela não trava mesmo com arquivos grandes. Com o resultado por linha pronto, as linhas alteradas de conteúdo parecido são pareadas e marcadas como "modificadas", e o conteúdo delas é comparado mais uma vez na unidade escolhida (palavra, bloco ou caractere) para o destaque.
Coloque dois textos no comparador de textos e troque a unidade de comparação dentro da linha para ver como o resultado muda. Para ler o resultado no formato do git, veja Como ler um unified diff.