treemanifest: make diff() faster
Containment checking is slower in treemanifest than it is in
manifestdict, making the current diff algorithm O(n log n). By
traversing both treemanifests in parallel, we can make it O(n). More
importantly, once we start lazily loading submanifests, we will be
able to easily skip entire submanifest if they have the same nodeid.
$ hg init
$ mkdir alpha
$ touch alpha/one
$ mkdir beta
$ touch beta/two
$ hg add alpha/one beta/two
$ hg ci -m "start"
$ echo 1 > alpha/one
$ echo 2 > beta/two
everything
$ hg diff --nodates
diff -r 7d5ef1aea329 alpha/one
--- a/alpha/one
+++ b/alpha/one
@@ -0,0 +1,1 @@
+1
diff -r 7d5ef1aea329 beta/two
--- a/beta/two
+++ b/beta/two
@@ -0,0 +1,1 @@
+2
beta only
$ hg diff --nodates beta
diff -r 7d5ef1aea329 beta/two
--- a/beta/two
+++ b/beta/two
@@ -0,0 +1,1 @@
+2
inside beta
$ cd beta
$ hg diff --nodates .
diff -r 7d5ef1aea329 beta/two
--- a/beta/two
+++ b/beta/two
@@ -0,0 +1,1 @@
+2
$ cd ..