Merkletrie.Difftree return wrong results for directories named after files without extension.

[alcortesm]

On http://github.com/git/git.git:

; git diff-tree -r 249894 c1f7a56
:000000 100644 0000000000000000000000000000000000000000 1239c70de997dd93a59bf6d3d9cc126bffbc5392 A	src/runtime/cgo/tmpdir_darwin.go

But the current merkletrie.difftree implementation returns something different:

; go-git-diff-tree-sprint-demo . 249894ab6c4d8439e7fd47ca55ba618d636ab239 c1f7a56fc05584b931c979779dd086c417b50dcb
:000644 000000 169a31d4c6ed57a4fb6ba44b28cb52c97d9b007a 0000000000000000000000000000000000000000 D	src/runtime/cgo.go
:000000 000644 0000000000000000000000000000000000000000 1239c70de997dd93a59bf6d3d9cc126bffbc5392 A	src/runtime/cgo/tmpdir_darwin.go
:000000 000644 0000000000000000000000000000000000000000 169a31d4c6ed57a4fb6ba44b28cb52c97d9b007a A	src/runtime/cgo.go

This is because we have a bug in how merkletrie.Difftree tells insertions from deletions. The way to do it is, while iterating over the tree, checking which one of the current noders would come first when iterating over the tree:

• If from would come after to, it means the to has been inserted (otherwise we will be having it in the from too).

• If from would come before to, it means from was deleted (otherwise we will be having it in the to too).

The current way to tell which one would come first is by comparing their path lexicographically, but this is wrong, as it returns incorrect results with some nested directories, example:

                       Insert 
                       a/b/d.go

             From                      To
               a                        a
              /  \                    /  \
            b    b.go               b     b.go
           /                      /  \
         /                      /      \
       c.go                   c.go      d.go

When from -> a/b.go and to -> a/b/d.go, from will be lexicographically smaller than to, which will result in believing from has been deleted, which is not.

To fix this, we must compare paths level by level, instead of over the full path.