모든 diff는 최단 경로 문제다 — Myers 알고리즘과 LCS
여러분이 지금까지 본 거의 모든 diff — git diff, GNU diff, 아래의 출력 — 는 1986년의 논문 하나에서 내려옵니다. Eugene Myers의 "An O(ND) Difference Algorithm and Its Variations"입니다. 이 논문이 푸는 문제는 최단 편집 스크립트(shortest edit script) 찾기입니다. 텍스트 A를 텍스트 B로 바꾸는 데 필요한 최소한의 줄 삽입·삭제 횟수를 찾는 것이죠. 이것은 수학적으로 최장 공통 부분수열(LCS) 찾기와 같은 문제입니다 — 두 텍스트에 같은 순서로(꼭 인접하지는 않게) 등장하는 가장 긴 줄들의 나열입니다. LCS에 속한 줄은 변경 없는 컨텍스트가 되고, 나머지는 모두 빨간 마이너스나 초록 플러스가 됩니다.
Myers는 두 텍스트를 편집 그래프(edit graph)로 모델링합니다. 오른쪽 이동은 A에서 한 줄 삭제, 아래 이동은 B의 한 줄 삽입이고, 두 줄이 일치하는 곳에서는 공짜 대각선 이동이 가능합니다. 최단 편집 스크립트는 모서리에서 모서리까지의 가장 저렴한 경로이며, 알고리즘은 이를 편집 1회씩 탐욕적으로 탐색합니다. O(ND)라는 이름이 핵심 성질입니다. N은 전체 길이, D는 차이의 개수라서 두 텍스트가 비슷할수록 — 같은 문서의 개정판이라는 가장 흔한 경우 — 극도로 빠르고, 두 입력이 거의 아무것도 공유하지 않을 때만 느려집니다.
알아둘 미묘한 점 하나: 최단 스크립트는 대개 유일하지 않습니다. 서로 다른 여러 diff가 모두 최소 편집 횟수를 가질 수 있고, 그중 무엇을 보게 되는지는 구현 내부의 동점 처리 방식에 달려 있습니다. 두 diff 도구가 둘 다 "정확"하면서도 같은 입력 쌍에 대해 다른 출력을 내놓는 이유가 이것입니다.
old: A B C A B B A new: C B A B A C
LCS: C A B A (longest common subsequence, length 4)
shortest edit script (D = 5 edits):
-A -B C +B A B -B A +C
del del keep ins keep keep del keep ins → C B A B A CPatience diff — 최단 diff가 가장 읽기 좋은 diff는 아니다
최적과 가독성은 다릅니다. Myers는 편집 횟수를 최소화하지만, 코드에는 반복되는 줄이 가득합니다 — 닫는 중괄호, 빈 줄, "end", "return nil". 알고리즘 입장에서는 모두 동일한 줄이므로, 새 함수의 닫는 중괄호를 태연히 다른 함수의 닫는 중괄호와 매칭합니다. 전형적인 증상은 기존 함수 위에 새 함수를 추가했을 때 두 함수의 경계가 엉뚱한 곳에 그어진 diff가 나오는 것입니다. 기술적으로는 최소지만 사람이 보기엔 틀린 결과죠.
Bram Cohen의 patience diff는 노이즈에 앵커를 박기를 거부하는 방식으로 이를 공략합니다. 먼저 양쪽 파일에 정확히 한 번씩만 등장하는 줄 — 함수 시그니처, 특징적인 문장 — 만 고려하여, 그 유일 매칭들의 최장 증가 부분수열을 찾고(알고리즘 이름의 유래인 카드 게임 patience 정렬 사용), 이를 앵커로 고정한 뒤 앵커 쌍 사이를 재귀적으로 처리합니다. 중괄호와 빈 줄은 유일하지 않으므로 더 이상 가짜 앵커 역할을 할 수 없습니다. 결과는 Myers보다 편집이 몇 개 더 많을 수 있지만, 사람이 보는 의미 구조와 정렬됩니다.
같은 아이디어를 git이 다듬은 histogram diff는 앵커를 (엄격히 유일하지 않은) 저빈도 줄까지 확장하고 실전에서 더 빠릅니다. JGit의 기본이며 git config diff.algorithm의 인기 있는 선택지입니다. 이동되거나 중복된 코드의 diff가 뒤죽박죽으로 보인다면 git diff --patience나 --histogram을 시도해 보세요 — 같은 입력, 극적으로 다른 이야기가 나옵니다.
# Same change, two algorithms
git diff file.py git diff --patience file.py
def totals(): def totals():
return sum(rows) return sum(rows)
+
+def averages(): +def averages():
+ return sum(rows)/n + return sum(rows)/n
+ +
def render(): def render():
# Myers may anchor on the shared 'return sum(rows)' line and
# split the new function across the old one; patience anchors
# on the unique 'def' lines and keeps each function intact.라인, 단어, 문자 — 알맞은 비교 단위 고르기
라인 기반 diff가 기본인 이유는 코드가 줄 단위로 바뀌기 때문이기도 하고, 값이 싸기 때문이기도 합니다. 줄 전체를 해싱하면 비싼 알고리즘이 돌기 전에 각 파일이 짧은 토큰 시퀀스로 축소됩니다. 하지만 라인 단위에는 맹점이 있습니다 — 300자짜리 줄에서 한 글자만 바꿔도 diff는 그 줄 전체를 삭제+추가로 보고하고, 어디가 다른지는 눈으로 찾아야 합니다.
코드 리뷰 도구들이 쓰는 해법은 2패스 diff입니다. 라인 수준 패스로 어떤 줄이 바뀌었는지 찾고, 삭제/추가된 줄 쌍 각각에 대해서만 문자 또는 단어 수준 패스를 돌려 인라인 하이라이트를 만듭니다. 파일 전체에 문자 단위 diff를 직접 돌리는 것은 거의 가치가 없습니다 — 편집 그래프가 입력 길이에 대해 제곱으로 커지고, 무관한 줄들 사이의 한 글자짜리 정렬은 통찰이 아니라 노이즈를 만듭니다. git은 단어 수준 뷰를 git diff --word-diff(토큰 출력)와 --color-words(인라인 색상)로 제공하며, "한 줄"이 사실상 문단인 산문, 마크다운, 번역문에서 매우 유용합니다.
세 번째 축은 구조입니다. 두 JSON 문서는 의미상 동일해도 텍스트로는 다를 수 있습니다 — 키 순서, 들여쓰기, 후행 콤마. 그래서 원시 JSON의 텍스트 diff는 대부분 포매팅을 재는 셈입니다. 견고한 워크플로는 먼저 정규화하는 것입니다. 두 문서를 같은 포매터(안정된 키 순서, 고정 들여쓰기)에 통과시킨 뒤 diff하세요. SQL, XML, 서로 다른 도구로 포매팅된 코드에도 같은 요령이 적용되며, 코드에는 포매팅을 아예 무시하는 difftastic 같은 AST 수준 differ도 있습니다. diff의 의미는 그 전에 한 정규화만큼만 유효합니다.
공백, 줄바꿈 문자, 그리고 보이지 않는 차이들
가장 혼란스러운 diff는 양쪽이 똑같아 보이는 diff입니다. 가장 흔한 용의자는 줄바꿈 문자입니다. Windows 도구는 CRLF(\r\n)를, Unix는 LF를 쓰기 때문에 잘못된 OS에서 한 번 저장된 파일은 모든 줄이 변경된 것으로 표시됩니다. git의 방어책은 core.autocrlf, 그리고 더 좋은 방법으로는 명시적 eol 규칙을 담아 커밋한 .gitattributes입니다. 팀 전체가 같은 방식으로 정규화하게 되죠. 원시 diff 출력에서 캐리지 리턴은 줄 끝의 ^M으로 나타나곤 합니다.
두 번째 부류는 후행 공백과 탭 대 스페이스 들여쓰기입니다. 이를 억제하는 표준 플래그가 있습니다. diff -b는 공백 양의 변화를 무시하고, diff -w는 공백을 완전히 무시하며, git diff는 -w, -b, --ignore-blank-lines를 지원합니다. 이것들은 점검 도구이지 해결책이 아닙니다 — 공백 노이즈가 diff를 오염시킨다면 영원히 -w로 diff할 게 아니라 포매터와 .editorconfig로 소스를 고치세요. Python이나 YAML에서는 그 "노이즈"가 실제 의미 변화일 수 있으니까요.
세 번째 부류는 유니코드입니다. 웹 페이지에서 붙여넣은 줄바꿈 없는 공백(U+00A0), 폭 없는 공백(U+200B), 파일 첫머리의 바이트 순서 표식(U+FEFF)은 모두 일반 문자와 똑같이 렌더링되면서 불일치를 일으킵니다. 비슷하게, 악센트 붙은 문자는 코드 포인트 하나(NFC)일 수도, 기본 글자 + 결합 기호(NFD)일 수도 있습니다 — macOS 파일 API가 NFD를 만들어내는 것으로 유명합니다. diff가 차이를 볼 수 없는 줄을 지목하면 눈을 믿지 말고 두 줄을 hexdump 하세요. 답은 언제나 바이트 안에 있습니다.
# Both lines render as "hello" — the bytes disagree
$ printf 'hello \n' | xxd # trailing space: ...6f 20 0a
$ printf 'hello\r\n' | xxd # CRLF ending: ...6f 0d 0a
# Ignore whitespace while investigating
git diff -w # all whitespace
git diff -b --ignore-blank-lines # amount + blank lines
# Normalize line endings for the whole team (.gitattributes)
* text=auto
*.sh text eol=lfUnified diff 출력을 원어민처럼 읽기
unified 포맷 — GNU diffutils를 위해 발명되었고 git이 채택한 이후 보편화된 — 은 몇 개의 기호에 많은 정보를 담습니다. @@ -117,6 +117,8 @@ 같은 헝크(hunk) 헤더는 이렇게 읽습니다: 이 헝크는 원본의 117번째 줄부터 6줄, 새 버전의 117번째 줄부터 8줄을 다룬다. 이 개수에는 변경 없는 컨텍스트 줄(기본값은 위아래 각 3줄, -U로 조정 가능)이 포함됩니다. 교체된 줄은 마이너스 하나 + 플러스 하나이므로, 추가 수에서 삭제 수를 뺀 값은 항상 두 개수의 차와 같습니다 — 패치를 손으로 편집할 때 유용한 검산법입니다.
사람들이 자주 헷갈리는 표식이 둘 있습니다. 두 번째 @@ 뒤의 텍스트는 diff의 일부가 아니라, 위치 파악을 돕기 위해 제공되는 해당 부분을 감싸는 함수나 섹션 제목입니다. 그리고 "\ No newline at end of file" 줄은 실제 내용이 아니라 바로 앞 줄에 끝 줄바꿈이 없음을 표시하는 플래그입니다. 파일 끝에 줄바꿈 하나를 추가했을 뿐인데 두 줄짜리 diff가 나오는 이유가 이것입니다.
헝크를 이해하면 패치 적용의 미스터리도 풀립니다. patch와 git apply는 줄 번호를 맹목적으로 쓰지 않습니다. 명시된 위치 근처에서 컨텍스트 줄을 검색해서, 파일이 밀려 있으면 오프셋을 적용하고, 컨텍스트가 부분적으로만 일치하면 fuzz로 적용합니다 — 지난주 파일 기준으로 작성한 패치가 오늘도 적용되는 원리입니다. 컨텍스트가 머지에서 중요한 이유이기도 합니다. 3-way 머지 충돌(<<<<<<< / ======= / >>>>>>>)은 정확히 같은 컨텍스트 영역이 서로 다른 두 헝크를 받은 경우이며, git의 diff3 스타일(merge.conflictStyle = diff3)은 마커 사이에 공통 조상을 추가해 양쪽이 무엇에서 출발해 무엇을 바꿨는지 보여줍니다.
@@ -117,6 +117,8 @@ function render() {
const rows = fetchRows(); ← context (3 lines above)
const total = sum(rows);
- return format(total); ← removed from old file
+ const avg = total / rows.length;
+ return format(total, avg); ← added in new file
}
// counts: old 6 = 3+1+2 ctx, new 8 = 3+2+2 ctx +1
\ No newline at end of file