[engine] Stem 생성 로직 동작 예시

[ooooorobo]

DAG 순회 시작하기

Stem을 만들기 위해, Commit DAG(Directed Acyclic Graph)의 leaf node부터 순회를 시작합니다. 어떤 CommitRaw 객체의 branches 배열이 비어 있지 않다면, 해당 커밋은 DAG의 leaf node인 것으로 판단할 수 있습니다.

DAG를 순회하기 위해, 시작점인 leaf node를 큐에 담습니다. 이 때, 기준점이 되는 브랜치의 커밋을 큐에 가장 먼저 담습니다. 기준점 외의 leaf node는 commitDate 최신순으로 담습니다.

그런데 branches 값 중 'HEAD'가 포함되어 있다면, 그 커밋은 leaf node가 아닐 가능성이 있습니다. (git checkout 커맨드로 leaf node가 아닌 커밋에 HEAD 포인터를 이동시킬 수 있습니다) 따라서, 'HEAD'가 포함된 커밋은 큐에 leaf node 중에서 가장 마지막에 담습니다.

예시 그림에서, 기준 브랜치를 'main' 브랜치로 설정했을 때, 큐에 모든 leaf node를 담고 나면 [f, m, o] 순으로 담깁니다.

Stem 객체 만들기

큐에 값이 존재한다면, dequeue로 커밋 노드를 꺼내고, Stem 객체 생성을 준비합니다. 이 때 dequeue하여 꺼낸 커밋을 'tail node'라고 부르겠습니다.

큐에서 dequeue로 커밋 f를 꺼냈습니다. 큐에는 [m(i'), o]가 담겨 있습니다.

Stem 객체는 ID 값을 가집니다. ID는 아래와 같이 결정됩니다.

• tail node가 branch를 가지고 있고,
  • branches에 기준 브랜치가 포함되어 있다면 기준 브랜치의 이름
  • branches에 HEAD가 포함되어 있다면 'HEAD'
  • 그 외의 경우, branches[0]
• tail node에 branches가 비어 있다면, implicit-{numbering}

커밋 f는 'main' 브랜치를 가지고 있습니다. 'main' 브랜치는 기준 브랜치이므로, 커밋 f가 만드는 stem의 ID는 'main' 입니다.

Stem 객체는 CommitNode 배열을 가집니다. tail node부터 순회를 시작하며, 커밋의 parents[0]이 존재하지 않을 때까지 parents[0]를 따라 순회합니다. 이 때, 순회한 커밋은 Stem의 CommitNode 배열에 넣습니다.

커밋 f부터 순회를 시작해서, parents[0]이 존재하지 않는 커밋 a까지 순회합니다. 배열은 [f, e, d, c, b, a]가 되었습니다.

순회 도중 parents를 2개 이상 가지고 있는 커밋을 만난다면, parents 배열에서 인덱스가 1 이상인 커밋을 큐에 담습니다.

순회 도중 parents를 2개 이상 가지는 커밋 e, c를 만났습니다. 두 커밋의 parents 중 인덱스가 1 이상인 것들을 큐에 담아 큐에는 [m(i'), o, i, g]가 담겨 있습니다.

순회를 완료한 CommitNode에는 그 커밋이 포함된 Stem의 Id를 마킹합니다. 이 값으로 해당 커밋을 순회했는지 여부를 알 수 있습니다.

a~f 커밋의 CommitNode.stemId === 'main' 입니다.

이 과정을 큐가 완전히 빌 때까지 반복합니다.

그러면 결과적으로 아래와 같은 StemDict가 생성됩니다.

{
  'main': [f, e, d, c, b, a],
  'implicit-1': [i, h, g],
  'dev': [m(i'), l, k, j],
  'HEAD': [o, n]
}

예외 상황

노드 g

buildStem 호출 시, f 노드부터 순회를 시작합니다. 그러면 큐에는 i, g 노드가 담기게 됩니다.
그런데 만약 i가 아니라 g부터 순회를 시작한다면, g번 노드가 만드는 Stem은 [g]이 되고, i번 노드가 만드는 Stem은 [h, i]가 됩니다.
올바른 Stem은 [g, h, i]가 되어야 합니다. 따라서 i가 g보다 큐에서 먼저 위치해야 하므로, 커밋된 시간이 더 늦은 노드가 우선순위가 높습니다.

노드 m(i')

m(i') 노드는 i 노드의 체리픽 노드입니다. 따라서 authorDate와 CommitterDate이 다릅니다.
authorDate는 i 노드와 같은 값을, CommitterDate는 cherry-pick을 수행한 시간을 가집니다.
따라서 커밋 노드를 정렬할 때 CommitterDate를 기준으로 정렬해야 합니다.

노드 o

o는 HEAD가 가리키는 브랜치입니다. 그리고 n은,

• m(i’)번을 커밋한 시점에서,
• l 커밋에 checkout한 다음,
• i 커밋을 merge한 상황입니다.

이런 상황에서, 다른 브랜치의 커밋 노드보다 HEAD 브랜치의 노드인 o 부터 순회를 시작한다면, [j, k, l, n, o] Stem이 생성되고, Dev 브랜치의 Stem은 [m(i')]로 만들어집니다.
따라서 main/master/sub 브랜치의 Stem이 모두 생성된 다음, HEAD Stem을 만들고, implicit 브랜치의 Stem을 만들어야 합니다.

커밋 우선순위

큐는 아래의 우선순위에 따라 커밋을 정렬합니다.

1. 기준 브랜치 커밋
2. 기준 브랜치가 아니고 HEAD가 아닌 sub 브랜치 커밋들
3. HEAD 커밋
4. branches.length === 0인 커밋들

• 위 우선순위가 동일할 경우, CommitDate가 최신일수록 우선순위가 높음

관련 PR

#91

[ansrlm]

정리 너무 잘하셨습니다!!

[ytaek]

이슈 정리중입니다~. 정리가 끝난 이슈면 close 해주시면 감사하겠습니다 😸

[ytaek]

아.. 빠른 정리를 위해 제가 일단 임의로 닫겠습니다 : ---)
knowledge쪽은 wiki 쪽으로 한번 빼서 정리하는게 필요하겠네요.