git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 0/2] A new merge algorithm, take 3

From
Junio C Hamano <junkio@cox.net>
Date
Sep 8, 2005, 20:54 UTC
Message-ID
<7v4q8vuvom.fsf@assigned-by-dhcp.cox.net>
In-Reply-To
<7v1x407min.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano <junkio@cox.net> writes:
Show 13 quoted lines
> ... I'd like to leave what
> merge strategy to use as an user option, and leave the door open
> for other merge strategies to emerge later.  I know Pasky wants
> to look into pcdv merge and other alternatives.
>
> This is still off-the-top-of-my-head, but the top-level merge
> entry point for the end user would be just:
>
>     git merge <head> <remote> <merge-message>
>
> and by default 'git-merge-script' (sorry, I am taking over the
> name of your script for this 'generic driver for underlying
> merge strategy scripts') would do something like:

And here is "an illustration of concept" patch, requesting for comments. It probably is buggy as h*ll, but I am showing interfaces early, hoping this is something people can agree on to use to plug various merge strategies into.

The patch uses 'git-show-branches --merge-base' as an improved 'git-merge-base -a' that can do more than two heads, which still only exists in my development repository, but I hope you get the idea.

------------
Subject: [PATCH] Multi-backend merge driver.
This is just an illustration of concept patch.

The new command 'git merge' takes the current head and one or more remote heads, with the commit log message for the automated case.

If the heads being merged are simple fast-forwards, it acts the same way as the current 'git resolve'. Otherwise, it tries different merge strategies and takes the result from the one that succeeded auto-merging, if there is any.

If no merge strategy succeeds auto-merging, their results are evaluated for number of paths needed for hand resolving, and the one with the least number of such paths is left in the working tree. The user is asked to resolve them by hand and make a commit manually.

The calling convention from the 'git merge' driver to merge strategy programs is very simple:

 - A strategy program is to be called 'git-merge-<strategy>'.
 - They take input of this form:
	<common1> <common2> ... '--' <head> <remote1> <remote2>...
   That is, one or more the common ancestors, double dash, the
   current head, and one or more remote heads being merged into
   the current branch.
 - Before a strategy program is called, the working tree is
   matched to the current <head>.
 - The strategy program exits with status code 0 when it
   successfully auto-merges the given heads.  It should do
   update-cache for all the merged paths when it does so -- the
   index file will be used to record the merge result as a
   commit by the driver.
 - The strategy program exits with status code 1 when it leaves
   conflicts behind.  It should do update-cache for all the
   merged paths that it successfully auto-merged, and leave the
   cache entry in the index file as the same as <head> for paths
   it could not auto-merge, and leave its best-effort result
   with conflict markers in the working tree when it does so.
 - The strategy program exists with status code other than 0 or
   1 if it does not handle the given merge at all.

As examples, this commit comes with merge strategies based on 'git resolve' and 'git octopus'.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
 git-commit.sh        |    2 
 git-merge-octopus.sh |   86 +++++++++++++++++++++
 git-merge-resolve.sh |   80 ++++++++++++++++++++
 git-merge.sh         |  205 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 372 insertions(+), 1 deletions(-)
 create mode 100755 git-merge-octopus.sh
 create mode 100755 git-merge-resolve.sh
 create mode 100755 git-merge.sh
a65a614ce7f67c3ed4dee3bed3ab4d86d3f79577
diff --git a/git-commit.sh b/git-commit.sh
--- a/git-commit.sh
+++ b/git-commit.sh
@@ -158,7 +158,7 @@ if [ ! -r "$GIT_DIR/HEAD" ]; then
 	PARENTS=""
 else
 	if [ -f "$GIT_DIR/MERGE_HEAD" ]; then
-		PARENTS="-p HEAD -p MERGE_HEAD"
+		PARENTS="-p HEAD "`sed -e 's/^/-p /' "$GIT_DIR/MERGE_HEAD"`
 	fi
 	if test "$use_commit" != ""
 	then
diff --git a/git-merge-octopus.sh b/git-merge-octopus.sh
new file mode 100755
--- /dev/null
+++ b/git-merge-octopus.sh
@@ -0,0 +1,86 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Junio C Hamano
+#
+# Resolve two or more trees.
+#
+
+# The first parameters up to -- are merge bases; the rest are heads.
+bases= head= remotes= sep_seen=
+for arg
+do
+	case ",$sep_seen,$head,$arg," in
+	*,--,)
+		sep_seen=yes
+		;;
+	,yes,,*)
+		head=$arg
+		;;
+	,yes,*)
+		remotes="$remotes$arg "
+		;;
+	*)
+		bases="$bases$arg "
+		;;
+	esac
+done
+
+# Reject if this is not an Octopus -- resolve should be used instead.
+case "$remotes" in
+?*' '?*)
+	;;
+*)
+	exit 2 ;;
+esac
+
+# MRC is the current "merge reference commit"
+# MRT is the current "merge result tree"
+
+MRC=$head MSG= PARENT="-p $head"
+MRT=$(git-write-tree)
+CNT=1 ;# counting our head
+NON_FF_MERGE=0
+for SHA1 in $remotes
+do
+	common=$(git-merge-base $MRC $SHA1) ||
+		die "Unable to find common commit with $SHA1"
+
+	if test "$common" = $SHA1
+	then
+		echo "Already up-to-date with $SHA1"
+		continue
+	fi
+
+	CNT=`expr $CNT + 1`
+	PARENT="$PARENT -p $SHA1"
+
+	if test "$common,$NON_FF_MERGE" = "$MRC,0"
+	then
+		# The first head being merged was a fast-forward.
+		# Advance MRC to the head being merged, and use that
+		# tree as the intermediate result of the merge.
+		# We still need to count this as part of the parent set.
+
+		echo "Fast forwarding to: $SHA1"
+		git-read-tree -u -m $head $SHA1 || exit
+		MRC=$SHA1 MRT=$(git-write-tree)
+		continue
+	fi
+
+	NON_FF_MERGE=1
+
+	echo "Trying simple merge with $SHA1"
+	git-read-tree -u -m $common $MRT $SHA1 || exit 2
+	next=$(git-write-tree 2>/dev/null)
+	if test $? -ne 0
+	then
+		echo "Simple merge did not work, trying automatic merge."
+		git-merge-index -o git-merge-one-file -a ||
+		exit 2 ; # Automatic merge failed; should not be doing Octopus
+		next=$(git-write-tree 2>/dev/null)
+	fi
+	MRC=$common
+	MRT=$next
+done
+
+exit 0
diff --git a/git-merge-resolve.sh b/git-merge-resolve.sh
new file mode 100755
--- /dev/null
+++ b/git-merge-resolve.sh
@@ -0,0 +1,80 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Linus Torvalds
+#
+# Resolve two trees.
+
+# The first parameters up to -- are merge bases; the rest are heads.
+bases= head= remotes= sep_seen=
+for arg
+do
+	case ",$sep_seen,$head,$arg," in
+	*,--,)
+		sep_seen=yes
+		;;
+	,yes,,*)
+		head=$arg
+		;;
+	,yes,*)
+		remotes="$remotes$arg "
+		;;
+	*)
+		bases="$bases$arg "
+		;;
+	esac
+done
+
+# Give up if we are given more than two remotes -- not handling octopus.
+case "$remotes" in
+?*' '?*)
+	exit 2 ;;
+esac
+
+# Find an optimum merge base if there are more than one candidates.
+case "$bases" in
+?*' '?*)
+	echo "Trying to find the optimum merge base."
+	G=.tmp-index$$
+	best=
+	best_cnt=-1
+	for c in $bases
+	do
+		rm -f $G
+		GIT_INDEX_FILE=$G git-read-tree -m $c $head $remotes \
+			 2>/dev/null ||	continue
+		# Count the paths that are unmerged.
+		cnt=`GIT_INDEX_FILE=$G git-ls-files --unmerged | wc -l`
+		if test $best_cnt -le 0 -o $cnt -le $best_cnt
+		then
+			best=$c
+			best_cnt=$cnt
+			if test "$best_cnt" -eq 0
+			then
+				# Cannot do any better than all trivial merge.
+				break
+			fi
+		fi
+	done
+	rm -f $G
+	common="$best"
+	;;
+*)
+	common="$bases"
+	;;
+esac
+
+git-update-index --refresh 2>/dev/null
+git-read-tree -u -m $common $head $remotes || exit 2
+echo "Trying simple merge."
+if result_tree=$(git-write-tree  2>/dev/null)
+then
+	exit 0
+else
+	echo "Simple merge failed, trying Automatic merge."
+	if git-merge-index -o git-merge-one-file -a
+	then
+		exit 0
+	else
+		exit 1
+	fi
+fi
diff --git a/git-merge.sh b/git-merge.sh
new file mode 100755
--- /dev/null
+++ b/git-merge.sh
@@ -0,0 +1,205 @@
+#!/bin/sh
+#
+# Copyright (c) 2005 Junio C Hamano
+#
+
+. git-sh-setup || die "Not a git archive"
+
+LF='
+'
+
+usage () {
+    die "git-merge [-n] [-s <strategy>]... <merge-message> <head> <remote>+"
+}
+
+# all_strategies='resolve barkarow fredrik octopus'
+
+all_strategies='resolve octopus'
+default_strategies='resolve octopus'
+use_strategies=
+
+dropheads() {
+	rm -f -- "$GIT_DIR/MERGE_HEAD" || exit 1
+}
+
+summary() {
+	case "$no_summary" in
+	'')
+		git-diff-tree -p -M $head "$1" |
+		git-apply --stat --summary
+		;;
+	esac
+}
+
+while case "$#" in 0) break ;; esac
+do
+	case "$1" in
+	-n|--n|--no|--no-|--no-s|--no-su|--no-sum|--no-summ|\
+		--no-summa|--no-summar|--no-summary)
+		no_summary=t ;;
+	-s=*|--s=*|--st=*|--str=*|--stra=*|--strat=*|--strate=*|\
+		--strateg=*|--strategy=*|\
+	-s|--s|--st|--str|--stra|--strat|--strate|--strateg|--strategy)
+		case "$#,$1" in
+		*,*=*)
+			strategy=`expr "$1" : '-[^=]*=\(.*\)'` ;;
+		0,*)
+			usage ;;
+		*)
+			strategy="$2"
+			shift ;;
+		esac
+		case " $all_strategies " in
+		*" $strategy "*)
+			use_strategies="$use_strategies$strategy " ;;
+		*)
+			die "available strategies are: $all_strategies" ;;
+		esac
+		;;
+	-*)	usage ;;
+	*)	break ;;
+	esac
+	shift
+done
+
+case "$use_strategies" in
+'')
+	use_strategies=$default_strategies
+	;;
+esac
+test "$#" -le 2 && usage ;# we need at least two heads.
+
+merge_msg="$1"
+shift
+head=$(git-rev-parse --verify "$1"^0) || usage
+shift
+
+# All the rest are remote heads
+for remote
+do
+	git-rev-parse --verify "$remote'^0 >/dev/null ||
+	    die "$remote - not something we can merge"
+done
+
+common=$(git-show-branch --merge-base $head "$@")
+echo "$head" >"$GIT_DIR/ORIG_HEAD"
+
+case "$#,$common" in
+*,'')
+	die "Unable to find common commit between $head and $*"
+	;;
+1,"$1")
+	# If head can reach all the merge then we are up to date.
+	# but first the most common case of merging one remote
+	echo "Already up-to-date. Yeeah!"
+	dropheads
+	exit 0
+	;;
+1,"$head")
+	# Again the most common case of merging one remote.
+	echo "Updating from $head to $1."
+	git-update-index --refresh 2>/dev/null
+	git-read-tree -u -m $head "$1" || exit 1
+	echo "$1" > "$GIT_DIR/HEAD"
+	summary "$1"
+	dropheads
+	exit 0
+	;;
+1,*)
+	# We are not doing octopus and not fast forward.  Need a
+	# real merge.
+	;;
+*)
+	# An octopus.  If we can reach all the remote we are up to date.
+	up_to_date=t
+	for remote
+	do
+		common_one=$(git-merge-base $head $remote)
+		if test "$common_one" != "$remote"
+		then
+			up_to_date=f
+			break
+		fi
+	done
+	if test "$up_to_date" = t
+	then
+		echo "Already up-to-date. Yeeah!"
+		dropheads
+		exit 0
+	fi
+	;;
+esac
+
+# At this point we need a real merge.  Require that the tree matches
+# exactly our head.
+
+git-update-index --refresh &&
+test '' = `git-diff-index --cache --name-only $head` || {
+	die "Need real merge but the working tree has local changes."
+}
+
+result_tree= best_cnt=-1 best_strategy= wt_strategy=
+for strategy in $use_strategies
+do
+    test "$wt_strategy" = '' || git reset --hard $head
+
+    echo "Trying merge strategy $strategy..."
+    wt_strategy=$strategy
+    git-merge-$strategy $common -- $head "$@" || {
+
+	# The backend exits with 1 when conflicts are left to be resolved,
+	# with 2 when it does not handle the given merge at all.
+
+	case "$?" in
+	1)
+	    cnt=`git-diff-files --name-only | wc -l`
+	    if test $best_cnt -le 0 -o $cnt -le $best_cnt
+	    then
+		best_strategy=$strategy
+		best_cnt=$cnt
+	    fi
+	esac
+	continue
+    }
+
+    # Automerge succeeded.
+    result_tree=$(git-write-tree) && break
+done
+
+# If we have a resulting tree, that means the strategy module
+# auto resolved the merge cleanly.
+if test '' != $result_tree
+then
+    parents="-p $head"
+    for remote
+    do
+        parents="$parents -p $remote"
+    done
+    result_commit=$(echo "$merge_msg" | git-commit-tree $result_tree $parents)
+    echo "Committed merge $result_commit, made by $wt_strategy."
+    echo $result_commit >"$GIT_DIR"/HEAD
+    summary $result_commit
+    dropheads
+    exit 0
+fi
+
+# Pick the result from the best strategy and have the user fix it up.
+case "$best_strategy" in
+'')
+	git reset --hard $head
+	die "No merge strategy handled the merge."
+	;;
+"$wt_strategy")
+	# We already have its result in the working tree.
+	;;
+*)
+	echo "Using the $strategy to prepare resolving by hand."
+	git reset --hard $head
+	git-merge-$best_strategy $common -- $head "$@"
+	;;
+esac
+for remote
+do
+	echo $remote
+done >"$GIT_DIR/MERGE_HEAD"
+die "Automatic merge failed; fix up by hand"
Previous: Junio C HamanoNext: A Large Angry SCM
Message 22 of 40 in “A new merge algorithm, take 3”
  1. 0/2 A new merge algorithm, take 3Fredrik Kuivinen, Sep 7, 2005
  2. 1/2 Add '-i' flag to read-tree to make it ignore whats in the working directory.Fredrik Kuivinen, Sep 7, 2005
  3. Unified merge driver pushed out to "master" branchJunio C Hamano, Sep 11, 2005
  4. Fredrik KuivinenSep 11, 2005
  5. Junio C HamanoSep 12, 2005
  6. Another merge test case from the kernel tree.Junio C Hamano, Sep 14, 2005
  7. Daniel BarkalowSep 14, 2005
  8. Junio C HamanoSep 14, 2005
  9. Fredrik KuivinenSep 14, 2005
  10. Junio C HamanoSep 14, 2005
  11. Yet another set of merge test cases from the kernel tree.Junio C Hamano, Sep 15, 2005
  12. Fredrik KuivinenSep 19, 2005
  13. Junio C HamanoSep 20, 2005
  14. Fredrik KuivinenSep 20, 2005
  15. 2/2 A new merge algorithmFredrik Kuivinen, Sep 7, 2005
  16. Daniel BarkalowSep 7, 2005
  17. Fredrik KuivinenSep 8, 2005
  18. Daniel BarkalowSep 8, 2005
  19. Fredrik KuivinenSep 8, 2005
  20. Daniel BarkalowSep 8, 2005
  21. Junio C HamanoSep 7, 2005
  22. Junio C HamanoSep 8, 2005
  23. A Large Angry SCMSep 8, 2005
  24. Chuck LeverSep 8, 2005
  25. Junio C HamanoSep 8, 2005
  26. Linus TorvaldsSep 8, 2005
  27. Junio C HamanoSep 8, 2005
  28. Chuck LeverSep 8, 2005
  29. Linus TorvaldsSep 8, 2005
  30. Chuck LeverSep 8, 2005
  31. Linus TorvaldsSep 8, 2005
  32. [RFH] Merge driverJunio C Hamano, Sep 9, 2005
  33. Daniel BarkalowSep 9, 2005
  34. Junio C HamanoSep 9, 2005
  35. Daniel BarkalowSep 9, 2005
  36. [RFH] Merge driverJunio C Hamano, Sep 11, 2005
  37. Fredrik KuivinenSep 12, 2005
  38. Junio C HamanoSep 12, 2005
  39. Fredrik KuivinenSep 13, 2005
  40. Junio C HamanoSep 13, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.