[JGIT PATCH 0/8] Crude merge support

[JGIT PATCH 0/8] Crude merge support

[Shawn O. Pearce]

This series add some basic merge support to JGit.  Its more of a
"merge toolkit" than a merge implementation.  I have about 200
lines of code in another codebase that calls this stuff in JGit to
actually make a merge.  Eventually I hope to migrate a lot of that
code back into JGit, but for now its not here as I'm not entirely
sure what API merge applications need, and how much of that code
is application specific and how much of it should be core to JGit.

FWIW, that code will be open-sourced soon-ish too.  But I really
think a lot of it belongs in JGit, so it will probably migrate over.

No unit tests yet.  Yea, I know.  I've had this done and in use
for about 3 or 4 weeks now.  I just couldn't find the time to get
the Javadoc cleaned up to post to the list for comments, let alone
write unit tests.

But it does add the missing "write-tree" support to DirCache. :)

Shawn O. Pearce (8):
  Expose the raw path for the current entry of a TreeWalk
  Expose DirCacheEntry.getFileMode as a utility function
  Add writeTree support to DirCache
  Allow a DirCache to be created with no backing store file
  Allow CanonicalTreeParsers to be created with a UTF-8 path prefix
  Recursively load an entire tree into a DirCacheBuilder
  Allow DirCacheEntry instances to be created with stage > 0
  Define a basic merge API, and a two-way tree merge strategy

 .../src/org/spearce/jgit/dircache/DirCache.java    |   37 ++++
 .../org/spearce/jgit/dircache/DirCacheBuilder.java |   58 ++++++
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   61 +++++-
 .../org/spearce/jgit/dircache/DirCacheTree.java    |  115 +++++++++++
 .../spearce/jgit/errors/UnmergedPathException.java |   67 +++++++
 .../src/org/spearce/jgit/lib/FileMode.java         |    7 +
 .../src/org/spearce/jgit/lib/ObjectWriter.java     |   12 +-
 .../src/org/spearce/jgit/merge/MergeStrategy.java  |  134 +++++++++++++
 .../src/org/spearce/jgit/merge/Merger.java         |  207 ++++++++++++++++++++
 .../org/spearce/jgit/merge/StrategyOneSided.java   |   98 +++++++++
 .../jgit/merge/StrategySimpleTwoWayInCore.java     |  179 +++++++++++++++++
 .../jgit/treewalk/AbstractTreeIterator.java        |   31 +++
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   28 +++
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   17 ++-
 14 files changed, 1041 insertions(+), 10 deletions(-)
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/errors/UnmergedPathException.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/MergeStrategy.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/Merger.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/StrategyOneSided.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java

[JGIT PATCH 1/8] Expose the raw path for the current entry of a TreeWalk

[Shawn O. Pearce]

Copying the path byte array (keeping it encoded in UTF-8) is quicker
than converting to String and then back again to UTF-8 when creating
a DirCacheEntry for the current position in a TreeWalk.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   15 +++++++++++++++
 1 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 26544b5..3af3d09 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -582,6 +582,21 @@ public String getPathString() {
 	}
 
 	/**
+	 * Get the current entry's complete path as a UTF-8 byte array.
+	 * 
+	 * @return complete path of the current entry, from the root of the
+	 *         repository. If the current entry is in a subtree there will be at
+	 *         least one '/' in the returned string.
+	 */
+	public byte[] getRawPath() {
+		final AbstractTreeIterator t = currentHead;
+		final int n = t.pathLen;
+		final byte[] r = new byte[n];
+		System.arraycopy(t.path, 0, r, 0, n);
+		return r;
+	}
+
+	/**
 	 * Test if the supplied path matches the current entry's path.
 	 * <p>
 	 * This method tests that the supplied path is exactly equal to the current
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 2/8] Expose DirCacheEntry.getFileMode as a utility function

[Shawn O. Pearce]

Its easier to get the FileMode object in some applications than to
get the raw mode and convert it to the FileMode in the application
code.  Its slower, but sometimes you just have to have the proper
FileMode singleton.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
index cc683d7..355cd3e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
@@ -295,6 +295,15 @@ public int getRawMode() {
 	}
 
 	/**
+	 * Obtain the {@link FileMode} for this entry.
+	 * 
+	 * @return the file mode singleton for this entry.
+	 */
+	public FileMode getFileMode() {
+		return FileMode.fromBits(getRawMode());
+	}
+
+	/**
 	 * Set the file mode for this entry.
 	 *
 	 * @param mode
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 3/8] Add writeTree support to DirCache

[Shawn O. Pearce]

This way we can write a full tree from the DirCache, including reusing
any valid tree entries stored within the 'TREE' cache extension.  By
reusing those entries we can avoid generating the tree objects that
are already stored in the Git repository.

The algorithm may cause up to 3 passes over the DirCache entries:

 * Pass 1: Compute the tree structure
 * Pass 2: Compute the sizes of each tree
 * Pass 3: Write the tree object to the object store

These extra passes cause more CPU time to be expended in exchange
for a lower memory requirement during the tree writing.  The code
is only formatting the lowest level leaf tree which has not yet
been written to the object store, so higher level trees do not
occupy memory while they are waiting for the leaves to write out.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/dircache/DirCache.java    |   20 ++++
 .../org/spearce/jgit/dircache/DirCacheTree.java    |  115 ++++++++++++++++++++
 .../spearce/jgit/errors/UnmergedPathException.java |   67 ++++++++++++
 .../src/org/spearce/jgit/lib/FileMode.java         |    7 ++
 .../src/org/spearce/jgit/lib/ObjectWriter.java     |   12 ++-
 5 files changed, 219 insertions(+), 2 deletions(-)
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/errors/UnmergedPathException.java

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
index 76657c4..b3c57ad 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
@@ -51,8 +51,11 @@
 import java.util.Comparator;
 
 import org.spearce.jgit.errors.CorruptObjectException;
+import org.spearce.jgit.errors.UnmergedPathException;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.LockFile;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.ObjectWriter;
 import org.spearce.jgit.lib.Repository;
 import org.spearce.jgit.util.MutableInteger;
 import org.spearce.jgit.util.NB;
@@ -692,4 +695,21 @@ public DirCacheTree getCacheTree(final boolean build) {
 		}
 		return tree;
 	}
+
+	/**
+	 * Write all index trees to the object store, returning the root tree.
+	 * 
+	 * @param ow
+	 *            the writer to use when serializing to the store.
+	 * @return identity for the root tree.
+	 * @throws UnmergedPathException
+	 *             one or more paths contain higher-order stages (stage > 0),
+	 *             which cannot be stored in a tree object.
+	 * @throws IOException
+	 *             an unexpected error occurred writing to the object store.
+	 */
+	public ObjectId writeTree(final ObjectWriter ow)
+			throws UnmergedPathException, IOException {
+		return getCacheTree(true).writeTree(sortedEntries, 0, 0, ow);
+	}
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheTree.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheTree.java
index 26b6348..cf96ded 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheTree.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheTree.java
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
+ * Copyright (C) 2008, Google Inc.
  *
  * All rights reserved.
  *
