如何在Shell中复现Git分支的继承树结构？

Alright, let's break down how to build that Git branch inheritance tree into a binary search tree structure in Shell—focusing on correctly capturing left/right node relationships. The key steps are gathering branch parent data, mapping commits to branches, and then structuring the tree (using left-child right-sibling notation since Git branches can have multiple children, which we need to adapt to a binary tree).

Step 1: Collect Branch-to-Parent Commit Mappings #

First, we need to get the parent commit(s) for each local branch. Git's git show command can pull this with the %p format flag, which returns all parent hashes (critical for handling merge branches).

# Declare associative arrays to store mappings
declare -A branch_parents  # key: branch name, value: space-separated parent commit hashes

# Populate branch-to-parent-commits mapping
for branch in $(git branch --format="%(refname:short)"); do
    # Get parent commits for the branch's HEAD
    parent_hashes=$(git show -s --pretty=%p "$branch")
    branch_parents["$branch"]="$parent_hashes"
done

Step 2: Map Commit Hashes Back to Branch Names #

Parent commits often correspond to the HEAD of another branch. We'll create a reverse mapping from commit hashes to the branches that point to them.

declare -A commit_to_branches  # key: commit hash, value: space-separated branch names

# Populate commit-to-branches mapping
for branch in $(git branch --format="%(refname:short)"); do
    commit_hash=$(git rev-parse "$branch")
    # Append branch name to the commit's entry (handles multiple branches pointing to same commit)
    commit_to_branches["$commit_hash"]="${commit_to_branches[$commit_hash]} $branch"
done

Step 3: Build Parent-to-Children Branch Mapping #

Now we'll reverse the branch-parent data to create a list of child branches for each parent branch.

declare -A parent_to_children  # key: parent branch, value: space-separated child branches

for branch in "${!branch_parents[@]}"; do
    parent_hashes=${branch_parents[$branch]}
    # Iterate over each parent commit hash for the current branch
    for hash in $parent_hashes; do
        # Get the first branch associated with this commit hash (adjust if you need all)
        parent_branch=$(echo "${commit_to_branches[$hash]}" | awk '{print $1}')
        if [[ -n "$parent_branch" ]]; then
            # Add current branch to the parent's child list
            parent_to_children["$parent_branch"]="${parent_to_children[$parent_branch]} $branch"
        fi
    done
done

Step 4: Convert Multi-Child Tree to Binary Tree (Left-Child Right-Sibling) #

Git branches can have multiple children, but a binary tree only allows two nodes per parent. The standard way to adapt this is using left-child right-sibling notation:

• The first child of a parent becomes its left child
• Each subsequent child becomes the right sibling of the previous child

declare -A branch_left_child     # key: branch, value: left child branch
declare -A branch_right_sibling  # key: branch, value: right sibling branch

for parent in "${!parent_to_children[@]}"; do
    # Sort child branches (adjust sort order based on your needs: name, commit date, etc.)
    sorted_children=$(echo "${parent_to_children[$parent]}" | tr ' ' '\n' | sort | tr '\n' ' ')
    sorted_children=${sorted_children% }  # Trim trailing space
    
    # Convert to array for iteration
    IFS=' ' read -r -a children_array <<< "$sorted_children"
    
    # Assign left child (first child)
    if [[ ${#children_array[@]} -gt 0 ]]; then
        branch_left_child["$parent"]="${children_array[0]}"
        
        # Assign right siblings for remaining children
        for ((i=0; i < ${#children_array[@]}-1; i++)); do
            current_child="${children_array[$i]}"
            next_child="${children_array[$i+1]}"
            branch_right_sibling["$current_child"]="$next_child"
        done
    fi
done

Step 5: Find Root Nodes & Print the Binary Tree #

Root nodes are branches with no parent. We'll identify them, then write a recursive function to print the tree structure.

# Find root branches (branches not listed as children of any other branch)
all_branches=$(git branch --format="%(refname:short)" | sort)
child_branches=$(printf "%s\n" "${!branch_left_child[@]}" "${!branch_right_sibling[@]}" | sort | uniq)
root_branches=$(comm -23 <(echo "$all_branches") <(echo "$child_branches"))

# Recursive function to print the binary tree
print_tree() {
    local branch=$1
    local indent=$2
    
    echo "${indent}${branch}"
    
    # Print left child first
    if [[ -n "${branch_left_child[$branch]}" ]]; then
        print_tree "${branch_left_child[$branch]}" "${indent}├─ "
    fi
    
    # Print right sibling next
    if [[ -n "${branch_right_sibling[$branch]}" ]]; then
        print_tree "${branch_right_sibling[$branch]}" "${indent}│  "
    fi
}

# Print all root trees
echo "Binary Tree Representation of Git Branch Inheritance:"
echo "-----------------------------------------------------"
for root in $root_branches; do
    print_tree "$root" ""
done

Key Notes #

• Sort Order: Adjust the sort command in Step 4 to order children by commit date (e.g., using git log --format=%ci "$branch" to sort chronologically) instead of alphabetical if that fits your needs better.
• Merge Branches: If a branch has multiple parent commits (from a merge), this script will map it to all parent branches. Tweak the parent_branch selection logic if you only want to track a single primary parent.
• Edge Cases: The associative arrays handle branches with no parents (root branches) and multiple branches pointing to the same commit seamlessly.

内容的提问来源于stack exchange，提问作者0andriy