머지(버전 제어)

Merge (version control)
병합을 빨간색 화살표로 표시한 버전 제어 프로젝트의 기록 그래프 예제

버전 제어에서 병합(통합이라고도 함)은 버전 제어 파일 모음에 대한 여러 변경 사항을 조정하는 기본 작업입니다.대부분의 경우 파일이 두 개의 독립된 분기에서 수정된 후 병합될 때 필요합니다.그 결과 두 가지 변경 사항이 모두 포함된 단일 파일 집합이 생성됩니다.

변경 내용을 재구성하기에 충분한 이력 정보가 있고 변경 내용이 경합하지 않기 때문에 마지를 자동으로 수행할 수 있는 경우도 있습니다.그 외의 경우는, 그 결과 파일에 포함되는 것을 정확하게 결정할 필요가 있습니다.많은 리비전 제어 소프트웨어 도구에는 병합 기능이 포함되어 있습니다.

병합 유형

병합에는 자동과 수동의 두 가지 유형이 있습니다.

비구조화 결합

구조화되지 않은 병합은 원시 텍스트에서 작동하며, 일반적으로 텍스트 행을 원자 단위로 사용합니다.이것은 Unix 툴(diff/patch)과 CVS 툴(SVN, Git)이 사용하는 것입니다.텍스트 행이 소스 코드의 구조를 나타내지 않기 때문에 이는 제한적입니다.

구조화된 결합

구조화된 병합 도구 또는 AST 병합은 소스 코드를 완전히 해결된 AST로 변환합니다.이것에 의해, 스플리어스 경합을 회피하는 세밀한 Marge가 가능하게 됩니다.그러나 AST가 포맷을 추상화함에 따라 AST에서 소스 코드로 예쁘게 인쇄하면 병합된 파일의 포맷 스타일이 완전히 달라질 수 있습니다.이 문제를 극복하기 위해서는 기본적으로 언어 특유의 [1]고화질 인쇄가 필요합니다.

워크플로우

자동 병합은 버전 제어 소프트웨어가 동시에 발생한 변경 사항을 논리적으로 조정할 때 수행하는 작업입니다.또, 다른 소프트웨어에서는, 같은 컨텐츠를 동시에 편집할 수 있는 경우는, 자동 머지를 전개합니다.예를 들어, 위키피디아에서는 두 사람이 동시에 동일한 문서를 편집할 수 있습니다. 후자의 기여자가 저장하면 이전 일련의 [2]변경 사항을 덮어쓰는 대신 변경 내용이 문서에 병합됩니다.수동 머지는 서로 다른 파일을 조정해야 할 때 사용자가 의지해야 하는 것입니다(아마도 머지 도구를 통해 도움을 받을 수 있습니다).예를 들어, 2개의 시스템에 약간 다른 버전의 컨피규레이션파일이 있고, 유저가 그 양쪽 모두에 적절한 것을 필요로 하는 경우는, 통상, 수동으로 컨피규레이션파일을 Marge 해 양쪽의 소스로부터 원하는 변경을 선택하는 것으로 실현할 수 있습니다(이것은 쌍방향 Marge라고도 불립니다).수동 머지는 변경 경합이 발생하는 경우에도 필요합니다.예를 들어, 두 변경 사항을 동일한 코드 행에 머지할 수 있는 자동 머지 도구는 거의 없습니다(예를 들어 함수 이름을 변경하는 도구와 주석을 추가하는 도구).이 경우 리비전 제어 시스템은 의도된 병합 결과를 지정하기 위해 사용됩니다.

병합 알고리즘

자동 병합에는 미묘한 차이가 있지만 다양한 접근 방식이 있습니다.보다 주목되는 머지 알고리즘에는 3방향 머지, 재귀 3방향 머지, 퍼지 패치애플리케이션, 위브 머지, 패치 변환 등이 있습니다.

삼원 마지

Diagram of a three way merge
C는 오리진, A와 B는 C의 파생 모델, D는 새로운 출력 버전입니다.

