[MERGE] walkdirs sort order

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert Collins wrote:
> This patch adds a sort key, and compare operator for paths that will
> result in the same sort order that iter_entries_by_dirs and walkdirs
> use.
> 
> The interesting thing to note here is that if we have the number of '/'
> in a path prefixed to it, a normal bisect call can find a path in the
> planned dirstate output trivially.
> 
> We might want to cache that value in the dirstate: i.e.
> instead of 
> ====
> 
> ====
> for an empty path, use
> ====
> 0 
> ====
> 
> and instead of 
> ====
> /foo/bar
> ====
> use
> ====
> 2 /foo/bar
> ====
> 
> Dunno if this is cheaper than just counting the '/' at parse time.
> 
> Rob


Hey Rob-
I don't think you tested it enough. I think this works for simplistic
cases, but not for complex ones. Specifically what about:

0 a
1 a/b
2 a/b/c
0 b
1 b/c
0 d
1 d/e
2 d/e/f
1 d/f
1 d/g
0 g

The above is normal sorted order, if you change it to dir sorted order
you get:

0 a
0 b
0 d
0 g
1 a/b
2 a/b/c
1 b/c
1 d/e
1 d/f
1 d/g
2 d/e/f

Which violates your number prefix.
It only works for 1 layer, not for deeply nested things. (all 1's come
after all 0's, but some 2's occur before the 1's are finished).

So -1 on your patch after all.

John
=:->

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEktF6JdeBCYSNAAMRAi2QAJ9DeM3UgMlQq2ih5gy88RvusqBnSQCgpZrF
En+ZrFEba3wJPIN9lRudbUA=
=rGf7
-----END PGP SIGNATURE-----