[RFC] git-brebase

[Alejandro Colomar <alx@kernel.org>]

[-- Attachment #1: Type: text/plain, Size: 11404 bytes --]

Hi!

I've significantly improved the idea from the original thread, thanks to
suggestions from several people (the most fundamental, by Nico Williams
and Ben Boeckel), and inspired to write it after knowing about the tool
written by Nico Williams and Viktor Dukhovni (but I implemented it from
scratch, without reading their implementation, other than looking at the
file size --which, being under 100 LoC, gave me the confidence that it
could be implemented easily--).

I believe now, after several improvements, it is not only simpler than
git-imerge, but also more powerful.

I've not used git-imerge, but I've watched the youtube video of the talk
in which the author explains how it works (and it's quite nice, to be
fair).  First some similarities between both:

-  Both git-imerge and my tool support --first-parent (per the README of
   git-imerge).  My tool has support for this by using git-bisect(1)
   interally for the bisection.

   This feature was suggested to me by Ben Boeckel.

-  Both git-imerge and my tool reach the same tip after a successful
   session.  They differ in the intermediate history.

Below goes an overview of key limitations of the git-imerge approach
(IMO), and which are not present in mine.  If git-imerge supports any of
this, I'm sorry; I didn't find them in their README.

-  git-imerge creates a 2D matrix of conflict resolutions.  This is nice
   for the case of two flat branches.  However, the branch to be rebased
   might also contain merge commits.  This is less common than having
   merge commits in the target branch, but it happens, and in those
   cases, it's frequent to want to keep the structure of the branch,
   with --rebase-merges.  My tool has support for this by using
   git-rebase(1) internally for the rebases.

-  One may want to skip arbitrary commits (because they're known to be
   broken, and possibly immediately reverted).  For that, I've provided
   a specific flag, --pre-exec, which is similar to git-rebase(1)'s
   --exec, but which is executed before each rebase operation, at the
   BISECT_HEAD commit.  An exit code of 125 skips that revision
   immediately, without trying to do any rebases.

   This feature was suggested to me by Ben Boeckel.

-  One may also want to find and resolve semantic conflicts that do not
   appear as physical text conflicts.  For that, I've provided a
   specific flag, --post-exec, which is similar to --pre-exec, but runs
   after each successful git-rebase(1) operation.  This would usually
   build and test the software itself.

   This feature was suggested to me by Ben Boeckel.

-  git-imerge is limited when rebasing trees of branches.  Let's
   consider something more complex:

	*---*---*---*---*---M
	 \
	  *---*---A---*---B
	   \ /     \
	    *       *---C---D

   Let's say M is master, to which we want to rebase the tree composed
   of branches A, B, and C, so that it results in this:

	*---*---*---*---*---M
	                     \
	                      *---*---A'--*---B'
	                       \ /     \
	                        *       *---C'--D'

   With my tool, this becomes trivial (I've been doing this all day
   earlier today, resolving in a few hours what would have taken me
   days).  The approach in this case would be to rebase from root to
   leaves, but to solve conlicts from leaves to root:

	1)  Use git-brebase to rebase A until the first conflict with M.

	2)  Abort the conflicting rebase.  We don't want to resolve the
	    conflict yet, or we'd have to repeat the same resolution
	    later.

	3)  Rebase all its direct descendants into the new A, by
	    performing operations 1 and 2 but with the descendant
	    branches.  Do this recursively with children of children.

	4)  Once all descendants have been moved below the new A, it's
	    time to solve the conflicts in A.  This will result in
	    advancing A by just one commit of M, since we had aborted
	    exactly at the conflicting rebase.

	5)  Rebase the direct descendants on top of the new A, this time
	    with git-rebase(1) --not brebase!-- with --interactive,
	    dropping all commits that exist in A.  This avoids resolving
	    the same conflicts again.  Do this recursively with children
	    of children.

	6)  Rinse and repeat since step 1, until everything is
	    successful.  At that point, we have reached the end of the
	    session.

   This approach is different from git-imerge, in that git-imerge
   manages in a single session the entire rebase operation until
   success, while my tool performs each conflict resolution in a single
   step, and they are entirely independent, and can be interrupted to do
   other work.  My tool requires repeated invocations until reaching the
   end point, denoted by a successful exit status.

Something that git-imerge has that my tool hasn't is the ability to do
merge commits.  My tool exclusively does rebases.  However, once the end
commit is reached, creating that could be used to produce a merge
commit.  It could be done by first reaching the rebase tip in a
disposable branch, then perform a regular merge commit with
git-merge(1), and resolve conflicts by doing something like
	$ git checkout disposable -- .
and then finish the merge.  It's not a critical limitation of my tool,
IMO.  (Although, admittedly, it's a trick that not everyone would know
to do.)

Another difference is that, by doing rebases, my tool doesn't remember
the entire history matrix that git-imerge holds while doing the work.
I see this as an advantage, as once we've finished one conflict step,
and we've verified with git-range-diff(1) and with proper testing that
it's correct, the extra history would clutter the
'git log --graph --oneline HEAD target current' (something essential
when doing these operations).  Having a lean history in the process
helps get it right, being able to check important commits in the log.

Now about details of the implementaion:

-  The tool supports --first-parent, and passes it transparently to
   git-bisect(1).

-  The tool supports the flags --pre-exec and --post-exec, which are
   interpreted especially by the tool.

