[EGIT] Sort order from hell fixes, take 2

[EGIT] Sort order from hell fixes, take 2

[Robin Rosenberg]

Hi fans,

My previous attempt to fix this failed, so here is another round, including
some new infrastructure like a TreeIterator to support this fix and whatever
will need it.

Feed free to scrutize and invent whatever evil test case might be missing.

The reason I noticed the problem was introduced in c20142, where the unit
tests for org.spearce.jgit was moved to the new project org.spearce.jgit.test .

-- robin

[EGIT PATCH 01/10] Tighten IndexDiffTest to make it test better what it claims to test

[Robin Rosenberg]

I.e. test more of the expected state

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../tst/org/spearce/jgit/lib/IndexDiffTest.java    |   22 ++++++++++++++++++++
 1 files changed, 22 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java
index ba5d8d7..629c06c 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java
@@ -31,8 +31,12 @@ public class IndexDiffTest extends RepositoryTestCase {
 		index.add(trash, new File(trash, "dir/subfile"));
 		IndexDiff diff = new IndexDiff(tree, index);
 		diff.diff();
+		assertEquals(2, diff.getAdded().size());
 		assertTrue(diff.getAdded().contains("file1"));
 		assertTrue(diff.getAdded().contains("dir/subfile"));
+		assertEquals(0, diff.getChanged().size());
+		assertEquals(0, diff.getModified().size());
+		assertEquals(0, diff.getRemoved().size());
 	}
 
 	public void testRemoved() throws IOException {
@@ -44,11 +48,20 @@ public class IndexDiffTest extends RepositoryTestCase {
 		tree.addFile("file2");
 		tree.addFile("dir/file3");
 		assertEquals(2, tree.memberCount());
+		tree.findBlobMember("file2").setId(new ObjectId("30d67d4672d5c05833b7192cc77a79eaafb5c7ad"));
+		Tree tree2 = (Tree) tree.findTreeMember("dir");
+		tree2.findBlobMember("file3").setId(new ObjectId("873fb8d667d05436d728c52b1d7a09528e6eb59b"));
+		tree2.setId(new ObjectWriter(db).writeTree(tree2));
+		tree.setId(new ObjectWriter(db).writeTree(tree));
 
 		IndexDiff diff = new IndexDiff(tree, index);
 		diff.diff();
+		assertEquals(2, diff.getRemoved().size());
 		assertTrue(diff.getRemoved().contains("file2"));
 		assertTrue(diff.getRemoved().contains("dir/file3"));
+		assertEquals(0, diff.getChanged().size());
+		assertEquals(0, diff.getModified().size());
+		assertEquals(0, diff.getAdded().size());
 	}
 
 	public void testModified() throws IOException {
@@ -65,10 +78,19 @@ public class IndexDiffTest extends RepositoryTestCase {
 		tree.addFile("dir/file3").setId(new ObjectId("0123456789012345678901234567890123456789"));
 		assertEquals(2, tree.memberCount());
 
+		Tree tree2 = (Tree) tree.findTreeMember("dir");
+		tree2.setId(new ObjectWriter(db).writeTree(tree2));
+		tree.setId(new ObjectWriter(db).writeTree(tree));
 		IndexDiff diff = new IndexDiff(tree, index);
 		diff.diff();
+		assertEquals(2, diff.getChanged().size());
 		assertTrue(diff.getChanged().contains("file2"));
 		assertTrue(diff.getChanged().contains("dir/file3"));
+		assertEquals(1, diff.getModified().size());
 		assertTrue(diff.getModified().contains("dir/file3"));
+		assertEquals(0, diff.getAdded().size());
+		assertEquals(0, diff.getRemoved().size());
+		assertEquals(0, diff.getMissing().size());
 	}
+
 }
-- 
1.5.4.2

[EGIT PATCH 02/10] Extend IndexDiffTest with more tests

[Robin Rosenberg]

This adds tests for some nasty cases. These can be summarized
by declaring that this is the correct order:

	a.b
	a/b
	a=b

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../tst/org/spearce/jgit/lib/IndexDiffTest.java    |   67 ++++++++++++++++++++
 1 files changed, 67 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java
index 629c06c..4692fa2 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/IndexDiffTest.java
@@ -93,4 +93,71 @@ public class IndexDiffTest extends RepositoryTestCase {
 		assertEquals(0, diff.getMissing().size());
 	}
 
+	public void testUnchangedSimple() throws IOException {
+		GitIndex index = new GitIndex(db);
+
+		index.add(trash, writeTrashFile("a.b", "a.b"));
+		index.add(trash, writeTrashFile("a.c", "a.c"));
+		index.add(trash, writeTrashFile("a=c", "a=c"));
+		index.add(trash, writeTrashFile("a=d", "a=d"));
+
+		Tree tree = new Tree(db);
+		// got the hash id'd from the data using echo -n a.b|git hash-object -t blob --stdin
+		tree.addFile("a.b").setId(new ObjectId("f6f28df96c2b40c951164286e08be7c38ec74851"));
+		tree.addFile("a.c").setId(new ObjectId("6bc0e647512d2a0bef4f26111e484dc87df7f5ca"));
+		tree.addFile("a=c").setId(new ObjectId("06022365ddbd7fb126761319633bf73517770714"));
+		tree.addFile("a=d").setId(new ObjectId("fa6414df3da87840700e9eeb7fc261dd77ccd5c2"));
+
+		tree.setId(new ObjectWriter(db).writeTree(tree));
+
+		IndexDiff diff = new IndexDiff(tree, index);
+		diff.diff();
+		assertEquals(0, diff.getChanged().size());
+		assertEquals(0, diff.getAdded().size());
+		assertEquals(0, diff.getRemoved().size());
+		assertEquals(0, diff.getMissing().size());
+		assertEquals(0, diff.getModified().size());
+	}
+
+	/**
+	 * This test has both files and directories that involve
+	 * the tricky ordering used by Git.
+	 *
+	 * @throws IOException
+	 */
+	public void testUnchangedComplex() throws IOException {
+		GitIndex index = new GitIndex(db);
+
+		index.add(trash, writeTrashFile("a.b", "a.b"));
+		index.add(trash, writeTrashFile("a.c", "a.c"));
+		index.add(trash, writeTrashFile("a/b.b/b", "a/b.b/b"));
+		index.add(trash, writeTrashFile("a/b", "a/b"));
+		index.add(trash, writeTrashFile("a/c", "a/c"));
+		index.add(trash, writeTrashFile("a=c", "a=c"));
+		index.add(trash, writeTrashFile("a=d", "a=d"));
+
+		Tree tree = new Tree(db);
+		// got the hash id'd from the data using echo -n a.b|git hash-object -t blob --stdin
+		tree.addFile("a.b").setId(new ObjectId("f6f28df96c2b40c951164286e08be7c38ec74851"));
+		tree.addFile("a.c").setId(new ObjectId("6bc0e647512d2a0bef4f26111e484dc87df7f5ca"));
+		tree.addFile("a/b.b/b").setId(new ObjectId("8d840bd4e2f3a48ff417c8e927d94996849933fd"));
+		tree.addFile("a/b").setId(new ObjectId("db89c972fc57862eae378f45b74aca228037d415"));
+		tree.addFile("a/c").setId(new ObjectId("52ad142a008aeb39694bafff8e8f1be75ed7f007"));
+		tree.addFile("a=c").setId(new ObjectId("06022365ddbd7fb126761319633bf73517770714"));
+		tree.addFile("a=d").setId(new ObjectId("fa6414df3da87840700e9eeb7fc261dd77ccd5c2"));
+
+		Tree tree3 = (Tree) tree.findTreeMember("a/b.b");
+		tree3.setId(new ObjectWriter(db).writeTree(tree3));
+		Tree tree2 = (Tree) tree.findTreeMember("a");
+		tree2.setId(new ObjectWriter(db).writeTree(tree2));
+		tree.setId(new ObjectWriter(db).writeTree(tree));
+
+		IndexDiff diff = new IndexDiff(tree, index);
+		diff.diff();
+		assertEquals(0, diff.getChanged().size());
+		assertEquals(0, diff.getAdded().size());
+		assertEquals(0, diff.getRemoved().size());
+		assertEquals(0, diff.getMissing().size());
+		assertEquals(0, diff.getModified().size());
+	}
 }
