case-sensitivity of filesystem apis

[programmerjake]

I think it would be a good idea to standardise on if the file-system APIs should be case-sensitive or not and to what extent implementations should enforce case-sensitive/insensitive file-system access on common platforms such as Linux or Windows.

See bytecodealliance/wasmtime#235 (comment) for some ideas.

[tschneidereit]

As mentioned in the linked Wasmtime PR, I don't think we can require either case-sensitivity or case-insensitivity, unfortunately.

@programmerjake mentioned a potential way to at least help with portability issues (see also the consecutive discussion). It seems like that might be viable, but would still incur some overhead. It also seems like it's more of a lint, and should perhaps be something an implementation can warn about, if it chooses to.

[sunfishcode]

I agree with @tschneidereit. The goal of the filesystem APIs is to enable access to filesystems, so we have to work within what they give us. So we can't depend on case sensitivity, or insensivity, or even a specific version of Unicode's case tables being used.

The technique @programmerjake mentioned here is a good idea to help mitigate the portability issues. Another thing we can do is encourage engines to have developer modes that occasionally scan for files that differ only in case.

And as an aside, another possibility, which we could do independently of the above, is to create a concept of WASI-specific directories, which would be directories where we allow ourselves to assume that only WASI programs will access the files. That would allow us to mangle names to avoid case sensitivity, and potentially implement other custom filesystem semantics.

[programmerjake]

I agree with @tschneidereit. The goal of the filesystem APIs is to enable access to filesystems, so we have to work within what they give us. So we can't depend on case sensitivity, or insensivity, or even a specific version of Unicode's case tables being used.

I'm not sure, but I think NTFS is case insensitive for just ASCII characters and it is case sensitive for non-ASCII characters.

[Serentty]

@programmerjake It's unfortunately a lot more complicated than that. From what I understand from my friends way more knowledgeable about Windows than I am, the way Windows handles case mapping is that it establishes a set of case mappings when you format a drive, based on what is current in Unicode at the time (or at least what Microsoft has gotten around to telling Windows about). So, take this with a grain of salt because this is second-hand information, but I think that two different hard drives might have different case mapping rules depending on when they were formatted, and two files with names considered equivalent on one may not be considered equivalent on the other. To make matters worse, due to legacy reasons, Windows is only case sensitive for characters within the BMP; characters outside of it are never case sensitive.

[bjorn3]

What about only allowing to create a file when there is no other file with different case? That would prevent creating files with different case on case-insensitive systems, while still being able to open differently cased files on case-sensitive systems.

[indolering]

I've done a deep dive on this and I think case-insensitivity would be the right path forward. Should I just write a proposal on this ticket or would y'all perfer an RFC?

[sunfishcode]

The difficulty we perceive with plain case-insensitivity is that it's inefficient to emulate on case-sensitive hosts. An implementation on a case-sensitive host would have to scan the parent directory on every access to find case-insensitive matches. So for example, creating N files within a directory would take O(N^2) time. Or they could try every possible case variation of a name, which is O(2^N) with the length of filenames. If anyone knows of a way to avoid this, we'd love to hear it :-).

I've been imagining that the main WASI filesystem APIs will end up just saying that directories may or may not be case-insensitive, that case-insensitivity may be interpreted with arbitrary Unicode versions and/or optionally applied just to the ASCII or BMP subsets, and they may or may not apply any version of NFC or NFD normalization they chose. This unfortunately passes a lot of complexity up into applications, so it'd be great if anyone has better alternatives.

We might be able to do some things to help such as this, perhaps for normalization as well as case, which should hopefully help with portability, though that won't fix all the problems.

[indolering]

Or they could try every possible case variation of a name, which is O(2^N) with the length of filenames.

No, you just do a comparison of the casefolded filename. So it would be O(log files) on casefold-aware files systems (because they store the casefolded filename in the b-tree) or O(files) (where the limiting factor will be listing the files of a directory and then performing a save operation).

I'm going to write up my thoughts and post in a minute : )

[indolering]

So hi! I'm indolering, a security focused usability engineer. There are a lot of points to address here, so I’ll leave a summary below and link to the full explainer.

Case-insensitivity is required by end users: Windows, OS X, and Android all enforce some level of case-insensitivity - even Linux supports it!. They are all slightly different but, as Ted Tso put it, “the world is converging enough that the latest versions of Mac OS X’s APFS and Windows NTFS behave pretty much the same way.”

The feared complexity of case-insensitivity is unwarranted, as caseless matching is a pure function mapping from single codepoints to case-folded variant(s). This behavior is immutable for any assigned codepoint: any non-determinism caused by outdated Unicode tables can be caught at runtime, but would be vanishingly rare in practice.

The linked proposal for a versionless Unicode case-folding is modeled on Rusts overflow handling: allow for precisely defined implementation dependent behavior that can be deterministic, but mostly “just works” when backed by commodity filesystems.

It requires additional complexity, but the payoff is happy developers and users.

[indolering]

Updates based on chat:

If we can't assume WASI only filesystem access, then we should just fallback to whatever the filesystem does. Linux now supports case-insensitive on a per-directory basis, so case-insensitive matching will be fast and simple most of the time.

[programmerjake]

oops... closed by mistake

[Serentty]

Case-insensitivity is required by end users: Windows, OS X, and Android all enforce some level of case-insensitivity - even Linux supports it!.

The fact that so many systems do it doesn’t seem like good evidence of that to me. End users who would be confused by case sensitivity are mostly interacting with dialogue boxes which can present a case-insensitive search anyway, which most GUIs on Linux do. It doesn’t seem to me like this is a good argument for the filesystem itself to need this.

They are all slightly different but, as Ted Tso put it, “the world is converging enough that the latest versions of Mac OS X’s APFS and Windows NTFS behave pretty much the same way.”
The feared complexity of case-insensitivity is unwarranted, as caseless matching is a pure function mapping from single codepoints to case-folded variant(s). This behavior is immutable for any assigned codepoint: any non-determinism caused by outdated Unicode tables can be caught at runtime, but would be vanishingly rare in practice.

The complexity here isn’t in matching the Unicode standard—it’s in being deterministic across different platforms. “Pretty much the same way” isn’t deterministic, and can be used for fingerprinting.

Distros that care about usability will eventually adopt case-insensitivity, even if it is just for the home directories.

I sincerely doubt this. I have seen no indicating of interesting in this from any of them.