-  The tool accepts other flags, and passes them transparently to
   git-rebase(1).  If some flag isn't supported by git-rebase(1), it
   will be that program which will complain.  Also, I haven't made an
   attempt to validate that the flags passed make sense with this tool
   (for example, passing --abort would be accepted by git-rebase(1), but
    it wouldn't make sense, and would probably fail at some point).

   It would be good to curate a list of flags that make sense.

-  My tool, being a simple shell script with rudimentary option parsing,
   only accepts flags that take a single shell argument.  That is,
   --foo=bar is ok, but --foo bar is not okay (and will probably result
   in parsing errors).

-  The tool is meant to be used almost as a drop-in of git-rebase(1).
   It does the same thing, except that instead of rebasing on the
   target, it rebases on the first commit of the target branch which
   has conflicts.

(It has grown a bit fatter than it was, but it's still way below
 git-imerge.)

	$ wc -l <src/bin/git-brebase 
	164

We'll discuss the exact way it should be integrated within git(1), but
first it'd be interesting to get feedback about the tool itself,
regardless of the actual form.  Actually, because of the specialized
flags --pre-exec and --post-exec, and the --first-parent flag from
git-bisect(1) --and the fact that it runs git-bisect(1) machinery--, I'm
not entirely sure that it should be just a new flag to git-rebase(1).
It might be confusing to have these three flags being dependent on
another flag, and not being able to use this within a git-bisect(1)
session, unlike other git-rebase(1) operations.  That might call for
a new git command.

Please let me know any feedback!  :)

Junio, since you seemed to love git-imerge, I wonder what you'll think
of this tool.  :-)

Having presented the tool, below goes the implementation.


Have a lovely day!
Alex

---
#!/bin/bash
# Copyright 2026, Alejandro Colomar <alx@kernel.org>
# SPDX-License-Identifier: GPL-3.0-or-later

set -Eeufo pipefail;
shopt -s lastpipe;

err()
{
	>&2 printf '%s\n' "$(basename "$0"): error: $*";
	exit 1;
}

fp='';
other='';
pre='';
post='';
while test $# -ge 1; do
	case "$1" in
	--first-parent)
		fp='--first-parent';
		;;
	--pre-exec=*)
		echo "$1" \
		| sed 's/--pre-exec=//' \
		| read -r pre;
		;;
	--post-exec=*)
		echo "$1" \
		| sed 's/--post-exec=//' \
		| read -r post;
		;;
	-*)
		other="$other $1";
		;;
	*)
		break;
		;;
	esac;
	shift;
done;
gbopts="$fp";
gropts="$other";

if test $# -lt 1; then
	err 'Missing target commit.';
fi;
if test $# -gt 1; then
	err 'Too many arguments.';
fi;
git rev-list -1 "$1" \
| read -r tgt;
git rev-parse --abbrev-ref HEAD \
| read -r branch;

# Set up the callback script for 'git rebase run'.
mktemp \
| read -r callback;
cat >"$callback" <<__EOF__
#!/bin/bash

	set -Eeufo pipefail;
	shopt -s lastpipe;

	git rev-list -1 HEAD \
	| read -r bisect_head;

	if test -n '$pre'; then
		printf '%s' 'Pre-rebase exec: ';
		pre='$pre';
		if
			\$pre;
			x="\$?";
			true;
		then
			case "\$x" in
			0)
				echo 'success';
				;;
			125)
				echo 'skip';
				git checkout --detach "\$bisect_head" 2>/dev/null;
				exit 125;
				;;
			*)
				echo "failure (\$x)";
				git checkout --detach "\$bisect_head" 2>/dev/null;
				exit "\$x";
				;;
			esac;
		fi;
	fi;

	git switch '$branch' >/dev/null 2>/dev/null;
	git rev-list -1 HEAD \
	| read -r old_head;
	printf '%s' 'Rebase: ';
	if git rebase $gropts "\$bisect_head" >/dev/null 2>/dev/null; then
		echo 'success';
	else
		echo 'conflict';
		git rebase --abort >/dev/null;
		git checkout --detach "\$bisect_head" 2>/dev/null;
		exit 1;
	fi;

	if test -n '$post'; then
		printf '%s' 'Post-rebase exec: ';
		post='$post';
		if
			\$post;
			x="\$?";
			true;
		then
			case "\$x" in
			0)
				echo 'success';
				;;
			125)
				echo 'skip';
				git reset --hard "\$old_head";
				git checkout --detach "\$bisect_head" 2>/dev/null;
				exit 125;
				;;
			*)
				echo "failure (\$x)";
				git reset --hard "\$old_head";
				git checkout --detach "\$bisect_head" 2>/dev/null;
				exit "\$x";
				;;
			esac;
		fi;
	fi;
	git checkout --detach "\$bisect_head" 2>/dev/null;
	exit 0;
__EOF__
chmod +x "$callback";

# Try the target first.
git checkout --detach "$tgt" 2>/dev/null;
if "$callback"; then
	exit 0;
fi;
git status;

# Bisect.
# shellcheck disable=SC2248  # gbopts may hold multiple options
git bisect start $gbopts >/dev/null;
git bisect bad "$tgt" >/dev/null;
git merge-base "$branch" "$tgt" \
| xargs -I{} git bisect good {};
git bisect run "$callback";
git rev-list -1 bisect/bad \
| read -r bad;
git bisect reset >/dev/null 2>/dev/null;

# Perform the conflicting rebase
git switch "$branch";
# shellcheck disable=SC2086  # gropts may hold multiple options
git rebase $gropts "$bad";
if test -v post; then
	echo 'Running post-rebase exec.';
	$post;
fi;


-- 
<https://www.alejandro-colomar.es>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]