2009-07-30 Gonzalo Paniagua Javier <gonzalo@novell.com>

[mono.git] / mcs / class / corlib / Mono.Globalization.Unicode / Collation-notes.txt

* String collation Notes

** Summary

        We are going to implement Windows-like collation, apart from ICU (that
        implements UCA, Unicode Collation Algorithm).


** Tasks

        * create collation element table(s)
                - infer how Windows collation element table is composed
                  : mostly analyzed.
                - write table generator source(s)
                  : mostly implemented. Need to fix nearly 400 mappings.
                    They are mainly 1) IPA extensions (U+250-U+300),
                    2) Latin extensions (U+1E00-U+1F00), 3) Letterlike
                    symbols (U+2100-U+2140), 4) some Cyrillic letters
                    (U+460-U+500), and 5) some Hangul characters.
                - culture-specific sortkey data
                  : They are defined in mono-tailoring-source.txt.
                    All single sortkey remapping in all cultures are filled.
                    Contractions are not fully checked yet (should be filled
                    from UCA tailorings via create-tailorings.exe).


** How to implement CompareInfo members

        GetSortKey() : done
                Compute sort key for every character elements into byte[].
        Compare() : done
                Find first difference and compare it.
                "Larger/smaller" matters (beyond "different").
        IsPrefix()
                It calls CompareInternal() which also answers if the target
                is fully consumed, so it just returns true if it says that
                the target is fully consumed.
        IsSuffix()
                It tries CompareInternal() to compare source and target at
                the end, where source varies from minimum tail to the
                original args.
        IndexOf(), LastIndexOf()
                For character search, it finds the matching character element
                to the end (or start) of the string to find.
                For string search, it invokes one of private IndexOf() (or
                LastIndexOf()) overload passing the first character element
                of the target, and if found, tests if the sequence is a valid
                start point, using IsPrefix() (or IsSuffix()).

*** Optimizations

        For Compare() and IsPrefix(), it uses forward iteration, which moves
        forward and don't stop until either it finds next "primary" character
        or it reached the end of the string, checking with IsSafe(char).

        For IndexOf(char) and LastIndexOf(char), there is no special 
        optimization (since the codepoints usually do not match, while they
        often matches as a natural collation), but it omits extraneous sortkey
        value computation.

        IsSuffix() reuses Compare() and returns false if it does not consume
        the target string more than 3 times. 3 is kind of magic number that
        represents the longest expansion.

        IndexOf(string) is implemented as a combination of IndexOf(char) and
        IsPrefix().

        LastIndexOf(string) is implemented as a combination of
        LastIndexOf(char) and IsPrefix().

        Porting them to C code is an alternative possible approach, but from
        Compare() optimization experience, it is quick enough.

** How to support CompareOptions

        There are two kind of "ignorance" : strippers' ignorance and
        normalizers' ignorance.

        The strippers will "filter characters out" and there will be no
        corresponding character elements in SortKey binaries.

        Normalizers, on the other hand, will result in certain characters 
        that is still in effect between irrelevant character and itself.
        For example, with IgnoreKanaType Hiragana "A" and Katakana "A" are
        not distinguished, but Hiragana "A" and Hiragana "I" are.

        Actually, even without any IgnoreXXX flags (i.e. "None"), there are 
        many characters that are ignored ("completely ignorable").

        Except for LCID 101/1125(div), '\ufdf2' is completely ignorable.
        This rule even applies to CompareOptions.None.

*** Normalizers

        IgnoreCase
                Maybe culture-dependent TextInfo.ToLower() could be used.

                Unlike ICU (specialCaseToLower()), even with tr-TR(LCID 31)
                and IgnoreCase, I\u0307 is not regarded as equal to i.

        IgnoreKanaType
                ToKanaTypeInsensitive(). Note that this does not cover the
                whole "level 4" differences described later.

        IgnoreWidth
                ToWidthInsensitive(), which is likely to be culture
                independent. See also "Notes".

        IgnoreNonSpace (see also Strippers; this flag works in both sides)
                For some cultures this logic is still incomplete. All culture-
                dependent collators must handle valid "replacement" of "one or
                more characters" which might be related to specific
                CompareOptions.
                For example, there is a Japanese text sorting rule that
                however applies to InvariantCulture. Concretely to say,
                "\u3042\u30FC" is equivalent to "\u3042\u3042" only when
                IgnoreNonSpace is specified.

                I'll take those items from CLDR (those items which has
                <reset before="..." />), case by case though.

*** Strippers

        I already wrote all the required strippers which should be MS
        compatible (at least with .NET 1.1 invariant culture).

        IgnoreNonSpace
                IsIgnorableNonSpacing().
                Some Diacritic characters are covered by this flag.

                There are some culture *dependent* characters:
                        LCID 90/1114(syr) : 64b, 652, 670

        IgnoreSymbols
                IsIgnorableSymbol().
                UnicodeCategory does not work here.

                There are some culture *dependent* characters:
                        LCID 17/1041(ja) : 2015
                        LCID 90/1114(syr) : 64b, 652

*** StringSort

        See "sort order categories" section.

** ICU and UCA

        First to note: we won't use collation element table from unicode.org.

        There are many differences between ICU/UCA and Windows despite they
        look so similar; having collation keys in different levels, culture
        dependent composition, etc. In the history, Windows collation is 
        designed before UCA was specified, so basically Windows is obsolete
        in this area. 
        
        - Logic: Unlike UCA it has no concept of "blocked" combining marks,
          and combining marks are never considered as an independent character
          (thus combining in Windows is buggy).
        - Data: Windows is based on old Unicode standard (even older than 1.1).
          It ignores minor cultures. Character property values differ as well
          as those from the default Unicode collation element table (DUCET).
          In a few cultures Windows collation is close to the native language
          (e.g. Tamil, while it does not conform to TAM).

        IgnoreWidth/IgnoreSymbols is processed after Kana voice mark
        decomposition (something like NFD, but not equivalent. Example: \u304C
        is completely equivalent to \u304B\u309B, which is not part of NFKD).
        <del>This means, if there is a combined Kana characters, it will be
        first decomposed and then compared.<del> It scarcely matters since
        there are special weight data for Japanese.

