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의 전 과정에 대해 자세히 설명하고 있다.

광고

git의 revision에 대해

git에서 revision이란 특정 Git object를 가리킬 수 있는 표현식을 의미한다. HEAD~2, master, a8dd808db6d87a1d809b1a223e08ab69602b2d3a, HEAD:test.txt 등이 모두 “revision”이다.

문법

ABNF 로 표현해보면 대략 다음과 같다.

DIGIT = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
sha1 = 1*40HEXDIGIT
refname = name / "refs" "/" (name /
          ("tags" "/" name) /
          ("heads" "/" name) /
          ("remotes" "/" name) /
          ("remotes" "/" name "/" HEAD))
specifier = "@" "{" (date / num) "}"
rev = sha1 / refname [specifier] / specifier /
      rev ("^" / "~" / "^" DIGIT / "~" DIGIT)
revision = rev /  ":" "/" regexp / ":" ("0" / "1" / "2" / "3") ":" path

그닥 잘 알려져 있지는 않지만 간혹 유용한 몇가지 표현을 소개해 보겠다.

@{…}

@을 이용해, 특정 refname(브랜치 등)이 과거에 가리켰던 커밋을 지칭할 수 있다. 쉽게 말해서 git reflog에 나열되는 특정 커밋을 지칭할 수 있다.

  • <refname>@{n} – refname이 과거에 가리켰던 커밋. git reflog 해보면 무슨 의미인지 알 수 있을 것이다. master@{5} 와 같은 표현이 가능하다.
  • <refname>@{date} – 특정 날짜, 시각에서 refname이 가리켰던 커밋. master@{yesterday} 식의 표현이 가능하다.

:n:path

:n:path 표현식으로, 주어진 path에 대해 특정 상태에서의 tree 혹은 blob을 지칭할 수 있다.

  • :0:path – staging area

머지중인 상태에서는 공통 조상이나 특정 브랜치의 path에 대응하는 tree나 blob을 지칭할 수 있다.

  • :1:path – 공통 조상(common ancestor)
  • :2:path – 현재 브랜치
  • :3:path – 현재 브랜치에 머지되어지는 중인 브랜치

더 자세히

man gitrevisions로 더 자세한 설명을 볼 수 있다.

git에서 특정 파일만 남기기 (git 기반 위키에서 특정 파일만 공개하기)

코드저장소에서 실수로 절대 넣어서는 안되는 파일을 넣어 버렸을 때, git의 filter-branch 명령을 사용하면 간단하게 특정 파일만 제외시키고 전체 히스토리를 재구축하는 것이 가능하다.

그러나 반대로 특정 파일만 남기는 것은 조금 까다롭다. filter-branch를 응용해서 남기고자 하는 파일 외에는 모두 삭제하면서 히스토리 전체를 재구축하는 방법이 있긴 한데, 속도도 느리고 잘 동작하게 만들기도 쉽지가 않다.

사실 일반적인 소프트웨어 개발 프로젝트라면, 프로젝트에서 특정 파일만 남기겠다는 요구사항은 그렇게 흔하지 않을 것이다. 하지만 git은 소프트웨어 개발 프로젝트에서만 쓰이는 것이 아니다. 개발자노트골룸과 같은 위키시스템은 git 저장소에 위키페이지를 저장한다. 그리고 위키 사용자들은 개인위키로 관리하던 페이지에서 몇몇 페이지만 선별하여 공개적으로 publish하고 싶어한다.

git은 rcs나 cvs와는 달리 파일별로 버전관리를 하지 않기 때문에 이런 요구에 부응해주기가 참 어렵다. 하지만 불가능하지는 않다.

이런 경우 보통은 fiter-branch를 써서 불필요한 파일들을 제거하는 해법을 선택하겠지만, 여기서는 그보다 더 빠르고 보다 잘 동작하는 방법을 알아볼 것이다.

