Do NFKC normalization in lexer

[catamorphism]

next_token_inner in the lexer has a comment saying to do NKFC normalization. I have no idea what that is, but I guess we should do it.

reference: NFKC is one of four unicode Normalization Forms.

reference: UAX-31 supplies guidelines for use of normalization with identifiers.

[graydon]

Actually I've changed my mind on this and no longer think we should nfkc normalize here. But check the python unicode identifiers pep to confirm they do not either.

[marijnh]

Python does normalize. See http://bugs.python.org/issue10952 for some relevant discussion.

[graydon]

Sadness!

And double-sadness on the filesystem thing. Though I don't really understand what the commenter is getting at in http://bugs.python.org/issue10952#msg126592 ... wouldn't the filename in the filesystem (however it's encoded) NFKC-normalize to the NFKC-normalized string the user asked for?

In any case, I think we can probably dodge whatever bullet is there (if there is one) due to us doing our linkage by relatively open-ended scanning plus matching metadata tags. I don't think it should ever be a bug to consider "too many crates" in the search path; including a directory in the search path should open up the possibility of the compiler looking at all crates in that dir as part of its scan.

[bblum]

revisiting for triage; all i have to add is the sparkling new A-unicode tag

[pnkfelix]

visiting for triage, email from 2013-08-26.

(Added link to definition of NFKC in unicode spec.)

[pnkfelix]

Regarding Graydon's question about the filesystem problem: My interpretation of the problem is that you have this scenario where:

1. You have some string of characters, e.g. F which NFKC normalizes to F', where F != F'. (In the example, F = \xB5Torrent and F' = \u03BCTorrent
2. The compiler sees an occurrence of F in the source code and normalizes it to F'
3. But the filesystem is actually incapable of representing F' as a filename. In its internal representation of the directory structure, it has F.
4. So when the compiler goes to look for the post-normalized F', it "cannot find it", since the filesystem does not (and will never) have an entry for F'.

Hypothetically I guess the compiler could attempt to invert the normalization process during the filesystem lookup and attempt to query the filesystem for every filename E such that E normalizes to F' ? (Maybe that's what Graydon meant when he said he did not understand the problem; maybe he was assuming that whatever component was doing a filesystem query should be able to walk over a relatively small set of candidate files and NFKC-normalize their names during the lookup?)

In any case, don't we always have the option of putting explicit names for the modules we import into attribute-strings, which (AFAIK) should not be NFKC-normalized? And therefore someone should always be able to workaround this problem if it arises for their particular filesystem? (Isn't that right? We're only talking here about NFKC-normalization of identifier tokens, not of literal strings, right? That's certainly the only place that the FIXME occurs in lexer.rs.)

(Also, the above scenario may just be an artificial problem. That argument was certainly made on that thread on Python Issue 10952.)

---

There is also discussion of NFKC/NFC normalization for identifiers, in the context of Scheme, here:

http://srfi.schemers.org/srfi-52/mail-archive/msg00019.html

[pnkfelix]

My personal instinct has been to do NFC normalization, not NFKC. Yet it seems that experts in both the Python community and the Scheme community have argued for NFKC normalization of identifiers. (As did @nikomatsakis during the triage meeting, I think.)

Well, maybe for Scheme that makes more sense. At least on implementations that also case-fold; that was what came to my mind when I read the statement here:

http://bugs.python.org/issue10952#msg182911

According to that note, fullwidth and halfwidth variants are commonly used and recognized as different characters in Japanese environments, and the commenter was thinking it odd to distinguish upper- and lower-case while conflating full- and half-width. (Anyone here familiar with Japanese environments? I'd love to get better understanding of this.)

[pnkfelix]

(also, added reference to UAX-31 to the description.)

[nikomatsakis]

My personal instinct has been to do NFC normalization, not NFKC.
Yet it seems that experts in both the Python and the Scheme have
argued for NFKC normalization of identifiers. (As did @nikomatsakis
during the triage meeting, I think.)

I actually don't claim to argue either way. I feel like this is not
something I can have an opinion on, since all my identifiers are ASCII
and will almost certainly always be ASCII. But I can certainly see
an argument for identical glyphs being equivalent (I can also see an
argument for NFC).

[sanxiyn]

I am not familiar with Japanese environment(tagging @gifnksm), but for Korean, my understanding is that it is desirable to have U+1100 HANGUL CHOSEONG KIYEOK and U+3131 HANGUL LETTER KIYEOK equivalent, which means compatibility normalization. The reason is that the same keypress will result in U+3131 in Windows but U+1100 in Mac.

[lilyball]

My initial feeling was that we should do NFC and not NFKC, but fullwidth vs halfwidth, and @sanxiyn's example Korean characters, have changed my mind such that I think NFKC is the appropriate choice.

Regarding the filesystem issue, the only filesystem I know of offhand that normalizes is HFS+, which is fine because it normalizes to NFD and AFAIK Unicode isn't adding any new composed characters (which means HFS+ won't encounter a composed character that it doesn't know how to decompose). Although strictly speaking it normalizes to a variant of NFD that doesn't match current Unicode (I don't know if it's pegged at an older Unicode standard or merely has modifications), for backwards compatibility reasons.

Regardless, on HFS+ we shouldn't have an issue. Are there in fact filesystems out there that impose other character sets on filenames? If so, instead of trying to reverse the process (which seems implausible; besides not having a pre-existing mapping of NFC/NFD to all composed characters that could result in those (note: there are composed characters that will actually be decomposed by NFC), due to how normalization orders combining marks something like Zalgo would produce a combinatorial explosion of potential un-normalized names). Instead, if this is actually found to be an issue in practice, I would recommend simply reading the directory, passing all encountered files through NFKC normalization, and picking the file that matches. If multiple files match, consider that an error. Naturally this would only be done if there is no file that already matches the normalized identifier.

In any case, I think the right approach is to NFKC-normalize identifiers during lexing, and then if we don't want to solve the filesystem issue we can either introduce a lint or a feature-gate for non-ascii module names and extern crate names (as no other identifier will map to a filename).

---

Another point to consider is future compatibility for XID_Start/XID_Continue. There's 3 approaches we can take:

1. Use XID_Start/XID_Continue from whatever the latest Unicode is. This will always be backwards-compatible, but it may result in newer versions of rustc accepting identifiers that older versions didn't (as new characters get added to these classes).
2. Define our identifiers as XID_Start/XID_Continue from a specific version of Unicode. This will be future-compatible, but it means that as Unicode changes to add new characters to these classes, these characters will never be valid Rust identifiers.
   2a. Approach bind's glue function should tail-call its target  #2, but update the Unicode version whenever we make a backwards-incompatible language change that invalidates most programs (a minor language change that affects few programs is probably not sufficient, but something that requires modifying all but the most trivial of Rust files would be appropriate).
3. Similar to approach bind's glue function should tail-call its target  #2. Define our identifiers as:
   • Any character in XID_Start/XID_Continue as of Unicode , OR
   • Any unassigned character as of Unicode that does not have any of the following properties:
     • Pattern_White_Space=True
     • Pattern_Syntax=True
     • General_Category=Private_Use, Surrogate, or Control
     • Noncharacter_Code_Point=True

These 3 approaches are all suggested by UAX #31 (Unicode Identifier and Pattern Syntax). Approach #3 is the most forward-compatible, but it has the downside of allowing identifiers that would otherwise be invalid.

#1 is obviously the easiest. And personally, I think #1 is probably ok. If you want to use identifiers characters added in future versions of Unicode in your project, you just have to be ok with requiring a minimum version of rustc to compile it. And if this is a big worry we can always add a lint to catch such newly-added characters.