equal-tree-merges as way to make rebases fast-forward-able

The itch this idea is supposed to scratch is the problem that a rebase
or a amended commit is no longer a fast-forward, so cannot be easily
pulled.
While this is not a problem in most workflows, as one can either merge
or keep everything private and rebase until published, it would be nice
to have a way for cases in between, where both a clean presentable
commit order is to be maintained and people (or yourself from different
repositories) should be able to easily upgrade to newer versions without
an error-prone not-fast-forward.

My idea to solve this is combining both histories, the rebased/revised
history and the actualy history, marking with some "equal-tree-merge"
the point where they have the same result.
The following mails show some patches to implement this by means of
a merge where all parents have the same tree and some special casing
when encountering such a thing. This has the advantage that older git
version will just see strange merges and may present both histories,
but otherwise just work.

Example 1:

Let's assume you maintain such a regularily-rebased branch that you
want to be able to publish (or pull from other repositories for example
on your laptop):

o=m=o=o=master
   \
    a=b=c=d=e=feature

with this patch you can do "git rebase -eqt master" and get:

              a'=b'=c'=d'=e'=feature'=eqt
             /                       /
o=m=o=o=master--------              /
   \                  \            /
    a=b=c=d=e=feature--merge-------

i.e: the new feature branch has both histories:
  - "feature'" where everything is cleanly rebased and in a form where
               format-patch is suitable to send it upstream
  - "merge" which is both a descendant from feature (so one can see what
    changed since that time and can just pull when one had had cloned feature)

Example 2:

Let's assume you have a feature branch like

o=master
   \
    a=b=c=d=e=f

Assume you just commited "f" which fixes a bug introduced by "b".
Now you of course do not want to send it that way upstream (as it will
make reviewing harder, may force people bisecting to skip some versions
every time they hit this region and so on), so you want to
bisect -i and squash "f" into "b".

o=master
   \
    a=b+f=c'=d'=e'

But if you had already cloned at state "d" to your laptop (or made a backup
of that branch at some server, or published it for use of some collegues)
it will not be a fast-forward, so you have to be very carefull to not
accidentially lose a commit that is already there.

So with this patches you can do "git rebase -i --eqt" and squash f into b
and get:

o=master
   \
    a=b=c=d=e=f---
     \            \
      b+f=c'=d'=e'=eqt

which means that you can just pull from your laptop and get the new head
as fast-forward, but still have a proper history ready for submitting.

The only downsize of this approach is that an unpatched/old git of course
does not know about that it can just choose one of both histories but think
it has to look at both, so git-format-patch will return patches multiple times
and git-rebase will also try to apply both branches, which the patched version
no longer does, only showing the 'presentable' in this case.

Those patches are a bit rough and mostly intended to show how it could work
and to allow experimenting with it. I think the biggest thing still missing
(apart from documentation, error handling, better commit messages) is making
git bisect take advantage of this and only looking at the nice branch.

Bernhard R. Link (7):
  add new command git equal-tree-marker
  add option to only visit the first parent of a equal tree merge
  format-patch defaults to --first-equal-tree-only
  support equal tree merges in interactive rebase
  make rebase -m equal tree marker aware
  add support for creating equal tree markers after rebase
  add support for creating equal tree markers to rebase -i

 .gitignore                 |    1 +
 Makefile                   |    1 +
 builtin-log.c              |    1 +
 git-equal-tree-marker.sh   |   50 ++++++++++++++++++++++++++++++++++++++
 git-rebase--interactive.sh |   33 +++++++++++++++++++++++++
 git-rebase.sh              |   35 ++++++++++++++++++++++++--
 revision.c                 |   57 +++++++++++++++++++++++++++++++++++++-------
 revision.h                 |    1 +
 8 files changed, 167 insertions(+), 12 deletions(-)
 create mode 100644 git-equal-tree-marker.sh

Hochachtungsvoll,
	Bernhard R. Link
-- 
"Never contain programs so few bugs, as when no debugging tools are available!"
	Niklaus Wirth

This adds a new commit denoting tha current branch has the same
tree as another branch, thus allowing fast-forward from the named
commits to this one.

