Git as a Directed Acyclic Graph (DAG) 🕸️

Mục tiêu: Hiểu tại sao Git là DAG và tại sao operations chỉ là di chuyển pointers.

Bạn đã học về Blobs, Trees, và Commits. Bây giờ hãy zoom out và nhìn bức tranh toàn cảnh: Git là một Directed Acyclic Graph - và điều này giải thích MỌI THỨ về cách Git hoạt động.

---

🎯 What is a DAG?

Định nghĩa

Directed Acyclic Graph (DAG) là một đồ thị có hướng không có chu trình:

• Directed: Các cạnh có hướng (từ A đến B, không phải ngược lại)
• Acyclic: Không có đường đi nào quay về điểm xuất phát

Git as a DAG

Mỗi commit trỏ đến parent (ngược thời gian):

• Mũi tên đi từ commit mới → commit cũ
• Không thể tạo vòng lặp (commit không thể là ancestor của chính nó)

---

🔀 Branching and Merging in the DAG

Linear History

Branching

Khi tạo branch:

• Không copy bất kỳ data nào
• Chỉ tạo một file mới trong refs/heads/ chứa SHA-1

# Tạo branch = tạo file chứa SHA-1
git branch feature
cat .git/refs/heads/feature
# Output: a1b2c3d4... (same as current commit)

Merging

Merge commit có 2 parents → đây là điểm hội tụ trong DAG.

# Xem merge commit
git cat-file -p HEAD

# Output:
# tree abc123...
# parent def456...  ← main branch's previous commit
# parent ghi789...  ← feature branch's commit
# author HPN ...
#
# Merge branch 'feature'

---

📍 Refs: Pointers into the DAG

Refs (references) là named pointers trỏ vào các nodes trong DAG.

Types of Refs

Ref Storage

# HEAD: symbolic ref
cat .git/HEAD
# ref: refs/heads/main

# Branch: commit SHA-1
cat .git/refs/heads/main
# a1b2c3d4e5f6...

# Remote tracking branch
cat .git/refs/remotes/origin/main
# 9z8y7x6w5v...

---

⚡ Operations are Just Pointer Moves

Đây là insight quan trọng nhất: Hầu hết các Git operations chỉ là di chuyển pointers.

git checkout / git switch

Checkout chỉ làm 2 việc:

1. Update HEAD để trỏ đến branch mới
2. Update working directory để match snapshot

# Checkout = update HEAD + update working dir
git checkout feature
# Equivalent to:
# echo "ref: refs/heads/feature" > .git/HEAD
# git restore --source=feature .

---

git branch

# Tạo branch = tạo file mới chứa SHA-1
git branch new-feature
# Tương đương với:
git rev-parse HEAD > .git/refs/heads/new-feature

Cost: O(1) - Chỉ tạo một file 40 bytes!

---

git reset

Reset chỉ di chuyển branch pointer. Commit C3 vẫn tồn tại - chỉ không còn ref nào trỏ đến nó.

ORPHANED COMMITS

Commits không có ref trỏ đến gọi là "unreachable". Chúng vẫn tồn tại trong .git/objects/ và có thể recover qua reflog - cho đến khi git gc dọn dẹp.

---

git merge (Fast-forward)

Fast-forward merge = Di chuyển pointer. Không tạo commit mới!

---

git rebase

Rebase tạo commits MỚI (C3', C4') với nội dung tương tự nhưng SHA-1 khác (vì parent khác).

---

🔍 Why DAG Matters

1. Efficient Storage

• Objects được share giữa các branches
• Không duplicate data khi branch

2. Fast Operations

• Branch/checkout: O(1) pointer update
• Merge (fast-forward): O(1) pointer update
• History traversal: Follow parent links

3. Integrity

• SHA-1 của commit phụ thuộc vào toàn bộ history
• Thay đổi bất kỳ commit nào → thay đổi tất cả descendants

4. Distributed

• Mỗi clone là một DAG hoàn chỉnh
• Merge = liên kết các DAGs với nhau

---

📊 Complete DAG Visualization

---

🛠️ Hands-on: Visualize Your DAG

# Text-based DAG visualization
git log --graph --oneline --all --decorate

# Example output:
# * a1b2c3d (HEAD -> main) Latest commit
# *   e5f6g7h Merge feature branch
# |\  
# | * i9j0k1l (feature) Add new feature
# | * m3n4o5p Feature WIP
# * | q7r8s9t Hotfix on main
# |/  
# * u1v2w3x Previous commit
# * y5z6a7b Initial commit

# Count commits reachable from HEAD
git rev-list HEAD --count

# Find common ancestor
git merge-base main feature

# List all refs
git show-ref

---

💡 Key Takeaways

HPN'S INSIGHT

"Khi bạn hiểu Git là DAG + Pointers, mọi lệnh Git đều trở nên intuitive. Checkout? Di chuyển HEAD. Reset? Di chuyển branch. Merge? Liên kết DAG nodes."

Summary Table

Operation	DAG Effect	Pointer Effect
commit	Add new node	Move current branch
branch	None	Create new pointer
checkout	None	Move HEAD
reset	None (orphan possible)	Move branch
merge (ff)	None	Move branch
merge (3-way)	Add merge node	Move branch
rebase	Add new nodes (copies)	Move branch

The Mental Model

Git = Immutable DAG of Commits + Mutable Refs (Pointers)

1. Commits form an immutable DAG - Once created, never change
2. Refs are just pointers - They can move freely
3. Most operations move pointers - The DAG mostly grows, rarely changes
4. Unreachable nodes get garbage collected - Eventually, by git gc

GOLDEN RULE

Objects are immutable. Refs are mutable. Hiểu điều này, bạn hiểu Git.