Estratégia de merge recursivo

Você deve ter ouvido falar da “estratégia de merge recursivo no git” que é o algoritmo padrão que o git usa quando faz o merge de duas branches. Como ele funciona e porque é bom?

Básico – elementos em um merge

Você tem duas branches em que quer executar o merge. Os “players” básicos a serem considerados são:

• A “fonte”: o changeset do qual você está executando o merge. O Changeset 16 do exemplo abaixo.
• O “destino”: o changeset para o qual você está executando o merge. É o número 15 no exemplo.
• O “antecessor”: o changeset (ou commit) que é o parente mais próximo da “fonte” e do “destino”, que é número 10 do exemplo.

Portanto, iremos executar o merge de 16 e 15 usando 10 como o antecessor. Nós PRECISAMOS de um antecessor para ser utilizado em merges de “três vias”. (mais sobre isso aqui).

Quando o “merge recursivo” é necessário?

Mas, às vezes, o cenário não é tão simples. E se encontrarmos “dois antecessores comuns”? A imagem abaixo mostra como, neste exemplo, temos a possibilidade de dois “antecessores comuns”.

Por favor, preste atenção: o exemplo é um pouco forçado, uma vez que não existe um bom motivo (inicialmente) para o desenvolvedor executar o merge do changeset 11 para o 16, ao invés de executar o merge do changeset 15 (o último da branch do “main” no ponto do merge). Mas vamos pressupor que ele tenha que fazer isso por algum motivo (sobre o changeset: o 11 era estável e, no momento, o 13 e o 15 não – por exemplo). A questão é: entre o 15 e o 16 não existe um único antecessor, mas dois antecessores a mesma “distância”: o 12 e o 11.

Mesmo que isso não aconteça diariamente, há probabilidades de acontecer com branches de vida longa, ou topologias complexas de branches (o caso retratado acima é o mais curto, que leva ao problema de “múltiplos ancestrais”, mas isso pode acontecer com vários changesets e branches entre os merges “cruzados”).

 Como o “merge recursivo” funciona?

Quando mais de um antecessor válido é encontrado, a estratégia de “merge recursivo” irá criar um novo “antecessor virtual” único, usando o merge apenas naqueles inicialmente encontrados. A imagem a seguir retrata o algoritmo:

 

Um novo“antecessor 2” será usado como “antecessor” para executar o merge do “src” e do “dst”.

A “estratégia de merge recursivo” é capaz de encontrar uma solução melhor do que apenas “selecionar um dos dois”, como descreverei abaixo.

 Porque o merge recursivo é melhor – um exemplo passo-a-passo

Deixe-me usar a seguinte “marcação” no próximo exemplo: um arquivo “foo.c” com três linhas assim:

b

c

d

E ele será descrito como: /foo.c = bcd.

Para tornar as coisas mais simples, usarei “linhas bobas” como “abc”, mas o exemplo é valido para ser usado com códigos reais.

Vamos dar uma olhada na situação mostrada no diagrama abaixo:

Tentarei descrevê-lo changeset por changeset:

•  0 -> tínhamos um arquivo foo.c com conteúdo foo=bcd (três linhas: primeira é “b”, segunda é “c” e terceira é “d”)
• 1 -> editamos foo.c em um branch e adicionamos uma nova linha para que ele ficasse foo=bcde
• 2 -> modificamos a segunda linha do arquivo em “main”. Agora o arquivo é foo=bCd
• 3 -> criamos uma nova branch a partir do changeset “2” e adicionamos uma nova linha no seu começo, então agora ele é foo.c=abCd
• 4 -> voltamos ao “task001” e modificamos a linha que acabamos de adicionar: foo.c=bcdE
• 5 -> nós “desfazemos” a mudança que acabamos de fazer em “main”: foo.c=bcd
• 6 -> nós executamos o merge “4” e “3” e criamos o “6” como foo.c=abCdE (combinamos as mudanças que fizemos na “task002” (adicionando uma nova linha no seu começo) com aquelas na “task001” – adicionando “E” no final – e também a mudança vinda de “2” em /main.
• 7 -> agora fazemos o merge “4” e “5” introduzindo a mudança do “4” (última linha adicionada) dentro do “main”: foo.c=bcdE. Se agora executarmos o merge “task002” no “main” (changeset “7” e “6”), o que vamos ter?

Nós deveríamos ter uma “adição” em “task002” (uma nova linha “a” no começo) em cima do “7”, certo?

O resultado esperado é: foo.c=abcdE.

Não deveríamos ter a linha “C” em letras maiúsculas, como está no “task002”, porque a consertamos depois em “main”.

Como você pode ver no diagrama, eu destaquei os changesets “4” e “2” porque eles são os dois antecessores possíveis de “6” e “7”.

Qual deve ser escolhido?

O Mercurial irá escolher o “4”, porque seu algoritmo escolhe o antecessor mais “profundo”, no caso de mais de um ser encontrado.

O que acontece se escolhermos o “4”?

Iremos fazer o merge do 4=bcdE, 6=abCdE e 7=abcdE, e o resultado automático (por qualquer ferramenta de merge em 3 vias) será:

Primeira linha -> a (está no 6 e 7)

Segunda linha -> b (está nos três contribuidores)

Terceira linha -> C (mudado no “6” mas “des-mudado” no “4” e “7”)

Quarta linha -> d (não foi alterado)

Quinta linha -> E (não foi alterado)

Então, nós automaticamente temos foo=abCdE, o que é ERRADO!!

Pegamos “C” ao invés de “c”, devido à seleção do antecessor errado.  

Como um merge recursivo conserta a bagunça?

Como descrito acima, a primeira coisa que o “merge recursivo” irá fazer é calcular um novo “antecessor virtual” executando o merge “4” e “2”, como mostrado na figura abaixo:

O resultado “changeset X” é foo=bCdE.

Depois, o “changeset X” é usado como o “antecessor” de “6” e “7” e então temos:

Antecessor: foo=bCdeE

Fonte: foo=abCdE

Destino: foo=bcdE

Resultado: foo=abcdE ->  que é o que estamos procurando!

O resultado calculado leva em consideração o “conserto” feito no changeset “5”, e assim o resultado está correto!

Por que é tão bom?

Se você tiver que lidar com a execução de branch e merge, e você não tem um bom algoritmo de merge, você pode acabar com arquivos quebrados sem saber. Resumindo: O Git fará isso corretamente, o Hg irá quebrar o resultado e o SVN e outros irão simplesmente acabar com a coisa toda.

No Plastic SCM 4.0 nós também implementamos o algoritmo “merge recursivo”, então conseguimos produzir o mesmo resultado (na verdade, nosso algoritmo é ainda mais poderoso, lidando corretamente com casos que nem o Git consegue resolver com sucesso).

Mais casos

Eu foquei em “conflitos de arquivos” hoje, mas também é fácil encontrar exemplos que afetam as estruturas de diretórios também.

Finalizando

O branch e o merge são duas armas que você deve ter na sua caixa de ferramentas como desenvolvedor, mas se certifique de que você tenha as melhores possíveis; que realmente fazem o trabalho.

 ***

Texto original disponível em http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html