From: Junio C Hamano <junkio@cox.net>
Date: Mon, 9 Apr 2007 06:54:47 +0000 (-0700)
Subject: Merge branch 'jc/push'
X-Git-Tag: v1.5.2-rc0~68
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/5bcbc7ff1014c58e7296713926206bf6a69e0f4c?hp=fd1d1b05e937ff3164be38b111e5d76d592ee548

Merge branch 'jc/push'

* jc/push:
git-push to multiple locations does not stop at the first failure
git-push reports the URL after failing.
---

diff --git a/.gitignore b/.gitignore
index b39f78fcdf..9229e918cd 100644
--- a/.gitignore
+++ b/.gitignore
@@ -77,6 +77,7 @@ git-merge-ours
 git-merge-recursive
 git-merge-resolve
 git-merge-stupid
+git-merge-subtree
 git-mergetool
 git-mktag
 git-mktree
@@ -148,6 +149,7 @@ test-chmtime
 test-date
 test-delta
 test-dump-cache-tree
+test-match-trees
 common-cmds.h
 *.tar.gz
 *.dsc
diff --git a/Documentation/.gitignore b/Documentation/.gitignore
index 6a51331b2f..b98d21e98e 100644
--- a/Documentation/.gitignore
+++ b/Documentation/.gitignore
@@ -2,6 +2,7 @@
 *.html
 *.1
 *.7
+*.made
 howto-index.txt
 doc.dep
 cmds-*.txt
diff --git a/Documentation/RelNotes-1.5.1.1.txt b/Documentation/RelNotes-1.5.1.1.txt
new file mode 100644
index 0000000000..b48b4bc3e8
--- /dev/null
+++ b/Documentation/RelNotes-1.5.1.1.txt
@@ -0,0 +1,46 @@
+GIT v1.5.1.1 Release Notes (draft)
+==========================
+
+Fixes since v1.5.1
+------------------
+
+* Documentation updates
+
+  - The --left-right option of rev-list and friends is documented.
+
+  - The documentation for cvsimport has been majorly improved.
+
+* Bugfixes
+
+  - "git send-email" produced of References header of unbounded length;
+    fixed this with line-folding.
+
+  - "git archive" to download from remote site should not
+    require you to be in a git repository, but it incorrectly
+    did.
+
+  - "git apply" ignored -p<n> for "diff --git" formatted
+    patches.
+
+  - "git rerere" recorded a conflict that had one side empty
+    (the other side adds) incorrectly; this made merging in the
+    other direction fail to use previously recorded resolution.
+
+  - t4200 test was broken where "wc -l" pads its output with
+    spaces.
+
+  - "git branch -m old new" to rename branch did not work
+    without a configuration file in ".git/config".
+
+  - The sample hook for notification e-mail was misnamed.
+
+  - gitweb did not show type-changing patch correctly in the
+    blobdiff view.
+
+* Performance Tweaks
+
+--
+exec >/var/tmp/1
+O=v1.5.1-26-ge94a4f6
+echo O=`git describe refs/heads/maint`
+git shortlog --no-merges $O..refs/heads/maint
diff --git a/Documentation/RelNotes-1.5.2.txt b/Documentation/RelNotes-1.5.2.txt
new file mode 100644
index 0000000000..2e3c7bc4f1
--- /dev/null
+++ b/Documentation/RelNotes-1.5.2.txt
@@ -0,0 +1,76 @@
+GIT v1.5.2 Release Notes (draft)
+========================
+
+Updates since v1.5.1
+--------------------
+
+* New commands and options.
+
+  - "git bisect start" can optionally take a single bad commit and
+    zero or more good commits on the command line.
+
+* Updated behavior of existing commands.
+
+  - "git diff --stat" shows size of preimage and postimage blobs
+    for binary contents.  Earlier it only said "Bin".
+
+  - "git lost-found" shows stuff that are unreachable except
+    from reflogs.
+
+  - "git checkout branch^0" now detaches HEAD at the tip commit
+    on the named branch, instead of just switching to the
+    branch (use "git checkout branch" to switch to the branch,
+    as before).
+
+  - "git bisect next" can be used after giving only a bad commit
+    without giving a good one (this starts bisection half-way to
+    the root commit).  We used to refuse to operate without a
+    good and a bad commit.
+
+* Builds
+
+  - git-p4import has never been installed; now there is an
+    installation option to do so.
+
+  - gitk and git-gui can be configured out.
+
+  - Generated documentation pages automatically get version
+    information from GIT_VERSION
+
+  - Parallel build with "make -j" descending into subdirectory
+    was fixed.
+
+* Performance Tweaks
+
+  - optimized "git-rev-list --bisect" (hence "git-bisect").
+
+  - optimized "git-add $path" in a large directory, most of
+    whose contents are ignored.
+
+
+Fixes since v1.5.1
+------------------
+
+The following are all in v1.5.1.x series, unless otherwise noted.
+
+* Documentation updates
+
+* Bugfixes
+
+  - Switching branches with "git checkout" refused to work when
+    a path changes from a file to a directory between the
+    current branch and the new branch, in order not to lose
+    possible local changes in the directory that is being turned
+    into a file with the switch.  We now allow such a branch
+    switch after making sure that there is no locally modified
+    file nor un-ignored file in the directory.  This has not
+    been backported to 1.5.1.x series, as it is rather an
+    intrusive change.
+
+* Performance Tweaks
+
+--
+exec >/var/tmp/1
+O=v1.5.1-91-g640ee0d
+echo O=`git describe refs/heads/master`
+git shortlog --no-merges $O..refs/heads/master ^refs/heads/maint
diff --git a/Documentation/git-cvsserver.txt b/Documentation/git-cvsserver.txt
index 85d0950cf4..f9e0c77379 100644
--- a/Documentation/git-cvsserver.txt
+++ b/Documentation/git-cvsserver.txt
@@ -110,12 +110,12 @@ To get a checkout with the Eclipse CVS client:
 Protocol notes: If you are using anonymous access via pserver, just select that.
 Those using SSH access should choose the 'ext' protocol, and configure 'ext'
 access on the Preferences->Team->CVS->ExtConnection pane. Set CVS_SERVER to
