fix(tree): show that fixing Tree.cache is not possible

The problem is that a per-tree modification API cannot work properly, as the sorting is based
on full paths of all entries within the repository. This feat can only be achieved by the index,
which to my knowledge already does it correctly.

The only fix is to remove the misleading API entirely, which will happen in the next commit.

Related to #369

2 files changed, 64 insertions, 43 deletions

diff --git a/git/objects/tree.py b/git/objects/tree.py
index e7d579d0..4f853f92 100644
--- a/git/objects/tree.py
+++ b/git/objects/tree.py
@@ -35,33 +35,42 @@ def git_cmp(t1, t2):
     if min_cmp:
         return min_cmp
 
-    return len_b - len_a
+    return len_a - len_b
 
-if PY3:
-    # taken from https://wiki.python.org/moin/HowTo/Sorting#The_Old_Way_Using_the_cmp_Parameter
-    class CmpToKey(object):
-        __slots__ = 'obj'
 
-        def __init__(self, obj, *args):
-            self.obj = obj
+def merge_sort(a, cmp):
+    if len(a) < 2:
+        return
 
-        def __lt__(self, other):
-            return git_cmp(self.obj, other.obj) < 0
+    mid = len(a) // 2
+    lefthalf = a[:mid]
+    righthalf = a[mid:]
 
-        def __gt__(self, other):
-            return git_cmp(self.obj, other.obj) > 0
+    merge_sort(lefthalf, cmp)
+    merge_sort(righthalf, cmp)
 
-        def __eq__(self, other):
-            return git_cmp(self.obj, other.obj) == 0
+    i = 0
+    j = 0
+    k = 0
 
-        def __le__(self, other):
-            return git_cmp(self.obj, other.obj) <= 0
+    while i < len(lefthalf) and j < len(righthalf):
+        if cmp(lefthalf[i], righthalf[j]) <= 0:
+            a[k] = lefthalf[i]
+            i = i + 1
+        else:
+            a[k] = righthalf[j]
+            j = j + 1
+        k = k + 1
 
-        def __ge__(self, other):
-            return git_cmp(self.obj, other.obj) >= 0
+    while i < len(lefthalf):
+        a[k] = lefthalf[i]
+        i = i + 1
+        k = k + 1
 
-        def __ne__(self, other):
-            return git_cmp(self.obj, other.obj) != 0
+    while j < len(righthalf):
+        a[k] = righthalf[j]
+        j = j + 1
+        k = k + 1
 
 
 class TreeModifier(object):
@@ -90,10 +99,7 @@ class TreeModifier(object):
         It may be called several times, but be aware that each call will cause
         a sort operation
         :return self:"""
-        if PY3:
-            self._cache.sort(key=CmpToKey)
-        else:
-            self._cache.sort(cmp=git_cmp)
+        merge_sort(self._cache, git_cmp)
         return self
     #} END interface
 
diff --git a/git/test/test_tree.py b/git/test/test_tree.py
index 5e94e70b..a7cdd9c6 100644
--- a/git/test/test_tree.py
+++ b/git/test/test_tree.py
@@ -77,30 +77,10 @@ class TestTree(TestBase):
             # del again, its fine
             del(mod[invalid_name])
 
-            # SPECIAL ORDERING !
-            # Add items which should sort differently from standard alum sort order
-            mod.add(hexsha, Tree.blob_id << 12, 'fild')
-            mod.add(hexsha, Tree.blob_id << 12, 'file')
-            mod.add(hexsha, Tree.blob_id << 12, 'file.second')
-            mod.add(hexsha, Tree.blob_id << 12, 'filf')
-
-            def names_in_mod_cache():
-                return [t[2] for t in mod._cache]
-
-            def chunk_from(a, name, size):
-                index = a.index(name)
-                return a[index:index + size]
-
-            assert chunk_from(names_in_mod_cache(), 'fild', 4) == ['fild', 'file', 'file.second',
-                                                                   'filf']
-
             # have added one item, we are done
             mod.set_done()
             mod.set_done()      # multiple times are okay
 
-            assert chunk_from(names_in_mod_cache(), 'fild', 4) == ['fild', 'file.second', 'file',
-                                                                   'filf']
-
             # serialize, its different now
             stream = BytesIO()
             testtree._serialize(stream)
@@ -114,6 +94,41 @@ class TestTree(TestBase):
             assert invalid_name not in testtree
         # END for each item in tree
 
+    def test_tree_modifier_ordering(self):
+        hexsha = '6c1faef799095f3990e9970bc2cb10aa0221cf9c'
+        roottree = self.rorepo.tree(hexsha)
+        blob_mode = Tree.blob_id << 12
+        tree_mode = Tree.tree_id << 12
+
+        files_in_desired_order = [
+            (blob_mode, '_.htaccess'),
+            (tree_mode, 'fileadmin'),
+            (blob_mode, 'index.php'),
+            (tree_mode, 'typo3'),
+            (tree_mode, 'typo3_src-6.2.12'),
+            (tree_mode, 'typo3_src'),
+            (blob_mode, 'typo3cms'),
+            (tree_mode, 'typo3conf'),
+            (tree_mode, 'uploads'),
+        ]
+        mod = roottree.cache
+        for (file_mode, file_name) in files_in_desired_order:
+            mod.add(hexsha, file_mode, file_name)
+        # end for each file
+
+        def file_names_in_order():
+            return [t[1] for t in files_in_desired_order]
+
+        def names_in_mod_cache():
+            a = [t[2] for t in mod._cache]
+            here = file_names_in_order()
+            return [e for e in a if e in here]
+
+        assert names_in_mod_cache() == file_names_in_order(), 'add() keeps order'
+
+        mod.set_done()
+        assert names_in_mod_cache() == file_names_in_order(), 'set_done() performs git-sorting'
+
     def test_traverse(self):
         root = self.rorepo.tree('0.1.6')
         num_recursive = 0