STEM
- 상위 노드 중 하나만 포함하는 특정 커밋의 상위 노드 목록
- 단일 브랜치에만 소속되어 있는 노드들의 집합
(출처 : https://ieeexplore.ieee.org/document/9222261#sec5a1)
The top straight line in the DAG of a Git repository generally represents the master branch (Fig. 4a).
However, an overwhelming number of branches and the connected links between them could hinder tracking down the origin of changes even for commits in the master branch.
To alleviate this problem, Githru removes the connected links between the branches in a DAG to form a group of stems.Git 리포지토리의 DAG에서 위쪽 직선은 일반적으로 마스터 브랜치를 나타냅니다.
그러나 압도적인 수의 브랜치와 이들 사이의 연결된 링크는 마스터 브랜치의 커밋에 대해서도 변경 출처를 추적하는 데 방해가 될 수 있습니다.
이 문제를 완화하기 위해, Githru는 DAG의 브랜치 사이에 연결된 링크를 제거하여 STEM 그룹을 형성합니다.
A stem is a list of ancestor nodes for a specific commit that includes only one of the parents when there are multiple preceding nodes.
STEM 은 선행 노드가 여러 개 있을 때 상위 노드 중 하나만 포함하는 특정 커밋의 상위 노드 목록입니다.It is similar to the first-parent option of the git log command, which removes other parent nodes from a branch.
(분기에서 다른 부모 노드를 제거하는) git log 명령의 first-parent 옵션과 유사합니다.However, git log focuses only on a single branch while neglecting pruned nodes and their parents.
그러나 git log는 가지치기(pruned)된 노드와 그 부모를 무시하고 단일 브랜치에만 초점을 맞춥니다.Conversely, Githru applies the approach to every branch to provide an overview of the overall history of development.
그에 비해 Githru는 모든 브랜치에 접근 방식을 적용하여 전체 개발 히스토리에 대한 개요를 제공합니다.
The process starts with building the main stem from the master branch, into which commits finally merge.
Pruning a branch could affect the topology of other branches that exclusively occupy common ancestor nodes.
Thus, we begin the process from the master branch to preserve the order of events in the mainline of development.
The rest of the branches are pruned afterward by retaining only the first parent commits in each branch.
Then, we remove links to non-first-parent nodes in adjacent stems to reduce visual complexity.
Eventually, only one path remains for every stem.
Due to the simple topology and reduced number of edges, the result provides a brief overview of branches and enables simple traversal without any backtracking to multiple parents.프로세스는 커밋이 최종적으로 병합되는 master/main 브랜치에서 메인 STEM을 구축하는 것으로 시작됩니다.
브랜치를 가지치기하면 공통 조상 노드를 독점적으로 차지하는 다른 브랜치의 토폴로지에 영향을 줄 수 있습니다.
따라서 우리는 개발의 메인라인에서 이벤트의 순서를 유지하기 위해 마스터 브랜치에서 프로세스를 시작합니다.
나머지 브랜치는 각각 첫 번째 상위 커밋만 유지되도록 정리됩니다.
그런 다음 시각적 복잡성을 줄이기 위해, 인접한 STEM에서 첫 번째 부모가 아닌 노드에 대한 링크를 제거합니다.
결국 모든 브랜치에 대해 하나의 경로만 남게 됩니다.
단순한 토폴로지와 감소된 엣지 수로 인해, 결과는 브랜치에 대한 간략한 개요를 제공하고, 여러 부모에 대한 역추적 없이 간단한 순회를 가능하게 합니다.
The downside of converting to a stem structure is leaving extra implicit stems that have no branch information, as shown in Fig. 4b.
Also, the process removes links between stems that hold branching and merging information.
However, in the case of understanding the context of development history, the experts in requirement analysis confirmed that they were interested in finding the contents of merged commits rather than the underlying links between branches.
We combat these disadvantages through a Context-Preserving Squash Merge, described in the following section.STEM 구조로 변환할 때의 단점은 브랜치 정보가 없는(implicit) 브랜치가 남는다는 것입니다.
또한 이 프로세스는 병합 정보를 보유하는 브랜치 간의 링크를 제거합니다.
그러나 개발 이력의 맥락을 이해하는 경우, 요구사항 분석 전문가들은 브랜치 간의 기본 연결보다 병합된 커밋의 내용을 찾는데 관심이 있음을 확인했습니다.
우리는 다음 섹션에서 설명하는 CSM(Context-Preserving Squash Merge)를 통해 이러한 단점을 해결합니다.
- master/main 브랜치의 마지막 커밋부터 시작해서 첫번째 상위커밋만 따라 올라간다
- 순회한 모든 커밋을 동일 STEM 으로 묶는다
- 나머지 브랜치에서도 반복한다 (implicit 브랜치 포함)
DAG(stemA) ← DAG(stemA) ← DAG(stemA) <<< start!
↖ DAG(stemB) ← DAG(stemB) <<< start!
- input : DAG
- output : DAG (with STEM)
-
리프노드를 찾는다
top-down DAG 일경우, 최초커밋 or 고아커밋 (n개가 될수있음)- bottom-up DAG 일경우, 마지막커밋 (n개가 될수있음)
-
노드의 parent 를 찾는다
- parent 1개 : 일반커밋. parent[0] 으로 넘어감 (마킹)
- parent 2개 : 머지커밋. parent[0] 으로 넘어감 (마킹) + parent[1] 으로 넘어감 (재귀호출)
- parent 0개 : 마지막커밋. 종료
-
순회한 노드의 parent 가 0 일때까지 2) 를 반복한다
-
DAG 섹션 내 "기존 코드 분석 - STEM" 부분 참조
let branchedNodes = [this.getNodeById(this.headId)].concat(branchedNodesNotHead);
let FPTreeNodeListMapByNodeId = {};
branchedNodes.forEach( branchedNode => {
let id = branchedNode.id;
let firstParentNodesOrderedList = [];
let firstParentTreeBranchNames = this.nodesMap[id].commit.branches;
let isHeadBranch = (id === this.headId);
branchedNode.isLeaf = true;
branchedNode.traversed = true;
branchedNode.firstParentTreeBranchNames = firstParentTreeBranchNames;
branchedNode.firstParentTreeLeafNode = branchedNode;
while (id in this.firstParentIdMap) {
id = this.firstParentIdMap[id];
let node = this.getNodeById(id);
if (node.traversed === true) break;
if (isHeadBranch) {
node.isMainStem = true;
node.implicitBranchNo = 0;
} else {
if (node.commit.branches !== undefined && node.commit.branches.length > 0) {
break;
}
}
firstParentNodesOrderedList.push(node);
// TODO - suppose that isHead = origin/master
// it is NOT commit's branch name but node's
node.firstParentTreeBranchNames = firstParentTreeBranchNames;
node.firstParentTreeLeafNode = branchedNode;
// node.branches = headBranchNames;
node.traversed = true;
}
FPTreeNodeListMapByNodeId[branchedNode.id] = firstParentNodesOrderedList;
});/////////////////////////////////////
// get implicit branch number
let bno = 0;
let rootCount = 0;
this.allNodeList.forEach(node => {
// when meet other roots
if (node.isRoot && !node.isMainStem) {
node.implicitBranchNo += 10000 + this.allNodeList.length + rootCount++;
}
let firstParentChildNodes = this.getChildNodes(node).filter(childNode => this.firstParentIdMap[childNode.id] === node.id);
if (firstParentChildNodes.length === 0) {
node.hasNoFirstParentChild = true;
return;
}
let implicitBranchNo = node.implicitBranchNo;
firstParentChildNodes
.sort( (a, b) => (b.seq - a.seq))
.sort( (a, b) => (b.implicitBranchNo - a.implicitBranchNo))
.forEach( (childNode, i) => {
if (i === 0) {
childNode.implicitBranchNo = implicitBranchNo;
} else {
childNode.implicitBranchNo = ++bno;
}
});
});