파일 "A"와 파일 "B"의 자동 차분 해석 후, 양쪽 파일 "C"의 원점, 즉 공통 상위 항목을 고려하여 3방향 마지를 실시한다.이는 대략적인 병합 방법이지만 병합할 변경 사항을 재구성하는 데 하나의 공통 조상만 필요하므로 널리 적용할 수 있습니다.3방향 병합은 원시 텍스트(줄의 순서) 또는 구조화된 [3]트리에서 수행할 수 있습니다.

3방향 병합은 3개의 파일 중 2개만 동일한 섹션을 찾습니다.이 경우 섹션에는 두 가지 버전이 있으며 공통 상위 "C"에 있는 버전은 폐기되고 다른 버전은 출력에 유지됩니다."A"와 "B"가 일치하면 출력에 표시됩니다."A"와 "C"가 같은 구간은 변경된 버전을 "B"로 출력하고, "B"와 "C"가 같은 구간은 "A"로 출력한다.

3개의 파일 모두 다른 섹션은 충돌 상황으로 표시되며 사용자가 해결할 수 있도록 남겨집니다.

3방향 마지는 유비쿼터스 diff3 프로그램에 의해 구현되며 파일 잠금 기반 리비전 제어 시스템에서 머지 기반 리비전 제어 시스템으로의 전환을 가능하게 하는 핵심 혁신이었습니다.CVS(Concurrent Versions System)에서 광범위하게 사용됩니다.

재귀 삼원 병합

3방향 머지 기반의 리비전 제어 툴이 널리 사용되고 있습니다만, 이 기술은 기본적으로 머지할 버전의 공통 조상을 찾는 것에 의존합니다.

수정된 버전의 고유한 마지막 공통 조상이 존재하지 않는 "크리스-크로스 병합"[4]과 같은 난처한 경우가 있습니다.

소프트웨어 버전 제어의 "크리스 크로스 머지" 문제.왼쪽 절반의 2개 영역은 XX) Y X X X X가 순차적으로 수정됩니다.솔루션은 오른쪽 절반에 표시되어 있습니다.가상 조상(파선된 원)이 생성됩니다.

다행히 이 경우 후보 조상은 최대 2개이며, 재귀 삼원 결합은 우선 비고유 조상을 결합함으로써 가상 조상을 구성합니다.이 머지 자체에서도 같은 문제가 발생할 수 있기 때문에 알고리즘은 이들을 재귀적으로 머지합니다.이력에는 한정된 수의 버전이 존재하기 때문에 프로세스는 최종적으로 종료됩니다.이 기술은 Git 리비전 제어 툴에서 사용합니다.

(Git의 재귀적인 머지 실장은 파일이 한 버전에서 수정되고 다른 버전에서 이름이 변경되는 등 다른 곤란한 케이스도 처리합니다만, 그것들은 3방향 머지 실장의 확장일 뿐, 3가지 버전의 머지 실장을 찾는 기술의 일부가 아닙니다.)

재귀 3원 병합은 도구가 병합할 파생상품의 총 조상 방향 비순환 그래프(DAG)에 대한 지식을 가지고 있는 경우에만 사용할 수 있습니다.따라서 파생상품이나 병합이 상위 항목을 완전히 지정하지 않는 상황에서는 사용할 수 없습니다.

퍼지 패치 적용

패치는 파일의 변경에 대한 설명이 들어 있는 파일입니다.Unix 세계에서는 텍스트 파일에 대한 변경을 "diff -u"에 의해 생성된 형식의 패치로 배포하는 전통이 있습니다.패치 프로그램은 이 형식을 사용하여 텍스트파일 또는 텍스트파일을 포함한 디렉토리 구조에 변경을 재적용(또는 삭제)할 수 있습니다.

그러나 패치 프로그램에는 패치 생성에 사용된 원본 파일과 완전히 유사하지 않은 파일에 패치를 적용하는 기능도 있습니다.이 프로세스를 퍼지 패치어플리케이션이라고 부릅니다.이 프로세스는 패치프로그램이 패치 적용처를 찾지 못할 경우 패치의 변경이 파기되는 일종의 비대칭 3방향 머지를 발생시킵니다.

CVS가 diff3의 스크립트 세트로 시작했듯이 GNU arch는 패치의 스크립트 세트로 시작되었습니다.단, 퍼지 패치어플리케이션은 비교적 신뢰할 수 없는 방법입니다.컨텍스트가 너무 적은 패치(특히 새 파일을 작성하는 패치)를 악용하거나 두 파생 버전에서 수행한 삭제 적용을 거부하는 경우가 있습니다.

