세 갈래 병합

세 갈래 병합은 따로 고친 두 파일을 하나로 합쳐 줍니다. 두 파일만 비교하지 않고 둘이 갈라지기 전의 원래 파일까지 셋을 함께 봅니다. 원래 파일을 잣대로 삼아 누가 무엇을 바꿨는지 가려냅니다. 한쪽만 바꾼 곳은 알아서 합칩니다. 양쪽이 같은 곳을 서로 다르게 바꾼 곳만 사람에게 넘깁니다.

상세

이 절은 세 갈래 병합이 무엇을 받아 무엇을 내놓는지부터 봅니다.

받는 것과 내놓는 것

버전관리 도구는 파일들의 한 시점 상태를 커밋으로 저장소에 기록합니다. 커밋은 저마다 바로 앞 커밋을 가리킵니다. 이 앞 커밋을 그 커밋의 부모라고 부릅니다. 부모를 따라 거슬러 올라가면 파일이 바뀌어 온 차례가 나옵니다.

브랜치는 한 저장소 안에서 커밋을 따로 쌓아 가는 흐름입니다. 브랜치는 자기 흐름의 맨 끝 커밋을 가리킵니다. 새 커밋을 쌓으면 브랜치가 가리키는 커밋도 그 새 커밋으로 옮겨 갑니다.

두 사람이 각자 브랜치에서 같은 파일을 고치면 그 파일은 두 판으로 갈라집니다. 갈라진 두 판을 하나로 모으는 일을 병합이라고 합니다. 세 갈래 병합은 이 병합을 해내는 절차입니다.

이름대로 재료가 셋입니다. 아래 표의 영어 이름은 병합 도구의 옵션과 화면에 자주 나옵니다.

기준은 두 브랜치가 마지막으로 같았던 판입니다. 이 판을 공통 조상이라고 부릅니다. 갈라진 뒤 양쪽이 무엇을 했든 둘 다 이 판에서 출발했습니다. 이 판을 잣대로 삼으면 양쪽이 각각 무엇을 바꿨는지 잴 수 있습니다.

아래 그림은 세 재료가 이력의 어디에 있는지를 보입니다. 화살표는 시간이 흐르는 방향입니다. 기준에서 갈라진 두 브랜치가 합친 판에서 다시 만납니다.

flowchart TD
    B["기준 · 공통 조상"] -->|"내가 쌓은 커밋"| O["이쪽 · 내 브랜치의 끝"]
    B -->|"동료가 쌓은 커밋"| T["저쪽 · 동료 브랜치의 끝"]
    O --> M["합친 판"]
    T --> M

내놓는 것은 둘 중 하나입니다. 모든 곳이 자동으로 정해지면 합친 판 하나가 나옵니다. 정하지 못한 곳이 남으면 거기에 표시를 박은 파일을 내놓고 멈춥니다. 이렇게 정하지 못한 곳을 충돌이라고 부릅니다.

두 판만 견줄 때의 빈칸

셋째 재료가 왜 필요한지는 한 줄짜리 예로 드러납니다. 설정 파일에 타임아웃 값을 적은 줄이 하나 있습니다. 나는 이 값을 올렸습니다. 동료는 이 줄을 건드리지 않았습니다.

timeout = 30    # 기준
timeout = 60    # 이쪽 · 내가 올림
timeout = 30    # 저쪽 · 손대지 않음

이쪽과 저쪽 두 판만 놓고 보면 알 수 있는 것은 「이 줄이 다르다」뿐입니다. 내가 30 을 60 으로 올렸을 수도 있습니다. 동료가 60 을 30 으로 내렸을 수도 있습니다. 두 판만으로는 어느 쪽인지 가를 근거가 없습니다.

기준을 같이 보면 답이 나옵니다. 기준이 30 이니 바꾼 쪽은 이쪽입니다. 저쪽은 손대지 않았으니 이쪽의 60 을 받으면 됩니다. 기준 하나가 「다르다」를 「누가 바꿨다」로 바꿔 줍니다.

두 판만 비교하는 방식을 두 갈래 병합이라고 부릅니다. 두 갈래 병합에서는 다른 줄마다 사람이 골라야 합니다. 세 갈래 병합이 사람에게 넘기는 것은 양쪽이 모두 바꾼 곳뿐입니다.

구간마다 내리는 판정

