Show the dependence tree of remote git branches (clone repo and run this script inside)

git_branch_dependence.py

#!/usr/bin/env python3

import subprocess
import sys
from collections import defaultdict

def get_branches(include_local=False):
    """Get branches in the repository."""
    branches = []
    
    if include_local:
        # Get local branches
        result = subprocess.run(
            ['git', 'branch'],
            capture_output=True,
            text=True
        )
        
        if result.returncode != 0:
            print("Error: Not a git repository or git not found")
            sys.exit(1)
        
        for line in result.stdout.split('\n'):
            line = line.strip().lstrip('* ')
            if line:
                branches.append(line)
    
    # Get remote branches
    result = subprocess.run(
        ['git', 'branch', '-r'],
        capture_output=True,
        text=True
    )
    
    if not include_local and result.returncode != 0:
        print("Error: Not a git repository or git not found")
        sys.exit(1)
    
    for line in result.stdout.split('\n'):
        line = line.strip()
        if line and 'HEAD' not in line:
            branches.append(line)
    
    return branches

def is_subset(branch1, branch2):
    """Check if branch1 is a complete subset of branch2."""
    result = subprocess.run(
        ['git', 'log', branch1, '--not', branch2, '--oneline'],
        capture_output=True,
        text=True
    )
    
    # If there are no commits only in branch1, it's a subset of branch2
    return len(result.stdout.strip()) == 0

def build_hierarchy(branches):
    """Build a hierarchy of branches based on subset relationships."""
    # Find all subset relationships
    subsets = defaultdict(set)  # parent -> set of children
    parents = defaultdict(set)  # child -> set of parents
    
    print("Checking all branch pairs...")
    for i, branch1 in enumerate(branches):
        if i % 5 == 0:
            print(f"  Checked {i}/{len(branches)} branches...")
        for branch2 in branches:
            if branch1 != branch2 and is_subset(branch1, branch2):
                subsets[branch2].add(branch1)
                parents[branch1].add(branch2)
    
    print(f"  Checked {len(branches)}/{len(branches)} branches.")
    print()
    
    # Find root branches (those that are not subsets of any other branch)
    all_subsets = set()
    for children in subsets.values():
        all_subsets.update(children)
    
    roots = [b for b in branches if b not in all_subsets]
    
    # For each branch, find its immediate parent (most specific superset)
    # Skip identical branches (where A is subset of B and B is subset of A)
    immediate_parent = {}
    for branch in all_subsets:
        if branch in parents:
            parent_list = list(parents[branch])
            
            # Filter out circular relationships (identical branches)
            parent_list = [p for p in parent_list if branch not in subsets.get(p, set())]
            
            if not parent_list:
                # This branch only has circular relationships, treat as root
                roots.append(branch)
                continue
            
            # Find the parent that is itself a subset of all other parents
            # This is the most specific (smallest) superset
            best_parent = None
            
            for candidate in parent_list:
                # Check if this candidate is a subset of all other parents
                is_most_specific = True
                for other in parent_list:
                    if candidate != other and not is_subset(candidate, other):
                        is_most_specific = False
                        break
                
                if is_most_specific:
                    best_parent = candidate
                    break
            
            if best_parent:
                immediate_parent[branch] = best_parent
            else:
                # No clear best parent, pick the first one
                immediate_parent[branch] = parent_list[0]
    
    return roots, immediate_parent

def print_tree(branch, immediate_parent, prefix="", is_last=True, printed=None):
    """Print the tree recursively."""
    if printed is None:
        printed = set()
    
    if branch in printed:
        return
    
    printed.add(branch)
    
    # Print current branch
    connector = "└── " if is_last else "├── "
    print(f"{prefix}{connector}{branch}")
    
    # Find children of this branch
    children = [child for child, parent in immediate_parent.items() if parent == branch]
    
    # Sort children for consistent output
    children.sort()
    
    # Print children
    extension = "    " if is_last else "│   "
    for i, child in enumerate(children):
        is_last_child = (i == len(children) - 1)
        print_tree(child, immediate_parent, prefix + extension, is_last_child, printed)

def print_simple_chains(roots, immediate_parent):
    """Print chains in a simple format like foo<-bar<-baz"""
    printed_chains = set()
    
    def get_chain(branch, chain=None):
        if chain is None:
            chain = []
        chain.append(branch)
        
        # Find children
        children = [child for child, parent in immediate_parent.items() if parent == branch]
        
        if not children:
            return [chain]
        
        all_chains = []
        for child in children:
            all_chains.extend(get_chain(child, chain.copy()))
        
        return all_chains
    
    for root in sorted(roots):
        chains = get_chain(root)
        for chain in chains:
            if len(chain) > 1:  # Only show chains with at least 2 branches
                chain_str = "<-".join(chain)
                if chain_str not in printed_chains:
                    print(chain_str)
                    printed_chains.add(chain_str)

