'git log --graph'또는 'hg graphlog'는 어떻게 작동합니까?

Question

Git의 히스토리가 DAG라는 데이터 구조에 저장되어 있다는 것을 알고 있습니다. 나는 DFS에 대해 듣고 다소 관련이 있다는 것을 알고있다.

git log --graph 또는 hg graphlog과 같은 프로그램이 어떻게 기록을 끌어 냈는지 궁금합니다. 나는 언제나 차선과 모든 것을 그리는 것이 꽤 복잡하다고 생각했다.

누군가가 그것을 보여주는 의사 코드를 작성할 수 있습니까?

참고 : Git 또는 hg 코드를 살펴 보았지만 계속 진행되고 있으며 진행 상황을 파악하는 것은 매우 어렵습니다.

Answer 1

일반적으로 그래프 디스플레이에 비해이 특별한 문제는 그리 어렵지 않습니다. 커밋 된 순서대로 노드를 유지하기 때문에 문제가 훨씬 간단 해집니다.

또한 디스플레이 모델은 그리드 기반이며, 행은 커밋이고 열은 과거/미래의 에지입니다.

git 소스를 읽지는 않았지만 가장 최근에 시작하여 커밋 목록을 살펴본 다음 열린 가장자리 목록을 과거로 유지하십시오. 가장자리를 따라 자연스럽게 분할/병합 열로 이어지고 종류의 나무 git/hg 표시로 끝납니다.

가장자리를 병합 할 때 다른 가장자리를 교차하지 않으려면 미리 열을 정렬해야합니다. 이것은 실제로 간단하지 않을 수있는 유일한 부분입니다. 예를 들어, 첫 번째 패스의 가장자리에 대해 열 순서를 만들고 두 번째 패스에서 드로잉을 수행하여 두 번 통과 알고리즘을 수행 할 수 있습니다.

Answer 2

나는 힘내거나 코드의 코드를 둘러 보았지만, 무슨 일이 일어나고 있는지에 대한 일반적인 생각을 따르는 것은 매우 어렵다.

hg의 경우 hg 자체 또는 그래프 로그의 코드를 따르려고 했습니까?

그래프 로그의 코드가 매우 짧기 때문에. 당신은 hgext/graphlog.py에서 그것을 찾을 수 있고, 중요한 부분은 최상위 200 줄입니다. 나머지는 확장 기능의 부트 스트랩과 선택된 개정 그래프를 찾는 것입니다. 코드 생성 기능이 마지막 파라미터

Answer 3

우선 (함수가 graphlog 의해 generate 제공되는 자체 generate의 마지막 행에 대해 수행되는 통화) asciiedge 호출의 결과 인 상태 ascii이고, 하나 얻는 커밋 목록 (git rev-list), 각 커밋의 부모. "열 예약 목록"은 메모리에 보관됩니다. 각각에 대해

는 커밋 :

• (가) 그것을 위해 예약 럼이없는 커밋 경우
  는 무료 컬럼에 할당합니다. 이것은 지점 머리가 시작하는 방법입니다.
• 열 예약 목록에 따라 트리 그래픽을 인쇄 한 후 메시지를 현재 컬럼의 예약의 목록 항목/전류의 최초의 부모로 업데이트됩니다 커밋하는 커밋
• , 같은 부모가가는 것을 커밋 같은 열에 인쇄하십시오.
• 다른 부모는 새로운 무료 열을 얻습니다.
• 이 병합 였다면, 다음 라인은은 (이 루프와 "≡ 다리"를 만든다)

예제의 출력을 나타내는 것으로 커밋 열에 제 부모를 연결하려고 할 aufs2-util의 git-forest에 분기가 두 개 이상있는 추가 커밋이 있음). 내다와

, 하나는 지금까지 병합 포인트 아래로 될 것이며 더 심미적으로 만족시키는 결과를 제공하기 위해 두 개의 열 사이에 나무를 짜내는 방법을 예상 할 수 있습니다.