[engine] STEM 구현

[anpaul0615]

STEM 개요

• 부모가 동일한 커밋을 한 줄로 보여준다

STEM 목적

• CSM 생성시,
  • 현재커밋과 분기커밋의 STEM 동일여부 확인
• CSM 클러스터링시,
  • 인접 CSM을 가져올때, 동일STEM 내 CSM 들을 가져옴

인터페이스

• input : CommitDAG
• output : CommitDAG (with STEM)

todo

• 모든 DAG 구성요소에 STEM 마킹

[ansrlm]

#21

[anpaul0615]

@ooooorobo
STEM 기능 정의를 위해 논의했던 내용들을 아래와 같이 정리해봤습니다.
한번 살펴보시고 의견부탁드릴게요!

• STEM 이란 무엇인가..?
• CommitRaw 에서 STEM 을 어떻게 만들수있는가..?
• STEM 은 어떤 데이터구조를 가져야하는가..?
• STEM 생성함수는 어떤 인터페이스를 가져야하는가..?
• STEM 으로 CSM 을 어떻게 만들수 있는가..?
• 그래서 STEM 은 어떤 기능을 가지고있어야하는가..?

---

STEM 이란 무엇인가..?

• 커밋을 한줄로 묶어놓은 개념
• 기본적으로는 브랜치 개수 === STEM 개수
• implicit branch 가 존재하면 implicit stem 으로 구분 (보통은 머지커밋의 자취)
• 즉, 하나의 repository에서는 N개의 STEM 만들어질수있음 (브랜치 개수 +@)

---

CommitRaw 에서 STEM 을 어떻게 만들수있는가..?

• 특정 브랜치의 커밋노드부터 시작하여, 첫번째 parent 를 찾아올라가면서(botton-up) 만들어짐 (parent-id 로 CommitDict 접근)
• 보통은 브랜치 커밋노드 === 그 브랜치의 leaf-node
• master 브랜치의 경우, 보통 leaf-node 부터 root-node 까지 묶임
• 그 외 브랜치의 경우, leaf-node 부터 브랜치 분기 node 까지 묶임
• implicit 브랜치 의 경우, 머지커밋으로부터 브랜치 분기 node 까지 묶임

---

STEM 은 어떤 데이터구조를 가져야하는가..?

• type STEM = CommitRaw[]
• index 로 next/prev 접근 (어차피 한줄이니깐)
• STEM 만드는 과정에서 CommitDict 를 먼저 만들어야함 (parent 찾아가는 용도)

---

STEM 생성함수는 어떤 인터페이스를 가져야하는가..?

• function buildStem( CommitRaw[] ) : STEM[] => { ... };
• CommitRaw[] 를 전달받아, STEM 목록을 반환함 (하나의 repository에서 N개의 STEM 만들어질수있으므로)

---

STEM 으로 CSM 을 어떻게 만들수있는가..?

• CSM 은 각 STEM의 root-node 부터 시작하여, leaf-node 까지 찾아내려가면서(top-down) 만들어짐
• STEM 은 한줄Array 형식이므로, child 로 넘어갈때는 index번호로 next 탐색
• child 탐색중 머지커밋을 발견하면, parent[1] 을 찾아올라가게됨 (parent-id 로 CommitDict 접근)
  • parent[1] 로 이동한 노드는 다른 STEM 에 소속된 노드이므로, index번호로 prev 탐색하여 parent 를 찾아올라갈수있음
  • 다른 STEM을 탐색하는중에 다시 현재 STEM 을 만나게되면, 그동안 방문했던 STEM 노드들을 머지커밋으로 가져와 묶음 (종료조건)
  • 다른 STEM을 탐색하는중에 다시 머지커밋을 발견하면, 동일하게 parent[1] 을 찾아올라가서 동일한 행위를 반복함 (재귀호출)

---

STEM → CSM 을 위해 필요한 기능은 무엇인가..?

• 한 커밋노드에서 parent[1] 로 통해 다른 커밋노드로 이동할 수 있어야함 (머지커밋의 parent[1] 로 이동)
  => CommitDict 로 해결..?
• STEM 안에서의 노드에서 prev/next 로 이동할수있어야함 (머지커밋을 찾기위한 순탐색, 머지커밋의 parent[1] 부터 역탐색)
  => STEM 자체가 한줄짜리 Array 형태이므로, 인덱스 기반 prev/next 접근..?