Algoritmos de diff de texto: como Git, patches e ferramentas de diff funcionam

Toda ferramenta de revisão de código, toda saída de git diff, todo arquivo de patch que você já leu remonta a um pequeno número de algoritmos inventados entre 1976 e 2009. Saber qual o seu tool usa — e que suposição ele faz — é a diferença entre ler um diff em 30 segundos e ficar olhando para um confuso por dez minutos, imaginando se a refatoração realmente preservou o comportamento.

O que um diff realmente é

Um diff é um script de edição: uma sequência mínima de inserções e exclusões que transforma o arquivo A no arquivo B. Para dois arquivos de comprimento total N com D diferenças, existem muitos scripts possíveis. Um algoritmo de diff escolhe um de acordo com algum critério de otimização — geralmente o menor D, mas nem sempre.

Dois corolários seguem. Primeiro, a mesma mudança de arquivo pode legitimamente produzir diffs com aparências diferentes de ferramentas diferentes; todos estão corretos no sentido de que aplicá-los reconstrói o arquivo B. Segundo, “diff legível” é uma restrição mais fraca do que “diff menor”, e os dois frequentemente discordam. Você pode comparar dois arquivos com nossa ferramenta de diff de texto e ver a saída unificada lado a lado.

Diff Myers — o padrão em toda parte

O artigo de 1986 de Eugene Myers An O(ND) Difference Algorithm and Its Variations definiu o algoritmo que GNU diff, Git, Mercurial, SVN e a maioria dos editores ainda usam por padrão. Ele enquadra o problema de diff como encontrar o caminho mais curto por um grafo de edição: cada passo diagonal é uma linha correspondente, cada passo horizontal exclui uma linha de A, cada passo vertical insere uma linha de B.

A fraqueza do Myers é que ele minimiza o tamanho do diff sem nenhum senso de estrutura. Após mover um bloco de código, Myers frequentemente emparelha a chave de fechamento de uma função com a de outra diferente porque isso produz menos linhas alteradas no total.

Diff Patience — projetado para legibilidade

Bram Cohen (o autor do BitTorrent) introduziu o Patience diff em 2007 especificamente para corrigir o problema de legibilidade de refatoração do Myers. O algoritmo:

1. Encontra todas as linhas que aparecem exatamente uma vez em ambos os arquivos. Essas são linhas-âncora únicas.
2. Calcula a subsequência comum mais longa das âncoras únicas.
3. Faz o diff recursivamente em cada região entre âncoras consecutivas, recorrendo ao Myers quando não há âncoras únicas restantes.

O resultado alinha o diff em torno das linhas que um humano reconheceria como “a mesma coisa” — assinaturas de função, comentários únicos, declarações de classe. Ative no Git com git diff --patience ou globalmente com git config diff.algorithm patience.

Diff Histogram — Patience, refinado

O Histogram diff foi introduzido pelo JGit (a implementação Java do Git) e depois portado para o Git principal. Ele melhora o Patience sendo mais inteligente sobre quais linhas-âncora escolher: em vez de exigir unicidade, ele escolhe as linhas raras com a menor contagem de ocorrências em ambos os arquivos. Ative globalmente com git config --global diff.algorithm histogram.

Lendo um hunk de diff unificado

O diff unificado (-u) é o formato de troca de facto. Um hunk se parece com:

@@ -42,7 +42,9 @@ class UserController {
   const user = await User.findById(id);
   if (!user) {
-    return res.status(404).end();
+    logger.warn({ id }, "user not found");
+    return res.status(404).json({ error: "not found" });
   }
   return res.json(user);
 }

A linha @@ é o cabeçalho do hunk. Ela diz: o arquivo antigo começa na linha 42 e abrange 7 linhas; o novo arquivo começa na linha 42 e abrange 9 linhas. Linhas sem prefixo são contexto inalterado. Linhas começando com - existem apenas no arquivo antigo; linhas começando com + existem apenas no novo.

Espaços em branco e terminações de linha

• Espaço em branco à direita. Configure core.whitespace e git diff --ignore-space-at-eol.
• Indentação mista. Use git diff -wpara ignorar todas as diferenças de espaço em branco.
• Terminações de linha. CRLF vs LF. Configure .gitattributes com * text=auto para normalizar no commit.
• Nova linha final. Arquivos sem nova linha final mostram \ No newline at end of file no diff.

Merge de três vias e por que ocorrem conflitos

Quando você faz merge do branch B no branch A, o Git examina três versões: o ancestral comum C, a versão A e a versão B. O merge procede linha por linha:

• Linha inalterada de C para A, mas modificada em B → pega B.
• Linha modificada em A, mas inalterada em B → pega A.
• Linha modificada de forma idêntica em ambos → pega qualquer uma; sem conflito.
• Linha modificada de forma diferente em A e B → conflito.

Conflitos são sinalizados no arquivo de trabalho com <<<<<<<, ======= e >>>>>>> mostrando ambas as versões.

Escolhendo um algoritmo na prática

Para o trabalho diário, Histogram é o melhor padrão e o que a maioria das equipes deve configurar globalmente. Patience produz resultados muito similares e permanece útil para arquivos muito grandes. Myers é a escolha certa para pipelines máquina-a-máquina que consomem diffs programaticamente.

A conclusão honesta

Mude seu algoritmo global do Git para Histogram e nunca pense nisso novamente para a maioria dos repositórios. Quando um diff confundir você após uma refatoração, renderize novamente com um algoritmo diferente antes de assumir que a mudança está errada. Normalize espaços em branco e terminações de linha no nível do repositório para que os revisores gastem seu tempo com lógica, não com formatação.