패치 커뮤테이션

패치 변환은 Darcs에서 변경 내용을 병합하기 위해 사용되며 git에서도 구현됩니다(단, "리베이스"라고 불립니다.패치 커밋 머지는 패치가 선형 이력을 형성하도록 패치의 순서(변경 설명)를 변경하는 것을 의미합니다.실제로 공통 상황의 컨텍스트에서2개의 패치가 작성되면 Marge 시 한쪽 패치가 다른 쪽 패치의 컨텍스트에서 이루어진 것처럼 보이도록 고쳐 씁니다.

패치 변환을 수행하려면 파생 파일을 만든 정확한 변경 사항을 저장하거나 재구성할 수 있어야 합니다.이러한 정확한 변경으로부터 한쪽을 다른 한쪽에서 기본 재배치하기 위해 어떻게 변경해야 하는지를 계산할 수 있습니다.예를 들어 패치A가 파일F의 7행 뒤에 X행, 패치B가 파일F의 310행 뒤에 Y행 뒤에 X행 추가했을 경우, A에 추가된 행이 1개씩 오프셋되기 때문에 A에 근거하고 있는 경우, 그 행은 파일F의 311행 위에 추가되어야 합니다.

패치 변환은 공식적으로 많이 연구되어 왔지만 패치 변환의 병합 충돌을 처리하기 위한 알고리즘은 여전히 미해결 연구 질문으로 남아 있습니다.단, 패치 커뮤테이션은 다른 머지 스트래티지 대부분이 사용자가 원하는 것을 생성하는 휴리스틱스인 경우 "올바른" 머지[citation needed] 결과를 얻을 수 있음을 증명할 수 있습니다.

Unix 프로그램flipdiffdiff - u에 의해 생성된 기존 패치에 대한 패치 변환을 구현합니다.

위브 머지

위브 병합은 두 파일에 대해 공통 상위 항목을 사용하지 않는 알고리즘입니다.대신 파일의 파생 버전에서 단일 행이 추가 및 삭제되는 방법을 추적하고 이 정보에 대해 병합된 파일을 생성합니다.

파생 파일의 각 줄에 대해 위브 병합은 다음 정보를 수집합니다. 그 앞에 있는 줄, 뒤에 이어지는 줄 및 파생 파일 이력의 일부 단계에서 삭제되었는지 여부입니다.어떤 파생상품에서 해당 행이 삭제된 경우 병합된 버전에는 해당 행이 없어야 합니다.다른 행의 경우 병합된 버전에 해당 행이 있어야 합니다.

행은 각 행이 과거 어느 시점에서 그 앞에 있는 모든 행과 과거 어느 시점에서 그 뒤에 있는 모든 행 앞에 있는 순서로 정렬됩니다.이러한 제약조건이 모든 라인에 대해 완전한 순서를 부여하지 않는 경우, 서로 순서가 없는 라인은 경합하는 추가입니다.

위브 머지는 상용 리비전 제어 툴인 BitKeeper에 의해 사용된 것으로 보이며, 3자 머지에 의해 잘못된 결과나 나쁜 결과가 발생하는 문제의 일부에 대처할 수 있습니다.또한 GNU 바자 리비전 제어 툴의 결합 옵션 중 하나이며 [citation needed]Codeville에서 사용됩니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Larsen, Simon; Falleri, Jean-Remy; Baudry, Benoit; Monperrus, Martin (2022). "Spork: Structured Merge for Java with Formatting Preservation". IEEE Transactions on Software Engineering: 1–1. doi:10.1109/TSE.2022.3143766. ISSN 0098-5589.
  2. ^ 도움말: Edit conflict #Prevention
  3. ^ Lindholm, Tancred (2004). "A three-way merge for XML documents". Proceedings of the 2004 ACM symposium on Document engineering - DocEng '04. New York, New York, USA: ACM Press. doi:10.1145/1030397.1030399.
  4. ^ Cohen, Bram (2005-04-28). "The criss-cross merge case". Git (Mailing list). Message-ID <Pine.LNX.4.44.0504271254120.4678-100000@wax.eds.org>.