판정은 기준을 사이에 두고 양쪽을 한 번씩 비교하는 데서 시작합니다. 두 파일에서 같은 줄과 달라진 줄을 가려내는 비교를 diff라고 합니다. 세 갈래 병합은 diff 를 두 번 돌립니다. 기준과 이쪽 사이에 한 번, 기준과 저쪽 사이에 한 번입니다.

flowchart TD
    B["기준"] --> D1["기준과 이쪽을 비교한다"]
    O["이쪽"] --> D1
    B --> D2["기준과 저쪽을 비교한다"]
    T["저쪽"] --> D2
    D1 --> M["두 변경 목록을 기준의 줄 위에 겹친다"]
    D2 --> M
    M --> R["합친 판 또는 충돌"]

두 번의 diff 가 끝나면 변경 목록이 둘 생깁니다. 목록의 항목 하나는 「기준의 몇째 줄부터 몇째 줄까지를 무엇으로 바꿨다」입니다. 두 목록 모두 기준의 줄 번호로 적혀 있습니다. 덕분에 같은 눈금 위에 겹쳐 볼 수 있습니다.

목록의 항목 하나는 한 줄이 아니라 붙어 있는 변경 줄의 덩어리입니다. 이 덩어리를 헝크(hunk)라고 부릅니다. 판정도 한 줄씩이 아니라 이 덩어리 단위로 내립니다.

겹쳐 본 뒤에는 기준을 구간으로 나눠 하나씩 판정합니다. 헝크가 덮은 줄 묶음이 한 구간입니다. 헝크 사이에 남은 안 바뀐 줄 묶음도 한 구간입니다. 경우는 다섯입니다.

다섯 줄은 한 문장으로 줄어듭니다. 한쪽만 바꾼 구간은 바꾼 쪽을 따릅니다. 양쪽이 같은 구간을 다르게 바꿨을 때만 멈춥니다.

양쪽 헝크가 조금만 겹쳐도 판정은 넓게 걸립니다. 이쪽 헝크와 저쪽 헝크가 기준에서 한 줄이라도 겹치면 두 헝크를 합친 범위 전체가 충돌 구간이 됩니다. 구현에 따라서는 겹치지 않고 바로 맞닿기만 해도 충돌로 봅니다.

아래 그림은 기준 다섯 줄 위에 헝크 셋이 놓인 경우입니다. 이쪽 헝크 하나가 1~2줄을, 저쪽 헝크 둘이 2~3줄과 5줄을 덮습니다.

flowchart TD
    subgraph BASE["기준의 줄"]
        L1["1줄 · 이쪽 헝크"]
        L2["2줄 · 이쪽 헝크와 저쪽 헝크"]
        L3["3줄 · 저쪽 헝크"]
        L4["4줄 · 안 바뀜"]
        L5["5줄 · 저쪽 헝크"]
        L1 ~~~ L2 ~~~ L3 ~~~ L4 ~~~ L5
    end
    L2 --> C["1~3줄 전체가 충돌"]
    L5 --> A["5줄은 저쪽 것을 쓴다"]

두 헝크가 겹친 것은 2줄 하나입니다. 그래도 충돌 구간은 두 헝크를 합친 1~3줄 전체입니다. 5줄의 저쪽 헝크는 이쪽 헝크와 떨어져 있어 자동으로 들어갑니다.

한쪽 브랜치가 갈라진 뒤 아무것도 안 했을 수도 있습니다. 그러면 기준과 그 브랜치의 판이 같아서 모든 구간이 다른 브랜치의 것으로 정해집니다. 이때는 병합을 돌리지 않고 브랜치가 가리키는 커밋만 앞으로 옮기는 도구가 많습니다. 이것을 패스트 포워드라고 합니다.

드는 비용

비용은 대부분 두 번의 diff 에서 나옵니다. 변경 목록을 겹쳐 보는 단계는 두 목록을 앞에서부터 한 번 훑으면 끝납니다. 세 갈래 병합의 속도는 결국 어떤 diff 알고리즘을 쓰느냐에 달려 있습니다.

diff 는 두 파일에서 순서를 지키며 겹치는 줄을 가장 길게 찾는 문제로 풉니다. 이 문제를 최장 공통 부분 수열 문제라고 합니다. 두 파일에 함께 남은 줄이 안 바뀐 줄입니다. 나머지가 바뀐 줄입니다.

두 파일이 거의 같으면 빨리 끝납니다. 많이 다를수록 오래 걸립니다.

멈췄을 때 파일의 모양

