[EGIT Patches] Sort order from hell fixes

[EGIT Patches] Sort order from hell fixes

[Robin Rosenberg]

This fixes conflict detection in checkout that yielded false conflicts
and, according to a user, a problem where checkin did not find anything
to check in.

-- robin

[EGIT PATCH 1/2] 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.rc4.25.g81cc

[EGIT PATCH 2/2] Resort entries in "normal" order before looking for conflicts

[Robin Rosenberg]

When checking out another branch we get a problem if our version contains
a tree name that is longer, but has another tree as a prefix.

        Our tree
          a/a
          a.a/b

        Other tree
          a/a

The conflict comes from names not being compared properly in git
order.

Directory/File conflicts are not easy to handle. This solution
is cheating, but solved a real user's problem.

This commit adds test cases for the particular problem plus one
similar test that didn't fail before either.

Signed-off-by: Robin Rosenberg <robin.rosenberg@dewire.com>
---
 .../tst/org/spearce/jgit/lib/ReadTreeTest.java     |   16 ++++++++-
 .../src/org/spearce/jgit/lib/IndexTreeWalker.java  |   35 ++++++++++++--------
 2 files changed, 36 insertions(+), 15 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();
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..bc2fb23 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java
@@ -19,6 +19,8 @@ package org.spearce.jgit.lib;
 
 import java.io.File;
 import java.io.IOException;
+import java.util.Arrays;
+import java.util.Comparator;
 
 import org.spearce.jgit.lib.GitIndex.Entry;
 
@@ -85,9 +87,28 @@ public class IndexTreeWalker {
 		walk(mainTree, newTree, "/");
 	}
 
+	static Comparator<TreeEntry> treeEntryPlainComparator() {
+		return new Comparator<TreeEntry>() {
+			public int compare(TreeEntry o1, TreeEntry o2) {
+				return o1.getName().compareTo(o2.getName());
+			}
+		};
+	}
+
+	static Comparator<Entry> indexEntryPlainComparator() {
+		return new Comparator<Entry>() {
+			public int compare(Entry o1, Entry o2) {
+				return o1.getName().compareTo(o2.getName());
+			}
+		};
+	}
+
 	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();
+		Arrays.sort(treeMembers, treeEntryPlainComparator());
+		Arrays.sort(auxTreeMembers, treeEntryPlainComparator());
+		Arrays.sort(indexMembers, indexEntryPlainComparator());
 		int treeCounter = 0;
 		int auxTreeCounter = 0;
 		
@@ -308,18 +329,4 @@ public class IndexTreeWalker {
 		}
 		return t1.getName().compareTo(t2.getName());
 	}
-	
-	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.rc4.25.g81cc

Re: [EGIT PATCH 2/2] Resort entries in "normal" order before looking for conflicts

[Robin Rosenberg]

Forget this one, it just causes other problems.

-- robin

Re: [EGIT PATCH 2/2] Resort entries in "normal" order before looking for conflicts

[Robin Rosenberg]

>From 39d5e19cd2e16f476501fda71d6551e51225ed2d Mon Sep 17 00:00:00 2001
From: Robin Rosenberg <robin.rosenberg@dewire.com>
Date: Sun, 10 Feb 2008 20:03:06 +0100
Subject: [PATCH] Extend IndexDiffTest with more tests

In order to fix a bug where everything is marked as modified, or in some cases
not modified the unit tests. The fixes here continue to work, but I want to
emphasize the tests. Comments?

---
 .../tst/org/spearce/jgit/lib/IndexDiffTest.java    |   67 ++++++++++++++++++++
 1 files changed, 67 insertions(+), 0 deletions(-)

One more to come (that fails).

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.rc4.25.g81cc

Re: [EGIT PATCH 2/2] Resort entries in "normal" order before looking for conflicts

[Robin Rosenberg]

söndagen den 10 februari 2008 skrev Robin Rosenberg:
> In order to fix a bug where everything is marked as modified, or in some cases
> not modified the unit tests. The fixes here continue to work, but I want to
> emphasize the tests. Comments?

Actually the reverse. This the extension that works, the previous mail contains
the test that fails, i.e. testUnchangedComplex().

You need this patch first though. 

-- robin

From 6d169c4e682359d8832047662591e341e91d186d Mon Sep 17 00:00:00 2001
From: Robin Rosenberg <robin.rosenberg@dewire.com>
Date: Sun, 10 Feb 2008 20:01:53 +0100
Subject: [PATCH] Tighten IndexDiffTest to make it test better what it claims to test

---
 .../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.rc4.25.g81cc

Re: [EGIT PATCH 2/2] Resort entries in "normal" order before looking for conflicts

[David Watson]

Looks reasonable enough to me. 

On Sun, Feb 10, 2008 at 09:18:29PM +0100, Robin Rosenberg wrote:
> söndagen den 10 februari 2008 skrev Robin Rosenberg:
> > In order to fix a bug where everything is marked as modified, or in some cases
> > not modified the unit tests. The fixes here continue to work, but I want to
> > emphasize the tests. Comments?
> 
> Actually the reverse. This the extension that works, the previous mail contains
> the test that fails, i.e. testUnchangedComplex().
> 
> You need this patch first though. 
> 
> -- robin
> 
> From 6d169c4e682359d8832047662591e341e91d186d Mon Sep 17 00:00:00 2001
> From: Robin Rosenberg <robin.rosenberg@dewire.com>
> Date: Sun, 10 Feb 2008 20:01:53 +0100
> Subject: [PATCH] Tighten IndexDiffTest to make it test better what it claims to test
> 
> ---
>  .../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.rc4.25.g81cc
> 

-- 
Dave Watson
Software Engineer
MIMvista Corp