TODO: manpage, rewrite as builtin once the semantics are accepted?
---
 .gitignore               |    1 +
 Makefile                 |    1 +
 git-equal-tree-marker.sh |   50 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 52 insertions(+), 0 deletions(-)
 create mode 100644 git-equal-tree-marker.sh

diff --git a/.gitignore b/.gitignore
index ac02a58..248d146 100644
--- a/.gitignore
+++ b/.gitignore

@@ -39,6 +39,7 @@
 /git-difftool
 /git-difftool--helper
 /git-describe
+/git-equal-tree-marker
 /git-fast-export
 /git-fast-import
 /git-fetch

diff --git a/Makefile b/Makefile
index 4dba10e..913d4c4 100644
--- a/Makefile
+++ b/Makefile

@@ -336,6 +336,7 @@ TEST_PROGRAMS =
 SCRIPT_SH += git-am.sh
 SCRIPT_SH += git-bisect.sh
 SCRIPT_SH += git-difftool--helper.sh
+SCRIPT_SH += git-equal-tree-marker.sh
 SCRIPT_SH += git-filter-branch.sh
 SCRIPT_SH += git-lost-found.sh
 SCRIPT_SH += git-merge-octopus.sh

diff --git a/git-equal-tree-marker.sh b/git-equal-tree-marker.sh
new file mode 100644
index 0000000..403cc56
--- /dev/null
+++ b/git-equal-tree-marker.sh

@@ -0,0 +1,50 @@
+#!/bin/sh
+#
+# Copyright (c) 2009 Bernhard R. Link
+#
+# Create a new commit making HEAD parent of the arguments,
+# which must be commits with the same tree.
+
+set -e
+
+USAGE='<head>...'
+LONG_USAGE='Make current HEAD parent of the given heads (which need to have the same tree).'
+SUBDIRECTORY_OK=Yes
+OPTIONS_SPEC=
+. git-sh-setup
+cd_to_toplevel
+
+# is there really no function for this?
+tree_of_commit() {
+	git cat-file commit "$1" | grep '^tree ' | head -n 1 | sed -e 's/^tree //'
+}
+
+head="$(git rev-parse --verify HEAD)"
+htree="$(tree_of_commit $head)"
+parents=""
+while test $# -gt 0
+do
+	case "$1" in
+	-h|--h|--he|--hel|--help)
+		usage
+		;;
+	*)
+		h="$(git rev-parse --verify $1)"
+		tree="$(tree_of_commit "$h")"
+		if test "x${htree}" != "x${tree}" ; then
+			echo "Tree of $h is not the same as tree of $head" >&2
+			exit 1
+		fi
+		parents="$parents -p $h"
+		;;
+	esac
+	shift
+done
+
+if test "x$parents" = "x" ; then
+	echo "Not enough arguments!" >&2
+	exit 1
+fi
+
+new_commit="$(echo "Equal tree marker" | git commit-tree "$tree" -p "$head" $parents)"
+git-update-ref HEAD "$new_commit"

-- 
1.6.6.rc0.82.g60a15.dirty

rev_info gets a new flag first_equal_tree_only that causes
revision walks to ignore all but the first parent of equal tree
merges.
The default is off and there are options --first-equal-tree-only
and --all-equal-trees to switch it on/off respectively.

TODO:
 - manpage updates
 - check interaction with some of the other options
---
 revision.c |   57 ++++++++++++++++++++++++++++++++++++++++++++++++---------
 revision.h |    1 +
 2 files changed, 49 insertions(+), 9 deletions(-)

diff --git a/revision.c b/revision.c
index a8a3c3a..fb019d6 100644
--- a/revision.c
+++ b/revision.c

@@ -452,6 +452,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 	struct commit_list *parent = commit->parents;
 	unsigned left_flag;
 	struct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;
+	int first_parent_only;
 
 	if (commit->object.flags & ADDED)
 		return 0;

@@ -499,6 +500,21 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 
 	left_flag = (commit->object.flags & SYMMETRIC_LEFT);
 
+	if (revs->first_parent_only)
+		first_parent_only = 1;
+	else if (revs->first_equal_tree_only && commit->parents) {
+		for (parent = commit->parents; parent; parent = parent->next) {
+			struct commit *p = parent->item;
+
+			if (parse_commit(p) < 0)
+				return -1;
+			if (p->tree != commit->tree)
+				break;
+		}
+		first_parent_only = !parent;
+	} else
+		first_parent_only = 0;
+
 	for (parent = commit->parents; parent; parent = parent->next) {
 		struct commit *p = parent->item;
 

@@ -511,7 +527,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			p->object.flags |= SEEN;
 			insert_by_date_cached(p, list, cached_base, cache_ptr);
 		}