충돌이 나도 세 갈래 병합은 파일을 비워 두지 않습니다. 충돌 구간에 양쪽 내용을 모두 넣고 경계마다 표시 줄을 박습니다. 이 표시 줄을 충돌 표시라고 부릅니다. 앞의 예에서 동료도 값을 90 으로 바꿨다면 파일은 이렇게 됩니다.

<<<<<<< 이쪽
timeout = 60
||||||| 기준
timeout = 30
=======
timeout = 90
>>>>>>> 저쪽

표시 줄 넷이 파일을 세 칸으로 나눕니다. 예시의 위에서부터 차례로 읽습니다.

• <<<<<<< 줄과 ||||||| 줄 사이가 이쪽 내용입니다. 예시에서는 60 입니다
• ||||||| 줄과 ======= 줄 사이가 기준 내용입니다. 예시에서는 30 입니다
• ======= 줄과 >>>>>>> 줄 사이가 저쪽 내용입니다. 예시에서는 90 입니다

기준 칸은 도구에 따라 빠지기도 합니다. 그러면 ||||||| 줄이 없어지고 이쪽 칸이 ======= 줄까지 이어집니다. 위 예에서는 표시 뒤에 이쪽·기준·저쪽이라고 적었습니다. 도구는 그 대목에 브랜치 이름 같은 꼬리표를 붙입니다.

기준 칸이 있으면 사람도 기계와 같은 판단을 할 수 있습니다. 위 예에서 기준이 30 이니 양쪽 다 값을 올린 것이 보입니다. 한쪽은 60, 한쪽은 90 입니다. 어느 값을 남길지는 두 사람이 왜 바꿨는지를 알아야 정해집니다.

사람이 표시 줄을 지우고 남길 내용을 고쳐 쓰면 충돌 해소가 끝납니다. 그 뒤에야 병합 결과를 커밋으로 남길 수 있습니다.

병합 결과를 담은 커밋을 병합 커밋이라고 합니다. 보통 커밋은 부모가 하나입니다. 병합 커밋은 합친 두 브랜치의 끝 커밋을 모두 부모로 가리킵니다. 앞의 그림에서 합친 판으로 모이는 화살표 두 개가 이 부모 둘입니다.

셋을 봐도 못 잡는 것

세 갈래 병합은 글자만 비교합니다. 코드가 무슨 뜻인지는 모릅니다. 그 탓에 충돌 없이 합쳐진 코드가 깨지는 일이 생깁니다.

내가 함수 load 의 이름을 fetch 로 바꿨습니다. 같은 시간에 동료는 같은 파일 아래쪽에 load 를 부르는 줄을 새로 넣었습니다. 두 변경은 서로 다른 곳이라 겹치지 않습니다. 병합은 멈추지 않고 끝납니다. 결과에는 두 변경이 다 들어갑니다.

def fetch():        # 이쪽이 이름을 바꿈
    ...

load()              # 저쪽이 새로 넣은 호출

합친 파일에는 이제 없는 load 를 부르는 줄이 남았습니다. 이 코드는 실행하면 그 줄에서 이름을 못 찾고 멈춥니다. 글자로는 안 부딪혔습니다. 뜻으로 부딪힌 것입니다.

이런 충돌을 글자 충돌과 갈라 의미 충돌이라고 부릅니다. 병합 도구는 의미 충돌을 못 봅니다. 병합이 끝난 뒤에도 빌드와 테스트를 다시 돌리는 까닭이 이것입니다.

공통 조상이 둘일 때

기준은 공통 조상 하나라고 했습니다. 그런데 이력 모양에 따라 공통 조상이 하나로 안 정해지기도 합니다. 두 브랜치가 비슷한 때에 서로를 합친 경우입니다.

시작 판에서 브랜치 가와 나가 갈라집니다. 가에는 커밋 가1 이, 나에는 커밋 나1 이 쌓입니다. 커밋 이름은 브랜치 이름에 쌓인 차례를 붙여 적습니다. 그다음 가는 나를 합쳐 병합 커밋 가2 를 만듭니다. 같은 때 나도 가를 합쳐 병합 커밋 나2 를 만듭니다.

flowchart TD
    S["시작 판"] --> GA1["가1 · 가의 커밋"]
    S --> NA1["나1 · 나의 커밋"]
    GA1 --> GA2["가2 · 가의 병합 커밋"]
    NA1 --> GA2
    NA1 --> NA2["나2 · 나의 병합 커밋"]
    GA1 --> NA2
    GA1 -.-> V["가상의 기준"]
    NA1 -.-> V

