3-way merge 알고리즘에 대해

Git에서 두 브랜치를 머지할 때, 기본적으로 3-way merge 알고리즘을 사용하게 된다.

어떤 sequence A, B와 그 둘의 base인 sequence O가 있다고 하자. Git으로 치면 A, B는 머지할 브랜치, O는 base commit이 된다. sequence의 각 item은 소스코드의 한 줄이라고 생각하면 된다.

이렇게 A, O, B가 있을 때,

1. A, O, B에 대해 [Longest common subsequence](이하 LCS) (( 이름 그대로 가장 긴 공통 sequence이다. 알고리즘은 http://rosettacode.org/wiki/Longest_common_subsequence 의 예제코드들을 보면 쉽게 이해할 수 있을 것이다. )) 를 찾는다. A, O에 대해 LCS를 먼저 찾고, O, B에 대해서도 찾은 다음 이 LCS들을 통해 얻는다.
2. 위의 LCS를 이용해 모든 chunk에 대해 stable, unstable 여부를 검사한다. A, O, B가 모두 같다면 stable이고 아니면 unstable이다.
3. unstable chunk에서 A와 O가 같지만 B가 다르다면 B를 택하고, B와 O가 같지만 A가 다르다면 A를 택한다. 셋이 모두 다르다면 충돌로 처리한다.

A Formal Investigation of Diff3에 소개된 예를 통해 위의 알고리즘을 설명하겠다.

다음과 같은 세 sequence가 있다면,

A = [1, 4, 5, 2, 3, 6]
O = [1, 2, 3, 4, 5, 6]
B = [1, 2, 4, 5, 3, 6]

A, O의 LCS는 다음과 같고

A = [[1], [4, 5], [2, 3], [],     [6]]
O = [[1], []      [2, 3], [4, 5], [6]]

O, B의 LCS는 다음과 같다.

O = [[1, 2], [3], [4, 5], [],  [6]]
B = [[1, 2], [],  [4, 5], [3], [6]]

셋의 LCS를 찾으면 다음과 같다.

A = [[1], [4, 5], [2], [3],       [6]]
O = [[1], [],     [2], [3, 4, 5], [6]]
B = [[1], [],     [2], [4, 5, 3], [6]]

위에서 [1], [2], [6]은 셋이 모두 같으므로, stable chunk라고 하며 그 외에는 unstable chunk라고 한다. unstable chunk에 대해서 conflict가 발생헀는지 찾는다. A, O, B가 모두 다른 chunk가 있다면 conflict다.

A' = [[1], [4, 5], [2], [3],       [6]]
O' = [[1], [4, 5], [2], [3, 4, 5], [6]]
B' = [[1], [4, 5], [2], [4, 5, 3], [6]]

2번째 chunk는 A만 [4, 5]이고 O와 B는 같으므로([]) A에서만 변경이 있었음을 의미한다. merge하면 따라서 [4, 5]가 선택된다. 4번째 chunk인 [3], [3, 4, 5], [4, 5, 3]은 A’, O’, B’가 모두 다르므로 conflict다.

위 결과를 출력하면 다음과 같다.

1
4
5
2
<<<<<<< A
3
||||||| O
3
4
5
=======
4
5
3
>>>>>>> B
6

그러나 실제 patch, diff3, Git등으로 merge를 해 보면 이보다 더 쉽게 충돌한다. 주위 문맥을 고려하기 때문이다. 대개 전후 3줄 이내에 변경이 있으면 충돌로 간주한다.

3-way merge에 대해 더 자세히 알고 싶다면 A Formal Investigation of Diff3을 보라. Longest common subsequence를 포함해 3-way merge의 전 과정에 대해 자세히 설명하고 있다.