Add file content merge algorithm

Adds the file content merge alorithm and tests for merge to jgit.
The merge algorithm:

- Gets as input parameters the common base, the two new contents
  called "ours" and "theirs".

- Computes the Edits from base to ours and from base to theirs with
  the help of MyersDiff.

- Iterates over the edits.

- Independent edits from ours or from theirs will just be applied
  to the result.

- For conflicting edits we first harmonize the ranges of the edits
  so that in the end we have exactly two edits starting and ending
  at the same points in the common base. Then we write the two
  conclicting contents into the result stream.

Change-Id: I411862393e7bf416b6f33ca55ec5af608ff4663
Signed-off-by: Christian Halstrick <christian.halstrick@sap.com>
[sp: Fixed up two awkard comments in documentation.]
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

4 files changed, 688 insertions, 0 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
new file mode 100644
index 0000000000..deae82e762
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeAlgorithm.java
@@ -0,0 +1,230 @@
+/*
+ * Copyright (C) 2009, 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.merge;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.jgit.diff.Edit;
+import org.eclipse.jgit.diff.EditList;
+import org.eclipse.jgit.diff.MyersDiff;
+import org.eclipse.jgit.diff.Sequence;
+import org.eclipse.jgit.merge.MergeChunk.ConflictState;
+
+/**
+ * Provides the merge algorithm which does a three-way merge on content provided
+ * as RawText. Makes use of {@link MyersDiff} to compute the diffs.
+ */
+public final class MergeAlgorithm {
+
+	/**
+	 * Since this class provides only static methods I add a private default
+	 * constructor to prevent instantiation.
+	 */
+	private MergeAlgorithm() {
+	}
+
+	// An special edit which acts as a sentinel value by marking the end the
+	// list of edits
+	private final static Edit END_EDIT = new Edit(Integer.MAX_VALUE,
+			Integer.MAX_VALUE);
+
+	/**
+	 * Does the three way merge between a common base and two sequences.
+	 *
+	 * @param base the common base sequence
+	 * @param ours the first sequence to be merged
+	 * @param theirs the second sequence to be merged
+	 * @return the resulting content
+	 */
+	public static MergeResult merge(Sequence base, Sequence ours,
+			Sequence theirs) {
+		List<Sequence> sequences = new ArrayList<Sequence>(3);
+		sequences.add(base);
+		sequences.add(ours);
+		sequences.add(theirs);
+		MergeResult result = new MergeResult(sequences);
+		EditList oursEdits = new MyersDiff(base, ours).getEdits();
+		Iterator<Edit> baseToOurs = oursEdits.iterator();
+		EditList theirsEdits = new MyersDiff(base, theirs).getEdits();
+		Iterator<Edit> baseToTheirs = theirsEdits.iterator();
+		int current = 0; // points to the next line (first line is 0) of base
+		                 // which was not handled yet
+		Edit oursEdit = nextEdit(baseToOurs);
+		Edit theirsEdit = nextEdit(baseToTheirs);
+
+		// iterate over all edits from base to ours and from base to theirs
+		// leave the loop when there are no edits more for ours or for theirs
+		// (or both)
+		while (theirsEdit != END_EDIT || oursEdit != END_EDIT) {
+			if (oursEdit.getEndA() <= theirsEdit.getBeginA()) {
+				// something was changed in ours not overlapping with any change
+				// from theirs. First add the common part in front of the edit
+				// then the edit.
+				if (current != oursEdit.getBeginA()) {
+					result.add(0, current, oursEdit.getBeginA(),
+							ConflictState.NO_CONFLICT);
+				}
+				result.add(1, oursEdit.getBeginB(), oursEdit.getEndB(),
+						ConflictState.NO_CONFLICT);
+				current = oursEdit.getEndA();
+				oursEdit = nextEdit(baseToOurs);
+			} else if (theirsEdit.getEndA() <= oursEdit.getBeginA()) {
+				// something was changed in theirs not overlapping with any
+				// from ours. First add the common part in front of the edit
+				// then the edit.
+				if (current != theirsEdit.getBeginA()) {
+					result.add(0, current, theirsEdit.getBeginA(),
+							ConflictState.NO_CONFLICT);
+				}
+				result.add(2, theirsEdit.getBeginB(), theirsEdit.getEndB(),
+						ConflictState.NO_CONFLICT);
+				current = theirsEdit.getEndA();
+				theirsEdit = nextEdit(baseToTheirs);
+			} else {
+				// here we found a real overlapping modification
+
+				// if there is a common part in front of the conflict add it
+				if (oursEdit.getBeginA() != current
+						&& theirsEdit.getBeginA() != current) {
+					result.add(0, current, Math.min(oursEdit.getBeginA(),
+							theirsEdit.getBeginA()), ConflictState.NO_CONFLICT);
+				}
+
+				// set some initial values for the ranges in A and B which we
+				// want to handle
+				int oursBeginB = oursEdit.getBeginB();
+				int theirsBeginB = theirsEdit.getBeginB();
+				// harmonize the start of the ranges in A and B
+				if (oursEdit.getBeginA() < theirsEdit.getBeginA()) {
+					theirsBeginB -= theirsEdit.getBeginA()
+							- oursEdit.getBeginA();
+				} else {
+					oursBeginB -= oursEdit.getBeginA() - theirsEdit.getBeginA();
+				}
+
+				// combine edits:
+				// Maybe an Edit on one side corresponds to multiple Edits on
+				// the other side. Then we have to combine the Edits of the
+				// other side - so in the end we can merge together two single
+				// edits.
+				//
+				// It is important to notice that this combining will extend the
+				// ranges of our conflict always downwards (towards the end of
+				// the content). The starts of the conflicting ranges in ours
+				// and theirs are not touched here.
+				//
+				// This combining is an iterative process: after we have
+				// combined some edits we have to do the check again. The
+				// combined edits could now correspond to multiple edits on the
+				// other side.
+				//
+				// Example: when this combining algorithm works on the following
+				// edits
+				// oursEdits=((0-5,0-5),(6-8,6-8),(10-11,10-11)) and
+				// theirsEdits=((0-1,0-1),(2-3,2-3),(5-7,5-7))
+				// it will merge them into
+				// oursEdits=((0-8,0-8),(10-11,10-11)) and
+				// theirsEdits=((0-7,0-7))
+				//
+				// Since the only interesting thing to us is how in ours and
+				// theirs the end of the conflicting range is changing we let
+				// oursEdit and theirsEdit point to the last conflicting edit
+				Edit nextOursEdit = nextEdit(baseToOurs);
+				Edit nextTheirsEdit = nextEdit(baseToTheirs);
+				for (;;) {
+					if (oursEdit.getEndA() > nextTheirsEdit.getBeginA()) {
+						theirsEdit = nextTheirsEdit;
+						nextTheirsEdit = nextEdit(baseToTheirs);
+					} else if (theirsEdit.getEndA() > nextOursEdit.getBeginA()) {
+						oursEdit = nextOursEdit;
+						nextOursEdit = nextEdit(baseToOurs);
+					} else {
+						break;
+					}
+				}
+
+				// harmonize the end of the ranges in A and B
+				int oursEndB = oursEdit.getEndB();
+				int theirsEndB = theirsEdit.getEndB();
+				if (oursEdit.getEndA() < theirsEdit.getEndA()) {
+					oursEndB += theirsEdit.getEndA() - oursEdit.getEndA();
+				} else {
+					theirsEndB += oursEdit.getEndA() - theirsEdit.getEndA();
+				}
+
+				// Add the conflict
+				result.add(1, oursBeginB, oursEndB,
+						ConflictState.FIRST_CONFLICTING_RANGE);
+				result.add(2, theirsBeginB, theirsEndB,
+						ConflictState.NEXT_CONFLICTING_RANGE);
+
+				current = Math.max(oursEdit.getEndA(), theirsEdit.getEndA());
+				oursEdit = nextOursEdit;
+				theirsEdit = nextTheirsEdit;
+			}
+		}
+		// maybe we have a common part behind the last edit: copy it to the
+		// result
+		if (current < base.size()) {
+			result.add(0, current, base.size(), ConflictState.NO_CONFLICT);
+		}
+		return result;
+	}
+
+	/**
+	 * Helper method which returns the next Edit for an Iterator over Edits.
+	 * When there are no more edits left this method will return the constant
+	 * END_EDIT.
+	 *
+	 * @param it
+	 *            the iterator for which the next edit should be returned
+	 * @return the next edit from the iterator or END_EDIT if there no more
+	 *         edits
+	 */
+	private static Edit nextEdit(Iterator<Edit> it) {
+		return (it.hasNext() ? it.next() : END_EDIT);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeChunk.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeChunk.java
new file mode 100644
index 0000000000..2b2cf3384d
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeChunk.java
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2009, 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.merge;
+
+/**
+ * One chunk from a merge result. Each chunk contains a range from a
+ * single sequence. In case of conflicts multiple chunks are reported for one
+ * conflict. The conflictState tells when conflicts start and end.
+ */
+public class MergeChunk {
+	/**
+	 * A state telling whether a MergeChunk belongs to a conflict or not. The
+	 * first chunk of a conflict is reported with a special state to be able to
+	 * distinguish the border between two consecutive conflicts
+	 */
+	public enum ConflictState {
+		/**
+		 * This chunk does not belong to a conflict
+		 */
+		NO_CONFLICT,
+
+		/**
+		 * This chunk does belong to a conflict and is the first one of the
+		 * conflicting chunks
+		 */
+		FIRST_CONFLICTING_RANGE,
+
+		/**
+		 * This chunk does belong to a conflict but is not the first one of the
+		 * conflicting chunks. It's a subsequent one.
+		 */
+		NEXT_CONFLICTING_RANGE
+	};
+
+	private final int sequenceIndex;
+
+	private final int begin;
+
+	private final int end;
+
+	private final ConflictState conflictState;
+
+	/**
+	 * Creates a new empty MergeChunk
+	 *
+	 * @param sequenceIndex
+	 *            determines to which sequence this chunks belongs to. Same as
+	 *            in {@link MergeResult#add(int, int, int, ConflictState)}
+	 * @param begin
+	 *            the first element from the specified sequence which should be
+	 *            included in the merge result. Indexes start with 0.
+	 * @param end
+	 *            specifies the end of the range to be added. The element this
+	 *            index points to is the first element which not added to the
+	 *            merge result. All elements between begin (including begin) and
+	 *            this element are added.
+	 * @param conflictState
+	 *            the state of this chunk. See {@link ConflictState}
+	 */
+	protected MergeChunk(int sequenceIndex, int begin, int end,
+			ConflictState conflictState) {
+		this.sequenceIndex = sequenceIndex;
+		this.begin = begin;
+		this.end = end;
+		this.conflictState = conflictState;
+	}
+
+	/**
+	 * @return the index of the sequence to which sequence this chunks belongs
+	 *         to. Same as in
+	 *         {@link MergeResult#add(int, int, int, ConflictState)}
+	 */
+	public int getSequenceIndex() {
+		return sequenceIndex;
+	}
+
+	/**
+	 * @return the first element from the specified sequence which should be
+	 *         included in the merge result. Indexes start with 0.
+	 */
+	public int getBegin() {
+		return begin;
+	}
+
+	/**
+	 * @return the end of the range of this chunk. The element this index
+	 *         points to is the first element which not added to the merge
+	 *         result. All elements between begin (including begin) and this
+	 *         element are added.
+	 */
+	public int getEnd() {
+		return end;
+	}
+
+	/**
+	 * @return the state of this chunk. See {@link ConflictState}
+	 */
+	public ConflictState getConflictState() {
+		return conflictState;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeFormatter.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeFormatter.java
new file mode 100644
index 0000000000..2ff3e9b655
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeFormatter.java
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2009, 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.merge;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.jgit.diff.RawText;
+import org.eclipse.jgit.merge.MergeChunk.ConflictState;
+
+/**
+ * A class to convert merge results into a Git conformant textual presentation
+ */
+public class MergeFormatter {
+	/**
+	 * Formats the results of a merge of {@link RawText} objects in a Git
+	 * conformant way. This method also assumes that the {@link RawText} objects
+	 * being merged are line oriented files which use LF as delimiter. This
+	 * method will also use LF to separate chunks and conflict metadata,
+	 * therefore it fits only to texts that are LF-separated lines.
+	 *
+	 * @param out
+	 *            the outputstream where to write the textual presentation
+	 * @param res
+	 *            the merge result which should be presented
+	 * @param seqName
+	 *            When a conflict is reported each conflicting range will get a
+	 *            name. This name is following the "<<<<<<< " or ">>>>>>> "
+	 *            conflict markers. The names for the sequences are given in
+	 *            this list
+	 * @param charsetName
+	 *            the name of the characterSet used when writing conflict
+	 *            metadata
+	 * @throws IOException
+	 */
+	public void formatMerge(OutputStream out, MergeResult res,
+			List<String> seqName, String charsetName) throws IOException {
+		String lastConflictingName = null; // is set to non-null whenever we are
+		// in a conflict
+		boolean threeWayMerge = (res.getSequences().size() == 3);
+		for (MergeChunk chunk : res) {
+			RawText seq = (RawText) res.getSequences().get(
+					chunk.getSequenceIndex());
+			if (lastConflictingName != null
+					&& chunk.getConflictState() != ConflictState.NEXT_CONFLICTING_RANGE) {
+				// found the end of an conflict
+				out.write((">>>>>>> " + lastConflictingName + "\n").getBytes(charsetName));
+				lastConflictingName = null;
+			}
+			if (chunk.getConflictState() == ConflictState.FIRST_CONFLICTING_RANGE) {
+				// found the start of an conflict
+				out.write(("<<<<<<< " + seqName.get(chunk.getSequenceIndex()) +
+						"\n").getBytes(charsetName));
+				lastConflictingName = seqName.get(chunk.getSequenceIndex());
+			} else if (chunk.getConflictState() == ConflictState.NEXT_CONFLICTING_RANGE) {
+				// found another conflicting chunk
+
+				/*
+				 * In case of a non-three-way merge I'll add the name of the
+				 * conflicting chunk behind the equal signs. I also append the
+				 * name of the last conflicting chunk after the ending
+				 * greater-than signs. If somebody knows a better notation to
+				 * present non-three-way merges - feel free to correct here.
+				 */
+				lastConflictingName = seqName.get(chunk.getSequenceIndex());
+				out.write((threeWayMerge ? "=======\n" : "======= "
+						+ lastConflictingName + "\n").getBytes(charsetName));
+			}
+			// the lines with conflict-metadata are written. Now write the chunk
+			for (int i = chunk.getBegin(); i < chunk.getEnd(); i++) {
+				seq.writeLine(out, i);
+				out.write('\n');
+			}
+		}
+		// one possible leftover: if the merge result ended with a conflict we
+		// have to close the last conflict here
+		if (lastConflictingName != null) {
+			out.write((">>>>>>> " + lastConflictingName + "\n").getBytes(charsetName));
+		}
+	}
+
+	/**
+	 * Formats the results of a merge of exactly two {@link RawText} objects in
+	 * a Git conformant way. This convenience method accepts the names for the
+	 * three sequences (base and the two merged sequences) as explicit
+	 * parameters and doesn't require the caller to specify a List
+	 *
+	 * @param out
+	 *            the {@link OutputStream} where to write the textual
+	 *            presentation
+	 * @param res
+	 *            the merge result which should be presented
+	 * @param baseName
+	 *            the name ranges from the base should get
+	 * @param oursName
+	 *            the name ranges from ours should get
+	 * @param theirsName
+	 *            the name ranges from theirs should get
+	 * @param charsetName
+	 *            the name of the characterSet used when writing conflict
+	 *            metadata
+	 * @throws IOException
+	 */
+	public void formatMerge(OutputStream out, MergeResult res, String baseName,
+			String oursName, String theirsName, String charsetName) throws IOException {
+		List<String> names = new ArrayList<String>(3);
+		names.add(baseName);
+		names.add(oursName);
+		names.add(theirsName);
+		formatMerge(out, res, names, charsetName);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeResult.java b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeResult.java
new file mode 100644
index 0000000000..0da487bc66
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/merge/MergeResult.java
@@ -0,0 +1,161 @@
+/*
+ * Copyright (C) 2009, 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.merge;
+
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.jgit.diff.Sequence;
+import org.eclipse.jgit.merge.MergeChunk.ConflictState;
+import org.eclipse.jgit.util.IntList;
+
+/**
+ * The result of merging a number of {@link Sequence} objects. These sequences
+ * have one common predecessor sequence. The result of a merge is a list of
+ * MergeChunks. Each MergeChunk contains either a range (a subsequence) from
+ * one of the merged sequences, a range from the common predecessor or a
+ * conflicting range from one of the merged sequences. A conflict will be
+ * reported as multiple chunks, one for each conflicting range. The first chunk
+ * for a conflict is marked specially to distinguish the border between two
+ * consecutive conflicts.
+ * <p>
+ * This class does not know anything about how to present the merge result to
+ * the end-user. MergeFormatters have to be used to construct something human
+ * readable.
+ */
+public class MergeResult implements Iterable<MergeChunk> {
+	private final List<Sequence> sequences;
+
+	private final IntList chunks = new IntList();
+
+	private boolean containsConflicts = false;
+
+	/**
+	 * Creates a new empty MergeResult
+	 *
+	 * @param sequences
+	 *            contains the common predecessor sequence at position 0
+	 *            followed by the merged sequences. This list should not be
+	 *            modified anymore during the lifetime of this {@link MergeResult}.
+	 */
+	public MergeResult(List<Sequence> sequences) {
+		this.sequences = sequences;
+	}
+
+	/**
+	 * Adds a new range from one of the merged sequences or from the common
+	 * predecessor. This method can add conflicting and non-conflicting ranges
+	 * controlled by the conflictState parameter
+	 *
+	 * @param srcIdx
+	 *            determines from which sequence this range comes. An index of
+	 *            x specifies the x+1 element in the list of sequences
+	 *            specified to the constructor
+	 * @param begin
+	 *            the first element from the specified sequence which should be
+	 *            included in the merge result. Indexes start with 0.
+	 * @param end
+	 *            specifies the end of the range to be added. The element this
+	 *            index points to is the first element which not added to the
+	 *            merge result. All elements between begin (including begin) and
+	 *            this element are added.
+	 * @param conflictState
+	 *            when set to NO_CONLICT a non-conflicting range is added.
+	 *            This will end implicitly all open conflicts added before.
+	 */
+	public void add(int srcIdx, int begin, int end, ConflictState conflictState) {
+		chunks.add(conflictState.ordinal());
+		chunks.add(srcIdx);
+		chunks.add(begin);
+		chunks.add(end);
+		if (conflictState != ConflictState.NO_CONFLICT)
+			containsConflicts = true;
+	}
+
+	/**
+	 * Returns the common predecessor sequence and the merged sequence in one
+	 * list. The common predecessor is is the first element in the list
+	 *
+	 * @return the common predecessor at position 0 followed by the merged
+	 *         sequences.
+	 */
+	public List<Sequence> getSequences() {
+		return sequences;
+	}
+
+	private static final ConflictState[] states = ConflictState.values();
+
+	/**
+	 * @return an iterator over the MergeChunks. The iterator does not support
+	 * the remove operation
+	 */
+	public Iterator<MergeChunk> iterator() {
+		return new Iterator<MergeChunk>() {
+			int idx;
+
+			public boolean hasNext() {
+				return (idx < chunks.size());
+			}
+
+			public MergeChunk next() {
+				ConflictState state = states[chunks.get(idx++)];
+				int srcIdx = chunks.get(idx++);
+				int begin = chunks.get(idx++);
+				int end = chunks.get(idx++);
+				return new MergeChunk(srcIdx, begin, end, state);
+			}
+
+			public void remove() {
+				throw new UnsupportedOperationException();
+			}
+		};
+	}
+
+	/**
+	 * @return true if this merge result contains conflicts
+	 */
+	public boolean containsConflicts() {
+		return containsConflicts;
+	}
+}