| 1 |
.. _imap-developer-guidance-internationalization: |
| 2 |
|
| 3 |
.. Note: This document was converted from the original by Nic Bernstein |
| 4 |
(Onlight). Any formatting mistakes are my fault and not the |
| 5 |
original author's. |
| 6 |
|
| 7 |
Cyrus IMAP Server: Internationalization |
| 8 |
======================================= |
| 9 |
|
| 10 |
introduction |
| 11 |
------------ |
| 12 |
|
| 13 |
Cyrus currently transcodes characters to a canonical UTF-8 form for |
| 14 |
searching. The base spec of IMAP4 only requires understanding multiple |
| 15 |
character sets to properly implement SEARCH. Since the base spec came |
| 16 |
out, several extensions have been proposed that require further charset |
| 17 |
support: SORT, THREAD, and the Sieve subsystem. As of this writing, |
| 18 |
Cyrus doesn't correctly support these other commands. |
| 19 |
|
| 20 |
Cyrus currently only believes in 16-bit characters. Technically, Unicode |
| 21 |
has up to 21-bit characters (expressible in UTF-16 and 3-byte UTF-8) and |
| 22 |
ISO 10646 allows up to 31-bit characters (though ISO's current policy is |
| 23 |
to not allocate any characters outside of the 21-bit Unicode range). The |
| 24 |
lower 16-bit characters make up the basic multilingual plane (BMP) where |
| 25 |
the majority of languages live. This restriction is apparent in |
| 26 |
``charset.c:writeutf8()``, the UTF-8 decoders, and the Unicode |
| 27 |
canonicalization table used by Cyrus. Since Cyrus's known character sets |
| 28 |
(except for UTF-8) don't contain any characters off of the BMP this |
| 29 |
isn't seen to be a major problem. |
| 30 |
|
| 31 |
Throughout this text, Unicode and ISO 10646 will be used interchangeable |
| 32 |
to refer to the 16-bit character set of the BMP, regardless of encoding. |
| 33 |
"Character", unless otherwise specified, refers to a single Unicode |
| 34 |
character ``ffff`` or under. |
| 35 |
|
| 36 |
cyrus canonical form |
| 37 |
-------------------- |
| 38 |
|
| 39 |
Since when users search e-mail messages it's much easier for them to |
| 40 |
eliminate false positives than realize there are hits that aren't |
| 41 |
displayed, the Cyrus searching algorithm errs on the side of more |
| 42 |
matches. Before comparing any two strings, Cyrus puts them in a |
| 43 |
canonical form. Logically, the process works as follows: |
| 44 |
|
| 45 |
- the input string is translated into a sequence of Unicode characters. |
| 46 |
- each character is transformed into lowercase. (For some characters, a |
| 47 |
single uppercase character may transform into multiple lowercase |
| 48 |
characters.) |
| 49 |
- each character is fully decomposed. |
| 50 |
- all whitespace (Unicode general categories starting with ``Z``) is |
| 51 |
removed. |
| 52 |
- combining diacritical marks, such as the accent on é, are removed. |
| 53 |
(These are Unicode characters ``0300``-``03ff``.) |
| 54 |
- certain characters are expanded to alternative spellings using ASCII |
| 55 |
characters, such as "æ" to "ae". |
| 56 |
- the output characters are then encoded in UTF-8. |
| 57 |
|
| 58 |
The actual transcoding does all of these steps at once with the aid of |
| 59 |
tables, carefully built at compile-time. |
| 60 |
|
| 61 |
The central part of Cyrus's internationalization support is it's |
| 62 |
transcoding routines in ``lib/charset.[ch]``, and |
| 63 |
``lib/chartable.[ch]``. Cyrus's transcoding routines are very elegant |
| 64 |
and very compact, thus somewhat intimidating. During compilation, Cyrus |
| 65 |
builds up a large number of tables (see `mkchartable <#mkchartable>`__) |
| 66 |
and uses them so that it never has to consider more than a single octet |
| 67 |
at a time while outputting the Cyrus canonical form for an input string. |
| 68 |
|
| 69 |
external interface |
| 70 |
------------------ |
| 71 |
|
| 72 |
``lib/charset.h`` is the public interface for Cyrus lib clients to get |
| 73 |
character canonicalization and searching support. In contains the |
| 74 |
following functions: |
| 75 |
|
| 76 |
``char *charset_convert(const char *s, int charset, char *buf, int bufsz)`` |
| 77 |
Given a string *s* in charset *charset*, decode it into canonical |
| 78 |
form in *buf*. *buf* must be reallocable and currently at least size |
| 79 |
*bufsz*. |
| 80 |
``char *charset_decode_mimeheader(const char *s, char *buf, int bufsz)`` |
| 81 |
Given a string *s* containing possible MIME encoded substrings (per |
| 82 |
RFC 2047), decode into canonical form in *buf*. *buf* must be |
| 83 |
reallocable and currently at least size *bufsz*. |
| 84 |
``charset_index charset_lookupname(const char *name)`` |
| 85 |
Given *name* return the Cyrus charset index. 0 always represents |
| 86 |
US-ASCII. The returned charset\_index may be saved in a file; it is |
| 87 |
stable and is an integer. If this version of Cyrus does not support |
| 88 |
the charset, ``CHARSET_UNKNOWN_CHARSET`` is returned. |
| 89 |
``comp_pat *charset_compilepat(const char *s)`` |
| 90 |
Compiles a NUL-terminated canonicalized string *s* into a |
| 91 |
Boyer-Moore table for fast searching. I'll describe these `compiled |
| 92 |
patterns <#comp_pat>`__ later. |
| 93 |
``void charset_freepat(comp_pat *pat)`` |
| 94 |
Frees a pattern previously return by ``charset_compilepat()``. |
| 95 |
``int charset_searchstring(const char *substr, comp_pat *pat, const char *s, int len)`` |
| 96 |
Searches for a canonicalized string *substr* in the canonicalized |
| 97 |
string *s*. *s* is of length *len*. *substr* must have been |
| 98 |
previously compiled into *pat*. Returns non-zero for a hit, zero for |
| 99 |
no match. |
| 100 |
``int charset_searchfile(const char *substr, comp_pat *pat, const char *msg_base, int mapnl, int len, charset_index charset, int encoding)`` |
| 101 |
Searches for the canonicalized string *substr* with compiled pattern |
| 102 |
*pat* in a large buffer starting at *msg\_base* of length *len*. The |
| 103 |
large buffer is of charset *charset* with the encoding *encoding*. |
| 104 |
``charset_searchfile()`` will dynamically unencode and canonicalize |
| 105 |
the search text looking for *substr*. (If *mapnl* is set, the buffer |
| 106 |
has only ``\n`` instead of ``\r\n``, but the length assumes that |
| 107 |
each ``\n`` is dynamically converted to ``\r\n``. This feature is |
| 108 |
deprecated.) |
| 109 |
``char *charset_decode_mimebody(const char *msg_base, int len, int encoding, char **buf, int *bufsz, int *outlen)`` |
| 110 |
Decode the MIME body part (per RFC 2045) located in the large buffer |
| 111 |
starting at *msg\_base* of length *len*. The large buffer is of |
| 112 |
encoding *encoding*. ``charset_decode_mimebody()`` will decode into |
| 113 |
*buf*. *buf* must be reallocable and currently at least size |
| 114 |
*bufsz*. The number of decoded bytes is returned in *outlen*. |
| 115 |
``charset_extractfile()`` |
| 116 |
Used by ``squatter`` and possibly other text indexing engines, but |
| 117 |
not described here. |
| 118 |
|
| 119 |
the TRANSLATE macro: using the transcoding tables |
| 120 |
------------------------------------------------- |
| 121 |
|
| 122 |
The external interface is implemented with the help of the ``START`` and |
| 123 |
``TRANSLATE`` macros: |
| 124 |
|
| 125 |
``void START(struct decode_state *state, const unsigned char (*table)[256][4])`` |
| 126 |
``START`` initializes *state* to be ready for transcoding of the |
| 127 |
charset translation table given with *table*. The starting active |
| 128 |
table is always the first one in the list passed in. |
| 129 |
``void TRANSLATE(struct decode_state *state, unsigned char input, unsigned char *outbuf, unsigned outindex)`` |
| 130 |
``TRANSLATE`` takes four parameters: *state* is the current state of |
| 131 |
the translation; it must have been initialized with ``START`` and is |
| 132 |
modified by ``TRANSLATE``; *input* is one octet of input from the |
| 133 |
stream to be transcoded; *outbuf* is a pointer to the start of the |
| 134 |
buffer to write output characters; *outindex* is the index where |
| 135 |
this translation should be written. The size of *outbuf* must be at |
| 136 |
least *outindex + charset\_max\_translation*. |
| 137 |
|
| 138 |
Each charset consists of a set of one or more tables; the *table* |
| 139 |
parameter passed into ``START`` is the first of these tables and the |
| 140 |
others are adjacent in memory. Characters are transcoded by indexing |
| 141 |
into the active table with *input* and examining the 4 octet |
| 142 |
translation. The 4 octet translation may consist of 0–3 character |
| 143 |
translations followed by a control code or a series of control codes. In |
| 144 |
effect, the translation for a given octet is a mini-program that |
| 145 |
consists either of UTF-8 octets or control codes. One of the control |
| 146 |
codes RET, END, JSR, or JMP must occur in the 4 octet translation. |
| 147 |
|
| 148 |
control codes |
| 149 |
~~~~~~~~~~~~~ |
| 150 |
|
| 151 |
Control codes are represented by uppercase US-ASCII characters since no |
| 152 |
uppercase characters can appear in the output translation (recall that |
| 153 |
Cyrus canonical form downcases). Any uppercase US-ASCII character |
| 154 |
(``[A .. Z]``) is thus interpreted specially by the ``TRANSLATE`` |
| 155 |
virtual machine. Any other octet encountered as an output translation is |
| 156 |
presumed to be part of the UTF-8 output sequence and copied to the |
| 157 |
output. |
| 158 |
|
| 159 |
The names of control codes are actually C pre-processor defines to |
| 160 |
uppercase US-ASCII characters. As the mnenomics are easier to |
| 161 |
understand, I use them in discussing their semantics. |
| 162 |
|
| 163 |
control code reference |
| 164 |
~~~~~~~~~~~~~~~~~~~~~~ |
| 165 |
|
| 166 |
``TRANSLATE`` recognizes the following "normal" control codes: |
| 167 |
|
| 168 |
XLT |
| 169 |
This is the first octet of the four octet sequence, indicating that |
| 170 |
the desired translation is larger than 3 UTF-8 octets. The next two |
| 171 |
octets represent an offset to look up in the special |
| 172 |
chartables\_long\_translations[] table. After that translation is |
| 173 |
copied to the outbuf, the final octet is interpreted (it must be |
| 174 |
either a RET or an END). |
| 175 |
JSR |
| 176 |
The ``TRANSLATE`` virtual machine has a stack, fixed at size 1. A |
| 177 |
JSR copies address of the current active table to the stack and |
| 178 |
transitions to the active table given by the next two octets. (For |
| 179 |
instance, table 1 would be the next table after the table given as a |
| 180 |
parameter to ``START``.) Translation of the current octet stops |
| 181 |
after encountering a JSR. |
| 182 |
|
| 183 |
JSRs are useful for converting a two octet input character: the |
| 184 |
first octet in the character will make a JSR to some table; the |
| 185 |
second octet will produce a translation and RET to the current |
| 186 |
table. |
| 187 |
|
| 188 |
Since the virtual machine has a fixed size stack, it would be highly |
| 189 |
unusual for the virtual machine to encounter two different JSRs |
| 190 |
without an intervening RET. |
| 191 |
|
| 192 |
JMP |
| 193 |
Similar to JSR, but does not change the stack. It is the equivalent |
| 194 |
of a goto. JMPs are useful to deal with modal input character sets |
| 195 |
(such as an escape in ISO-2022-JP, see `how the tables are |
| 196 |
generated <#mkchartable>`__). |
| 197 |
RET |
| 198 |
Indicates that we are done translating this input octet and we |
| 199 |
should return to the previous active table. It might appear as the |
| 200 |
first of the 4 translation octets, in which case this input |
| 201 |
character translates into nothing (it might be whitespace, for |
| 202 |
instance). |
| 203 |
END |
| 204 |
Indicates we are done translating this input octet. When |
| 205 |
``TRANSLATE`` is next called, that input octet will be interpreted |
| 206 |
against the current active table; the stack does not change. |
| 207 |
|
| 208 |
In addition, it recognizes the following "special" control codes for |
| 209 |
charsets that aren't easily represented by a set of tables, UTF-8 and |
| 210 |
UTF-7: |
| 211 |
|
| 212 |
U7F |
| 213 |
UTF-7 consists of US-ASCII characters and a special escape character |
| 214 |
that indicates a transition to base-64 encoded UTF-16 characters. |
| 215 |
The virtual machine has built in code to handle the base64 decoding. |
| 216 |
In UTF-7's base64, 8 input octets result in 3 characters, so the |
| 217 |
tables would be rather large. |
| 218 |
U7N |
| 219 |
This indicates that the current octet is the continuation of the |
| 220 |
base-64 section. |
| 221 |
U83 |
| 222 |
One and two character UTF-8 sequences are handled normally in the |
| 223 |
charset code. To keep the table size down, 3 octet sequences are |
| 224 |
handled specially. U83 indicates that the current input octet is the |
| 225 |
start of a three character sequence. It is also an implicit jump to |
| 226 |
the 2nd table in the UTF-8 sequence, ending this translation. |
| 227 |
U83\_2 |
| 228 |
This input octet 2nd of 3-octet UTF-8 input, with an implicit jump |
| 229 |
to the 3rd table. |
| 230 |
U83\_3 |
| 231 |
3rd octet of a 3-octet UTF-8 input. This produces the output |
| 232 |
characters and has an implicit jump to the 1st table of UTF-8. |
| 233 |
|
| 234 |
Finally, it's useful to mention the special character ``EMPTY`` which is |
| 235 |
guaranteed not to match any character. It is also represented by an |
| 236 |
uppercase US-ASCII character. |
| 237 |
|
| 238 |
searching and compiled patterns |
| 239 |
------------------------------- |
| 240 |
|
| 241 |
boyer-moore |
| 242 |
~~~~~~~~~~~ |
| 243 |
|
| 244 |
brief description of boyer-moore xxx |
| 245 |
|
| 246 |
cyrus implementation |
| 247 |
~~~~~~~~~~~~~~~~~~~~ |
| 248 |
|
| 249 |
why two arrays? us-ascii optimization, really kinda useless now xxx |
| 250 |
|
| 251 |
meta-data stored at the end xxx |
| 252 |
|
| 253 |
generating the tables: ``mkchartable`` |
| 254 |
-------------------------------------- |
| 255 |
|
| 256 |
The program ``mkchartable`` is used to generate the charset transcoding |
| 257 |
tables used by TRANSLATE. These tables are carefully constructed so no |
| 258 |
more than a single octet need be examined at a time; this octet results |
| 259 |
in either an output stream of UTF-8 characters being generated or some |
| 260 |
sort of state change. |
| 261 |
|
| 262 |
``mkchartable`` uses three different sorts of input files to generate |
| 263 |
these tables. These files are located in the ``lib/charset`` directory. |
| 264 |
|
| 265 |
charset tables |
| 266 |
~~~~~~~~~~~~~~ |
| 267 |
|
| 268 |
Each charset file maps a single charset to the corresponding Unicode |
| 269 |
characters. For the US-ASCII and ISO-8859-x character sets this is |
| 270 |
trivial: each input byte corresponds to a single Unicode character. |
| 271 |
(Actually, some ISO-8859-x octets do not map to any Unicode character. |
| 272 |
In that case, the file either does not contain that octet or map it to |
| 273 |
"``????``".) |
| 274 |
|
| 275 |
Other character sets are trickier. For instance, GB-2312 has both single |
| 276 |
and double byte characters, but is still a simple map from input |
| 277 |
character to output character. More complicated are modal character |
| 278 |
encodings. For instance, ISO-2022-JP starts in US-ASCII mode and uses |
| 279 |
``1B`` as an escape character followed by another two characters to |
| 280 |
select a new mode. |
| 281 |
|
| 282 |
The input charset labels modes with "``:``" followed by the mode name. |
| 283 |
The starting mode "``US-ASCII``" in ISO-2022-JP is preceded by |
| 284 |
"``:US-ASCII``". Mode transitions are denoted by a Unicode conversion of |
| 285 |
"``>newmode``" or "``:newmode``". To denote that the octet ``42`` |
| 286 |
transitions into the "``US-ASCII``" mode, the charset file has |
| 287 |
"``42 >US-ASCII``". The mode names themselves are arbitrary labels and |
| 288 |
have no effect on the output. |
| 289 |
|
| 290 |
The input charset labels modes with ":" followed by the mode name. The |
| 291 |
mode name is optionally followed by a space and the "``<``" character. |
| 292 |
If the "``<``" character is present, then all translations will be |
| 293 |
followed by a RET instruction instead of an END instruction. |
| 294 |
|
| 295 |
The transition "``>newmode``" results in a JSR instruction being |
| 296 |
generated. A JMP instruction is generated by a transition of |
| 297 |
"``:newmode``". |
| 298 |
|
| 299 |
The input byte can be specified as "``*``". This is used to define the |
| 300 |
"default action" which is used for input bytes that are not otherwise |
| 301 |
defined for the mode. If the default action is not explicitly stated, it |
| 302 |
is a translation to EMPTY. |
| 303 |
|
| 304 |
unicode data table |
| 305 |
~~~~~~~~~~~~~~~~~~ |
| 306 |
|
| 307 |
The ``unidata2.txt`` file is verbatim from the Unicode standard. More |
| 308 |
recent versions should be available `from their |
| 309 |
website <http://www.unicode.org/xxx>`__. Each entry in the file |
| 310 |
describers a Unicode character by the following properties, separated by |
| 311 |
semicolons: |
| 312 |
|
| 313 |
- code point (16-bit character value) in hex |
| 314 |
- character name (unused by Cyrus) |
| 315 |
- general category, such as whitespace or punctuation |
| 316 |
- the canonical combining class (unused) |
| 317 |
- bidirection category (unused) |
| 318 |
- character decomposition |
| 319 |
- decimal digit value (unused) |
| 320 |
- digit value (unused, and, no, I don't know the difference) |
| 321 |
- numeric value including fractions (unused) |
| 322 |
- mirrored character (unused) |
| 323 |
- Unicode 1.0 name (unused) |
| 324 |
- comment (unused) |
| 325 |
- upper case equivalent (unused) |
| 326 |
- lower case equivalent |
| 327 |
|
| 328 |
In general, Cyrus uses the lower case equivalent if there is one, and |
| 329 |
the decomposed value otherwise. |
| 330 |
|
| 331 |
unicode fixup table |
| 332 |
~~~~~~~~~~~~~~~~~~~ |
| 333 |
|
| 334 |
The ``unifix.txt`` file contains Cyrus-specific mappings for characters. |
| 335 |
It overrides the ``unidata2.txt`` table. Each rule in the file is |
| 336 |
explained with a comment. It's helpful to remember that the Unicode |
| 337 |
general categories starting with ``Z`` represent whitespace, and |
| 338 |
whitespace is always removed. |
| 339 |
|
| 340 |
generating ``chartable.c`` |
| 341 |
~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 342 |
|
| 343 |
how ``mkchartable`` works: collapses the encoding modes, the unicode |
| 344 |
translations, and other normalizations into the output tables described |
| 345 |
above xxx |
| 346 |
|
| 347 |
for the future |
| 348 |
-------------- |
| 349 |
|
| 350 |
Sieve/ACAP comparators |
| 351 |
~~~~~~~~~~~~~~~~~~~~~~ |
| 352 |
|
| 353 |
adjustable normalization? |
| 354 |
~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 355 |
|
| 356 |
The use of uppercase US-ASCII characters is one of the annoyances in |
| 357 |
trying to generalize the charset transcoding. If we continue to restrict |
| 358 |
the characters under consideration to the BMP, switching to UTF-8 |
| 359 |
control codes that start 4 or 5 byte sequences is possible. |
| 360 |
|
| 361 |
Another possibility is to use a NUL character as an escape sequence, |
| 362 |
though this increases the size of each control code by 1 octet. |
| 363 |
|
| 364 |
handle >2 octet input characters |
| 365 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 366 |
|
| 367 |
make UTF-8 more regular |
| 368 |
~~~~~~~~~~~~~~~~~~~~~~~ |
| 369 |
|
| 370 |
consider whether we really need U83, U83\_2, U83\_3. also consider |
| 371 |
changing ``{ U83, 0, 0, 0 }`` translations to ``{ U83, JMP, 0, 1 }`` |
| 372 |
sequences to at least eliminate the implicit jump. |
| 373 |
|
| 374 |
require minimal UTF-8 characters |
| 375 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 376 |
|
| 377 |
references |
| 378 |
---------- |
| 379 |
|
| 380 |
xxx |
| 381 |
|
| 382 |
- [UNICODE] Unicode / ISO 10646 |
| 383 |
- [UTF-8] utf-8 RFC |
| 384 |
- [UTF-7] utf-7 RFC |
| 385 |
- [BM] boyer-moore |
| 386 |
- [ACAP] the comparators reference. see section XXX of RFC 2244. |