Como o Git encontra as alterações? (O algoritmo Diff)

git diff é um comando que todo desenvolvedor usa diariamente.

Não é incrível como ele encontra instantaneamente exatamente quais linhas foram adicionadas ou excluídas entre milhares de linhas de código?

É simplesmente comparar dois arquivos linha por linha? Se assim for, inserir uma única linha no meio marcaria todas as linhas subsequentes como "alteradas".

O Git usa um método inteligente chamado Algoritmo Myers Diff para encontrar o "conjunto mínimo de alterações".

1. Distância de Edição

O problema de calcular a diferença entre duas strings (ou arquivos) se resume a encontrar o "número mínimo de edições necessárias para transformar A em B". Isso é chamado de Distância de Edição.

Por exemplo, para mudar ABC para ABD:

1. Excluir C
2. Adicionar D (Distância de Edição: 2)

O Git realiza esse cálculo não caractere por caractere, mas linha por linha.

2. Subsequência Comum Mais Longa (LCS)

O núcleo do algoritmo de Myers é encontrar a Subsequência Comum Mais Longa (LCS) entre dois arquivos.

Uma vez que a LCS é encontrada, o resto é fácil.

• Partes de A que não estão na LCS são Excluídas (-).
• Partes de B que não estão na LCS são **Adicionadas (+)`.

Por exemplo:

• Arquivo A: 1 2 3 4
• Arquivo B: 1 3 5 4

Aqui, a LCS é 1 3 4.
Portanto, podemos deduzir que 2 foi excluído e 5 foi adicionado.

3. A Magia do Algoritmo de Myers

Publicado por Eugene W. Myers em 1986, este algoritmo transforma o problema LCS em um problema de travessia de grafo (encontrar o caminho mais curto) para resolvê-lo de forma muito eficiente.

O Git usa esse algoritmo por padrão, mas também oferece outros algoritmos como histogram ou patience como opções.

Conclusão

Por trás dos sinais + e - que tomamos como garantidos, existe um algoritmo matemático elegante comprovado há mais de 30 anos.

Se você achar a saída do git diff confusa ou bagunçada, tente git diff --algorithm=histogram. Muitas vezes produz resultados que refletem melhor a estrutura do código.