def main():
    import argparse
    
    parser = argparse.ArgumentParser(description='Show branch subset relationships as a tree')
    parser.add_argument('--simple', action='store_true', 
                       help='Print simple chains like foo<-bar<-baz instead of tree')
    parser.add_argument('--debug', action='store_true',
                       help='Show debug information about relationships found')
    parser.add_argument('--include-local', action='store_true',
                       help='Include local branches in the analysis')
    parser.add_argument('--remote-only', action='store_true',
                       help='Only show relationships between remote branches (filters output)')
    args = parser.parse_args()
    
    print("Analyzing branch subset relationships...")
    print("=" * 50)
    
    branches = get_branches(include_local=args.include_local)
    
    if not branches:
        print("No branches found.")
        return
    
    if args.debug:
        print(f"\nFound {len(branches)} branches:")
        for b in sorted(branches):
            print(f"  {b}")
        print()
    
    # Build hierarchy but also get all relationships for debug
    all_relationships = defaultdict(set)
    print("Finding all subset relationships (this may take a while)...")
    checked = 0
    found = 0
    for i, branch1 in enumerate(branches):
        if i % 5 == 0:
            print(f"  Checked {checked} pairs, found {found} relationships...")
        for branch2 in branches:
            checked += 1
            if branch1 != branch2 and is_subset(branch1, branch2):
                all_relationships[branch2].add(branch1)
                found += 1
    print(f"  Checked {checked} pairs, found {found} relationships.")
    print()
    
    roots, immediate_parent = build_hierarchy(branches)
    
    if args.debug:
        print("\nAll subset relationships (child <- parent):")
        if all_relationships:
            for parent in sorted(all_relationships.keys()):
                children = sorted(all_relationships[parent])
                print(f"  {parent} contains:")
                for child in children:
                    print(f"    - {child}")
        else:
            print("  None")
        
        print("\nImmediate parent relationships (for tree building):")
        if immediate_parent:
            for child, parent in sorted(immediate_parent.items()):
                print(f"  {child} <- {parent}")
        else:
            print("  None")
        print()
    
    # Print arrow-based relationships
    print("Branch subset relationships (subset <- superset):")
    print()
    
    if all_relationships:
        # Build chains by finding transitive relationships
        # For each branch, find the complete chain from smallest to largest
        
        # First, find all branches involved in relationships
        all_involved = set()
        for parent, children in all_relationships.items():
            all_involved.add(parent)
            all_involved.update(children)
        
        # Remove circular relationships (identical branches)
        filtered_relationships = {}
        for parent, children in all_relationships.items():
            filtered_children = set()
            for child in children:
                if child not in all_relationships or parent not in all_relationships[child]:
                    filtered_children.add(child)
            if filtered_children:
                filtered_relationships[parent] = filtered_children
        
        if not filtered_relationships:
            print("No subset relationships found (only identical branches)")
            print()
            print("=" * 50)
            return
        
        # Build chains: for each leaf node, trace back to all roots
        def find_chains_from_leaf(leaf, relationships):
            """Find all chains starting from a leaf node going up to roots"""
            # Find all parents of this leaf
            parents = [p for p, children in relationships.items() if leaf in children]
            
            if not parents:
                # This is a root
                return [[leaf]]
            
            # Recursively build chains through each parent
            all_chains = []
            for parent in parents:
                parent_chains = find_chains_from_leaf(parent, relationships)
                for chain in parent_chains:
                    all_chains.append([leaf] + chain)
            
            return all_chains
        
        # Find leaf nodes (branches that are not parents of anything)
        all_parents = set(filtered_relationships.keys())
        all_children = set()
        for children in filtered_relationships.values():
            all_children.update(children)
        
        leaves = all_children - all_parents
        
        # Generate all chains
        all_chains = []
        for leaf in sorted(leaves):
            chains = find_chains_from_leaf(leaf, filtered_relationships)
            all_chains.extend(chains)
        
        # For each unique (start, end) pair, keep only the longest chain
        chain_by_endpoints = {}
        for chain in all_chains:
            key = (chain[0], chain[-1])  # (leaf, root)
            if key not in chain_by_endpoints or len(chain) > len(chain_by_endpoints[key]):
                chain_by_endpoints[key] = chain
        
        # Print chains
        printed_chains = set()
        
        for chain in sorted(chain_by_endpoints.values(), key=lambda x: (x[0], len(x), x)):
            chain_str = " <- ".join(chain)
            if chain_str not in printed_chains:
                print(chain_str)
                printed_chains.add(chain_str)
        
        # Print isolated supersets (branches that contain others but aren't contained)
        roots_only = all_parents - all_children
        for root in sorted(roots_only):
            # Check if this root is already part of a printed chain
            already_printed = any(root in chain_str for chain_str in printed_chains)
            if not already_printed and root in filtered_relationships:
                # Print the root and its direct children only
                for child in sorted(filtered_relationships[root]):
                    chain_str = f"{child} <- {root}"
                    if chain_str not in printed_chains:
                        print(chain_str)
                        printed_chains.add(chain_str)
    else:
        print("No subset relationships found")
    
    print()
    print("=" * 50)
    return
    
    if not roots and not immediate_parent:
        print("\nNo subset relationships found.")
        print("All branches have unique commits.")
        return

if __name__ == '__main__':
    main()