-		if (revs->first_parent_only)
+		if (first_parent_only)
 			break;
 	}
 	return 0;

@@ -1067,6 +1083,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 		revs->min_age = approxidate(arg + 8);
 	} else if (!strcmp(arg, "--first-parent")) {
 		revs->first_parent_only = 1;
+	} else if (!strcmp(arg, "--first-equal-tree-only")) {
+		revs->first_equal_tree_only = 1;
+	} else if (!strcmp(arg, "--all-equal-trees")) {
+		revs->first_equal_tree_only = 0;
 	} else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) {
 		init_reflog_walk(&revs->reflog_info);
 	} else if (!strcmp(arg, "--default")) {

@@ -1912,6 +1932,16 @@ static void create_boundary_commit_list(struct rev_info *revs)
 	sort_in_topological_order(&revs->commits, revs->lifo);
 }
 
+static inline void add_boundary_commit(struct rev_info *revs, struct commit *c) {
+	struct object *p = &c->object;
+
+	if (p->flags & (CHILD_SHOWN | SHOWN))
+		return;
+	p->flags |= CHILD_SHOWN;
+	gc_boundary(&revs->boundary_commits);
+	add_object_array(p, NULL, &revs->boundary_commits);
+}
+
 static struct commit *get_revision_internal(struct rev_info *revs)
 {
 	struct commit *c = NULL;

@@ -1987,16 +2017,25 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 	 * 'c', we need to mark its parents that they could be boundaries.
 	 */
 
-	for (l = c->parents; l; l = l->next) {
-		struct object *p;
-		p = &(l->item->object);
-		if (p->flags & (CHILD_SHOWN | SHOWN))
-			continue;
-		p->flags |= CHILD_SHOWN;
-		gc_boundary(&revs->boundary_commits);
-		add_object_array(p, NULL, &revs->boundary_commits);
+	if (revs->first_equal_tree_only && c->parents) {
+		for (l = c->parents; l; l = l->next) {
+			struct commit *p = l->item;
+			parse_commit(p);
+			if (c->tree != p->tree)
+				break;
+		}
+		/* if all parents have the same tree as this node,
+		 * it's an equal tree merge, so ignore all but the
+		 * first parent */
+		if (!l) {
+			add_boundary_commit(revs, c->parents->item);
+			return c;
+		}
 	}
 
+	for (l = c->parents; l; l = l->next) {
+		add_boundary_commit(revs, l->item);
+	}
 	return c;
 }
 

diff --git a/revision.h b/revision.h
index d368003..7ac263c 100644
--- a/revision.h
+++ b/revision.h

@@ -64,6 +64,7 @@ struct rev_info {
 			reverse_output_stage:1,
 			cherry_pick:1,
 			bisect:1,
+			first_equal_tree_only:1,
 			first_parent_only:1;
 
 	/* Diff flags */

TODO: manpage update to hint to --all-equal-trees?
---
 builtin-log.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/builtin-log.c b/builtin-log.c
index 33fa6ea..a3a2d3f 100644
--- a/builtin-log.c
+++ b/builtin-log.c

@@ -960,6 +960,7 @@ int cmd_format_patch(int argc, const char **argv, const char *prefix)
 	rev.diff = 1;
 	rev.combine_merges = 0;
 	rev.ignore_merges = 1;
+	rev.first_equal_tree_only = 1;
 	DIFF_OPT_SET(&rev.diffopt, RECURSIVE);
 
 	rev.subject_prefix = fmt_patch_subject_prefix;

---
 git-rebase--interactive.sh |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 0bd3bf7..3da9f3e 100755
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh

@@ -703,6 +703,7 @@ first and then run 'git rebase --continue' again."
 		fi
 		git rev-list $MERGES_OPTION --pretty=oneline --abbrev-commit \
 			--abbrev=7 --reverse --left-right --topo-order \
+			--first-equal-tree-only \
 			$REVISIONS | \
 			sed -n "s/^>//p" | while read shortsha1 rest
 		do

---
 git-rebase.sh |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/git-rebase.sh b/git-rebase.sh
index b121f45..391f6d6 100755
--- a/git-rebase.sh
+++ b/git-rebase.sh

@@ -539,7 +539,7 @@ echo "$head_name" > "$dotest/head-name"
 echo "$GIT_QUIET" > "$dotest/quiet"
 
 msgnum=0
-for cmt in `git rev-list --reverse --no-merges "$revisions"`
+for cmt in `git rev-list --reverse --first-equal-tree-only --no-merges "$revisions"`
 do
 	msgnum=$(($msgnum + 1))
 	echo "$cmt" > "$dotest/cmt.$msgnum"

With the new --eqt option, git rebase adds an equal tree marker,
so that the old branch can be fast-forwarded to the new one.
If the trees are not equal, a fake merge of the new base and the
old branch is created first.

TODO:
 - manpage update,
 - should --eqt have a better (longer more descriptive) name?
 - the commit message of the merge should have a better default
   and presented to the user for editing
---
 git-rebase.sh |   33 +++++++++++++++++++++++++++++++--
 1 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/git-rebase.sh b/git-rebase.sh
index 391f6d6..681c97b 100755
--- a/git-rebase.sh
+++ b/git-rebase.sh

@@ -50,6 +50,7 @@ diffstat=$(git config --bool rebase.stat)
 git_am_opt=
 rebase_root=
 force_rebase=
+equal_tree_marker=
 
 continue_merge () {
 	test -n "$prev_head" || die "prev_head must be defined"

@@ -132,11 +133,30 @@ call_merge () {
 	esac
 }
 
+# is there really no already existing function for this?
+tree_of_commit() {
+        git cat-file commit "$1" | grep '^tree ' | head -n 1 | sed -e 's/^tree //'
+}
+
 move_to_original_branch () {
 	test -z "$head_name" &&
 		head_name="$(cat "$dotest"/head-name)" &&
 		onto="$(cat "$dotest"/onto)" &&
-		orig_head="$(cat "$dotest"/orig-head)"
+		orig_head="$(cat "$dotest"/orig-head)" &&
+		equal_tree_marker="$(cat "$dotest"/eqt)"
+	if test t = "$equal_tree_marker" ; then
+		# first apply all the changes to the old branch
+		old_tree=$(tree_of_commit "$orig_head")
+		new_tree=$(tree_of_commit HEAD)
+		if test "$old_tree" = "$new_tree" ; then
+			old_branch="$orig_head"
+		else
+			# TODO: better commit message
+			old_branch=$(echo "rebase $head_name onto $onto" | git-commit-tree $new_tree -p "$orig_head" -p "$onto" )
+		fi
+		# then say the old branch can be upgraded to the new one:
+		git equal-tree-marker "$old_branch"
+	fi
 	case "$head_name" in
 	refs/*)
 		message="rebase finished: $head_name onto $onto"

@@ -220,6 +240,7 @@ do
 			end=$(cat "$dotest/end")
 			msgnum=$(cat "$dotest/msgnum")
 			onto=$(cat "$dotest/onto")
+			equal_tree_marker=$(cat "$dotest/eqt")
 			GIT_QUIET=$(cat "$dotest/quiet")
 			continue_merge
 			while test "$msgnum" -le "$end"

@@ -234,6 +255,7 @@ do
 		onto=$(cat "$GIT_DIR"/rebase-apply/onto) &&
 		orig_head=$(cat "$GIT_DIR"/rebase-apply/orig-head) &&
 		GIT_QUIET=$(cat "$GIT_DIR"/rebase-apply/quiet)
+		equal_tree_marker=$(cat "$GIT_DIR"/rebase-apply/eqt)
 		git am --resolved --3way --resolvemsg="$RESOLVEMSG" &&
 		move_to_original_branch
 		exit

@@ -251,6 +273,7 @@ do
 			msgnum=$(cat "$dotest/msgnum")
 			msgnum=$(($msgnum + 1))
 			onto=$(cat "$dotest/onto")
+			equal_tree_marker=$(cat "$dotest/eqt")
 			GIT_QUIET=$(cat "$dotest/quiet")
 			while test "$msgnum" -le "$end"
 			do

@@ -264,6 +287,7 @@ do
 		onto=$(cat "$GIT_DIR"/rebase-apply/onto) &&
 		orig_head=$(cat "$GIT_DIR"/rebase-apply/orig-head) &&
 		GIT_QUIET=$(cat "$GIT_DIR"/rebase-apply/quiet)
+		equal_tree_marker=$(cat "$GIT_DIR"/rebase-apply/eqt)
 		git am -3 --skip --resolvemsg="$RESOLVEMSG" &&
 		move_to_original_branch
 		exit

@@ -340,6 +364,9 @@ do
 		git_am_opt="$git_am_opt $1"
 		force_rebase=t
 		;;
+	--eqt)
+		equal_tree_marker=t
+		;;
 	-C*)
 		git_am_opt="$git_am_opt $1"
 		;;

@@ -522,7 +549,8 @@ then
 		echo $head_name > "$GIT_DIR"/rebase-apply/head-name &&
 		echo $onto > "$GIT_DIR"/rebase-apply/onto &&
 		echo $orig_head > "$GIT_DIR"/rebase-apply/orig-head &&
-		echo "$GIT_QUIET" > "$GIT_DIR"/rebase-apply/quiet
+		echo "$GIT_QUIET" > "$GIT_DIR"/rebase-apply/quiet &&
+		echo "$equal_tree_marker" > "$GIT_DIR"/rebase-apply/eqt
 	exit $ret
 fi
 

@@ -537,6 +565,7 @@ echo "$prev_head" > "$dotest/prev_head"
 echo "$orig_head" > "$dotest/orig-head"
 echo "$head_name" > "$dotest/head-name"
 echo "$GIT_QUIET" > "$dotest/quiet"
+echo "$equal_tree_marker" > "$dotest/eqt"
 
 msgnum=0
 for cmt in `git rev-list --reverse --first-equal-tree-only --no-merges "$revisions"`

With the new --eqt option, git rebase -i adds an equal tree marker,
so that the old branch can be fast-forwarded to the new one.
If the trees are not equal, a fake merge of the new base and
the old branch is created first.

TODO:
- manpage update,
- should --eqt have a better (longer more descriptive) name?
- the commit message of the merge should have a better default
  and presented to the user for editing
---
 git-rebase--interactive.sh |   32 ++++++++++++++++++++++++++++++++
 1 files changed, 32 insertions(+), 0 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 3da9f3e..51cc5fa 100755
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh

@@ -20,6 +20,7 @@ v,verbose          display a diffstat of what changed upstream
 onto=              rebase onto given branch instead of upstream
 p,preserve-merges  try to recreate merges instead of ignoring them
 s,strategy=        use the given merge strategy
+eqt                create an equal tree marker to allow f-f from old tree
 m,merge            always used (no-op)
 i,interactive      always used (no-op)
  Actions:

@@ -46,6 +47,7 @@ ONTO=
 VERBOSE=
 OK_TO_SKIP_PRE_REBASE=
 REBASE_ROOT=
+EQUAL_TREE_MARKER=
 
 GIT_CHERRY_PICK_HELP="  After resolving the conflicts,
 mark the corrected paths with 'git add <paths>', and

@@ -325,6 +327,11 @@ peek_next_command () {
 	sed -n "1s/ .*$//p" < "$TODO"
 }
 
+# is there really no already existing function for this?
+tree_of_commit() {
+	git cat-file commit "$1" | grep '^tree ' | head -n 1 | sed -e 's/^tree //'
+}
+
 do_next () {
 	rm -f "$DOTEST"/message "$DOTEST"/author-script \
 		"$DOTEST"/amend || exit

@@ -426,6 +433,25 @@ do_next () {
 	esac
 	test -s "$TODO" && return
 
+	if test t = "$(cat "$DOTEST/eqt")" ; then
+		HEADNAME=$(cat "$DOTEST"/head-name)
+		OLDHEAD=$(cat "$DOTEST"/head)
+		ONTO=$(cat "$DOTEST"/onto)
+		NEWHEAD=$(git rev-parse HEAD)
+		OLDTREE=$(tree_of_commit "$OLDHEAD")
+		NEWTREE=$(tree_of_commit HEAD)
+		if test "$NEWTREE" = "$OLDTREE" ; then
+			OLDBRANCH="$OLDHEAD"
+		else
+			echo "Creating commit with differences of '$OLDHEAD' now that is applied to '$ONTO' (tree $NEWTREE)"
+			OLDBRANCH="$( (grep '^# Rebase' "$TODO".full \
+				; grep -v '^#' "$TODO".full ) \
+				| git-commit-tree "$NEWTREE" \
+				-p "$OLDHEAD" -p "$ONTO")"
+		fi
+		git equal-tree-marker "$OLDBRANCH"
+	fi
+
 	comment_for_reflog finish &&
 	HEADNAME=$(cat "$DOTEST"/head-name) &&
 	OLDHEAD=$(cat "$DOTEST"/head) &&

@@ -605,6 +631,9 @@ first and then run 'git rebase --continue' again."
 		ONTO=$(git rev-parse --verify "$1") ||
 			die "Does not point to a valid commit: $1"
 		;;
+	--eqt)
+		EQUAL_TREE_MARKER=t
+		;;
 	--)
 		shift
 		test -z "$REBASE_ROOT" -a $# -ge 1 -a $# -le 2 ||

@@ -656,6 +685,7 @@ first and then run 'git rebase --continue' again."
 			: >"$DOTEST"/rebase-root ;;
 		esac
 		echo $ONTO > "$DOTEST"/onto
+		echo "$EQUAL_TREE_MARKER" > "$DOTEST"/eqt
 		test -z "$STRATEGY" || echo "$STRATEGY" > "$DOTEST"/strategy
 		test t = "$VERBOSE" && : > "$DOTEST"/verbose
 		if test t = "$PRESERVE_MERGES"

@@ -787,6 +817,8 @@ EOF
 
 		test -d "$REWRITTEN" || skip_unnecessary_picks
 
+		cp "$TODO" "$TODO".full
+
 		git update-ref ORIG_HEAD $HEAD
 		output git checkout $ONTO && do_rest
 		;;

Heya,

On Mon, Nov 30, 2009 at 15:43, Bernhard R. Link [off-list ref] wrote:

Those patches are a bit rough and mostly intended to show how it could work
and to allow experimenting with it.

Given the experimental nature of your patches it would probably have
been appropriate to mark them "RFC" (request for comment). You can do
so by running: `git format-patch --subject-prefix="RFC PATCH"` instead
of "git format-patch".

-- 
Cheers,

Sverre Rabbelier

On 11/30/2009 03:43 PM, Bernhard R. Link wrote:

The itch this idea is supposed to scratch is the problem that a rebase
or a amended commit is no longer a fast-forward, so cannot be easily
pulled.

How does this compare with topgit?

Paolo

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43:

The itch this idea is supposed to scratch is the problem that a rebase
or a amended commit is no longer a fast-forward, so cannot be easily
pulled.

Do you mean pushed?
For pull, the state of the branch on the receiving side play a role, of
course.

While this is not a problem in most workflows, as one can either merge
or keep everything private and rebase until published, it would be nice
to have a way for cases in between, where both a clean presentable
commit order is to be maintained and people (or yourself from different
repositories) should be able to easily upgrade to newer versions without
an error-prone not-fast-forward.

My idea to solve this is combining both histories, the rebased/revised
history and the actualy history, marking with some "equal-tree-merge"
the point where they have the same result.
The following mails show some patches to implement this by means of
a merge where all parents have the same tree and some special casing
when encountering such a thing. This has the advantage that older git
version will just see strange merges and may present both histories,
but otherwise just work.

Without having the time to go through the detailed setup you described
below (sorry), I'm wondering how this differs from what Git calls a
trivial merge? Is it merely about asserting that you merge coinciding
(heads with) trees?

Michael

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43:

You mean there should be something really simple, such as:

git rev-parse "$1"^{tree}

Michael

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43:
[...]

Ok, I couldn't resist looking at your examples. Actually, before
anything else: Thanking for describing *what* you want to achieve, not
only how.

Example 1:

Let's assume you maintain such a regularily-rebased branch that you
want to be able to publish (or pull from other repositories for example
on your laptop):

o=m=o=o=master
   \
    a=b=c=d=e=feature

with this patch you can do "git rebase -eqt master" and get:

              a'=b'=c'=d'=e'=feature'=eqt
             /                       /
o=m=o=o=master--------              /
   \                  \            /
    a=b=c=d=e=feature--merge-------

git checkout -b featureprime feature
git rebase master
git merge feature # should be trivial
git branch -M featureprime feature

i.e: the new feature branch has both histories:
  - "feature'" where everything is cleanly rebased and in a form where
               format-patch is suitable to send it upstream
  - "merge" which is both a descendant from feature (so one can see what
    changed since that time and can just pull when one had had cloned feature)

Example 2:

Let's assume you have a feature branch like

o=master
   \
    a=b=c=d=e=f

Assume you just commited "f" which fixes a bug introduced by "b".
Now you of course do not want to send it that way upstream (as it will
make reviewing harder, may force people bisecting to skip some versions
every time they hit this region and so on), so you want to
bisect -i and squash "f" into "b".

o=master
   \
    a=b+f=c'=d'=e'

But if you had already cloned at state "d" to your laptop (or made a backup
of that branch at some server, or published it for use of some collegues)
it will not be a fast-forward, so you have to be very carefull to not
accidentially lose a commit that is already there.

So with this patches you can do "git rebase -i --eqt" and squash f into b
and get:

o=master
   \
    a=b=c=d=e=f---
     \            \
      b+f=c'=d'=e'=eqt

which means that you can just pull from your laptop and get the new head
as fast-forward, but still have a proper history ready for submitting.

If that side branch is named "feature":
git checkout -b fixup feature
git rebase -i a # squash f into b; creates b+f c# d' e'
git merge feature # should be trivial
git branch -M fixup feature

You can also go crazy with rebase --onto here, or use cherry-pick
repeatedly.

Note that I always use a temporary branch for rewriting, before renaming
it to the proper branch name. I haven't checked, but I assume the
"first-parents" are the way you want them (you want log --first-parent
--no-merges to show the rewritten commits, right?); otherwise you would
have to do the merges the other way round.

Cheers,
Michael

* Paolo Bonzini [off-list ref] [091130 16:32]:

On 11/30/2009 03:43 PM, Bernhard R. Link wrote:

quoted

The itch this idea is supposed to scratch is the problem that a rebase
or a amended commit is no longer a fast-forward, so cannot be easily
pulled.

How does this compare with topgit?

It's not easily compareable as having different aims, but I think there
are some use-cases where this allows native usage of git where
previously the best bet was topgit.

Assume for example you want to maintain a set of patches of some
upstream, which you want to have in some form relative to upstream
and in patches easily reviewable and pickable by other people.

You could do that with topgit by making each change a topgit branch.
But to clone that repository then you would need topgit to get all
the information and cherry picking one of your changes (that perhaps
grow with the time, was adapted to new upstreams and had bugs fixed)
needs telling topgit to combine the changes of that branch and use that
instead of a simple cherry pick.

With this equal-tree-marker you can just do a git rebase --eqt or git
rebase -i --eqt and both have a history with your changes as single
commits which are easy to look at (and you can just pushing head^1
somewhere for upstream to pull from) while still having all the history
in your git archive so someone else can look what actually happened or
just clone your current head and repeatenly pull from it.

Hochachtungsvoll,
	Bernhard R. Link

* Michael J Gruber [off-list ref] [091130 17:00]:

Bernhard R. Link venit, vidit, dixit 30.11.2009 15:43:

quoted

o=m=o=o=master
   \
    a=b=c=d=e=feature

with this patch you can do "git rebase -eqt master" and get:

git checkout -b featureprime feature
git rebase master
git merge feature # should be trivial
git branch -M featureprime feature

[...]

Note that I always use a temporary branch for rewriting, before renaming
it to the proper branch name. I haven't checked, but I assume the
"first-parents" are the way you want them (you want log --first-parent
--no-merges to show the rewritten commits, right?); otherwise you would
have to do the merges the other way round.

My problem with that is that --first-parent-only makes no difference
between this and other merges.

Assume the example2

o=master
   \
    a=b=c=d=e=f---
     \            \
      b+f=c'=d'=e'=eqt

would continue with some paralel commits and a merge:

o=master
   \
    a=b=c=d=e=f---       y
     \            \     / \
      b+f=c'=d'=e'=eqt-x   m
                        \ /
                         z

now if you rebase that tree (or want to send it with format-patch),
you either get the old commits multiple times in format-patch
(and possibly causing already resolved conflicts when doing the am
step in rebase), or you use --first-parent-only and might miss z.

Thus the idea to have some way to destinguish this merge from a normal
merge and thus the extra pseudo-merge in example 1 to get the following
merge to merge things with equal tree.

Hochachtungsvoll,
	Bernhard R. Link
-- 
"Never contain programs so few bugs, as when no debugging tools are available!"
	Niklaus Wirth

Hi,

On Mon, 30 Nov 2009, Bernhard R. Link wrote:

The itch this idea is supposed to scratch is the problem that a rebase 
or a amended commit is no longer a fast-forward, so cannot be easily 
pulled.

Actually, I did something like this without any new tool:

	git rebase origin/master
	git merge -s ours master@{1}

The effect is that there is a merge commit which really merges the old 
state.

OTOH I can see that there is merit in trying to avoid to _require_ the 
whole history of the rebased branch.  But then, would it not be more in 
line with Git's ideas if there was a tool trying to identify, say, 
from the commit message which commits in HEAD...MERGE_HEAD are 
supposed to be identical?

Ciao,
Dscho

Bernhard R. Link wrote:

Example 1:

Let's assume you maintain such a regularily-rebased branch that you
want to be able to publish (or pull from other repositories for example
on your laptop):

o=m=o=o=master
   \
    a=b=c=d=e=feature

with this patch you can do "git rebase -eqt master" and get:

              a'=b'=c'=d'=e'=feature'=eqt
             /                       /
o=m=o=o=master--------              /
   \                  \            /
    a=b=c=d=e=feature--merge-------

Actually, there is more information that can be retained about this
rebase operation.  Your scheme records the fact that (a+b+c+d+e+merge)
== (o+o+a'+b'+c'+d'+e'), which is certainly true.  But in the process of
rebasing, the user has (implicitly or explicitly) resolved conflicts in
transforming each of the patches a -> a', b -> b', etc.  In fact, the
patch a' is itself a merge between a and master; b' is a merge between b
and a'; etc.  If you record each of these merges individually, the
result looks like this:

o=m=o=o=master
   \      \
    \      a'=b'=c'=d'=e'=feature'
     \    /  /  /  /  /
      ---a==b==c==d==e==feature

There are advantages to retaining all of this history:

* It faithfully represents intermediate steps of the rebase.

* There is no need for special "merge" and "eqt" merge commits affecting
an arbitrary group of feature patches; each of the rebased patches is
treated identically.

* There is a direct ancestry connection from the "new version" to the
"old version" of each patch; for example, it is easy to see that c' is a
new version of c and to compute the corresponding interdiffs.

* There are situations where the additional info can help git choose
better merge bases in the case of merge/rebases across three or more
repositories.  For example, somebody who is developing a subfeature
based on the feature branch can merge/rebase changes from both feature
and master without causing utter chaos.

The "historical" version of the feature branch should be omitted from
most git output as you have suggested, but this would be best
implemented by marking the "historical" ancestor with some extra flag in
each merge commit.

Example 2:

Let's assume you have a feature branch like

o=master
   \
    a=b=c=d=e=f

Assume you just commited "f" which fixes a bug introduced by "b". [...]

So with this patches you can do "git rebase -i --eqt" and squash f into b
and get:

o=master
   \
    a=b=c=d=e=f---
     \            \
      b+f=c'=d'=e'=eqt

This case can also record additional information:

o=master
   \
    a=b===c==d=e=f
       \   \  \   \
        b+f=c'=d'==e'

Here the new DAG cannot represent *all* ancestry information (namely,
that b+f, c', and d' also include the original patch f), but it does
accurately reflect useful information such as that c' includes c and
that e' includes e and f.

I wrote some blog entries about rebasing-with-history that might be
interesting [1-3].

Michael

[1]
http://softwareswirl.blogspot.com/2009/04/truce-in-merge-vs-rebase-war.html
[2]
http://softwareswirl.blogspot.com/2009/08/upstream-rebase-just-works-if-history.html
[3]
http://softwareswirl.blogspot.com/2009/08/rebase-with-history-implementation.html