*** Microsoft design problem

        Microsoft implementation seems to have a serious problem that many,
        many characters that are used in for each specific culture, such as
        Myanmar, Mongolian, Cherokee, Etiopic, Tagalog, Khmer, are regarded as
        "completely ignorable".

        I tagged many LAMESPEC items in the implementation (both in collator
        and table generator).


** MS collation design inference

*** Levels

        Each character has several "weights". It is a common concept between
        Windows and UCA.

        There are 5 levels:

        - level 1: primary difference
          The first byte of level 1 means the category of the character.
        - level 2: diacritic difference, including Japanese voice mark countup
        - level 3: case/width sensitivity, and Hangul properties
        - level 4: kana weight (all of them have primary category 22, at least
          in InvariantCulture)
        - level 5: shift weight (apostrophe, hyphens etc.)

        Note that these levels does not digitally match IgnoreXXX flags. Thus
        it is not OK that we omit some levels of sortkey values in reflection
        to CompareOptions.

        String comparison is done from level 1 to 5. The comparison won't
        stop until either it found the primary difference, or it reached to
        the end (thus upper level differences are returned).

        For example, "e" is smaller than "E", but "eB" is bigger than "EA".
        If the collator just returned case difference at first 'e' and 'E',
        "eB" is still smaller than "EA".

**** level 5: shift weight by StringSort

        There are some characters that are treated specially. Namely they are
        apostrophe and hyphens. The sortkeys for them is put after level 4
        (thus here I write them as "level 5"). It has different sort key
        format. See immediate below. There is no level 5 characters when 
        StringSort is specified.

