DAG

DAG (Directed Acyclic Graph)

• 순환이 없는 무한 유향 그래프 wikipedia
  • 방향 그래프이므로, 각 간선은 방향을 가진다.
  • 비순환 그래프이므로, 임의의 노드 s, v에서 s -> v로 향하는 경로가 있다면 v -> s 방향으로 이어지는 경로는 없다.

Git Commit DAG

Git 메타데이터는 각 커밋의 집합이다. 커밋은 부모 커밋과 연결되며, 이는 DAG로 표현된다.

이미지 출처

• Root 노드는 여러개일 수 있다 (orphan branch)
• 하나의 노드가 여러 개의 parent를 가질 수 있다 (merge commit)

한계

프로젝트가 성장하는 만큼, 개발자가 만드는 브랜치 수와 생성되는 implicit branch도 늘어난다. 브랜치의 개수가 많아지면 그래프가 매우 많은 갈래로 갈라지며 복잡해지고, 결국 그래프만을 통해서는 전반적인 개발 히스토리를 알기 어렵다.

기존 코드 분석

기존 Githru Analyzer에서, 그래프를 생성하는 코드를 간소화한 코드.

DAG 부분에서 해줘야 할 일

• 주요
  • 커밋 리스트의 각 커밋에 해당하는 노드를 생성
    • 이때, 커밋과 parent commit이 연결될 수 있도록 처리해주기 (이후 STEM 생성을 위해)
  • 노드를 잇는 간선 생성
    • 🤔 사용하는 곳이 있는지?
• 부차적
  • 커밋이 머지 커밋인지 체크
  • 머지 커밋에 PR 정보를 연결
  • 커밋에 등록된 태그가 release 태그인지 확인 + release 태그라면 노드에 표시해주기

const allNodeMap: Map<string, CommitNode> = new Map();
const allNodeList: Array<CommitNode> = [];
const rootNodeList: Array<CommitNode> = [];
const edgeList: Array<CommitEdge> = [];
const nodeToFirstParentIdMap: Map<string, string> = new Map();

function buildContextAbstractionGraph(commits, headId) {
    // 커밋 노드 생성
    commits.forEach(commit => {
        const node = new CommitNode(commit.id, commit);
        allNodeList.push(node);
        allNodeMap.set(commit.id, node);

        if (commit.parents.length === 0) {
            rootNodeList.push(node);
        } else {
            // 나중에 STEM 만들 때 필요함
            nodeToFirstParentIdMap.set(commit.id, commit.parents[0]);
        }

        if (isMergeCommit(node)) {
            node.isMergeCommit = true;
        }
    })

    /**
     * -- 여기서 PR 관련 처리...
     */

    // 간선 생성 =>> view에서 사용?
    commits.forEach(commit => {
        commit.parents.forEach(parentId => {
            const edge = new CommitEdge(commit.id, parentId);
            edgeList.push(edge);
        })
    })

    /**
     * -- 여기서 tag 관련 처리...
     * release 태그가 붙은 커밋을 가진 노드는 isMajorRelease 표시해둔다.
     */

    /**
     *  STEM 만드는 부분
     */
    const allBranchedNodes = allNodeList.filter(node => node.hasBranches());
    const branchIdToNodeListMap: Map<string, CommitNode[]> = new Map();

    allBranchedNodes.forEach(branchedNode => {
        let nowNode = branchedNode
        const isHead = branchedNode.id === headId

        const orderedNodeListInBranch = [branchedNode];
        // 브랜치가 가리키고 있는 노드부터 parent 방향으로 순회한다
        while (nowNode.id in nodeToFirstParentIdMap) {
            nowNode = nodeToFirstParentIdMap[nowNode.id];
            if (isHead) {
                nowNode.isMainStream = true;
            } else if (nowNode.isRoot()) {
                break;
            }

            orderedNodeListInBranch.push(nowNode);
            nowNode.leafNode = branchedNode;
        }

        branchIdToNodeListMap.set(branchedNode.id, orderedNodeListInBranch);
    })

    /**
     * -- 여기서 implicit branch number 계산..
     */

    /**
     * CSM 만드는 부분
     * -- 여기서 branchIdToNodeListMap를 돌면서, 머지 커밋을 찾는다...
     * 머지 커밋을 찾으면 squash함
     */
}