i;unicode-casemap - Simple Unicode Collation Algorithm
Extracted elements (15)
Alternative implementations of the preparation process are permitted if they produce the same results. For example, converting all input to UTF-16 or UTF-32 prior to step (2) is acceptable, and UTF-32 may be used as an alternative to UTF-8 in step (3) if all strings are Unicode.
The collation is not locale sensitive. OS-supplied functions such as strcasecmp and toupper are sometimes locale sensitive and may inconsistently casemap letters, so care must be taken when using them to implement this collation.
UTF-16 is explicitly unsuitable as an alternative to UTF-8 in step (3) because UTF-16 surrogates cause i;octet to collate codepoints U+E0000 through U+FFFF after non-BMP codepoints, producing incorrect ordering.
i;unicode-casemap is intended as an alternative and preferred replacement for i;ascii-casemap but does not replace the i;basic collation. It is well suited for Internet protocols and computer languages but is often inappropriate for natural language sorting, including for some Scandinavian letters, Welsh names, and non-letter symbols.
UTF-8 and US-ASCII are the only mandatory-to-implement charsets for step (1)(a). All other charset support is optional, and strings in unsupported charsets fall through to binary i;octet comparison, which may produce collation results inconsistent with user expectations.
An implementation MAY use an NFKD library routine that normalizes out-of-order diacriticals in step (2)(b), which impacts step (2)(b) and possibly step (1)(a); this is an issue only with ill-formed UTF-8 input.
For input strings in UTF-8, the UTF-8 sequence MUST be valid according to the rules of RFC 3629; overlong UTF-8 sequences are invalid. If an invalid sequence occurs, conversion ceases, partial results are discarded, and the original string is used unchanged with the i;octet comparator.
Implementations SHOULD, as far as feasible, support all the charsets they are likely to encounter in the input data in order to avoid poor collation caused by falling through to the i;octet binary comparison rule.
Each input string is prepared by converting it to a 'titlecased canonicalized UTF-8' string through a four-step process: obtain Unicode codepoints, apply titlecase then recursive decomposition, append in UTF-8, and repeat. The resulting prepared string is then compared using i;octet operations.
Step (2)(a): if a codepoint has a titlecase property in UnicodeData.txt (normally the same as uppercase), it is converted to the titlecase codepoints. Step (2)(b): if the resulting codepoint has a decomposition property of any type, it is recursively decomposed until no further decomposition is possible (effectively NFKD).
Strings in arbitrary and mixed character sets are allowed as long as the character set is identified and conversion to Unicode is possible. Strings with unidentified character sets or that cannot be converted to Unicode are treated as binary rather than rejected.
The 'i;unicode-casemap' collation is a simple case-insensitive collation for Unicode strings providing equality, substring, and ordering operations. The validity test operation returns 'valid' for any input.
The i;unicode-casemap collation has been added to the IANA registry of collations defined in RFC 4790 (Internet Application Protocol Collation Registry), with scope 'global' and intended use 'common'.
An attacker may create ill-formed or unknown-charset input to impact comparator results or exploit other system components. Even well-formed data can cause unexpected results; for example, substituting U+0041 (LATIN CAPITAL LETTER A) with U+0391 (GREEK CAPITAL LETTER ALPHA) or U+0410 (CYRILLIC CAPITAL LETTER A) can cause visually identical strings to not match or sort differently.
Implementations MUST consider whether result variation across implementations is a problem for their use case. Four sources of variation are identified: (1) new Unicode characters with unknown decomposition/titlecase properties, (2) optional NFKD normalization of out-of-order diacriticals in step (2)(b), (3) open-ended charset support in step (1)(a), and (4) charset revisions adding new characters.