branch 만들기 및 checkout

filter-branch와 다른 방법인 것 처럼 이야기했지만, 사실 기본적인 접근은 같다. 히스토리를 바닥부터 쌓아가는 것이다. 우선 완전히 아무 커밋도 없는 브랜치 “public”를 만든다. –orphan 옵션을 사용하면 가능하다.

git checkout --orphan "public"

준비

그리고 이제부터 커밋을 하나하나 쌓아갈 것이니, 불필요하게 staging area에 파일이 남아있다면 모두 제거해버리자.

git rm --cached -r .

commit

그럼 이제부터가 진짜다. 이제 공개하고자 하는 파일에 대한 히스토리를 죽 뽑아서, 그에 대한 커밋만 커밋할 것이다.

다음과 같은 방법으로 특정 파일들에 대한 커밋의 목록을 얻는다.

filenames=file1 file2 file3
commits=`git log --reverse --format='%H' master -- $filenames`

--foramt='%H'를 주면 커밋로그 출력 옵션이 커밋 아이디만 출력하는 형태가 될 것이다. --reverse 옵션을 주는 이유는, 커밋 로그를 가장 오래된 것이 먼저 오게 출력하기 위함이다. 그 순서대로 커밋을 할 것이기 때문이다.

위에서 얻은 커밋들을 하나하나 커밋한다. 그 커밋들에서도 오직 공개하기를 원하는 파일만 뽑아내어 커밋한다.

for commit in $commits
do
git checkout -qf $commit -- $filenames
git add --ignore-errors $filenames
git commit -C $commit
done

push

마지막으로 이렇게 구축한 브랜치 “public” 를 원격저장소에 push하면, 내가 선정한 파일들만 push될 것이다. 아마도 이 push는 히스토리 전체를 뒤바꿀 것이므로, -f 옵션을 줘야만 할 것이다.

아래는 개발자노트에 공개하고자 하는 페이지들만 담긴 브랜치 “public”을 push하는 예이다.

git push -f http://npcode.com:3000/devnote/notes/note.git public:master

마무리

“publish” 브랜치는 더 이상 필요치 않으니 제거한다. 다음번에 또 publish를 하기 위함이다.

git branch -D "publish"

전체 소스코드

전체 소스코드는 아래와 같다. argument로 공개할 파일들을 지정해주면 알아서 브랜칭하고, 히스토리를 재구축하고, “public”이란 이름의 저장소로 push한 뒤, 그 branch를 삭제하기까지 해주는 쉘 스크립트이다.

filenames=$*
from=master
commits=`git log --reverse --format='%H' $from -- $filenames`
branch="pub-`date +'%y%m%d-%H%M%S'`"
git checkout --orphan "$branch"
git rm --cached -r .
for commit in $commits
do
git checkout -qf $commit -- $filenames
git add --ignore-errors $filenames
git commit -C $commit > /dev/null
done
git push -f public "$branch":master
git branch -D $branch

사용은 다음과 같이 하면 된다. 아래와 같이 실행하면 “git”, “linux”, “mac” 페이지만 공개하게 된다.

./pub.sh git linux mac

Git의 blob은 어떻게 발음하는가.

Git 메일링 리스트에 문의해 본 결과, 일반명사 blob과 같이 블랍으로 발음하는 것이 맞다고 한다.

사실 이걸 어떻게 발음하는 것이 맞는가에 대해서는 어디에도 명시되어 있지 않다. gitglossary에도 없다.

일반적으로 database에서는 blob이 binary large object라는 의미로 쓰이고, 비랍(bee-lab)으로 발음하지만 Git에서는 그런 의미가 아닌지도 모르겠다.

단 두 명이 답을 주었을 뿐이긴 하지만, 이 메일링 리스트는 Git 개발자와 사용자가 모두 활발히 참여하는 메일링 리스트이고, 이견을 말하는 사람이 없는 것으로 보아 맞다고 봐도 무방할 것이다.

