diff options
15 files changed, 1439 insertions, 20 deletions
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/DefaultNoteMergerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/DefaultNoteMergerTest.java new file mode 100644 index 0000000000..9956492536 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/DefaultNoteMergerTest.java @@ -0,0 +1,149 @@ +/* + * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@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.notes; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertSame; + +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.lib.ObjectInserter; +import org.eclipse.jgit.lib.ObjectReader; +import org.eclipse.jgit.lib.Repository; +import org.eclipse.jgit.lib.RepositoryTestCase; +import org.eclipse.jgit.revwalk.RevBlob; +import org.junit.After; +import org.junit.Before; +import org.junit.Test; + +public class DefaultNoteMergerTest extends RepositoryTestCase { + + private TestRepository<Repository> tr; + + private ObjectReader reader; + + private ObjectInserter inserter; + + private DefaultNoteMerger merger; + + private Note baseNote; + + private RevBlob noteOn; + + @Override + @Before + public void setUp() throws Exception { + super.setUp(); + tr = new TestRepository<Repository>(db); + reader = db.newObjectReader(); + inserter = db.newObjectInserter(); + merger = new DefaultNoteMerger(); + noteOn = tr.blob("a"); + baseNote = newNote("data"); + } + + @Override + @After + public void tearDown() throws Exception { + reader.release(); + inserter.release(); + super.tearDown(); + } + + @Test + public void testDeleteDelete() throws Exception { + assertNull(merger.merge(baseNote, null, null, null, null)); + } + + @Test + public void testEditDelete() throws Exception { + Note edit = newNote("edit"); + assertSame(merger.merge(baseNote, edit, null, null, null), edit); + assertSame(merger.merge(baseNote, null, edit, null, null), edit); + } + + @Test + public void testIdenticalEdit() throws Exception { + Note edit = newNote("edit"); + assertSame(merger.merge(baseNote, edit, edit, null, null), edit); + } + + @Test + public void testEditEdit() throws Exception { + Note edit1 = newNote("edit1"); + Note edit2 = newNote("edit2"); + + Note result = merger.merge(baseNote, edit1, edit2, reader, inserter); + assertEquals(result, noteOn); // same note + assertEquals(result.getData(), tr.blob("edit1edit2")); + + result = merger.merge(baseNote, edit2, edit1, reader, inserter); + assertEquals(result, noteOn); // same note + assertEquals(result.getData(), tr.blob("edit2edit1")); + } + + @Test + public void testIdenticalAdd() throws Exception { + Note add = newNote("add"); + assertSame(merger.merge(null, add, add, null, null), add); + } + + @Test + public void testAddAdd() throws Exception { + Note add1 = newNote("add1"); + Note add2 = newNote("add2"); + + Note result = merger.merge(null, add1, add2, reader, inserter); + assertEquals(result, noteOn); // same note + assertEquals(result.getData(), tr.blob("add1add2")); + + result = merger.merge(null, add2, add1, reader, inserter); + assertEquals(result, noteOn); // same note + assertEquals(result.getData(), tr.blob("add2add1")); + } + + private Note newNote(String data) throws Exception { + return new Note(noteOn, tr.blob(data)); + } +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapMergerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapMergerTest.java new file mode 100644 index 0000000000..9cb228405a --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapMergerTest.java @@ -0,0 +1,509 @@ +/* + * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@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.notes; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +import java.io.IOException; +import java.util.Iterator; + +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.lib.ObjectInserter; +import org.eclipse.jgit.lib.ObjectReader; +import org.eclipse.jgit.lib.Repository; +import org.eclipse.jgit.lib.RepositoryTestCase; +import org.eclipse.jgit.merge.MergeStrategy; +import org.eclipse.jgit.revwalk.RevBlob; +import org.eclipse.jgit.revwalk.RevCommit; +import org.junit.After; +import org.junit.Before; +import org.junit.Test; + +public class NoteMapMergerTest extends RepositoryTestCase { + private TestRepository<Repository> tr; + + private ObjectReader reader; + + private ObjectInserter inserter; + + private NoteMap noRoot; + + private NoteMap empty; + + private NoteMap map_a; + + private NoteMap map_a_b; + + private RevBlob noteAId; + + private String noteAContent; + + private RevBlob noteABlob; + + private RevBlob noteBId; + + private String noteBContent; + + private RevBlob noteBBlob; + + private RevCommit sampleTree_a; + + private RevCommit sampleTree_a_b; + + @Override + @Before + public void setUp() throws Exception { + super.setUp(); + tr = new TestRepository<Repository>(db); + reader = db.newObjectReader(); + inserter = db.newObjectInserter(); + + noRoot = NoteMap.newMap(null, reader); + empty = NoteMap.newEmptyMap(); + + noteAId = tr.blob("a"); + noteAContent = "noteAContent"; + noteABlob = tr.blob(noteAContent); + sampleTree_a = tr.commit() + .add(noteAId.name(), noteABlob) + .create(); + tr.parseBody(sampleTree_a); + map_a = NoteMap.read(reader, sampleTree_a); + + noteBId = tr.blob("b"); + noteBContent = "noteBContent"; + noteBBlob = tr.blob(noteBContent); + sampleTree_a_b = tr.commit() + .add(noteAId.name(), noteABlob) + .add(noteBId.name(), noteBBlob) + .create(); + tr.parseBody(sampleTree_a_b); + map_a_b = NoteMap.read(reader, sampleTree_a_b); + } + + @Override + @After + public void tearDown() throws Exception { + reader.release(); + inserter.release(); + super.tearDown(); + } + + @Test + public void testNoChange() throws IOException { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap result; + + assertEquals(0, countNotes(merger.merge(noRoot, noRoot, noRoot))); + assertEquals(0, countNotes(merger.merge(empty, empty, empty))); + + result = merger.merge(map_a, map_a, map_a); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + } + + @Test + public void testOursEqualsTheirs() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap result; + + assertEquals(0, countNotes(merger.merge(empty, noRoot, noRoot))); + assertEquals(0, countNotes(merger.merge(map_a, noRoot, noRoot))); + + assertEquals(0, countNotes(merger.merge(noRoot, empty, empty))); + assertEquals(0, countNotes(merger.merge(map_a, empty, empty))); + + result = merger.merge(noRoot, map_a, map_a); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + result = merger.merge(empty, map_a, map_a); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + result = merger.merge(map_a_b, map_a, map_a); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + result = merger.merge(map_a, map_a_b, map_a_b); + assertEquals(2, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + assertEquals(noteBBlob, result.get(noteBId)); + } + + @Test + public void testBaseEqualsOurs() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap result; + + assertEquals(0, countNotes(merger.merge(noRoot, noRoot, empty))); + result = merger.merge(noRoot, noRoot, map_a); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + assertEquals(0, countNotes(merger.merge(empty, empty, noRoot))); + result = merger.merge(empty, empty, map_a); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + assertEquals(0, countNotes(merger.merge(map_a, map_a, noRoot))); + assertEquals(0, countNotes(merger.merge(map_a, map_a, empty))); + result = merger.merge(map_a, map_a, map_a_b); + assertEquals(2, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + assertEquals(noteBBlob, result.get(noteBId)); + } + + @Test + public void testBaseEqualsTheirs() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap result; + + assertEquals(0, countNotes(merger.merge(noRoot, empty, noRoot))); + result = merger.merge(noRoot, map_a, noRoot); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + assertEquals(0, countNotes(merger.merge(empty, noRoot, empty))); + result = merger.merge(empty, map_a, empty); + assertEquals(1, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + + assertEquals(0, countNotes(merger.merge(map_a, noRoot, map_a))); + assertEquals(0, countNotes(merger.merge(map_a, empty, map_a))); + result = merger.merge(map_a, map_a_b, map_a); + assertEquals(2, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + assertEquals(noteBBlob, result.get(noteBId)); + } + + @Test + public void testAddDifferentNotes() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap result; + + NoteMap map_a_c = NoteMap.read(reader, sampleTree_a); + RevBlob noteCId = tr.blob("c"); + RevBlob noteCBlob = tr.blob("noteCContent"); + map_a_c.set(noteCId, noteCBlob); + map_a_c.writeTree(inserter); + + result = merger.merge(map_a, map_a_b, map_a_c); + assertEquals(3, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + assertEquals(noteBBlob, result.get(noteBId)); + assertEquals(noteCBlob, result.get(noteCId)); + } + + @Test + public void testAddSameNoteDifferentContent() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, new DefaultNoteMerger(), + null); + NoteMap result; + + NoteMap map_a_b1 = NoteMap.read(reader, sampleTree_a); + String noteBContent1 = noteBContent + "change"; + RevBlob noteBBlob1 = tr.blob(noteBContent1); + map_a_b1.set(noteBId, noteBBlob1); + map_a_b1.writeTree(inserter); + + result = merger.merge(map_a, map_a_b, map_a_b1); + assertEquals(2, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + assertEquals(tr.blob(noteBContent + noteBContent1), result.get(noteBId)); + } + + @Test + public void testEditSameNoteDifferentContent() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, new DefaultNoteMerger(), + null); + NoteMap result; + + NoteMap map_a1 = NoteMap.read(reader, sampleTree_a); + String noteAContent1 = noteAContent + "change1"; + RevBlob noteABlob1 = tr.blob(noteAContent1); + map_a1.set(noteAId, noteABlob1); + map_a1.writeTree(inserter); + + NoteMap map_a2 = NoteMap.read(reader, sampleTree_a); + String noteAContent2 = noteAContent + "change2"; + RevBlob noteABlob2 = tr.blob(noteAContent2); + map_a2.set(noteAId, noteABlob2); + map_a2.writeTree(inserter); + + result = merger.merge(map_a, map_a1, map_a2); + assertEquals(1, countNotes(result)); + assertEquals(tr.blob(noteAContent1 + noteAContent2), + result.get(noteAId)); + } + + @Test + public void testEditDifferentNotes() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap result; + + NoteMap map_a1_b = NoteMap.read(reader, sampleTree_a_b); + String noteAContent1 = noteAContent + "change"; + RevBlob noteABlob1 = tr.blob(noteAContent1); + map_a1_b.set(noteAId, noteABlob1); + map_a1_b.writeTree(inserter); + + NoteMap map_a_b1 = NoteMap.read(reader, sampleTree_a_b); + String noteBContent1 = noteBContent + "change"; + RevBlob noteBBlob1 = tr.blob(noteBContent1); + map_a_b1.set(noteBId, noteBBlob1); + map_a_b1.writeTree(inserter); + + result = merger.merge(map_a_b, map_a1_b, map_a_b1); + assertEquals(2, countNotes(result)); + assertEquals(noteABlob1, result.get(noteAId)); + assertEquals(noteBBlob1, result.get(noteBId)); + } + + @Test + public void testDeleteDifferentNotes() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + + NoteMap map_b = NoteMap.read(reader, sampleTree_a_b); + map_b.set(noteAId, null); // delete note a + map_b.writeTree(inserter); + + assertEquals(0, countNotes(merger.merge(map_a_b, map_a, map_b))); + } + + @Test + public void testEditDeleteConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, new DefaultNoteMerger(), + null); + NoteMap result; + + NoteMap map_a_b1 = NoteMap.read(reader, sampleTree_a_b); + String noteBContent1 = noteBContent + "change"; + RevBlob noteBBlob1 = tr.blob(noteBContent1); + map_a_b1.set(noteBId, noteBBlob1); + map_a_b1.writeTree(inserter); + + result = merger.merge(map_a_b, map_a_b1, map_a); + assertEquals(2, countNotes(result)); + assertEquals(noteABlob, result.get(noteAId)); + assertEquals(noteBBlob1, result.get(noteBId)); + } + + @Test + public void testLargeTreesWithoutConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + NoteMap map1 = createLargeNoteMap("note_1_", "content_1_", 300, 0); + NoteMap map2 = createLargeNoteMap("note_2_", "content_2_", 300, 0); + + NoteMap result = merger.merge(empty, map1, map2); + assertEquals(600, countNotes(result)); + // check a few random notes + assertEquals(tr.blob("content_1_59"), result.get(tr.blob("note_1_59"))); + assertEquals(tr.blob("content_2_10"), result.get(tr.blob("note_2_10"))); + assertEquals(tr.blob("content_2_99"), result.get(tr.blob("note_2_99"))); + } + + @Test + public void testLargeTreesWithConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, new DefaultNoteMerger(), + null); + NoteMap largeTree1 = createLargeNoteMap("note_1_", "content_1_", 300, 0); + NoteMap largeTree2 = createLargeNoteMap("note_1_", "content_2_", 300, 0); + + NoteMap result = merger.merge(empty, largeTree1, largeTree2); + assertEquals(300, countNotes(result)); + // check a few random notes + assertEquals(tr.blob("content_1_59content_2_59"), + result.get(tr.blob("note_1_59"))); + assertEquals(tr.blob("content_1_10content_2_10"), + result.get(tr.blob("note_1_10"))); + assertEquals(tr.blob("content_1_99content_2_99"), + result.get(tr.blob("note_1_99"))); + } + + private NoteMap createLargeNoteMap(String noteNamePrefix, + String noteContentPrefix, int notesCount, int firstIndex) + throws Exception { + NoteMap result = NoteMap.newEmptyMap(); + for (int i = 0; i < notesCount; i++) { + result.set(tr.blob(noteNamePrefix + (firstIndex + i)), + tr.blob(noteContentPrefix + (firstIndex + i))); + } + result.writeTree(inserter); + return result; + } + + @Test + public void testFanoutAndLeafWithoutConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + + NoteMap largeTree = createLargeNoteMap("note_1_", "content_1_", 300, 0); + NoteMap result = merger.merge(map_a, map_a_b, largeTree); + assertEquals(301, countNotes(result)); + } + + @Test + public void testFanoutAndLeafWitConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, new DefaultNoteMerger(), + null); + + NoteMap largeTree_b1 = createLargeNoteMap("note_1_", "content_1_", 300, + 0); + String noteBContent1 = noteBContent + "change"; + largeTree_b1.set(noteBId, tr.blob(noteBContent1)); + largeTree_b1.writeTree(inserter); + + NoteMap result = merger.merge(map_a, map_a_b, largeTree_b1); + assertEquals(301, countNotes(result)); + assertEquals(tr.blob(noteBContent + noteBContent1), result.get(noteBId)); + } + + @Test + public void testCollapseFanoutAfterMerge() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, null); + + NoteMap largeTree = createLargeNoteMap("note_", "content_", 257, 0); + assertTrue(largeTree.getRoot() instanceof FanoutBucket); + NoteMap deleteFirstHundredNotes = createLargeNoteMap("note_", "content_", 157, + 100); + NoteMap deleteLastHundredNotes = createLargeNoteMap("note_", + "content_", 157, 0); + NoteMap result = merger.merge(largeTree, deleteFirstHundredNotes, + deleteLastHundredNotes); + assertEquals(57, countNotes(result)); + assertTrue(result.getRoot() instanceof LeafBucket); + } + + @Test + public void testNonNotesWithoutNonNoteConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, + MergeStrategy.RESOLVE); + RevCommit treeWithNonNotes = + tr.commit() + .add(noteAId.name(), noteABlob) // this is a note + .add("a.txt", tr.blob("content of a.txt")) // this is a non-note + .create(); + tr.parseBody(treeWithNonNotes); + NoteMap base = NoteMap.read(reader, treeWithNonNotes); + + treeWithNonNotes = + tr.commit() + .add(noteAId.name(), noteABlob) + .add("a.txt", tr.blob("content of a.txt")) + .add("b.txt", tr.blob("content of b.txt")) + .create(); + tr.parseBody(treeWithNonNotes); + NoteMap ours = NoteMap.read(reader, treeWithNonNotes); + + treeWithNonNotes = + tr.commit() + .add(noteAId.name(), noteABlob) + .add("a.txt", tr.blob("content of a.txt")) + .add("c.txt", tr.blob("content of c.txt")) + .create(); + tr.parseBody(treeWithNonNotes); + NoteMap theirs = NoteMap.read(reader, treeWithNonNotes); + + NoteMap result = merger.merge(base, ours, theirs); + assertEquals(3, countNonNotes(result)); + } + + @Test + public void testNonNotesWithNonNoteConflict() throws Exception { + NoteMapMerger merger = new NoteMapMerger(db, null, + MergeStrategy.RESOLVE); + RevCommit treeWithNonNotes = + tr.commit() + .add(noteAId.name(), noteABlob) // this is a note + .add("a.txt", tr.blob("content of a.txt")) // this is a non-note + .create(); + tr.parseBody(treeWithNonNotes); + NoteMap base = NoteMap.read(reader, treeWithNonNotes); + + treeWithNonNotes = + tr.commit() + .add(noteAId.name(), noteABlob) + .add("a.txt", tr.blob("change 1")) + .create(); + tr.parseBody(treeWithNonNotes); + NoteMap ours = NoteMap.read(reader, treeWithNonNotes); + + treeWithNonNotes = + tr.commit() + .add(noteAId.name(), noteABlob) + .add("a.txt", tr.blob("change 2")) + .create(); + tr.parseBody(treeWithNonNotes); + NoteMap theirs = NoteMap.read(reader, treeWithNonNotes); + + try { + merger.merge(base, ours, theirs); + fail("NotesMergeConflictException was expected"); + } catch (NotesMergeConflictException e) { + // expected + } + } + + private static int countNotes(NoteMap map) { + int c = 0; + Iterator<Note> it = map.iterator(); + while (it.hasNext()) { + it.next(); + c++; + } + return c; + } + + private static int countNonNotes(NoteMap map) { + int c = 0; + NonNoteEntry nonNotes = map.getRoot().nonNotes; + while (nonNotes != null) { + c++; + nonNotes = nonNotes.next; + } + return c; + } +} diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/JGitText.properties index 10d30cf023..c8f5920977 100644 --- a/org.eclipse.jgit/resources/org/eclipse/jgit/JGitText.properties +++ b/org.eclipse.jgit/resources/org/eclipse/jgit/JGitText.properties @@ -258,6 +258,8 @@ lockError=lock error: {0} lockOnNotClosed=Lock on {0} not closed. lockOnNotHeld=Lock on {0} not held. malformedpersonIdentString=Malformed PersonIdent string (no < was found): {0} +mergeConflictOnNotes=Merge conflict on note {0}. base = {1}, ours = {2}, theirs = {2} +mergeConflictOnNonNoteEntries=Merge conflict on non-note entries: base = {0}, ours = {1}, theirs = {2} mergeStrategyAlreadyExistsAsDefault=Merge strategy "{0}" already exists as a default strategy mergeStrategyDoesNotSupportHeads=merge strategy {0} does not support {1} heads to be merged into HEAD mergeUsingStrategyResultedInDescription=Merge of revisions {0} with base {1} using strategy {2} resulted in: {3}. {4} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/JGitText.java index 95236a30db..083abe5f02 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/JGitText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/JGitText.java @@ -318,6 +318,8 @@ public class JGitText extends TranslationBundle { /***/ public String lockOnNotClosed; /***/ public String lockOnNotHeld; /***/ public String malformedpersonIdentString; + /***/ public String mergeConflictOnNotes; + /***/ public String mergeConflictOnNonNoteEntries; /***/ public String mergeStrategyAlreadyExistsAsDefault; /***/ public String mergeStrategyDoesNotSupportHeads; /***/ public String mergeUsingStrategyResultedInDescription; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectInserter.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectInserter.java index de0c55f651..48fc39b4f6 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectInserter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectInserter.java @@ -177,6 +177,16 @@ public abstract class ObjectInserter { } /** + * Compute the ObjectId for the given tree without inserting it. + * + * @param formatter + * @return the computed ObjectId + */ + public ObjectId idFor(TreeFormatter formatter) { + return formatter.computeId(this); + } + + /** * Insert a single tree into the store, returning its unique name. * * @param formatter diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/TreeFormatter.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/TreeFormatter.java index 737a1c3fc1..86c3fc042a 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/TreeFormatter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/TreeFormatter.java @@ -290,6 +290,25 @@ public class TreeFormatter { } /** + * Compute the ObjectId for this tree + * + * @param ins + * @return ObjectId for this tree + */ + public ObjectId computeId(ObjectInserter ins) { + if (buf != null) + return ins.idFor(OBJ_TREE, buf, 0, ptr); + + final long len = overflowBuffer.length(); + try { + return ins.idFor(OBJ_TREE, len, overflowBuffer.openInputStream()); + } catch (IOException e) { + // this should never happen + throw new RuntimeException(e); + } + } + + /** * Copy this formatter's buffer into a byte array. * * This method is not efficient, as it needs to create a copy of the diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/DefaultNoteMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/DefaultNoteMerger.java new file mode 100644 index 0000000000..9624e49e98 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/DefaultNoteMerger.java @@ -0,0 +1,89 @@ +/* + * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@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.notes; + +import java.io.IOException; + +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ObjectInserter; +import org.eclipse.jgit.lib.ObjectLoader; +import org.eclipse.jgit.lib.ObjectReader; +import org.eclipse.jgit.util.io.UnionInputStream; + +/** + * Default implementation of the {@link NoteMerger}. + * <p> + * If ours and theirs are both non-null, which means they are either both edits + * or both adds, then this merger will simply join the content of ours and + * theirs (in that order) and return that as the merge result. + * <p> + * If one or ours/theirs is non-null and the other one is null then the non-null + * value is returned as the merge result. This means that an edit/delete + * conflict is resolved by keeping the edit version. + * <p> + * If both ours and theirs are null then the result of the merge is also null. + */ +public class DefaultNoteMerger implements NoteMerger { + + public Note merge(Note base, Note ours, Note theirs, ObjectReader reader, + ObjectInserter inserter) throws IOException { + if (ours == null) + return theirs; + + if (theirs == null) + return ours; + + if (ours.getData().equals(theirs.getData())) + return ours; + + ObjectLoader lo = reader.open(ours.getData()); + ObjectLoader lt = reader.open(theirs.getData()); + UnionInputStream union = new UnionInputStream(lo.openStream(), + lt.openStream()); + ObjectId noteData = inserter.insert(Constants.OBJ_BLOB, + lo.getSize() + lt.getSize(), union); + return new Note(ours, noteData); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java index 944e575008..953929464a 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java @@ -99,17 +99,35 @@ class FanoutBucket extends InMemoryNoteBucket { table = new NoteBucket[256]; } - void parseOneEntry(int cell, ObjectId id) { + void setBucket(int cell, ObjectId id) { table[cell] = new LazyNoteBucket(id); cnt++; } + void setBucket(int cell, InMemoryNoteBucket bucket) { + table[cell] = bucket; + cnt++; + } + @Override ObjectId get(AnyObjectId objId, ObjectReader or) throws IOException { NoteBucket b = table[cell(objId)]; return b != null ? b.get(objId, or) : null; } + NoteBucket getBucket(int cell) { + return table[cell]; + } + + static InMemoryNoteBucket loadIfLazy(NoteBucket b, AnyObjectId prefix, + ObjectReader or) throws IOException { + if (b == null) + return null; + if (b instanceof InMemoryNoteBucket) + return (InMemoryNoteBucket) b; + return ((LazyNoteBucket) b).load(prefix, or); + } + @Override Iterator<Note> iterator(AnyObjectId objId, final ObjectReader reader) throws IOException { @@ -209,16 +227,7 @@ class FanoutBucket extends InMemoryNoteBucket { if (cnt == 0) return null; - if (estimateSize(noteOn, or) < LeafBucket.MAX_SIZE) { - // We are small enough to just contract to a single leaf. - InMemoryNoteBucket r = new LeafBucket(prefixLen); - for (Iterator<Note> i = iterator(noteOn, or); i.hasNext();) - r = r.append(i.next()); - r.nonNotes = nonNotes; - return r; - } - - return this; + return contractIfTooSmall(noteOn, or); } else if (n != b) { table[cell] = n; @@ -227,11 +236,39 @@ class FanoutBucket extends InMemoryNoteBucket { } } + InMemoryNoteBucket contractIfTooSmall(AnyObjectId noteOn, ObjectReader or) + throws IOException { + if (estimateSize(noteOn, or) < LeafBucket.MAX_SIZE) { + // We are small enough to just contract to a single leaf. + InMemoryNoteBucket r = new LeafBucket(prefixLen); + for (Iterator<Note> i = iterator(noteOn, or); i.hasNext();) + r = r.append(i.next()); + r.nonNotes = nonNotes; + return r; + } + + return this; + } + private static final byte[] hexchar = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }; @Override ObjectId writeTree(ObjectInserter inserter) throws IOException { + return inserter.insert(build(true, inserter)); + } + + ObjectId getTreeId() { + try { + return new ObjectInserter.Formatter().idFor(build(false, null)); + } catch (IOException e) { + // should never happen as we are not inserting + throw new RuntimeException(e); + } + } + + private TreeFormatter build(boolean insert, ObjectInserter inserter) + throws IOException { byte[] nameBuf = new byte[2]; TreeFormatter fmt = new TreeFormatter(treeSize()); NonNoteEntry e = nonNotes; @@ -249,12 +286,18 @@ class FanoutBucket extends InMemoryNoteBucket { e = e.next; } - fmt.append(nameBuf, 0, 2, TREE, b.writeTree(inserter)); + ObjectId id; + if (insert) { + id = b.writeTree(inserter); + } else { + id = b.getTreeId(); + } + fmt.append(nameBuf, 0, 2, TREE, id); } for (; e != null; e = e.next) e.format(fmt); - return inserter.insert(fmt); + return fmt; } private int treeSize() { @@ -320,11 +363,16 @@ class FanoutBucket extends InMemoryNoteBucket { return treeId; } - private NoteBucket load(AnyObjectId objId, ObjectReader or) + @Override + ObjectId getTreeId() { + return treeId; + } + + private InMemoryNoteBucket load(AnyObjectId prefix, ObjectReader or) throws IOException { - AbbreviatedObjectId p = objId.abbreviate(prefixLen + 2); - NoteBucket self = NoteParser.parse(p, treeId, or); - table[cell(objId)] = self; + AbbreviatedObjectId p = prefix.abbreviate(prefixLen + 2); + InMemoryNoteBucket self = NoteParser.parse(p, treeId, or); + table[cell(prefix)] = self; return self; } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java index db56eda2b1..8866849837 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java @@ -107,6 +107,14 @@ class LeafBucket extends InMemoryNoteBucket { return 0 <= idx ? notes[idx].getData() : null; } + Note get(int index) { + return notes[index]; + } + + int size() { + return cnt; + } + @Override Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader) { return new Iterator<Note>() { @@ -169,6 +177,15 @@ class LeafBucket extends InMemoryNoteBucket { @Override ObjectId writeTree(ObjectInserter inserter) throws IOException { + return inserter.insert(build()); + } + + @Override + ObjectId getTreeId() { + return new ObjectInserter.Formatter().idFor(build()); + } + + private TreeFormatter build() { byte[] nameBuf = new byte[OBJECT_ID_STRING_LENGTH]; int nameLen = OBJECT_ID_STRING_LENGTH - prefixLen; TreeFormatter fmt = new TreeFormatter(treeSize(nameLen)); @@ -190,7 +207,7 @@ class LeafBucket extends InMemoryNoteBucket { for (; e != null; e = e.next) e.format(fmt); - return inserter.insert(fmt); + return fmt; } private int treeSize(final int nameLen) { @@ -229,7 +246,7 @@ class LeafBucket extends InMemoryNoteBucket { return MAX_SIZE <= cnt && prefixLen + 2 < OBJECT_ID_STRING_LENGTH; } - private InMemoryNoteBucket split() { + FanoutBucket split() { FanoutBucket n = new FanoutBucket(prefixLen); for (int i = 0; i < cnt; i++) n.append(notes[i]); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java index defc37dbec..5c7b325f0d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java @@ -71,4 +71,6 @@ abstract class NoteBucket { ObjectReader reader) throws IOException; abstract ObjectId writeTree(ObjectInserter inserter) throws IOException; + + abstract ObjectId getTreeId(); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java index abde6db765..591b1aeb19 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java @@ -157,6 +157,23 @@ public class NoteMap implements Iterable<Note> { return map; } + /** + * Construct a new note map from an existing note bucket. + * + * @param root + * the root bucket of this note map + * @param reader + * reader to scan the note branch with. This reader may be + * retained by the NoteMap for the life of the map in order to + * support lazy loading of entries. + * @return the note map built from the note bucket + */ + static NoteMap newMap(InMemoryNoteBucket root, ObjectReader reader) { + NoteMap map = new NoteMap(reader); + map.root = root; + return map; + } + /** Borrowed reader to access the repository. */ private final ObjectReader reader; @@ -338,6 +355,11 @@ public class NoteMap implements Iterable<Note> { return root.writeTree(inserter); } + /** @return the root note bucket */ + InMemoryNoteBucket getRoot() { + return root; + } + private void load(ObjectId rootTree) throws MissingObjectException, IncorrectObjectTypeException, CorruptObjectException, IOException { AbbreviatedObjectId none = AbbreviatedObjectId.fromString(""); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMapMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMapMerger.java new file mode 100644 index 0000000000..b0965d2c07 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMapMerger.java @@ -0,0 +1,353 @@ +/* + * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@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.notes; + +import java.io.IOException; + +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.lib.AbbreviatedObjectId; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.MutableObjectId; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ObjectInserter; +import org.eclipse.jgit.lib.ObjectReader; +import org.eclipse.jgit.lib.Repository; +import org.eclipse.jgit.merge.MergeStrategy; +import org.eclipse.jgit.merge.Merger; +import org.eclipse.jgit.merge.ThreeWayMergeStrategy; +import org.eclipse.jgit.merge.ThreeWayMerger; +import org.eclipse.jgit.treewalk.AbstractTreeIterator; +import org.eclipse.jgit.treewalk.TreeWalk; + +/** + * Three-way note tree merge. + * <p> + * Direct implementation of NoteMap merger without using {@link TreeWalk} and + * {@link AbstractTreeIterator} + */ +public class NoteMapMerger { + private static final FanoutBucket EMPTY_FANOUT = new FanoutBucket(0); + + private static final LeafBucket EMPTY_LEAF = new LeafBucket(0); + + private final Repository db; + + private final NoteMerger noteMerger; + + private final MergeStrategy nonNotesMergeStrategy; + + private final ObjectReader reader; + + private final ObjectInserter inserter; + + private final MutableObjectId objectIdPrefix; + + /** + * Constructs a NoteMapMerger with custom {@link NoteMerger} and custom + * {@link MergeStrategy}. + * + * @param db + * Git repository + * @param noteMerger + * note merger for merging conflicting changes on a note + * @param nonNotesMergeStrategy + * merge strategy for merging non-note entries + */ + public NoteMapMerger(Repository db, NoteMerger noteMerger, + MergeStrategy nonNotesMergeStrategy) { + this.db = db; + this.reader = db.newObjectReader(); + this.inserter = db.newObjectInserter(); + this.noteMerger = noteMerger; + this.nonNotesMergeStrategy = nonNotesMergeStrategy; + this.objectIdPrefix = new MutableObjectId(); + } + + /** + * Constructs a NoteMapMerger with {@link DefaultNoteMerger} as the merger + * for notes and the {@link MergeStrategy#RESOLVE} as the strategy for + * resolving conflicts on non-notes + * + * @param db + * Git repository + */ + public NoteMapMerger(Repository db) { + this(db, new DefaultNoteMerger(), MergeStrategy.RESOLVE); + } + + /** + * Performs the merge. + * + * @param base + * base version of the note tree + * @param ours + * ours version of the note tree + * @param theirs + * theirs version of the note tree + * @return merge result as a new NoteMap + * @throws IOException + */ + public NoteMap merge(NoteMap base, NoteMap ours, NoteMap theirs) + throws IOException { + try { + InMemoryNoteBucket mergedBucket = merge(0, base.getRoot(), + ours.getRoot(), theirs.getRoot()); + inserter.flush(); + return NoteMap.newMap(mergedBucket, reader); + } finally { + reader.release(); + inserter.release(); + } + } + + /** + * This method is called only when it is known that there is some difference + * between base, ours and theirs. + * + * @param treeDepth + * @param base + * @param ours + * @param theirs + * @return merge result as an InMemoryBucket + * @throws IOException + */ + private InMemoryNoteBucket merge(int treeDepth, InMemoryNoteBucket base, + InMemoryNoteBucket ours, InMemoryNoteBucket theirs) + throws IOException { + InMemoryNoteBucket result; + + if (base instanceof FanoutBucket || ours instanceof FanoutBucket + || theirs instanceof FanoutBucket) { + result = mergeFanoutBucket(treeDepth, asFanout(base), + asFanout(ours), asFanout(theirs)); + + } else { + result = mergeLeafBucket(treeDepth, (LeafBucket) base, + (LeafBucket) ours, (LeafBucket) theirs); + } + + result.nonNotes = mergeNonNotes(nonNotes(base), nonNotes(ours), + nonNotes(theirs)); + return result; + } + + private FanoutBucket asFanout(InMemoryNoteBucket bucket) { + if (bucket == null) + return EMPTY_FANOUT; + if (bucket instanceof FanoutBucket) + return (FanoutBucket) bucket; + return ((LeafBucket) bucket).split(); + } + + private static NonNoteEntry nonNotes(InMemoryNoteBucket b) { + return b == null ? null : b.nonNotes; + } + + private InMemoryNoteBucket mergeFanoutBucket(int treeDepth, + FanoutBucket base, + FanoutBucket ours, FanoutBucket theirs) throws IOException { + FanoutBucket result = new FanoutBucket(treeDepth * 2); + // walking through entries of base, ours, theirs + for (int i = 0; i < 256; i++) { + NoteBucket b = base.getBucket(i); + NoteBucket o = ours.getBucket(i); + NoteBucket t = theirs.getBucket(i); + + if (equals(o, t)) + addIfNotNull(result, i, o); + + else if (equals(b, o)) + addIfNotNull(result, i, t); + + else if (equals(b, t)) + addIfNotNull(result, i, o); + + else { + objectIdPrefix.setByte(treeDepth, i); + InMemoryNoteBucket mergedBucket = merge(treeDepth + 1, + FanoutBucket.loadIfLazy(b, objectIdPrefix, reader), + FanoutBucket.loadIfLazy(o, objectIdPrefix, reader), + FanoutBucket.loadIfLazy(t, objectIdPrefix, reader)); + result.setBucket(i, mergedBucket); + } + } + return result.contractIfTooSmall(objectIdPrefix, reader); + } + + private static boolean equals(NoteBucket a, NoteBucket b) { + if (a == null && b == null) + return true; + return a != null && b != null && a.getTreeId().equals(b.getTreeId()); + } + + private void addIfNotNull(FanoutBucket b, int cell, NoteBucket child) + throws IOException { + if (child == null) + return; + if (child instanceof InMemoryNoteBucket) + b.setBucket(cell, ((InMemoryNoteBucket) child).writeTree(inserter)); + else + b.setBucket(cell, child.getTreeId()); + } + + private InMemoryNoteBucket mergeLeafBucket(int treeDepth, LeafBucket bb, + LeafBucket ob, LeafBucket tb) throws MissingObjectException, + IOException { + bb = notNullOrEmpty(bb); + ob = notNullOrEmpty(ob); + tb = notNullOrEmpty(tb); + + InMemoryNoteBucket result = new LeafBucket(treeDepth * 2); + int bi = 0, oi = 0, ti = 0; + while (bi < bb.size() || oi < ob.size() || ti < tb.size()) { + Note b = get(bb, bi), o = get(ob, oi), t = get(tb, ti); + Note min = min(b, o, t); + + b = sameNoteOrNull(min, b); + o = sameNoteOrNull(min, o); + t = sameNoteOrNull(min, t); + + if (sameContent(o, t)) + result = addIfNotNull(result, o); + + else if (sameContent(b, o)) + result = addIfNotNull(result, t); + + else if (sameContent(b, t)) + result = addIfNotNull(result, o); + + else + result = addIfNotNull(result, + noteMerger.merge(b, o, t, reader, inserter)); + + if (b != null) + bi++; + if (o != null) + oi++; + if (t != null) + ti++; + } + return result; + } + + private static LeafBucket notNullOrEmpty(LeafBucket b) { + return b != null ? b : EMPTY_LEAF; + } + + private static Note get(LeafBucket b, int i) { + return i < b.size() ? b.get(i) : null; + } + + private static Note min(Note b, Note o, Note t) { + Note min = b; + if (min == null || (o != null && o.compareTo(min) < 0)) + min = o; + if (min == null || (t != null && t.compareTo(min) < 0)) + min = t; + return min; + } + + private static Note sameNoteOrNull(Note min, Note other) { + return sameNote(min, other) ? other : null; + } + + private static boolean sameNote(Note a, Note b) { + if (a == null && b == null) + return true; + return a != null && b != null && AnyObjectId.equals(a, b); + } + + private static boolean sameContent(Note a, Note b) { + if (a == null && b == null) + return true; + return a != null && b != null + && AnyObjectId.equals(a.getData(), b.getData()); + } + + private static InMemoryNoteBucket addIfNotNull(InMemoryNoteBucket result, + Note note) { + if (note != null) + return result.append(note); + else + return result; + } + + private NonNoteEntry mergeNonNotes(NonNoteEntry baseList, + NonNoteEntry oursList, NonNoteEntry theirsList) throws IOException { + if (baseList == null && oursList == null && theirsList == null) + return null; + + ObjectId baseId = write(baseList); + ObjectId oursId = write(oursList); + ObjectId theirsId = write(theirsList); + inserter.flush(); + + ObjectId resultTreeId; + if (nonNotesMergeStrategy instanceof ThreeWayMergeStrategy) { + ThreeWayMerger m = ((ThreeWayMergeStrategy) nonNotesMergeStrategy) + .newMerger(db, true); + m.setBase(baseId); + if (!m.merge(oursId, theirsId)) + throw new NotesMergeConflictException(baseList, oursList, + theirsList); + + resultTreeId = m.getResultTreeId(); + } else { + Merger m = nonNotesMergeStrategy.newMerger(db, true); + if (!m.merge(new AnyObjectId[] { oursId, theirsId })) + throw new NotesMergeConflictException(baseList, oursList, + theirsList); + resultTreeId = m.getResultTreeId(); + } + AbbreviatedObjectId none = AbbreviatedObjectId.fromString(""); + return NoteParser.parse(none, resultTreeId, reader).nonNotes; + } + + private ObjectId write(NonNoteEntry list) + throws IOException { + LeafBucket b = new LeafBucket(0); + b.nonNotes = list; + return b.writeTree(inserter); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMerger.java new file mode 100644 index 0000000000..c70211df9e --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMerger.java @@ -0,0 +1,87 @@ +/* + * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@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.notes; + +import java.io.IOException; + +import org.eclipse.jgit.lib.ObjectInserter; +import org.eclipse.jgit.lib.ObjectReader; + +/** + * Three-way note merge operation. + * <p> + * This operation takes three versions of a note: base, ours and theirs, + * performs the three-way merge and returns the merge result. + */ +public interface NoteMerger { + + /** + * Merges the conflicting note changes. + * <p> + * base, ours and their are all notes on the same object. + * + * @param base + * version of the Note + * @param ours + * version of the Note + * @param their + * version of the Note + * @param reader + * the object reader that must be used to read Git objects + * @param inserter + * the object inserter that must be used to insert Git objects + * @return the merge result + * @throws NotesMergeConflictException + * in case there was a merge conflict which this note merger + * couldn't resolve + * @throws IOException + * in case the reader or the inserter would throw an IOException + * the implementor will most likely want to propagate it as it + * can't do much to recover from it + */ + Note merge(Note base, Note ours, Note their, ObjectReader reader, + ObjectInserter inserter) throws NotesMergeConflictException, + IOException; +} + diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java index 11ef10ae70..8ef3af10ad 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java @@ -165,7 +165,7 @@ final class NoteParser extends CanonicalTreeParser { for (; !eof(); next(1)) { final int cell = parseFanoutCell(); if (0 <= cell) - fanout.parseOneEntry(cell, getEntryObjectId()); + fanout.setBucket(cell, getEntryObjectId()); else storeNonNote(); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NotesMergeConflictException.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NotesMergeConflictException.java new file mode 100644 index 0000000000..60970a72a7 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NotesMergeConflictException.java @@ -0,0 +1,110 @@ +/* + * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@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.notes; + +import java.io.IOException; +import java.text.MessageFormat; + +import org.eclipse.jgit.JGitText; + +/** + * This exception will be thrown from the {@link NoteMerger} when a conflict on + * Notes content is found during merge. + */ +public class NotesMergeConflictException extends IOException { + private static final long serialVersionUID = 1L; + + /** + * Construct a NotesMergeConflictException for the specified base, ours and + * theirs note versions. + * + * @param base + * note version + * @param ours + * note version + * @param theirs + * note version + */ + public NotesMergeConflictException(Note base, Note ours, Note theirs) { + super(MessageFormat.format(JGitText.get().mergeConflictOnNotes, + noteOn(base, ours, theirs), noteData(base), noteData(ours), + noteData(theirs))); + } + + /** + * Constructs a NotesMergeConflictException for the specified base, ours and + * theirs versions of the root note tree. + * + * @param base + * version of the root note tree + * @param ours + * version of the root note tree + * @param theirs + * version of the root note tree + */ + public NotesMergeConflictException(NonNoteEntry base, NonNoteEntry ours, + NonNoteEntry theirs) { + super(MessageFormat.format( + JGitText.get().mergeConflictOnNonNoteEntries, name(base), + name(ours), name(theirs))); + } + + private static String noteOn(Note base, Note ours, Note theirs) { + if (base != null) + return base.name(); + if (ours != null) + return ours.name(); + return theirs.name(); + } + + private static String noteData(Note n) { + if (n != null) + return n.getData().name(); + return ""; + } + + private static String name(NonNoteEntry e) { + return e != null ? e.name() : ""; + } +} |