মার্জিং — fast-forward বনাম three-way merge

# git-এর থ্রি-ট্রি + branching + merge মডেল (L30, L34 রিইউজ) -- এই স্যান্ডবক্সে real git নেই,
# তাই এটি git-এর অভ্যন্তরীণ আচরণের একটি বিশ্বস্ত সিমুলেশন, real git চালানো নয়।

def make_repo():
    return {
        "working_directory": {},
        "staging_area": {},
        "commits": {},
        "branches": {"main": None},
        "head": "main",
    }

def current_commit_hash(repo):
    if repo["head"] in repo["branches"]:
        return repo["branches"][repo["head"]]
    return repo["head"]

def git_add(repo, filename):
    repo["staging_area"][filename] = repo["working_directory"][filename]

def git_commit(repo, message):
    parent = current_commit_hash(repo)
    commit_hash = f"c{len(repo['commits']) + 1}"
    repo["commits"][commit_hash] = {
        "message": message,
        "snapshot": dict(repo["staging_area"]),
        "parent": parent,
    }
    if repo["head"] in repo["branches"]:
        repo["branches"][repo["head"]] = commit_hash
    else:
        repo["head"] = commit_hash
    repo["staging_area"] = {}   # বাস্তব git-এর মতোই কমিটের পর staging area খালি হয়ে যায় (L30 রিইউজ)
    return commit_hash

def git_branch(repo, name):
    repo["branches"][name] = current_commit_hash(repo)

def git_switch(repo, branch_name):
    repo["head"] = branch_name
    target_hash = repo["branches"][branch_name]
    snapshot = dict(repo["commits"][target_hash]["snapshot"]) if target_hash else {}
    repo["working_directory"] = dict(snapshot)
    repo["staging_area"] = dict(snapshot)


# ---- মার্জ-সংক্রান্ত হেল্পার ----
def ancestors(repo, commit_hash):
    """commit_hash থেকে parent অনুসরণ করে root পর্যন্ত সব পূর্বপুরুষের তালিকা (নিজেসহ)।"""
    result = []
    current = commit_hash
    while current:
        result.append(current)
        current = repo["commits"][current]["parent"]
    return result

def is_ancestor(repo, maybe_ancestor_hash, commit_hash):
    return maybe_ancestor_hash in ancestors(repo, commit_hash)

def find_merge_base(repo, branch_a, branch_b):
    """দুই branch-এর সবচেয়ে সাম্প্রতিক কমন পূর্বপুরুষ -- LCA-স্টাইল গ্রাফ সার্চ (dsa-র সাথে সম্পর্কিত)।"""
    hash_a = repo["branches"][branch_a]
    hash_b = repo["branches"][branch_b]
    ancestors_a = ancestors(repo, hash_a)         # tip থেকে root পর্যন্ত, ক্রমানুসারে
    ancestors_b_set = set(ancestors(repo, hash_b))
    for h in ancestors_a:
        if h in ancestors_b_set:
            return h
    return None