-'git-cvsserver'. Not that password support is not good when using 'ext',
+'git-cvsserver'. Note that password support is not good when using 'ext',
 you will definitely want to have SSH keys setup.
 
 Alternatively, you can just use the non-standard extssh protocol that Eclipse
 offer. In that case CVS_SERVER is ignored, and you will have to replace
-the cvs utility on the server with git-cvsserver or manipulate your .bashrc
+the cvs utility on the server with git-cvsserver or manipulate your `.bashrc`
 so that calling 'cvs' effectively calls git-cvsserver.
 
 Clients known to work
@@ -134,9 +134,9 @@ checkout, diff, status, update, log, add, remove, commit.
 Legacy monitoring operations are not supported (edit, watch and related).
 Exports and tagging (tags and branches) are not supported at this stage.
 
-The server should set the -k mode to binary when relevant, however,
+The server should set the '-k' mode to binary when relevant, however,
 this is not really implemented yet. For now, you can force the server
-to set `-kb` for all files by setting the `gitcvs.allbinary` config
+to set '-kb' for all files by setting the `gitcvs.allbinary` config
 variable. In proper GIT tradition, the contents of the files are
 always respected. No keyword expansion or newline munging is supported.
 
diff --git a/Makefile b/Makefile
index ac29c629e3..a77d31de98 100644
--- a/Makefile
+++ b/Makefile
@@ -251,6 +251,8 @@ BUILT_INS = \
 # what 'all' will build and 'install' will install, in gitexecdir
 ALL_PROGRAMS = $(PROGRAMS) $(SCRIPTS)
 
+ALL_PROGRAMS += git-merge-subtree$X
+
 # what 'all' will build but not install in gitexecdir
 OTHER_PROGRAMS = git$X gitweb/gitweb.cgi
 ifndef NO_TCLTK
@@ -299,7 +301,7 @@ LIB_OBJS = \
 	server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
 	tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
 	revision.o pager.o tree-walk.o xdiff-interface.o \
-	write_or_die.o trace.o list-objects.o grep.o \
+	write_or_die.o trace.o list-objects.o grep.o match-trees.o \
 	alloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \
 	color.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o \
 	convert.o
@@ -725,6 +727,9 @@ git$X: git.c common-cmds.h $(BUILTIN_OBJS) $(GITLIBS) GIT-CFLAGS
 
 help.o: common-cmds.h
 
+git-merge-subtree$X: git-merge-recursive$X
+	rm -f $@ && ln git-merge-recursive$X $@
+
 $(BUILT_INS): git$X
 	$(QUIET_BUILT_IN)rm -f $@ && ln git$X $@
 
@@ -942,6 +947,9 @@ test-dump-cache-tree$X: dump-cache-tree.o $(GITLIBS)
 test-sha1$X: test-sha1.o $(GITLIBS)
 	$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(LIBS)
 
+test-match-trees$X: test-match-trees.o $(GITLIBS)
+	$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(LIBS)
+
 test-chmtime$X: test-chmtime.c
 	$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $<
 
diff --git a/RelNotes b/RelNotes
index d5e055de6f..c543b1d1ee 120000
--- a/RelNotes
+++ b/RelNotes
@@ -1 +1 @@
-Documentation/RelNotes-1.5.1.txt
\ No newline at end of file
+Documentation/RelNotes-1.5.2.txt
\ No newline at end of file
diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 213bd93c7f..316fb0f8da 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -233,6 +233,7 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)
 		if (0 <= pos)
 			die("file '%.*s' already exists.",
 					pfxlen-1, opts.prefix);
+		opts.pos = -1 - pos;
 	}
 
 	if (opts.merge) {
diff --git a/cache.h b/cache.h
index 1b50c32b13..eb57507b80 100644
--- a/cache.h
+++ b/cache.h
@@ -496,4 +496,7 @@ extern void trace_argv_printf(const char **argv, int count, const char *format,
 extern int convert_to_git(const char *path, char **bufp, unsigned long *sizep);
 extern int convert_to_working_tree(const char *path, char **bufp, unsigned long *sizep);
 
+/* match-trees.c */
+void shift_tree(const unsigned char *, const unsigned char *, unsigned char *, int);
+
 #endif /* CACHE_H */
diff --git a/git-fetch.sh b/git-fetch.sh
index fd70696b74..b04bd553f8 100755
--- a/git-fetch.sh
+++ b/git-fetch.sh
@@ -26,6 +26,7 @@ keep=
 shallow_depth=
 no_progress=
 test -t 1 || no_progress=--no-progress
+quiet=
 while case "$#" in 0) break ;; esac
 do
 	case "$1" in
@@ -56,6 +57,9 @@ do
 	--update-head-o|--update-head-ok)
 		update_head_ok=t
 		;;