*** sort key format

        00 means the end of sort key.
        01 means the end of the level.
        02-FF means the value.
        Actually '2' could be cut when all the following values are
        also '2' (i.e. the sort key binary won't contain extraneous '2').

        Every level has different key layout.

**** level 2

        It looks like all level 2 keys are just accumulated, however without
        considering overflow. It sometimes makes sense (e.g. diaeresis and
        acute) but it causes many conflicts (e.g. "A\u0308\u0301" and "\u1EA6"
        are incorrectly regarded as equal).

        Anyways since Japanese voice mark has level 2 value as 1 it just
        looked like the sum of voice marks.

**** level 3

        The actual value analysis is not complete in this document. See the
        actual generator code.

        The actual values are + 2 (e.g. for Hangul Normal Jamo, the value is 4)

        For Korean letters:
                - 2: Jongseong (11A8-11F9)
                - 4: Half width? (FFA0-FFDC) and Compatibility Jamo? (3165-318E)
                - 5: Compatibility Jamo (3130-3164)?
                     TODO: Learn about Korean characters.

        For numbers:
                - 4 circled inverse (2776-277F)
                - 8 circled sans serif (2780-2789)
                - C circled inverse && sans serif (278A-2793)
                - 47 roman (2160-2182)

        For Arabic letters:
                - 2 Isolated form in presentation form B in FE80-FE8D
                - 4 Alef/Bet/Gimel/Dalet (2135-2138)
                - 8 Final form in presentation form B in FE82-FEF2
                - 18 Medial form in presentation form B in FE8C-FEF4
                     Grep "ISOLATED", "FINAL" or "MEDIAL" on UnicodeData.txt
                     (and filter by codepoints).
                     or alternatively, see DerivedDecompositionType.txt.
                - 22 6A9 (TODO: what is it?)
                - 28 6AA (TODO: what is it?)

        For other letters:
                - 1 Fullwidth. UnicodeData.txt has <full>.
                - 2 Subscript. UnicodeData.txt has <sub>.
                - 8 Small capital, 03C2 (TODO: why?),
                    2104, 212B(flag=1A) (TODO: why?)
                    grep "SMALL CAPITAL" against UnicodeData.txt.
                - C only FE42. TODO: what is this?
                - E Superscripts. UnicodeData.txt has <super>.
                - 10 Uppercase.
                     DerivedCoreProperties.txt has Uppercase property.

        Note that simple 02 (value is 00) could be omitted.

        Summary: at least 7 bits are required as to represent a table -
        smallCapital, uppercase, normalization forms (2 bits:full/sub/super),
        arabic forms (2 bits:isolated/medial/final)

**** level 4

        Those sortkey data is collected only for Japanese (category 22)
        characters.

        There are 3 sections each of them ends with FF. Each of them
        represents the values for character by character:
        - small letter type (kogaki moji); C4 (small) or E4 (normal)
        - category middle section:
                two subsections separated by 0x02
                - char type;
                  3 (normal)
                  or 4 (voice mark - \u309D,\u309E,\u30FD,\u30FE, \uFF70)
                  or 5 (dash mark - \u30FC)
                - kana type; C4 (katakana) or E4 (hiragana)
        - width; 2 (normal) or C5 (full) or C4 (half)

          LAMESPEC: those characters of value '4' of middle section differs
          in level 2 wrt voice marks, but does not differetiate kana types
          (bug). It is ignored when IgnoreNonSpace applies.

**** level 5

        UPDATED: I noticed offsetL does not exist, so removed it from here.

        [offsetM + 0x80]? [const 3 + (offsetS + 1) * 4] [category] [level1]

        where "offsetM" and "offsetS" represents the offset in the input
        string. "offsetM" is always larger than 0x80.
        LAMESPEC: This design results in a buggy overflow.

        <xmp>
        byte [] data = new CultureInfo ("").CompareInfo.GetSortKey (s).KeyData;
        int idx = 0;
        for (int i = 0; i < 4; i++, idx++)
                for (; data [idx] != 1; idx++)
                        ;
        for (; idx < data.Length; idx++)
                Console.Write ("{0:X02} ", data [idx]);
        Console.WriteLine ();
        </xmp>

        inputs (s) and results:

        80 07 06 82 80 2F 06 82 00 // '-' + new string ('A', 10) + '-'
        80 07 06 82 81 97 06 82 00 // (100)
        80 07 06 82 8F A7 06 82 00 // (1000)
        80 07 06 82 9C 47 06 82 00 // (10000)
        80 07 06 82 9A 87 06 82 00 // (100000)
        80 07 06 82 89 07 06 82 00 // (1000000)

        The actual offset is 63 * offsetM + offsetS

        (const '3' may actually vary but no idea.
        At least 00, 01 and 02 are not acceptable since they are reserved.
        02 is not reserved by definition above, but the key-size optimizer
        uses it as a special mark, as mentioned above.)

*** sort key table

        Here is the simple sortkey dumper:

        public static void Main (string [] args)
        {
                CultureInfo culture = args.Length > 0 ?
                        new CultureInfo (args [0]) :
                        CultureInfo.InvariantCulture;
                CompareInfo ci = culture.CompareInfo;
                for (int i = 0; i < char.MaxValue; i++) {
                        string s = new string ((char) i, 1);
                        if (ci.Compare (s, "") == 0)
                                continue; // ignored
                        byte [] data = ci.GetSortKey (s).KeyData;
                        foreach (byte b in data) {
                                Console.Write ("{0:X02}", b);
                                Console.Write (' ');
                        }
                        Console.WriteLine (" : {0:X}, {1} {2}",
                                i,
                                Char.GetUnicodeCategory ((char) i),
                                data [2] != 1 ? '!' : ' ');
                }
        }

*** multiple character mappings

        Some sequence of characters are considered as a "composite" that is
        to be composed either as another character or another sequence of 
        characters. Those "composite" might not have corresponding equivalent
        character in sortkey.
        Similarly, some single characters are expanded to a sequence of
        characters.

**** diacritic characters

        Except for those shift-weight characters, there are only
        diacritical (or other kinds of nonspacing) characters that don't
        have primary weights.

        Diacritics are not regarded as a base character when placed after 
        (maybe some kind of) letters.

        The behavior is diacritic character dependent. For example, Japanese
        combination of a Kana character and a voice mark is compulsory (the
        resulting sort key is regarded as identical to the corresponding
        single character. Try \u304B\u309B with \u304C. It is invariant).

        In French cultures, diacritic orderings are checked from right to left.

**** Composite character processing

        There are some sequences of characters that are treated as another
        character or another sequence of characters.

        By default, there is no composite form.
        http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24C2.asp
        (Note that composite is different from expansion.)

        Note that composite characters is likely to not have equivalent
        codepoint.

**** Expanded character processing

        Some characters are expanded to two or more characters:

        C6 (AE), E6 (ae), 1F1-1F3 (dz), 1C4-1C6 (Dz), FB00-FB06 (ff, fi),
        132-133 (IJ), 1C7-1C9 (LJ), 1CA-1CC (NJ), 152-153 (OE),
        DF (ss), FB06 (st), FB05 (\u017Ft), FE, DE, 5F0-5F2,
        1113-115F (hangul)
        (CJK extension is not really expanded)

        They don't match with any of Unicode normalization.

        Some alphabetic cultures have different mappings, but mostly small
        (at least da-DK, lt-LT, fr-FR, es-ES have tiny differences).

        Invariant culture also puts Czech unique character \u0161 between s
        and t, unlike described here:
        http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24C0.asp

*** default sort key table

**** StringSort

        When CompareOptions.StringSort is specified, then it modifies
        characters in category 2 from "1 1 1 1 80 07 06 xx" to
        "06 xx yy zz" and some characters become case sensitive.

        For details, "level 5" description above.

        To handle them simply, they are laid out as "category 0x01" (which
        never happens in the actual sortkeys) for those shift-weight ones
        in the table.

        There seems no further differences between StringSort and None.

**** level 2 details

        The value analysis is not complete in this document. See the
        actual generator code.

        Known value maps:
                -0A: Korean parenthesized numbers (3200-321C)
                -0C: Korean circled numbers (3260-327B)

                -03: Japanese voice mark

                <primary category 13 : Arabic>
                -08: 627-648 (basic Abjad letters)
                -09: madda (622)
                -05: waw with hamza (624)
                -07: yeh with hamza (626. ignore Presentation Form A area)
                -0A: alef with hamza above (623)
                -0A: alef with hamza below (625)

                <primary category 0E : diacritics>
                Characters in non "0E" category are out of scope.
                They can be grepped in UnicodeData.txt.
                -0E: acute
                -0F: grave
                -10: dot above
                -11: middle dot
                -12: circumflex
                -13: diaeresis
                -14: caron
                     Note that 1C4-1C6 are covered but they are also expanded.
                -15: breve (cyrillic are also covered? at least 4C1/4C2 are.)
                -16: dialytika and tonos (category 0F though)
                -17: macron
                -19: tilde
                -1A: ring above | 212B
                -1B: ogonek ("WITH OGONEK;")
                -1C: cedilla (WITH CEDILLA;")
                -1D: double acute | acute and dot above
                -1E: stroke, except for 0E[1F] and cp{19B, 1BE} |
                     circumflex and acute | 18B,18C,19A,289
                     (i.e. they not one-to-one mapping. Neither that every
                     "stroke" are mapped to 1E, nor not every 1E are mapped to
                     "stroke".)
                -1F: diaeresis and acute | with circumflex and grave | l slash
                        beware "symbol slash"
                -20: diaeresis and grave | 19B,19F
                -21: breve and acute | D8,F8
                -22: caron and dot above | breve and grave
                -23: macron and acute
                -24: macron and grave
                -25: diaeresis and caron | dot above and macron | tilde and acute
                -26: ring above and acute
                -28: diaeresis and macron | cedilla and acute |
                     macron and diaeresis
                -29: circumflex and tilde
                -2A: tilde and diaeresis
                -2B: stroke and acute
                -2C: breve and tilde
                -2F: cedilla and breve
                -30: ogonek and macron
                -43: hook, except for cp{192,1B2,25A,25D,27B,28B,2B1,2B5} |
                     left hook | with hook above except for cp{1EF6,1EF7} |
                     27D,284
                -44: double grave | 1EF6,1EF7
                -46: inverted breve
                -48: preceded by apostrophe (actually only 149)
                -52: horn
                -55: line below | circumflex and hook above
                -57: palatal hook (actually only 1AB)
                -58: dot below except for cp{1EA0,1EA1}
                -59: "retroflex" (without "WITH") | diaeresis below | 1EA0,1EA1
                -5A: ring below | 1E76,1E77
                -60: circumflex below except for cp{1E76,1E77} | horn and acute
                -61: breve below | horn and grave
                -63: tilde below | 2125
                -68: D0,F0,182,183 | dot below and dot above | topbar
                -69: right half ring | horn and tilde
                -6A: circumflex and dot below
                -6D: breve and dot below
                -6E: dot below and macron
                -95: horn and hook above
                -AA: horn and dot

                (for 01-0D and 7B-8A, they are not related to diacritics.)

                <category BlahBlahNumbers from 0100 to 1000>
                -38: Arabic-Indic numbers (660-669)
                -39: extended Arabic-Indic numbers (6F0-6F9)
                -3A: Devanagari numbers (966-96F)
                -3B: Bengali numbers (9E6-9EF)
                -3C: Bengali currency enumerators (9F4-9F9)
                -3D: Gurmukhi numbers (A66-A6F)
                -3E: Gujarati numbesr (AE6-AEF)
                -3F: Oriya digit numbers (B66-B6F)
                -40: Tamil numbers (BE7-BF2)
                -41: Telugu numbers (C66-C6F)
                -42: Kannada numbers (CE6-CEF)
                -43: Malayam numbers (D66-D6F)
                -44: Thai numbers (E50-E59)
                -45: Lao numbers (ED0-ED9)
                <miscellaneous numbers>
                -47: Roman numbers (2160-2182)
                -4E: Hangchou numbers (3021-3029)

                -E0[64]: 2107 (Eurer)
                -E0[87]: some Tone letters (TONE TWO / TONE SIX)
                -EE: Circled letter-or-digits and katakanas
                        CIRCLED {DIGIT|NUMBER|LATIN|KATAKANA}
                        numbers (2460-2473,2776-2793,24EA)
                        latin (24B6-24E9)
                        katakana (32D0-32FE)
                -F3: Parenthesized enumerations
                        numbers (2474-2487)
                        latin (249C-24B5)
                        PARENTHESIZED {DIGIT|NUMBER|LATIN}
                -F4: Numbers with dot (2488-249B)
                        {DIGIT|NUMBER} * FULL STOP

                <miscellaneous>
                -258,25C-25E,285,286,29A,297 -> 0E[80-86,88]
                -27F,2B3-2B6 -> 0E 8A[80-84]
                -3D3 -> 0F[44]
                -476,477 -> 10[46]
                -215F -> 0C[03]

                -20D0-20E1 -> 01[DD-F0]
                -483-486 -> 01[94-97]
                -559,55A -> 01[98,99]
                -711 -> 01[9A]

                -346-348,2BE-2C5,2CE-2CF -> 01[74-7F]
                -2D1-2D3,2DE,2E4-2E9 -> 01[81-8A]

                -342,343 -> 01[8D,8E]
                -345 -> 01[90]

                -700-780 01[8D-AF]. Maybe there is some kind of traditional
                order in Estrangela, but for now am not sure.
                /*
                -740-742 -> 01[8D-8F]
                -747,748,732,735,738,739,73C,73F,743-746,730 -> 01[90,91,94-9F]
                -731,733,734,736,737,73A,73B,73D,73E,749,74A,7A6-7A9
                 -> 01[A0-AA,AC-AF]
                */
                -7AA-7B0 -> 01[B0-B6]

                -591-5C2 except for 5BA,5BE -> 01[03-33] in order

                No further patterns for >= 80

                TODO: Below are not done yet:
                        - x < 0x80 in non-"0E" part
                        - 03 <= x <= 0D in "0E" part
                        - 7B <= x <= 7F in "0E" part

**** sortkey details by category

        The actual value analysis is not complete in this document. See the
        actual generator code.

        1 specially ignored ones (Japanese, Tamil, Thai)

                IdentifyBy: constants
                Unicode: 3099-309C, BCD, E47, E4C, FF9E, FF9F
                SortKey: 01 01 01 01 00

        2 shift weight characters
        
        They are either at 01 01 01 01 or 06, depending on StringSort. For
        convenience, I use 06 to describe them.

        2.1 control characters (specified as such in Unicode), except for
        whitespaces (0009-000D).

                ProcessAfter: 4.1
                IdentifyBy: UnicodeCategory.Control
                Unicode: 0001-000F minus 0009-000D, 007F-009F
                SortKey: 06 03 - 06 3D

        2.2 Apostrophe
                IdentifyBy: constant
                Unicode: 0027,FF07 (')
                SortKey: 06 80 (and width insensitive equivalents)

        2.3  minus sign, hyphen, dash
          minus signs: FE63, 207B (super), 208B (sub), 002D, 00FD (full-width)
          hyphens: 00AD (soft), 2010, 2011 (nonbreaking) ... Unicode HYPHEN?
          dashes, horizontal bars: FE58 ... UnicodeCategory.DashPunctuation

                IdentifyBy: UnicodeCategory.DashPunctuation
                SortKey: 06 81 - 06 90 (and nonspace equivalents)

        2.4 Arabic spacing and equivalents (64B-652, FE70-FE7F)
          They are part of nonspacing mark, but not equal.

                SortKey: 06 A0 - 06 A7 (and nonspace equivalents)

        3 nonprimary characters, mixed.

          ModifierSymbol, except for that are not in category 0 and "07" area
          (i.e. < 128) nor those equivalents

          NonSpacingMark which is ignorable (IsIgnorableNonSpacing())
          // 30D, CD5-CD6, ABD, 2B9-2C5, 2C8, 2CB-2CD, 591-5C2. NonSpacingMark in
          // 981-A3C. A4D, A70, A71, ABC ...

          TODO: I need more insight to write table generator.

          SortKey: 01 03 01 - 01 B6 01

          This part of MS table design is problematic (buggy): \u0592 should
          not be equal to \u09BC.

          I guess, this buggy design is because Microsoft first thought that
          there won't be more than 255 characters in this area. Or they might be
          aware of the problem but prefer table optimization.

          Ideal solutions:

          1) We should not mix those code (make things sequential) and expands
             level 2 length to 2 bytes. Instead of having direct value, we
             could use index (pointer) to zero-terminating level 2 table.

          2) Include those charactors from minor cultures here.

          If in "discriminatory mode", those tables could be still provided
          as to be compatible to Windows.

          Additionally there seems some bugs around Modifier letter collection.
          For example, 2C6 should be nonspacing diacritical character but it
          is regarded as a primary character. The same applies to Mandarin
          tone marks (2C9-2CB) (and there's a plenty of such characters).

        4 space separators and some kind of marks

        4.1 whitespaces, paragraph separator etc.
          UnicodeCategory.SpaceSeparator : 20, 3000, A0, 9-D, 2000-200B

          SortKey : 07 02 - 07 18

        4.2 some OtherSymbols: 2422-2423
        
          SortKey : 07 19 - 07 1A

        4.3 ASCII compatible marks ('!', '^', ...)
          Non-alpha-numeric < 0x7F except for [[+-<=>']]
          small compatibility equivalents -> itself, wide

        4.3 other marks
          FIXME: how to identify them?
          some Punctuations: InitialQuote/FinalQuote/Open/Close/Connector
          some OtherSymbols: 2400-2424
          3003, 3006, 2D0, 10FB
          remaining Puncuations: 9xx, 7xx
          70F (Format)

          SortKey : 07 1B - 07 F0

        5 mathmatical symbols
          InitialQuotePunctuation and FinalQuotePunctuation in ASCII
          (not Quotation_Mark property in PropList.txt ; 22, 27)

          byte area MathSymbol: 2B,3C,3D,3E,AB,B1,BB,D7,F7 except for AC
          some MathSymbol (2044, 208A, 208C, 207A, 207C)
          OtherLetter (1C0-1C2)
          2200-22FF MathSymbol except for 221E (INF. ; regarded as a number)

          SortKey : 08 02 - 08 F8

        6 Arrows and Box drawings
          09 02 .. 09 7C : 2300-237A
                        only primary differences
          09 BC ... 09 FE : 25A0-AB, 25E7-EB, 25AC-B5, 25EC-EF, 25B6-B9,
                        25BC-C3, 25BA-25BB, 25C4-25D8, 25E6, 25DA-25E5
                        21*,25*,26*,27*
                        This area contains level 2 values.
          2190- (non-codepoint order)
                note that there are many compatibility equivalents
          2500- except for 266F (#)

          SortKey : 09 02 - 09 7C, 09 BC 01 03 - 09 BC 01 13,
                    09 {BD|BE|BF} 01 {03|04}, ...
                    TODO: fill the patterns

        7 currency sumbols and some punctuations
          byte CurrencySymbols except for 24 ($)
          byte OtherSymbols (A7-B6) 
          ConnectorPunctuation - 2040 (i.e. FF65, 30FB)
          OtherPunct/ConnectorPunct/CurrencyCymbol 2020-20AC - 20AC
          OtherSymbol 3012-303F,3004,327F
          MathSymbol/OtherSymbol 2600-2767 (math = 266F)
          OtherSymbol 2440-244A, 2117
          20AC (CurrencySymbol)

          Sortey : 0A 02 - 0A FB

        8 (C) numbers
          all DecimalDigitNumber, LetterNumber, non-CJK OtherNumber.
          9F8.
          digits, in numeric order. We can use NET_2_0 CharUnicodeInfo.
          221E. (INF.)

          SortKey : 0C 02 (9F8), 0C 03 - 0C E1 (normal numbers), 0C FF (INF.)

        9 (E) latin letters (alphabets), mixing alphabetical symbols
          Alphabets, A to Z, mixing alphabetical symbols. See below.
          F8-2B8 except for (1BB-1BD and 1C0-1C3), but not sequential.
          2E0-2E3.

          For diacritical orders, see level 2.

          For 'A' it is "0E 02", for 'B' "0E 09" ... 'Z' "0E A9", ezh "0E AA".
          0E B3 (1BE), 0E B4 (298)

          There are CJK compatibility characters (3800-) and letterlike
          symbols (2100-) in those A-to-Z area, ordered by character name.

          Primary weights are sometimes culture-dependent.
                FIXME: [0E 0D], [0E 0E], [0E 4B], [0E 75], [0E B2] are unknown
                02: A
                03: C4 in sk|vi
                04: C1 in is|pl|vi
                05-08: CJKext
                09: B
                0A: C
                0B: 10D in hr|lt|lv|pl, 107 in pl
                0C: C7 in az|tr, 10D in cs|sk, 106 in hr
                0F-19: CJKext
                1A: D
                1B: 189 (African D)
                1C: 2A3 (DZ Digraph)
                1D: 1C6 (dz) in hr
                1E: 110 (D with stroke) in hr
                1F-20: CJKext
                21: E
                22: 18F=259 in az, E9 in is, 119 in pl, EA in vi, 1EBE-1EC7 in vi
                23: F
                24: CJKext
                25: G
                26: 11F in az|tr, 123 in lv
                28-2B: CJKext
                2C: H
                2D: 267 (Heng with hook)
                2E: 33CB in az, 33CA in tr
                2F-31: CJKext
                32: I
                33: CD in is, 79 in lt
                34: CJKext
                35: J
                36: K
                37-47: CJKext
                48: L
                49: 2114
                4A: 1C9 in hr
                4C: 142 in pl
                4D-50: CJKext
                51: M
                52-6F: CJKext
                70: N
                71: 2116
                72: 144 in pl
                73: F1 in es, 1CC in hr
                74: 14B
                76-7B: CJKext
                7C: O
                7D: F6 in az|hu|tr, 151 in hu, F3 in is|pl, F4 in sk|vi, 1ED0-1ED9 in vi
                7E: P
                7F-88: CJKext
                89: Q
                8A: R
                8B: 211E
                8C: 211F
                8D: 159 in cs|sk
                8E-90: CJKext
                91: S
                92: 2108
                93: 2120
                94-95: CJKext
                96: 17F (LATIN SMALL LONG S)
                97: 15F in az|tr, 161 in cs|hr|lt|lv|sk|sl, 7A,179-17C in et, 15B in pl
                98: 17E in et, 15F in ro, 15B in sl
                99: T
                9A: 2121
                9B: CJKext
                9C: 2122
                9D: 2A6
                9E: 166
                9F: U
                A0: FA in is, 1B0,1EE8-1EF1 in vi
                A1: FC in az|tr, 56,57 in et, FC,171 in hu, FB in vi
                A2: V
                A3: 2123
                A4: W
                A5: CJKext
                A6: X
                A7: Y
                A8: FD in is
                A9: Z
                AA: 292
                AB: DE in is, 17E in lt|lv, 17A in pl
                AC: E6 in da|is, 1E3 in is, 17C in pl, 17E in sl
                AD: 17E in cs|hr|sk, E5 in fi, F6,F8 in is 17A in sl
                AE: F6,F8,151 in da
                AF: E4 in fi
                B0: F6,F8,151 in fi
                B1: E5 in da, "aa" in da
                B3: 1BE
                B4: 298

        10 culture dependent letters (general)
          0F: 386-3F2 ... Greek and Coptic
                386-3CF: [0F 02] - [0F 19] (consider primary equivalents)
                3D0-3EF: [0F 40] - [0F 54]
          10: 400-4E9 ... Cyrillic.
                For 400-45F and 4B1, they are mostly UCA DUCET order.
                After that 460-481 follows, by codepoint.
                (490-4FF except for 4B1 and Cyrillic supplementary are unused.)
          11: 531-586 ... Armenian.
                Simply sorted by codepoint (handle case).
          12: 5D0-5F2 ... Hebrew.
                Codepoint order (handle case).
          13: 621-6D5 plus 670 (NonSpacingMark) ... Arabic
                Area 1:
                They look like ordered by Arabic Presentation Form B except
                for FE95, and considering diacritical equivalents maybe based
                on the primary character area (621-6D5).
                There are still some special characters: 67E,686,698,6AF ...
                which might not have equivalent characters (I wonder how they
                are inserted into the presentation form B map).

                        Solution:
                        - hamza, waw, yeh (621,624,626) are special: [13 07]
                        - For all remaining letters, get primary letter name
                          and store it into dictionary. If unique, then
                          increment index by 4 from [13 0B]
                Area 2:
                674-6D5 : by codepoint from [13 84].
          14: 901-963 exc. 93A-93D 950-954 ... Devanagari.
                For <905 codepoint order, x2 from [14 04].
                For 905-939 codepoint order, x4 from [14 0B].
                For 93E-94D codepoint order, x2 from [14 DA].
          15: 982-9FA ... Bengali. Actually all UnicodeCategories except for
                NonSpacingMark, DecimalDigitNumber and OtherNumber.
                For <9E0 simple codepoint order from [15 02].
                For >9E0 simple codepoint order from [15 3B].
          16: A05-A74 exc. A3C A4D A66-A71 ... Gurmukhi.
                The same as UCA order, x4 from [16 04].
          17: A81-AE0 exc. ABC-ABD ... Gujarati.
                Mostly equivalent to UCA, but insert {AB3,A81-A83} before AB9,
                x4 from [17 04].
          18: B00-B70 ... Oriya
                All but NonSpacingMark and DecimalDigitNumber, by codepoint.
          19: B80-BFF ... Tamil
                BD7 is special : [19 02].
                B82-B93 (vowels) : x2 from [19 0A].
                B94 (vowel AU) : [19 24]
                For consonant order Windows has native Tamil order which is
                different from UCA.
                http://www.nationmaster.com/encyclopedia/Tamil-alphabet
                (The order is still different in "Grantha" order from TAM.)
                So, we should just hold constant array for consonants.
                And put them in order, x4 form [19 26].
                BBE-BCC : SpacingCombiningMark and BC0 ... x2 from [19 82].
          1A: C00-C61 ... Telugu.
                C55 and C56 are ignored (C5x line and remaining part of C6x
                line just look like ignored).
                C60 and C61 are specially placed. C60 after C0B, C61 after C0C.
                Except for above, by codepoint, x3 from [1A 04].
          1B: C80-CE5 ... Kannada.
                CD5,CD6 (and CE6-CEF: DecimalDigitNumber) are ignored.
                by codepoint, 3x from [1B 04].
          1C: D02-D40 ... Malayalam.
                by simple codepoint from [1C 02].
          (1D: Sinhala ... totally ignored?)
          1E: E00-E44 ... Thai.
                preceding vowels (E40-E44) by codepoint [1E 02 - 1E 06]
                consonants (E01-E2A) by codepoint, x6 from [1E 07].
          1F: E2B-E5B,E80-EDF ... Thai / Lao. (Thai breaks the category wall.)
                Thai:
                remaining consonants (E2B-E2E) by codepoint, x6 from [1E 07].
                remaining vowels (E2F-E3A) by codepoint.
                E45,E46,E4E,E4F,E5A,E5B
                Lao:
                E80-EDF by codepoint from [1F 02].
          21: 10A0-10FF ... Georgian
                Mostly equal to UCA order, but swap 10E3 <-> 10F3,
                x5 from [21 05].

        11 (22) japanese kana letters and symbols, not in codepoint order

          For single character, the sortkeys look like:
          - Katakana normal A, Half Width (FF71) : FF 02 C4 FF C4 FF 01 00
          - Katakana normal A, Full Width (30A2) : FF C4 FF 01 00
          - Hiragana normal A, Full Width (3042) : FF FF 01 00

          Actually for level 4 weights, there is a different rule (see
          "level 4" format above).

          There is also 32D0 (normal katakana A with circle) that have
          diacritic difference.

          For primary weights, 'A' to 'O' are mapped to 22-26, 'Ka' to 'Ko'
          are to 2A-2E, 'Sa' to 'So' are to 32-36 ... and follows.
          'Nn' is special: [22 80].

          After Kana characters, there are CJK compat characters.
          From 22 97 01 01 01 01 00 (3349) to 22 A6 01 01 01 01 00 (333B) are
          sorted in JIS table order (CP932.TXT). Remaining square characters
          are maybe sorted in Alphabetic order.

          UCA DUCET also does not apply here.

        12 (23) bopomofo letters
                3105-312C: simple codepoint order from [23 02].

        13 culture dependent letters 2
                710-72C : Estrangela (ancient Syriac).
                        codepoint order.
                        711 is excluded (superscript).
                        714,716,71C,724 and 727 are "alternative" characters.
                        SortKey: [24 0B]-[24 60], by x where x is 2 for those
                        which is "alternative" defined above, otherwise 4.

                780-7A5 : Thaana
                        Equals to UCA order, x2 from [24 6E].

        (Maybe we should add remaining minor-culture characters here. Tibetan,
        Limbu, Tagalog, Hanunoo, Buhid, Tagbanwa, Myanmar, Kumer, Tai-Le,
        Mongolian, Cherokee, Canadian-Aboriginal, Ogham, Runic are ignored)

        14 (41-45) surrogate Pt.1

        15 (52 02-7E C8) hangul, mixing combined ones

          It starts from 1100. After width-insensitive equivalents, those
          syllables (from AC00) follow (until <del>AE4B</del>D7A3).
          It follows kinda based on some formula (sometimes it looks not
          e.g. 1117). FIXME: this area should be clarified more.

          Hangle Syllables should not be filled in the table. Instead, they
          can be easily computed by the following formulum:

                // rc is the codepoint for the input Syllable
                // (p holds "category << 8 + level1weight")
                int ri = ((int) rc - 0xAC00) + 1;
                ushort p = (ushort)
                        ((ri / 254) * 256 + (ri % 254) + 2);

          Hangul Jamo cannot be filled in the table directly, since
          U+1113 - U+159 holds additional primary key bytes.
          FIXME: find out how they can be computed.
          See http://dev.icu-project.org/cgi-bin/viewcvs.cgi/*checkout*/icuhtml/design/collation/ICU_collation_design.htm?rev=HEAD&content-type=text/html#Hangul_Implicit_CEs

        16 (9E 02-F1 E4) CJK

           9E 02-F0 B4 [3192-319F,3220-3243,3280-32B0,4E00-9FA5] : CJK mark,
                parenthesized CJK (part), circled CJK (part), CJK ideograph.
                Ordered but condidering compatible characters (i.e. there is
                no other way than having massive mapping).
           F0 B5-F1 E4 [F900-FA2D]. CJK compatibility ideograph.

           LAMESPEC: in the latest spec CJK ends at 9F BB. Since MS table
           joins these two categories without any consideration, it is
           impossible to insert those new characters without breaking binary
           compatibility.

        17 (E5 02-FE 33) PrivateUse.

           In fact it overlaps to CJK characters (maybe layout design failure).

        18 (F2 01-F2 31) surrogate Pt.2

           In fact it overlaps to PrivateUse (maybe layout design failure).

        19 (FE FF 10 02 - FE FF 29 E9) CJK extensions

           3400-4DB5. Ordered.

           They should be computed, since this range should be anyways
           checked (to not directly acquire the sortkey values but needs
           FE FF part) and anyways it can be computed.

        20 (FF FF 01 01 01 01 00) special.
           Japanese extender marks:
                3005, 3031, 3032, 309D, 309E, 30FC, 30FD, 30FE, FF70

           LAMESPEC: In native context Microsoft's understanding of Japanese 
           3031 and 3032 is wrong. They can never be used to repeat *just
           previous one* character, but are usually used to repeat two or
           more characters. Also, 3005 is not always used to repeat exactly
           one character but sometimes used to repeat two (or possibly more)
           characters.

           Arabic shadda: FE7C (isolated), FE7D (medium)
           (Actually they are not extender in Unicode PropList.txt)


        - by UnicodeCategory -

        DashPunctuation         6 (no exception)
        DecimalDigitNumber      C (no exception)
        EnclosingMark           1 E (no exception)
        Format                  7 (only 70F)
        LetterNumber            C (no exception)
        LineSeparator           7 (only 2028)
        ParagraphSeparator      7 (only 2029)
        PrivateUse
        SpaceSeparator          7 (no exception)
        Surrogate

        OtherNumber             C(<3192), 9E-A7 (3124<)

        Control                 6 except for 9-D (7)
        FinalQuotePunctuation   7 except for BB (8)
        InitialQuotePunctuation 7 except for AB (8)
        ClosePunctuation        7 except for 232A (9)
        OpenPunctuation         7 except for 2329 (9)
        ConnectorPunctuation    7 except for FF65, 30FB, 2040 (A)

        OtherLetter             1, 7, 8 (1C0-1C2), C, 12-FF
        MathSymbol              8, 9, 6, 7, A, C
        OtherSymbol             7, 9, A, C, E, F, <22, 52<
        CurrencySymbol          A except for FF69,24,FF04 (7) and 9F2,9F3 (15)

        LowercaseLetter         E-11 except for B5 (A) and 1BD (C)
        TitlecaseLetter         E (no exception)
        UppercaseLetter         E,F,10,11,21 except for 1BC (C)
        ModifierLetter          1, 7, E, 1F, FF
        ModifierSymbol          1, 6, 7
        NonSpacingMark          1, 6, 13-1F
        OtherPunctuation        1, 7, A, 1F
        SpacingCombiningMark    1, 14-22

*** Culture dependent design

        (To assure this section, run the simple dumper code shown above,
        with all the supported cultures.)

**** primary cultures and non-primary cultures

        This code is used to iterate character dump through all cultures,
        using sort key dumper put above.

        public static void Main ()
        {
                foreach (CultureInfo ci in CultureInfo.GetCultures (
                        CultureTypes.AllCultures)) {
                        ProcessStartInfo psi = new ProcessStartInfo ();
                        psi.FileName = "../allsortkey.exe";
                        psi.Arguments = ci.Name;
                        psi.RedirectStandardOutput = true;
                        psi.UseShellExecute = false;
                        Process p = new Process ();
                        p.StartInfo = psi;
                        p.Start ();
                        string s = p.StandardOutput.ReadToEnd ();
                        StreamWriter sw = new StreamWriter (ci.Name + ".txt", false, Encoding.UTF8);
                        sw.Write (s);
                        sw.Close ();
                }
        }

        For each sub culture (that has a parent culture), its collation
        mapping is identical to that of its parent, except for az-AZ-Cyrl.

        Additionally,

        - zh-CHS = zh-CN = zh-SG = zh-MO : pronounciation
        - zh-TW = zh-HK = zh-CHT : stroke count
        - da = no
        - fi = sv
        - hr = sr

        (UCA implies that there are some cultures that sorts alphabets from
        large to small, but as long as I see there is no such CultureInfo.)

**** Latin characters and NonSpacingMark order tailorings

        div : FDF2 is 24 83 01 01 01 01 00 (only 1 difference)
        syr : some NonSpacingMarks are totally ignorable.
        tt,kk,mk,az-AZ-Cyrl,uk : cyrillic difference
        az,et,lt,lv,sl,tr,sv,ro,pl,no,is,hu,fi,es,da : latin difference
        fr : 1C4-1C6.
        sk,hr,cs : latin and NonSpacingMark differences

        ja,ko : 5C

**** CJK character order tailorings

        <how many tables?>

        There are five different CJK orderings:
        default, ko(-KR), ja(-JP), zh-CHS and zh-CHT
        They have very different CJK mapping for each.

        Since they seems based on traditional encodings, we are likely to
        provide other constant tables and switch depending on the culture.

        <what characters are different from the invariant culture?>

        ko : CJK layout difference (52 -> 80)
        ja,zh-CHS,zh-TW : dash (5C), CJK layout difference.

        Target characters are : CJK misc (3190-), Parenthesized CJK
        (3200-), CJK compat (3300-), CJK ideographs (4E00-),
        CJK compat ideograph (F900-), Half/Full width compat (FF00-)

        Additionally for Korean: Jamo (1100-), Hangle syllables (AC00)

        <how do they consist of?>

        Japanese CJK order looks based on JIS table order. Those characters
        which are also in JIS table are moved to 80 xx. Those which are *not*
        in JIS table are left as is (9E-FE).

        Additionally, Windows has different order for characters below:
        4EDD,337B,337E,337D,337D,337C
        They come in front of the first CJK character.

        Maybe Korean CJK order respects KS C 5619. Note that Korean mixes
        Hangul and CJK in their order so it's not flat order without indexes
        (thus, for CJK they are not computable). Also, there is an extra
        level2 values for Korean CJK map.

        For some Chinese such as zh-CHS, character order is based on pinyin.
        And for remaining Chinese such as zh-TW, it is stroke count based.

        CLDR of unicode.org has reference ordering of those characters, so
        our collation table extracts the sorting order from it.
        http://www.unicode.org/cldr/

**** Accent evaluation order

        With French cultures, diacritical marks are counted in reverse order.
        French ordering does not affect only on some diacritics (Japanese
        voice mark is not affected - FIXME: I doubt it, because the algorithm
        does not seem to allow it).

        Some other cultures might also have different ones, but not obvious.


** Mono implementation plans

*** Collator

        CompareInfo contains many overloaded methods that are just for 
        convenience. This class contains almost only required members.

        This class also provices access to tailoring information which is
        culture instance dependent:

        - French sorting
        - contractions/expansions - returns contraction or expansion
        - diacritical remapping
        - CJK custom mapping

        For data area, see CollationDataStructures.txt for now.

*** UnicodeTable (for now MSCompatUnicodeTable)

        Provides several access to character information with related to
        the collation element table (of our own).
        FIXME: I want to fix some bugs in Windows collation table especially
        to not ignore some characters, but it requires table modification
        which results in further memory allocation. Maybe it would be done
        as a patch for the runtime (or classlib) sources.

        - ignorable, ignorable nonspace, normalize width, normalize kanatype
        - level 4 sortkey provision method(s)

**** character comparison

        Since composite character is likely to *not have* equivalent
        codepoint, character comparison could not just be done by expecting
        "resulting char" value.
        In contrast, since composite character is likely to *do have*
        equivalent codepoint, character comparison could not also just be done
        by comparing "source char" value.

***** future optimizations

        From where those codepoints differ, for each strings it adjusts the
        position so that it represents exactly one character element. That is,
        find primary character as the start of the range and the last
        nonprimary character as the end of the range.

        Once Compare() adjusted the character location to be valid
        comparison position, further comparison is done as usual comparison,
        i.e. sortkey comparison considering comparisonLevel.

**** Characters in the table / characters computed

        Currently I plan not to contain following characters in the table
        but compute on demand:

        - PrivateUse
        - Surrogate

**** CJK Unified Ideographs

        For CJK unified ideographs, I had to make those culture-dependent
        tables in memory. Since they came from some classical encodings, they
        are not computed. Thus, they are in separate table.

**** Level 4: Kana type

        The table does not contain level 4 (kanatype) properties for
        the whole characters. They can be simply computed.

**** Level 3: Case/Width properties

        Case properties will be stored as a byte array, with limited areas of
        codepoint (cp < 3120 || FE00 < cp).

        For Hangul characters, it will be computed by codepoint areas.

**** Level 2: Diacritical properties

        The table will be composed as a byte for a character. If we provide
        non-buggy mode (Windows is buggy here by design; it just sums
        secondary weight values up), the values will come from UCA and
        non-blocking check will be introduced.

        Note that Japanese voice marks are considered at level 2 but no need to
        have maps.


** Reference materials

        Developing International Software for Windows 95 and Windows NT
        Appendix D Sort Order for Selected Languages
        http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24BF.asp

        UTR#10 Unicode Collation Algorithm (It is still informative)
        http://www.unicode.org/reports/tr10/

        UAX#15 Unicode Normalization
        http://www.unicode.org/reports/tr15/
        especially its canonical/compatibility equivalent characters might
        be informative to get those equivalent characters.
        
        To know which character can be expanded, Unicode Character Database
        (UCD) is informative (it's informative but not normative to us)
        http://www.unicode.org/Public/UNIDATA/UCD.html

        Decent char-by-char explaination is available here:
        http://www.fileformat.info/info/unicode/

        Wine uses UCA default element table, but has windows-like character
        filterings support in their LCMapString implementation:
        http://cvs.winehq.com/cvsweb/wine/dlls/kernel/locale.c
        http://cvs.winehq.com/cvsweb/wine/libs/unicode/sortkey.c

        Mimer has decent materials on culture specific collations:
        http://developer.mimer.com/collations/

        This is written in Japanese, but awesome analysis on MS Access
        string sorting:
        http://www.asahi-net.or.jp/~ez3k-msym/comp/acccoll.htm