v3, 19 partsapply: fix an incomplete comment in check_patch()

diff --git a/builtin/apply.c b/builtin/apply.c
index 725712d..be4e3f3 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3218,16 +3218,22 @@ static int check_patch(struct patch *patch)
 		return status;
 	old_name = patch->old_name;
 
+	/*
+	 * A type-change diff is always split into a patch to
+	 * delete old, immediately followed by a patch to
+	 * create new (see diff.c::run_diff()); in such a case
+	 * it is Ok that the entry to be deleted by the
+	 * previous patch is still in the working tree and in
+	 * the index.
+	 *
+	 * A patch to swap-rename between A and B would first rename
+	 * A to B and then rename B to A.  While applying the first
+	 * one, the presense of B should not stop A from renamed to B,
+	 * as to_be_deleted() knows about the later rename.  Removal
+	 * of B and rename from A to B will be handle the same way.
+	 */
 	if ((tpatch = in_fn_table(new_name)) &&
-			(was_deleted(tpatch) || to_be_deleted(tpatch)))
-		/*
-		 * A type-change diff is always split into a patch to
-		 * delete old, immediately followed by a patch to
-		 * create new (see diff.c::run_diff()); in such a case
-		 * it is Ok that the entry to be deleted by the
-		 * previous patch is still in the working tree and in
-		 * the index.
-		 */
+	    (was_deleted(tpatch) || to_be_deleted(tpatch)))
 		ok_if_exists = 1;
 	else
 		ok_if_exists = 0;

diff --git a/builtin/apply.c b/builtin/apply.c
index be4e3f3..8488c8e 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -2970,9 +2970,15 @@ static struct patch *in_fn_table(const char *name)
  * item->util in the filename table records the status of the path.
  * Usually it points at a patch (whose result records the contents
  * of it after applying it), but it could be PATH_WAS_DELETED for a
- * path that a previously applied patch has already removed.
+ * path that a previously applied patch has already removed, or
+ * PATH_TO_BE_DELETED for a path that a later patch would remove.
+ *
+ * The latter is needed to deal with a case where two paths A and B
+ * are swapped by first renaming A to B and then renaming B to A;
+ * moving A to B should not be prevented due to presense of B as we
+ * will remove it in a later patch.
  */
- #define PATH_TO_BE_DELETED ((struct patch *) -2)
+#define PATH_TO_BE_DELETED ((struct patch *) -2)
 #define PATH_WAS_DELETED ((struct patch *) -1)
 
 static int to_be_deleted(struct patch *patch)

diff --git a/builtin/apply.c b/builtin/apply.c
index 8488c8e..e2b0942 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -371,8 +371,8 @@ static void prepare_image(struct image *image, char *buf, size_t len,
 static void clear_image(struct image *image)
 {
 	free(image->buf);
-	image->buf = NULL;
-	image->len = 0;
+	free(image->line_allocated);
+	memset(image, 0, sizeof(*image));
 }
 
 /* fmt must contain _one_ %s and no other substitution */

diff --git a/builtin/apply.c b/builtin/apply.c
index e2b0942..3199691 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -2930,20 +2930,17 @@ static int apply_fragments(struct image *img, struct patch *patch)
 	return 0;
 }
 
-static int read_file_or_gitlink(struct cache_entry *ce, struct strbuf *buf)
+static int read_blob_object(struct strbuf *buf, const unsigned char *sha1, unsigned mode)
 {
-	if (!ce)
-		return 0;
-
-	if (S_ISGITLINK(ce->ce_mode)) {
+	if (S_ISGITLINK(mode)) {
 		strbuf_grow(buf, 100);
-		strbuf_addf(buf, "Subproject commit %s\n", sha1_to_hex(ce->sha1));
+		strbuf_addf(buf, "Subproject commit %s\n", sha1_to_hex(sha1));
 	} else {
 		enum object_type type;
 		unsigned long sz;
 		char *result;
 
-		result = read_sha1_file(ce->sha1, &type, &sz);
+		result = read_sha1_file(sha1, &type, &sz);
 		if (!result)
 			return -1;
 		/* XXX read_sha1_file NUL-terminates */
@@ -2952,6 +2949,13 @@ static int read_file_or_gitlink(struct cache_entry *ce, struct strbuf *buf)
 	return 0;
 }
 
+static int read_file_or_gitlink(struct cache_entry *ce, struct strbuf *buf)
+{
+	if (!ce)
+		return 0;
+	return read_blob_object(buf, ce->sha1, ce->ce_mode);
+}
+
 static struct patch *in_fn_table(const char *name)
 {
 	struct string_list_item *item;

diff --git a/builtin/apply.c b/builtin/apply.c
index 3199691..6a1fdc0 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3034,6 +3034,18 @@ static void prepare_fn_table(struct patch *patch)
 	}
 }
 
+static int checkout_target(struct cache_entry *ce, struct stat *st)
+{
+	struct checkout costate;
+
+	memset(&costate, 0, sizeof(costate));
+	costate.base_dir = "";
+	costate.refresh_cache = 1;
+	if (checkout_entry(ce, &costate, NULL) || lstat(ce->name, st))
+		return error(_("cannot checkout %s"), ce->name);
+	return 0;
+}
+
 static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)
 {
 	struct strbuf buf = STRBUF_INIT;
@@ -3163,13 +3175,7 @@ static int check_preimage(struct patch *patch, struct cache_entry **ce, struct s
 		}
 		*ce = active_cache[pos];
 		if (stat_ret < 0) {
-			struct checkout costate;
-			/* checkout */
-			memset(&costate, 0, sizeof(costate));
-			costate.base_dir = "";
-			costate.refresh_cache = 1;
-			if (checkout_entry(*ce, &costate, NULL) ||
-			    lstat(old_name, st))
+			if (checkout_target(*ce, st))
 				return -1;
 		}
 		if (!cached && verify_index_match(*ce, st))

diff --git a/builtin/apply.c b/builtin/apply.c
index 6a1fdc0..8496db5 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3046,10 +3046,10 @@ static int checkout_target(struct cache_entry *ce, struct stat *st)
 	return 0;
 }
 