-- 
1.5.4.2

[EGIT PATCH 03/10] WorkdirCheckout: more test for names that are close

[Robin Rosenberg]

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../tst/org/spearce/jgit/lib/ReadTreeTest.java     |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java
index 7ac48c9..6faedc7 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java
@@ -477,7 +477,21 @@ public class ReadTreeTest extends RepositoryTestCase {
 		
 		assertNoConflicts();
 	}
-	
+
+	public void testCloseNameConflictsX0() throws IOException {
+		setupCase(mkmap("a/a", "a/a-c"), mkmap("a/a","a/a", "b.b/b.b","b.b/b.bs"), mkmap("a/a", "a/a-c") );
+		checkout();
+		go();
+		assertNoConflicts();
+	}
+
+	public void testCloseNameConflicts1() throws IOException {
+		setupCase(mkmap("a/a", "a/a-c"), mkmap("a/a","a/a", "a.a/a.a","a.a/a.a"), mkmap("a/a", "a/a-c") );
+		checkout();
+		go();
+		assertNoConflicts();
+	}
+
 	private void checkout() throws IOException {
 		readTree = new WorkDirCheckout(db, trash, head, index, merge);
 		readTree.checkout();
-- 
1.5.4.2

[EGIT PATCH 04/10] Split a big test in ReadTreeTest into smaller tests

[Robin Rosenberg]

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../tst/org/spearce/jgit/lib/ReadTreeTest.java     |   84 +++++++++++++------
 1 files changed, 57 insertions(+), 27 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java
index 6faedc7..70c1396 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ReadTreeTest.java
@@ -273,50 +273,55 @@ public class ReadTreeTest extends RepositoryTestCase {
 	 *19   D	    0       F											  Update
 	 */
 	
-	public void testDirectoryFileConflicts() throws Exception {
+	public void testDirectoryFileConflicts_1() throws Exception {
 		// 1
 		doit(mk("DF/DF"), mk("DF"), mk("DF/DF"));
 		assertNoConflicts();
 		assertUpdated("DF");
 		assertRemoved("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_2() throws Exception {
 		// 2
 		setupCase(mk("DF/DF"), mk("DF"), mk("DF/DF"));
 		writeTrashFile("DF/DF", "different");
 		go();
 		assertConflict("DF/DF");
 		
+	}
+
+	public void testDirectoryFileConflicts_3() throws Exception {
 		// 3 - the first to break!
-		tearDown();
-		setUp();
 		doit(mk("DF/DF"), mk("DF/DF"), mk("DF"));
 		assertUpdated("DF/DF");
 		assertRemoved("DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_4() throws Exception {
 		// 4 (basically same as 3, just with H and M different)
-		tearDown();
-		setUp();
 		doit(mk("DF/DF"), mkmap("DF/DF", "foo"), mk("DF"));
 		assertUpdated("DF/DF");
 		assertRemoved("DF");
 		
+	}
+
+	public void testDirectoryFileConflicts_5() throws Exception {
 		// 5
-		tearDown();
-		setUp();
 		doit(mk("DF/DF"), mk("DF"), mk("DF"));
 		assertRemoved("DF/DF");
 		
+	}
+
+	public void testDirectoryFileConflicts_6() throws Exception {
 		// 6
-		tearDown();
-		setUp();
 		setupCase(mk("DF/DF"), mk("DF"), mk("DF"));
 		writeTrashFile("DF", "different");
 		go();
 		assertRemoved("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_7() throws Exception {
 		// 7
-		tearDown();
-		setUp();
 		doit(mk("DF"), mk("DF"), mk("DF/DF"));
 		assertUpdated("DF");
 		assertRemoved("DF/DF");
@@ -334,29 +339,40 @@ public class ReadTreeTest extends RepositoryTestCase {
 		assertConflict("DF/DF/DF/DF/DF");
 		assertUpdated("DF/DF");
 
+	}
+
+	// 8 ?
+
+	public void testDirectoryFileConflicts_9() throws Exception {
 		// 9
-		tearDown();
-		setUp();
 		doit(mk("DF"), mkmap("DF", "QP"), mk("DF/DF"));
 		assertRemoved("DF/DF");
 		assertUpdated("DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_10() throws Exception {
 		// 10
 		cleanUpDF();
 		doit(mk("DF"), mk("DF/DF"), mk("DF/DF"));
 		assertNoConflicts();
 		
+	}
+
+	public void testDirectoryFileConflicts_11() throws Exception {
 		// 11
-		cleanUpDF();
 		doit(mk("DF"), mk("DF/DF"), mkmap("DF/DF", "asdf"));
 		assertConflict("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_12() throws Exception {
 		// 12
 		cleanUpDF();
 		doit(mk("DF"), mk("DF/DF"), mk("DF"));
 		assertRemoved("DF");
 		assertUpdated("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_13() throws Exception {
 		// 13
 		cleanUpDF();
 		setupCase(mk("DF"), mk("DF/DF"), mk("DF"));
@@ -364,29 +380,39 @@ public class ReadTreeTest extends RepositoryTestCase {
 		go();
 		assertConflict("DF");
 		assertUpdated("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_14() throws Exception {
 		// 14
 		cleanUpDF();
 		doit(mk("DF"), mk("DF/DF"), mkmap("DF", "Foo"));
 		assertConflict("DF");
 		assertUpdated("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_15() throws Exception {
 		// 15
 		doit(mkmap(), mk("DF/DF"), mk("DF"));
 		assertRemoved("DF");
 		assertUpdated("DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_15b() throws Exception {
 		// 15, take 2, just to check multi-leveled
 		doit(mkmap(), mk("DF/DF/DF/DF"), mk("DF"));
 		assertRemoved("DF");
 		assertUpdated("DF/DF/DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_16() throws Exception {
 		// 16
 		cleanUpDF();
 		doit(mkmap(), mk("DF"), mk("DF/DF/DF"));
 		assertRemoved("DF/DF/DF");
 		assertUpdated("DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_17() throws Exception {
 		// 17
 		cleanUpDF();
 		setupCase(mkmap(), mk("DF"), mk("DF/DF/DF"));
@@ -394,13 +420,17 @@ public class ReadTreeTest extends RepositoryTestCase {
 		go();
 		assertConflict("DF/DF/DF");
 		assertUpdated("DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_18() throws Exception {
 		// 18
 		cleanUpDF();
 		doit(mk("DF/DF"), mk("DF/DF/DF/DF"), null);
 		assertRemoved("DF/DF");
 		assertUpdated("DF/DF/DF/DF");
-		
+	}
+
+	public void testDirectoryFileConflicts_19() throws Exception {
 		// 19
 		cleanUpDF();
 		doit(mk("DF/DF/DF/DF"), mk("DF/DF/DF"), null);
-- 
1.5.4.2

[EGIT PATCH 05/10] Fix git sort order compare bug

[Robin Rosenberg]

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../tst/org/spearce/jgit/lib/T0002_Tree.java       |   44 ++++++++++++++++++++
 .../src/org/spearce/jgit/lib/Tree.java             |   10 ++++-
 2 files changed, 52 insertions(+), 2 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0002_Tree.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0002_Tree.java
index 24b368f..7c7f6c0 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0002_Tree.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0002_Tree.java
@@ -17,6 +17,7 @@
 package org.spearce.jgit.lib;
 
 import java.io.IOException;
+import java.io.UnsupportedEncodingException;
 import java.util.ArrayList;
 import java.util.List;
 
@@ -24,6 +25,49 @@ public class T0002_Tree extends RepositoryTestCase {
 	private static final ObjectId SOME_FAKE_ID = new ObjectId(
 			"0123456789abcdef0123456789abcdef01234567");
 
+	private int compareNamesUsingSpecialCompare(String a,String b) throws UnsupportedEncodingException {
+		char lasta = '\0';
+		byte[] abytes;
+		if (a.length() > 0 && a.charAt(a.length()-1) == '/') {
+			lasta = '/';
+			a = a.substring(0, a.length() - 1);
+		}
+		abytes = a.getBytes("ISO-8859-1");
+		char lastb = '\0';
+		byte[] bbytes;
+		if (b.length() > 0 && b.charAt(b.length()-1) == '/') {
+			lastb = '/';
+			b = b.substring(0, b.length() - 1);
+		}
+		bbytes = b.getBytes("ISO-8859-1");
+		return Tree.compareNames(abytes, bbytes, lasta, lastb);
+	}
+
+	public void test000_sort_01() throws UnsupportedEncodingException {
+		assertEquals(0, compareNamesUsingSpecialCompare("a","a"));
+	}
+	public void test000_sort_02() throws UnsupportedEncodingException {
+		assertEquals(-1, compareNamesUsingSpecialCompare("a","b"));
+		assertEquals(1, compareNamesUsingSpecialCompare("b","a"));
+	}
+	public void test000_sort_03() throws UnsupportedEncodingException {
+		assertEquals(1, compareNamesUsingSpecialCompare("a:","a"));
+		assertEquals(1, compareNamesUsingSpecialCompare("a/","a"));
+		assertEquals(-1, compareNamesUsingSpecialCompare("a","a/"));
+		assertEquals(-1, compareNamesUsingSpecialCompare("a","a:"));
+		assertEquals(1, compareNamesUsingSpecialCompare("a:","a/"));
+		assertEquals(-1, compareNamesUsingSpecialCompare("a/","a:"));
+	}
+	public void test000_sort_04() throws UnsupportedEncodingException {
+		assertEquals(-1, compareNamesUsingSpecialCompare("a.a","a/a"));
+		assertEquals(1, compareNamesUsingSpecialCompare("a/a","a.a"));
+	}
+	public void test000_sort_05() throws UnsupportedEncodingException {
+		assertEquals(-1, compareNamesUsingSpecialCompare("a.","a/"));
+		assertEquals(1, compareNamesUsingSpecialCompare("a/","a."));
+
+	}
+
 	public void test001_createEmpty() throws IOException {
 		final Tree t = new Tree(db);
 		assertTrue("isLoaded", t.isLoaded());
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java
index ab83917..5d8e0e0 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java
@@ -65,7 +65,10 @@ public class Tree extends TreeEntry implements Treeish {
 			else if (aj > lastb)
 				return 1;
 			else
-				return 0;
+				if (j == a.length - 1)
+					return 0;
+				else
+					return -1;
 		}
 		if (k < nameEnd) {
 			int bk = nameUTF8[k] & 0xff;
@@ -74,7 +77,10 @@ public class Tree extends TreeEntry implements Treeish {
 			else if (lasta > bk)
 				return 1;
 			else
-				return 0;
+				if (k == nameEnd - 1)
+					return 0;
+				else
+					return 1;
 		}
 		if (lasta < lastb)
 			return -1;
-- 
1.5.4.2

[EGIT PATCH 06/10] Use the proper comparison algorithm

[Robin Rosenberg]

We must walk in Git sort order.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../src/org/spearce/jgit/lib/IndexTreeWalker.java  |   31 +------------------
 1 files changed, 2 insertions(+), 29 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
index 93d5bb2..c17cea1 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
@@ -288,38 +288,11 @@ public class IndexTreeWalker {
 	}
 
 	static int compare(TreeEntry t, Entry i) {
-		if (t.getFullName().equals(i.getName())) {
-			if (t instanceof Tree)
-				return 1;
-			return 0;
-		}
-		return t.getFullName().compareTo(i.getName());
+		return Tree.compareNames(t.getFullNameUTF8(), i.getNameUTF8(), TreeEntry.lastChar(t), TreeEntry.lastChar(i)); 
 	}
 	
 	static int compare(TreeEntry t1, TreeEntry t2) {
-		if (t1.getName().equals(t2.getName())) {
-			if (t1 instanceof Tree && t2 instanceof Tree)
-				return 0;
-			if (t1 instanceof Tree)
-				return 1;
-			if (t2 instanceof Tree)
-				return -1;
-			return 0;
-		}
-		return t1.getName().compareTo(t2.getName());
+		return Tree.compareNames(t1.getNameUTF8(), t2.getNameUTF8(), TreeEntry.lastChar(t1), TreeEntry.lastChar(t2)); 
 	}
 	
-	static int compare(byte[] name1, byte[] name2) {
-		for (int i = 0; i < name1.length && i < name2.length; i++) {
-			if (name1[i] < name2[i])
-				return -1;
-			if (name1[i] > name2[i])
-				return 1;
-		}
-		if (name1.length < name2.length)
-			return -1;
-		if (name2.length < name1.length)
-			return 1;
-		return 0;
-	}
 }
-- 
1.5.4.2

[EGIT PATCH 07/10] GitIndex: Get access to raw name and file mode

[Robin Rosenberg]

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../src/org/spearce/jgit/lib/GitIndex.java         |   15 +++++++++++++++
 1 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/GitIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/GitIndex.java
index 69ed270..d73866a 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/GitIndex.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/GitIndex.java
@@ -598,6 +598,13 @@ public class GitIndex {
 		}
 
 		/**
+		 * @return path name for this entry as byte array, hopefully UTF-8 encoded
+		 */
+		public byte[] getNameUTF8() {
+			return name;
+		}
+
+		/**
 		 * @return SHA-1 of the entry managed by this index
 		 */
 		public ObjectId getObjectId() {
@@ -655,6 +662,14 @@ public class GitIndex {
 			else
 				flags &= ~0x4000;
 		}
+
+		/**
+		 * Return raw file mode bits. See {@link FileMode}
+		 * @return file mode bits
+		 */
+		public int getModeBits() {
+			return mode;
+		}
 	}
 
 	static class Header {
-- 
1.5.4.2

[EGIT PATCH 08/10] TreeEntry: Accessors for full raw name and mode bits

[Robin Rosenberg]

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../src/org/spearce/jgit/lib/TreeEntry.java        |   23 ++++++++++++++++++++
 1 files changed, 23 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/TreeEntry.java b/org.spearce.jgit/src/org/spearce/jgit/lib/TreeEntry.java
index 8d46230..e73f5d5 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/TreeEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/TreeEntry.java
@@ -19,6 +19,8 @@ package org.spearce.jgit.lib;
 import java.io.IOException;
 import java.io.UnsupportedEncodingException;
 
+import org.spearce.jgit.lib.GitIndex.Entry;
+
 /**
  * This class represents an entry in a tree, like a blob or another tree.
  */
@@ -189,6 +191,14 @@ public abstract class TreeEntry implements Comparable {
 		return r.toString();
 	}
 
+	/**
+	 * @return repository relative name of the entry
+	 * FIXME better encoding
+	 */
+	public byte[] getFullNameUTF8() {
+		return getFullName().getBytes();
+	}
+
 	public int compareTo(final Object o) {
 		if (this == o)
 			return 0;
@@ -211,6 +221,19 @@ public abstract class TreeEntry implements Comparable {
 	}
 
 	/**
+	 * Helper for accessing tree/blob/index methods.
+	 *
+	 * @param i
+	 * @return '/' for Tre entries and NUL for non-treeish objects
+	 */
+	final public static int lastChar(Entry i) {
+		// FIXME, gitlink etc. Currently Trees cannot appear in the
+		// index so '\0' is always returned, except maybe for submodules
+		// which we do not support yet.
+		return FileMode.TREE.equals(i.getModeBits()) ? '/' : '\0';
+	}
+
+	/**
 	 * See @{link {@link #accept(TreeVisitor, int)}.
 	 *
 	 * @param tv
-- 
1.5.4.2

[EGIT PATCH 09/10] Implement a Tree iterator

[Robin Rosenberg]

This is an implementation of the Iterator interace. It can
be used for iterating over all entries in a tree in Git
order. Since it is an iterator it can be used to walk more
than one tree in parallel.

Although only post order is needed, preorder and leaves-only
mode is also implemented here.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../spearce/jgit/lib/TreeIteratorLeafOnlyTest.java |   85 +++++++++
 .../jgit/lib/TreeIteratorPostOrderTest.java        |  103 +++++++++++
 .../spearce/jgit/lib/TreeIteratorPreOrderTest.java |  103 +++++++++++
 .../src/org/spearce/jgit/lib/TreeIterator.java     |  182 ++++++++++++++++++++
 4 files changed, 473 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java
new file mode 100644
index 0000000..7d65982
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorLeafOnlyTest.java
@@ -0,0 +1,85 @@
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+
+public class TreeIteratorLeafOnlyTest extends RepositoryTestCase {
+
+	/** Empty tree */
+	public void testEmpty() {
+		Tree tree = new Tree(db);
+		TreeIterator i = makeIterator(tree);
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * one file
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF1() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("x", i.next().getName());
+	}
+
+	/**
+	 * two files
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF2() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a");
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getName());
+		assertEquals("x", i.next().getName());
+	}
+
+	/**
+	 * Empty tree
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleT() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addTree("a");
+		TreeIterator i = makeIterator(tree);
+		assertFalse(i.hasNext());
+	}
+	
+	public void testTricky() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a.b");
+		tree.addFile("a.c");
+		tree.addFile("a/b.b/b");
+		tree.addFile("a/b");
+		tree.addFile("a/c");
+		tree.addFile("a=c");
+		tree.addFile("a=d");
+
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=d", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	private TreeIterator makeIterator(Tree tree) {
+		return new TreeIterator(tree);
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java
new file mode 100644
index 0000000..a6def1d
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPostOrderTest.java
@@ -0,0 +1,103 @@
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+
+public class TreeIteratorPostOrderTest extends RepositoryTestCase {
+
+	/** Empty tree */
+	public void testEmpty() {
+		Tree tree = new Tree(db);
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * one file
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF1() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("x", i.next().getName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * two files
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF2() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a");
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getName());
+		assertEquals("x", i.next().getName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * Empty tree
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleT() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addTree("a");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+	
+	public void testTricky() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a.b");
+		tree.addFile("a.c");
+		tree.addFile("a/b.b/b");
+		tree.addFile("a/b");
+		tree.addFile("a/c");
+		tree.addFile("a=c");
+		tree.addFile("a=d");
+
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("a.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=d", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	private TreeIterator makeIterator(Tree tree) {
+		return new TreeIterator(tree, TreeIterator.Order.POSTORDER);
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java
new file mode 100644
index 0000000..e7e9bf4
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/TreeIteratorPreOrderTest.java
@@ -0,0 +1,103 @@
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+
+public class TreeIteratorPreOrderTest extends RepositoryTestCase {
+
+	/** Empty tree */
+	public void testEmpty() {
+		Tree tree = new Tree(db);
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * one file
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF1() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("x", i.next().getName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * two files
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleF2() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a");
+		tree.addFile("x");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getName());
+		assertEquals("x", i.next().getName());
+		assertFalse(i.hasNext());
+	}
+
+	/**
+	 * Empty tree
+	 * 
+	 * @throws IOException
+	 */
+	public void testSimpleT() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addTree("a");
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+	
+	public void testTricky() throws IOException {
+		Tree tree = new Tree(db);
+		tree.addFile("a.b");
+		tree.addFile("a.c");
+		tree.addFile("a/b.b/b");
+		tree.addFile("a/b");
+		tree.addFile("a/c");
+		tree.addFile("a=c");
+		tree.addFile("a=d");
+
+		TreeIterator i = makeIterator(tree);
+		assertTrue(i.hasNext());
+		assertEquals("", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a.c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/b.b/b", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a/c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=c", i.next().getFullName());
+		assertTrue(i.hasNext());
+		assertEquals("a=d", i.next().getFullName());
+		assertFalse(i.hasNext());
+	}
+
+	private TreeIterator makeIterator(Tree tree) {
+		return new TreeIterator(tree, TreeIterator.Order.PREORDER);
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java
new file mode 100644
index 0000000..e45d1fc
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java
@@ -0,0 +1,182 @@
+/*
+ *  Copyright (C) 2008 Robin Rosenberg
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Lesser General Public
+ *  License, version 2.1, as published by the Free Software Foundation.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Lesser General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public
+ *  License along with this library; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
+ */
+
+package org.spearce.jgit.lib;
+
+import java.io.IOException;
+import java.util.Iterator;
+
+/**
+ * A tree iterator iterates over a tree and all its members recursing into
+ * subtrees according to order.
+ *
+ * Default is to only visit leafs. An {@link Order} value can be supplied to
+ * make the iteration include Tree nodes as well either before or after the
+ * child nodes have been visited.
+ */
+public class TreeIterator implements Iterator<TreeEntry> {
+
+	private Tree tree;
+
+	private int index;
+
+	private TreeIterator sub;
+
+	private Order order;
+
+	private boolean visitTreeNodes;
+
+	private boolean hasVisitedTree;
+
+	/**
+	 * Traversal order
+	 */
+	public enum Order {
+		/**
+		 * Visit node first, then leaves
+		 */
+		PREORDER,
+
+		/**
+		 * Visit leaves first, then node
+		 */
+		POSTORDER
+	};
+
+	/**
+	 * Construct a {@link TreeIterator} for visiting all non-tree nodes.
+	 *
+	 * @param start
+	 */
+	public TreeIterator(Tree start) {
+		this(start, Order.PREORDER, false);
+	}
+
+	/**
+	 * Construct a {@link TreeIterator} visiting all nodes in a tree in a given
+	 * order.
+	 *
+	 * @param start Root node
+	 * @param order {@link Order}
+	 */
+	public TreeIterator(Tree start, Order order) {
+		this(start, order, true);
+	}
+
+	/**
+	 * Construct a {@link TreeIterator}
+	 *
+	 * @param start First node to visit
+	 * @param order Visitation {@link Order}
+	 * @param visitTreeNode True to include tree node
+	 */
+	private TreeIterator(Tree start, Order order, boolean visitTreeNode) {
+		this.tree = start;
+		this.visitTreeNodes = visitTreeNode;
+		this.index = -1;
+		this.order = order;
+		if (!visitTreeNodes)
+			this.hasVisitedTree = true;
+		try {
+			step();
+		} catch (IOException e) {
+			throw new Error(e);
+		}
+	}
+
+	public TreeEntry next() {
+		try {
+			TreeEntry ret = nextTreeEntry();
+			step();
+			return ret;
+		} catch (IOException e) {
+			throw new Error(e);
+		}
+	}
+
+	private TreeEntry nextTreeEntry() throws IOException {
+		TreeEntry ret;
+		if (sub != null)
+			ret = sub.nextTreeEntry();
+		else {
+			if (index < 0 && order == Order.PREORDER) {
+				return tree;
+			}
+			if (order == Order.POSTORDER && index == tree.memberCount()) {
+				return tree;
+			}
+			ret = tree.members()[index];
+		}
+		return ret;
+	}
+
+	public boolean hasNext() {
+		try {
+			return hasNextTreeEntry();
+		} catch (IOException e) {
+			throw new Error(e);
+		}
+	}
+
+	private boolean hasNextTreeEntry() throws IOException {
+		if (tree == null)
+			return false;
+		return sub != null
+			|| index < tree.memberCount()
+			|| order == Order.POSTORDER && index == tree.memberCount();
+	}
+
+	private boolean step() throws IOException {
+		if (tree == null)
+			return false;
+
+		if (sub != null) {
+			if (sub.step())
+				return true;
+			sub = null;
+		}
+
+		if (index < 0 && !hasVisitedTree && order == Order.PREORDER) {
+			hasVisitedTree = true;
+			return true;
+		}
+
+		while (++index < tree.memberCount()) {
+			TreeEntry e = tree.members()[index];
+			if (e instanceof Tree) {
+				sub = new TreeIterator((Tree) e, order, visitTreeNodes);
+				if (sub.hasNextTreeEntry())
+					return true;
+				sub = null;
+				continue;
+			}
+			return true;
+		}
+
+		if (index == tree.memberCount() && !hasVisitedTree
+				&& order == Order.POSTORDER) {
+			hasVisitedTree = true;
+			return true;
+		}
+		return false;
+	}
+
+	public void remove() {
+		throw new IllegalStateException(
+				"TreeIterator does not suppport remove()");
+	}
+}
-- 
1.5.4.2

[EGIT PATCH 10/10] Rewritten IndexTreeWalker

[Robin Rosenberg]

This one works better with git order and hopefull faster
though that is secondary. The IndexTreeWalker used the TreeIterator
for simplicity.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../spearce/jgit/lib/AbstractIndexTreeVisitor.java |    2 +-
 .../src/org/spearce/jgit/lib/IndexDiff.java        |    3 +-
 .../src/org/spearce/jgit/lib/IndexTreeVisitor.java |    3 +-
 .../src/org/spearce/jgit/lib/IndexTreeWalker.java  |  276 +++++++-------------
 .../src/org/spearce/jgit/lib/WorkDirCheckout.java  |    5 +-
 5 files changed, 105 insertions(+), 184 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/AbstractIndexTreeVisitor.java b/org.spearce.jgit/src/org/spearce/jgit/lib/AbstractIndexTreeVisitor.java
index 6f5ede4..c8962f0 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/AbstractIndexTreeVisitor.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/AbstractIndexTreeVisitor.java
@@ -29,7 +29,7 @@ import org.spearce.jgit.lib.GitIndex.Entry;
  *
  */
 public class AbstractIndexTreeVisitor implements IndexTreeVisitor {
-	public void finishVisitTree(Tree tree, Tree auxTree, int i, String curDir)
+	public void finishVisitTree(Tree tree, Tree auxTree, String curDir)
 			throws IOException {
 		// Empty
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexDiff.java b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexDiff.java
index 5ed22d3..45fc084 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexDiff.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexDiff.java
@@ -69,7 +69,8 @@ public class IndexDiff {
 					added.add(indexEntry.getName());
 					anyChanges = true;
 				} else if (indexEntry == null) {
-					removed.add(treeEntry.getFullName());
+					if (!(treeEntry instanceof Tree))
+						removed.add(treeEntry.getFullName());
 					anyChanges = true;
 				} else {
 					if (!treeEntry.getId().equals(indexEntry.getObjectId())) {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeVisitor.java b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeVisitor.java
index 0510711..26f3a33 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeVisitor.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeVisitor.java
@@ -58,11 +58,10 @@ public interface IndexTreeVisitor {
 	 *
 	 * @param tree
 	 * @param auxTree
-	 * @param i
 	 * @param curDir
 	 * @throws IOException
 	 */
-	public void finishVisitTree(Tree tree, Tree auxTree, int i, String curDir) throws IOException;
+	public void finishVisitTree(Tree tree, Tree auxTree, String curDir) throws IOException;
 
 	/**
 	 * Invoked after handling all child nodes of a tree, during two way merge.
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
index c17cea1..8323310 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
@@ -82,189 +82,92 @@ public class IndexTreeWalker {
 	 * @throws IOException
 	 */
 	public void walk() throws IOException {
-		walk(mainTree, newTree, "/");
+		walk(mainTree, newTree, "");
 	}
 
 	private void walk(Tree tree, Tree auxTree, String curDir) throws IOException {
-		TreeEntry[] treeMembers = tree == null ? new TreeEntry[0] : tree.members();
-		TreeEntry[] auxTreeMembers = auxTree == null ? new TreeEntry[0] : auxTree.members();
-		int treeCounter = 0;
-		int auxTreeCounter = 0;
-		
+		TreeIterator mi = new TreeIterator(tree, TreeIterator.Order.POSTORDER);
+		TreeIterator ai = new TreeIterator(auxTree, TreeIterator.Order.POSTORDER);
+		TreeEntry m = mi.hasNext() ? mi.next() : null;
+		TreeEntry a = ai.hasNext() ? ai.next() : null;
 		int curIndexPos = indexCounter;
-		
-		while (treeCounter < treeMembers.length || 
-				indexCounter < indexMembers.length || 
-				auxTreeCounter < auxTreeMembers.length) {
-			TreeEntry h = treeCounter < treeMembers.length ? treeMembers[treeCounter] : null;
-			TreeEntry m = auxTreeCounter < auxTreeMembers.length ? auxTreeMembers[auxTreeCounter] : null;
-			Entry i = indexCounter < indexMembers.length ? indexMembers[indexCounter] : null;
-
-			String indexName = i == null ? null : i.getName();
-			String treeName = h == null ? null : h.getFullName();
-			String auxTreeName = m == null ? null : m.getFullName();
+		Entry i = indexCounter < indexMembers.length ? indexMembers[indexCounter++] : null;
+		while (m != null || a != null || i != null) {
+			int cmpma = compare(m, a);
+			int cmpmi = compare(m, i);
+			int cmpai = compare(a, i);
 			
-			if (treeName != null && indexName != null && auxTreeName != null) { 
-				if (eq(h, i) && eq(m, i)) {
-					// H == I == M
-					visitor.visitEntry(h, m, i, new File(root, treeName));
-					
-					treeCounter++;
-					indexCounter++;
-					auxTreeCounter++;
-				} else if (eq(h, i) && lt(h, m)) {
-					// H == I, H < M
-					visitor.visitEntry(h, null, i, new File(root, treeName));
-					
-					treeCounter++;
-					indexCounter++;
-				} else if (eq(h, m) && lt(h, i)) {
-					// H == M, H < I
-					if (h instanceof Tree) {
-						walk((Tree)h, (Tree)m, "/" + treeName);
-					} else {
-						visitor.visitEntry(h, m, null, new File(root, treeName));
-					}
-					
-					treeCounter++;
-					auxTreeCounter++;
-					
-					
-				} else if (eq(m, i) && lt(i, h)) {
-					// I == M, I < H
-					visitor.visitEntry(null, m, i, new File(root, indexName));
-					
-					indexCounter++;
-					auxTreeCounter++;
-				} else if (lt(h, i) && lt(h, m)) {
-					// H < I, H < M
-					if (h instanceof Tree) {
-						walk((Tree) h, null, "/" + treeName);
-					} else {
-						visitor.visitEntry(h, null, null, new File(root, treeName));
-					}
-					
-					treeCounter++;
-				} else if (lt(m, i) && lt(m, h)) {
-					// M < I, M < H
-					if (m instanceof Tree) {
-						walk(null, (Tree) m, "/" + auxTreeName);
-					} else {
-						visitor.visitEntry(null, m, null, new File(root, auxTreeName));
-					}
-					
-					auxTreeCounter++;
-				} else { // index entry is first
-					// I < H, I < M
-					visitor.visitEntry(null, null, i, new File(root, indexName));
-					
-					indexCounter++;
-				}
-			} else if (treeName != null && indexName != null) {
-				if (eq(h, i)) {
-					if (threeTrees)
-						visitor.visitEntry(h, null, i, new File(root, indexName));
-					else visitor.visitEntry(h, i, new File(root, indexName));
-					
-					treeCounter++;
-					indexCounter++;
-				} else if (lt(h, i)) {
-					if (h instanceof Tree) 
-						walk((Tree) h, null, "/" + treeName);
-					else {
-						if (threeTrees) {
-							visitor.visitEntry(h, null, null, new File(root, treeName));
-						} else visitor.visitEntry(h, null, new File(root, treeName));
-					}
-					
-					treeCounter++;
-				} else { // lt(i, h)
-					if (threeTrees) {
-						visitor.visitEntry(null, null, i, new File(root, indexName));
-					} else visitor.visitEntry(null, i, new File(root, indexName));
-					
-					indexCounter++;
-				}
-			} else if (treeName != null && auxTreeName != null) {
-				if (eq(h, m)) {
-					if (h instanceof Tree) {
-						walk((Tree) h, (Tree) m, "/" + treeName);
-					} else {
-						visitor.visitEntry(h, m, null, new File(root, treeName));
-					}
-					
-					treeCounter++;
-					auxTreeCounter++;
-				} else if (lt(h, m)) {
-					if (h instanceof Tree) {
-						walk((Tree) h, null, "/" + treeName);
-					} else {
-						visitor.visitEntry(h, null, null, new File(root, treeName));
-					}
-					
-					treeCounter++;
-				} else { // lt(m, h)
-					if (m instanceof Tree) {
-						walk(null, (Tree) m, "/" + auxTreeName);
-					} else {
-						visitor.visitEntry(null, m, null, new File("/" + auxTreeName));
-					}
-						
-					auxTreeCounter++;
-				}
-				
-			} else if (indexName != null && auxTreeName != null) {
-				if (eq(m, i)) {
-					visitor.visitEntry(null, m, i, new File(root, indexName));
-					
-					auxTreeCounter++;
-					indexCounter++;
-				} else if (lt(m, i)) {
-					if (m instanceof Tree) 
-						walk(null, (Tree) m, "/" + auxTreeName);
-					else {
-						visitor.visitEntry(null, m, null, new File(root, auxTreeName));
-					}
-					
-					auxTreeCounter++;
-				} else { // lt(i, m)
-					visitor.visitEntry(null, null, i, new File(root, indexName));
-					
-					indexCounter++;
-				}
-			} else if (treeName != null) {
-				if (h instanceof Tree) {
-					walk((Tree) h, null, "/" + treeName);
-				} else if (threeTrees)
-					visitor.visitEntry(h, null, null, new File(root, treeName));
-				else visitor.visitEntry(h, null, new File(root, treeName));
-				
-				treeCounter++;
-			} else if (auxTreeName != null) {
-				if (m instanceof Tree) {
-					walk(null, (Tree)m, "/" + auxTreeName);
-				} else visitor.visitEntry(null, m, null, new File(root, auxTreeName));
-				
-				auxTreeCounter++;
-			} else if (indexName != null) {
-				// need to check if we're done with this tree
-				String curDirNoSlash = curDir.substring(1);
-				if (!indexName.startsWith(curDirNoSlash + "/") && curDirNoSlash.length() != 0)
-					break;
-				
-				if (threeTrees)
-					visitor.visitEntry(null, null, i, new File(root, indexName));
-				else visitor.visitEntry(null, i, new File(root, indexName));
-				indexCounter++;
-			}
+			TreeEntry pm = cmpma <= 0 && cmpmi <= 0 ? m : null;
+			TreeEntry pa = cmpma >= 0 && cmpai <= 0 ? a : null;
+			Entry     pi = cmpmi >= 0 && cmpai >= 0 ? i : null;
+
+			if (pi != null)
+				visitEntry(pm, pa, pi, root);
+			else
+				finishVisitTree(pm, pa, curIndexPos, root);
+
+			if (pm != null) m = mi.hasNext() ? mi.next() : null;
+			if (pa != null) a = ai.hasNext() ? ai.next() : null;
+			if (pi != null) i = indexCounter < indexMembers.length ? indexMembers[indexCounter++] : null;
 		}
-		
-		if (threeTrees) {
-			visitor.finishVisitTree(tree, auxTree, indexCounter - curIndexPos, 
-					curDir.substring(1));
-		} else {
-			visitor.finishVisitTree(tree, indexCounter - curIndexPos, curDir);
+	}
+
+	private void visitEntry(TreeEntry t1, TreeEntry t2,
+			Entry i, File root) throws IOException {
+
+		assert t1 != null || t2 != null || i != null : "Needs at least one entry";
+		assert root != null : "Needs workdir";
+
+		if (t1 != null && t1.getParent() == null)
+			t1 = null;
+		if (t2 != null && t2.getParent() == null)
+			t2 = null;
+
+		File f = null;
+		if (i != null)
+			f = new File(root, i.getName());
+		else if (t1 != null)
+			f = new File(root, t1.getFullName());
+		else if (t2 != null)
+			f = new File(root, t2.getFullName());
+
+		if (t1 != null || t2 != null || i != null)
+			if (threeTrees)
+				visitor.visitEntry(t1, t2, i, f);
+			else
+				visitor.visitEntry(t1, i, f);
+	}
+
+	private void finishVisitTree(TreeEntry t1, TreeEntry t2, int curIndexPos, File root)
+			throws IOException {
+
+		assert t1 != null || t2 != null : "Needs at least one entry";
+		assert root != null : "Needs workdir";
+
+		if (t1 != null && t1.getParent() == null)
+			t1 = null;
+		if (t2 != null && t2.getParent() == null)
+			t2 = null;
+
+		File f = null;
+		String c= null;
+		if (t1 != null) {
+			c = t1.getFullName();
+			f = new File(root, c);
+		} else if (t2 != null) {
+			c = t2.getFullName();
+			f = new File(root, c);
 		}
+		if (t1 instanceof Tree || t2 instanceof Tree)
+			if (threeTrees)
+				visitor.finishVisitTree((Tree)t1, (Tree)t2, c);
+			else
+				visitor.finishVisitTree((Tree)t1, indexCounter - curIndexPos, c);
+		else if (t1 != null || t2 != null)
+			if (threeTrees)
+				visitor.visitEntry(t1, t2, null, f);
+			else
+				visitor.visitEntry(t1, null, f);
 	}
 
 	static boolean lt(TreeEntry h, Entry i) {
@@ -288,11 +191,30 @@ public class IndexTreeWalker {
 	}
 
 	static int compare(TreeEntry t, Entry i) {
+		if (t == null && i == null)
+			return 0;
+		if (t == null)
+			return 1;
+		if (i == null)
+			return -1;
 		return Tree.compareNames(t.getFullNameUTF8(), i.getNameUTF8(), TreeEntry.lastChar(t), TreeEntry.lastChar(i)); 
 	}
 	
 	static int compare(TreeEntry t1, TreeEntry t2) {
-		return Tree.compareNames(t1.getNameUTF8(), t2.getNameUTF8(), TreeEntry.lastChar(t1), TreeEntry.lastChar(t2)); 
+		if (t1 != null && t1.getParent() == null && t2 != null && t2.getParent() == null)
+			return 0;
+		if (t1 != null && t1.getParent() == null)
+			return -1;
+		if (t2 != null && t2.getParent() == null)
+			return 1;
+
+		if (t1 == null && t2 == null)
+			return 0;
+		if (t1 == null)
+			return 1;
+		if (t2 == null)
+			return -1;
+		return Tree.compareNames(t1.getFullNameUTF8(), t2.getFullNameUTF8(), TreeEntry.lastChar(t1), TreeEntry.lastChar(t2));
 	}
 	
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WorkDirCheckout.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WorkDirCheckout.java
index 04785e4..40ad332 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WorkDirCheckout.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WorkDirCheckout.java
@@ -243,11 +243,10 @@ public class WorkDirCheckout {
 			}
 	
 			@Override
-			public void finishVisitTree(Tree tree, Tree auxTree, int i,
-					String curDir) throws IOException {
+			public void finishVisitTree(Tree tree, Tree auxTree, String curDir) throws IOException {
 				if (curDir.length() == 0) return;
 				
-				if (auxTree != null && i == 0) {
+				if (auxTree != null) {
 					if (index.getEntry(curDir) != null)
 						removed.add(curDir);
 				} 
-- 
1.5.4.2

Re: [EGIT] Sort order from hell fixes, take 2

[David Watson]

I've looked over this a bit, and it looks like a good set of changes. 


On Sun, Feb 24, 2008 at 12:50:33AM +0100, Robin Rosenberg wrote:
> Hi fans,
> 
> My previous attempt to fix this failed, so here is another round, including
> some new infrastructure like a TreeIterator to support this fix and whatever
> will need it.
> 
> Feed free to scrutize and invent whatever evil test case might be missing.
> 
> The reason I noticed the problem was introduced in c20142, where the unit
> tests for org.spearce.jgit was moved to the new project org.spearce.jgit.test .
> 
> -- robin
> 
> 

-- 
Dave Watson
Software Engineer
MIMvista Corp