[MERGE] walkdirs sort order

[John Arbash Meinel]

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

John Arbash Meinel wrote:
> 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
> 

I just realized what it was, your patch changes depth-first sort order
into breadth-first sort order. However, dir sorted is actually a hybrid
(as we have discussed).
So I don't think there is a quick fix.
I've been trying to do the dir_sorted_to_sorted_order function, and I
was running into some problems like this.
In general, it wasn't possible to do unless you go in dir-block mode. So
that you know when you've gotten all the items for a directory.

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

iD8DBQFEktJTJdeBCYSNAAMRAkgRAJ93sGzSf1sbIAPtGjXkO+aRlj2mNwCdHyUK
/ITb2uSz98QMRxBUHUyBI/4=
=QeQA
-----END PGP SIGNATURE-----