디스크 공간 절약을 위해 파일을 Git 저장소에 보관하기

SSD를 쓰기 시작하면서 디스크 공간이 굉장히 소중해졌다. 그래서 잘 안 쓰는 파일들은 zip으로 압축해서 저장하곤 하지만 뭔가 파일 하나가 보고 싶을 때는 꺼내기가 좀 불편하다.

대안은 Git bare 저장소로 보관하는 것이다. 이 방법은 공간도 적게 사용하면서 필요할 때 gut 명령으로 간단히 파일을 꺼내 볼 수도 있다.

뿐만 아니라 Git 저장소는 굉장히 공간효율적이다. 때때로 gzip으로 압축했을 때 보다도 디스크 공간을 적게 사용하는 경우도 있어 나를 놀라게 한다.

Git 저장소로 파일을 보관하고 읽고 쓰는 법에 대해 간단히 알아보자.

Git 저장소에 넣기

평소에 문서파일을 저장하던 text라는 디렉토리를 Git 저장소로 바꾸고 싶어졌다면 다음과 같이 하면 된다.

cd text
git init
git add *
git commit -m 'put them all'
mv .git ../text.git
cd ..
rm -rf text
cd text.git
git config core.bare true

Git 저장소의 파일 다루기

위에서 git 명령으로 간단히 파일을 꺼내 볼 수 있다고 말하긴 했지만, 사실 bare 저장소에 들어있는 파일을 직접 다루는 것은 흔치 않은 일이다. 그래서 익숙해지기 어렵다. 그러므로 Git bare 저장소에서 동작하는 cp나 cat과 같은 coreutils를 간단히 만들어서 쓰는 것이 편하다.

git-cat

우선 git-cat을 만들어보자. 아주 간단하다.

#!/bin/sh
git show HEAD:$1

이 파일을 실행 가능하게 설정하고, path가 잡혀있는 디렉토리에 넣어두면 그 다음부터는 git cat <filename>으로 git 저장소에 들어있는 파일 내용을 볼 수 있게 된다. 예를 들면 다음과 같다.

$ cd text.git
~/text.git$ git cat hello.txt
Hello, World

git-ls

git-cat은 GNU coreutils의 cat과는 달리 디렉토리의 내용도 볼 수 있다. 하지만 좀 더 ls에 가깝게 출력하는 기능이 필요하다면 다음과 같은 스크립트를 만들면 된다.

#!/bin/sh
git ls-tree --name-only HEAD

알려진 이슈: 한글 파일명을 제대로 보여주지 못한다는 문제가 있다. “\355\225\234\352\270\200” 와 같이 코드로 보여준다.

git-cp

마지막으로 저장소 밖의 파일을 저장소 안으로 넣을 수 있는 git-cp다. 이건 파이썬으로 작성했다. 전체 소스코드는 여기에 있는데, 상당히 긴 관계로 가장 중요한 세 군데만 설명하겠다.

우선 git hash-object로 blob을 만든다. (do()는 쉘명령 실행하는 함수) blob은 파일 하나에 해당한다.

blob_id = do(git_cmd + ['hash-object', '-t', 'blob', '-w', '--', src],
        None, options).strip()

그리고 git mktreee로 위에서 만든 blob이 담긴 tree를 만든다. tree는 디렉토리에 해당한다.

tree_id = do(git_cmd + ['mktree', '-z'], None, options, ''.join(files)).strip()

마지막으로 git commit-tree로 커밋을 하면 된다.

commit_id = do(git_cmd + ['commit-tree', tree_id] + parent_param +
        ['-m', message], None, options).strip()

사용법은 다음과 같다.

$ git cp hello.txt text.git

알려진 이슈: 커밋을 한번도 안한 빈 코드저장소에 파일을 복사하려 시도하면 오동작한다.

전체 소스코드