@@ -37,14 +38,20 @@
 
 package org.spearce.jgit.dircache;
 
+import static org.spearce.jgit.lib.Constants.OBJECT_ID_LENGTH;
+
+import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.OutputStream;
 import java.nio.ByteBuffer;
 import java.util.Arrays;
 import java.util.Comparator;
 
+import org.spearce.jgit.errors.UnmergedPathException;
 import org.spearce.jgit.lib.Constants;
+import org.spearce.jgit.lib.FileMode;
 import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.ObjectWriter;
 import org.spearce.jgit.util.MutableInteger;
 import org.spearce.jgit.util.RawParseUtils;
 
@@ -273,6 +280,114 @@ public String getPathString() {
 		return r.toString();
 	}
 
+	/**
+	 * Write (if necessary) this tree to the object store.
+	 * 
+	 * @param cache
+	 *            the complete cache from DirCache.
+	 * @param cIdx
+	 *            first position of <code>cache</code> that is a member of this
+	 *            tree. The path of <code>cache[cacheIdx].path</code> for the
+	 *            range <code>[0,pathOff-1)</code> matches the complete path of
+	 *            this tree, from the root of the repository.
+	 * @param pathOffset
+	 *            number of bytes of <code>cache[cacheIdx].path</code> that
+	 *            matches this tree's path. The value at array position
+	 *            <code>cache[cacheIdx].path[pathOff-1]</code> is always '/' if
+	 *            <code>pathOff</code> is > 0.
+	 * @param ow
+	 *            the writer to use when serializing to the store.
+	 * @return identity of this tree.
+	 * @throws UnmergedPathException
+	 *             one or more paths contain higher-order stages (stage > 0),
+	 *             which cannot be stored in a tree object.
+	 * @throws IOException
+	 *             an unexpected error occurred writing to the object store.
+	 */
+	ObjectId writeTree(final DirCacheEntry[] cache, int cIdx,
+			final int pathOffset, final ObjectWriter ow)
+			throws UnmergedPathException, IOException {
+		if (id == null) {
+			final int endIdx = cIdx + entrySpan;
+			final int size = computeSize(cache, cIdx, pathOffset, ow);
+			final ByteArrayOutputStream out = new ByteArrayOutputStream(size);
+			int childIdx = 0;
+			int entryIdx = cIdx;
+
+			while (entryIdx < endIdx) {
+				final DirCacheEntry e = cache[entryIdx];
+				final byte[] ep = e.path;
+				if (childIdx < childCnt) {
+					final DirCacheTree st = children[childIdx];
+					if (st.contains(ep, pathOffset, ep.length)) {
+						FileMode.TREE.copyTo(out);
+						out.write(' ');
+						out.write(st.encodedName);
+						out.write(0);
+						st.id.copyRawTo(out);
+
+						entryIdx += st.entrySpan;
+						childIdx++;
+						continue;
+					}
+				}
+
+				e.getFileMode().copyTo(out);
+				out.write(' ');
+				out.write(ep, pathOffset, ep.length - pathOffset);
+				out.write(0);
+				out.write(e.idBuffer(), e.idOffset(), OBJECT_ID_LENGTH);
+				entryIdx++;
+			}
+
+			id = ow.writeCanonicalTree(out.toByteArray());
+		}
+		return id;
+	}
+
+	private int computeSize(final DirCacheEntry[] cache, int cIdx,
+			final int pathOffset, final ObjectWriter ow)
+			throws UnmergedPathException, IOException {
+		final int endIdx = cIdx + entrySpan;
+		int childIdx = 0;
+		int entryIdx = cIdx;
+		int size = 0;
+
+		while (entryIdx < endIdx) {
+			final DirCacheEntry e = cache[entryIdx];
+			if (e.getStage() != 0)
+				throw new UnmergedPathException(e);
+
+			final byte[] ep = e.path;
+			if (childIdx < childCnt) {
+				final DirCacheTree st = children[childIdx];
+				if (st.contains(ep, pathOffset, ep.length)) {
+					final int stOffset = pathOffset + st.nameLength() + 1;
+					st.writeTree(cache, entryIdx, stOffset, ow);
+
+					size += FileMode.TREE.copyToLength();
+					size += st.nameLength();
+					size += OBJECT_ID_LENGTH + 2;
+
+					entryIdx += st.entrySpan;
+					childIdx++;
+					continue;
+				}
+			}
+
+			final FileMode mode = e.getFileMode();
+			if (mode.getObjectType() == Constants.OBJ_BAD)
+				throw new UnmergedPathException(e);
+
+			size += mode.copyToLength();
+			size += ep.length - pathOffset;
+			size += OBJECT_ID_LENGTH + 2;
+			entryIdx++;
+		}
+
+		return size;
+	}
+
 	private void appendName(final StringBuilder r) {
 		if (parent != null) {
 			parent.appendName(r);
diff --git a/org.spearce.jgit/src/org/spearce/jgit/errors/UnmergedPathException.java b/org.spearce.jgit/src/org/spearce/jgit/errors/UnmergedPathException.java
new file mode 100644
index 0000000..17a3965
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/errors/UnmergedPathException.java
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * 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 Git Development Community 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.spearce.jgit.errors;
+
+import java.io.IOException;
+
+import org.spearce.jgit.dircache.DirCacheEntry;
+
+/**
+ * Indicates one or more paths in a DirCache have non-zero stages present.
+ */
+public class UnmergedPathException extends IOException {
+	private static final long serialVersionUID = 1L;
+
+	private final DirCacheEntry entry;
+
+	/**
+	 * Create a new unmerged path exception.
+	 * 
+	 * @param dce
+	 *            the first non-zero stage of the unmerged path.
+	 */
+	public UnmergedPathException(final DirCacheEntry dce) {
+		super("Unmerged path: " + dce.getPathString());
+		entry = dce;
+	}
+
+	/** @return the first non-zero stage of the unmerged path */
+	public DirCacheEntry getDirCacheEntry() {
+		return entry;
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/FileMode.java b/org.spearce.jgit/src/org/spearce/jgit/lib/FileMode.java
index fe5f2f6..cf42f37 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/FileMode.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/FileMode.java
@@ -191,6 +191,13 @@ public void copyTo(final OutputStream os) throws IOException {
 	}
 
 	/**
+	 * @return the number of bytes written by {@link #copyTo(OutputStream)}.
+	 */
+	public int copyToLength() {
+		return octalBytes.length;
+	}
+
+	/**
 	 * Get the object type that should appear for this type of mode.
 	 * <p>
 	 * See the object type constants in {@link Constants}.
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectWriter.java
index 6c2cd4f..ffa7837 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectWriter.java
@@ -155,10 +155,18 @@ public ObjectId writeTree(final Tree t) throws IOException {
 			o.write(0);
 			id.copyRawTo(o);
 		}
-		return writeTree(o.toByteArray());
+		return writeCanonicalTree(o.toByteArray());
 	}
 
-	private ObjectId writeTree(final byte[] b) throws IOException {
+	/**
+	 * Write a canonical tree to the object database.
+	 *
+	 * @param b
+	 *            the canonical encoding of the tree object.
+	 * @return SHA-1 of the tree
+	 * @throws IOException
+	 */
+	public ObjectId writeCanonicalTree(final byte[] b) throws IOException {
 		return writeTree(b.length, new ByteArrayInputStream(b));
 	}
 
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 4/8] Allow a DirCache to be created with no backing store file

[Shawn O. Pearce]

This permits using a DirCache as a temporary storage area in memory
only, with no chance of it being written out to disk.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/dircache/DirCache.java    |   17 +++++++++++++++++
 1 files changed, 17 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
index b3c57ad..c5a4f91 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
@@ -111,6 +111,17 @@ static int cmp(final byte[] aPath, final int aLen, final byte[] bPath,
 	}
 
 	/**
+	 * Create a new empty index which is never stored on disk.
+	 * 
+	 * @return an empty cache which has no backing store file. The cache may not
+	 *         be read or written, but it may be queried and updated (in
+	 *         memory).
+	 */
+	public static DirCache newInCore() {
+		return new DirCache(null);
+	}
+
+	/**
 	 * Create a new in-core index representation and read an index from disk.
 	 * <p>
 	 * The new index will be read before it is returned to the caller. Read
@@ -297,6 +308,8 @@ void replace(final DirCacheEntry[] e, final int cnt) {
 	 *             library does not support.
 	 */
 	public void read() throws IOException, CorruptObjectException {
+		if (liveFile == null)
+			throw new IOException("DirCache does not have a backing file");
 		if (!liveFile.exists())
 			clear();
 		else if (liveFile.lastModified() != lastModified) {
@@ -407,6 +420,8 @@ private static boolean is_DIRC(final byte[] hdr) {
 	 *             hold the lock.
 	 */
 	public boolean lock() throws IOException {
+		if (liveFile == null)
+			throw new IOException("DirCache does not have a backing file");
 		final LockFile tmp = new LockFile(liveFile);
 		if (tmp.lock()) {
 			tmp.setNeedStatInformation(true);
@@ -515,6 +530,8 @@ public boolean commit() {
 	}
 
 	private void requireLocked(final LockFile tmp) {
+		if (liveFile == null)
+			throw new IllegalStateException("DirCache is not locked");
 		if (tmp == null)
 			throw new IllegalStateException("DirCache "
 					+ liveFile.getAbsolutePath() + " not locked.");
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 5/8] Allow CanonicalTreeParsers to be created with a UTF-8 path prefix

[Shawn O. Pearce]

Creating an iterator with a path prefix permits a tree to be
"mounted" at a different part of a repository, permitting more
sophisticated merge strategies beyond just 1:1 path matching.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/AbstractTreeIterator.java        |   31 ++++++++++++++++++++
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   28 ++++++++++++++++++
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |    2 +-
 3 files changed, 60 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 5226ab6..adfbb11 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -170,6 +170,37 @@ protected AbstractTreeIterator(final String prefix) {
 	}
 
 	/**
+	 * Create a new iterator with no parent and a prefix.
+	 * <p>
+	 * The prefix path supplied is inserted in front of all paths generated by
+	 * this iterator. It is intended to be used when an iterator is being
+	 * created for a subsection of an overall repository and needs to be
+	 * combined with other iterators that are created to run over the entire
+	 * repository namespace.
+	 *
+	 * @param prefix
+	 *            position of this iterator in the repository tree. The value
+	 *            may be null or the empty array to indicate the prefix is the
+	 *            root of the repository. A trailing slash ('/') is
+	 *            automatically appended if the prefix does not end in '/'.
+	 */
+	protected AbstractTreeIterator(final byte[] prefix) {
+		parent = null;
+
+		if (prefix != null && prefix.length > 0) {
+			pathLen = prefix.length;
+			path = new byte[Math.max(DEFAULT_PATH_SIZE, pathLen + 1)];
+			System.arraycopy(prefix, 0, path, 0, pathLen);
+			if (path[pathLen - 1] != '/')
+				path[pathLen++] = '/';
+			pathOffset = pathLen;
+		} else {
+			path = new byte[DEFAULT_PATH_SIZE];
+			pathOffset = 0;
+		}
+	}
+	
+	/**
 	 * Create an iterator for a subtree of an existing iterator.
 	 * 
 	 * @param p
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
index dcc53cd..3dac6dd 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
@@ -62,6 +62,34 @@ public CanonicalTreeParser() {
 		// Nothing necessary.
 	}
 
+	/**
+	 * Create a new parser for a tree appearing in a subset of a repository.
+	 * 
+	 * @param prefix
+	 *            position of this iterator in the repository tree. The value
+	 *            may be null or the empty array to indicate the prefix is the
+	 *            root of the repository. A trailing slash ('/') is
+	 *            automatically appended if the prefix does not end in '/'.
+	 * @param repo
+	 *            repository to load the tree data from.
+	 * @param treeId
+	 *            identity of the tree being parsed; used only in exception
+	 *            messages if data corruption is found.
+	 * @throws MissingObjectException
+	 *             the object supplied is not available from the repository.
+	 * @throws IncorrectObjectTypeException
+	 *             the object supplied as an argument is not actually a tree and
+	 *             cannot be parsed as though it were a tree.
+	 * @throws IOException
+	 *             a loose object or pack file could not be read.
+	 */
+	public CanonicalTreeParser(final byte[] prefix, final Repository repo,
+			final ObjectId treeId) throws IncorrectObjectTypeException,
+			IOException {
+		super(prefix);
+		reset(repo, treeId);
+	}
+
 	private CanonicalTreeParser(final CanonicalTreeParser p) {
 		super(p);
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 3af3d09..b1cbd2d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -307,7 +307,7 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,
 				o = trees[i];
 				while (o.parent != null)
 					o = o.parent;
-				if (o instanceof CanonicalTreeParser) {
+				if (o instanceof CanonicalTreeParser && o.pathOffset == 0) {
 					o.matches = null;
 					o.matchShift = 0;
 					((CanonicalTreeParser) o).reset(db, ids[i]);
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 6/8] Recursively load an entire tree into a DirCacheBuilder

[Shawn O. Pearce]

This implements the DirCache portion of "git read-tree", where a
tree can be recursively read into a DirCache instance without an
impact on the working directory.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/dircache/DirCacheBuilder.java |   58 ++++++++++++++++++++
 1 files changed, 58 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuilder.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuilder.java
index 3a37054..88bda4d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuilder.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuilder.java
@@ -37,8 +37,15 @@
 
 package org.spearce.jgit.dircache;
 
+import java.io.IOException;
 import java.util.Arrays;
 
+import org.spearce.jgit.lib.AnyObjectId;
+import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.treewalk.AbstractTreeIterator;
+import org.spearce.jgit.treewalk.CanonicalTreeParser;
+import org.spearce.jgit.treewalk.TreeWalk;
+
 /**
  * Updates a {@link DirCache} by adding individual {@link DirCacheEntry}s.
  * <p>
@@ -112,6 +119,57 @@ public void keep(final int pos, int cnt) {
 		fastKeep(pos, cnt);
 	}
 
+	/**
+	 * Recursively add an entire tree into this builder.
+	 * <p>
+	 * If pathPrefix is "a/b" and the tree contains file "c" then the resulting
+	 * DirCacheEntry will have the path "a/b/c".
+	 * <p>
+	 * All entries are inserted at stage 0, therefore assuming that the
+	 * application will not insert any other paths with the same pathPrefix.
+	 * 
+	 * @param pathPrefix
+	 *            UTF-8 encoded prefix to mount the tree's entries at. If the
+	 *            path does not end with '/' one will be automatically inserted
+	 *            as necessary.
+	 * @param db
+	 *            repository the tree(s) will be read from during recursive
+	 *            traversal. This must be the same repository that the resulting
+	 *            DirCache would be written out to (or used in) otherwise the
+	 *            caller is simply asking for deferred MissingObjectExceptions.
+	 * @param tree
+	 *            the tree to recursively add. This tree's contents will appear
+	 *            under <code>pathPrefix</code>. The ObjectId must be that of a
+	 *            tree; the caller is responsible for dereferencing a tag or
+	 *            commit (if necessary).
+	 * @throws IOException
+	 *             a tree cannot be read to iterate through its entries.
+	 */
+	public void addTree(final byte[] pathPrefix, final Repository db,
+			final AnyObjectId tree) throws IOException {
+		final TreeWalk tw = new TreeWalk(db);
+		tw.reset();
+		tw.addTree(new CanonicalTreeParser(pathPrefix, db, tree.toObjectId()));
+		tw.setRecursive(true);
+		if (tw.next()) {
+			final DirCacheEntry newEntry = toEntry(tw);
+			beforeAdd(newEntry);
+			fastAdd(newEntry);
+			while (tw.next())
+				fastAdd(toEntry(tw));
+		}
+	}
+
+	private DirCacheEntry toEntry(final TreeWalk tw) {
+		final DirCacheEntry e = new DirCacheEntry(tw.getRawPath());
+		final AbstractTreeIterator i;
+
+		i = tw.getTree(0, AbstractTreeIterator.class);
+		e.setFileMode(tw.getFileMode(0));
+		e.setObjectIdFromRaw(i.idBuffer(), i.idOffset());
+		return e;
+	}
+
 	public void finish() {
 		if (!sorted)
 			resort();
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 7/8] Allow DirCacheEntry instances to be created with stage > 0

[Shawn O. Pearce]

As the stage is part of the sorting criteria for DirCacheEntry
objects we don't allow the stage to be modified on the fly in
an existing instance.  Instead the stage must be set by reading
it from the on-disk format or by creating a new entry with the
proper path and stage components.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   52 +++++++++++++++++---
 1 files changed, 45 insertions(+), 7 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
index 355cd3e..9304501 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
@@ -60,6 +60,18 @@
 public class DirCacheEntry {
 	private static final byte[] nullpad = new byte[8];
 
+	/** The standard (fully merged) stage for an entry. */
+	public static final int STAGE_0 = 0;
+
+	/** The base tree revision for an entry. */
+	public static final int STAGE_1 = 1;
+
+	/** The first tree revision (usually called "ours"). */
+	public static final int STAGE_2 = 2;
+
+	/** The second tree revision (usually called "theirs"). */
+	public static final int STAGE_3 = 3;
+
 	// private static final int P_CTIME = 0;
 
 	// private static final int P_CTIME_NSEC = 4;
@@ -141,8 +153,8 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,
 	}
 
 	/**
-	 * Create an empty entry.
-	 *
+	 * Create an empty entry at stage 0.
+	 * 
 	 * @param newPath
 	 *            name of the cache entry.
 	 */
@@ -151,20 +163,46 @@ public DirCacheEntry(final String newPath) {
 	}
 
 	/**
-	 * Create an empty entry.
-	 *
+	 * Create an empty entry at the specified stage.
+	 * 
+	 * @param newPath
+	 *            name of the cache entry.
+	 * @param stage
+	 *            the stage index of the new entry.
+	 */
+	public DirCacheEntry(final String newPath, final int stage) {
+		this(Constants.encode(newPath), stage);
+	}
+
+	/**
+	 * Create an empty entry at stage 0.
+	 * 
 	 * @param newPath
 	 *            name of the cache entry, in the standard encoding.
 	 */
 	public DirCacheEntry(final byte[] newPath) {
+		this(newPath, STAGE_0);
+	}
+
+	/**
+	 * Create an empty entry at the specified stage.
+	 * 
+	 * @param newPath
+	 *            name of the cache entry, in the standard encoding.
+	 * @param stage
+	 *            the stage index of the new entry.
+	 */
+	public DirCacheEntry(final byte[] newPath, final int stage) {
 		info = new byte[INFO_LEN];
 		infoOffset = 0;
-
 		path = newPath;
+
+		int flags = ((stage & 0x3) << 12);
 		if (path.length < NAME_MASK)
-			NB.encodeInt16(info, infoOffset + P_FLAGS, path.length);
+			flags |= path.length;
 		else
-			NB.encodeInt16(info, infoOffset + P_FLAGS, NAME_MASK);
+			flags |= NAME_MASK;
+		NB.encodeInt16(info, infoOffset + P_FLAGS, flags);
 	}
 
 	void write(final OutputStream os) throws IOException {
-- 
1.6.0.2.706.g340fc

[JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Shawn O. Pearce]

This basic merge implementation is sufficient to merge two commits in
memory and write the result out as a new commit, without having a work
tree on the local filesystem.  It is therefore suitable for use within
a batch server process where human intervention is not available to
resolve conflicts.

This API should permit extending it with the working tree and a copy
of the work tree's DirCache, so edits in the tree can be merged in
parallel with edits from commits.  But the functionality is not yet
implemented, so it is still a pie-in-the-sky concept.

The main strategy "simple-two-way-in-core" provides a basic 3 way
merge on the path level only.  File contents are never patched by
this strategy, making it somewhat safe for automatic merges.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/merge/MergeStrategy.java  |  134 +++++++++++++
 .../src/org/spearce/jgit/merge/Merger.java         |  207 ++++++++++++++++++++
 .../org/spearce/jgit/merge/StrategyOneSided.java   |   98 +++++++++
 .../jgit/merge/StrategySimpleTwoWayInCore.java     |  179 +++++++++++++++++
 4 files changed, 618 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/MergeStrategy.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/Merger.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/StrategyOneSided.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java

diff --git a/org.spearce.jgit/src/org/spearce/jgit/merge/MergeStrategy.java b/org.spearce.jgit/src/org/spearce/jgit/merge/MergeStrategy.java
new file mode 100644
index 0000000..d28dcc1
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/merge/MergeStrategy.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * 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 Git Development Community 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.spearce.jgit.merge;
+
+import java.util.HashMap;
+
+import org.spearce.jgit.lib.Repository;
+
+/**
+ * A method of combining two or more trees together to form an output tree.
+ * <p>
+ * Different strategies may employ different techniques for deciding which paths
+ * (and ObjectIds) to carry from the input trees into the final output tree.
+ */
+public abstract class MergeStrategy {
+	/** Simple strategy that sets the output tree to the first input tree. */
+	public static final MergeStrategy OURS = new StrategyOneSided("ours", 0);
+
+	/** Simple strategy that sets the output tree to the second input tree. */
+	public static final MergeStrategy THEIRS = new StrategyOneSided("theirs", 1);
+
+	/** Simple strategy to merge paths, without simultaneous edits. */
+	public static final MergeStrategy SIMPLE_TWO_WAY_IN_CORE = StrategySimpleTwoWayInCore.INSTANCE;
+
+	private static final HashMap<String, MergeStrategy> STRATEGIES = new HashMap<String, MergeStrategy>();
+
+	static {
+		register(OURS);
+		register(THEIRS);
+		register(SIMPLE_TWO_WAY_IN_CORE);
+	}
+
+	/**
+	 * Register a merge strategy so it can later be obtained by name.
+	 * 
+	 * @param imp
+	 *            the strategy to register.
+	 * @throws IllegalArgumentException
+	 *             a strategy by the same name has already been registered.
+	 */
+	public static void register(final MergeStrategy imp) {
+		register(imp.getName(), imp);
+	}
+
+	/**
+	 * Register a merge strategy so it can later be obtained by name.
+	 * 
+	 * @param name
+	 *            name the strategy can be looked up under.
+	 * @param imp
+	 *            the strategy to register.
+	 * @throws IllegalArgumentException
+	 *             a strategy by the same name has already been registered.
+	 */
+	public static synchronized void register(final String name,
+			final MergeStrategy imp) {
+		if (STRATEGIES.containsKey(name))
+			throw new IllegalArgumentException("Merge strategy \"" + name
+					+ "\" already exists as a default strategy");
+		STRATEGIES.put(name, imp);
+	}
+
+	/**
+	 * Locate a strategy by name.
+	 * 
+	 * @param name
+	 *            name of the strategy to locate.
+	 * @return the strategy instance; null if no strategy matches the name.
+	 */
+	public static synchronized MergeStrategy get(final String name) {
+		return STRATEGIES.get(name);
+	}
+
+	/**
+	 * Get all registered strategies.
+	 * 
+	 * @return the registered strategy instances. No inherit order is returned;
+	 *         the caller may modify (and/or sort) the returned array if
+	 *         necessary to obtain a reasonable ordering.
+	 */
+	public static synchronized MergeStrategy[] get() {
+		final MergeStrategy[] r = new MergeStrategy[STRATEGIES.size()];
+		STRATEGIES.values().toArray(r);
+		return r;
+	}
+
+	/** @return default name of this strategy implementation. */
+	public abstract String getName();
+
+	/**
+	 * Create a new merge instance.
+	 * 
+	 * @param db
+	 *            repository database the merger will read from, and eventually
+	 *            write results back to.
+	 * @return the new merge instance which implements this strategy.
+	 */
+	public abstract Merger newMerger(Repository db);
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/merge/Merger.java b/org.spearce.jgit/src/org/spearce/jgit/merge/Merger.java
new file mode 100644
index 0000000..fb8d7b2
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/merge/Merger.java
@@ -0,0 +1,207 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * 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 Git Development Community 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.spearce.jgit.merge;
+
+import java.io.IOException;
+
+import org.spearce.jgit.errors.IncorrectObjectTypeException;
+import org.spearce.jgit.lib.AnyObjectId;
+import org.spearce.jgit.lib.Constants;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.ObjectWriter;
+import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.revwalk.RevCommit;
+import org.spearce.jgit.revwalk.RevObject;
+import org.spearce.jgit.revwalk.RevTree;
+import org.spearce.jgit.revwalk.RevWalk;
+import org.spearce.jgit.revwalk.filter.RevFilter;
+import org.spearce.jgit.treewalk.AbstractTreeIterator;
+import org.spearce.jgit.treewalk.CanonicalTreeParser;
+import org.spearce.jgit.treewalk.EmptyTreeIterator;
+
+/**
+ * Instance of a specific {@link MergeStrategy} for a single {@link Repository}.
+ */
+public abstract class Merger {
+	/** The repository this merger operates on. */
+	protected final Repository db;
+
+	/** A RevWalk for computing merge bases, or listing incoming commits. */
+	protected final RevWalk walk;
+
+	private ObjectWriter writer;
+
+	/** The original objects supplied in the merge; this can be any tree-ish. */
+	protected RevObject[] sourceObjects;
+
+	/** If {@link #sourceObjects}[i] is a commit, this is the commit. */
+	protected RevCommit[] sourceCommits;
+
+	/** The trees matching every entry in {@link #sourceObjects}. */
+	protected RevTree[] sourceTrees;
+
+	/**
+	 * Create a new merge instance for a repository.
+	 * 
+	 * @param local
+	 *            the repository this merger will read and write data on.
+	 */
+	protected Merger(final Repository local) {
+		db = local;
+		walk = new RevWalk(db);
+	}
+
+	/**
+	 * @return the repository this merger operates on.
+	 */
+	public Repository getRepository() {
+		return db;
+	}
+
+	/**
+	 * @return an object writer to create objects in {@link #getRepository()}.
+	 */
+	public ObjectWriter getObjectWriter() {
+		if (writer == null)
+			writer = new ObjectWriter(getRepository());
+		return writer;
+	}
+
+	/**
+	 * Merge together two or more tree-ish objects.
+	 * <p>
+	 * Any tree-ish may be supplied as inputs. Commits and/or tags pointing at
+	 * trees or commits may be passed as input objects.
+	 * 
+	 * @param tips
+	 *            source trees to be combined together. The merge base is not
+	 *            included in this set.
+	 * @return true if the merge was completed without conflicts; false if the
+	 *         merge strategy cannot handle this merge or there were conflicts
+	 *         preventing it from automatically resolving all paths.
+	 * @throws IncorrectObjectTypeException
+	 *             one of the input objects is not a commit, but the strategy
+	 *             requires it to be a commit.
+	 * @throws IOException
+	 *             one or more sources could not be read, or outputs could not
+	 *             be written to the Repository.
+	 */
+	public final boolean merge(final AnyObjectId[] tips) throws IOException {
+		sourceObjects = new RevObject[tips.length];
+		for (int i = 0; i < tips.length; i++)
+			sourceObjects[i] = walk.parseAny(tips[i]);
+
+		sourceCommits = new RevCommit[sourceObjects.length];
+		for (int i = 0; i < sourceObjects.length; i++) {
+			try {
+				sourceCommits[i] = walk.parseCommit(sourceObjects[i]);
+			} catch (IncorrectObjectTypeException err) {
+				sourceCommits[i] = null;
+			}
+		}
+
+		sourceTrees = new RevTree[sourceObjects.length];
+		for (int i = 0; i < sourceObjects.length; i++)
+			sourceTrees[i] = walk.parseTree(sourceObjects[i]);
+
+		return mergeImpl();
+	}
+
+	/**
+	 * 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}.
+	 * @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)
+			throws IOException {
+		if (sourceCommits[aIdx] == null)
+			throw new IncorrectObjectTypeException(sourceObjects[aIdx],
+					Constants.TYPE_COMMIT);
+		if (sourceCommits[bIdx] == null)
+			throw new IncorrectObjectTypeException(sourceObjects[bIdx],
+					Constants.TYPE_COMMIT);
+
+		walk.reset();
+		walk.setRevFilter(RevFilter.MERGE_BASE);
+		walk.markStart(sourceCommits[aIdx]);
+		walk.markStart(sourceCommits[bIdx]);
+		final RevCommit base = walk.next();
+		if (base == null)
+			return new EmptyTreeIterator();
+		final RevCommit base2 = walk.next();
+		if (base2 != null) {
+			throw new IOException("Multiple merge bases for:" + "\n  "
+					+ sourceCommits[aIdx].name() + "\n  "
+					+ sourceCommits[bIdx].name() + "found:" + "\n  "
+					+ base.name() + "\n  " + base2.name());
+		}
+		return new CanonicalTreeParser(null, db, base.getTree());
+	}
+
+	/**
+	 * Execute the merge.
+	 * <p>
+	 * This method is called from {@link #merge(AnyObjectId[])} after the
+	 * {@link #sourceObjects}, {@link #sourceCommits} and {@link #sourceTrees}
+	 * have been populated.
+	 * 
+	 * @return true if the merge was completed without conflicts; false if the
+	 *         merge strategy cannot handle this merge or there were conflicts
+	 *         preventing it from automatically resolving all paths.
+	 * @throws IncorrectObjectTypeException
+	 *             one of the input objects is not a commit, but the strategy
+	 *             requires it to be a commit.
+	 * @throws IOException
+	 *             one or more sources could not be read, or outputs could not
+	 *             be written to the Repository.
+	 */
+	protected abstract boolean mergeImpl() throws IOException;
+
+	/**
+	 * @return resulting tree, if {@link #merge(AnyObjectId[])} returned true.
+	 */
+	public abstract ObjectId getResultTreeId();
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/merge/StrategyOneSided.java b/org.spearce.jgit/src/org/spearce/jgit/merge/StrategyOneSided.java
new file mode 100644
index 0000000..0c3dcc2
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/merge/StrategyOneSided.java
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * 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 Git Development Community 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.spearce.jgit.merge;
+
+import java.io.IOException;
+
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.Repository;
+
+/**
+ * Trivial merge strategy to make the resulting tree exactly match an input.
+ * <p>
+ * This strategy can be used to cauterize an entire side branch of history, by
+ * setting the output tree to one of the inputs, and ignoring any of the paths
+ * of the other inputs.
+ */
+public class StrategyOneSided extends MergeStrategy {
+	private final String strategyName;
+
+	private final int treeIndex;
+
+	/**
+	 * Create a new merge strategy to select a specific input tree.
+	 * 
+	 * @param name
+	 *            name of this strategy.
+	 * @param index
+	 *            the position of the input tree to accept as the result.
+	 */
+	protected StrategyOneSided(final String name, final int index) {
+		strategyName = name;
+		treeIndex = index;
+	}
+
+	@Override
+	public String getName() {
+		return strategyName;
+	}
+
+	@Override
+	public Merger newMerger(final Repository db) {
+		return new OneSide(db, treeIndex);
+	}
+
+	protected static class OneSide extends Merger {
+		private final int treeIndex;
+
+		protected OneSide(final Repository local, final int index) {
+			super(local);
+			treeIndex = index;
+		}
+
+		@Override
+		protected boolean mergeImpl() throws IOException {
+			return treeIndex < sourceTrees.length;
+		}
+
+		@Override
+		public ObjectId getResultTreeId() {
+			return sourceTrees[treeIndex];
+		}
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java b/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java
new file mode 100644
index 0000000..893add9
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java
@@ -0,0 +1,179 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * 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 Git Development Community 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.spearce.jgit.merge;
+
+import java.io.IOException;
+
+import org.spearce.jgit.dircache.DirCache;
+import org.spearce.jgit.dircache.DirCacheBuilder;
+import org.spearce.jgit.dircache.DirCacheEntry;
+import org.spearce.jgit.errors.UnmergedPathException;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.treewalk.AbstractTreeIterator;
+import org.spearce.jgit.treewalk.NameConflictTreeWalk;
+
+/**
+ * Merges two commits together in-memory, ignoring any working directory.
+ * <p>
+ * The strategy chooses a path from one of the two input trees if the path is
+ * unchanged in the other relative to their common merge base tree. This is a
+ * trivial 3-way merge (at the file path level only).
+ * <p>
+ * Modifications of the same file path (content and/or file mode) by both input
+ * trees will cause a merge conflict, as this strategy does not attempt to merge
+ * file contents.
+ */
+public class StrategySimpleTwoWayInCore extends MergeStrategy {
+	static final MergeStrategy INSTANCE = new StrategySimpleTwoWayInCore();
+
+	/** Create a new instance of the strategy. */
+	protected StrategySimpleTwoWayInCore() {
+		//
+	}
+
+	@Override
+	public String getName() {
+		return "simple-two-way-in-core";
+	}
+
+	@Override
+	public Merger newMerger(final Repository db) {
+		return new InCoreMerger(db);
+	}
+
+	private static class InCoreMerger extends Merger {
+		private static final int T_BASE = 0;
+
+		private static final int T_OURS = 1;
+
+		private static final int T_THEIRS = 2;
+
+		private final NameConflictTreeWalk tw;
+
+		private final DirCache cache;
+
+		private DirCacheBuilder builder;
+
+		private ObjectId resultTree;
+
+		InCoreMerger(final Repository local) {
+			super(local);
+			tw = new NameConflictTreeWalk(db);
+			cache = DirCache.newInCore();
+		}
+
+		@Override
+		protected boolean mergeImpl() throws IOException {
+			if (sourceTrees.length != 2)
+				return false;
+
+			tw.reset();
+			tw.addTree(mergeBase(0, 1));
+			tw.addTree(sourceTrees[0]);
+			tw.addTree(sourceTrees[1]);
+
+			boolean hasConflict = false;
+			builder = cache.builder();
+			while (tw.next()) {
+				final int modeO = tw.getRawMode(T_OURS);
+				final int modeT = tw.getRawMode(T_THEIRS);
+				if (modeO == modeT && tw.idEqual(T_OURS, T_THEIRS)) {
+					same();
+					continue;
+				}
+
+				final int modeB = tw.getRawMode(T_BASE);
+				if (modeB == modeO && tw.idEqual(T_BASE, T_OURS))
+					add(T_THEIRS, DirCacheEntry.STAGE_0);
+				else if (modeB == modeT && tw.idEqual(T_BASE, T_THEIRS))
+					add(T_OURS, DirCacheEntry.STAGE_0);
+				else {
+					conflict();
+					hasConflict = true;
+				}
+			}
+			builder.finish();
+			builder = null;
+
+			if (hasConflict)
+				return false;
+			try {
+				resultTree = cache.writeTree(getObjectWriter());
+				return true;
+			} catch (UnmergedPathException upe) {
+				resultTree = null;
+				return false;
+			}
+		}
+
+		private void same() throws IOException {
+			if (tw.isSubtree())
+				builder.addTree(tw.getRawPath(), db, tw.getObjectId(1));
+			else
+				add(T_OURS, DirCacheEntry.STAGE_0);
+		}
+
+		private void conflict() {
+			add(T_BASE, DirCacheEntry.STAGE_1);
+			add(T_OURS, DirCacheEntry.STAGE_2);
+			add(T_THEIRS, DirCacheEntry.STAGE_3);
+		}
+
+		private void add(final int tree, final int stage) {
+			final AbstractTreeIterator i = getTree(tree);
+			if (i != null) {
+				final DirCacheEntry e;
+
+				e = new DirCacheEntry(tw.getRawPath(), stage);
+				e.setObjectIdFromRaw(i.idBuffer(), i.idOffset());
+				e.setFileMode(tw.getFileMode(tree));
+				builder.add(e);
+			}
+		}
+
+		private AbstractTreeIterator getTree(final int tree) {
+			return tw.getTree(tree, AbstractTreeIterator.class);
+		}
+
+		@Override
+		public ObjectId getResultTreeId() {
+			return resultTree;
+		}
+	}
+}
-- 
1.6.0.2.706.g340fc

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Robin Rosenberg]

Hi, Shawn

Shouldn't testTrivialTwoWay_disjointhistories()  work?

The two trees have nothing in common and so should be trivially mergeable.

-- robin

>From cef2695431e368da616a1e9c8de3e5e419854a4c Mon Sep 17 00:00:00 2001
From: Robin Rosenberg <robin.rosenberg@dewire.com>
Date: Thu, 23 Oct 2008 23:09:10 +0200
Subject: [EGIT PATCH] Simple merge test

---
 .../org/spearce/jgit/merge/SimpleMergeTest.java    |   28 ++++++++++++++++++++
 1 files changed, 28 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java
new file mode 100644
index 0000000..8ec1c7f
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java
@@ -0,0 +1,28 @@
+package org.spearce.jgit.merge;
+
+import java.io.IOException;
+
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.RepositoryTestCase;
+
+public class SimpleMergeTest extends RepositoryTestCase {
+
+	public void testTrivialTwoWay_noway() throws IOException {
+		Merger ourMerger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(db);
+		boolean merge = ourMerger.merge(new ObjectId[] { db.resolve("a"), db.resolve("c") });
+		assertFalse(merge);
+	}
+
+	public void testTrivialTwoWay_disjointhistories() throws IOException {
+		Merger ourMerger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(db);
+		boolean merge = ourMerger.merge(new ObjectId[] { db.resolve("a"), db.resolve("c~4") });
+		assertTrue(merge); 
+	}
+
+	public void testTrivialTwoWay_ok() throws IOException {
+		Merger ourMerger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(db);
+		boolean merge = ourMerger.merge(new ObjectId[] { db.resolve("a^0^0^0"), db.resolve("a^0^0^1") });
+		assertTrue(merge);
+		assertEquals(db.mapTree("a^0^0").getId(), ourMerger.getResultTreeId());
+	}
+}
-- 
1.6.0.2.308.gef4a

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Robin Rosenberg]

I never got a  received reply... on this.

-- robin

torsdag 23 oktober 2008 23:14:29 skrev Robin Rosenberg:
> Hi, Shawn
> 
> Shouldn't testTrivialTwoWay_disjointhistories()  work?
> 
> The two trees have nothing in common and so should be trivially mergeable.
> 
> -- robin
> 
> From cef2695431e368da616a1e9c8de3e5e419854a4c Mon Sep 17 00:00:00 2001
> From: Robin Rosenberg <robin.rosenberg@dewire.com>
> Date: Thu, 23 Oct 2008 23:09:10 +0200
> Subject: [EGIT PATCH] Simple merge test
> 
> ---
>  .../org/spearce/jgit/merge/SimpleMergeTest.java    |   28 ++++++++++++++++++++
>  1 files changed, 28 insertions(+), 0 deletions(-)
>  create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java
> 
> diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java
> new file mode 100644
> index 0000000..8ec1c7f
> --- /dev/null
> +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java
> @@ -0,0 +1,28 @@
> +package org.spearce.jgit.merge;
> +
> +import java.io.IOException;
> +
> +import org.spearce.jgit.lib.ObjectId;
> +import org.spearce.jgit.lib.RepositoryTestCase;
> +
> +public class SimpleMergeTest extends RepositoryTestCase {
> +
> +	public void testTrivialTwoWay_noway() throws IOException {
> +		Merger ourMerger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(db);
> +		boolean merge = ourMerger.merge(new ObjectId[] { db.resolve("a"), db.resolve("c") });
> +		assertFalse(merge);
> +	}
> +
> +	public void testTrivialTwoWay_disjointhistories() throws IOException {
> +		Merger ourMerger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(db);
> +		boolean merge = ourMerger.merge(new ObjectId[] { db.resolve("a"), db.resolve("c~4") });
> +		assertTrue(merge); 
> +	}
> +
> +	public void testTrivialTwoWay_ok() throws IOException {
> +		Merger ourMerger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(db);
> +		boolean merge = ourMerger.merge(new ObjectId[] { db.resolve("a^0^0^0"), db.resolve("a^0^0^1") });
> +		assertTrue(merge);
> +		assertEquals(db.mapTree("a^0^0").getId(), ourMerger.getResultTreeId());
> +	}
> +}

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Shawn O. Pearce]

Robin Rosenberg <robin.rosenberg@dewire.com> wrote:
> I never got a  received reply... on this.

Sorry.  Its in my "pending" queue.  I'm still using the code
in Gerrit but I've been so swamped that I haven't been able to
look at your test case, or what's wrong with the code and why it
doesn't pass.

I honestly hoped to have something by this point, but I got behind
and I haven't quite had a chance to look at it.
 
> torsdag 23 oktober 2008 23:14:29 skrev Robin Rosenberg:
> > Hi, Shawn
> > 
> > Shouldn't testTrivialTwoWay_disjointhistories()  work?
> > 
> > The two trees have nothing in common and so should be trivially mergeable.
> > 
> > -- robin
> > 
> > From cef2695431e368da616a1e9c8de3e5e419854a4c Mon Sep 17 00:00:00 2001
> > From: Robin Rosenberg <robin.rosenberg@dewire.com>
> > Date: Thu, 23 Oct 2008 23:09:10 +0200
> > Subject: [EGIT PATCH] Simple merge test
> > 
> > ---
> >  .../org/spearce/jgit/merge/SimpleMergeTest.java    |   28 ++++++++++++++++++++
> >  1 files changed, 28 insertions(+), 0 deletions(-)
> >  create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/merge/SimpleMergeTest.java

-- 
Shawn.

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Tomi Pakarinen]

testTrivialTwoWay_disjointhistories() failed because merge strategy
didn't handle missing base
version. Am'i right?

  Tomi.

>From 1ed694b55d307c640d29eeebfcd108e08681297b Mon Sep 17 00:00:00 2001
From: Tomi Pakarinen <tomi.pakarinen@iki.fi>
Date: Sat, 17 Jan 2009 20:56:04 +0200
Subject: [PATCH] If base version missing, we can merge version from
one of other trees.

Signed-off-by: Tomi Pakarinen <tomi.pakarinen@iki.fi>
---
 .../jgit/merge/StrategySimpleTwoWayInCore.java     |   28 +++++++++++++++-----
 1 files changed, 21 insertions(+), 7 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java
b/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java
index 893add9..eb718ab 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/merge/StrategySimpleTwoWayInCore.java
@@ -43,6 +43,7 @@
 import org.spearce.jgit.dircache.DirCacheBuilder;
 import org.spearce.jgit.dircache.DirCacheEntry;
 import org.spearce.jgit.errors.UnmergedPathException;
+import org.spearce.jgit.lib.FileMode;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.Repository;
 import org.spearce.jgit.treewalk.AbstractTreeIterator;
@@ -119,13 +120,26 @@ protected boolean mergeImpl() throws IOException {
 				}

 				final int modeB = tw.getRawMode(T_BASE);
-				if (modeB == modeO && tw.idEqual(T_BASE, T_OURS))
-					add(T_THEIRS, DirCacheEntry.STAGE_0);
-				else if (modeB == modeT && tw.idEqual(T_BASE, T_THEIRS))
-					add(T_OURS, DirCacheEntry.STAGE_0);
-				else {
-					conflict();
-					hasConflict = true;
+				if (!FileMode.MISSING.equals(modeB)) {
+					if (modeB == modeO && tw.idEqual(T_BASE, T_OURS))
+						add(T_THEIRS, DirCacheEntry.STAGE_0);
+					else if (modeB == modeT && tw.idEqual(T_BASE, T_THEIRS))
+						add(T_OURS, DirCacheEntry.STAGE_0);
+					else {
+						conflict();
+						hasConflict = true;
+					}
+				} else {
+					if (!FileMode.MISSING.equals(modeO)
+							&& FileMode.MISSING.equals(modeT))
+						add(T_OURS, DirCacheEntry.STAGE_0);
+					else if (FileMode.MISSING.equals(modeO)
+							&& !FileMode.MISSING.equals(modeT))
+						add(T_THEIRS, DirCacheEntry.STAGE_0);
+					else {
+						conflict();
+						hasConflict = true;
+					}
 				}
 			}
 			builder.finish();
-- 
1.6.0.4

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Robin Rosenberg]

lördag 17 januari 2009 20:16:21 skrev Tomi Pakarinen:
> testTrivialTwoWay_disjointhistories() failed because merge strategy
> didn't handle missing base
> version. Am'i right?
Kyllä

Or so it seems. My test cases pass. I'll see if I can come up with somehing nasty.
If not I'll apply 

-- robin

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Shawn O. Pearce]

Tomi Pakarinen <tomi.pakarinen@gmail.com> wrote:
> testTrivialTwoWay_disjointhistories() failed because merge strategy
> didn't handle missing base
> version. Am'i right?

I don't think so.
 
> @@ -119,13 +120,26 @@ protected boolean mergeImpl() throws IOException {
>  				}
> 
>  				final int modeB = tw.getRawMode(T_BASE);

Under a missing base condition modeB == 0.  So,

> -				if (modeB == modeO && tw.idEqual(T_BASE, T_OURS))
> -					add(T_THEIRS, DirCacheEntry.STAGE_0);

If modeB == 0 and modeO == 0 its not in the base and its not in ours.
Both SHA-1s will be 0{40} and are thus idEqual, so we should enter
this add(T_THEIRS) block.  Which is what you tried to write below in
your else block, isn't it?.

> -				else if (modeB == modeT && tw.idEqual(T_BASE, T_THEIRS))
> -					add(T_OURS, DirCacheEntry.STAGE_0);

Again, if modeB == 0 and modeT == 0 both SHA-1s will be 0{40} and
are idEqual, so we should enter this add(T_OURS) block if both base
and theirs are missing.  Which again is what you tried to write in
your else block.

If that isn't coming out right then perhaps tw.idEqual() is busted
for when FileMode is FileMode.MISSING (aka 0).  Granted, doing
idEqual on FileMode.MISSING is pointless and just wastes clock
cycles, but it shouldn't harm the algorithm's correctness.

> -				else {
> -					conflict();
> -					hasConflict = true;
> +				if (!FileMode.MISSING.equals(modeB)) {
> +					if (modeB == modeO && tw.idEqual(T_BASE, T_OURS))
> +						add(T_THEIRS, DirCacheEntry.STAGE_0);
> +					else if (modeB == modeT && tw.idEqual(T_BASE, T_THEIRS))
> +						add(T_OURS, DirCacheEntry.STAGE_0);
> +					else {
> +						conflict();
> +						hasConflict = true;
> +					}
> +				} else {
> +					if (!FileMode.MISSING.equals(modeO)
> +							&& FileMode.MISSING.equals(modeT))
> +						add(T_OURS, DirCacheEntry.STAGE_0);
> +					else if (FileMode.MISSING.equals(modeO)
> +							&& !FileMode.MISSING.equals(modeT))
> +						add(T_THEIRS, DirCacheEntry.STAGE_0);
> +					else {
> +						conflict();
> +						hasConflict = true;
> +					}
>  				}
>  			}
>  			builder.finish();
> -- 
> 1.6.0.4

-- 
Shawn.

Re: [JGIT PATCH 8/8] Define a basic merge API, and a two-way tree merge strategy

[Shawn O. Pearce]

"Shawn O. Pearce" <spearce@spearce.org> wrote:
> Tomi Pakarinen <tomi.pakarinen@gmail.com> wrote:
> > testTrivialTwoWay_disjointhistories() failed because merge strategy
> > didn't handle missing base
> > version. Am'i right?
> 
> If that isn't coming out right then perhaps tw.idEqual() is busted

Yup, that's what it is, idEqual is busted.

The definition of TreeWalk.idEqual is:

	public boolean idEqual(final int nthA, final int nthB) {
		final AbstractTreeIterator ch = currentHead;
		final AbstractTreeIterator a = trees[nthA];
		final AbstractTreeIterator b = trees[nthB];
		return a.matches == ch && b.matches == ch && a.idEqual(b);
	}

The problem is this method always returns false if the name isn't
defined in either path.  I think this is the definition we want
instead:

		if (a.matches == ch && b.matches == ch)
			return a.idEqual(b);
		if (a.matches != ch && b.matches != ch) {
			// If neither tree matches the current path node then neither
			// tree has this entry. In such case the ObjectId is zero(),
			// and zero() is always equal to zero().
			//
			return true;
		}
		return false;

Patch to follow.

-- 
Shawn.