project-machine / puzzlefs

A next-generation container filesystem
Apache License 2.0
393 stars 17 forks source link

Directory traversal is depth-first instead of breadth-first #44

Open ariel-miculas opened 1 year ago

ariel-miculas commented 1 year ago

walker in builder/src/lib.rs says:

breadth first search for sharing, don't cross filesystems just to be safe, order by file name.

It's also mentioned in doc/chunking.md:

We serialize the filesystem by doing a breadth first walk, ordering directory
entries lexicographically. We use a breadth first search so that hopefully
package directories can be shared.

but https://docs.rs/walkdir/latest/walkdir/struct.WalkDir.html traverses the directory in depth-first fashion.

Furthermore, it doesn't provide support for breadth-first search: https://github.com/BurntSushi/walkdir/issues/16