이제 가2 와 나2 를 합치려 하면 가1 과 나1 이 둘 다 공통 조상입니다. 둘 다 양쪽 이력에 들어 있습니다. 어느 쪽도 다른 쪽의 조상이 아닙니다. 마지막으로 같았던 판이 하나로 안 정해지는 것입니다.

서로 합친 흔적이 엇갈린 이런 이력 모양을 십자 병합이라고 부릅니다. 그림에서 가1·나1 과 가2·나2 사이의 화살표가 엇갈리는 모양이 이 이름의 유래입니다.

한 가지 방법은 조상 둘을 먼저 세 갈래 병합으로 합치는 것입니다. 이 병합에서는 두 조상의 공통 조상인 시작 판이 기준이 됩니다. 그렇게 나온 판을 가상의 기준으로 삼아 가2 와 나2 의 병합을 돌립니다. 그림의 점선이 이 가상의 기준입니다.

리베이스와 체리픽 안의 세 갈래 병합

세 갈래 병합은 브랜치를 합칠 때만 도는 것이 아닙니다. 커밋 하나를 다른 브랜치 위에 옮겨 적용할 때도 돕니다. 이때는 재료를 잡는 방법이 조금 다릅니다.

체리픽은 다른 브랜치의 커밋 하나를 골라 지금 브랜치 위에 다시 적용합니다. 체리픽에서 세 재료는 이렇게 잡힙니다.

아래 그림은 이 세 재료가 이력의 어디에 있는지를 보입니다. 기준과 저쪽이 모두 다른 브랜치 안에 나란히 붙어 있습니다.

flowchart TD
    subgraph OTHER["다른 브랜치"]
        P0["앞선 커밋"] --> P["기준 · 고른 커밋의 부모"]
        P --> C["저쪽 · 고른 커밋"]
    end
    subgraph CUR["지금 브랜치"]
        X["이쪽 · 지금 브랜치의 끝"] --> N["새 커밋"]
    end
    C -.->|"기준과 저쪽의 차이만"| N

기준과 저쪽의 차이는 고른 커밋이 한 변경 그 자체입니다. 세 갈래 병합을 돌리면 그 변경만 이쪽 위에 얹힙니다. 앞선 커밋의 변경은 기준과 저쪽에 똑같이 들어 있습니다. 저쪽이 안 바꾼 것으로 읽히니 따라오지 않습니다.

리베이스는 한 브랜치의 커밋 여럿을 다른 브랜치 끝으로 차례로 옮겨 붙입니다. 커밋 하나를 옮길 때마다 체리픽과 같은 세 갈래 병합이 한 번씩 돕니다. 옮겨 붙여 새로 생긴 커밋이 다음 병합의 이쪽이 됩니다.

브랜치 다의 커밋 다1·다2 둘을 옮기는 경우를 그리면 이렇습니다. 옮겨 붙여 새로 생긴 커밋은 다1′·다2′ 로 적습니다.

flowchart TD
    subgraph S1["첫째 병합"]
        B1["기준 · 다1 의 부모"]
        O1["이쪽 · 옮겨 갈 브랜치의 끝"]
        T1["저쪽 · 다1"]
    end
    S1 --> N1["다1′"]
    subgraph S2["둘째 병합"]
        B2["기준 · 다1"]
        T2["저쪽 · 다2"]
    end
    N1 -->|"이쪽"| S2
    S2 --> N2["다2′"]

첫째 병합이 만든 다1′ 이 둘째 병합의 이쪽으로 들어갑니다. 병합이 커밋마다 따로 돌기 때문에 리베이스 중에는 커밋마다 충돌이 따로 날 수 있습니다.

관련 항목

세 갈래 병합이 받는 재료

공통 조상 · 브랜치 · 커밋 · 스냅샷

세 갈래 병합을 이루는 비교 절차

diff · 헝크 · 최장 공통 부분 수열 · diff3

세 갈래 병합이 내놓는 결과와 막히는 경우

병합 커밋 · 충돌 · 충돌 표시 · 충돌 해소 · 의미 충돌 · 십자 병합

세 갈래 병합을 안에서 쓰는 작업

병합 · 리베이스 · 체리픽 · 되돌리기 · 풀

갈라진 편집을 다르게 합치는 방식

두 갈래 병합 · 패스트 포워드 · 스쿼시 · 옥토퍼스 · 운영 변환 · CRDT

세 갈래 병합을 쓰는 버전 관리 도구

버전관리 · Git · 머큐리얼 · 서브버전