Unicode's Transliteration Rules Are Turing-Complete
27 points by mpweiher
27 points by mpweiher
Fun fact that not many people seem aware of: APFS is unicode normalization insensitive (NFD or something I think?). e.g. groß and gross will be the same file :D
Another fun fact many people don't seem aware of: Turing completeness is trivial and it sometimes takes effort to avoid (and it should be avoided in cases like this)
Yeah, I know of only one iterated string rewriting system that avoids being Turing complete without an artificial run time limit: previously
It does at times feel like step 1 of not creating something that is accidentally Turing complete is to avoid creating any kind of file format :D
AFAIK Unicode NFC / NFD etc are unrelated to these transliteration rules. It’s unclear to me what these transliterations are for: something like squashing greek or cyrillic to latin? but in what context are these transliterations invoked?
And APFS inherited its case-insensitive normalization from HFS+, it’s a very longstanding weirdness of Mac OS X and its precursors. Tho it’s only in recent months that I have seen people joking about the secret ßh command…
What do you mean by “weirdness” here? Most users don’t expect different capitalization to be different file names, because why would they be? It also creates the hazard of accidentally editing the wrong version of a document, etc.
Case sensitivity is not a particularly user friendly model for file names, outside of developers where it’s useful for the purpose of insuring your build works on case sensitive file systems :D :D
I think it’s weird to push unicode algorithms into the kernel, rather than doing it in the UI toolkits. I would expect it to be simpler and more flexible to implement filename search and match in userland on top of unix-style bag-of-bytes names, because then searching can be decoupled from canonicalization, and the algorithms can change over time based on UX requirements without interference from lower-level considerations.
One reason I think this is because it’s rare for GUI users to type in a filename that’s expected to be a direct match for an existing file; instead the UI is more like typing in a search term then confirming the choice. Low-level unicode shenanigans aren’t much help for this kind of search UI.
Of course there are historical reasons that Mac OS X works the way it does. I got the impression at one point (before APFS) there were some attempts to move to unix-style filenames, but they didn’t get very far, I guess owing to backwards compatibility problems. One of those rural Irish road directions problems: if you want to get there I wouldn’t start from here.
How would it work if not done as part of the file system?
The UI does a readdir() and compares the names with the user’s input to present a list of matching files from which the user can select the one they want. The name passed to open() comes from readdir() not from the user’s input, so it’s always bytewise identical. Or instead of readdir() the search uses a userland filesystem index.
The UI might do some kind of IME style matching so that eg pinyin matches hanzi or kana matches kanji. Case insensitivity is basically a simplified special case of more sophisticated matching algorithms. I don’t think it makes sense to put euro-centric matching into the kernel when userland still needs multilingual matching on top: kernel case-insensitivity is redundant.
I have a briefer reply here: https://lobste.rs/c/gexoor
Or a different TLDR: The only thing that knows how filenames are encoded, and the rules for those filenames, is the filesystem itself. Trying to implement any kind of faked rendering of filenames on top of that is a significant increase in the amount of work required for every single program, an significant increase in user confusion, a significant increase in UI complexity, and the potential for normalization mismatches leading to security vulnerabilities.
Basically if the UI has a different representation of the filesystem every UI interface must duplicate that logic, duplicate the normalization scheme, deal with files that have different capitalization, different unicode filename encodings for the same characters, etc. "Every UI" includes CLI tools.
So now for any tool to do the "right thing" they can no longer use fopen() at all, and they instead have to do
If any tool does not do this, or does not do it exactly right, then you immediately get a slew of UI confusion, perceived data loss, and security vulnerabilities.
Filenames, and filename representation, are a property of the filesystem, having the UI representation of filenames not match the actual filesystem is a recipe for user confusion, data loss (potentially just perceived, or as a product of different UIs presenting choosing different filenames or normalization).
This also gets to another problem: your UI chooses to try and normalize filenames, but the filesystem is something that is expected to be case sensitive then what do you do?
I don’t think it needs to be that complicated. (Obviously Mac OS is that complicated, but that’s because it put the wrong model of filenames into the kernel.) Almost all APIs should handle filenames in the same way as trad unix, that is, a filename will only be found if it is re-entered in a bytewise identical manner. (CLIs are APIs.) Your list of problems evaporates when filename normalization is the identity function, as it is in trad unix.
That’s a pain in the arse for non-programmers, so design the GUI such that existing filenames are chosen from a list, and what the user types in is treated as a search term, not directly as a filename. (GUIs mostly work that way already.) The search algorithm doesn’t have to be based on unicode normalization; different apps or different versions of the OS or GUI might have different search algorithms; what matters is that search fuzzy matching is useful enough for the user to find the file they want. (If the search uses unicode normalization, then normalized names are an internal ephemeral detail of the search, and therefore filenames on disk do not need to be in any particular form.) By construction there are no conflicts: the user resolves ambiguous searches by choosing the file they wanted from the narrowed-down list presented in the GUI.
There’s no need to fiddle with descriptors: the search returns strings that are guaranteed to be bytewise identical to existing filenames. Of course the list of filenames in the GUI must match what’s in the actual filesystem: you have to go through extra unnecessary steps to mess that up, so don’t do that. Search+choose works for a filename that the user can’t enter (foreign language?) or that can’t be displayed properly (font without full unicode coverage?): if the user can pick it out of a list with their pointer, they can still open it or rename it to something more legible. This even works for filenames that use unassigned codepoints or bare surrogates or have malformed UTF-8, provided the GUI is able to display a reasonable (or just halfarsed) representation of the name.
Search+choose also works for filesystems such as APFS that normalize filenames, because the chooser always produces a filename that the filesystem previously normalized. When APFS gets tricky is creating a file, because the new name entered by the user might not be present verbatim in the updated directory listing, so an app can’t trivially do things like highlight the current file in the list. Dunno how Mac OS deals with that; I would probably fstat() the new file’s descriptor and look through readdir() for a matching inode number, and update my idea of the name to the filesystem’s normalized version; but maybe Mac OS has a quicker fd -> name lookup. Of course, this problem doesn’t happen in trad unix because it creates files with the given name verbatim.
On Mac, you can easily have two files in Finder that look to users like they have the same filename due to either hidden extensions or localization. I think it would make more sense for Apple to move to a system where behind the scenes at the file system level file names are case sensitive and to users at the UI level you let users see two files with the "same" name or illegal characters in the name that you secretly deduplicate and hide at the file system level.
If the UI layer becomes responsible for that, it means every UI toolkit needs to
(1) detect the filesystem type, and the configuration (2) implement an identical normalization scheme
Then you have to deal with Foo.txt and foo.txt both existing because some UI toolkit, bash, etc did not perform the normalization.
You can't have the UI layer be responsible for rendering of filenames, if that rendering does not match the filenames.
The hidden extensions are resolved by - in general - the different icons they get, the interfaces where icons are available are things like the shell where the extensions are visible.
This is how Mac OS already is though. If you change your OS language to Japanese, suddenly your ~/Music folder becomes ~/ミュージック. It's been like this for decades. I already have to deal with foo.txt and Foo.txt existing because Git punts filename resolution to the file system, so renaming a file from lowercase to title case causes Git to choke and die. I have at many jobs added a disk image for Git to use that is case sensitive just so I run into fewer of these bugs.
Sorry for the delayed reply, I missed this entirely (so feel free to ignore).
Music etc are a specific fixed (and small) subset of folders - and I think those specific folders, eg “Music” as a general name is not translated.
For the filename + git the solution is to make the fs case sensitive which is what every Mac developer I know uses. Of course the problem is that you really want to do that from the initial setup, but I recall some people having an apfs case sensitive logical volume (or whatever it’s called) that they use for repos as that means they can also verify correct application behaviour on the default configuration.