Repository: go
Issue: testing/fstest: `TestFS` falsely fails for certain directory trees on macOS
Labels: help wanted,OS-Darwin,NeedsInvestigation

<!--
Please answer these questions before submitting your issue. Thanks!
-->

### What version of Go are you using (`go version`)?

<pre>
$ go version
go version go1.19 darwin/arm64
</pre>

### Does this issue reproduce with the latest release?

Yep! I've also tested it with 1.17.13 and 1.18.5.

### What operating system and processor architecture are you using (`go env`)?

<details><summary><code>go env</code> Output</summary><br><pre>
$ go env
...
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
...
</pre></details>

### What did you do?

<!--
If possible, provide a recipe for reproducing the error.
A complete runnable program is good.
A link on go.dev/play is best.
-->

On a macOS host, create this `testdata/` tree. The file contents don't matter, only the hierarchy and file names are important:
```console
$ mkdir -p testdata/bug/sub/{new,paths}
$ touch testdata/bug/{hello,sub/bar,sub/new/file,sub/paths/foo}
$ tree testdata
testdata
└── bug
    ├── hello
    └── sub
        ├── bar
        ├── new
        │   └── file
        └── paths
            └── foo
```

Then run the following test

```go
package testfsbug

import (
    "io/fs"
    "os"
    "testing"
    "testing/fstest"
)

func TestTestFS(t *testing.T) {
    tests := map[string]struct {
        src           fs.FS
        expectedFiles []string
    }{
        // Fails on macOS hosts because of ordering of dirents returned
        // by `readDir`.
        "dirfs - bug": {
            src: os.DirFS("testdata/bug"),
            expectedFiles: []string{
                "hello",
                "sub/bar",
                "sub/paths/foo",
                "sub/new/file",
            },
        },
        // This spells out the same file tree as the previous test, but this
        // time as a fstest.MapFS. This one passes because of the ordering in
        // reading dirents in `readDir`.
        "mapfs": {
            src: fstest.MapFS{
                "hello":         &fstest.MapFile{Data: []byte("hello world!"), Mode: 0644},
                "sub/bar":       &fstest.MapFile{Data: []byte("this is bar"), Mode: 0644},
                "sub/new/file":  &fstest.MapFile{Data: []byte("cool file"), Mode: 0644},
                "sub/paths/foo": &fstest.MapFile{Data: []byte("foo"), Mode: 0644},
            },
            expectedFiles: []string{
                "hello",
                "sub/bar",
                "sub/paths/foo",
                "sub/new/file",
            },
        },
    }
    for name, tt := range tests {
        t.Run(name, func(t *testing.T) {
            err := fstest.TestFS(tt.src, tt.expectedFiles...)
            if err != nil {
                t.Fatal(err)
            }
        })
    }
}
```


### What did you expect to see?

The `dirfs - bug` test case should pass, because all expected files exist under `testdata/bug`. The `mapfs` test case at least proves that `fstest.TestFS` can handle a file tree like this, because it always passes.

### What did you see instead?

The `dirfs - bug` test case fails on macOS, with an error case I like to call "Schrödinger's bar":

```
$ go version
go version go1.19 darwin/arm64

$ go test -v ./...
=== RUN   TestTestFS
=== RUN   TestTestFS/dirfs_-_bug
    fstest_test.go:93: testing fs.Sub(fsys, sub): TestFS found errors:
        .: Glob(`*a*`): wrong output:
        extra: bar
        missing: bar
=== RUN   TestTestFS/mapfs
--- FAIL: TestTestFS (0.00s)
    --- FAIL: TestTestFS/dirfs_-_bug (0.00s)
    --- PASS: TestTestFS/mapfs (0.00s)
FAIL
FAIL    testfsbug       0.186s
FAIL
```

But always passes on linux:

```
$ docker run \
    -v $(pwd):/test \
    -w /test \
    golang:1.19 \
    go test -v ./...
=== RUN   TestTestFS
=== RUN   TestTestFS/dirfs_-_bug
=== RUN   TestTestFS/mapfs
--- PASS: TestTestFS (0.09s)
    --- PASS: TestTestFS/dirfs_-_bug (0.09s)
    --- PASS: TestTestFS/mapfs (0.00s)
PASS
ok      testfsbug       0.093s
```

### Analysis

This one fails (on darwin), but we'd expect it not to. All expected files exist in that test directory. The checks at [the end of `fstester.checkGlob`][1] rely on both `names` and `want` being sorted, but it only checks that `names` is sorted. The ordering of `want` is dependent on what [`ReadDirFile.ReadDir` returns here][2] and, for `os.DirFS`, that ordering is platform dependent. The docs for [`ReadDirFile.ReadDir`][3] say to the files being returned in "directory order":

> ReadDir reads the contents of the directory and returns
> a slice of up to n DirEntry values in directory order.

There are [consistency checks in `fstester.checkDir`][4] for reading the dir entries before checking the glob, but these fail to prevent the ordering issue and `list` ultimately ends up as `want`. The closest this come to checking `list`'s order is checking that the [elements match with what `fs.ReadDir` returns][5] (which is `list2`) and then [checking that `list2` is sorted][6]. Passing `list2` into `t.checkGlob` would likely fix the issue because it is guaranteed to be sorted.

This only happens when there are at least two paths in the same directory that match the internally computed glob. In this test, both `sub/bar` and `sub/paths` match glob `*a*` in `sub/`. Obviously if there is only one path that matches the glob, the ordering doesn't matter.

In this test case (on darwin), you end up with the following state at the [want/names check here][7]:
- `want  = ["paths", "bar"]`
- `names = ["bar", "paths"]`

That code doesn't properly compare two unsorted slices, and so you end with the error:

```
    fstest_test.go:76: testing fs.Sub(fsys, sub): TestFS found errors:
        .: Glob(`*a*`): wrong output:
        extra: bar
        missing: bar
```

[1]: https://github.com/golang/go/blob/go1.19/src/testing/fstest/testfs.go#L373-L386
[2]: https://github.com/golang/go/blob/go1.19/src/testing/fstest/testfs.go#L138-L143
[3]: https://pkg.go.dev/io/fs#ReadDirFile
[4]: https://github.com/golang/go/blob/go1.19/src/testing/fstest/testfs.go#L200-L271
[5]: https://github.com/golang/go/blob/go1.19/src/testing/fstest/testfs.go#L265
[6]: https://github.com/golang/go/blob/go1.19/src/testing/fstest/testfs.go#L267-L271
[7]: https://github.com/golang/go/blob/go1.19/src/testing/fstest/testfs.go#L374