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

Question

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:

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

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

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