Implement recursive merge strategy

Extend ResolveMerger with RecursiveMerger to merge two tips
that have up to 200 bases.

Bug: 380314
CQ: 6854
Change-Id: I6292bb7bda55c0242a448a94956f2d6a94fddbaa
Also-by: Christian Halstrick <christian.halstrick@sap.com>
Signed-off-by: Chris Aniszczyk <zx@twitter.com>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

9 files changed, 657 insertions, 92 deletions

diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index b3ef62ad04..cc0b766231 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -288,6 +288,8 @@ mergeConflictOnNotes=Merge conflict on note {0}. base = {1}, ours = {2}, theirs
 mergeStrategyAlreadyExistsAsDefault=Merge strategy "{0}" already exists as a default strategy
 mergeStrategyDoesNotSupportHeads=merge strategy {0} does not support {1} heads to be merged into HEAD
 mergeUsingStrategyResultedInDescription=Merge of revisions {0} with base {1} using strategy {2} resulted in: {3}. {4}
+mergeRecursiveReturnedNoCommit=Merge returned no commit:\n Depth {0}\n Head one {1}\n Head two {2}
+mergeRecursiveTooManyMergeBasesFor = "More than {0} merge bases for:\n a {1}\n b {2} found:\n  count {3}"
 minutesAgo={0} minutes ago
 missingAccesskey=Missing accesskey.
 missingConfigurationForKey=No value for key {0} found in configuration
@@ -313,6 +315,7 @@ noApplyInDelete=No apply in delete
 noClosingBracket=No closing {0} found for {1} at index {2}.
 noHEADExistsAndNoExplicitStartingRevisionWasSpecified=No HEAD exists and no explicit starting revision was specified
 noHMACsupport=No {0} support: {1}
+noMergeBase=No merge base could be determined. Reason={0}. {1}
 noMergeHeadSpecified=No merge head specified
 noSuchRef=no such ref
 notABoolean=Not a boolean: {0}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/errors/NoMergeBaseException.java b/org.eclipse.jgit/src/org/eclipse/jgit/errors/NoMergeBaseException.java