git-coreutils에 전체 코드를 올려 놓았다.

git bisect 응용 – 줄바꿈 문자 잘못 넣은 사람 찾기

나는 언제나 줄바꿈 문자를 ‘\n’로 통일한다. 내가 참여하는 모든 프로젝트에서도 그러하다.

그러나 윈도 사용자들은 기본적으로 ‘\r\n’을 사용하도록 되어있으므로, IDE나 편집기에서 혹은 Git에서 설정을 변경해주지 않는 이상 줄바꿈 문자가 ‘\r\n’이 된다. 이로 인해 다양한 OS를 사용하는 개발자들이 함께 같은 프로젝트에서 개발을 하다보면 내가 작성한 코드에 누군가 ‘\r\n’을 집어넣어 심란해지는 일이 종종 있다. 누가 집어넣었는지 찾아내고 싶지만 (( 물론 누군지 찾아내서 그의 편집기나 Git 설정을 올바르게 바로잡아주려는 것이다. )) 이미 들어간지 며칠 지나서 커밋이 수십개나 쌓였다면 찾아내기가 쉽지는 않다.

작년에 이런 문제를 실제로 자주 겪었었고, 지난번 포스팅에서 소개했던 git bisect를 이용해 해결했었다.

우선 아래와 같이 간단히 \r\n을 검출하는 파이썬 스크립트 eol.py 를 만들었다.

#/bin/env python
import sys

if sys.stdin.readlines()[0][-2:] == 'rn':
    exit(1)

그리고 위의 스크립트를 이용해 원하는 파일에 대해 줄바꿈 문자를 검사하는 쉘스크립트 test.sh를 만들었다. (( 이걸 굳이 두 개의 스크립트로 쪼갠 것은, 난 기본적으로 파이썬이 익숙해서 왠만하면 파이썬으로 만들긴 하지만, 이 사례에서는 혹시 대상 파일이 옮겨졌더라도 잘 동작하게 하기 위해 쉘의 **이 필요했기 때문이다. ))

#!/bin/sh
cat **/RepositoryController.java | python eol.py
exit $?

그럼 이제 test.sh 를 실행하면 내가 검사하고자 하는 RepositoryController.java 파일에 eol 문자가 ‘\r\n’인 경우에는 1, 아니면 0이 반환될 것이다.

이제 아래와 같이 실행하면 ‘\r\n’이 처음으로 잘못 들어간 커밋이 무엇인지 알려준다. 엔 문제가 없었던(‘\r\n’이 없었던) 커밋을 적어주면 된다.

git bisect bad
git bisect good <good-commit>
git bisect run sh test.sh

ps. git log -G 로 간단히 잘못된 줄바꿈 문자를 찾아내는 것도 가능하지 않을까 싶은데 방법을 잘 모르겠다.

git으로 버그의 원인 찾기

간만에 공용 저장소에서 커밋들을 pull 해왔을 때, 내 저장소의 코드가 제대로 동작하지 않기 시작하면 정말 난감하기 짝이 없다. 이 때 디버깅이 간단하지 않다면, 천천히 버그의 원인을 찾아보게 된다. 버그의 원인은, 현재 발생하고 있는 버그가 최초로 발생한 커밋에 있을 것이므로 그 커밋을 찾아낼 수 있다면 쉽게 원인도 파악할 수 있을 것이다.

bisect로 찾기

bisect –run

git bisect start
git bisect bad <bad-commit>
git bisect good <good-commit>
git bisect --run <shell command>

버그의 원인으로 의심되는 커밋을 자동으로 찾아주는 아주 편리한 기능이다. git bisect badgit bisect good으로 버그가 발견된 시점과 버그가 없었던 시점을 알려주고, git bisect --run으로 버그 존재 여부를 확인할 수 있는 쉘 명령을 주면, 최초로 버그가 발생한 시점을 binary search로 찾아낸다.

