Rebasing a tree (a commit/branch and all its children)

This is my current git tree:

A - H (master)
|
\- B - C - D - E (feature)
           |
           \- F (new)
           |
           \- G (other)

And I’d like to rebase the side branch so that it depends on H rather than A:

  • Nested git repositories without submodules?
  • Jenkins not playing nice with a private GitHub repository (Windows)
  • How do I stop XCode 4 from modifying a local Git repository?
  • Git workflow for different versions of a framework
  • Git hook: add a new file to repo if a new branch is created
  • What are the downsides to rebasing topic branches instead of merging?
  • A - H (master)
        |
        \- B'- C'- D'- E'(feature)
                   |
                   \- F'(new)
                   |
                   \- G'(other)
    

    Easy concept, hard to do automatically, it seems. This has already been asked here and here, but the proposed solutions are not working for me.

    First, as pointed out in the former, the git branch output is not trivial to parse when the current branch is there (there is a * prepended). But that’s not a stopper, in my case I can easily provide the names feature, new and other by hand, or make sure the current branch is master.

    Then I tried with these commands:

    git rebase --committer-date-is-author-date --preserve-merges --onto master feature^ feature
    git rebase --committer-date-is-author-date --preserve-merges --onto master feature^ new
    git rebase --committer-date-is-author-date --preserve-merges --onto master feature^ other
    

    and I end up with:

    A - H (master)
        |
        \- E'(feature)
        |
        \- B' - C' - D' - F'(new)
        |
        \- B" - C" - D" - G'(other)
    

    Definitely not what I want! Or, if I use B^ instead of feature^, then I also get the B - C - D history in the feature branch.

    So, any further suggestion on how to get this done more or less automatically?

    EDIT: It sort of works with this:

    git checkout feature
    git merge other
    git merge new
    git rebase -p master feature
    

    Now at least the tree looks correct, I just have to move the branch heads to their right commits before the merges… which could be done with:

    git checkout master
    git branch -f new feature^2
    git branch -f feature feature^1
    git branch -f other feature^2
    git branch -f feature feature^1
    

  • What is the difference between git push origin HEAD and git push origin ?
  • multiple commands are not working in git post-receive
  • 'git add .' doesn't work
  • Writing a reliable data store in GoLang
  • Is it possible to add/commit a file to the index of a local bare Git repo?
  • How do I stop git bisect?
  • 4 Solutions collect form web for “Rebasing a tree (a commit/branch and all its children)”

    Ah, I didn’t spot that your commands were based on the accepted answer to your first linked question. In any case, you quite explicitly asked for what you got: each of E, F and G rebased onto master.

    I think what you wanted was:

    git rebase ... --onto master A feature
    

    to change from

    A - H (master)
    |
    \- B - C - D - E (feature)
    

    to

    A - H (master)
        |
        \- B'- C'- D'- E'(feature)
    

    (master is the new root, A is the old root. Using feature^ as the old root means you only transplanted the last commit of feature, as you saw)

    And then:

    git rebase ... --onto D' D new
    git rebase ... --onto D' D other
    

    to detach new and other from D, and transplant them onto D’. Note that after you’ve rebased feature, feature^ means D' and not D.


    As for automating the process, I can show you something that sort of works, but the tricky part is error handling and recovery.

    transplant_tree.sh

    #!/bin/bash
    trap "rm -f /tmp/$$.*" EXIT
    
    function transplant() # <from> <to> <branch>
    {
        OLD_TRUNK=$1
        NEW_TRUNK=$2
        BRANCH=$3
    
        # 1. get branch revisions
        REV_FILE="/tmp/$$.rev-list.$BRANCH"
        git rev-list $BRANCH ^$OLD_TRUNK > "$REV_FILE" || exit $?
        OLD_BRANCH_FORK=$(tail -1 "$REV_FILE")
        OLD_BRANCH_HEAD=$(head -1 "$REV_FILE")
        COMMON_ANCESTOR="${OLD_BRANCH_FORK}^"
    
        # 2. transplant this branch
        git rebase --onto $NEW_TRUNK $COMMON_ANCESTOR $BRANCH
    
        # 3. find other sub-branches:
        git branch --contains $OLD_BRANCH_FORK | while read sub;
        do
            # 4. figure out where the sub-branch diverges,
            # relative to the (old) branch head
            DISTANCE=$(git rev-list $OLD_BRANCH_HEAD ^$sub | wc -l)
    
            # 5. transplant sub-branch from old branch to new branch, attaching at
            # same number of commits before new HEAD
            transplant $OLD_BRANCH_HEAD ${BRANCH}~$DISTANCE  $sub
        done
    }
    
    transplant $1 $2 $3
    

    for your use, transplant_tree.sh master master feature should work, assuming all the rebases succeed. It would look something like:

    • OLD_TRUNK=NEW_TRUNK=master, BRANCH=feature
      1. get branch revisions
        • OLD_BRANCH_FORK=B
        • OLD_BRANCH_HEAD=E
        • COMMON_ANCESTOR=B^ ==A
      2. transplant this branch
        • git rebase --onto master B^ feature
      3. find other sub-branches
        • sub=new
          • DISTANCE=$(git rev-list E ^new | wc -l) == 1
          • recurse with OLD_TRUNK=E, NEW_TRUNK=feature~1, BRANCH=new
        • sub=other
          • etc.

    If one of the rebases fails, should it let you fix it manually and somehow resume? Should it be able to roll the whole thing back?

    This is my first attempt at using “plumbing” commands, so feel free to suggest improvements.

    The two powerful commands you can use here, to figure out how to move this tree, are git for-each-ref and git rev-list:

    • git for-each-ref refs/heads --contains B gives you all (local) refs you’d want to move, that is feature, new, other
    • git rev-list ^B^ feature new other gives you all commits you want to move.

    Now thanks to rebase, we don’t really need to move every commit, only the nodes in your tree that are leaves or forks. Thus those that have zero or 2 (or more) child commits.

    Let us assume, for the sake of consistency with rebase that you give arguments as:
    git transplant-onto H A <list of branches>, then you could use the following (and put it under git-transplant-onto in your path):

    #!/usr/bin/env bash
    
    function usage() {
        echo
        echo "Usage: $0 [-n] [-v] <onto> <from> <ref-list>"
        echo "    Transplants the tree from <from> to <onto>"
        echo "    i.e. performs git rebase --onto <onto> <from> <ref>, for each <ref> in <ref-list>"
        echo "    while maintaining the tree structure inside <ref-list>"
        exit $1
    }
    
    dry_run=0
    verbose=0
    while [[ "${1::1}" == "-" ]]; do
        case $1 in
            -n) dry_run=1 ;;
            -v) verbose=1 ;;
            *) echo Unrecognized option $1; usage -1 ;;
        esac
        shift
    done
    
    # verifications
    if (( $# < 2 )) || ! onto=$(git rev-parse --verify $1) || ! from=$(git rev-parse --verify $2); then usage $#; fi
    git diff-index --quiet HEAD || {echo "Please stash changes before transplanting"; exit 3}
    
    # get refs to move
    shift 2
    if (( $# == 0 )); then
        refs=$(git for-each-ref --format "%(refname)" refs/heads --contains $from)
    else
        refs=$(git show-ref --heads --tags $@ | cut -d' ' -f2)
        if (( $# != $(echo "$refs" | wc -l) )); then echo Some refs passed as arguments were wrong; exit 4; fi
    fi
    
    # confirm
    echo "Following branches will be moved: "$refs
    REPLY=invalid
    while [[ ! $REPLY =~ ^[nNyY]?$ ]]; do read -p "OK? [Y/n]"; done
    if [[ $REPLY =~ [nN] ]]; then exit 2; fi
    
    # only work with non-redundant refs
    independent=$(git merge-base --independent $refs)
    
    if (( verbose )); then
        echo INFO:
        echo independent refs:;git --no-pager show -s --oneline --decorate $independent
        echo redundant refs:;git --no-pager show -s --oneline --decorate $(git show-ref $refs | grep -Fwvf <(echo "$independent") )
    fi
    
    # list all commits, keep those that have 0 or 2+ children
    # so we rebase only forks or leaves in our tree
    tree_nodes=$(git rev-list --topo-order --children ^$from $independent | sed -rn 's/^([0-9a-f]{40})(( [0-9a-f]{40}){2,})?$/\1/p')
    
    # find out ancestry in this node list (taking advantage of topo-order)
    declare -A parents
    for f in $tree_nodes; do
        for p in ${tree_nodes#*$h} $from; do
            if git merge-base --is-ancestor $p $h ; then
                parents[$h]=$p
                break
            fi
        done
        if [[ ${parents[$h]:-unset} = unset ]]; then echo Failed at finding an ancestor for the following commit; git --no-pager show -s --oneline --decorate $h; exit 2; fi
    done
    
    # prepare to rebase, remember mappings
    declare -A map
    map[$from]=$onto
    
    # IMPORTANT! this time go over in chronological order, so when rebasing a node its ancestor will be already moved
    while read h; do
        old_base=${parents[$h]}
        new_base=${map[$old_base]}
        git rebase --preserve-merges --onto $new_base $old_base $h || {
            git rebase --abort
            git for-each-ref --format "%(refname:strip=2)" --contains $old_base refs/heads/ | \
                xargs echo ERROR: Failed a rebase in $old_base..$h, depending branches are:
            exit 1
        }
        map[$h]=$(git rev-parse HEAD)
    done < <(echo "$tree_nodes" | tac)
    
    # from here on, all went well, all branches were rebased.
    # update refs if no dry-run, otherwise show how
    
    ref_dests=
    for ref in $refs; do
        # find current and future hash for each ref we wanted to move
        # all independent tags are in map, maybe by chance some redundant ones as well
        orig=$(git show-ref --heads --tags -s $ref)
        dest=${map[$orig]:-unset}
    
        # otherwise look for a child in the independents, use map[child]~distance as target
        if [[ $dest = unset ]]; then
            for child in $independent; do
                if git merge-base --is-ancestor $ref $child ; then
                    dest=$(git rev-parse ${map[$child]}~$(git rev-list $ref..$child | wc -l) )
                    break
                fi
            done
        fi
    
        # finally update ref
        ref_dests+=" $dest"
        if (( dry_run )); then
            echo git update-ref $ref $dest
        else
            git update-ref $ref $dest
        fi
    done
    
    if (( dry_run )); then
        echo
        echo If you apply the update-refs listed above, the tree will be:
        git show-branch $onto $ref_dests
    else
        echo The tree now is:
        git show-branch $onto $refs
    fi
    

    Another way is to get all individual commits with their parent in an order that you may transpose (say git rev-list --topo-order --reverse --parents) and then use git am on each individual commit.

    I don’t think you should be in position to really want automatism for the case. Rebasing even simple branches normally need fair attention. If done on aged branch and/or more than a handful of commits, chances of just succeeding is very small. And you seem to have a full forest there.

    While if the situation is not really that fuzzy and rebase mostly work, just issuing an interactive rebase command and cutting the todo manually would take just seconds.

    Also from the nature I don’t see a full auto solution.

    But to be constructive, this is how I would try a solution:

    • first create a program that can analyze the source history and gives me tree branches. For the example above it would give B..D on A; E..E on D; F..G on D.
    • mark A’ as H (from extrenal input)
    • Apply the lowest chunk that is based on A: cherry-pick (or rebase onto) B..D to A’;
    • mark the new top as D’
    • apply the remaining chunks for which mapping is already done

    In these cases, a nice trick is to merge (join) all the branches to be
    moved into a final commit node. After that, use rebase with the
    --preserve-merges option for moving the resulting enclosed subtree
    (set of branches).

    Creating a closed subtree that contains all the branches, exposes
    2 nodes (start and end) that are used as input parameters for the rebase
    command.

    The end of the closed subtree is an artificial node that may
    be deleted after moving the tree, as well as the other nodes that
    may have been created for merging other branches.

    Let’s see the following case.

    The developer wants to insert a new commit (master) into
    other 3 development branches (b11, b2, b3). One of these (b11) is
    a merge of a feature branch b12, both based on b1. The other 2
    branches (b2, b3) diverge.

    Of course the developer could cherry-pick that new commit into
    each one of these branches, but the developer may prefer not to
    have the same commit in 3 different branches, but just 1 commit
    before the branches diverge.

    * baa687d (HEAD -> master) new common commit
    | * b507c23 (b11) b11
    | *   41849d9 Merge branch 'b12' into b11
    | |\
    | | * 20459a3 (b12) b12
    | * | 1f74dd9 b11
    | * | 554afac b11
    | * | 67d80ab b11
    | |/
    | * b1cbb4e b11
    | * 18c8802 (b1) b1
    |/
    | * 7b4e404 (b2) b2
    | | * 6ec272b (b3) b3
    | | * c363c43 b2 h
    | |/
    | * eabe01f header
    |/
    * 9b4a890 (mirror/master) initial
    * 887d11b init
    

    For that, the first step is to create a common merge commit that
    includes the 3 branches. For that a temporary branch called pack
    is used.

    Merging into pack may create conflicts, but that is not important
    since these merges will later be discarded. Just instruct git to
    automatically solve them, adding options -s recursive -Xours.

    $ git checkout -b pack b11 # create new branch at 'b11' to avoid losing original refs
    $ git merge -s recursive -Xours b2 # merges b2 into pack
    $ git merge -s recursive -Xours b3 # merges b3 into pack
    

    This is the whole tree after merging everything into the pack branch:

    *   b35a4a7 (HEAD -> pack) Merge branch 'b3' into pack
    |\
    | * 6ec272b (b3) b3
    | * c363c43 b2 h
    * |   60c9b7c Merge branch 'b2' into pack
    |\ \
    | * | 7b4e404 (b2) b2
    | |/
    | * eabe01f header
    * | b507c23 (b11) b11
    * |   41849d9 Merge branch 'b12' into b11
    |\ \
    | * | 20459a3 (b12) b12
    * | | 1f74dd9 b11
    * | | 554afac b11
    * | | 67d80ab b11
    |/ /
    * | b1cbb4e b11
    * | 18c8802 (b1) b1
    |/
    | * baa687d (master) new common commit
    |/
    * 9b4a890 initial
    * 887d11b init
    

    Now it’s time to move the subtree that has been created. For that
    the following command is used:

    $ git rebase --preserve-merges --onto master master^ pack
    

    The reference master^ means the commit before master (master‘s
    parent), 9b4a890 in this case. This commit is NOT rebased, it is
    the origin of the 3 rebased branches. And of course, pack is the final reference of the
    whole subtree.

    There may be some merge conflicts during the rebase. In case there had
    already been conflicts before doing the merge these will arise again. Be
    sure to solve them the same way. For the the artificial commits created
    for merging into the temporary node pack, don’t bother and
    solve them automatically.

    After the rebase, that would be the resulting tree:

    *   95c8d3d (HEAD -> pack) Merge branch 'b3' into pack
    |\
    | * d304281 b3
    | * ed66668 b2 h
    * |   b8756ee Merge branch 'b2' into pack
    |\ \
    | * | 8d82257 b2
    | |/
    | * e133de9 header
    * | f2176e2 b11
    * |   321356e Merge branch 'b12' into b11
    |\ \
    | * | c919951 b12
    * | | 8b3055f b11
    * | | 743fac2 b11
    * | | a14be49 b11
    |/ /
    * | 3fad600 b11
    * | c7d72d6 b1
    |/
    * baa687d (master) new common commit
    |
    * 9b4a890 initial
    * 887d11b init
    

    Sometimes the old branch references may not be relocated (even if
    the tree relocates without them). In that case you can recover
    or change some reference by hand.

    It’s also time to undo the pre-rebase merges that made possible
    rebasing the whole tree. After some delete, reset/checkout, this
    is the tree:

    * f2176e2 (HEAD -> b11) b11
    *   321356e Merge branch 'b12' into b11
    |\
    | * c919951 (b12) b12
    * | 8b3055f b11
    * | 743fac2 b11
    * | a14be49 b11
    |/
    * 3fad600 b11
    * c7d72d6 (b1) b1
    | * d304281 (b3) b3
    | * ed66668 b2 h
    | | * 8d82257 (b2) b2
    | |/
    | * e133de9 header
    |/
    * baa687d (mirror/master, mirror/HEAD, master) new common commit
    * 9b4a890 initial
    * 887d11b init
    

    Which is exactly what the developer wanted to achieve: the commit
    is shared by the 3 branches.

    Git Baby is a git and github fan, let's start git clone.