fs::read_dir() and ReadDir need clear warnings about not relying on iteration order

[abonander]

The docs for fs::read_dir() and fs::ReadDir need to clearly state that iteration order is implementation defined and may vary not just between OS's but between identical versions of a directory on different filesystems.

Currently the warning on fs::read_dir() is uselessly vague:

Platform-specific behavior

This function currently corresponds to the opendir function on Unix and the FindFirstFile function on Windows. Note that, this may change in the future.

Meanwhile even this warning is completely missing from ReadDir.

Finding the semantics on ordering requires going through the docs for the target platform:

• opendir() does not specify order but links to readdir() which states:

The order in which filenames are read by successive calls to
readdir() depends on the filesystem implementation; it is unlikely
that the names will be sorted in any fashion.

• FindFirstFileA does not specify order but links to FindNextFile which states:

The order in which the search returns the files, such as alphabetical order, is not guaranteed, and is dependent on the file system. If the data must be sorted, the application must do the ordering after obtaining all the results.

The order in which this function returns the file names is dependent on the file system type. With the NTFS file system and CDFS file systems, the names are usually returned in alphabetical order. With FAT file systems, the names are usually returned in the order the files were written to the disk, which may or may not be in alphabetical order. However, as stated previously, these behaviors are not guaranteed.

In both cases the relevant information is two links deep which isn't really acceptable for stdlib documentation.

I want to note that I just spent 20 minutes trying to figure this out from a unit test that was dependent on this ordering and was passing locally but failing on our CI server even though both machines are running Linux x64. The problem was I'm running btrfs (which apparently returns files in lexicographical order, or just happened to return them that way) while I'm not entirely sure what filesystem the CI server is using (build jobs are running inside Docker anyway). Either way it turns out they iterated identical copies of the same directory in different orders. Frustratingly, a very similar test also depending on the ordering of read_dir() but for a different directory was passing on both machines, which lead me to initially discount that it might have been an issue of iteration order.

This issue has been assigned to @ali-raheem via this comment.

[abonander]

The good news is that this would be a good issue for a beginner since it should just be touching docs. An example for getting entries sorted by path would be nice too. I'll gladly mentor on this if no one else is available.

[abonander]

@GuillaumeGomez I can mentor on this if you'd like to mark it E-Mentor

[GuillaumeGomez]

Oh nice! Adding right away.

[ali-raheem]

@rustbot claim

I'd like to try dealing with this, it will be my first issue :)

[ali-raheem]

@abonander

master...ali-raheem:rust-lang#63183

Is this the kind of change you were hoping for?

The changes are to ReadDir and read_dir in src/libstd/fs.rs

[abonander]

@ali-raheem I'd like the message to have its own header if possible, like:

#### Note: Iteration Order is Implementation-Defined

I'd also like to maybe see an example of collecting the DirEntry::path() values to a Vec which is then sorted; it should be as simple as calling .sort() on the vec as PathBuf implements Ord. You will have to handle the io::Results returned from the iterator but that's not too hard as you can collect to an io::Result<Vec<PathBuf>> and then handle the result outside the iterator chain.

[ali-raheem]

use std::fs;
use std::io;
use std::path::{Path, PathBuf};

fn main() {
    let path = Path::new(".");
    sorted_read_dir(&path);
}

fn sorted_read_dir(path: &Path) -> io::Result<()> {
    let dir = fs::read_dir(path)?;
    let mut entries: Vec<PathBuf> = dir
        .filter(Result::is_ok)
        .map(|e| e.unwrap().path())
        .collect();
    entries.sort();
    for entry in entries {
        println!("{:?}", entry);
    }
    Ok(())
}

Hows this for the example?

[abonander]

@ali-raheem I don't think they want examples showing throwing away io::Errors. You can do this instead:

let mut entries = dir
    .map(|res| res.map(|e| e.path()))
    // this will return the iterator collected to a `Vec` or the first error
    .collect::<Result<Vec<_>>>()?;

println!("Entries before sorting (may or may not be sorted already): {:?}", entries);

entries.sort();

println!("Entries after sorting: {:?}", entries);

[ali-raheem]

@abonander

Okay, I've changed the example, there are two examples for read_dir now including this one.

I've added the warning to ReadDir, and read_dir (and added a slightly more verbose note).

https://github.com/rust-lang/rust/compare/master...ali-raheem:rust-lang%2363183?expand=1

Hows this looking?

[abonander]

@ali-raheem Looks good, though you don't need a separate function from main as you can just return an io::Result<()> from that. If you start your code block with ```rust,no_run then it will be compile-checked but not run so the directory you use doesn't have to exist. fs::read_dir() also can take a &str so you don't need to convert to Path first:

use std::{fs, io};

fn main() -> io::Result<()> { 
    // The order read_dir returns entries is not guaranteed. If reproducible
    // ordering is required the entries should be explicitly sorted.
    let mut entries = fs::read_dir(".")?
        .map(|res| res.map(|e| e.path()))
        .collect::<Result<Vec<_>, io::Error>>()?;

    println!(
        "Entries before sorting (may or may not be sorted already): {:?}",
        entries
    );
 
    entries.sort();
 
    println!("Entries after sorting: {:?}", entries);
    Ok(())
}

I would place this example as the second one, though.

I would also put the same message under the header on ReadDir at line 118 as you have on fs::read_dir() lines 1966-1967.

Finally, it's "reproducible" and not "reproducable" but I can never remember which one it is either, the Firefox spell-checker had to tell me.

[ali-raheem]

@abonander Great! Here it is all together (and spell checked -- sorry!)

https://github.com/rust-lang/rust/compare/master...ali-raheem:issue%2363183?expand=1

Let me know if you're happy for me to put in a pull request.

[abonander]

@ali-raheem looks good to me now, good work!

[TheOregonTrail]

I think this can get closed since it seems to have been resolved. Thanks for help @ali-raheem and @abonander for opening the issue

[abonander]

@luigisHat this shouldn't be closed until #63356 is merged.

[TheOregonTrail]

Ah I see still getting used to how all this works. Thanks for letting me know @abonander

[dunnock]

@abonander this seems was merged to master, should it be closed now?