두 가지 조건을 만족해야 이 기능을 사용할 수 있다.

버그가 발생하지 않았던 시점을 알아야 한다.

........ffff..fffH
        ^  ^  ^
        F1 F2 F3

위와 같은 상태의 저장소가 있다고 가정하자. 첫번째 줄에 나열된 문자들은 히스토리를 상징한다. 문자 하나가 커밋 하나다. .은 버그가 없는 커밋이고 f는 버그가 있는 커밋이며 H는 현재 시점(HEAD)다.

H 시점에서 버그가 발견되었다면, 그 원인은 F3에 있을 것이다. F3이 어디인지 알아내기 위해서는 F2와 F3 사이의 아무 커밋이나 하나를 찍어서 git bisect good으로 해당 시점에는 버그가 없었음을 알려주어야 한다. 그렇게 하면 git bisect는 그 커밋 이후부터의 커밋에서 버그가 발생한 지점을 탐색할 것이고 정확하게 F3을 찾아낼 것이다.

그러나 만약 F1 이전 시점을 good으로 선택했다면 git이 알려주는 최초 버그발생 시점은 F1일 수도 있고 F3일 수도 있다. 앞에서 언급했듯이 binary search를 사용하기 때문이다. 위의 사례처럼 테스트 실패가 방치되는 경향이 있는 프로젝트라면 이런 어려움을 겪을 가능성이 높다.

쉘 명령으로 버그를 탐지하는 것이 가능해야 한다.

이 조건은, 커맨드라인에서 유닛테스트 실행할 수 있도록 되어있다면 간단히 만족된다. git bisect --run은 주어진 쉘 커맨드가 0을 반환하면 버그없음, 0이 아닌값을 반환하면 버그가 있는 것으로 간주한다. 커맨드라인에서 실행가능한 유닛테스트라면 틀림없이 그렇게 동작하도록 구현되어 있을 것이므로 그냥 사용하면 된다.

수동 bisect

git bisect start
git bisect bad <bad-commit>
git bisect good <good-commit>
# ...
git bisect good
# ...
git bisect bad

쉘 명령으로 정상/오류 상태를 판단할 수 없다면 사람이 수동으로 판단할 수 밖에 없다. 이 방법은 위의 git bisect --run 대신 수동으로 하나하나 해 보는 방법이다.

git bisect badgit bisect good으로 버그가 발견된 지점과 버그가 없었던 지점을 각각 선택해주면 그 다음부터 정상동작하는지 테스트가 필요한 지점으로 git이 알아서 checkout 해준다. 수동으로 테스트를 해 보고 버그가 있으면 bad, 없으면 good이라고 알려주면 된다. 몇 차례 반복하면 git이 최초 버그가 발생한 지점이 어디인지 알려줄 것이다.

이 방법 역시 앞에서 이야기한 조건 중 ‘버그가 발생하지 않았던 시점을 알아야 한다’는 만족해야 사용할 수 있다.

log로 검색해서 찾기

모든 버그의 원인을 bisect로 다 밝혀낼 수는 없다. 자동화된 테스트로 탐지되지도 않고 언제부터 버그였는지 짐작도 되지 않는 그런 오류의 근본 원인을 찾아야 하는 상황이라면 더 단순한 도구와 당신의 머리를 활용해서 탐사를 해야 한다.

log –grep

git log --grep <pattern>

커밋로그를 검색한다. 커밋로그를 잘 남겼다면 버그를 일으키는 모듈이나 기능을 언제 추가했는지 이것으로 찾아낼 수 있을 것이다.

log -S 혹은 log -G

git log -S <string>
git log -G <pattern>

모든 커밋의 변경내역을 검색한다. 버그의 원인으로 짐작되는 함수, 변수, 상수를 발견했다면 이 기능을 이용해 최초 추가된 시점을 찾을 수 있을 것이다. -S 대신 -G를 쓰면 정규식으로 검색한다.