def git_merge(repo, source_branch):
    target_branch = repo["head"]
    target_hash = repo["branches"][target_branch]
    source_hash = repo["branches"][source_branch]

    if is_ancestor(repo, target_hash, source_hash):
        # ফাস্ট-ফরওয়ার্ড: target এখনো source-এর ইতিহাসের ভেতরেই আছে, নড়েনি
        repo["branches"][target_branch] = source_hash
        repo["working_directory"] = dict(repo["commits"][source_hash]["snapshot"])
        repo["staging_area"] = dict(repo["commits"][source_hash]["snapshot"])
        return {"type": "fast-forward", "new_head": source_hash}

    # থ্রি-ওয়ে মার্জ: merge base খুঁজে দুই পাশের পরিবর্তন একত্রিত করা (সরলীকৃত, conflict-free ধরে নেওয়া হচ্ছে)
    base_hash = find_merge_base(repo, target_branch, source_branch)
    base_snapshot = repo["commits"][base_hash]["snapshot"] if base_hash else {}
    target_snapshot = repo["commits"][target_hash]["snapshot"]
    source_snapshot = repo["commits"][source_hash]["snapshot"]

    merged_snapshot = dict(source_snapshot)
    for filename, target_content in target_snapshot.items():
        if base_snapshot.get(filename) != target_content:
            merged_snapshot[filename] = target_content  # target-পাশে বদলানো ফাইল ধরে রাখা

    new_hash = f"c{len(repo['commits']) + 1}"
    repo["commits"][new_hash] = {
        "message": f"Merge branch '{source_branch}' into {target_branch}",
        "snapshot": merged_snapshot,
        "parent": target_hash,
        "parents": [target_hash, source_hash],  # আসল দুই parent -- merge commit-এর প্রমাণ
    }
    repo["branches"][target_branch] = new_hash
    repo["working_directory"] = dict(merged_snapshot)
    repo["staging_area"] = dict(merged_snapshot)
    return {"type": "three-way-merge", "new_head": new_hash, "merge_base": base_hash}


# ==== সিনারিও ১: ফাস্ট-ফরওয়ার্ড (main নড়েনি) ====
repo_ff = make_repo()
repo_ff["working_directory"]["readme.md"] = "# প্রজেক্ট"
git_add(repo_ff, "readme.md")
git_commit(repo_ff, "প্রাথমিক কমিট")

git_branch(repo_ff, "feature-x")
git_switch(repo_ff, "feature-x")
repo_ff["working_directory"]["feature.py"] = "def f(): return 1"
git_add(repo_ff, "feature.py")
git_commit(repo_ff, "ফিচার শুরু")
repo_ff["working_directory"]["feature.py"] = "def f(): return 2"
git_add(repo_ff, "feature.py")
git_commit(repo_ff, "ফিচার আপডেট")

git_switch(repo_ff, "main")  # main এখনো প্রথম কমিটেই
result_ff = git_merge(repo_ff, "feature-x")

print("=== সিনারিও ১: ফাস্ট-ফরওয়ার্ড ===")
print("ফলাফল:", result_ff)
print("main pointer এখন:", repo_ff["branches"]["main"])
print("মোট কমিট সংখ্যা:", len(repo_ff["commits"]), "(কোনো নতুন merge commit তৈরি হয়নি!)")

# ==== সিনারিও ২: থ্রি-ওয়ে মার্জ (দুই branch-ই বিচ্যুত) ====
repo_dv = make_repo()
repo_dv["working_directory"]["readme.md"] = "# প্রজেক্ট ২"
git_add(repo_dv, "readme.md")
git_commit(repo_dv, "প্রাথমিক কমিট")

git_branch(repo_dv, "feature-y")
git_switch(repo_dv, "feature-y")
repo_dv["working_directory"]["feature.py"] = "def g(): pass"
git_add(repo_dv, "feature.py")
git_commit(repo_dv, "feature-y: feature.py যোগ")

git_switch(repo_dv, "main")
repo_dv["working_directory"]["readme.md"] = "# প্রজেক্ট ২\nmain-এ আপডেট হয়েছে"
git_add(repo_dv, "readme.md")
git_commit(repo_dv, "main: readme আপডেট")

result_dv = git_merge(repo_dv, "feature-y")

print("\n=== সিনারিও ২: থ্রি-ওয়ে মার্জ (বিচ্যুত) ===")
print("ফলাফল:", result_dv)
new_hash = result_dv["new_head"]
print("merge commit-এর parents ফিল্ড:", repo_dv["commits"][new_hash]["parents"])
print("merge commit-এর snapshot:", repo_dv["commits"][new_hash]["snapshot"])
print("মোট কমিট সংখ্যা:", len(repo_dv["commits"]), "(ঠিক ১টি নতুন merge commit যোগ হয়েছে)")