+	-q|--q|--qu|--qui|--quie|--quiet)
+		quiet=--quiet
+		;;
 	-v|--verbose)
 		verbose=Yes
 		;;
@@ -173,8 +177,8 @@ fetch_all_at_once () {
 	    git-bundle unbundle "$remote" $rref ||
 	    echo failed "$remote"
 	else
-	  git-fetch-pack --thin $exec $keep $shallow_depth $no_progress \
-		"$remote" $rref ||
+	  git-fetch-pack --thin $exec $keep $shallow_depth \
+	      $quiet $no_progress "$remote" $rref ||
 	  echo failed "$remote"
 	fi
       ) |
@@ -248,7 +252,8 @@ fetch_per_ref () {
 	  expr "z$head" : "z$_x40\$" >/dev/null ||
 		die "No such ref $remote_name at $remote"
 	  echo >&2 "Fetching $remote_name from $remote using $proto"
-	  git-http-fetch -v -a "$head" "$remote" || exit
+	  case "$quiet" in '') v=-v ;; *) v= ;; esac
+	  git-http-fetch $v -a "$head" "$remote" || exit
 	  ;;
       rsync://*)
 	  test -n "$shallow_depth" &&
@@ -257,8 +262,9 @@ fetch_per_ref () {
 	  rsync -L -q "$remote/$remote_name" "$TMP_HEAD" || exit 1
 	  head=$(git-rev-parse --verify TMP_HEAD)
 	  rm -f "$TMP_HEAD"
+	  case "$quiet" in '') v=-v ;; *) v= ;; esac
 	  test "$rsync_slurped_objects" || {
-	      rsync -av --ignore-existing --exclude info \
+	      rsync -a $v --ignore-existing --exclude info \
 		  "$remote/objects/" "$GIT_OBJECT_DIRECTORY/" || exit
 
 	      # Look at objects/info/alternates for rsync -- http will
diff --git a/git-merge.sh b/git-merge.sh
index fa4589173f..7ebbce4bdb 100755
--- a/git-merge.sh
+++ b/git-merge.sh
@@ -16,10 +16,10 @@ test -z "$(git ls-files -u)" ||
 LF='
 '
 
-all_strategies='recur recursive octopus resolve stupid ours'
+all_strategies='recur recursive octopus resolve stupid ours subtree'
 default_twohead_strategies='recursive'
 default_octopus_strategies='octopus'
-no_trivial_merge_strategies='ours'
+no_trivial_merge_strategies='ours subtree'
 use_strategies=
 
 index_merge=t
diff --git a/git-svn.perl b/git-svn.perl
index 6216cade0f..ac44f60b81 100755
--- a/git-svn.perl
+++ b/git-svn.perl
@@ -363,13 +363,12 @@ sub cmd_dcommit {
 	my $head = shift;
 	$head ||= 'HEAD';
 	my @refs;
-	my ($url, $rev, $uuid) = working_head_info($head, \@refs);
-	my $c = $refs[-1];
-	unless (defined $url && defined $rev && defined $uuid) {
+	my ($url, $rev, $uuid, $gs) = working_head_info($head, \@refs);
+	unless ($gs) {
 		die "Unable to determine upstream SVN information from ",
 		    "$head history\n";
 	}
-	my $gs = Git::SVN->find_by_url($url);
+	my $c = $refs[-1];
 	my $last_rev;
 	foreach my $d (@refs) {
 		if (!verify_ref("$d~1")) {
@@ -431,16 +430,11 @@ sub cmd_dcommit {
 
 sub cmd_rebase {
 	command_noisy(qw/update-index --refresh/);
-	my $url = (working_head_info('HEAD'))[0];
-	if (!defined $url) {
+	my ($url, $rev, $uuid, $gs) = working_head_info('HEAD');
+	unless ($gs) {
 		die "Unable to determine upstream SVN information from ",
 		    "working tree history\n";
 	}
-
-	my $gs = Git::SVN->find_by_url($url);
-	unless ($gs) {
-		die "Unable to determine remote information from URL: $url\n";
-	}
 	if (command(qw/diff-index HEAD --/)) {
 		print STDERR "Cannot rebase with uncommited changes:\n";
 		command_noisy('status');
@@ -453,8 +447,8 @@ sub cmd_rebase {
 }
 
 sub cmd_show_ignore {
-	my $url = (::working_head_info('HEAD'))[0];
-	my $gs = Git::SVN->find_by_url($url) || Git::SVN->new;
+	my ($url, $rev, $uuid, $gs) = working_head_info('HEAD');
+	$gs ||= Git::SVN->new;
 	my $r = (defined $_revision ? $_revision : $gs->ra->get_latest_revnum);
 	$gs->traverse_ignore(\*STDOUT, $gs->{path}, $r);
 }
@@ -776,16 +770,23 @@ sub cmt_metadata {
 
 sub working_head_info {
 	my ($head, $refs) = @_;
-	my ($url, $rev, $uuid);
 	my ($fh, $ctx) = command_output_pipe('rev-list', $head);
 	while (<$fh>) {
 		chomp;
-		($url, $rev, $uuid) = cmt_metadata($_);
-		last if (defined $url && defined $rev && defined $uuid);
+		my ($url, $rev, $uuid) = cmt_metadata($_);
+		if (defined $url && defined $rev) {
+			if (my $gs = Git::SVN->find_by_url($url)) {
+				my $c = $gs->rev_db_get($rev);
+				if ($c && $c eq $_) {
+					close $fh; # break the pipe
+					return ($url, $rev, $uuid, $gs);
+				}
+			}
+		}
 		unshift @$refs, $_ if $refs;
 	}
-	close $fh; # break the pipe
-	($url, $rev, $uuid);
+	command_close_pipe($fh, $ctx);
+	(undef, undef, undef, undef);
 }
 
 package Git::SVN;
@@ -3262,12 +3263,19 @@ package Git::SVN::Log;
 sub cmt_showable {
 	my ($c) = @_;
 	return 1 if defined $c->{r};
+
+	# big commit message got truncated by the 16k pretty buffer in rev-list
 	if ($c->{l} && $c->{l}->[-1] eq "...\n" &&
 				$c->{a_raw} =~ /\@([a-f\d\-]+)>$/) {
+		@{$c->{l}} = ();
 		my @log = command(qw/cat-file commit/, $c->{c});
-		shift @log while ($log[0] ne "\n");
+
+		# shift off the headers
+		shift @log while ($log[0] ne '');
 		shift @log;
-		@{$c->{l}} = grep !/^git-svn-id: /, @log;
+
+		# TODO: make $c->{l} not have a trailing newline in the future
+		@{$c->{l}} = map { "$_\n" } grep !/^git-svn-id: /, @log;
 
 		(undef, $c->{r}, undef) = ::extract_metadata(
 				(grep(/^git-svn-id: /, @log))[-1]);
@@ -3321,8 +3329,8 @@ sub git_svn_log_cmd {
 		last;
 	}
 
-	my $url = (::working_head_info($head))[0];
-	my $gs = Git::SVN->find_by_url($url) || Git::SVN->_new;
+	my ($url, $rev, $uuid, $gs) = ::working_head_info($head);
+	$gs ||= Git::SVN->_new;
 	my @cmd = (qw/log --abbrev-commit --pretty=raw --default/,
 	           $gs->refname);
 	push @cmd, '-r' unless $non_recursive;
diff --git a/match-trees.c b/match-trees.c
new file mode 100644
index 0000000000..23cafe47b4
--- /dev/null
+++ b/match-trees.c
@@ -0,0 +1,304 @@
+#include "cache.h"
+#include "tree.h"
+#include "tree-walk.h"
+
+static int score_missing(unsigned mode, const char *path)
+{
+	int score;
+
+	if (S_ISDIR(mode))
+		score = -1000;
+	else if (S_ISLNK(mode))
+		score = -500;
+	else
+		score = -50;
+	return score;
+}
+
+static int score_differs(unsigned mode1, unsigned mode2, const char *path)
+{
+	int score;
+
+	if (S_ISDIR(mode1) != S_ISDIR(mode2))
+		score = -100;
+	else if (S_ISLNK(mode1) != S_ISLNK(mode2))
+		score = -50;
+	else
+		score = -5;
+	return score;
+}
+
+static int score_matches(unsigned mode1, unsigned mode2, const char *path)
+{
+	int score;
+
+	/* Heh, we found SHA-1 collisions between different kind of objects */
+	if (S_ISDIR(mode1) != S_ISDIR(mode2))
+		score = -100;
+	else if (S_ISLNK(mode1) != S_ISLNK(mode2))
+		score = -50;
+
+	else if (S_ISDIR(mode1))
+		score = 1000;
+	else if (S_ISLNK(mode1))
+		score = 500;
+	else
+		score = 250;
+	return score;
+}
+
+/*
+ * Inspect two trees, and give a score that tells how similar they are.
+ */
+static int score_trees(const unsigned char *hash1, const unsigned char *hash2)
+{
+	struct tree_desc one;
+	struct tree_desc two;
+	void *one_buf, *two_buf;
+	int score = 0;
+	enum object_type type;
+	unsigned long size;
+
+	one_buf = read_sha1_file(hash1, &type, &size);
+	if (!one_buf)
+		die("unable to read tree (%s)", sha1_to_hex(hash1));
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(hash1));
+	init_tree_desc(&one, one_buf, size);
+	two_buf = read_sha1_file(hash2, &type, &size);
+	if (!two_buf)
+		die("unable to read tree (%s)", sha1_to_hex(hash2));
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(hash2));
+	init_tree_desc(&two, two_buf, size);
+	while (one.size | two.size) {
+		const unsigned char *elem1 = elem1;
+		const unsigned char *elem2 = elem2;
+		const char *path1 = path1;
+		const char *path2 = path2;
+		unsigned mode1 = mode1;
+		unsigned mode2 = mode2;
+		int cmp;
+
+		if (one.size)
+			elem1 = tree_entry_extract(&one, &path1, &mode1);
+		if (two.size)
+			elem2 = tree_entry_extract(&two, &path2, &mode2);
+
+		if (!one.size) {
+			/* two has more entries */
+			score += score_missing(mode2, path2);
+			update_tree_entry(&two);
+			continue;
+		}
+		if (!two.size) {
+			/* two lacks this entry */
+			score += score_missing(mode1, path1);
+			update_tree_entry(&one);
+			continue;
+		}
+		cmp = base_name_compare(path1, strlen(path1), mode1,
+					path2, strlen(path2), mode2);
+		if (cmp < 0) {
+			/* path1 does not appear in two */
+			score += score_missing(mode1, path1);
+			update_tree_entry(&one);
+			continue;
+		}
+		else if (cmp > 0) {
+			/* path2 does not appear in one */
+			score += score_missing(mode2, path2);
+			update_tree_entry(&two);
+			continue;
+		}
+		else if (hashcmp(elem1, elem2))
+			/* they are different */
+			score += score_differs(mode1, mode2, path1);
+		else
+			/* same subtree or blob */
+			score += score_matches(mode1, mode2, path1);
+		update_tree_entry(&one);
+		update_tree_entry(&two);
+	}
+	free(one_buf);
+	free(two_buf);
+	return score;
+}
+
+/*
+ * Match one itself and its subtrees with two and pick the best match.
+ */
+static void match_trees(const unsigned char *hash1,
+			const unsigned char *hash2,
+			int *best_score,
+			char **best_match,
+			char *base,
+			int recurse_limit)
+{
+	struct tree_desc one;
+	void *one_buf;
+	enum object_type type;
+	unsigned long size;
+
+	one_buf = read_sha1_file(hash1, &type, &size);
+	if (!one_buf)
+		die("unable to read tree (%s)", sha1_to_hex(hash1));
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(hash1));
+	init_tree_desc(&one, one_buf, size);
+
+	while (one.size) {
+		const char *path;
+		const unsigned char *elem;
+		unsigned mode;
+		int score;
+
+		elem = tree_entry_extract(&one, &path, &mode);
+		if (!S_ISDIR(mode))
+			goto next;
+		score = score_trees(elem, hash2);
+		if (*best_score < score) {
+			char *newpath;
+			newpath = xmalloc(strlen(base) + strlen(path) + 1);
+			sprintf(newpath, "%s%s", base, path);
+			free(*best_match);
+			*best_match = newpath;
+			*best_score = score;
+		}
+		if (recurse_limit) {
+			char *newbase;
+			newbase = xmalloc(strlen(base) + strlen(path) + 2);
+			sprintf(newbase, "%s%s/", base, path);
+			match_trees(elem, hash2, best_score, best_match,
+				    newbase, recurse_limit - 1);
+			free(newbase);
+		}
+
+	next:
+		update_tree_entry(&one);
+	}
+	free(one_buf);
+}
+
+/*
+ * A tree "hash1" has a subdirectory at "prefix".  Come up with a
+ * tree object by replacing it with another tree "hash2".
+ */
+static int splice_tree(const unsigned char *hash1,
+		       char *prefix,
+		       const unsigned char *hash2,
+		       unsigned char *result)
+{
+	char *subpath;
+	int toplen;
+	char *buf;
+	unsigned long sz;
+	struct tree_desc desc;
+	unsigned char *rewrite_here;
+	const unsigned char *rewrite_with;
+	unsigned char subtree[20];
+	enum object_type type;
+	int status;
+
+	subpath = strchr(prefix, '/');
+	if (!subpath)
+		toplen = strlen(prefix);
+	else {
+		toplen = subpath - prefix;
+		subpath++;
+	}
+
+	buf = read_sha1_file(hash1, &type, &sz);
+	if (!buf)
+		die("cannot read tree %s", sha1_to_hex(hash1));
+	init_tree_desc(&desc, buf, sz);
+
+	rewrite_here = NULL;
+	while (desc.size) {
+		const char *name;
+		unsigned mode;
+		const unsigned char *sha1;
+
+		sha1 = tree_entry_extract(&desc, &name, &mode);
+		if (strlen(name) == toplen &&
+		    !memcmp(name, prefix, toplen)) {
+			if (!S_ISDIR(mode))
+				die("entry %s in tree %s is not a tree",
+				    name, sha1_to_hex(hash1));
+			rewrite_here = (unsigned char *) sha1;
+			break;
+		}
+		update_tree_entry(&desc);
+	}
+	if (!rewrite_here)
+		die("entry %.*s not found in tree %s",
+		    toplen, prefix, sha1_to_hex(hash1));
+	if (subpath) {
+		status = splice_tree(rewrite_here, subpath, hash2, subtree);
+		if (status)
+			return status;
+		rewrite_with = subtree;
+	}
+	else
+		rewrite_with = hash2;
+	hashcpy(rewrite_here, rewrite_with);
+	status = write_sha1_file(buf, sz, tree_type, result);
+	free(buf);
+	return status;
+}
+
+/*
+ * We are trying to come up with a merge between one and two that
+ * results in a tree shape similar to one.  The tree two might
+ * correspond to a subtree of one, in which case it needs to be
+ * shifted down by prefixing otherwise empty directories.  On the
+ * other hand, it could cover tree one and we might need to pick a
+ * subtree of it.
+ */
+void shift_tree(const unsigned char *hash1,
+		const unsigned char *hash2,
+		unsigned char *shifted,
+		int depth_limit)
+{
+	char *add_prefix;
+	char *del_prefix;
+	int add_score, del_score;
+
+	add_score = del_score = score_trees(hash1, hash2);
+	add_prefix = xcalloc(1, 1);
+	del_prefix = xcalloc(1, 1);
+
+	/*
+	 * See if one's subtree resembles two; if so we need to prefix
+	 * two with a few fake trees to match the prefix.
+	 */
+	match_trees(hash1, hash2, &add_score, &add_prefix, "", depth_limit);
+
+	/*
+	 * See if two's subtree resembles one; if so we need to
+	 * pick only subtree of two.
+	 */
+	match_trees(hash2, hash1, &del_score, &del_prefix, "", depth_limit);
+
+	/* Assume we do not have to do any shifting */
+	hashcpy(shifted, hash2);
+
+	if (add_score < del_score) {
+		/* We need to pick a subtree of two */
+		unsigned mode;
+
+		if (!*del_prefix)
+			return;
+
+		if (get_tree_entry(hash2, del_prefix, shifted, &mode))
+			die("cannot find path %s in tree %s",
+			    del_prefix, sha1_to_hex(hash2));
+		return;
+	}
+
+	if (!*add_prefix)
+		return;
+
+	splice_tree(hash1, add_prefix, hash2, shifted);
+}
+
diff --git a/merge-recursive.c b/merge-recursive.c
index 2b614b64ba..3096594b3e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -16,6 +16,22 @@
 #include "path-list.h"
 #include "xdiff-interface.h"
 
+static int subtree_merge;
+
+static struct tree *shift_tree_object(struct tree *one, struct tree *two)
+{
+	unsigned char shifted[20];
+
+	/*
+	 * NEEDSWORK: this limits the recursion depth to hardcoded
+	 * value '2' to avoid excessive overhead.
+	 */
+	shift_tree(one->object.sha1, two->object.sha1, shifted, 2);
+	if (!hashcmp(two->object.sha1, shifted))
+		return two;
+	return lookup_tree(shifted);
+}
+
 /*
  * A virtual commit has
  * - (const char *)commit->util set to the name, and
@@ -1137,6 +1153,12 @@ static int merge_trees(struct tree *head,
 		       struct tree **result)
 {
 	int code, clean;
+
+	if (subtree_merge) {
+		merge = shift_tree_object(head, merge);
+		common = shift_tree_object(head, common);
+	}
+
 	if (sha_eq(common->object.sha1, merge->object.sha1)) {
 		output(0, "Already uptodate!");
 		*result = head;
@@ -1342,6 +1364,13 @@ int main(int argc, char *argv[])
 	struct lock_file *lock = xcalloc(1, sizeof(struct lock_file));
 	int index_fd;
 
+	if (argv[0]) {
+		int namelen = strlen(argv[0]);
+		if (8 < namelen &&
+		    !strcmp(argv[0] + namelen - 8, "-subtree"))
+			subtree_merge = 1;
+	}
+
 	git_config(merge_config);
 	if (getenv("GIT_MERGE_VERBOSITY"))
 		verbosity = strtol(getenv("GIT_MERGE_VERBOSITY"), NULL, 10);
diff --git a/read-cache.c b/read-cache.c
index a8f8a6b2b2..54573ce2ee 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -485,6 +485,8 @@ static int has_file_name(const struct cache_entry *ce, int pos, int ok_to_replac
 			continue;
 		if (p->name[len] != '/')
 			continue;
+		if (!ce_stage(p) && !p->ce_mode)
+			continue;
 		retval = -1;
 		if (!ok_to_replace)
 			break;
@@ -517,26 +519,37 @@ static int has_dir_name(const struct cache_entry *ce, int pos, int ok_to_replace
 
 		pos = cache_name_pos(name, ntohs(create_ce_flags(len, stage)));
 		if (pos >= 0) {
-			retval = -1;
-			if (!ok_to_replace)
-				break;
-			remove_cache_entry_at(pos);
-			continue;
+			/*
+			 * Found one, but not so fast.  This could
+			 * be a marker that says "I was here, but
+			 * I am being removed".  Such an entry is
+			 * not a part of the resulting tree, and
+			 * it is Ok to have a directory at the same
+			 * path.
+			 */
+			if (stage || active_cache[pos]->ce_mode) {
+				retval = -1;
+				if (!ok_to_replace)
+					break;
+				remove_cache_entry_at(pos);
+				continue;
+			}
 		}
+		else
+			pos = -pos-1;
 
 		/*
 		 * Trivial optimization: if we find an entry that
 		 * already matches the sub-directory, then we know
 		 * we're ok, and we can exit.
 		 */
-		pos = -pos-1;
 		while (pos < active_nr) {
 			struct cache_entry *p = active_cache[pos];
 			if ((ce_namelen(p) <= len) ||
 			    (p->name[len] != '/') ||
 			    memcmp(p->name, name, len))
 				break; /* not our subdirectory */
-			if (ce_stage(p) == stage)
+			if (ce_stage(p) == stage && (stage || p->ce_mode))
 				/* p is at the same stage as our entry, and
 				 * is a subdirectory of what we are looking
 				 * at, so we cannot have conflicts at our
@@ -560,12 +573,21 @@ static int has_dir_name(const struct cache_entry *ce, int pos, int ok_to_replace
  */
 static int check_file_directory_conflict(const struct cache_entry *ce, int pos, int ok_to_replace)
 {
+	int retval;
+
+	/*
+	 * When ce is an "I am going away" entry, we allow it to be added
+	 */
+	if (!ce_stage(ce) && !ce->ce_mode)
+		return 0;
+
 	/*
 	 * We check if the path is a sub-path of a subsequent pathname
 	 * first, since removing those will not change the position
-	 * in the array
+	 * in the array.
 	 */
-	int retval = has_file_name(ce, pos, ok_to_replace);
+	retval = has_file_name(ce, pos, ok_to_replace);
+
 	/*
 	 * Then check if the path might have a clashing sub-directory
 	 * before it.
diff --git a/test-match-trees.c b/test-match-trees.c
new file mode 100644
index 0000000000..a3c4688778
--- /dev/null
+++ b/test-match-trees.c
@@ -0,0 +1,24 @@
+#include "cache.h"
+#include "tree.h"
+
+int main(int ac, char **av)
+{
+	unsigned char hash1[20], hash2[20], shifted[20];
+	struct tree *one, *two;
+
+	if (get_sha1(av[1], hash1))
+		die("cannot parse %s as an object name", av[1]);
+	if (get_sha1(av[2], hash2))
+		die("cannot parse %s as an object name", av[2]);
+	one = parse_tree_indirect(hash1);
+	if (!one)
+		die("not a treeish %s", av[1]);
+	two = parse_tree_indirect(hash2);
+	if (!two)
+		die("not a treeish %s", av[2]);
+
+	shift_tree(one->object.sha1, two->object.sha1, shifted, -1);
+	printf("shifted: %s\n", sha1_to_hex(shifted));
+
+	exit(0);
+}
diff --git a/unpack-trees.c b/unpack-trees.c
index ee10eea24c..a0b676903a 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -70,7 +70,6 @@ static int entcmp(const char *name1, int dir1, const char *name2, int dir2)
 
 static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 			    const char *base, struct unpack_trees_options *o,
-			    int *indpos,
 			    struct tree_entry_list *df_conflict_list)
 {
 	int baselen = strlen(base);
@@ -100,7 +99,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 		cache_name = NULL;
 
 		/* Check the cache */
-		if (o->merge && *indpos < active_nr) {
+		if (o->merge && o->pos < active_nr) {
 			/* This is a bit tricky: */
 			/* If the index has a subdirectory (with
 			 * contents) as the first name, it'll get a
@@ -118,7 +117,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 			 * file case.
 			 */
 
-			cache_name = active_cache[*indpos]->name;
+			cache_name = active_cache[o->pos]->name;
 			if (strlen(cache_name) > baselen &&
 			    !memcmp(cache_name, base, baselen)) {
 				cache_name += baselen;
@@ -158,8 +157,8 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 
 		if (cache_name && !strcmp(cache_name, first)) {
 			any_files = 1;
-			src[0] = active_cache[*indpos];
-			remove_cache_entry_at(*indpos);
+			src[0] = active_cache[o->pos];
+			remove_cache_entry_at(o->pos);
 		}
 
 		for (i = 0; i < len; i++) {
@@ -228,7 +227,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 #if DBRT_DEBUG > 1
 				printf("Added %d entries\n", ret);
 #endif
-				*indpos += ret;
+				o->pos += ret;
 			} else {
 				for (i = 0; i < src_size; i++) {
 					if (src[i]) {
@@ -244,7 +243,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,
 			newbase[baselen + pathlen] = '/';
 			newbase[baselen + pathlen + 1] = '\0';
 			if (unpack_trees_rec(subposns, len, newbase, o,
-					     indpos, df_conflict_list)) {
+					     df_conflict_list)) {
 				retval = -1;
 				goto leave_directory;
 			}
@@ -375,7 +374,6 @@ static void check_updates(struct cache_entry **src, int nr,
 
 int unpack_trees(struct object_list *trees, struct unpack_trees_options *o)
 {
-	int indpos = 0;
 	unsigned len = object_list_length(trees);
 	struct tree_entry_list **posns;
 	int i;
@@ -404,7 +402,7 @@ int unpack_trees(struct object_list *trees, struct unpack_trees_options *o)
 			posn = posn->next;
 		}
 		if (unpack_trees_rec(posns, len, o->prefix ? o->prefix : "",
-				     o, &indpos, &df_conflict_list))
+				     o, &df_conflict_list))
 			return -1;
 	}
 
@@ -467,6 +465,64 @@ static void invalidate_ce_path(struct cache_entry *ce)
 		cache_tree_invalidate_path(active_cache_tree, ce->name);
 }
 
+static int verify_clean_subdirectory(const char *path, const char *action,
+				      struct unpack_trees_options *o)
+{
+	/*
+	 * we are about to extract "path"; we would not want to lose
+	 * anything in the existing directory there.
+	 */
+	int namelen;
+	int pos, i;
+	struct dir_struct d;
+	char *pathbuf;
+	int cnt = 0;
+
+	/*
+	 * First let's make sure we do not have a local modification
+	 * in that directory.
+	 */
+	namelen = strlen(path);
+	pos = cache_name_pos(path, namelen);
+	if (0 <= pos)
+		return cnt; /* we have it as nondirectory */
+	pos = -pos - 1;
+	for (i = pos; i < active_nr; i++) {
+		struct cache_entry *ce = active_cache[i];
+		int len = ce_namelen(ce);
+		if (len < namelen ||
+		    strncmp(path, ce->name, namelen) ||
+		    ce->name[namelen] != '/')
+			break;
+		/*
+		 * ce->name is an entry in the subdirectory.
+		 */
+		if (!ce_stage(ce)) {
+			verify_uptodate(ce, o);
+			ce->ce_mode = 0;
+		}
+		cnt++;
+	}
+
+	/*
+	 * Then we need to make sure that we do not lose a locally
+	 * present file that is not ignored.
+	 */
+	pathbuf = xmalloc(namelen + 2);
+	memcpy(pathbuf, path, namelen);
+	strcpy(pathbuf+namelen, "/");
+
+	memset(&d, 0, sizeof(d));
+	if (o->dir)
+		d.exclude_per_dir = o->dir->exclude_per_dir;
+	i = read_directory(&d, path, pathbuf, namelen+1, NULL);
+	if (i)
+		die("Updating '%s' would lose untracked files in it",
+		    path);
+	free(pathbuf);
+	return cnt;
+}
+
 /*
  * We do not want to remove or overwrite a working tree file that
  * is not tracked, unless it is ignored.
@@ -478,9 +534,62 @@ static void verify_absent(const char *path, const char *action,
 
 	if (o->index_only || o->reset || !o->update)
 		return;
-	if (!lstat(path, &st) && !(o->dir && excluded(o->dir, path)))
+
+	if (!lstat(path, &st)) {
+		int cnt;
+
+		if (o->dir && excluded(o->dir, path))
+			/*
+			 * path is explicitly excluded, so it is Ok to
+			 * overwrite it.
+			 */
+			return;
+		if (S_ISDIR(st.st_mode)) {
+			/*
+			 * We are checking out path "foo" and
+			 * found "foo/." in the working tree.
+			 * This is tricky -- if we have modified
+			 * files that are in "foo/" we would lose
+			 * it.
+			 */
+			cnt = verify_clean_subdirectory(path, action, o);
+
+			/*
+			 * If this removed entries from the index,
+			 * what that means is:
+			 *
+			 * (1) the caller unpack_trees_rec() saw path/foo
+			 * in the index, and it has not removed it because
+			 * it thinks it is handling 'path' as blob with
+			 * D/F conflict;
+			 * (2) we will return "ok, we placed a merged entry
+			 * in the index" which would cause o->pos to be
+			 * incremented by one;
+			 * (3) however, original o->pos now has 'path/foo'
+			 * marked with "to be removed".
+			 *
+			 * We need to increment it by the number of
+			 * deleted entries here.
+			 */
+			o->pos += cnt;
+			return;
+		}
+
+		/*
+		 * The previous round may already have decided to
+		 * delete this path, which is in a subdirectory that
+		 * is being replaced with a blob.
+		 */
+		cnt = cache_name_pos(path, strlen(path));
+		if (0 <= cnt) {
+			struct cache_entry *ce = active_cache[cnt];
+			if (!ce_stage(ce) && !ce->ce_mode)
+				return;
+		}
+
 		die("Untracked working tree file '%s' "
 		    "would be %s by merge.", path, action);
+	}
 }
 
 static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
@@ -525,7 +634,7 @@ static int deleted_entry(struct cache_entry *ce, struct cache_entry *old,
 	return 1;
 }
 
-static int keep_entry(struct cache_entry *ce)
+static int keep_entry(struct cache_entry *ce, struct unpack_trees_options *o)
 {
 	add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
 	return 1;
@@ -682,7 +791,7 @@ int threeway_merge(struct cache_entry **stages,
 	if (!head_match || !remote_match) {
 		for (i = 1; i < o->head_idx; i++) {
 			if (stages[i]) {
-				keep_entry(stages[i]);
+				keep_entry(stages[i], o);
 				count++;
 				break;
 			}
@@ -695,8 +804,8 @@ int threeway_merge(struct cache_entry **stages,
 		show_stage_entry(stderr, "remote ", stages[remote_match]);
 	}
 #endif
-	if (head) { count += keep_entry(head); }
-	if (remote) { count += keep_entry(remote); }
+	if (head) { count += keep_entry(head, o); }
+	if (remote) { count += keep_entry(remote, o); }
 	return count;
 }
 
@@ -713,12 +822,18 @@ int twoway_merge(struct cache_entry **src,
 		struct unpack_trees_options *o)
 {
 	struct cache_entry *current = src[0];
-	struct cache_entry *oldtree = src[1], *newtree = src[2];
+	struct cache_entry *oldtree = src[1];
+	struct cache_entry *newtree = src[2];
 
 	if (o->merge_size != 2)
 		return error("Cannot do a twoway merge of %d trees",
 			     o->merge_size);
 
+	if (oldtree == o->df_conflict_entry)
+		oldtree = NULL;
+	if (newtree == o->df_conflict_entry)
+		newtree = NULL;
+
 	if (current) {
 		if ((!oldtree && !newtree) || /* 4 and 5 */
 		    (!oldtree && newtree &&
@@ -726,9 +841,9 @@ int twoway_merge(struct cache_entry **src,
 		    (oldtree && newtree &&
 		     same(oldtree, newtree)) || /* 14 and 15 */
 		    (oldtree && newtree &&
-		     !same(oldtree, newtree) && /* 18 and 19*/
+		     !same(oldtree, newtree) && /* 18 and 19 */
 		     same(current, newtree))) {
-			return keep_entry(current);
+			return keep_entry(current, o);
 		}
 		else if (oldtree && !newtree && same(current, oldtree)) {
 			/* 10 or 11 */
@@ -774,7 +889,7 @@ int bind_merge(struct cache_entry **src,
 	if (a && old)
 		die("Entry '%s' overlaps.  Cannot bind.", a->name);
 	if (!a)
-		return keep_entry(old);
+		return keep_entry(old, o);
 	else
 		return merged_entry(a, NULL, o);
 }
@@ -804,7 +919,7 @@ int oneway_merge(struct cache_entry **src,
 			    ce_match_stat(old, &st, 1))
 				old->ce_flags |= htons(CE_UPDATE);
 		}
-		return keep_entry(old);
+		return keep_entry(old, o);
 	}
 	return merged_entry(a, old, o);
 }
diff --git a/unpack-trees.h b/unpack-trees.h
index 191f7442f1..fee7da4382 100644
--- a/unpack-trees.h
+++ b/unpack-trees.h
@@ -16,6 +16,7 @@ struct unpack_trees_options {
 	int verbose_update;
 	int aggressive;
 	const char *prefix;
+	int pos;
 	struct dir_struct *dir;
 	merge_fn_t fn;