mozilla/rust — pull request #13720 by aturon (2014-04-24 01:44:24+00:00)
Title: fix O(n^2) perf bug for std::io::fs::walk_dir

The `walk_dir iterator was simulating a queue using a vector (in particular, using `shift`),
leading to O(n^2) performance. Since the order was not well-specified (see issue #13411),
the simplest fix is to use the vector as a stack (and thus yield a depth-first traversal).
This patch does exactly that, and adds a test checking for depth-first behavior.

Note that the underlying `readdir` function does not specify any particular order, nor
does the system call it uses.

Closes #13411.