Bug #21559: Unicode normalization nfd -> nfc -> nfd is not reversible

• Status: Closed
• Assignee: duerst (Martin Dürst)
• Target version: -
• Backport: 3.2: DONTNEED, 3.3: DONTNEED, 3.4: DONTNEED

[tompng (tomoya ishida)]

I expect nfd(nfc(str)) == nfd(str) but found a string that doesn't.

# Ruby 3.1 - 3.5
str = "s\u{11930}\u{323}\u{11930}\u{307}"
p str.unicode_normalize(:nfd) == str.unicode_normalize(:nfc).unicode_normalize(:nfd)
#=> false

# ruby 3.5.0dev
str = "s\u{1611e}\u{323}\u{1611e}\u{307}\u{1611f}"
p str.unicode_normalize(:nfd) == str.unicode_normalize(:nfc).unicode_normalize(:nfd)
#=> false

[nobu (Nobuyoshi Nakada)]

"s\u{11930 323 11930 307}".unicode_normalize(:nfc).dump #=> "\u1E69\u{11930}\u{11930}"
"s\u{323 307}".unicode_normalize(:nfc).dump  #=> "\u1E69"

Are U+0323 and U+0307 composed to s jumping over U+11930?

[ima1zumi (Mari Imaizumi)]

• Assignee set to ima1zumi (Mari Imaizumi)

This looks like a bug. Per Unicode TR15, the identity toNFD(x) == toNFD(toNFC(x)) must be maintained. https://unicode.org/reports/tr15/#Design_Goals
It seems the NFC process is combining characters across U+11930, even though its CCC is 0.

CC: @duerst (Martin Dürst)

[duerst (Martin Dürst)]

• Assignee changed from ima1zumi (Mari Imaizumi) to duerst (Martin Dürst)

@ima1zumi (Mari Imaizumi) Not sure this is even allowed, but I'm sure I'm responsible for this behavior, and want to fix it myself, so I change the Assignee to myself.

[ima1zumi (Mari Imaizumi)]

@duerst (Martin Dürst) Thank you, I appreciate you taking care of it.

[duerst (Martin Dürst)]

• Status changed from Open to Closed

Added regression test at https://github.com/ruby/ruby/commit/a122d7a58e91ed6cd531e906cb398688d7cc8b17
and fix at https://github.com/ruby/ruby/commit/e4c8e3544237b8c0efba6b945173dc66552d641c.
Many thanks to Tomoya Ishida for finding this bug.

[duerst (Martin Dürst)]

• Backport changed from 3.2: UNKNOWN, 3.3: UNKNOWN, 3.4: UNKNOWN to 3.2: DONTNEED, 3.3: DONTNEED, 3.4: DONTNEED

Backport would only be needed if the upgrade to Unicode 16.0.0 (see https://bugs.ruby-lang.org/issues/20724) is backported.

[duerst (Martin Dürst)]

Note to potential backporters: https://github.com/ruby/ruby/commit/bd51b20c50 should also be backported.

[camertron (Cameron Dutro)]

Hi there @duerst (Martin Dürst) 👋

I found this ticket after running into a normalization problem while working on an implementation of the Unicode Collation Algorithm. It seems there is at least one other case where the identity toNFD(x) == toNFD(toNFC(x)) is not maintained by the current Ruby normalization implementation:

# ruby 4.1 (master)
str = "\u0FB2\u0591\u0F81\u0061"
p str.unicode_normalize(:nfd) == str.unicode_normalize(:nfc).unicode_normalize(:nfd)
#=> false

In this example, the 0F81 decomposes into 0F71 0F80, which have combining classes of 129 and 130 respectively. The 0591 that comes logically earlier in the codepoint sequence has a combining class of 220. Because Ruby's NFD normalization algorithm decomposes subsections of the string rather than the entire string at once, the 0FB2 and 0591 are processed in isolation, which generates a string with combining classes 0 220 129 130 0, which is not the correct canonical order; 0591 (combining class of 220) should be ordered after 0F80 (combining class of 130).

One possible solution is to augment the NFD regex to include characters that decompose into entirely "accent" characters (i.e. characters that all have non-zero combining classes). That way, such characters are decomposed and reordered along with any accent characters that precede them.

I've created a PR demonstrating this solution: https://github.com/ruby/ruby/pull/19393

Curious to hear your thoughts.