git - reorder commit on branch as early as possible without a conflict

Question

How would I go about moving a commit up a branch to be as early as possible without any conflicts (without much manual work, eg rebase -i)?

Eg

A-B-C-D-X

should become

A-B-X-C-D

if swapping X with C and D has no conflicts but swapping X with B would result in a conflict.

Thanks.

Answer 1

We really need to go commit by commit in order to find the earliest point where the commit in question and all later commits apply. One way to do this efficiently is to iterate backwards through the list of commits. This seems similar to the idea in CoderBrien's answer.

The (very rough) script below finds this point and prints useful information about it that helps decide if you really want to move the commit that far. Compared to CoderBrien's script, it uses higher-level commands like cherry-pick and revert. The script expects a commit at the command line, if not given, the last commit is used.

To actually move the commit, use git rebase -i . While this could be automated, some control over the process seems actually useful here.

Bubbling down a commit can be achieved simply by doing git rebase -i and trying to move the commit to the end. The rebase process will stop at the latest point of failure, or succeed.

For both cases, just because a commit applies doesn't mean it makes sense. Ideally, each commit would also "pass all tests". The script could be enhanced to cater for that.

The most up to date version is at https://github.com/krlmlr/scriptlets/blob/main/home/bin/git-bubble.

#!/bin/sh

set -ex

top_level=$(git rev-parse --show-toplevel)
# TODO: Does this always exist?
git_dir=${top_level}/.git
tmpdir="${git_dir}/bubble-work"
/bin/rm -rf "$tmpdir"
git clone "$top_level" "$tmpdir"

start_commit=$(git rev-parse HEAD)

if [ -n "$1" ]; then
  my_commit=$1
else
  my_commit=$start_commit
fi

git -C $tmpdir reset --hard ${my_commit}^

# https://stackoverflow.com/a/62397081/946850
# FIXME: Better way to find branch point?
for current_commit in $(git log --format="%H" origin/HEAD..${my_commit}^); do
  git -C $tmpdir revert --no-edit $current_commit
  if ! git -C $tmpdir cherry-pick --no-commit $my_commit; then
    # Show info that helps decide if this is really the right place
    # to move that commit to, and to navigate in the subsequent `git rebase -i`
    git --no-pager show $current_commit
    git --no-pager show $my_commit
    git log --oneline -n 1 $current_commit
    git log --oneline -n 1 $my_commit
    exit 1
  fi
  git -C $tmpdir reset --hard HEAD
done

echo "End reached, can be applied onto the main branch"

Answer 2

Well, this pretty much works but needs some cleanup.

After working with it for a while, I've bumped into another problem which I've posted here.

#!/bin/sh -e

# todo: integrate with git
GIT_DIR=./.git/

commitid=$1

if [ "$1" = "" ]; then
   echo usage: $0 commitid
   exit 1
fi

tmpdir="$GIT_DIR/bubble-work"
/bin/rm -rf "$tmpdir"
mkdir "$tmpdir"

# checkout commit with detached head
git checkout -q $commitid^0 || die "could not detach HEAD"

while [ 1 = 1 ]; do

# todo pipe output to avoid temp files
# see git-rebase.sh

patchfile=`git format-patch -k --full-index --src-prefix=a/ --dst-prefix=b/ --no-renames -o "$tmpdir" HEAD~1`
echo patch = $patchfile

git checkout -q HEAD~2
git am --rebasing "$patchfile" || die "git am failed"
/bin/rm -f "$patchfile"

echo looping
done



/bin/rm -rf "$tmpdir"

Answer 3

Here's a demonstration of what I came up with after 15 minutes of hacking. It's not a complete solution to the posed problem, but it should cut down on the work involved.

The goal is to use git bisect to find the earliest conflict-free merge point for a future commit. The solution takes advantage of the binary search capability inherent in git bisect in order to cut down on the steps.

Unfortunately, this does not preclude later commits from conflicting, so an interactive rebase is required to vet the results (but that's the point, anyway).

The one disadvantage/caveat is that you have to reverse the sense of good and bad in your head when you instruct git about whether the step failed or succeeded when testing the patch.

If any of the steps below are unclear, let me know and I'll try to elaborate.

First create the following file in a series of commits. Each commit should add a series of four identical lines (a's, then b's, then c's, then d's).

a
a
a
a
b
b
b
b
c
c
c
c
d
d
d
d

At this point, git log should output something like:

commit 6f2b809863632a86cc0523df3a4bcca22cf5ab17
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:45:44 2011 -0500

    Added d.

commit 91ba7e6f19db74adb6ce79e7b85ea965788f6b88
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:44:26 2011 -0500

    Added c.

commit f83beee55d6e060536584852ebb55c5ac3b850b2
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:44:00 2011 -0500

    Added b.

commit d6d924b0a30a9720f6e01dcc79dc49097832a587
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:43:38 2011 -0500

    Added a.

commit 74d41121470108642b1a5df087bc837fdf77d31c
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:43:11 2011 -0500

    Initial commit.

Now edit the file, so that it contains the following, and commit this:

a
a
a
a
b
x
x
b
c
x
x
c
d
d
d
d

The log should now include one more commit:

commit 09f247902a9939cb228b580d39ed2622c3211ca6
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:46:36 2011 -0500

    Replaced a few lines with x.

Now generate a patch for the X commit.

git diff -p master~ > x.patch

Crank up bisect -- remember to use git bisect good when the patch fails and git bisect bad when the patch succeeds:

$ git bisect start
$ git bisect good 74d41121470108642b1a5df087bc837fdf77d31c
$ git bisect bad master
Bisecting: 2 revisions left to test after this (roughly 1 step)
[f83beee55d6e060536584852ebb55c5ac3b850b2] Added b.
$ patch --dry-run -p1 < x.patch 
patching file file.txt
Hunk #1 FAILED at 3.
1 out of 1 hunk FAILED -- saving rejects to file file.txt.rej
$ git bisect good
Bisecting: 0 revisions left to test after this (roughly 1 step)
[6f2b809863632a86cc0523df3a4bcca22cf5ab17] Added d.
$ patch --dry-run -p1 < x.patch 
patching file file.txt
$ git bisect bad
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[91ba7e6f19db74adb6ce79e7b85ea965788f6b88] Added c.
$ patch --dry-run -p1 < x.patch 
patching file file.txt
Hunk #1 succeeded at 3 with fuzz 2.
$ git bisect bad
91ba7e6f19db74adb6ce79e7b85ea965788f6b88 is the first bad commit
commit 91ba7e6f19db74adb6ce79e7b85ea965788f6b88
Author: Todd Sundsted <...>
Date:   Tue Dec 20 22:44:26 2011 -0500

    Added c.

$ git bisect reset

As expected, the edits in commit X can be moved immediately after commit C. An interactive rebase confirms this:

91e92489 * Added d.
6c082b1f * Replaced a few lines with x.
a60ae2a9 * Added c.
4d5e78f2 * Added b.
7d2ff759 * Added a.
74d41121 * Initial commit.

Answer 4

Use git rebase -i X~ where X~ is the revision before X.

Then reorder the lines in the rebase log to you're desired order.

More about interactive rebase.