new file mode 100644
index 0000000000..df90e69009
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/errors/NoMergeBaseException.java
@@ -0,0 +1,124 @@
+/*
+ * Copyright (C) 2013, Christian Halstrick <christian.halstrick@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.errors;
+
+import java.io.IOException;
+import java.text.MessageFormat;
+
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.merge.RecursiveMerger;
+
+/**
+ * Exception thrown if a merge fails because no merge base could be determined.
+ */
+public class NoMergeBaseException extends IOException {
+	private static final long serialVersionUID = 1L;
+
+	private MergeBaseFailureReason reason;
+
+	/**
+	 * An enum listing the different reason why no merge base could be
+	 * determined.
+	 */
+	public static enum MergeBaseFailureReason {
+		/**
+		 * Multiple merge bases have been found (e.g. the commits to be merged
+		 * have multiple common predecessors) but the merge strategy doesn't
+		 * support this (e.g. ResolveMerge)
+		 */
+		MULTIPLE_MERGE_BASES_NOT_SUPPORTED,
+
+		/**
+		 * The number of merge bases exceeds {@link RecursiveMerger#MAX_BASES}
+		 */
+		TOO_MANY_MERGE_BASES,
+
+		/**
+		 * In order to find a single merge base it may required to merge
+		 * together multiple common predecessors. If during these merges
+		 * conflicts occur the merge fails with this reason
+		 */
+		CONFLICTS_DURING_MERGE_BASE_CALCULATION
+	}
+
+
+	/**
+	 * Construct a NoMergeBase exception
+	 *
+	 * @param reason
+	 *            the reason why no merge base could be found
+	 * @param message
+	 *            a text describing the problem
+	 */
+	public NoMergeBaseException(MergeBaseFailureReason reason, String message) {
+		super(MessageFormat.format(JGitText.get().noMergeBase,
+				reason.toString(), message));
+		this.reason = reason;
+	}
+
+	/**
+	 * Construct a NoMergeBase exception
+	 *
+	 * @param reason
+	 *            the reason why no merge base could be found
+	 * @param message
+	 *            a text describing the problem
+	 * @param why
+	 *            an exception causing this error
+	 */
+	public NoMergeBaseException(MergeBaseFailureReason reason, String message,
+			Throwable why) {
+		super(MessageFormat.format(JGitText.get().noMergeBase,
+				reason.toString(), message));
+		this.reason = reason;
+		initCause(why);
+	}
+
+	/**
+	 * @return the reason why no merge base could be found
+	 */
+	public MergeBaseFailureReason getReason() {
+		return reason;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index d032bbc88b..f8ea5ff932 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2010, 2013 Sasa Zivkov <sasa.zivkov@sap.com>
+ * Copyright (C) 2012, Research In Motion Limited
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -349,6 +350,8 @@ public class JGitText extends TranslationBundle {
 	/***/ public String mergeStrategyAlreadyExistsAsDefault;
 	/***/ public String mergeStrategyDoesNotSupportHeads;
 	/***/ public String mergeUsingStrategyResultedInDescription;
+	/***/ public String mergeRecursiveReturnedNoCommit;
+	/***/ public String mergeRecursiveTooManyMergeBasesFor;
 	/***/ public String minutesAgo;
 	/***/ public String missingAccesskey;
 	/***/ public String missingConfigurationForKey;
@@ -374,6 +377,7 @@ public class JGitText extends TranslationBundle {
 	/***/ public String noClosingBracket;
 	/***/ public String noHEADExistsAndNoExplicitStartingRevisionWasSpecified;
 	/***/ public String noHMACsupport;
+	/***/ public String noMergeBase;
 	/***/ public String noMergeHeadSpecified;
 	/***/ public String noSuchRef;
 	/***/ public String notABoolean;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeStrategy.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeStrategy.java
index 2e6fc41378..3b64ddd361 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeStrategy.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeStrategy.java
@@ -1,6 +1,7 @@
 /*
  * Copyright (C) 2008-2009, Google Inc.
  * Copyright (C) 2009, Matthias Sohn <matthias.sohn@sap.com>
+ * Copyright (C) 2012, Research In Motion Limited
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -66,9 +67,18 @@ public abstract class MergeStrategy {
 	/** Simple strategy to merge paths, without simultaneous edits. */
 	public static final ThreeWayMergeStrategy SIMPLE_TWO_WAY_IN_CORE = new StrategySimpleTwoWayInCore();
 
-	/** Simple strategy to merge paths. It tries to merge also contents. Multiple merge bases are not supported */
+	/**
+	 * Simple strategy to merge paths. It tries to merge also contents. Multiple
+	 * merge bases are not supported
+	 */
 	public static final ThreeWayMergeStrategy RESOLVE = new StrategyResolve();
 
+	/**
+	 * Recursive strategy to merge paths. It tries to merge also contents.
+	 * Multiple merge bases are supported
+	 */
+	public static final ThreeWayMergeStrategy RECURSIVE = new StrategyRecursive();
+
 	private static final HashMap<String, MergeStrategy> STRATEGIES = new HashMap<String, MergeStrategy>();
 
 	static {
@@ -76,6 +86,7 @@ public abstract class MergeStrategy {
 		register(THEIRS);
 		register(SIMPLE_TWO_WAY_IN_CORE);
 		register(RESOLVE);
+		register(RECURSIVE);
 	}
 
 	/**
@@ -103,7 +114,8 @@ public abstract class MergeStrategy {
 	public static synchronized void register(final String name,
 			final MergeStrategy imp) {
 		if (STRATEGIES.containsKey(name))
-			throw new IllegalArgumentException(MessageFormat.format(JGitText.get().mergeStrategyAlreadyExistsAsDefault, name));
+			throw new IllegalArgumentException(MessageFormat.format(
+					JGitText.get().mergeStrategyAlreadyExistsAsDefault, name));
 		STRATEGIES.put(name, imp);
 	}
 
@@ -146,7 +158,7 @@ public abstract class MergeStrategy {
 
 	/**
 	 * Create a new merge instance.
-	 * 
+	 *
 	 * @param db
 	 *            repository database the merger will read from, and eventually
 	 *            write results back to.
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/Merger.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/Merger.java
index fd94cfb23f..04c29e6e83 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/Merger.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/Merger.java
@@ -47,6 +47,8 @@ import java.io.IOException;
 import java.text.MessageFormat;
 
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.NoMergeBaseException;
+import org.eclipse.jgit.errors.NoMergeBaseException.MergeBaseFailureReason;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.Constants;
@@ -186,19 +188,19 @@ public abstract class Merger {
 	/**
 	 * Create an iterator to walk the merge base of two commits.
 	 *
-	 * @param aIdx
-	 *            index of the first commit in {@link #sourceObjects}.
-	 * @param bIdx
-	 *            index of the second commit in {@link #sourceObjects}.
+	 * @param a
+	 *            the first commit in {@link #sourceObjects}.
+	 * @param b
+	 *            the second commit in {@link #sourceObjects}.
 	 * @return the new iterator
 	 * @throws IncorrectObjectTypeException
 	 *             one of the input objects is not a commit.
 	 * @throws IOException
 	 *             objects are missing or multiple merge bases were found.
 	 */
-	protected AbstractTreeIterator mergeBase(final int aIdx, final int bIdx)
+	protected AbstractTreeIterator mergeBase(RevCommit a, RevCommit b)
 			throws IOException {
-		RevCommit base = getBaseCommit(aIdx, bIdx);
+		RevCommit base = getBaseCommit(a, b);
 		return (base == null) ? new EmptyTreeIterator() : openTree(base.getTree());
 	}
 
@@ -224,18 +226,38 @@ public abstract class Merger {
 		if (sourceCommits[bIdx] == null)
 			throw new IncorrectObjectTypeException(sourceObjects[bIdx],
 					Constants.TYPE_COMMIT);
+		return getBaseCommit(sourceCommits[aIdx], sourceCommits[bIdx]);
+	}
+
+	/**
+	 * Return the merge base of two commits.
+	 *
+	 * @param a
+	 *            the first commit in {@link #sourceObjects}.
+	 * @param b
+	 *            the second commit in {@link #sourceObjects}.
+	 * @return the merge base of two commits
+	 * @throws IncorrectObjectTypeException
+	 *             one of the input objects is not a commit.
+	 * @throws IOException
+	 *             objects are missing or multiple merge bases were found.
+	 */
+	protected RevCommit getBaseCommit(RevCommit a, RevCommit b)
+			throws IncorrectObjectTypeException, IOException {
 		walk.reset();
 		walk.setRevFilter(RevFilter.MERGE_BASE);
-		walk.markStart(sourceCommits[aIdx]);
-		walk.markStart(sourceCommits[bIdx]);
+		walk.markStart(a);
+		walk.markStart(b);
 		final RevCommit base = walk.next();
 		if (base == null)
 			return null;
 		final RevCommit base2 = walk.next();
 		if (base2 != null) {
-			throw new IOException(MessageFormat.format(JGitText.get().multipleMergeBasesFor
-					, sourceCommits[aIdx].name(), sourceCommits[bIdx].name()
-					, base.name(), base2.name()));
+			throw new NoMergeBaseException(
+					MergeBaseFailureReason.MULTIPLE_MERGE_BASES_NOT_SUPPORTED,
+					MessageFormat.format(
+					JGitText.get().multipleMergeBasesFor, a.name(), b.name(),
+					base.name(), base2.name()));
 		}
 		return base;
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/RecursiveMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/RecursiveMerger.java
new file mode 100644
index 0000000000..d68be35403
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/RecursiveMerger.java
@@ -0,0 +1,274 @@
+/*
+ * Copyright (C) 2012, Research In Motion Limited
+ * Copyright (C) 2012, Christian Halstrick <christian.halstrick@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Contributors:
+ *    George Young - initial API and implementation
+ *    Christian Halstrick - initial API and implementation
+ */
+package org.eclipse.jgit.merge;
+
+import java.io.IOException;
+import java.text.MessageFormat;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.logging.Logger;
+
+import org.eclipse.jgit.dircache.DirCache;
+import org.eclipse.jgit.dircache.DirCacheBuilder;
+import org.eclipse.jgit.dircache.DirCacheEntry;
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.NoMergeBaseException;
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.lib.CommitBuilder;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.filter.RevFilter;
+import org.eclipse.jgit.treewalk.TreeWalk;
+import org.eclipse.jgit.treewalk.WorkingTreeIterator;
+
+/**
+ * A three-way merger performing a content-merge if necessary across multiple
+ * bases using recursion
+ *
+ * This merger extends the resolve merger and does several things differently:
+ *
+ * - allow more than one merge base, up to a maximum
+ *
+ * - uses "Lists" instead of Arrays for chained types
+ *
+ * - recursively merges the merge bases together to compute a usable base
+ *
+ */
+
+public class RecursiveMerger extends ResolveMerger {
+	static Logger log = Logger.getLogger(RecursiveMerger.class.toString());
+
+	/**
+	 * The maximum number of merge bases. This merge will stop when the number
+	 * of merge bases exceeds this value
+	 */
+	public final int MAX_BASES = 200;
+
+	private PersonIdent ident = new PersonIdent(db);
+
+	/**
+	 * Normal recursive merge when you want a choice of DirCache placement
+	 * inCore
+	 *
+	 * @param local
+	 * @param inCore
+	 */
+	protected RecursiveMerger(Repository local, boolean inCore) {
+		super(local, inCore);
+	}
+
+	/**
+	 * Normal recursive merge, implies not inCore
+	 *
+	 * @param local
+	 */
+	protected RecursiveMerger(Repository local) {
+		this(local, false);
+	}
+
+	/**
+	 * Get a single base commit for two given commits. If the two source commits
+	 * have more than one base commit recursively merge the base commits
+	 * together until you end up with a single base commit.
+	 *
+	 * @throws IOException
+	 * @throws IncorrectObjectTypeException
+	 */
+	@Override
+	protected RevCommit getBaseCommit(RevCommit a, RevCommit b)
+			throws IncorrectObjectTypeException, IOException {
+		return getBaseCommit(a, b, 0);
+	}
+
+	/**
+	 * Get a single base commit for two given commits. If the two source commits
+	 * have more than one base commit recursively merge the base commits
+	 * together until a virtual common base commit has been found.
+	 *
+	 * @param a
+	 *            the first commit to be merged
+	 * @param b
+	 *            the second commit to be merged
+	 * @param callDepth
+	 *            the callDepth when this method is called recursively
+	 * @return the merge base of two commits
+	 * @throws IOException
+	 * @throws IncorrectObjectTypeException
+	 *             one of the input objects is not a commit.
+	 * @throws NoMergeBaseException
+	 *             too many merge bases are found or the computation of a common
+	 *             merge base failed (e.g. because of a conflict).
+	 */
+	protected RevCommit getBaseCommit(RevCommit a, RevCommit b, int callDepth)
+			throws IOException {
+		ArrayList<RevCommit> baseCommits = new ArrayList<RevCommit>();
+		walk.reset();
+		walk.setRevFilter(RevFilter.MERGE_BASE);
+		walk.markStart(a);
+		walk.markStart(b);
+		RevCommit c;
+		while ((c = walk.next()) != null)
+			baseCommits.add(c);
+
+		if (baseCommits.isEmpty())
+			return null;
+		if (baseCommits.size() == 1)
+			return baseCommits.get(0);
+		if (baseCommits.size() >= MAX_BASES)
+			throw new NoMergeBaseException(NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES, MessageFormat.format(
+					JGitText.get().mergeRecursiveTooManyMergeBasesFor,
+					Integer.valueOf(MAX_BASES), a.name(), b.name(),
+							Integer.valueOf(baseCommits.size())));
+
+		// We know we have more than one base commit. We have to do merges now
+		// to determine a single base commit. We don't want to spoil the current
+		// dircache and working tree with the results of this intermediate
+		// merges. Therefore set the dircache to a new in-memory dircache and
+		// disable that we update the working-tree. We set this back to the
+		// original values once a single base commit is created.
+		RevCommit currentBase = baseCommits.get(0);
+		DirCache oldDircache = dircache;
+		boolean oldIncore = inCore;
+		WorkingTreeIterator oldWTreeIt = workingTreeIterator;
+		workingTreeIterator = null;
+		try {
+			dircache = dircacheFromTree(currentBase.getTree());
+			inCore = true;
+
+			List<RevCommit> parents = new ArrayList<RevCommit>();
+			parents.add(currentBase);
+			for (int commitIdx = 1; commitIdx < baseCommits.size(); commitIdx++) {
+				RevCommit nextBase = baseCommits.get(commitIdx);
+				if (commitIdx >= MAX_BASES)
+					throw new NoMergeBaseException(
+							NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES,
+							MessageFormat.format(
+							JGitText.get().mergeRecursiveTooManyMergeBasesFor,
+							Integer.valueOf(MAX_BASES), a.name(), b.name(),
+									Integer.valueOf(baseCommits.size())));
+				parents.add(nextBase);
+				if (mergeTrees(
+						openTree(getBaseCommit(currentBase, nextBase,
+								callDepth + 1).getTree()),
+						currentBase.getTree(),
+						nextBase.getTree()))
+					currentBase = createCommitForTree(resultTree, parents);
+				else
+					throw new NoMergeBaseException(
+							NoMergeBaseException.MergeBaseFailureReason.CONFLICTS_DURING_MERGE_BASE_CALCULATION,
+							MessageFormat.format(
+									JGitText.get().mergeRecursiveTooManyMergeBasesFor,
+									Integer.valueOf(MAX_BASES), a.name(),
+									b.name(),
+									Integer.valueOf(baseCommits.size())));
+			}
+		} finally {
+			inCore = oldIncore;
+			dircache = oldDircache;
+			workingTreeIterator = oldWTreeIt;
+		}
+		return currentBase;
+	}
+
+	/**
+	 * Create a new commit by explicitly specifying the content tree and the
+	 * parents. The commit message is not set and author/committer are set to
+	 * the current user.
+	 *
+	 * @param tree
+	 *            the tree this commit should capture
+	 * @param parents
+	 *            the list of parent commits
+	 * @return a new (persisted) commit
+	 * @throws IOException
+	 */
+	private RevCommit createCommitForTree(ObjectId tree, List<RevCommit> parents)
+			throws IOException {
+		CommitBuilder c = new CommitBuilder();
+		c.setParentIds(parents);
+		c.setTreeId(tree);
+		c.setAuthor(ident);
+		c.setCommitter(ident);
+		ObjectInserter odi = db.newObjectInserter();
+		ObjectId newCommitId = odi.insert(c);
+		odi.flush();
+		RevCommit ret = walk.lookupCommit(newCommitId);
+		walk.parseHeaders(ret);
+		return ret;
+	}
+
+	/**
+	 * Create a new in memory dircache which has the same content as a given
+	 * tree.
+	 *
+	 * @param treeId
+	 *            the tree which should be used to fill the dircache
+	 * @return a new in memory dircache
+	 * @throws IOException
+	 */
+	private DirCache dircacheFromTree(ObjectId treeId) throws IOException {
+		DirCache ret = DirCache.newInCore();
+		DirCacheBuilder builder = ret.builder();
+		TreeWalk tw = new TreeWalk(db);
+		tw.addTree(treeId);
+		tw.setRecursive(true);
+		while (tw.next()) {
+			DirCacheEntry e = new DirCacheEntry(tw.getRawPath());
+			e.setFileMode(tw.getFileMode(0));
+			e.setObjectId(tw.getObjectId(0));
+			builder.add(e);
+		}
+		builder.finish();
+		return ret;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/ResolveMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/ResolveMerger.java
index 433458a273..bea2119333 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/ResolveMerger.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/ResolveMerger.java
@@ -1,6 +1,7 @@
 /*
  * Copyright (C) 2010, Christian Halstrick <christian.halstrick@sap.com>,
  * Copyright (C) 2010-2012, Matthias Sohn <matthias.sohn@sap.com>
+ * Copyright (C) 2012, Research In Motion Limited
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -80,6 +81,8 @@ import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.revwalk.RevTree;
+import org.eclipse.jgit.treewalk.AbstractTreeIterator;
 import org.eclipse.jgit.treewalk.CanonicalTreeParser;
 import org.eclipse.jgit.treewalk.NameConflictTreeWalk;
 import org.eclipse.jgit.treewalk.WorkingTreeIterator;
@@ -104,7 +107,10 @@ public class ResolveMerger extends ThreeWayMerger {
 
 	private NameConflictTreeWalk tw;
 
-	private String commitNames[];
+	/**
+	 * string versions of a list of commit SHA1s
+	 */
+	protected String commitNames[];
 
 	private static final int T_BASE = 0;
 
@@ -118,7 +124,10 @@ public class ResolveMerger extends ThreeWayMerger {
 
 	private DirCacheBuilder builder;
 
-	private ObjectId resultTree;
+	/**
+	 * merge result as tree
+	 */
+	protected ObjectId resultTree;
 
 	private List<String> unmergedPaths = new ArrayList<String>();
 
@@ -134,13 +143,38 @@ public class ResolveMerger extends ThreeWayMerger {
 
 	private boolean enterSubtree;
 
-	private boolean inCore;
+	/**
+	 * Set to true if this merge should work in-memory. The repos dircache and
+	 * workingtree are not touched by this method. Eventually needed files are
+	 * created as temporary files and a new empty, in-memory dircache will be
+	 * used instead the repo's one. Often used for bare repos where the repo
+	 * doesn't even have a workingtree and dircache.
+	 */
+	protected boolean inCore;
+
+	/**
+	 * Set to true if this merger should use the default dircache of the
+	 * repository and should handle locking and unlocking of the dircache. If
+	 * this merger should work in-core or if an explicit dircache was specified
+	 * during construction then this field is set to false.
+	 */
+	protected boolean implicitDirCache;
 
-	private DirCache dircache;
+	/**
+	 * Directory cache
+	 */
+	protected DirCache dircache;
 
-	private WorkingTreeIterator workingTreeIterator;
+	/**
+	 * The iterator to access the working tree. If set to <code>null</code> this
+	 * merger will not touch the working tree.
+	 */
+	protected WorkingTreeIterator workingTreeIterator;
 
-	private MergeAlgorithm mergeAlgorithm;
+	/**
+	 * our merge algorithm
+	 */
+	protected MergeAlgorithm mergeAlgorithm;
 
 	/**
 	 * @param local
@@ -153,11 +187,14 @@ public class ResolveMerger extends ThreeWayMerger {
 				ConfigConstants.CONFIG_KEY_ALGORITHM,
 				SupportedAlgorithm.HISTOGRAM);
 		mergeAlgorithm = new MergeAlgorithm(DiffAlgorithm.getAlgorithm(diffAlg));
-		commitNames = new String[] { "BASE", "OURS", "THEIRS" };
+		commitNames = new String[] { "BASE", "OURS", "THEIRS" }; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 		this.inCore = inCore;
 
 		if (inCore) {
+			implicitDirCache = false;
 			dircache = DirCache.newInCore();
+		} else {
+			implicitDirCache = true;
 		}
 	}
 
@@ -170,67 +207,11 @@ public class ResolveMerger extends ThreeWayMerger {
 
 	@Override
 	protected boolean mergeImpl() throws IOException {
-		boolean implicitDirCache = false;
-
-		if (dircache == null) {
+		if (implicitDirCache)
 			dircache = getRepository().lockDirCache();
-			implicitDirCache = true;
-		}
 
 		try {
-			builder = dircache.builder();
-			DirCacheBuildIterator buildIt = new DirCacheBuildIterator(builder);
-
-			tw = new NameConflictTreeWalk(db);
-			tw.addTree(mergeBase());
-			tw.addTree(sourceTrees[0]);
-			tw.addTree(sourceTrees[1]);
-			tw.addTree(buildIt);
-			if (workingTreeIterator != null)
-				tw.addTree(workingTreeIterator);
-
-			while (tw.next()) {
-				if (!processEntry(
-						tw.getTree(T_BASE, CanonicalTreeParser.class),
-						tw.getTree(T_OURS, CanonicalTreeParser.class),
-						tw.getTree(T_THEIRS, CanonicalTreeParser.class),
-						tw.getTree(T_INDEX, DirCacheBuildIterator.class),
-						(workingTreeIterator == null) ? null : tw.getTree(T_FILE, WorkingTreeIterator.class))) {
-					cleanUp();
-					return false;
-				}
-				if (tw.isSubtree() && enterSubtree)
-					tw.enterSubtree();
-			}
-
-			if (!inCore) {
-				// No problem found. The only thing left to be done is to
-				// checkout all files from "theirs" which have been selected to
-				// go into the new index.
-				checkout();
-
-				// All content-merges are successfully done. If we can now write the
-				// new index we are on quite safe ground. Even if the checkout of
-				// files coming from "theirs" fails the user can work around such
-				// failures by checking out the index again.
-				if (!builder.commit()) {
-					cleanUp();
-					throw new IndexWriteException();
-				}
-				builder = null;
-
-			} else {
-				builder.finish();
-				builder = null;
-			}
-
-			if (getUnmergedPaths().isEmpty() && !failed()) {
-				resultTree = dircache.writeTree(getObjectInserter());
-				return true;
-			} else {
-				resultTree = null;
-				return false;
-			}
+			return mergeTrees(mergeBase(), sourceTrees[0], sourceTrees[1]);
 		} finally {
 			if (implicitDirCache)
 				dircache.unlock();
@@ -279,14 +260,15 @@ public class ResolveMerger extends ThreeWayMerger {
 	/**
 	 * Reverts the worktree after an unsuccessful merge. We know that for all
 	 * modified files the old content was in the old index and the index
-	 * contained only stage 0. In case if inCore operation just clear
-	 * the history of modified files.
+	 * contained only stage 0. In case if inCore operation just clear the
+	 * history of modified files.
 	 *
 	 * @throws IOException
 	 * @throws CorruptObjectException
 	 * @throws NoWorkTreeException
 	 */
-	private void cleanUp() throws NoWorkTreeException, CorruptObjectException, IOException {
+	private void cleanUp() throws NoWorkTreeException, CorruptObjectException,
+			IOException {
 		if (inCore) {
 			modifiedFiles.clear();
 			return;
@@ -298,7 +280,10 @@ public class ResolveMerger extends ThreeWayMerger {
 		while(mpathsIt.hasNext()) {
 			String mpath=mpathsIt.next();
 			DirCacheEntry entry = dc.getEntry(mpath);
-			FileOutputStream fos = new FileOutputStream(new File(db.getWorkTree(), mpath));
+			if (entry == null)
+				continue;
+			FileOutputStream fos = new FileOutputStream(new File(
+					db.getWorkTree(), mpath));
 			try {
 				or.open(entry.getObjectId()).copyTo(fos);
 			} finally {
@@ -610,6 +595,9 @@ public class ResolveMerger extends ThreeWayMerger {
 	}
 
 	private boolean isIndexDirty() {
+		if (inCore)
+			return false;
+
 		final int modeI = tw.getRawMode(T_INDEX);
 		final int modeO = tw.getRawMode(T_OURS);
 
@@ -623,7 +611,7 @@ public class ResolveMerger extends ThreeWayMerger {
 	}
 
 	private boolean isWorktreeDirty(WorkingTreeIterator work) {
-		if (inCore || work == null)
+		if (work == null)
 			return false;
 
 		final int modeF = tw.getRawMode(T_FILE);
@@ -862,19 +850,20 @@ public class ResolveMerger extends ThreeWayMerger {
 
 	/**
 	 * Sets the DirCache which shall be used by this merger. If the DirCache is
-	 * not set explicitly this merger will implicitly get and lock a default
-	 * DirCache. If the DirCache is explicitly set the caller is responsible to
-	 * lock it in advance. Finally the merger will call
-	 * {@link DirCache#commit()} which requires that the DirCache is locked. If
-	 * the {@link #mergeImpl()} returns without throwing an exception the lock
-	 * will be released. In case of exceptions the caller is responsible to
-	 * release the lock.
+	 * not set explicitly and if this merger doesn't work in-core, this merger
+	 * will implicitly get and lock a default DirCache. If the DirCache is
+	 * explicitly set the caller is responsible to lock it in advance. Finally
+	 * the merger will call {@link DirCache#commit()} which requires that the
+	 * DirCache is locked. If the {@link #mergeImpl()} returns without throwing
+	 * an exception the lock will be released. In case of exceptions the caller
+	 * is responsible to release the lock.
 	 *
 	 * @param dc
 	 *            the DirCache to set
 	 */
 	public void setDirCache(DirCache dc) {
 		this.dircache = dc;
+		implicitDirCache = false;
 	}
 
 	/**
@@ -891,4 +880,73 @@ public class ResolveMerger extends ThreeWayMerger {
 	public void setWorkingTreeIterator(WorkingTreeIterator workingTreeIterator) {
 		this.workingTreeIterator = workingTreeIterator;
 	}
+
+
+	/**
+	 * The resolve conflict way of three way merging
+	 *
+	 * @param baseTree
+	 * @param headTree
+	 * @param mergeTree
+	 * @return whether the trees merged cleanly
+	 * @throws IOException
+	 */
+	protected boolean mergeTrees(AbstractTreeIterator baseTree,
+			RevTree headTree, RevTree mergeTree) throws IOException {
+
+		builder = dircache.builder();
+		DirCacheBuildIterator buildIt = new DirCacheBuildIterator(builder);
+
+		tw = new NameConflictTreeWalk(db);
+		tw.addTree(baseTree);
+		tw.addTree(headTree);
+		tw.addTree(mergeTree);
+		tw.addTree(buildIt);
+		if (workingTreeIterator != null)
+			tw.addTree(workingTreeIterator);
+
+		while (tw.next()) {
+			if (!processEntry(
+					tw.getTree(T_BASE, CanonicalTreeParser.class),
+					tw.getTree(T_OURS, CanonicalTreeParser.class),
+					tw.getTree(T_THEIRS, CanonicalTreeParser.class),
+					tw.getTree(T_INDEX, DirCacheBuildIterator.class),
+					(workingTreeIterator == null) ? null : tw.getTree(T_FILE,
+							WorkingTreeIterator.class))) {
+				cleanUp();
+				return false;
+			}
+			if (tw.isSubtree() && enterSubtree)
+				tw.enterSubtree();
+		}
+
+		if (!inCore) {
+			// No problem found. The only thing left to be done is to
+			// checkout all files from "theirs" which have been selected to
+			// go into the new index.
+			checkout();
+
+			// All content-merges are successfully done. If we can now write the
+			// new index we are on quite safe ground. Even if the checkout of
+			// files coming from "theirs" fails the user can work around such
+			// failures by checking out the index again.
+			if (!builder.commit()) {
+				cleanUp();
+				throw new IndexWriteException();
+			}
+			builder = null;
+
+		} else {
+			builder.finish();
+			builder = null;
+		}
+
+		if (getUnmergedPaths().isEmpty() && !failed()) {
+			resultTree = dircache.writeTree(getObjectInserter());
+			return true;
+		} else {
+			resultTree = null;
+			return false;
+		}
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/StrategyRecursive.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/StrategyRecursive.java
new file mode 100644
index 0000000000..11c8bca5dd
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/StrategyRecursive.java
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2012, Research In Motion Limited
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.merge;
+
+import org.eclipse.jgit.lib.Repository;
+
+/**
+ * A three-way merge strategy performing a content-merge if necessary
+ */
+public class StrategyRecursive extends StrategyResolve {
+
+	@Override
+	public ThreeWayMerger newMerger(Repository db) {
+		return new RecursiveMerger(db, false);
+	}
+
+	@Override
+	public ThreeWayMerger newMerger(Repository db, boolean inCore) {
+		return new RecursiveMerger(db, inCore);
+	}
+
+	@Override
+	public String getName() {
+		return "recursive";
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/ThreeWayMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/ThreeWayMerger.java
index 521f8963a4..1ad791bb79 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/merge/ThreeWayMerger.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/ThreeWayMerger.java
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2009, Google Inc.
+ * Copyright (C) 2012, Research In Motion Limited
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
@@ -118,6 +119,6 @@ public abstract class ThreeWayMerger extends Merger {
 	protected AbstractTreeIterator mergeBase() throws IOException {
 		if (baseTree != null)
 			return openTree(baseTree);
-		return mergeBase(0, 1);
+		return mergeBase(sourceCommits[0], sourceCommits[1]);
 	}
 }