From be97c4558992a437cde235aafc7ae2bd6df84ac8 Mon Sep 17 00:00:00 2001 From: Sebastian Thiel Date: Tue, 22 Jun 2010 21:23:47 +0200 Subject: Initial frame for implementing read_tree using pure python. As git-read-tree can do much more than we can ( and faster assumably ), the .new method is used to create new index instances from up to 3 trees. Implemented multi-tree traversal to facilitate building a stage list more efficiently ( although I am not sure whether it could be faster to use a dictionary together with some intensive lookup ), including test Added performance to learn how fast certain operations are, and whether one should be preferred over another --- test/git/test_fun.py | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) create mode 100644 test/git/test_fun.py (limited to 'test/git/test_fun.py') diff --git a/test/git/test_fun.py b/test/git/test_fun.py new file mode 100644 index 00000000..ccf15c77 --- /dev/null +++ b/test/git/test_fun.py @@ -0,0 +1,70 @@ +from test.testlib import * +from git.objects.fun import ( + traverse_tree_recursive, + traverse_trees_recursive + ) + +from git.index.fun import ( + aggressive_tree_merge + ) + +class TestFun(TestBase): + + def test_aggressive_tree_merge(self): + # head tree with additions, removals and modification compared to its predecessor + HC = self.rorepo.commit("6c1faef799095f3990e9970bc2cb10aa0221cf9c") + H = HC.tree + B = HC.parents[0].tree + + # test new index from single tree + + def _assert_entries(self, entries, num_trees): + assert len(entries[0]) == num_trees + for entry in entries: + paths = set(e[2] for e in entry if e) + + # only one path per set of entries + assert len(paths) == 1 + # END verify entry + + def test_tree_traversal(self): + # low level tree tarversal + odb = self.rorepo.odb + H = self.rorepo.tree('29eb123beb1c55e5db4aa652d843adccbd09ae18') # head tree + M = self.rorepo.tree('e14e3f143e7260de9581aee27e5a9b2645db72de') # merge tree + B = self.rorepo.tree('f606937a7a21237c866efafcad33675e6539c103') # base tree + B_old = self.rorepo.tree('1f66cfbbce58b4b552b041707a12d437cc5f400a') # old base tree + + # two very different trees + entries = traverse_trees_recursive(odb, [B_old.sha, H.sha], '') + self._assert_entries(entries, 2) + + oentries = traverse_trees_recursive(odb, [H.sha, B_old.sha], '') + assert len(oentries) == len(entries) + self._assert_entries(oentries, 2) + + # single tree + is_no_tree = lambda i, d: i.type != 'tree' + entries = traverse_trees_recursive(odb, [B.sha], '') + assert len(entries) == len(list(B.traverse(predicate=is_no_tree))) + self._assert_entries(entries, 1) + + # two trees + entries = traverse_trees_recursive(odb, [B.sha, H.sha], '') + self._assert_entries(entries, 2) + + # tree trees + entries = traverse_trees_recursive(odb, [B.sha, H.sha, M.sha], '') + self._assert_entries(entries, 3) + + def test_tree_traversal_single(self): + max_count = 50 + count = 0 + odb = self.rorepo.odb + for commit in self.rorepo.commit("29eb123beb1c55e5db4aa652d843adccbd09ae18").traverse(): + if count >= max_count: + break + count += 1 + entries = traverse_tree_recursive(odb, commit.tree.sha, '') + assert entries + # END for each commit -- cgit v1.2.3 From c0ef65b43688b1a4615a1e7332f6215f9a8abb19 Mon Sep 17 00:00:00 2001 From: Sebastian Thiel Date: Wed, 23 Jun 2010 00:28:36 +0200 Subject: Implemented simple tree merging and a simple test, more elaborate testing is in progress --- test/git/test_fun.py | 64 ++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 57 insertions(+), 7 deletions(-) (limited to 'test/git/test_fun.py') diff --git a/test/git/test_fun.py b/test/git/test_fun.py index ccf15c77..4ddc1910 100644 --- a/test/git/test_fun.py +++ b/test/git/test_fun.py @@ -8,17 +8,67 @@ from git.index.fun import ( aggressive_tree_merge ) +from git.index import IndexFile +from stat import ( + S_IFDIR, + S_IFREG, + S_IFLNK + ) + class TestFun(TestBase): + def _assert_index_entries(self, entries, trees): + index = IndexFile.from_tree(self.rorepo, *trees) + assert entries + assert len(index.entries) == len(entries) + for entry in entries: + assert (entry.path, entry.stage) in index.entries + # END assert entry matches fully + def test_aggressive_tree_merge(self): # head tree with additions, removals and modification compared to its predecessor + odb = self.rorepo.odb HC = self.rorepo.commit("6c1faef799095f3990e9970bc2cb10aa0221cf9c") H = HC.tree B = HC.parents[0].tree - # test new index from single tree + # entries from single tree + trees = [H.sha] + self._assert_index_entries(aggressive_tree_merge(odb, trees), trees) + + # from multiple trees + trees = [B.sha, H.sha] + self._assert_index_entries(aggressive_tree_merge(odb, trees), trees) + + # three way, no conflict + tree = self.rorepo.tree + B = tree("35a09c0534e89b2d43ec4101a5fb54576b577905") + H = tree("4fe5cfa0e063a8d51a1eb6f014e2aaa994e5e7d4") + M = tree("1f2b19de3301e76ab3a6187a49c9c93ff78bafbd") + trees = [B.sha, H.sha, M.sha] + self._assert_index_entries(aggressive_tree_merge(odb, trees), trees) + + # three-way, conflict in at least one file, both modified + B = tree("a7a4388eeaa4b6b94192dce67257a34c4a6cbd26") + H = tree("f9cec00938d9059882bb8eabdaf2f775943e00e5") + M = tree("44a601a068f4f543f73fd9c49e264c931b1e1652") + trees = [B.sha, H.sha, M.sha] + self._assert_index_entries(aggressive_tree_merge(odb, trees), trees) + + def make_tree(odb, entries): + """create a tree from the given tree entries and safe it to the database""" + + + @with_rw_repo('0.1.6') + def test_three_way_merge(self, rwrepo): + def mkfile(name, sha, executable=0): + return (sha, S_IFREG | 644 | executable*0111, name) + def mkcommit(name, sha): + return (sha, S_IFDIR | S_IFLNK, name) + odb = rwrepo.odb + - def _assert_entries(self, entries, num_trees): + def _assert_tree_entries(self, entries, num_trees): assert len(entries[0]) == num_trees for entry in entries: paths = set(e[2] for e in entry if e) @@ -37,25 +87,25 @@ class TestFun(TestBase): # two very different trees entries = traverse_trees_recursive(odb, [B_old.sha, H.sha], '') - self._assert_entries(entries, 2) + self._assert_tree_entries(entries, 2) oentries = traverse_trees_recursive(odb, [H.sha, B_old.sha], '') assert len(oentries) == len(entries) - self._assert_entries(oentries, 2) + self._assert_tree_entries(oentries, 2) # single tree is_no_tree = lambda i, d: i.type != 'tree' entries = traverse_trees_recursive(odb, [B.sha], '') assert len(entries) == len(list(B.traverse(predicate=is_no_tree))) - self._assert_entries(entries, 1) + self._assert_tree_entries(entries, 1) # two trees entries = traverse_trees_recursive(odb, [B.sha, H.sha], '') - self._assert_entries(entries, 2) + self._assert_tree_entries(entries, 2) # tree trees entries = traverse_trees_recursive(odb, [B.sha, H.sha, M.sha], '') - self._assert_entries(entries, 3) + self._assert_tree_entries(entries, 3) def test_tree_traversal_single(self): max_count = 50 -- cgit v1.2.3 From aea0243840a46021e6f77c759c960a06151d91c9 Mon Sep 17 00:00:00 2001 From: Sebastian Thiel Date: Wed, 23 Jun 2010 13:49:05 +0200 Subject: Added test for aggressive_tree_merge --- test/git/test_fun.py | 111 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 106 insertions(+), 5 deletions(-) (limited to 'test/git/test_fun.py') diff --git a/test/git/test_fun.py b/test/git/test_fun.py index 4ddc1910..ce610014 100644 --- a/test/git/test_fun.py +++ b/test/git/test_fun.py @@ -1,20 +1,26 @@ from test.testlib import * from git.objects.fun import ( traverse_tree_recursive, - traverse_trees_recursive + traverse_trees_recursive, + tree_to_stream ) from git.index.fun import ( aggressive_tree_merge ) -from git.index import IndexFile +from gitdb.base import IStream +from gitdb.typ import str_tree_type + from stat import ( S_IFDIR, S_IFREG, S_IFLNK ) +from git.index import IndexFile +from cStringIO import StringIO + class TestFun(TestBase): def _assert_index_entries(self, entries, trees): @@ -55,18 +61,113 @@ class TestFun(TestBase): trees = [B.sha, H.sha, M.sha] self._assert_index_entries(aggressive_tree_merge(odb, trees), trees) - def make_tree(odb, entries): + def mktree(self, odb, entries): """create a tree from the given tree entries and safe it to the database""" - + sio = StringIO() + tree_to_stream(entries, sio.write) + sio.seek(0) + istream = odb.store(IStream(str_tree_type, len(sio.getvalue()), sio)) + return istream.sha @with_rw_repo('0.1.6') def test_three_way_merge(self, rwrepo): def mkfile(name, sha, executable=0): - return (sha, S_IFREG | 644 | executable*0111, name) + return (sha, S_IFREG | 0644 | executable*0111, name) def mkcommit(name, sha): return (sha, S_IFDIR | S_IFLNK, name) + def assert_entries(entries, num_entries, has_conflict=False): + assert len(entries) == num_entries + assert has_conflict == (len([e for e in entries if e.stage != 0]) > 0) + mktree = self.mktree + + shaa = "\1"*20 + shab = "\2"*20 + shac = "\3"*20 + odb = rwrepo.odb + # base tree + bfn = 'basefile' + fbase = mkfile(bfn, shaa) + tb = mktree(odb, [fbase]) + + # non-conflicting new files, same data + fa = mkfile('1', shab) + th = mktree(odb, [fbase, fa]) + fb = mkfile('2', shac) + tm = mktree(odb, [fbase, fb]) + + # two new files, same base file + trees = [tb, th, tm] + assert_entries(aggressive_tree_merge(odb, trees), 3) + + # both delete same file, add own one + fa = mkfile('1', shab) + th = mktree(odb, [fa]) + fb = mkfile('2', shac) + tm = mktree(odb, [fb]) + + # two new files + trees = [tb, th, tm] + assert_entries(aggressive_tree_merge(odb, trees), 2) + + # modify same base file, differently + fa = mkfile(bfn, shab) + th = mktree(odb, [fa]) + fb = mkfile(bfn, shac) + tm = mktree(odb, [fb]) + + # conflict, 3 versions on 3 stages + trees = [tb, th, tm] + assert_entries(aggressive_tree_merge(odb, trees), 3, True) + + + # change mode on same base file, by making one a commit, the other executable + # no content change ( this is totally unlikely to happen in the real world ) + fa = mkcommit(bfn, shaa) + th = mktree(odb, [fa]) + fb = mkfile(bfn, shaa, executable=1) + tm = mktree(odb, [fb]) + + # conflict, 3 versions on 3 stages, because of different mode + trees = [tb, th, tm] + assert_entries(aggressive_tree_merge(odb, trees), 3, True) + + for is_them in range(2): + # only we/they change contents + fa = mkfile(bfn, shab) + th = mktree(odb, [fa]) + + trees = [tb, th, tb] + if is_them: + trees = [tb, tb, th] + entries = aggressive_tree_merge(odb, trees) + assert len(entries) == 1 and entries[0].binsha == shab + + # only we/they change the mode + fa = mkcommit(bfn, shaa) + th = mktree(odb, [fa]) + + trees = [tb, th, tb] + if is_them: + trees = [tb, tb, th] + entries = aggressive_tree_merge(odb, trees) + assert len(entries) == 1 and entries[0].binsha == shaa and entries[0].mode == fa[1] + + # one side deletes, the other changes = conflict + fa = mkfile(bfn, shab) + th = mktree(odb, [fa]) + tm = mktree(odb, []) + trees = [tb, th, tm] + if is_them: + trees = [tb, tm, th] + # as one is deleted, there are only 2 entries + assert_entries(aggressive_tree_merge(odb, trees), 2, True) + # END handle ours, theirs + + + + def _assert_tree_entries(self, entries, num_trees): assert len(entries[0]) == num_trees -- cgit v1.2.3 From 1e2265a23ecec4e4d9ad60d788462e7f124f1bb7 Mon Sep 17 00:00:00 2001 From: Sebastian Thiel Date: Wed, 23 Jun 2010 15:48:57 +0200 Subject: fixed critical bug in traverse_trees_recursive, implemented IndexFile.new including simple test, it may be simple as the methods it uses are throroughly tested --- test/git/test_fun.py | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'test/git/test_fun.py') diff --git a/test/git/test_fun.py b/test/git/test_fun.py index ce610014..b2b94415 100644 --- a/test/git/test_fun.py +++ b/test/git/test_fun.py @@ -60,6 +60,9 @@ class TestFun(TestBase): M = tree("44a601a068f4f543f73fd9c49e264c931b1e1652") trees = [B.sha, H.sha, M.sha] self._assert_index_entries(aggressive_tree_merge(odb, trees), trees) + + # too many trees + self.failUnlessRaises(ValueError, aggressive_tree_merge, odb, trees*2) def mktree(self, odb, entries): """create a tree from the given tree entries and safe it to the database""" @@ -164,14 +167,10 @@ class TestFun(TestBase): # as one is deleted, there are only 2 entries assert_entries(aggressive_tree_merge(odb, trees), 2, True) # END handle ours, theirs - - - - def _assert_tree_entries(self, entries, num_trees): - assert len(entries[0]) == num_trees for entry in entries: + assert len(entry) == num_trees paths = set(e[2] for e in entry if e) # only one path per set of entries -- cgit v1.2.3