Re: git on MacOSX and files with decomposed utf-8 file names

From: Theodore Tso <tytso@mit.edu>
Date: Jan 23, 2008, 02:06 UTC
Message-ID: <20080123020607.GC1320@mit.edu>
In-Reply-To: <E6F76F93-24C9-4D10-813C-770A9C3A9828@sb.org>

On Tue, Jan 22, 2008 at 07:38:04PM -0500, Kevin Ballard wrote:

Show 7 quoted lines

> * Any new characters added to Unicode will only have one form (decomposed), 
> so HFS+ will always accept new characters as they will be NFD. The only 
> exception is case-sensitivity, as the case-folding tables in HFS+ are 
> static, so new characters with case variants will be treated in a 
> case-sensitive manner. However, as they are already decomposed, the NFD 
> algorithm will not change their encoding. This means that no, there are 
> zero problems moving HFS+ drives between versions of OS X.

Except there *are* problems, because this promise doesn't apply to Unicode 2.1 (Mac OS 10.2 and before) and Unicode 3.2 (Mac OS 10.3 and above). And there were changes between the normalization algorithm between Unicode 3.2 and the Unicode version 4.1. So taking a hard drive between Mac OS X 10.2 and 10.3 *will* cause problems. The guarantees of Unicode stability didn't come until well past Unicode 2.1.

Also, I know of no guarantee that there will be no more new compositions. According to Unicode Stnadard Annex #15 (http://unicode.org/reports/tr15/), new characters that can be decomposed are strongly discouraged, but "It would be possible to add more compositions in a future version of Unicode". Got a reference to back up your claim that there will never be any more?

Show 7 quoted lines

> * At the time HFS+ was developed, there was no one common standard for 
> normalization. The HFS+ developers picked NFD because they thought it was 
> "a more flexible, future-looking form", but Microsoft ended up picking the 
> opposite just a short time later. Interestingly, NFC is a weird hybrid form 
> which only has composed forms for pre-existing characters, and decomposed 
> forms for all new characters (as they only have one form). So in a sense 
> NFD is more sane then NFC.

NFC is better if you care about compatibility with existing legacy character sets, where you want round-trip conversions to be idempotent. On the other hand, given that Mac OS has historically never cared about being compatible with the rest of the world, it makes sense that it would choose NFD.

> * The core issue here, which is why you think HFS+ is so stupid, is that 
> you guys see no problem with having 2 files "Märchen" (NFC) and "Märchen" 
> (NFD), whereas the HFS+ developers don't consider it acceptable to have 2 
> visually identical names as independent files.

Yep. No problems to do that. You seem to think that supporting Unicode requires imposing this constraint, but that's simply not true, except maybe in some kind of religious sense.

> Unfortunately, the only way 
> to do this matching is to store the normalized form in the filesystem, 
> because it would be a performance nightmare to try and do this matching any 
> other way.

Nope. They were just not clever enough. If they use a hashed key for their b-tree and used a hash which had the property that two strings that were equivalent in the Unicode sense have the same hash value, it's quite possible to do Unicode-equivalence lookups quickly. Yeah, calculating the hash algorithm takes a bit amount of time, but it gets called no more than the normalization routine, and its performance overhead is no worse than the normalizing a string.

I know how to do it in a Linux filesystem; it's just an insane thing to do, and so I choose not to do it. But it is doable; if you must persue the course of filesystem insanity, it's possible to do it in a performant way, without normalization; it's the same way that you can use b-tree lookups in a case insensitive way.

> I must say it is shocking that someone as smart as you is still more 
> interested in finding ways to prove me wrong then to actually address the 
> problem. It's obvious that the only research you did was intended to find 
> ways to call me stupid.

No, I did the research to try to find the HFS-specific filename mangling algorithm. And given that's based on an back-level, old version of Unicode, you can't just use NFD algorithm from the latest Unicode spec. As I did that research, I came across the evidence that claims you had made (i.e., that HFS had never changed the Unicode version for its Normalization algorithm), was directly contradicted by the Apple TechNote.

    	  					- Ted