* [EGIT] Sort order from hell fixes, take 2 @ 2008-02-23 23:50 Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 01/10] Tighten IndexDiffTest to make it test better what it claims to test Robin Rosenberg 2008-03-03 14:17 ` [EGIT] Sort order from hell fixes, take 2 David Watson 0 siblings, 2 replies; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [EGIT PATCH 01/10] Tighten IndexDiffTest to make it test better what it claims to test 2008-02-23 23:50 [EGIT] Sort order from hell fixes, take 2 Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 02/10] Extend IndexDiffTest with more tests Robin Rosenberg 2008-03-03 14:17 ` [EGIT] Sort order from hell fixes, take 2 David Watson 1 sibling, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 02/10] Extend IndexDiffTest with more tests 2008-02-23 23:50 ` [EGIT PATCH 01/10] Tighten IndexDiffTest to make it test better what it claims to test Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 03/10] WorkdirCheckout: more test for names that are close Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 03/10] WorkdirCheckout: more test for names that are close 2008-02-23 23:50 ` [EGIT PATCH 02/10] Extend IndexDiffTest with more tests Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 04/10] Split a big test in ReadTreeTest into smaller tests Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 04/10] Split a big test in ReadTreeTest into smaller tests 2008-02-23 23:50 ` [EGIT PATCH 03/10] WorkdirCheckout: more test for names that are close Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 05/10] Fix git sort order compare bug Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 05/10] Fix git sort order compare bug 2008-02-23 23:50 ` [EGIT PATCH 04/10] Split a big test in ReadTreeTest into smaller tests Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 06/10] Use the proper comparison algorithm Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 06/10] Use the proper comparison algorithm 2008-02-23 23:50 ` [EGIT PATCH 05/10] Fix git sort order compare bug Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 07/10] GitIndex: Get access to raw name and file mode Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 07/10] GitIndex: Get access to raw name and file mode 2008-02-23 23:50 ` [EGIT PATCH 06/10] Use the proper comparison algorithm Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 08/10] TreeEntry: Accessors for full raw name and mode bits Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 08/10] TreeEntry: Accessors for full raw name and mode bits 2008-02-23 23:50 ` [EGIT PATCH 07/10] GitIndex: Get access to raw name and file mode Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 09/10] Implement a Tree iterator Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 09/10] Implement a Tree iterator 2008-02-23 23:50 ` [EGIT PATCH 08/10] TreeEntry: Accessors for full raw name and mode bits Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 10/10] Rewritten IndexTreeWalker Robin Rosenberg 0 siblings, 1 reply; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* [EGIT PATCH 10/10] Rewritten IndexTreeWalker 2008-02-23 23:50 ` [EGIT PATCH 09/10] Implement a Tree iterator Robin Rosenberg @ 2008-02-23 23:50 ` Robin Rosenberg 0 siblings, 0 replies; 12+ messages in thread From: Robin Rosenberg @ 2008-02-23 23:50 UTC (permalink / raw) To: git; +Cc: David Watson, 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 ^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [EGIT] Sort order from hell fixes, take 2 2008-02-23 23:50 [EGIT] Sort order from hell fixes, take 2 Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 01/10] Tighten IndexDiffTest to make it test better what it claims to test Robin Rosenberg @ 2008-03-03 14:17 ` David Watson 1 sibling, 0 replies; 12+ messages in thread From: David Watson @ 2008-03-03 14:17 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2008-03-03 14:17 UTC | newest] Thread overview: 12+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2008-02-23 23:50 [EGIT] Sort order from hell fixes, take 2 Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 01/10] Tighten IndexDiffTest to make it test better what it claims to test Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 02/10] Extend IndexDiffTest with more tests Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 03/10] WorkdirCheckout: more test for names that are close Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 04/10] Split a big test in ReadTreeTest into smaller tests Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 05/10] Fix git sort order compare bug Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 06/10] Use the proper comparison algorithm Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 07/10] GitIndex: Get access to raw name and file mode Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 08/10] TreeEntry: Accessors for full raw name and mode bits Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 09/10] Implement a Tree iterator Robin Rosenberg 2008-02-23 23:50 ` [EGIT PATCH 10/10] Rewritten IndexTreeWalker Robin Rosenberg 2008-03-03 14:17 ` [EGIT] Sort order from hell fixes, take 2 David Watson
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).