-static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)
+static int load_preimage(struct image *image,
+			 struct patch *patch, struct stat *st, struct cache_entry *ce)
 {
 	struct strbuf buf = STRBUF_INIT;
-	struct image image;
 	size_t len;
 	char *img;
 	struct patch *tpatch;
@@ -3086,7 +3086,16 @@ static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *
 	}
 
 	img = strbuf_detach(&buf, &len);
-	prepare_image(&image, img, len, !patch->is_binary);
+	prepare_image(image, img, len, !patch->is_binary);
+	return 0;
+}
+
+static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)
+{
+	struct image image;
+
+	if (load_preimage(&image, patch, st, ce) < 0)
+		return -1;
 
 	if (apply_fragments(&image, patch) < 0)
 		return -1; /* note with --reject this succeeds. */

diff --git a/builtin/apply.c b/builtin/apply.c
index 8496db5..78dc1a8 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3046,22 +3046,50 @@ static int checkout_target(struct cache_entry *ce, struct stat *st)
 	return 0;
 }
 
+static struct patch *previous_patch(struct patch *patch, int *gone)
+{
+	struct patch *previous;
+
+	*gone = 0;
+	if (patch->is_copy || patch->is_rename)
+		return NULL; /* "git" patches do not depend on the order */
+
+	previous = in_fn_table(patch->old_name);
+	if (!previous)
+		return NULL;
+
+	if (to_be_deleted(previous))
+		return NULL; /* the deletion hasn't happened yet */
+
+	if (was_deleted(previous))
+		*gone = 1;
+
+	return previous;
+}
+
+/*
+ * We are about to apply "patch"; populate the "image" with the
+ * current version we have, from the working tree or from the index,
+ * depending on the situation e.g. --cached/--index.  If we are
+ * applying a non-git patch that incrementally updates the tree,
+ * we read from the result of a previous diff.
+ */
 static int load_preimage(struct image *image,
 			 struct patch *patch, struct stat *st, struct cache_entry *ce)
 {
 	struct strbuf buf = STRBUF_INIT;
 	size_t len;
 	char *img;
-	struct patch *tpatch;
+	struct patch *previous;
+	int status;
 
-	if (!(patch->is_copy || patch->is_rename) &&
-	    (tpatch = in_fn_table(patch->old_name)) != NULL && !to_be_deleted(tpatch)) {
-		if (was_deleted(tpatch)) {
-			return error(_("patch %s has been renamed/deleted"),
-				patch->old_name);
-		}
+	previous = previous_patch(patch, &status);
+	if (status)
+		return error(_("path %s has been renamed/deleted"),
+			     patch->old_name);
+	if (previous) {
 		/* We have a patched copy in memory; use that. */
-		strbuf_add(&buf, tpatch->result, tpatch->resultsize);
+		strbuf_add(&buf, previous->result, previous->resultsize);
 	} else if (cached) {
 		if (read_file_or_gitlink(ce, &buf))
 			return error(_("read of %s failed"), patch->old_name);
@@ -3143,39 +3171,35 @@ static int verify_index_match(struct cache_entry *ce, struct stat *st)
 	return ce_match_stat(ce, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
 }
 
+/*
+ * If "patch" that we are looking at modifies or deletes what we have,
+ * we would want it not to lose any local modification we have, either
+ * in the working tree or in the index.
+ */
 static int check_preimage(struct patch *patch, struct cache_entry **ce, struct stat *st)
 {
 	const char *old_name = patch->old_name;
-	struct patch *tpatch = NULL;
-	int stat_ret = 0;
+	struct patch *previous = NULL;
+	int stat_ret = 0, status;
 	unsigned st_mode = 0;
 
-	/*
-	 * Make sure that we do not have local modifications from the
-	 * index when we are looking at the index.  Also make sure
-	 * we have the preimage file to be patched in the work tree,
-	 * unless --cached, which tells git to apply only in the index.
-	 */
 	if (!old_name)
 		return 0;
 
 	assert(patch->is_new <= 0);
+	previous = previous_patch(patch, &status);
 
-	if (!(patch->is_copy || patch->is_rename) &&
-	    (tpatch = in_fn_table(old_name)) != NULL && !to_be_deleted(tpatch)) {
-		if (was_deleted(tpatch))
-			return error(_("%s: has been deleted/renamed"), old_name);
-		st_mode = tpatch->new_mode;
+	if (status)
+		return error(_("path %s has been renamed/deleted"), old_name);
+	if (previous) {
+		st_mode = previous->new_mode;
 	} else if (!cached) {
 		stat_ret = lstat(old_name, st);
 		if (stat_ret && errno != ENOENT)
 			return error(_("%s: %s"), old_name, strerror(errno));
 	}
 
-	if (to_be_deleted(tpatch))
-		tpatch = NULL;
-
-	if (check_index && !tpatch) {
+	if (check_index && !previous) {
 		int pos = cache_name_pos(old_name, strlen(old_name));
 		if (pos < 0) {
 			if (patch->is_new < 0)
@@ -3197,7 +3221,7 @@ static int check_preimage(struct patch *patch, struct cache_entry **ce, struct s
 		return error(_("%s: %s"), old_name, strerror(errno));
 	}
 
-	if (!cached && !tpatch)
+	if (!cached && !previous)
 		st_mode = ce_mode_from_stat(*ce, st->st_mode);
 
 	if (patch->is_new < 0)

diff --git a/builtin/apply.c b/builtin/apply.c
index 78dc1a8..35e9a9c 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3067,6 +3067,31 @@ static struct patch *previous_patch(struct patch *patch, int *gone)
 	return previous;
 }
 
+#define SUBMODULE_PATCH_WITHOUT_INDEX 1
+
+static int load_patch_target(struct strbuf *buf,
+			     struct cache_entry *ce,
+			     struct stat *st,
+			     const char *name,
+			     unsigned expected_mode)
+{
+	if (cached) {
+		if (read_file_or_gitlink(ce, buf))
+			return error(_("read of %s failed"), name);
+	} else if (name) {
+		if (S_ISGITLINK(expected_mode)) {
+			if (ce)
+				return read_file_or_gitlink(ce, buf);
+			else
+				return SUBMODULE_PATCH_WITHOUT_INDEX;
+		} else {
+			if (read_old_data(st, name, buf))
+				return error(_("read of %s failed"), name);
+		}
+	}
+	return 0;
+}
+
 /*
  * We are about to apply "patch"; populate the "image" with the
  * current version we have, from the working tree or from the index,
@@ -3090,26 +3115,22 @@ static int load_preimage(struct image *image,
 	if (previous) {
 		/* We have a patched copy in memory; use that. */
 		strbuf_add(&buf, previous->result, previous->resultsize);
-	} else if (cached) {
-		if (read_file_or_gitlink(ce, &buf))
+	} else {
+		status = load_patch_target(&buf, ce, st,
+					   patch->old_name, patch->old_mode);
+		if (status < 0)
+			return status;
+		else if (status == SUBMODULE_PATCH_WITHOUT_INDEX) {
+			/*
+			 * There is no way to apply subproject
+			 * patch without looking at the index.
+			 * NEEDSWORK: shouldn't this be flagged
+			 * as an error???
+			 */
+			free_fragment_list(patch->fragments);
+			patch->fragments = NULL;
+		} else if (status) {
 			return error(_("read of %s failed"), patch->old_name);
-	} else if (patch->old_name) {
-		if (S_ISGITLINK(patch->old_mode)) {
-			if (ce) {
-				read_file_or_gitlink(ce, &buf);
-			} else {
-				/*
-				 * There is no way to apply subproject
-				 * patch without looking at the index.
-				 * NEEDSWORK: shouldn't this be flagged
-				 * as an error???
-				 */
-				free_fragment_list(patch->fragments);
-				patch->fragments = NULL;
-			}
-		} else {
-			if (read_old_data(st, patch->old_name, &buf))
-				return error(_("read of %s failed"), patch->old_name);
 		}
 	}
 

diff --git a/builtin/apply.c b/builtin/apply.c
index 35e9a9c..6431178 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3159,29 +3159,6 @@ static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *
 	return 0;
 }
 
-static int check_to_create_blob(const char *new_name, int ok_if_exists)
-{
-	struct stat nst;
-	if (!lstat(new_name, &nst)) {
-		if (S_ISDIR(nst.st_mode) || ok_if_exists)
-			return 0;
-		/*
-		 * A leading component of new_name might be a symlink
-		 * that is going to be removed with this patch, but
-		 * still pointing at somewhere that has the path.
-		 * In such a case, path "new_name" does not exist as
-		 * far as git is concerned.
-		 */
-		if (has_symlink_leading_path(new_name, strlen(new_name)))
-			return 0;
-
-		return error(_("%s: already exists in working directory"), new_name);
-	}
-	else if ((errno != ENOENT) && (errno != ENOTDIR))
-		return error("%s: %s", new_name, strerror(errno));
-	return 0;
-}
-
 static int verify_index_match(struct cache_entry *ce, struct stat *st)
 {
 	if (S_ISGITLINK(ce->ce_mode)) {
@@ -3266,6 +3243,29 @@ static int check_preimage(struct patch *patch, struct cache_entry **ce, struct s
 	return 0;
 }
 
+static int check_to_create_blob(const char *new_name, int ok_if_exists)
+{
+	struct stat nst;
+	if (!lstat(new_name, &nst)) {
+		if (S_ISDIR(nst.st_mode) || ok_if_exists)
+			return 0;
+		/*
+		 * A leading component of new_name might be a symlink
+		 * that is going to be removed with this patch, but
+		 * still pointing at somewhere that has the path.
+		 * In such a case, path "new_name" does not exist as
+		 * far as git is concerned.
+		 */
+		if (has_symlink_leading_path(new_name, strlen(new_name)))
+			return 0;
+
+		return error(_("%s: already exists in working directory"), new_name);
+	}
+	else if ((errno != ENOENT) && (errno != ENOTDIR))
+		return error("%s: %s", new_name, strerror(errno));
+	return 0;
+}
+
 /*
  * Check and apply the patch in-core; leave the result in patch->result
  * for the caller to write it out to the final destination.

diff --git a/builtin/apply.c b/builtin/apply.c
index 6431178..c4166b3 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3243,9 +3243,21 @@ static int check_preimage(struct patch *patch, struct cache_entry **ce, struct s
 	return 0;
 }
 
-static int check_to_create_blob(const char *new_name, int ok_if_exists)
+
+#define EXISTS_IN_INDEX 1
+#define EXISTS_IN_WORKTREE 2
+
+static int check_to_create(const char *new_name, int ok_if_exists)
 {
 	struct stat nst;
+
+	if (check_index &&
+	    cache_name_pos(new_name, strlen(new_name)) >= 0 &&
+	    !ok_if_exists)
+		return EXISTS_IN_INDEX;
+	if (cached)
+		return 0;
+
 	if (!lstat(new_name, &nst)) {
 		if (S_ISDIR(nst.st_mode) || ok_if_exists)
 			return 0;
@@ -3259,10 +3271,10 @@ static int check_to_create_blob(const char *new_name, int ok_if_exists)
 		if (has_symlink_leading_path(new_name, strlen(new_name)))
 			return 0;
 
-		return error(_("%s: already exists in working directory"), new_name);
-	}
-	else if ((errno != ENOENT) && (errno != ENOTDIR))
+		return EXISTS_IN_WORKTREE;
+	} else if ((errno != ENOENT) && (errno != ENOTDIR)) {
 		return error("%s: %s", new_name, strerror(errno));
+	}
 	return 0;
 }
 
@@ -3310,15 +3322,21 @@ static int check_patch(struct patch *patch)
 
 	if (new_name &&
 	    ((0 < patch->is_new) | (0 < patch->is_rename) | patch->is_copy)) {
-		if (check_index &&
-		    cache_name_pos(new_name, strlen(new_name)) >= 0 &&
-		    !ok_if_exists)
+		int err = check_to_create(new_name, ok_if_exists);
+
+		switch (err) {
+		case 0:
+			break; /* happy */
+		case EXISTS_IN_INDEX:
 			return error(_("%s: already exists in index"), new_name);
-		if (!cached) {
-			int err = check_to_create_blob(new_name, ok_if_exists);
-			if (err)
-				return err;
+			break;
+		case EXISTS_IN_WORKTREE:
+			return error(_("%s: already exists in working directory"),
+				     new_name);
+		default:
+			return err;
 		}
+
 		if (!patch->new_mode) {
 			if (0 < patch->is_new)
 				patch->new_mode = S_IFREG | 0644;

builtin/apply.c, t/t4117-apply-reject.sh

diff --git a/builtin/apply.c b/builtin/apply.c
index c4166b3..509a297 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -46,6 +46,7 @@ static int apply_with_reject;
 static int apply_verbosely;
 static int allow_overlap;
 static int no_add;
+static int threeway;
 static const char *fake_ancestor;
 static int line_termination = '\n';
 static unsigned int p_context = UINT_MAX;
@@ -3139,6 +3140,12 @@ static int load_preimage(struct image *image,
 	return 0;
 }
 
+static int try_threeway(struct image *image, struct patch *patch,
+			struct stat *st, struct cache_entry *ce)
+{
+	return -1; /* for now */
+}
+
 static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)
 {
 	struct image image;
@@ -3146,8 +3153,11 @@ static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *
 	if (load_preimage(&image, patch, st, ce) < 0)
 		return -1;
 
-	if (apply_fragments(&image, patch) < 0)
-		return -1; /* note with --reject this succeeds. */
+	if (apply_fragments(&image, patch) < 0) {
+		/* Note: with --reject, apply_fragments() returns 0 */
+		if (!threeway || try_threeway(&image, patch, st, ce) < 0)
+			return -1;
+	}
 	patch->result = image.buf;
 	patch->resultsize = image.len;
 	add_to_fn_table(patch);
@@ -4073,6 +4083,8 @@ int cmd_apply(int argc, const char **argv, const char *prefix_)
 			"apply a patch without touching the working tree"),
 		OPT_BOOLEAN(0, "apply", &force_apply,
 			"also apply the patch (use with --stat/--summary/--check)"),
+		OPT_BOOL('3', "3way", &threeway,
+			 "attempt three-way merge if a patch does not apply"),
 		OPT_FILENAME(0, "build-fake-ancestor", &fake_ancestor,
 			"build a temporary index based on embedded index information"),
 		{ OPTION_CALLBACK, 'z', NULL, NULL, NULL,
@@ -4121,6 +4133,15 @@ int cmd_apply(int argc, const char **argv, const char *prefix_)
 	argc = parse_options(argc, argv, prefix, builtin_apply_options,
 			apply_usage, 0);
 
+	if (apply_with_reject && threeway)
+		die("--reject and --3way cannot be used together.");
+	if (cached && threeway)
+		die("--cached and --3way cannot be used together.");
+	if (threeway) {
+		if (is_not_gitdir)
+			die(_("--3way outside a repository"));
+		check_index = 1;
+	}
 	if (apply_with_reject)
 		apply = apply_verbosely = 1;
 	if (!force_apply && (diffstat || numstat || summary || check || fake_ancestor))
diff --git a/t/t4117-apply-reject.sh b/t/t4117-apply-reject.sh
index e9ccd16..8e15ecb 100755
--- a/t/t4117-apply-reject.sh
+++ b/t/t4117-apply-reject.sh
@@ -46,6 +46,14 @@ test_expect_success setup '
 	cat file1 >saved.file1
 '
 
+test_expect_success 'apply --reject is incompatible with --3way' '
+	test_when_finished "cat saved.file1 >file1" &&
+	git diff >patch.0 &&
+	git checkout file1 &&
+	test_must_fail git apply --reject --3way patch.0 &&
+	git diff --exit-code
+'
+
 test_expect_success 'apply without --reject should fail' '
 
 	if git apply patch.1

diff --git a/builtin/apply.c b/builtin/apply.c
index 509a297..6936588 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3140,10 +3140,54 @@ static int load_preimage(struct image *image,
 	return 0;
 }
 
+static int three_way_merge(struct image *image,
+			   char *path,
+			   unsigned char *base,
+			   unsigned char *ours,
+			   unsigned char *theirs)
+{
+	return -1; /* for now */
+}
+
 static int try_threeway(struct image *image, struct patch *patch,
 			struct stat *st, struct cache_entry *ce)
 {
-	return -1; /* for now */
+	unsigned char pre_sha1[20], post_sha1[20], our_sha1[20];
+	struct strbuf buf = STRBUF_INIT;
+	size_t len;
+	char *img;
+	struct image tmp_image;
+
+	/* No point falling back to 3-way merge in these cases */
+	if (patch->is_new || patch->is_delete ||
+	    S_ISGITLINK(patch->old_mode) || S_ISGITLINK(patch->new_mode))
+		return -1;
+
+	/* Preimage the patch was prepared for */
+	if (get_sha1(patch->old_sha1_prefix, pre_sha1) ||
+	    read_blob_object(&buf, pre_sha1, patch->old_mode))
+		return error("repository lacks the necessary blob to fall back on 3-way merge.");
+	img = strbuf_detach(&buf, &len);
+	prepare_image(&tmp_image, img, len, 1);
+	/* Apply the patch to get the post image */
+	if (apply_fragments(&tmp_image, patch) < 0) {
+		clear_image(&tmp_image);
+		return -1;
+	}
+	/* post_sha1[] is theirs */
+	write_sha1_file(tmp_image.buf, tmp_image.len, blob_type, post_sha1);
+	clear_image(&tmp_image);
+
+	/* our_sha1[] is ours */
+	if (load_preimage(&tmp_image, patch, st, ce))
+		return error("cannot read the current contents of '%s'",
+			     patch->old_name);
+	write_sha1_file(tmp_image.buf, tmp_image.len, blob_type, our_sha1);
+	clear_image(&tmp_image);
+
+	/* in-core three-way merge between post and our using pre as base */
+	return three_way_merge(image,
+			       patch->new_name, pre_sha1, our_sha1, post_sha1);
 }
 
 static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)

diff --git a/builtin/apply.c b/builtin/apply.c
index 6936588..5ef8652 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -16,6 +16,8 @@
 #include "dir.h"
 #include "diff.h"
 #include "parse-options.h"
+#include "xdiff-interface.h"
+#include "ll-merge.h"
 
 /*
  *  --check turns on checking that the working tree matches the
@@ -194,12 +196,16 @@ struct patch {
 	unsigned int is_copy:1;
 	unsigned int is_rename:1;
 	unsigned int recount:1;
+	unsigned int conflicted_threeway:1;
 	struct fragment *fragments;
 	char *result;
 	size_t resultsize;
 	char old_sha1_prefix[41];
 	char new_sha1_prefix[41];
 	struct patch *next;
+
+	/* three-way fallback result */
+	unsigned char threeway_stage[3][20];
 };
 
 static void free_fragment_list(struct fragment *list)
@@ -3142,11 +3148,33 @@ static int load_preimage(struct image *image,
 
 static int three_way_merge(struct image *image,
 			   char *path,
-			   unsigned char *base,
-			   unsigned char *ours,
-			   unsigned char *theirs)
+			   const unsigned char *base,
+			   const unsigned char *ours,
+			   const unsigned char *theirs)
 {
-	return -1; /* for now */
+	mmfile_t base_file, our_file, their_file;
+	mmbuffer_t result = { NULL };
+	int status;
+
+	read_mmblob(&base_file, base);
+	read_mmblob(&our_file, ours);
+	read_mmblob(&their_file, theirs);
+	status = ll_merge(&result, path,
+			  &base_file, "base",
+			  &our_file, "ours",
+			  &their_file, "theirs", NULL);
+	free(base_file.ptr);
+	free(our_file.ptr);
+	free(their_file.ptr);
+	if (status < 0 || !result.ptr) {
+		free(result.ptr);
+		return -1;
+	}
+	clear_image(image);
+	image->buf = result.ptr;
+	image->len = result.size;
+
+	return status;
 }
 
 static int try_threeway(struct image *image, struct patch *patch,
@@ -3155,6 +3183,7 @@ static int try_threeway(struct image *image, struct patch *patch,
 	unsigned char pre_sha1[20], post_sha1[20], our_sha1[20];
 	struct strbuf buf = STRBUF_INIT;
 	size_t len;
+	int status;
 	char *img;
 	struct image tmp_image;
 
@@ -3167,6 +3196,9 @@ static int try_threeway(struct image *image, struct patch *patch,
 	if (get_sha1(patch->old_sha1_prefix, pre_sha1) ||
 	    read_blob_object(&buf, pre_sha1, patch->old_mode))
 		return error("repository lacks the necessary blob to fall back on 3-way merge.");
+
+	fprintf(stderr, "Falling back to three-way merge...\n");
+
 	img = strbuf_detach(&buf, &len);
 	prepare_image(&tmp_image, img, len, 1);
 	/* Apply the patch to get the post image */
@@ -3186,8 +3218,23 @@ static int try_threeway(struct image *image, struct patch *patch,
 	clear_image(&tmp_image);
 
 	/* in-core three-way merge between post and our using pre as base */
-	return three_way_merge(image,
-			       patch->new_name, pre_sha1, our_sha1, post_sha1);
+	status = three_way_merge(image, patch->new_name,
+				 pre_sha1, our_sha1, post_sha1);
+	if (status < 0) {
+		fprintf(stderr, "Failed to fall back on three-way merge...\n");
+		return status;
+	}
+
+	if (status) {
+		patch->conflicted_threeway = 1;
+		hashcpy(patch->threeway_stage[0], pre_sha1);
+		hashcpy(patch->threeway_stage[1], our_sha1);
+		hashcpy(patch->threeway_stage[2], post_sha1);
+		fprintf(stderr, "Applied patch to '%s' with conflicts.\n", patch->new_name);
+	} else {
+		fprintf(stderr, "Applied patch to '%s' cleanly.\n", patch->new_name);
+	}
+	return 0;
 }
 
 static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *ce)

diff --git a/builtin/apply.c b/builtin/apply.c
index 5ef8652..8bc4218 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3074,6 +3074,16 @@ static struct patch *previous_patch(struct patch *patch, int *gone)
 	return previous;
 }
 
+static int verify_index_match(struct cache_entry *ce, struct stat *st)
+{
+	if (S_ISGITLINK(ce->ce_mode)) {
+		if (!S_ISDIR(st->st_mode))
+			return -1;
+		return 0;
+	}
+	return ce_match_stat(ce, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
+}
+
 #define SUBMODULE_PATCH_WITHOUT_INDEX 1
 
 static int load_patch_target(struct strbuf *buf,
@@ -3260,16 +3270,6 @@ static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *
 	return 0;
 }
 
-static int verify_index_match(struct cache_entry *ce, struct stat *st)
-{
-	if (S_ISGITLINK(ce->ce_mode)) {
-		if (!S_ISDIR(st->st_mode))
-			return -1;
-		return 0;
-	}
-	return ce_match_stat(ce, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
-}
-
 /*
  * If "patch" that we are looking at modifies or deletes what we have,
  * we would want it not to lose any local modification we have, either

diff --git a/builtin/apply.c b/builtin/apply.c
index 8bc4218..c3b9f76 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -197,6 +197,7 @@ struct patch {
 	unsigned int is_rename:1;
 	unsigned int recount:1;
 	unsigned int conflicted_threeway:1;
+	unsigned int direct_to_threeway:1;
 	struct fragment *fragments;
 	char *result;
 	size_t resultsize;
@@ -3187,6 +3188,48 @@ static int three_way_merge(struct image *image,
 	return status;
 }
 
+/*
+ * When directly falling back to add/add three-way merge, we read from
+ * the current contents of the new_name.  In no cases other than that
+ * this function will be called.
+ */
+static int load_current(struct image *image, struct patch *patch)
+{
+	struct strbuf buf = STRBUF_INIT;
+	int status, pos;
+	size_t len;
+	char *img;
+	struct stat st;
+	struct cache_entry *ce;
+	char *name = patch->new_name;
+	unsigned mode = patch->new_mode;
+
+	if (!patch->is_new)
+		die("BUG: patch to %s is not a creation", patch->old_name);
+
+	pos = cache_name_pos(name, strlen(name));
+	if (pos < 0)
+		return error(_("%s: does not exist in index"), name);
+	ce = active_cache[pos];
+	if (lstat(name, &st)) {
+		if (errno != ENOENT)
+			return error(_("%s: %s"), name, strerror(errno));
+		if (checkout_target(ce, &st))
+			return -1;
+	}
+	if (verify_index_match(ce, &st))
+		return error(_("%s: does not match index"), name);
+
+	status = load_patch_target(&buf, ce, &st, name, mode);
+	if (status < 0)
+		return status;
+	else if (status)
+		return -1;
+	img = strbuf_detach(&buf, &len);
+	prepare_image(image, img, len, !patch->is_binary);
+	return 0;
+}
+
 static int try_threeway(struct image *image, struct patch *patch,
 			struct stat *st, struct cache_entry *ce)
 {
@@ -3198,13 +3241,15 @@ static int try_threeway(struct image *image, struct patch *patch,
 	struct image tmp_image;
 
 	/* No point falling back to 3-way merge in these cases */
-	if (patch->is_new || patch->is_delete ||
+	if (patch->is_delete ||
 	    S_ISGITLINK(patch->old_mode) || S_ISGITLINK(patch->new_mode))
 		return -1;
 
 	/* Preimage the patch was prepared for */
-	if (get_sha1(patch->old_sha1_prefix, pre_sha1) ||
-	    read_blob_object(&buf, pre_sha1, patch->old_mode))
+	if (patch->is_new)
+		write_sha1_file("", 0, blob_type, pre_sha1);
+	else if (get_sha1(patch->old_sha1_prefix, pre_sha1) ||
+		 read_blob_object(&buf, pre_sha1, patch->old_mode))
 		return error("repository lacks the necessary blob to fall back on 3-way merge.");
 
 	fprintf(stderr, "Falling back to three-way merge...\n");
@@ -3221,9 +3266,15 @@ static int try_threeway(struct image *image, struct patch *patch,
 	clear_image(&tmp_image);
 
 	/* our_sha1[] is ours */
-	if (load_preimage(&tmp_image, patch, st, ce))
-		return error("cannot read the current contents of '%s'",
-			     patch->old_name);
+	if (patch->is_new) {
+		if (load_current(&tmp_image, patch))
+			return error("cannot read the current contents of '%s'",
+				     patch->new_name);
+	} else {
+		if (load_preimage(&tmp_image, patch, st, ce))
+			return error("cannot read the current contents of '%s'",
+				     patch->old_name);
+	}
 	write_sha1_file(tmp_image.buf, tmp_image.len, blob_type, our_sha1);
 	clear_image(&tmp_image);
 
@@ -3254,7 +3305,8 @@ static int apply_data(struct patch *patch, struct stat *st, struct cache_entry *
 	if (load_preimage(&image, patch, st, ce) < 0)
 		return -1;
 
-	if (apply_fragments(&image, patch) < 0) {
+	if (patch->direct_to_threeway ||
+	    apply_fragments(&image, patch) < 0) {
 		/* Note: with --reject, apply_fragments() returns 0 */
 		if (!threeway || try_threeway(&image, patch, st, ce) < 0)
 			return -1;
@@ -3425,7 +3477,9 @@ static int check_patch(struct patch *patch)
 	    ((0 < patch->is_new) | (0 < patch->is_rename) | patch->is_copy)) {
 		int err = check_to_create(new_name, ok_if_exists);
 
-		switch (err) {
+		if (err && threeway) {
+			patch->direct_to_threeway = 1;
+		} else switch (err) {
 		case 0:
 			break; /* happy */
 		case EXISTS_IN_INDEX:

builtin/apply.c, t/t4108-apply-threeway.sh

diff --git a/builtin/apply.c b/builtin/apply.c
index c3b9f76..8afba92 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -3288,7 +3288,10 @@ static int try_threeway(struct image *image, struct patch *patch,
 
 	if (status) {
 		patch->conflicted_threeway = 1;
-		hashcpy(patch->threeway_stage[0], pre_sha1);
+		if (patch->is_new)
+			hashclr(patch->threeway_stage[0]);
+		else
+			hashcpy(patch->threeway_stage[0], pre_sha1);
 		hashcpy(patch->threeway_stage[1], our_sha1);
 		hashcpy(patch->threeway_stage[2], post_sha1);
 		fprintf(stderr, "Applied patch to '%s' with conflicts.\n", patch->new_name);
@@ -3846,6 +3849,32 @@ static void create_one_file(char *path, unsigned mode, const char *buf, unsigned
 	die_errno(_("unable to write file '%s' mode %o"), path, mode);
 }
 
+static void add_conflicted_stages_file(struct patch *patch)
+{
+	int stage, namelen;
+	unsigned ce_size, mode;
+	struct cache_entry *ce;
+
+	if (!update_index)
+		return;
+	namelen = strlen(patch->new_name);
+	ce_size = cache_entry_size(namelen);
+	mode = patch->new_mode ? patch->new_mode : (S_IFREG | 0644);
+
+	remove_file_from_cache(patch->new_name);
+	for (stage = 1; stage < 4; stage++) {
+		if (is_null_sha1(patch->threeway_stage[stage - 1]))
+			continue;
+		ce = xcalloc(1, ce_size);
+		memcpy(ce->name, patch->new_name, namelen);
+		ce->ce_mode = create_ce_mode(mode);
+		ce->ce_flags = create_ce_flags(namelen, stage);
+		hashcpy(ce->sha1, patch->threeway_stage[stage - 1]);
+		if (add_cache_entry(ce, ADD_CACHE_OK_TO_ADD) < 0)
+			die(_("unable to add cache entry for %s"), patch->new_name);
+	}
+}
+
 static void create_file(struct patch *patch)
 {
 	char *path = patch->new_name;
@@ -3856,7 +3885,11 @@ static void create_file(struct patch *patch)
 	if (!mode)
 		mode = S_IFREG | 0644;
 	create_one_file(path, mode, buf, size);
-	add_index_file(path, mode, buf, size);
+
+	if (patch->conflicted_threeway)
+		add_conflicted_stages_file(patch);
+	else
+		add_index_file(path, mode, buf, size);
 }
 
 /* phase zero is to remove, phase one is to create */
@@ -3958,6 +3991,7 @@ static int write_out_results(struct patch *list)
 	int phase;
 	int errs = 0;
 	struct patch *l;
+	struct string_list cpath = STRING_LIST_INIT_DUP;
 
 	for (phase = 0; phase < 2; phase++) {
 		l = list;
@@ -3966,12 +4000,28 @@ static int write_out_results(struct patch *list)
 				errs = 1;
 			else {
 				write_out_one_result(l, phase);
-				if (phase == 1 && write_out_one_reject(l))
-					errs = 1;
+				if (phase == 1) {
+					if (write_out_one_reject(l))
+						errs = 1;
+					if (l->conflicted_threeway) {
+						string_list_append(&cpath, l->new_name);
+						errs = 1;
+					}
+				}
 			}
 			l = l->next;
 		}
 	}
+
+	if (cpath.nr) {
+		struct string_list_item *item;
+
+		sort_string_list(&cpath);
+		for_each_string_list_item(item, &cpath)
+			fprintf(stderr, "U %s\n", item->string);
+		string_list_clear(&cpath, 0);
+	}
+
 	return errs;
 }
 
@@ -4094,8 +4144,11 @@ static int apply_patch(int fd, const char *filename, int options)
 	    !apply_with_reject)
 		exit(1);
 
-	if (apply && write_out_results(list))
-		exit(1);
+	if (apply && write_out_results(list)) {
+		if (apply_with_reject)
+			exit(1);
+		return 1;
+	}
 
 	if (fake_ancestor)
 		build_fake_ancestor(list, fake_ancestor);
diff --git a/t/t4108-apply-threeway.sh b/t/t4108-apply-threeway.sh
new file mode 100755
index 0000000..475dfb5
--- /dev/null
+++ b/t/t4108-apply-threeway.sh
@@ -0,0 +1,78 @@
+#!/bin/sh
+
+test_description='git apply --3way'
+
+. ./test-lib.sh
+
+create_file () {
+	for i
+	do
+		echo "$i"
+	done
+}
+
+sanitize_conflicted_diff () {
+	sed -e '
+		/^index /d
+		s/^\(+[<>][<>][<>][<>]*\) .*/\1/
+	'
+}
+
+test_expect_success setup '
+	test_tick &&
+	create_file >one 1 2 3 4 5 6 7 &&
+	cat one >two &&
+	git add one two &&
+	git commit -m initial &&
+
+	git branch side &&
+
+	test_tick &&
+	create_file >one 1 two 3 4 5 six 7 &&
+	create_file >two 1 two 3 4 5 6 7 &&
+	git commit -a -m master &&
+
+	git checkout side &&
+	create_file >one 1 2 3 4 five 6 7 &&
+	create_file >two 1 2 3 4 five 6 7 &&
+	git commit -a -m side &&
+
+	git checkout master
+'
+
+test_expect_success 'apply without --3way' '
+	git diff side^ side >P.diff &&
+
+	# should fail to apply
+	git reset --hard &&
+	git checkout master^0 &&
+	test_must_fail git apply --index P.diff &&
+	# should leave things intact
+	git diff-files --exit-code &&
+	git diff-index --exit-code --cached HEAD
+'
+
+test_expect_success 'apply with --3way' '
+	# Merging side should be similar to applying this patch
+	git diff ...side >P.diff &&
+
+	# The corresponding conflicted merge
+	git reset --hard &&
+	git checkout master^0 &&
+	test_must_fail git merge --no-commit side &&
+	git ls-files -s >expect.ls &&
+	git diff HEAD | sanitize_conflicted_diff >expect.diff &&
+
+	# should fail to apply
+	git reset --hard &&
+	git checkout master^0 &&
+	test_must_fail git apply --index --3way P.diff &&
+	git ls-files -s >actual.ls &&
+	git diff HEAD | sanitize_conflicted_diff >actual.diff &&
+
+	# The result should resemble the corresponding merge
+	test_cmp expect.ls actual.ls &&
+	test_cmp expect.diff actual.diff
+'
+
+test_done

builtin/apply.c, t/t4108-apply-threeway.sh

diff --git a/builtin/apply.c b/builtin/apply.c
index 8afba92..d12f4f2 100644
--- a/builtin/apply.c
+++ b/builtin/apply.c
@@ -18,6 +18,7 @@
 #include "parse-options.h"
 #include "xdiff-interface.h"
 #include "ll-merge.h"
+#include "rerere.h"
 
 /*
  *  --check turns on checking that the working tree matches the
@@ -4020,6 +4021,8 @@ static int write_out_results(struct patch *list)
 		for_each_string_list_item(item, &cpath)
 			fprintf(stderr, "U %s\n", item->string);
 		string_list_clear(&cpath, 0);
+
+		rerere(0);
 	}
 
 	return errs;
diff --git a/t/t4108-apply-threeway.sh b/t/t4108-apply-threeway.sh
index 475dfb5..e6d4da6 100755
--- a/t/t4108-apply-threeway.sh
+++ b/t/t4108-apply-threeway.sh
@@ -75,4 +75,29 @@ test_expect_success 'apply with --3way' '
 	test_cmp expect.diff actual.diff
 '
 
+test_expect_success 'apply with --3way with rerere enabled' '
+	git config rerere.enabled true &&
+
+	# Merging side should be similar to applying this patch
+	git diff ...side >P.diff &&
+
+	# The corresponding conflicted merge
+	git reset --hard &&
+	git checkout master^0 &&
+	test_must_fail git merge --no-commit side &&
+
+	# Manually resolve and record the resolution
+	create_file 1 two 3 4 five six 7 >one &&
+	git rerere &&
+	cat one >expect &&
+
+	# should fail to apply
+	git reset --hard &&
+	git checkout master^0 &&
+	test_must_fail git apply --index --3way P.diff &&
+
+	# but rerere should have replayed the recorded resolution
+	test_cmp expect one
+'
+
 test_done

diff --git a/Documentation/git-apply.txt b/Documentation/git-apply.txt
index afd2c9a..634b84e 100644
--- a/Documentation/git-apply.txt
+++ b/Documentation/git-apply.txt
@@ -9,7 +9,7 @@ git-apply - Apply a patch to files and/or to the index
 SYNOPSIS
 --------
 [verse]
-'git apply' [--stat] [--numstat] [--summary] [--check] [--index]
+'git apply' [--stat] [--numstat] [--summary] [--check] [--index] [--3way]
 	  [--apply] [--no-add] [--build-fake-ancestor=<file>] [-R | --reverse]
 	  [--allow-binary-replacement | --binary] [--reject] [-z]
 	  [-p<n>] [-C<n>] [--inaccurate-eof] [--recount] [--cached]
@@ -72,6 +72,15 @@ OPTIONS
 	cached data, apply the patch, and store the result in the index
 	without using the working tree. This implies `--index`.
 
+-3::
+--3way::
+	When the patch does not apply cleanly, fall back on 3-way merge if
+	the patch records the identity of blobs it is supposed to apply to,
+	and we have those blobs available locally, possibly leaving the
+	conflict markers in the files in the working tree for the user to
+	resolve.  This option implies the `--index` option, and is incompatible
+	with the `--reject` and the `--cached` options.
+
 --build-fake-ancestor=<file>::
 	Newer 'git diff' output has embedded 'index information'
 	for each blob to help identify the original version that

diff --git a/t/t4108-apply-threeway.sh b/t/t4108-apply-threeway.sh
index e6d4da6..fa5d4ef 100755
--- a/t/t4108-apply-threeway.sh
+++ b/t/t4108-apply-threeway.sh
@@ -100,4 +100,58 @@ test_expect_success 'apply with --3way with rerere enabled' '
 	test_cmp expect one
 '
 
+test_expect_success 'apply -3 with add/add conflict setup' '
+	git reset --hard &&
+
+	git checkout -b adder &&
+	create_file 1 2 3 4 5 6 7 >three &&
+	create_file 1 2 3 4 5 6 7 >four &&
+	git add three four &&
+	git commit -m "add three and four" &&
+
+	git checkout -b another adder^ &&
+	create_file 1 2 3 4 5 6 7 >three &&
+	create_file 1 2 3 four 5 6 7 >four &&
+	git add three four &&
+	git commit -m "add three and four" &&
+
+	# Merging another should be similar to applying this patch
+	git diff adder...another >P.diff &&
+
+	git checkout adder^0 &&
+	test_must_fail git merge --no-commit another &&
+	git ls-files -s >expect.ls &&
+	git diff HEAD | sanitize_conflicted_diff >expect.diff
+'
+
+test_expect_success 'apply -3 with add/add conflict' '
+	# should fail to apply ...
+	git reset --hard &&
+	git checkout adder^0 &&
+	test_must_fail git apply --index --3way P.diff &&
+	# ... and leave conflicts in the index and in the working tree
+	git ls-files -s >actual.ls &&
+	git diff HEAD | sanitize_conflicted_diff >actual.diff &&
+
+	# The result should resemble the corresponding merge
+	test_cmp expect.ls actual.ls &&
+	test_cmp expect.diff actual.diff
+'
+
+test_expect_success 'apply -3 with add/add conflict (dirty working tree)' '
+	# should fail to apply ...
+	git reset --hard &&
+	git checkout adder^0 &&
+	echo >>four &&
+	cat four >four.save &&
+	cat three >three.save &&
+	git ls-files -s >expect.ls &&
+	test_must_fail git apply --index --3way P.diff &&
+	# ... and should not touch anything
+	git ls-files -s >actual.ls &&
+	test_cmp expect.ls actual.ls &&
+	test_cmp four.save four &&
+	test_cmp three.save three
+'
+
 test_done